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 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 denote the first order theory of a structure .
We consider a group as a set with binary operation , unary inverse operation , and nullary operation which satisfies the standard requirements that define groups: , , and . For abelian groups the binary operation is often denoted and the nullary operation is often denoted . The two element abelian group satisfies the requirements for a group as well as the sentences
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 . More generally the first order theory of a finite group totally determines its isomorphism class: if is a finite group and then is isomorphic to . This is because one can spell out the multiplication table of a group using a finitary sentence. Letting and be defined by , the following sentence totally determines up to group isomorphism:
We have seen that first order logical sentences can express ideas like “there exist elements” or “there do not exist 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 from ), “there exists a non trivial element of order two” (which allows you to distinguish from ), and “the group is nilpotent of height .” 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 utilizes only countably many non-logical symbols and has countably-infinitely many elements then for every infinite cardinal number there exists a structure having exactly elements such that .
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 there exist groups of all infinite cardinalities which have the same first order theory (most of which are clearly not isomorphic to .) For example, there exist uncountable groups which have the same first order theory as the infinite cyclic group . 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 is a partially ordered set such that for any there exists with . Let be a structure ( is the set of elements, is the set of functions and is the set of relations). We’ll say for the purposes of this discussion that a collection of substructures of has direct limit if and implies . In such a situation, since the non-logical symbols in are the same for as for its distinguished substructures , it is natural to compare to for each . It might be that is precisely the same as each , 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 has infinitely many elements and each of the has only finitely many elements, then since first order sentences can distinguish a finite structure from an infinite. Even so, it may be that the theories get closer and closer to in a way that we make explicit.
Let be the set of all first order sentences which can be made using functions in and/or relations in . Thus and for any it is either the case that or that , and similar statements hold for . Let
Clearly the inclusion holds, and if we write and say that the limit exists. We illustrate with some examples.
Example 1 Consider the structure where is the standard ordering on and if and only if is even. The finite substructure whose set of elements is satisfies the sentence if and only if is even. Letting under the natural ordering it is clear that is the direct limit of the . We see that is strictly included in and the limit does not exist.
Example 2 Consider the abelian group structure . Let be an enumeration of the prime numbers and for each let be the subgroup generated by . Again is the direct limit of the . Each is isomorphic to the group and so certainly the limit exists since is constant.
Example 3 Consider the structure where is the standard ordering on . Let . Clearly is a directed set under set inclusion, and letting be the substructure having as its elements it is clear that is the direct limit of . Each structure , and also , 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 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 ), 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 is a collection of substructures of such that is the direct limit of .
(1) If for each finite set of constants there exists an such that for and there exists an automorphism fixing each and such that the limit exists.
(2) If in addition to (1) for each finite set of constants there exists an such that for there exists an automorphism fixing each and such that then .
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 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 and the first order theory of an infinite rank free abelian group are not finitely axiomatizable.