Local embeddability
For an arbitrary class of algebraic structures we consider a notion of a structure locally embeddable to structures of the class. This generalizes the notion of a group locally embeddable to finite groups studied by Vershik and Gordon. We give various model-theoretic characterizations of such struct...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2012
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/152225 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Local embeddability / O. Belegradek // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 14–28. — Бібліогр.: 12 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152225 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1522252019-06-10T01:26:06Z Local embeddability Belegradek, O. For an arbitrary class of algebraic structures we consider a notion of a structure locally embeddable to structures of the class. This generalizes the notion of a group locally embeddable to finite groups studied by Vershik and Gordon. We give various model-theoretic characterizations of such structures. Some of them generalize known group-theoretic results. 2012 Article Local embeddability / O. Belegradek // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 14–28. — Бібліогр.: 12 назв. — англ. 1726-3255 2010 MSC:03C60, 20A15. http://dspace.nbuv.gov.ua/handle/123456789/152225 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
For an arbitrary class of algebraic structures we consider a notion of a structure locally embeddable to structures of the class. This generalizes the notion of a group locally embeddable to finite groups studied by Vershik and Gordon. We give various model-theoretic characterizations of such structures. Some of them generalize known group-theoretic results. |
| format |
Article |
| author |
Belegradek, O. |
| spellingShingle |
Belegradek, O. Local embeddability Algebra and Discrete Mathematics |
| author_facet |
Belegradek, O. |
| author_sort |
Belegradek, O. |
| title |
Local embeddability |
| title_short |
Local embeddability |
| title_full |
Local embeddability |
| title_fullStr |
Local embeddability |
| title_full_unstemmed |
Local embeddability |
| title_sort |
local embeddability |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152225 |
| citation_txt |
Local embeddability / O. Belegradek // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 1. — С. 14–28. — Бібліогр.: 12 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT belegradeko localembeddability |
| first_indexed |
2025-07-13T02:35:24Z |
| last_indexed |
2025-07-13T02:35:24Z |
| _version_ |
1837497454312816640 |
| fulltext |
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics SURVEY ARTICLE
Volume 14 (2012). Number 1. pp. 14 – 28
c© Journal “Algebra and Discrete Mathematics”
Local embeddability
Oleg Belegradek
Communicated by R. I. Grigorchuk
Abstract. For an arbitrary class of algebraic structures we
consider a notion of a structure locally embeddable to structures of
the class. This generalizes the notion of a group locally embeddable
to finite groups studied by Vershik and Gordon. We give various
model-theoretic characterizations of such structures. Some of them
generalize known group-theoretic results.
Introduction
In [12] a notion of a group locally embeddable to finite groups had
been introduced and studied. A group G is called locally embeddable into
finite groups (for short, G is a LEF-group) if for any finite subset S of G
there are a finite group H and a map φ : G → H such that φ is injective
on S, and φ(ab) = φ(a)φ(b) for all a, b ∈ S. It is mentioned in [12] that
this notion is a special case of some very general notion in model theory [7].
Apparently, the authors had in mind the following notion considered in [7,
§7.2]: an algebraic structure M is said to be locally embeddable into a
class of structures K if any finite reduct of any finite submodel of M is
embeddable into a K-structure.
In the present paper we consider, for an arbitrary class of structures K,
a notion of a structure locally embeddable into K (a LEK-structure, for
short) in the spirit of the definition of a LEF-group in [12]. This is a version
of the above definition from [7] but looks more algebraic because does not
2010 MSC: 03C60, 20A15.
Key words and phrases: local embeddability, universal theory, ultraproduct,
limit structure.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 15
refer to the relational structure associated with a given algebraic structure.
We present a proof that the LEK-structures are exactly the models of
the universal theory of the class K, or, equivalently, the substructures
of ultraproducts of K-structures. Implicitely, these results are contained
in [7]. In fact, the characterization of LEK-structures as models of the
universal theory of K has its roots in Maltsev’s idea of using compactness
theorem for obtaining local theorems in group theory [6], which was the
first application of logic to algebra.
The notions of sofic and hyperlinear groups, which are being actively
studied in the last years (see [10, 11]), are based on the same idea, but
with ultraproducts of metric structures instead of classical ones.
Under the assumption that there exists a so called universal locally
K-structure, we show that the LEK-structures can be characterized as
substructures of ultrapowers of locally K-structures. In particular, the
LEF-groups are exactly the subgroups of ultrapowers of locally finite
groups, and the groups locally embeddable into free groups are exactly
the subgroups of ultrapowers of the free group of rank two.
Any locally residually finite group is a LEF-group; for finitely presented
groups the converse is also true [8, 12]. We show that these results can be
generalized from the subclass of finite groups of the variety of all groups
to any subclass of any quasi-variety of algebraic structures.
In [3, 1, 2] a metric space of groups with a fixed set of n generators was
considered. We show that this is a special case of a general construction of
the Stone topology on the set of ultrafilters of a Boolean algebra. Since for
any language L the ultrafilters of the Boolean algebra of all quantifier-free
L-formulas in n free variables can be identified with the isomorphism
types of marked n-generated L-structures, one can define a Stone topology
on the class of these isomorphism types, and this topology is induced by
a natural metric.
We show that the marked n-generated models of the universal theory
of the class K are exactly the so called K-limit marked n-generated
structures, the members of the closure of the marked n-generated K-struc-
tures. Versions of this result are known for the class of finite groups
(the n-generated LEF-groups are exactly the limits of n-generated finite
groups [12]), and for the class of free groups (the limit groups are exactly
the finitely generated subgroups of ultraproducts of free groups [2]).
All definitions and facts from model theory that we use in the paper
can be found in [4, 7].
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
16 Local embeddability
1. Local embeddability into a class of structures
We call an algebraic structure in a language L an L-structure, and
members of a class K of L-structures K-structures.
Let M and N be L-structures, S a subset of M , and L′ a sublanguage
of L. We call a map φ : M → N an (L′, S)-embedding of M into N if
• φ is injective on S,
• φ(cM ) = cN ,
• φ(fM (a1, . . . , an)) = fN (φ(a1), . . . , φ(an)),
• (a1, . . . , an) ∈ PM iff (φ(a1), . . . , φ(an)) ∈ PN ,
for a1, . . . , an ∈ S, and any L′-constant symbol c, function L′-symbol f ,
and relation L′-symbol P of arity n ≥ 1. Clearly, an (L,M)-embedding
of M into N is just an ordinary embedding of M into N .
For a class of L-structures K, an L-structure M is said to be locally
embeddable into K if, for any finite subset S of M and any finite sub-
language L′ of L, there is an (L′, S)-embedding of M into a K-structure
N (depending on L′ and S). For short, we call such structures M LEK-
structures.
For example, let L be the language of groupoids {·}, and K be a class
of groupoids. Then a groupoid M is a LEK-groupoid iff for every finite
subset S of M there is a groupoid N ∈ K and a map φ : M → N such
that φ is injective on S, and φ(ab) = φ(a)φ(b) for all a, b ∈ S.
Note that if K is a class of semigroups then any LEK-groupoid M is
a semigroup. Indeed, let a, b, c ∈ M . For
S = {a, b, c, ab, bc, (ab)c, a(bc)}
there is an S-embedding φ of M into a semigroup N . We have
φ(a(bc)) = φ(ab)φ(c) = (φ(a)φ(b))φ(c)
= φ(a)(φ(b)φ(c)) = φ(a)φ(bc) = φ(a(bc))
in N . Then (ab)c = a(bc) in M because φ is injective on S.
However, if K is a class of groups in the language of grouppoids, a
LEK-groupoid can be not a group: an example is any subgroupoid of a
K-group which is not a group.
Let K be a class of groups in the language of groups L = {·,−1 , e}.
Then, by definition, an L-structure G is a LEK-structure iff for every
finite subset S of G there is a K-group H and an injective on S map
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 17
φ : G → H such that φ(ab) = φ(a)φ(b) and φ(a−1) = φ(a)−1 for all a,
b ∈ S, and φ(eG) = eH .
In this case G is a group (and therefore in the present context we
always consider groups as {·,−1 , e}-structures but not as {·})-structures).
As above, in G the operation · is associative. For any a ∈ G we have
aeG = eGa = a and aa−1 = a−1a = eG in G. Indeed, for S = {a, a−1, eG}
there is an S-embedding φ of G into a group H. We have in H
φ(aeG) = φ(a)φ(eG) = φ(a)eH = φ(a),
and so aeG = a in G because φ is injective on S. Similarly, eGa = a in G.
Also, in H
φ(aa−1) = φ(a)φ(a−1) = φ(a)φ(a)−1 = eH = φ(eG),
and so aa−1 = eG in G because φ is injective on S. Similarly, a−1a = eG.
A finite LEK-structure in a finite language is obviously embeddable
into a K-structure. Here is an example of a finite LEK-structure in an
infinite language which is not embeddable into a K-structure.
Let L consist of unary functional symbols fi, where i < ω. Let M
be a finite L-structure of size > 1 such that fMi is the identity map for
all i. For n < ω let Mn be an L-structure with the same universe, and
such that fMn
i is the identity map iff i ≤ n. Let K = {Mn : n < ω}.
For Ln = {f0, . . . , fn}, the identity map on M is a (Ln,M)-embedding
of M into Mn; hence M is a LEK-structure. But, obviously, there is no
embedding of M into any of Mn.
2. Model-theoretic characterization of LEK-structures
First order formulas of the form ∀x1 . . . xnθ, where θ is a quantifier-free
formula, are called universal; formulas of the form ∃x1 . . . xnθ are called
existential. A formula without free variables is said to be a sentence. For a
class K of L-structures the set of all sentences that hold in all K-structures
is called the theory of K; we denote it by Th(K). The set of all universal
sentences that hold in all K-structures is called the universal theory of K;
it is denoted by Th∀(K).
A set of L-formulas Φ with free variables {xi : i ∈ I} is called satisfiable
in an L-structure M if there is a family {ai : i ∈ I} of elements of M such
that all formulas in Φ are true in M when xi takes the value ai for all
i ∈ I. We say that Φ is satisfiable if it is satisfiable in some L-structure M .
The fundamental compactness theorem asserts that a set of formulas is
satisfiable if and only if every finite subset of it is satisfiable.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
18 Local embeddability
Theorem 1. Let K be a class of L-structures, and M an L-structure.
The following are equivalent:
(i) M is a model of Th∀(K);
(ii) M is a LEK-structure;
(iii) M is embeddable into a model of Th(K).
Proof. Let M be an L-structure. Let ∆(M) be the set of all L-formulas
in variables xa, where a ∈ M , of the forms xa1
6= xa2
, P (xa1
, . . . , xan
),
¬P (xa1
, . . . , xan
), c = xa, f(xa1
, . . . , xan
) = xa that hold in M when each
xa takes the value a.
For a subset S of M and a sublanguage L′ of L, let ∆L′,S(M) be the
set of all formulas from ∆(M) with P , f , c ∈ L′ and ai ∈ S (but with a
not necessarily in S).
Lemma 1. ∆L′,S(M) is satisfiable in an L-structure N iff there is an
(L′, S)-embedding of M into N . In particular, ∆(M) is satisfiable in N
iff M is embeddable into N .
Proof. For a map φ : M → N , we say that an L-formula in variables
xa, where a ∈ M , is valid in N if it holds in N when each xa takes the
value φ(a). Let ∆ = ∆L′,S(M). It suffises to check that φ : M → N is an
(L′, S)-embedding iff ∆ holds in N . Injectivity of φ on S means validity
in N of all formulas va1
6= va2
from ∆. For P ∈ L′ and a1, . . . , an ∈ S,
the property
(a1, . . . , an) ∈ PM ⇔ (φ(a1), . . . , φ(an)) ∈ PN
means that if P (va1
, . . . , van
) or ¬P (va1
, . . . , van
) belongs to ∆ then it is
valid in N . For f ∈ L′ and a1, . . . , an ∈ S, the property
φ(fM (a1, . . . , an)) = fN (φ(a1), . . . , φ(an))
means the validity in N of the formula f(xa1
, . . . , xan
) = xa, where
a = fM (a1, . . . , an). For c ∈ L′, the property φ(cM ) = cN means the
validity in N of the formula c = xa, where a = cM .
Lemma 2. Let ∆ = ∆L′,S(M), where S and L′ are finite. The following
are equivalent:
(a) Th(K) ∪ ∆ is satisfiable;
(b) Th∀(K) ∪ ∆ is satisfiable;
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 19
(c) there is an (L′, S)-embedding of M into a K-structure.
Proof. Let x̄ be all variables that occur in ∆. By Lemma 1, (c) holds iff
∆ is satisfiable in a K-structure iff ∃x̄
∧
∆ holds in some K-structure iff
Th(K) ∪ {∃x̄
∧
∆} has a model iff Th∀(K) ∪ {∃x̄
∧
∆} has a model. The
latter iff holds because ¬∃x̄
∧
∆ is equivalent to a universal formula.
(i)⇒(ii). If M is a model of Th∀(K) then Th∀(K) ∪ ∆L′,S(M) is
obviously satisfiable in M for all finite S ⊆ M and L′ ⊆ L, and hence M
is a LEK-structure, by Lemma 1 and Lemma 2, (b)⇒(c).
(ii)⇒(iii). IfM is a LEK-structure then Th(K)∪∆L′,S(M) is satisfiable
for all finite S ⊆ M and L′ ⊆ L, by Lemma 1 and Lemma 2, (c)⇒(a).
Then, by compactness theorem, Th(K) ∪ ∆(M) is satisfiable, and hence
M is embeddable into a model of Th(K).
(iii)⇒(i) because validity of universal sentences is preserved in sub-
structures.
A class K of L-structures is called axiomatizable if K is the class
of all models of some set of L-sentences, or, equivalently, K is the class
of all models of Th(K). The class K is called universally axiomatizable
if K is the class of all models of some set of universal L-sentences, or,
equivalently, K is the class of all models of Th∀(K).
Theorem 1 explains, for example, why if L = {·,−1 , e}, and K is any
class of groups in the language L, then any LEK-structure is a group.
The reason is that the class of all groups in the language L (in contrast
with the language {·}) is universally axiomatizable.
Corollary 1. If a class K of L-structures is axiomatizable then the LEK-
structures are exactly the substructures of K-structures.
Now we give another characterization of LEK-structures in terms of
ultraproducts.
Let {Mi : i ∈ I} be a family of L-structures, and M̄ its cartesian
product. For an ultrafilter D on I, elements g and h of M̄ are called
D-equivalent if {i ∈ I : g(i) = h(i)} ∈ D. This is an equivalence relation
on M̄ ; we denote the D-equivalence class of g by g/D. Moreover, it is
easy to check that the D-equivalence is a congruence relation on M̄ ;
the quotient of M̄ modulo this congruence is called the ultraproduct of
{Mi : i ∈ I} over D and is denoted by
∏
i∈IMi/D. For example, when
all Mi are groups, the ultraproduct is nothing but the quotient group
M̄/ND, where ND is the normal subgroup of the elements of M̄ that are
D-equivalent to the indentity.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
20 Local embeddability
The Łoś theorem claims that θ(g1/D, . . . , gn/D) holds in
∏
i∈IMi/D
iff the set {i ∈ I : θ(g1(i), . . . , gn(i)) holds in Mi} belongs to D, for
any L-formula θ(x1, . . . , xn) and g1, . . . , gn ∈ M̄ . When θ is an atomic
formula of the form P (x1, . . . , xn) or f(x1, . . . , xn−1) = xn, this holds
just by definition of ultraproduct; for an arbitrary θ it can be proved by
induction on the complexity of θ (see [4, 7]).
An immediate consequence of the Łoś theorem is that any ultraproduct
of K-structures is a model of Th(K). Hence any axiomatizable class is
closed under ultraproducts.
Theorem 2. An L-structure is a model of Th∀(K) iff it is embeddable
into an ultraproduct of K-structures.
Proof. Since ultraproducts of K-structures are models of Th(K), and the
validity of unversal sentences is preserved in substructures, any substruc-
ture of an ultraproduct of K-structures is a model of Th∀(K).
Let M be a model of Th∀(K). Then any finite subset ∆ of ∆(M) is
satisfiable in a K-structure. Indeed, suppose not. Let x̄ be all variables
that occur in ∆. Then ¬∃x̄
∧
∆ holds in any K-structure. Hence the
universal sentence ∀x̄¬
∧
∆ belongs to Th∀(K), and so holds in M . But
∃x̄
∧
∆ holds in M because ∆ ⊆ ∆(M). Contradiction.
Thus for any finite subset ∆ of ∆(M) there are a K-structure M∆
and a map φ : M → M∆ such that ∆ holds in M∆ when the variable xa
takes the value φ∆(a) for all a ∈ M .
Denote by I the collection of all finite subsets of ∆(M). For θ ∈
∆(M) let Iθ be the set of all ∆ ∈ I such that θ holds in M∆ when xa
takes the value φ∆(a) for all a ∈ M . The set {Iθ : θ ∈ ∆(M)} has the
finite intersection property because for any nonempty ∆ ∈ I we have
∆ ∈
⋂
θ∈∆ Iθ. Therefore there exists an ultrafilter D on I containing
{Iθ : θ ∈ ∆(M)}.
Let N =
∏
∆∈IM∆/D. Define φ : M → N by the rule
φ(a) = (φ∆(a) : ∆ ∈ I)/D.
We show that φ is an embedding of M into N , that is, θ ∈ ∆(M) holds
in N when xa takes the value φ(a) for all a ∈ M . By definition of
ultraproduct, this holds iff Iθ ∈ D, which is true by the choice of D. Thus
M is embeddable into N which is an ultraproduct of K-structures.
Thus Theorems 1 and 2 imply
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 21
Corollary 2. Up to isomorphism, the LEK-structures are exactly the
substructures of ultraproducts of K-structures. In particular, if K is closed
under ultraproducts then the LEK-structures are exactly the substructures
of K-structures.
For example, the LEF-groups are exactly the subgroups of ultraprod-
ucts of finite groups.
It is not difficult to show that the class K of all linear groups of a
fixed degree is closed under ultraproducts; so in this case the LEK-groups
are just the K-groups.
Clearly, for an axiomatizable class K′ of L′-structures with L′ ⊇ L,
the class K of L-reducts of K′-structures is closed under ultraproducts.
So Corrolary 2 is applicable to such classes K.
For instance, let K be the class of orderable groups in the group
language L, that is, the class of L-reducts of K′-structures, where K′ is
the class of all ordered groups in the language L′ = {·,−1 , e, <}. Clearly,
K′ is axiomatizable. Hence a group is a LEK-group iff it is a K-group.
3. Universal locally K-structures
Let K be a class of L-structures. An L-structure M is called a locally
K-structure if every finite subset of M is contained in a K-substructure;
when K is closed under finitely generated substructures this means that
any finitely generated substructure of M belongs to K. Clearly, every
K-structure is a locally K-structure, for any class K. Obviously, any locally
LEK-structure is a LEK-structure.
Since a universal sentence which fails in a locally K-structure fails in
some K-structure, we have Th∀(K) = Th∀(LEK).
A locally K-structure U is called a universal locally K-structure if
any finitely generated substructure of any K-structure is embeddable into
U . For many classes of structures K a universal locally K-structure does
exist.
For instanse, if a class of groups K is closed under finite direct products
then there exists a universal locally K-group. Indeed, let {Gi : i ∈ I}
be a family of K-groups such that any finitely generated subgroup of
a K-group is embeddable to one of Gi; then the direct sum of all Gi is
a universal locally K-group. Examples of classes of groups closed under
finite direct products are any quasi-variety of groups, the classes of finite
groups, torsion groups, divisible groups, amenable groups. New examples
can be obtained using the observation that the intersection of any family
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
22 Local embeddability
of such classes and the union of a chain of such classes is such a class.
For example, by this observation, the classes of finite solvable groups and
torsion-free nilpotent groups are such classes.
Also, there are classes of groups K with a universal locally K-group
which are not closed under finite direct products. Examples of such classes
K are the class of free groups (here F2 is a universal locally K-group)
and the class of finite cyclic groups (here
⊕
pC(p∞) is a universal locally
K-group).
Note that for the class of all cyclic groups there is no universal locally
cyclic group because it would contain an infinite cyclic group and a finite
cyclic group and so could not be locally cyclic.
We call L-structures M and N elementarily equivalent if they satisfy
the same L-sentences. Clearly, M and N are elementarily equivalent iff
M is a model of Th(N). By Theorems 1 and 2 applied to the class {N},
a structure M is a model of Th∀(N) iff M is embeddable into a structure
elementarily equivalent to N iff M is embeddable into an ultrapower
of N .
Theorem 3. Let K be a class of L-structures such that there exists a
universal locally K-structure U . For an L-structure M the following are
equivalent:
(1) M is a LEK-structure;
(2) M is embeddable into a structure elementarily equivalent to a locally
K-structure;
(3) M is embeddable into an ultrapower of a locally K-structure.
(4) M is embeddable into a structure elementarily equivalent to U ;
(5) M is embeddable into an ultrapower of U .
Proof. Since, by Theorem 1, M is a LEK-structure iff M is a model of
Th∀(K), it suffices to prove the following claims:
(i) Th∀(U) = Th∀(K),
(ii) M is a model of Th∀(K) iff M is a model of Th∀(N) for some locally
K-structure N .
A universal sentence which fails in some K-structure fails in some
finitely generated substructure of it, and hence fails in U . Therefore
Th∀(U) ⊇ Th∀(LEK) = Th∀(K) ⊇ Th∀(U).
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 23
Therefore (i) holds. Now we prove (ii). If M is a model of Th∀(K) then
M a model of Th∀(U). Suppose M is a model of Th∀(N), where N is a
locally K-structure. Since Th∀(K) = Th∀(LEK) ⊆ Th∀(N), the structure
M is a model of Th∀(K).
For example, Theorem 3 says that the LEF-groups can be character-
ized as the subgroups of ultrapowers of locally finite groups. Since the
group Sω(N) of all finitary permutations of N is a universal locally finite
group, the LEF-groups are exactly the subgroups of ultrapowers of Sω(N).
Another application: the groups locally embeddable to free groups are
exactly the subgroups of ultrapowers of F2.
Now we show that although there is no universal locally cyclic group,
the conclusion of Theorem 3 still holds for the class of cyclic groups.
Theorem 4. Let K be the class of all cyclic groups. Then for a group G
the following are equivalent:
(1) G is a LEK-group,
(2) G is embeddable into a group elementarily equivalent to a locally
cyclic group,
(3) G is embeddable into an ultrapower of a locally cyclic group.
Proof. As it was explained above, the equivalence of (2) and (3) is a
special case of a general fact. If (2) then G is a model of Th∀(H) for some
locally cyclic group H, and hence a model of Th∀(K); therefore (1) holds,
by Theorem 1.
Suppose (1); we need to show (2). Clearly, G is abelian. We may
assume that G 6= 0. Let Ĝ be the divisible hull of G; then the group Ĝ
is isomorphic to
⊕
pC(p∞)(κp) ⊕ Q(κ), for some cardinals κ, κp not all of
which are equal to 0.
It suffices to show that all κp ≤ 1. Indeed, it is known (see [4]) that if A
is an abelian group of unbounded exponent then A⊕ Q(κ) is elementarily
equivalent to A. If κp = 0 for all p then κ > 0, and so Ĝ is isomorphic to
Q(κ); hence Ĝ is elementarily equivalent to the locally cyclic group Q. If
some κp 6= 0 then Ĝ is elementarily equivalent to the group
⊕
pC(p∞)(κp)
which is locally cyclic when all κp ≤ 1.
For any nontrivial divisible subgroup B of Ĝ we have G ∩ B 6= 0.
Indeed, otherwise Ĝ = B⊕C for some subgroup C containing G. Clearly,
C is divisible, and G ≤ C < Ĝ, contrary to minimality of the divisible
hull. It follows that if κp 6= 0, then G contains a subgroup which is a
direct sum of κp copies of a cyclic group of order p. If κp ≥ 2 then G
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
24 Local embeddability
contains a finite subgroup A which is a direct sum of two copies of cyclic
groups of order p. This A is not embeddable into a K-group, which is
impossible because G is a LEK-group.
Remark. The characterization of LEK-groups given in Theorem 3 is
essentially different from the ones in Theorems 1 and 2, because a model
of the theory of K and a model of the theory of a locally K-structure are
not the same. To demonstrate this for the class K of all finite groups, we
show that
(i) the additive group of reals R is a model of the theory of finite groups
but is not elementarily equivalent to a locally finite group,
(ii) the group C(p∞) is locally finite but is not a model of the theory of
finite groups.
First, R is torsion-free and so cannot be elementarily equivalent to a
locally finite group. Second, R is isomorphic to an ultraproduct of finite
groups. Indeed, let D be a non-principal ultrafilter on the set of all primes,
and G =
∏
p∈P Zp/D. It is easy to show that |G| = 2ℵ0 . Using the Łoś
theorem one can check that G is a torsion-free, divisible abelian group.
Therefore G ≃ R. Thus (i) is proven.
Since the first order sentence “if there is an element of order p then
there is a non-p-divisible element” holds in any finite group but not in
C(p∞), we have (ii).
4. Fully residually K-structures
Let K be a class of L-structures. We call an L-structure M a residually
K-structure if for any two different a, b ∈ M there are a K-structure N
and a homomorphism τ : M → N such that τ(a) 6= τ(b). We call M a
fully residually K-structure if for any finite subset S of M there are a
K-structure N and a homomorphism τ : M → N which is injective on S.
Clearly, any fully residually K-structure is a residually K-structure.
Theorem 5. If K is closed under finite direct products then any residually
K-structure is a fully residually K-structure.
Proof. Let M be a residually-K structure, and S a finite subset of M .
For any different a, b ∈ M choose N{a,b} ∈ K and a homomorphism
τ{a,b} : M → N{a,b} injective on {a, b}. Let N be the direct product of
all N{a,b}. Since K is closed under finite direct products, N ∈ K. Let
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 25
τ : M → N be defined by the rule τ(x){a,b} = τ{a,b}(x). Then τ is a
homomorphism which is injective on S.
Obviously, any locally fully residually K-structure is a LEK-structure.
In general, the converse is not true: for example, there exist finitely
generated LEF-froups which are not residually finite [9].
Let K be any of the classes of finite groups, nilpotent groups, amen-
able groups. Then K is closed under finite direct products. Since any
nonabelian free group F is a residually K-group, it is a fully residually
K-group, and hence a LEK-group but not a locally K-group. Since F is
not embeddable into a K-group, this, together with Corollary 1, proves
that these classes are not axiomatizable.
It was proven in [8, 12] that a finitely presented group is a LEF-group
iff it is residually finite. The following result generalizes that fact.
Theorem 6. Let V be a quasi-variety of L-structures, and M a finitely
presented member of V. Let K be a subclass of V. Then M is a LEK-
structure iff M is a fully residually K-structure iff M is a residually
K-structure.
Proof. It suffices to show that if M is a LEK-structure then M is a fully
residually K-structure. Let 〈c̄ ; ρ1(c̄), . . . , ρm(c̄)〉 be a finite presentation
of M in V, where ρi are atomic L-formulas. Let S be a finite subset of
M of size n. Then S = {tMi (c̄) : 1 ≤ i ≤ n} for some L-terms ti(x̄). Since
the sentence
φ := ∃x̄(
∧
j
ρj(x̄) ∧
∧
i6=k
ti(x̄) 6= tk(x̄))
holds in M , and M is a model of the universal theory of K by Theorem 1,
φ holds in some K-structure N . Let b̄ be a tuple in N such that ρj(b̄)
holds in N for all j, and all tNi (b̄) are distinct. Since N ∈ V and ρj(b̄)
holds in N for all j, there is a homomorphism τ : M → N which takes c̄
to b̄. Then τ takes tMi (c̄) to tNi (b̄) for all i. Since all tNi (b̄) are distinct, τ
is injective on S.
5. K-limit structures
Each Boolean algebra B has an associated topological space called
the Stone space of B and denoted by St(B) (see [5]). Its points are the
ultrafilters on B, and a base of its topology consists of the sets
Ub = {p ∈ St(B) : b ∈ p},
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
26 Local embeddability
where b ∈ B. Clearly, the complement of Ub is Ub̄; hence the sets Ub are
clopen. The topological space St(B) is compact and totally disconnected.
Let QFn denote the set of all quantifier-free L-formulas in variables
x̄ = (x1, . . . , xn). For an L-structure N and a tuple ā = (a1, . . . , an) in
N , the set of all formulas in QFn such that θ(ā) holds in N is called the
quantifier-free type of the tuple ā in N , and denoted by qftpN (ā). It is
easy to see that qftpN (ā) is a maximal finitely satisfiable subset of QFn.
Moreover, the compactness theorem implies that any maximal finitely
satisfiable subset q of QFn is the quantifier-free type of an n-tuple ā in
an L-structure N ; we say that ā realizes q in N . We denote the set of all
quantifier-free types of n-tuples in L-structures by Qn.
Clearly, qftpN (ā) = qftp〈ā〉(ā), where 〈a〉 denotes the substructure
generated by ā. For n-tuples ā and b̄ in L-structures N and M , we have
qftpN (ā) = qftpM (b̄) if and only if there is an isomorphism between 〈ā〉
and 〈b̄〉 which takes ā to b̄. Therefore the quantifier-free types of n-tuples
in L-structures can be identified with the isomorphism types of pairs
(N, ā), where N is an L-structure generated by ā. We call such pairs
marked (or, more precisely, n-marked) L-structures. This generalizes the
notion of a marked group (see [2]); so the quantifier-free types of tuples
in groups are nothing but the isomorphism types of marked groups.
For a formula θ in QFn let [θ] denote the equivalence class of θ.
Let [QFn] be the Boolean algebra of equivalence classes of formulas
in QFn with the operations induced by ∧,∨,¬. It is easy to see that
the map p 7→ {θ : [θ] ∈ p} is a bijection from St([QFn]) to Qn. This
bijection induces a topology on Qn, a clopen base of which is the set
of all Uθ = {q ∈ Qn : θ ∈ q}, where θ ∈ QFn. Clearly, the set of all
Uθ with atomic or negated atomic θ is a subbase of the topology. We
call this topology the Stone topology on Qn. Since the elements of Qn
can be identified with n-marked L-structures, the Stone topology can be
considered as a topology on the set of n-marked L-structures.
Define an ultrametric d on Qn as follows: d(p, p) = 0, and if p 6= q
then d(p, q) = 1/v(p, q), where v(p, q) is the maximal m such that θ ∈ p
iff θ ∈ q for all θ ∈ QFn of length < m. Note that v(p, q) is the maximal
m such that θ ∈ p iff θ ∈ q for all atomic θ ∈ QFn of length < m.
Theorem 7. If L is finite then the Stone topology on Qn is induced by
the metric d.
Proof. First we show that for any point p and m ≥ 1 the open ball
B(p, 1/m) is open in the Stone topology; then any d-open set is open
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
O. Belegradek 27
in the Stone topology. We have B(p, 1/m) = {q : v(q, p) > m}, and the
condition v(q, p) > m means that θ ∈ q iff θ ∈ p for any θ ∈ QFn of the
length ≤ m. Therefore B(p, 1/m) is the intersection of all Uθ and all U¬ψ
such that θ,¬ψ ∈ p and θ, ψ are of length ≤ m. Since L is finite, there
are only finitely many formulas in QFn of length ≤ m, and so this is a
finite intersection. Hence B(p, 1/m) is open in the Stone topology.
To prove that any subset of Qn which is open in the Stone topology
is d-open, it suffices to show that for any consistent θ ∈ QFn the set Uθ is
d-open. Let p ∈ Uθ. If the length of θ is m, then B(p, 1/m) ⊆ Uθ. Indeed,
if q ∈ B(p, 1/m) then v(q, p) > m, and hence q ∈ Uθ, because θ ∈ q iff
θ ∈ p.
Let K be a class of L-structures. We call an n-marked L-structure
(N, ā) an n-marked K-structure if N ∈ K. Similarly, (N, ā) is said to
be a model of a theory T if N is a model of T . We call any member of
the closure of the set of n-marked K-structures in the Stone topology a
K-limit n-marked L-structure.
Theorem 8. Let K be a class of L-structures closed under substructures.
Then an n-marked L-structure is K-limit iff it is a model of the universal
theory of K.
Proof. Let (N, ā) be an n-marked structure which is a model of Th∀(K);
we show that (N, ā) is K-limit. Denote q = qftpN (ā). Suppose q ∈ Uθ,
where θ ∈ QFn. Then ∃x̄θ(x̄) holds in N , and hence in some K-structure
M . Let θ(b̄) holds in M . Then 〈b̄〉 ∈ K, and qfpt〈b̄〉(b̄) belongs to Uθ.
Suppose (N, ā) is K-limit; we show that N is a model of the universal
theory of K. The latter means that, whenever an existential L-sentence ψ
holds in N , it holds in some K-structure. Let ψ be ∃y1 . . . yk θ(y1, . . . , yk),
where θ is quantifier-free. Since ā generates N , there are L-terms ti(x̄)
such that ρ(ā) holds in N , where ρ is θ(t1(x̄), . . . , tk(x̄)). Since (N, ā) is
K-limit, and ρ(ā) holds in N , there is an n-marked K-structure (M, b̄)
such that ρ(b̄) holds in M . Then ψ holds in the K-structure M .
If K is the class of finite groups or the class of free groups, we have
that the marked n-generated LEK-groups are exactly the K-limit marked
n-generated groups. These results were proven in [12] for the finite groups,
and in [2] for the free groups.
Corollary. If K is universally axiomatizable then the n-marked K-limit
structures are exactly the n-marked LEK-structures.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
28 Local embeddability
References
[1] C. Champetier, L’espace des groupes de type fini, Topology 39 (2000), 657–680.
[2] C. Champetier, V. Guirardel, Limit groups as limits of free groups, Israel J. Math.
146 (2005) 1–75.
[3] R. Grigorchuk, Degrees of growth of finitely generated groups and the theory of
invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), 939–985.
[4] W. Hodges, Model theory, Cambridge University Press, Cambridge, 1993.
[5] P. T. Johnstone, Stone Spaces, Cambridge University Press, Cambridge, 1982.
[6] A. I. Mal’cev, On a general method for obtaining local theorems in group theory,
Ivanov. Gos. Ped. Inst. Uc. Zap. Fiz.-Mat. Fak. 1 (1941), no. 1, 3–9.
[7] A. I. Mal’cev, Algebraic systems, Springer-Verlag, New York–Heidelberg, 1973.
[8] A. M. Stëpin, Approximability of groups and group actions, Uspekhi Mat. Nauk 38
(1983), no. 6, 123–124.
[9] A. M. Stëpin, A remark on the approximability of groups, Vestnik Moskov. Univ.
Ser. I Mat. Mekh., 1984, no. 4, 85–87.
[10] V. G. Pestov, Hyperlinear and sofic groups: a brief guide, arXiv:math/0804.3968v8,
August 2008.
[11] V. G. Pestov, A. Kwiatkowska, An introduction to hyperlinear and sofic groups,
arXiv:math/0911.4266v4, April 2012.
[12] A. M. Vershik, E. I. Gordon, Groups that are locally embeddable in the class of
finite groups, Algebra i Analiz 9 (1997), no. 1, 71–97.
Contact information
Oleg Belegradek Department of Mathematics,
Istanbul Bilgi University,
Hacıahmet Mahallesi, Pir Hüsamettin Sokak,
No: 20,
Dolapdere 34440, Beyoğlu,
Istanbul, Turkey
E-Mail: olegb@bilgi.edu.tr
Received by the editors: 10.06.2012
and in final form 10.06.2012.
O. Belegradek
|