Limiting theories

First order logic has provided useful tools to mathematicians over the last several decades. We give some general motivation for interest in the first order theory of a structure, give some illuminating examples, and discuss some new results which are spelled out in Limiting theories of substructures.

One of the overarching themes in mathematics is to understand when two mathematical structures are essentially “the same.” This sameness is often characterized by the existence of a bijection between the elements of the structures which preserves the essential characteristics of the structures. Homeomorphisms of topological spaces, isometries of metric spaces, isomorphisms of groups (rings, fields, algebras, etc.), and order preserving bijections between ordered spaces are examples. It is useful to produce characteristics (invariants) of a structure which are preserved under a map which witnesses sameness. Invariants give sufficient conditions from which one may assert that two structures are not the same. For example, a topological space with two path components cannot be homeomorphic to a space which has one. Having a point named $x$ is not a homeomorphism invariant. The most naïve invariant of a structure is its cardinality, for if sameness is characterized via a bijection then structures of differing cardinality cannot be the same.

Another invariant of a structure is its first order theory. Without getting into the gory details of languages, well-formed formulas and sentences, the first order theory of a structure is essentially the set of finitary logical sentences which are true of the structure. It will hopefully suffice to give some examples of structures and first order sentences satisfied by them. We let $Th(\mathcal{S})$ denote the first order theory of a structure $\mathcal{S}$ .

We consider a group $G$ as a set with binary operation $*$ , unary inverse operation $^{-1}$ , and nullary operation $1$ which satisfies the standard requirements that define groups: $(\forall x)[x*1 = 1*x = x]$ , $(\forall x)[x*x^{-1} = x^{-1}*x = 1]$ , and $(\forall x)(\forall y)(\forall z)[x*(y*z) = (x*y)*z]$ . For abelian groups the binary operation is often denoted $+$ and the nullary operation is often denoted $0$ . The two element abelian group $\mathbb{Z}/2\mathbb{Z}$ satisfies the requirements for a group as well as the sentences

$(\forall x)[x+x = 0]$
$(\exists x)(\exists y)[x\neq y]$
$\neg (\exists x)(\exists y)(\exists z)[x\neq y \wedge x\neq z\wedge y\neq z]$

Sentence 1 states that all elements have order at most two, sentence 2 states that there are at least two elements, and sentence 3 states that there are not three elements. Any group of exactly two elements is isomorphic to $\mathbb{Z}/2\mathbb{Z}$ . More generally the first order theory of a finite group totally determines its isomorphism class: if $G$ is a finite group and $Th(G) = Th(H)$ then $G$ is isomorphic to $H$ . This is because one can spell out the multiplication table of a group using a finitary sentence. Letting $G = \{g_0, g_2, \ldots, g_{n-1}\}$ and $f: n\times n \rightarrow n$ be defined by $g_i*g_j = g_{f(i, j)}$ , the following sentence totally determines $G$ up to group isomorphism:

$(\exists x_0)(\exists x_1) \cdots (\exists x_{n-1})[\bigwedge_{0\leq i, j<n}x_i*x_j = x_{f(i, j)}]\wedge \neg (\exists x_0)(\exists x_1) \cdots (\exists x_n)[\bigwedge_{0\leq i<j<n+1}x_i \neq x_j]$

We have seen that first order logical sentences can express ideas like “there exist $n$ elements” or “there do not exist $n$ elements.” Some other concepts that can be expressed using first order logic are: “every element is twice an element” (which would allow you to distinguish the group $\mathbb{Q}$ from $\mathbb{Z}$ ), “there exists a non trivial element of order two” (which allows you to distinguish $\mathbb{Z} \oplus (\mathbb{Z}/2\mathbb{Z})$ from $\mathbb{Z}$ ), and “the group is nilpotent of height $n$ .” Thus, many algebraic properties may be expressed using first order logic and it might seem that first order logic can be used to distinguish any two nonisomorphic groups. It turns out that this latter sentiment is not only false but extraordinarily false. We’ll state a corollary to what is called the Upward Löwenheim-Skolem Theorem:

Corollary If a structure $\mathcal{S}$ utilizes only countably many non-logical symbols and has countably-infinitely many elements then for every infinite cardinal number $\kappa$ there exists a structure $\mathcal{S}'$ having exactly $\kappa$ elements such that $Th(\mathcal{S}) = Th(\mathcal{S}')$ .

Continuing our group theory examples, we note that groups have only finitely many non-logical symbols- the binary operation symbol, the inverse symbol, and the group identity symbol. Thus by this corollary, for any countably infinite group $G$ there exist groups of all infinite cardinalities which have the same first order theory (most of which are clearly not isomorphic to $G$ .) For example, there exist uncountable groups which have the same first order theory as the infinite cyclic group $\mathbb{Z}$ . This highlights that the property “being infinite cyclic” cannot be expressed using first order logic, since cyclic groups must be countable.

We move to a discussion of direct limits and of how the theories of a system of substructures can limit to the theory of the large structure. Recall that a directed set $I$ is a partially ordered set such that for any $i_0, i_1\in I$ there exists $i_2\in I$ with $i_2 \geq i_0, i_1$ . Let $\mathcal{S} = (S, F, R)$ be a structure ( $S$ is the set of elements, $F$ is the set of functions and $R$ is the set of relations). We’ll say for the purposes of this discussion that a collection $\{\mathcal{S}_i\}_{i\in I}$ of substructures of $\mathcal{S}$ has direct limit $\mathcal{S}$ if $\bigcup_{i\in I}S_i = S$ and $i_0 \leq i_1$ implies $S_{i_0} \subseteq S_{i_1}$ . In such a situation, since the non-logical symbols in $F \cup R$ are the same for $\mathcal{S}$ as for its distinguished substructures $\mathcal{S}_i$ , it is natural to compare $Th(\mathcal{S})$ to $Th(\mathcal{S}_i)$ for each $i\in I$ . It might be that $Th(\mathcal{S})$ is precisely the same as each $Th(\mathcal{S}_i)$ , but it is often the case that the theory of the large structure is different from that of each of the substructures. For example, if $\mathcal{S}$ has infinitely many elements and each of the $\mathcal{S}_i$ has only finitely many elements, then $Th(\mathcal{S}) \neq Th(\mathcal{S}_i)$ since first order sentences can distinguish a finite structure from an infinite. Even so, it may be that the theories $Th(\mathcal{S}_i)$ get closer and closer to $Th(\mathcal{S})$ in a way that we make explicit.

Let $Sent(F\cup R)$ be the set of all first order sentences which can be made using functions in $F$ and/or relations in $R$ . Thus $Th(\mathcal{S}) \subseteq Sent(F \cup R)$ and for any $\theta\in Sent(F\cup R)$ it is either the case that $\theta\in Th(\mathcal{S})$ or that $\neg \theta \in Th(\mathcal{S})$ , and similar statements hold for $Th(\mathcal{S}_i)$ . Let

$\limsup_I Th(\mathcal{S}_i) = \{\theta \in Sent(F\cup R): (\forall j\in I)(\exists i \geq j)[\theta \in Th(\mathcal{S}_i)]\}$

$\liminf_I Th(\mathcal{S}_i) = \{\theta \in Sent(F\cup R): (\exists j\in I)(\forall i \geq j)[\theta \in Th(\mathcal{S}_i)]\}$

Clearly the inclusion $\liminf_I Th(\mathcal{S}_i) \subseteq \limsup_I Th(\mathcal{S}_i)$ holds, and if $\liminf_I Th(\mathcal{S}_i) =\limsup_I Th(\mathcal{S}_i)$ we write $\lim_I Th(\mathcal{S}_i) = \liminf_I Th(\mathcal{S}_i) =\limsup_I Th(\mathcal{S}_i)$ and say that the limit $\lim_I Th(\mathcal{S}_i)$ exists. We illustrate with some examples.

Example 1 Consider the structure $\mathcal{S} = (\mathbb{N}, \leq, E)$ where $\leq$ is the standard ordering on $\mathbb{N}$ and $Ex$ if and only if $x$ is even. The finite substructure $\mathcal{S}_n$ whose set of elements is $\{0, 1, \ldots, n\}$ satisfies the sentence $(\exists x)[Ex\wedge (\forall y)[y\leq x]]$ if and only if $n$ is even. Letting $I = \mathbb{N}$ under the natural ordering it is clear that $\mathcal{S}$ is the direct limit of the $\mathcal{S}_n$ . We see that $\liminf_I Th(\mathcal{S}_i)$ is strictly included in $\limsup_I Th(\mathcal{S}_i)$ and the limit $\lim_I Th(\mathcal{S}_i)$ does not exist.

Example 2 Consider the abelian group structure $\mathcal{S} = (\mathbb{Q}, +, -, 0)$ . Let $\{p_0, p_1, \ldots\}$ be an enumeration of the prime numbers and for each $n\in \mathbb{N}$ let $\mathcal{S}_n$ be the subgroup generated by $\frac{1}{(p_0p_1\cdots p_n)^n}$ . Again $\mathcal{S}$ is the direct limit of the $\mathcal{S}_n$ . Each $\mathcal{S}_n$ is isomorphic to the group $\mathbb{Z}$ and so certainly the limit $\lim_I Th(\mathcal{S}_i)$ exists since $Th(\mathcal{S}_n)$ is constant.

Example 3 Consider the structure $\mathcal{S} = (\mathbb{R}, \leq)$ where $\leq$ is the standard ordering on $\mathbb{R}$ . Let $I = \{A \subseteq \mathbb{R}: \mathbb{Q} \subseteq A, |A|= \aleph_0\}$ . Clearly $I$ is a directed set under set inclusion, and letting $\mathcal{S}_A$ be the substructure having $A$ as its elements it is clear that $\mathcal{S}$ is the direct limit of $\{\mathcal{S}_A\}_{A\in I}$ . Each structure $\mathcal{S}_A$ , and also $\mathcal{S}$ , is a nonempty dense linear order with no first or last point, and it is classically known that all such structures have the same first order theory. Thus $\lim_I Th(\mathcal{S}_A)$ exists.

So far we have seen an example where the first order theory of the substructures did not have a limit, an example where the first order theory of the substructures did have a limit which was not equal to the theory of the large structure (since $Th((\mathbb{Q}, +. -, 0)) \neq Th((\mathbb{Z}, +, -, 0))$ ), and an example where the first order theories of the substructures have a limit which is equal to the theory of the large structure. We give a theorem which gives sufficient conditions under which the theories of substructures has a limit, and under which the limit of their theories is equal to the theory of the large structure (see Theorem A in Limiting theories of substructures):

Theorem Suppose $\{\mathcal{S}_i\}_{i\in I}$ is a collection of substructures of $\mathcal{S}$ such that $\mathcal{S}$ is the direct limit of $\{\mathcal{S}_i\}_{i\in I}$ .

(1) If for each finite set of constants $a_1, \ldots, a_m\in S$ there exists an $i\in I$ such that for $j \geq i$ and $b_1, \ldots, b_m \in S_j$ there exists an automorphism $f:\mathcal{S}_j \rightarrow \mathcal{S}_j$ fixing each $a_l$ and such that $f(\{a_1, \ldots, a_m, b_1, \ldots, b_m\}) \subseteq S_i$ the limit $\lim_I Th(\mathcal{S}_i)$ exists.

(2) If in addition to (1) for each finite set of constants $a_1, \ldots, a_m\in S$ there exists an $i\in I$ such that for $b_1, \ldots, b_m \in S$ there exists an automorphism $f:\mathcal{S} \rightarrow \mathcal{S}$ fixing each $a_l$ and such that $f(\{a_1, \ldots, a_m, b_1, \ldots, b_m\}) \subseteq S_i$ then $\lim_I Th(\mathcal{S}_i) = Th(\mathcal{S})$ .

What we have stated is a bit weaker than the statement of Theorem A in Limiting theories, but it is sufficient for our discussion. The theorem is proved in a more general setting, by induction on the number of quantifiers used in a sentence. This result can obviously be applied only in settings where structures have many automorphisms, that is, structures where there are automorphisms which can fix some prescribed finite subset and move some other finite subset into a designated structure. For example, in a structure which is simply an infinite set (no non-logical symbols), the hypotheses of both conditions (1) and (2) apply to the substructure net of finite subsets and we get that the theory of an infinite set is the limit of the theories of increasingly large finite sets. Similar conclusions regarding infinite abelian groups of prime exponent $p$ and infinite rank free abelian groups can be made. Moreover, the fact that the theory of a finite set is never equal to that of an infinite yields a new proof of the classical result that the theory of an infinite set is not finitely axiomatizable (this can otherwise be proved using either the Compactness Theorem or quantifier elimination). Similarly, the first order theory of an infinite abelian group of prime exponent $p$ and the first order theory of an infinite rank free abelian group are not finitely axiomatizable.

Share this:

Like this:

Related

Leave a Reply Cancel reply