On Generic Automorphisms

ERMEK NURKHAIDAROV

Department of Mathematics

Pennsylvania State University

Mont Alto, PA 17237

USA

Abstract: In this article we investigate generic automorphisms of countable models. Hodges et al. 1993 intro-

duces the notion of SI (small index) generic automorphisms. They used the existence of small index generics to

show the small index property of the model. Truss 1989 defines the notion of Truss generic automorphisms. An

automorphism fof Mis called Truss generic if its conjugacy class is comeagre in the automorphism group of M.

We study the relationship between these two types of generic automorphisms. We show that either the countable

random graph or a countable arithmetically saturated model of True Arithmetic have both SI generic and Truss

generic automorphisms. We prove that the dense linear order has the small index property and Truss-generic auto-

morphisms but it does not have SI generic automorphisms. We also construct an example of a countable structure

which has SI generics but it does not have Truss generics.

Key-Words: The small index property, countable models, dense linear order, generic automorphism, random

graph, True Arithmetic, comeagre conjugacy class.

Received: March 14, 2023. Revised: October 13, 2023. Accepted: November 14, 2023. Published: January 26, 2024.

1 Introduction

Throughout this paper Mis to be a countable infi-

nite model. We can consider its automorphism group

Aut(M)as a topological group by letting the stabiliz-

ers of finite subsets of Mbe the basic open subgroups.

We will use the notation G=Aut(M). If A⊂M

we write

GA={g∈G:g(a) = afor all a∈A},

so GAis the pointwise stabilizer of A.

The paper [1] introduces the following definition

of generic automorphism.

Definition 1. [1] An automorphism fof Mis called

Truss generic if its conjugacy class [f]G={fg=

g−1fg :g∈G}is comeagre in G.

A subgroup Hof Gis said to have small index in G

if |G:H|<2ω, and large otherwise. If a∈M, then

there is a bijection between the set of the right cosets

of Gawith {g(a) : g∈G}. Hence Ga, and so any

open subgroup of G, has small index in G. We say

that Mhas the small index property if the converse

holds: that is, every subgroup H≤Gof small index

is open in G.

If Ghas the small index property, then the topol-

ogy on Gcan be recovered from its abstract group

structure. This has applications in reconstructing a

structure from its automorphism group.

The paper [2] introduces the notion of SI generic

automorphisms, which are used to show that Mhas

the small index property.

Definition 2. [2] A base for Mis a set B(M)of sub-

sets of Msatisfying:

1. GAis open in Gfor all A∈B(M),

2. if A∈B(M)and g∈Gthen g(A)∈B(M).

Definition 3. [2] Let B(M)be a base for M, and let

0< n < ω. We say that (g1, . . . , gn)∈Gnis B(M)-

automorphism, if the following hold.

1. If A∈B(M)then

{GB:A⊆B∈B(M), gi(B) = Bfor all i≤n}

is a base of open neighborhoods of 1 in G.

2. Let A∈B(M)be such that gi(A) = A, 1≤i≤

n. Let B∈B(M), A ⊆B, and let hi∈Aut(B)

extend gi|A(1≤i≤n). Then there is α∈GA

such that gα

i=α−1giαextends hi(1≤i≤n).

If it is needed one can add extra requirements on

automorphisms (g1, . . . , gn)in Definition 3. For ex-

ample, when working with models of Peano Arith-

metic, [3] defines (g1, . . . , gn)∈Gnto be B(M)-

automorphism with additional conditions: gi|Bis ex-

istentially closed in the part 1 of the definition and

gi|Ais existentially closed in the part 2.

We will need the following property of B(M)-

automorphisms.

Lemma 4. [2] Let B(M)be a base for M, and let

(g1, . . . , gn),(h1, . . . , hn)be B(M)-automorphisms

(0< n < ω). Let B∈B(M)and suppose that

gi|B=hi|Bfor each i≤n. Then there is f∈GB

such that gf

i=hifor all i≤n.

Definition 5. [2] We say that Mhas SI generic au-

tomorphisms, if there exists a base B(M)for M

such that for all non-zero n<ω, the set of B(M)-

automorphisms of Gnis comeagre in Gn.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2024.23.8

Ermek Nurkhaidarov

E-ISSN: 2224-2880

Volume 23, 2024

Theorem 6. [2] If Mis a countable model with SI

generic automorphisms, then Mhas the small index

property.

The paper [2] and [4] show existence of SI generic

(and therefore the small index property) for the count-

able random graph and for ω-stable ω-categorical

structures. The paper [3] is using SI generics to

show that countable arithmetically saturated models

of Peano Arithmetic have the small index property.

In [5] it is noticed that if Mhas both SI and Truss

generic automorphisms, then they coincide (because

they both are comeagre). Hence there are four pos-

sibilities for a countable model: to have both SI and

Truss generics; to have SI but not Truss generics; to

have Truss but not SI generics; and to have neither SI

nor Truss generics.

The paper [2] shows that the countable random

graph has SI generic automorphisms and [1] proves

that the countable random graph has Truss generic au-

tomorphisms.

The paper [3] proves that if Mis a countable arith-

metically saturated model of Peano Arithmetic then

Mhas SI generic automorphisms. The paper [5]

shows that if Mis a countable arithmetically saturated

model of True Arithmetic then Mhas Truss generics.

Hence we have the following result:

Example 7. Let Mbe either the countable random

graph or a countable arithmetically saturated model

of True Arithmetic. Then Mhas both SI generic and

Truss generic automorphisms.

It is an open question whether there exists a count-

able arithmetically saturated model of Peano Arith-

metic which does not have Truss generic automor-

phisms. The paper [5] shows that existence of Truss-

generics for arithmetically saturated models of Peano

Arithmetic is very closely tied to Hedetniemi’s Con-

jecture – a well known open conjecture in the chro-

matic theory of graphs (see for example [6]).

In [7] the notion of SI generic automorphisms is

introduced. They show that every uncountable satu-

rated structure has SI generics.

2 Dense Linear Order

It is known that the countable model of the dense lin-

ear order without end-points has the small index prop-

erty and has Truss generic automorphisms ([1], [8]).

In this section we show that such model has no SI

generic automorphisms.

Let ⟨Q, <⟩be the countable model of the dense

linear order without end-points. It is not difficult to

show the next lemma.

Lemma 8. Let B⊂Qbe finite and let a∈Q\B.

Then there exists f∈Aut(Q)such that f∈GBand

f(a)=a.

The following result is not difficult either.

Lemma 9. Let B⊂Qbe such that GBis open. Then

Bis finite.

Proof. Assume not, that Bis infinite. Since GBis

open there is a finite set A⊂Qsuch that GAis a

subgroup of GB. Let b∈B\A. By Lemma 8 there

exists f∈GAsuch that f(b)=b. Hence f∈ GB,

but f∈GAwhich is contradiction.

Corollary 10. If Bis a base for Qand if B∈Bthen

Bis finite.

Proof. Definition 2 requires GBto be open for every

B∈B. Thus by Lemma 9 every B∈Bis finite.

Lemma 11. Let B⊂Qbe finite and let f∈Gbe

such that f(B) = B. Then f(b) = bfor every b∈B.

Proof. Assume that there is b0∈Bsuch that f(b0)=

b0. Then there is a finite sequence b0, b1, . . . , bn−1∈

Bsuch that

f(b0) = b1, f(b1) = b2, . . . , f (bn−2) = bn−1, f (bn−1) =b0.

Now, if b0< b1then b0< b1< b2< . . . < bn−1<

b0which is contradiction. The other case when b0>

b1is similar.

Statement 12. ⟨Q, <⟩does not have SI generic auto-

morphisms.

Proof. Let Bbe a base for ⟨Q, <⟩. Assume f∈G

is B-generic and f(A) = Afor some A∈B. By

Definition 3

H={GB|A⊂B∈B, f(B) = B}

is a base of open neighborhoods of 1 in G. If B∈B

and f(B) = Bthen by Lemma 10 Bis finite and by

Lemma 11 f∈GB. Hence

H={GB|A⊂B∈B, f ∈GB}.

Because His a base of open neighborhoods of 1 in

G: for every finite C⊂Qthere exists B⊂Qsuch

that GC≥GB∈H. Hence for every finite C⊂Q

there exists B∈Bsuch that A, C ⊆B, GB∈H.

Therefore

∪

A⊂B∈B,f∈GB

B=Q.

Thus fis the identity map and the proposition fol-

lows.

The papers [1], [8] prove the next result about

the countable model of the dense linear order without

end-points.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2024.23.8

Ermek Nurkhaidarov

E-ISSN: 2224-2880

Volume 23, 2024

Statement 13. [1], [8] ⟨Q, <⟩has the small index

property and Truss generic automorphisms.

By combining Statement 12 and Statement 13 we

conclude.

Theorem 14. ⟨Q, <⟩has the small index property

and Truss-generic automorphisms but ⟨Q, <⟩does

not have SI generic automorphisms.

Notice that we define SI generic for n-tuples of

automorphisms, n < ω. Similarly, we can also say

that an n-tuple (g1, g2, ..., gn)∈Gnis Truss generic

if the set {(gf

1, gf

2, . . . , gf

n) : f∈G}of its conju-

gates is a comeager in Gn. An unpublished result of

I.Hodkinson shows that ⟨Q, <⟩has no Truss generic

2-tuples of automorphisms, by Statement 12 it does

not have SI generic 2-tuples of automorphisms either.

3 A Few Examples

As we have mentioned earlier, there are four possi-

bilities for a countable model: to have both SI and

Truss generics; to have SI but not Truss generics; to

have Truss but not SI generics; and to have neither

SI nor Truss generics. We have already found mod-

els with both SI and Truss generics: the countable

random graph or a countable arithmetically saturated

model of True Arithmetic (Example 7). In the pre-

vious chapter we have shown that ⟨Q, <⟩has Truss-

generic automorphisms but ⟨Q, <⟩does not have SI

generic automorphisms. In this chapter we address

the other two remaining possibilities.

Let us consider a model Q× {0,1}where each

copy of Qis the countable model of the dense lin-

ear order without end-points. An automorphism of

Q×{0,1}preserves the partition {Q×{0},Q×{1}}

and is order preserving on each copy of Q. Then ev-

ery automorphism of Q×{0,1}either fixes each copy

of Qsetwise or sends Q× {0}to Q× {1}. We no-

tice that Q× {0,1}cannot have Truss generics. By a

similar argument as in the previous section we could

show Q× {0,1}has no SI generics. Therefore we

have an example of structure with neither Truss nor

SI generics.

Example 15. Q× {0,1}has neither Truss nor SI

generic automorphisms.

Notice that in Example 15 instead of Q×{0,1}we

might have considered Q×{0,1, . . . , n −1}, n < ω.

By a similar argument Q× {0,1, . . . , n −1}, n < ω

does not have Truss generics. On the other hand Q×ω

behaves differently, Q×ωhas Truss generics. See [1]

for the details.

Our next goal is to find a model with SI generics

but without Truss generics. We need the following

result.

Theorem 16. [2] Let Mbe a countable ω-stable ω-

categorical structure. Then Mhas SI generics.

Example 17. Let Mbe a countable ω-stable ω-

categorical structure. Then M× {0,1}has SI gener-

ics but it does not have Truss generics.

Proof. Let Mbe a countable ω-stable ω-categorical

structure. Since Mis countable ω-stable ω-

categorical then M×{0,1}is also countable ω-stable

ω-categorical. By Theorem 16 M× {0,1}has SI

generics. An automorphism of M× {0,1}preserves

the partition {M× {0}, M × {1}}. Thus every au-

tomorphism of M× {0,1}either fixes each copy of

Msetwise or sends M× {0}to M× {1}. We notice

that M× {0,1}cannot have Truss generics.

[2] and [4] show that the countable random graph

has an amalgamation base. [2] proves that if Mis

countable ω-categorical with an amalgamation base

then it has SI generics. Similar argument might be

applied to R× {0,1}. It can be shown that the base

consisting of finite sets is an amalgamation base for

R× {0,1}. Since R× {0,1}is ω-categorical, then,

using the mentioned result from [2], R× {0,1}has

SI generics. R× {0,1}does not have Truss generics

by the same argument as before. Hence we obtain the

following result.

Example 18. Let Rbe the countable random graph.

Then R× {0,1}has SI generics but it does not have

Truss generics.

4 Conclusion

Two types of generic automorphisms are defined

somewhat similar. Indeed if a model has both of SI

generics and Truss generics, they coincide. If Mis ei-

ther the countable random graph or a countable arith-

metically saturated model of True Arithmetic, then M

has both SI generic and Truss generic automorphisms.

We prove that the dense linear order has the small in-

dex property and Truss-generic automorphisms but it

does not have SI generic automorphisms. We also

construct examples: a countable structures which has

SI generics but it does not have Truss generics; a

countable structure which has no SI generics but it

has Truss generics; a countable structures which has

neither SI generics nor Truss generics.

References:

[1] Truss, J.K., Generic automorphisms of homo-

geneous structures, Proc. London Math. Soc.,

Vol.64, 1992, pp. 121–141.

[2] Hodges, W. and Hodkinson, I. and Lascar, D.

and Shelah, S., The small index property for ω-

stable ω-categorical structures and for the random

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2024.23.8

Ermek Nurkhaidarov

E-ISSN: 2224-2880

Volume 23, 2024

graph, J. London Math. Soc., Vol.48, no.2, 1993,

pp. 204–218.

[3] Lascar, D., The small index property and recur-

sively saturated models of Peano arithmetic, Au-

tomorphisms of first-order structures, 1994, pp.

281–292.

[4] Hrushovski, E., Extending partial automorphisms

of graphs, Combinatorica, Vol.12, 1992, pp. 411–

416.

[5] Schmerl, J.H., Generic automorphisms and graph

coloring, Discrete Mathematics, Vol.291, No.1-3,

2005, pp.235-242.

[6] Jensen, T.R. and Toft, B., Graph Coloring Prob-

lems, Wiley, 1995.

[7] Lascar, D. and Shelah, S., Uncountable saturated

structures have small index property, Bull. Lon-

don Math. Soc., Vol.25, No.2, 1993, pp. 125–131.

[8] Truss, J.K., Infinite permutation groups; sub-

groups of small index, J. Algebra, Vol.120, 1989,

pp. 494–515.

Contribution of Individual Authors to the

Creation of a Scientific Article (Ghostwriting

Policy)

Ermek Nurkhaidarov is the single author in the

present research, at all stages from the formulation of

the problem to the final findings and solution.

Sources of Funding for Research Presented in a

Scientific Article or Scientific Article Itself

No funding was received for conducting this study.

Conflicts of Interest

The authors have no conflicts of interest to

declare that are relevant to the content of this

article.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2024.23.8

Ermek Nurkhaidarov

E-ISSN: 2224-2880

Volume 23, 2024