Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 25 7 Solution Created 2026-10-03 Updated 2026-10-14
For nonempty first-order structures in a common language and an ultrafilter on , identify product functions byThe ultraproduct has these equivalence classes as elements. Functions are interpreted coordinatewise, and a relation holds of classes exactly when its coordinatewise truth set belongs to . Closure under finite intersections makes these interpretations independent of representatives.
The Łoś theorem assertsProve it by induction on first-order formulas. Atomic first-order formulas hold by the definitions and induction on terms. Conjunction uses intersections, and negation uses the fact that an ultrafilter contains exactly one of a set and its complement. For an existential first-order formula, a product witness gives a coordinate witness on a -large set. Conversely, on the -large set where a coordinate witness exists, choose one in each factor, and choose arbitrary values elsewhere. Its class is a product witness by the induction hypothesis. This is the only witness-selection step; the surrounding argument is made in a choice metatheory. The special case with all factors equal is an ultrapower, and constant functions give an elementary embedding.
Here is a direct compactness theorem proof. Suppose every finite subset of a theory has a model. Index factors by the finite subsets , choosing . For finite , the cone is nonempty, and . Extend the generated proper filter to an ultrafilter . For every sentence , its truth set contains , so the Łoś theorem gives . Finite satisfiability therefore implies satisfiability, directly from the ultraproduct construction rather than from a syntactic completeness argument.
For saturated models, a structure is -saturated if every complete type over fewer than parameters is realized. A useful concrete case is countable saturation of a nonprincipal ultraproduct over omega. In a countable language, enumerate any finitely satisfiable type over countably many parameters as , and represent its parameters by product functions. By the Łoś theorem, the set of coordinates where the first first-order formulas have a simultaneous witness belongs to the nonprincipal ultrafilter . PutThese are decreasing -large sets. At coordinate , let be the largest with , or zero if none exists, and choose a witness for the first first-order formulas. For fixed , every coordinate in has , so the resulting product function satisfies on a -large set. Its class realizes the whole type. Thus such an ultraproduct is -saturated.
There is also an existence construction at every prescribed degree . Given an infinite model , choose a regular cardinal and construct an elementary chain . At a successor stage, add a new constant for a realization of every type over every subset of of size below , together with the elementary diagram of . Every finite part is satisfiable: only finitely many types and finitely many first-order formulas from each are involved, and each finite type fragment has a witness in . Compactness therefore supplies a simultaneous elementary extension. At limits take unions. To justify elementarity of a union, any existential first-order formula with parameters in an earlier stage has a witness in that stage whenever it has one at a later stage, by elementarity; this is the Tarski-Vaught test.
Any fewer-than- parameters of occur together in some , by regularity of . A type over them which is finitely satisfiable in is finitely satisfiable in , again by elementarity, and was realized in . Hence every infinite structure has a -saturated elementary extension for any prescribed cardinal . No bound on the size of this extension is asserted; full saturation at the model's own cardinality has additional cardinal-arithmetic issues.
Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 3 16H Solution 2026-10-14
A first-order structure consists of a nonempty domain, an interpretation of each constant as a domain element, each -ary function symbol as a map from the -fold domain product to the domain, and each -ary relation symbol as a subset of that product. Under an assignment of values to variables, terms are evaluated recursively. Atomic formulas assert equality of term values or membership in an interpreted relation. Boolean connectives act on truth values, and quantifiers range over the whole domain. The set consists of assignments to the free variables making the formula true.
For a substructure , constants lie in , functions restrict to , and relations restrict to tuples from . Induction on terms shows that every term with arguments from has the same value in both structures. Atomic formulas consequently have the same truth values, and induction on Boolean connectives givesfor every quantifier-free formula.
For a nonempty chain of -model substructures, form their union . Every finite tuple belongs to one member of the chain, so is closed under all interpreted functions and contains the constants. Consider any inductive axiom . A specified finite tuple lies in one member, which supplies witnesses there. The quantifier-free formula has the same truth value in that member and , so satisfies the axiom. Hence is a -model and the least upper bound of the chain. The poset is complete for nonempty chains. If chain-complete is defined to include the empty chain, a least element must additionally exist, which the stated hypotheses do not ensure.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 26 1 Solution Created 2026-10-03 Updated 2026-10-14
Here an ultralimit in the model-theoretic sense is a model-theoretic ultralimit: start with a first-order structure, take successive ultrapowers along their diagonal elementary embeddings, and take the directed limit of elementary embeddings of that chain. The elementary chain theorem, proved by induction on formulas after identifying the embeddings with inclusions, makes every stage elementary in the limit. This definition concerns structures, rather than the topological ultrafilter limit.
We first prove the needed Frayne embedding lemma. If , every finite subset of the elementary diagram of a structure can be realized in : existentially quantify its finitely many named elements, and use elementary equivalence. Index by finite diagram fragments, choose such realizations, and extend the filter of cones requiring each diagram formula to an ultrafilter. For each , let give its chosen coordinate realizations, filling unspecified coordinates arbitrarily. The Łoś theorem shows that is an elementary embedding of into an ultrapower of . The formulas ensure injectivity.
There is a relative version: if , keep all named elements from constant in every coordinate. Each finite diagram fragment is realizable in over those parameters by elementarity, so the resulting embedding extends the diagonal embedding of into its ultrapower.
Now use alternating ultrapowers give isomorphic ultralimits. First embed into an ultrapower of . Apply the relative lemma to , embedding into an ultrapower of over its diagonal copy. Next embed into an ultrapower of over , and continue. After coherent identifications this givesEach is an ultrapower of along its diagonal embedding, and each is an ultrapower of likewise. The two subsequences are cofinal in the same chain of elementary substructures, so their limits are the same union. Hence . No isomorphism theorem for single ultrapowers has been assumed.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 26 5 Solution Created 2026-10-03 Updated 2026-10-14
Let be nonempty first-order structures in one language and let be an ultrafilter on . In the ultraproduct , identify functions when , interpret functions coordinatewise and relations by their coordinate truth sets. The Łoś theorem states that for every first-order formula ,All interpretations are independent of representatives: changing finitely many arguments on -small sets changes truth only on their finite union, also -small.
Prove the theorem by structural induction on formulas. Terms evaluate coordinatewise by induction on terms. This proves the atomic cases of logical equality and relation symbols. For conjunction, intersect the two truth sets and use the filter laws. For negation, the truth set is complemented, and an ultrafilter contains exactly one of a set and its complement. These cases supply the other Boolean connectives too.
For the existential step, a witness in the ultraproduct makes the coordinate truth set for belong to by the induction hypothesis. That set is contained in the coordinate truth set of , so the latter is in . Conversely, if that existential truth set belongs to , choose a witness in for each , and any element of elsewhere. The axiom of choice supplies this function. The induction hypothesis makes a witness in the ultraproduct. Universal quantification follows by negation. This completes the proof.
For the compactness theorem, take to be the set of finite subsets of the given theory . For each , choose . For , the cone is nonempty, and any finite intersection of such cones contains their union as an index. Extend the filter they generate to an ultrafilter . By the proved Łoś theorem, the ultraproduct satisfies every , because its coordinate truth set contains . Thus . This proves compactness without assuming it in the ultraproduct construction.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 26 6 Solution Created 2026-10-03 Updated 2026-10-14
The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order , an elementary extension containing distinct order-indiscernibles . After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of extends to a unique automorphism of this specified Skolem hull in the expanded language.
Choose a Skolem expansion of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants for and the elementary diagram of a structure of , using separate names for its elements. Require for distinct indices, and for each formula in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.
Every finite fragment is satisfiable in . Choose a countably infinite sequence of distinct elements of . The fragment mentions only finitely many formulas and arities. Color increasing -tuples of that sequence by the finite vector of truth values of its relevant -ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in . By the compactness theorem proved in Question 5, the full set of requirements has a model , giving the required elementary extension and order-indiscernible sequence.
Let comprise all values of Skolem-language terms in finitely many . It is closed under the witness functions. If for parameters in , the specified witness function supplies a witness in . Induction on formulas therefore gives ; its reduct is a model of . For infinite , its cardinality is at most and at least .
For an order automorphism , defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying gives its inverse. All of is generated by the and the named Skolem functions, so an automorphism extending must have precisely this action. Thus , with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 27 1 Solution Created 2026-10-03 Updated 2026-10-14
The Ehrenfeucht-Mostowski theorem says that an infinite first-order structure , after Skolem expansion, has an elementarily equivalent model generated as a Skolem hull by distinct order-indiscernible sequence for any prescribed linear order . Every order automorphism of extends uniquely to an automorphism preserving this Skolem expansion. The reduct still models , but uniqueness of an automorphism in the reduct alone is not asserted. Iterate adjoining witness functions through all successively enlarged languages, so every existential formula in the final language has its own Skolem function. Write for the resulting expanded structure.
For the Ramsey theorem proof, add constants and require that they are distinct and that every two increasing tuples of the same length agree on every formula of the expanded language. Include . A finite fragment mentions finitely many formulas and finitely many indices, say of them. Choose distinct . For each arity occurring in those formulas, color the increasing tuples of natural numbers by their finite truth vectors in . Repeated applications of the infinite Ramsey theorem give an infinite subset homogeneous for all these finitely many colorings. Interpret the constants by its first elements, in their prescribed order. All the fragment's indiscernibility requirements hold. Thus compactness theorem produces a model of the whole scheme.
Let be the Skolem hull of the . Whenever an existential formula with parameters in holds in , its chosen Skolem witness belongs to . The Tarski-Vaught test, proved by the existential step of induction on formulas, therefore makes . For an order automorphism , defineTo compare different term presentations, collect all their indices into one increasing tuple. Indiscernibility transfers the equality of the terms to the transported tuple, so this map is well defined. The same argument transfers every relation; it preserves all functions by construction, and the map for is its inverse. Since every hull element is a term in the generators, uniqueness follows.
For a genuinely ultraproduct proof, keep the distinct and choose a nonprincipal ultrafilter on . For each finite ordered subset , takewhere is the ordered Fubini product of ultrafilters. Explicitly, a subset is large if its indicator is true after successively applying “for -almost every ” in the increasing coordinate order. Projection to any sublist has exactly that sublist's product ultrafilter. Hence for , pulling functions back along gives an elementary embedding by the Łoś theorem. These embeddings commute. Form their directed limit of elementary embeddings; each finite tuple lies in one stage, so induction on formulas makes the stage embeddings elementary.
At a stage containing , let be the class of the coordinate function . If , equality of these coordinate functions is small: for a fixed first coordinate there is only one possible equal second coordinate, and a singleton is not in . Thus . For any increasing , the truth of is the same nested ultrafilter test applied to , independent of the actual indices. This is precisely indiscernibility in the expanded language. Its Skolem hull, and the term-transport construction above, finish the second proof. Both constructions give the required model and the extended index automorphisms.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 27 4 b Solution Created 2026-10-03 Updated 2026-10-14
For nonempty first-order structures and an ultrafilter on , define the ultraproduct by quotienting the product domain byFunctions are interpreted coordinatewise; a relation holds when its coordinate truth set belongs to the ultrafilter. Closure under finite intersections makes these interpretations independent of representatives. The Łoś theorem asserts, for every formula ,
Prove it by structural induction. A term evaluates coordinatewise, by induction on its construction, so atomic equality and relations are exactly their defining truth sets. Conjunction uses intersection; negation uses the ultrafilter property that exactly one of a set and its complement belongs to . These establish all Boolean connectives.
For the existential step put . If an ultraproduct witness exists, induction says , and this set is contained in , so . Conversely if , choose a witness at every and any domain element at the other coordinates. Induction makes a witness. This coordinatewise selection uses choice in the metatheory; nonemptiness of the factors is essential. Universal quantification follows from negation and existence, completing the proof.
For the requested compactness theorem, let . For each finite , choose . For each sentence , its cone is nonempty, and intersections of finitely many cones contain the finite union of their requirements. These cones generate a proper filter. The ultrafilter lemma extends it to . The coordinate models satisfying include , so the Łoś theorem makes their ultraproduct satisfy . Since this holds for each , the ultraproduct is a model of . No completeness theorem is needed in this second compactness proof.
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 20 6 Solution Created 2026-10-03 Updated 2026-10-14
For the Ehrenfeucht-Mostowski theorem, let be an infinite first-order structure and any linear order. Choose a full Skolem expansion : add witness functions for existential formulas, repeat in the expanded languages, and take their union. We will construct a model of its theory containing distinct generators , , forming an order-indiscernible sequence.
Adjoin the elementary diagram of , the inequalities for , and for every expanded-language formula and every two increasing -tuples of indices, the sentencesEvery finite subcollection is satisfiable in . To prove this, choose a countably infinite sequence of distinct elements of , and for each of the finitely many relevant arities color its increasing index tuples by the finite vector of truth values of the formulas of that arity. Repeated applications of the Ramsey's theorem give an infinite subsequence homogeneous for all these finitely many finite colorings. Interpret the finitely many mentioned by its elements in their index order. All indiscernibility and distinctness constraints hold, and the finite diagram fragment holds because the ambient structure is still .
By compactness theorem, a model of the full enlarged theory exists. Its Skolem hull generated by the is elementary: whenever an existential formula with parameters in holds in , its chosen witness function returns a value in , so the Tarski-Vaught test applies. Its reduct is a model of . If the index order has size , the hull has size at most , and it contains distinct generators.
Every order automorphism of induces the automorphismTo check well-definedness, write any two terms being compared over the same increasing list of their generators. Their equality is an expanded-language formula; indiscernibility of the order-indiscernible sequence preserves its truth under . The same argument preserves each relation, and the term construction preserves the functions. Applying gives the inverse. The extension is unique in the specified Skolem language since every hull element is a term in the generators; no uniqueness among all automorphisms of the reduct is being asserted. This proves the Ehrenfeucht-Mostowski theorem, including its usual automorphism consequence.
For simple typed set theory with atoms, use sorts , predicates for sets, and typed membership from sort to sort . Atoms have no members, extensionality compares sets, and every well-typed formula defines a set of the next sort. Typical ambiguity is the schema for every closed typed sentence, where the superscript raises all types by one.
Here are concrete full typed models before imposing the ambiguity schema. Choose increasing natural numbers and setThe auxiliary merely interprets the set predicate at the lowest sort. Define typed membership byThen the other objects of are atoms, regardless of their old membership. Every subset of has its representative in , giving comprehension even for formulas with higher-sort quantifiers and parameters. Extensionality holds for the set representatives and atoms have no typed members. The rank gaps leave infinitely many atoms at each sort, and all sorts are infinite.
Consider finitely many ambiguity instances with unraised sentences , and choose a fixed window length sufficient to include every sort used and its auxiliary predecessor. Color every increasing -tuple of natural numbers by the vector of truth values of these unraised sentences in its finite rank-window interpretation. There are only colors. The Ramsey's theorem gives an infinite homogeneous set. Choose successive points from it. The first points and last points have the same color, while the latter interpretation of is exactly the former model's interpretation of . The auxiliary predecessor shifts too, so this remains true for sentences mentioning the lowest set predicate. Extend the chosen rank sequence arbitrarily to interpret the remaining sorts. This yields a model of typed set theory satisfying all the specified ambiguity instances.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 23 1 b Solution Created 2026-10-03 Updated 2026-10-06
Take and the proper filter on a set . In the first-order language with unary predicates , let both factors be one-element first-order structures. Set true and false in the first factor, and reverse these truth values in the second.
The reduced product also has one element . Neither nor holds there: their truth sets are and , neither belonging to . ThusLogical disjunction can therefore break the equivalence. A union can belong to a filter on a set without either summand belonging to it; the corresponding union property does hold for an ultrafilter.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 23 2 b Solution Created 2026-10-03 Updated 2026-10-06
Let denote the universal consequences of a theory: all universal first-order sentences entailed by . A first-order structure satisfies exactly when it embeds into a model of , by the compactness theorem applied to its diagram of a structure.
The theory has algebraically prime models if, for every , there are and a structure embedding such that every structure embedding , , factors as for some structure embedding . Neither nor is required to be elementary.
For , simple closure means that every existential quantifier-free formula over which has a witness in has one in :Now take two models with common substructure . Since embeds into , it satisfies . Choose its algebraically prime extension , and embed into both and over .
If holds in , the image of in is a model of . The assumed simple closure of this image transfers a witness from into . Its embedding into then transfers the quantifier-free formula and its witness into . Thus the hypothesis of QET1 is satisfied. The second test follows: has quantifier elimination.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 23 4 a Solution Created 2026-10-03 Updated 2026-10-06
The quantifier rank measures maximum nesting depth:Two first-order structures are rank-n equivalent if they agree on all first-order sentences of quantifier rank at most . For tuples one similarly compares all such formulas evaluated at the tuples.
In the -round Ehrenfeucht-Fraïssé game, player I, the Spoiler, chooses an element from either structure each round; player II, the Duplicator, chooses an element in the other. After rounds the corresponding chosen tuples must define a partial isomorphism of structures: all atomic formulas, including equality and the interpretations of constants, have matching truth values. Repetitions must be respected. Failure of this condition is a loss for II.
The precise finite-vocabulary Ehrenfeucht-Fraïssé theorem is: for a finite relational language, allowing finitely many constants,The tuple version has the same conclusion when the corresponding tuples are fixed before play. The implication from a winning strategy to rank equivalence holds for arbitrary languages, by induction on formulas. For the converse, finite relational vocabulary ensures only finitely many rank-bounded types in a fixed tuple of variables; their defining formulas let one transfer the type of the next move. Without a finiteness hypothesis, the converse for the full atomic-diagram game need not hold. This qualification matters in the next part.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 23 5 e i Solution Created 2026-10-03 Updated 2026-10-06
Use the first-order language with one constant , take with equality only, and let . SetThis complete type contains and is isolated by that formula. In any first-order structure, at most one element can satisfy . In every , its interpretation of realizes , by elementary equivalence. Hence no elementarily equivalent model has infinitely many realizations of . An algebraic type can have a fixed finite number of realizations in every model.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 121 1 i Solution Created 2026-10-03 Updated 2026-10-05
For parameters , set-theoretic absoluteness means agreement of the two membership first-order structures:This must hold for every such parameter tuple. Equivalently, formula relativization to a class produces two formulas and whose truth values agree on tuples from . Agreement for parameters only in is not part of the definition. For a proper class in set theory, this notation is understood separately for each fixed first-order formula, rather than as an unrestricted truth predicate for the entire universe.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 4 Solution Created 2026-10-03 Updated 2026-10-05
One form of the Ehrenfeucht-Mostowski theorem says that, for every infinite first-order structure and every total order , an elementary extension contains distinct elements forming an order-indiscernible sequence. After a suitable Skolem expansion, their Skolem hull is a first-order model of , and every order automorphism of extends to a structure automorphism of that hull. If has a definable infinite linearly ordered subset , the generators may lie in and their order may agree with that definable order. Uniqueness of the extended structure automorphism is asserted in the chosen Skolem expansion, rather than for every structure automorphism of its reduct.
Here is an ultraproduct proof of the Ehrenfeucht-Mostowski theorem. First expand to with Skolem functions for all existential first-order formulas, iterating through the enlarged languages if necessary. This is done in the ordinary classical metatheory; the choice restriction in question 1 is not a restriction on this question. Fix a nonprincipal ultrafilter on .
We can obtain an infinite sequence of distinct elements in an elementary extension of by one preliminary ultrapower. For each choose a finite list of distinct elements of . Represent by the function taking the th entry when , with an arbitrary default otherwise. Distinctness holds on a cofinite set, so follows from Łoś theorem. In the definably ordered variant, first name any parameters defining , and choose each finite list increasingly inside instead; then and for . Infinitude of an ordered set supplies every finite increasing chain. This preparatory step uses no Ramsey theorem.
For a finite subset of , define the ultrafilter on by nested membership, in this order:where means . This is the ordered Fubini product of ultrafilters. Closure under intersections and the decision between a set and its complement hold at each nested level, proving it is an ultrafilter. For take the principal ultrafilter on the one-point product. PutIf , pull a function back along the projection . A test independent of an omitted coordinate is unchanged by its ultrafilter quantifier, so projection pushes to . The induced map is therefore an elementary embedding by Łoś theorem. These maps are coherent, giving a directed system indexed by finite subsets of .
Take its directed limit of elementary embeddings . One can verify elementarity directly: representatives of a finite tuple occur at a common stage; functions and atomic relations are interpreted there. In the existential step, a witness in the limit occurs with the parameters at some later common stage, and elementarity pulls the existence statement back. Thus every embeds elementarily into , which contains an elementary copy of .
For , let be the class of the coordinate function . Projection coherence makes this independent of . If , then for each fixed the set is cofinite. The nested test therefore gives . In the ordered variant, the same argument with gives and .
For every first-order formula of the expanded language and every increasing tuple , Łoś theorem givesThe right-hand side depends on the first-order formula and tuple length, not on the indices. This proves order indiscernibility in the expanded language. Let be the Skolem hull of the generators in . The Tarski-Vaught test gives , and its reduct is a first-order model of .
An order automorphism of acts byIndiscernibility makes this well defined: combine the finite supports of two term expressions into one increasing tuple, and apply indiscernibility to their logical equality. Applying it to relation first-order formulas proves preservation of all relations; the inverse is induced by . Every element of the hull is such a term, so the extension is unique among structure automorphisms preserving the Skolem expansion. MoreoverThis proves the theorem, including its ordered version and structure automorphism conclusion, using ultrapowers and a directed limit throughout.
A sufficient condition is that be first-order consistent, complete, and full in its own first-order language. Work in the allowed function-free setting. Since proves the logically valid first-order sentence , fullness guarantees at least one constant and a nonempty collection of names.
Form the carrier from equivalence classes of constant symbols underLogical equality logic makes this an equivalence relation. Interpret a constant by its class and interpret each relation symbol bySubstitution of equals makes this independent of representatives. This defines a canonical first-order structure because every carrier element is named by a constant.
The truth lemma, proved by induction on logical formulas with constants substituted for their free variables, saysAtomic formulas hold by construction; completeness and first-order consistency give the Boolean steps. For the existential step, a witness in the first-order structure is a named class, so its truth gives a proved instance and hence a proved existential sentence. Conversely a proved existential sentence has a constant witness by fullness, and the induction hypothesis realizes that instance in the first-order structure. The universal case follows by negation. Thus , provingThe witness condition is needed in the original first-order language; adding new constants produces a canonical first-order structure in an expanded first-order language, which is a different assertion.
A canonical first-order structure is generated by its names: every element is the value of a closed term. In the function-free setting permitted here, this means every element is the interpretation of a constant symbol. Equivalently, the natural map from closed terms modulo logical equality in the first-order structure onto its carrier is surjective. When canonical is defined specifically using constant names, the same definition and all the arguments below apply in this function-free setting.
A full set of first-order sentences has the witness property in its own first-order language: whenever it proves an existential sentence , some closed term satisfies that the set proves . In a deductively closed set, one can equivalently state this using membership of the first-order sentences. In the function-free setting the witness first-order term is a constant symbol. This is the Henkin witness property; fullness does not by itself replace the separate requirements of first-order consistency and completeness.
Use two expansions of the rational order. In the first interpret , so the named sequence is unbounded above. In the second interpret , so the named sequence is strictly increasing but has upper bounds in the rational order. Both expansions are countably infinite first-order models of the specified first-order theory.
An isomorphism preserving each would preserve the existence of an element greater than all the named constants, since any such element in one first-order structure would map to such an element in the other. The first first-order structure has none and the second has, for instance, . They cannot be isomorphic. ThusThe property of lying above all is an infinite partial type rather than a single first-order sentence. This is why its realization can distinguish the two first-order models without contradicting the completeness established in (iv).
A first-order theory is a set of first-order sentences in a fixed first-order language, often identified with its deductive closure. It is -categorical if it has a first-order model of cardinality and all first-order models of that cardinality are isomorphic as first-order structures in that same first-order language. In particular, an isomorphism must preserve the named constants as well as the order.
A first-order theory is complete if it is first-order consistent and decides every first-order sentence: for each it entails either or . Equivalently all its first-order models satisfy exactly the same first-order sentences. First-order consistency is included to exclude the vacuous first-order theory with no first-order models. The distinctions matter here: naming infinitely many ordered points changes countable categoricity without destroying completeness.
Every automorphism preserves all logical formulas by induction on their construction, so an automorphism taking to necessarily gives equal partial types.
For the converse, first note that a finite first-order structure is atomic by (ii). Thus in both cases every realized finite-tuple partial type has an isolating logical formula. Suppose two finite tuples have the same complete type, and choose a new element to extend the first tuple. Let isolate the realized partial type of . Sincelogical equality of partial types gives . Choose a witness . Isolation ensures and have the same complete type. In particular, if is distinct from the entries already used, their inequality logical formulas ensure is distinct from its corresponding entries. The resulting finite map is injective and partial elementary.
Start from , which is well-defined even for repeated coordinates because their logical equality patterns agree. Enumerate the carrier and extend alternately to include the next missing element in the domain and the next missing element in the range. For a range step apply the same extension argument to the inverse finite map. The union is an elementary bijection from onto itself: every finite tuple and every logical formula involving it is handled at some stage. It is therefore an automorphism taking to . In the finite case the construction terminates once all elements have been included.
HenceCountability makes the back-and-forth numeralwise enumeration in arithmetic exhaust the entire first-order structure; it cannot simply be dropped.
Let , with finite, and put . There are only finitely many competing tuples . For each whose complete type differs from that of , choose a logical formula true at and false at . Such a logical formula exists by the inequality of their complete types, negating a distinguishing logical formula if necessary.
Let be the conjunction of this finite list, or logical truth if the list is empty. It is true at , and every tuple satisfying it has the same partial type as . For each , the first-order sentenceis therefore true in and belongs to . The logical formula is first-order consistent with because it is realized at . It is consequently a principal formula of a type of the partial type, proving every partial type realized in a finite first-order structure is principal. Finiteness of the first-order structure, rather than finiteness of the first-order language, is what makes the conjunction finite.