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

  1. (\forall x)[x+x = 0]
  2. (\exists x)(\exists y)[x\neq y]
  3. \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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: