Soundness states that formal derivability implies semantic entailment:
For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.
Strong completeness states the converse:
Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.
Suppose such a first-order theory existed. Add two new constants and consider
where is the finite lower-bound logical formula from (iii).
Every finite subset of has a first-order model. Choose a first-order structure with exactly two equivalence classes: one countably infinite, and one finite of size at least the largest bound appearing in that subset. Interpret in the infinite class and in the finite class. The first-order structure satisfies all of , by its assumed characterization, and meets the finite demands on both named classes.
Compactness theorem in the language with the two new constants gives a first-order model of all of . Its classes of and are distinct and both infinite. Its reduct still satisfies , which is impossible if characterizes exactly one infinite class. Hence
The finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.
An -structure consists of a nonempty domain , an element for each constant symbol, a function for each -ary function symbol, and a relation for each -ary predicate symbol. When equality is part of the logic it is interpreted as actual identity on .
An assignment in a first-order structure is a function from logical variables to . It induces a term valuation of first-order terms recursively:
For an atomic formula, substitute these first-order term values into the interpreted relation, or compare them for equality. Extend satisfaction for a set structure through the truth tables of the logical connectives, and through the quantifier clauses
Thus the first-order structure and assignment in a first-order structure together determine truth values for all logical formulas. A first-order sentence has no free variables, so its truth does not depend on the assignment in a first-order structure.
The assertion that is a first-order model of means that every first-order sentence belonging to is true in the first-order structure:
Equivalently each first-order sentence is true under every assignment in a first-order structure, since first-order sentences have no free variables. The first-order sentences must all hold in the same interpretation of the language; one cannot select a different first-order structure for each member of .
For a countable first-order language, the Henkin construction introduces only countably many constant symbols: each round needs at most one for each logical formula, there are countably many finite strings in a countable alphabet, and countably many rounds suffice. There are therefore at most countably many closed terms. The term model, and also its quotient set by equality, has at most countably many elements.
It follows that every satisfiable theory in a countable first-order language has an at most countable first-order model. If the theory has no finite first-order model, the constructed first-order model is countably infinite. More generally the same counting argument gives a first-order model of cardinality at most for any satisfiable theory in language .
For the elementary-substructure version of the downward Löwenheim-Skolem theorem, begin with a first-order structure and a set of designated elements. Close , the named constant symbols and one initial element under the language's functions and under chosen witnesses in for existential formulas with parameters already chosen. Iterate countably often. The resulting set has cardinality at most , and its induced substructure is elementary: induction on logical formulas proves the truth equivalence, with the existential case supplied by the chosen witnesses. This is the same witness mechanism as the Henkin formal proof, now keeping witnesses inside a given first-order model.
A first-order structure consists of a nonempty domain , an interpretation of each constant symbol, a total function for each -ary function symbol, and a relation for each -ary predicate symbol. Logical equality is interpreted as actual identity.
An assignment in a first-order structure is a map from the variables into . It extends recursively to terms: , , and . Atomic truth is determined by membership of the resulting tuple in , or equality of the two term values. Negation reverses the truth value, and an implication is false exactly when its antecedent is true and its consequent false.
For a universal quantifier,
These clauses define a valuation on every formula by structural recursion. Only free-variable values affect a formula's truth; consequently a sentence has the same truth value under every assignment. This is a semantic assignment of domain elements, not a programming assignment operation.
The first-order terms are the least collection containing every variable and constant and closed under formation of whenever has arity and the are terms. A closed term has no variables.
The first-order formulas are the least collection containing the atomic formulas and of the appropriate arities, and closed under negation, logical implication, and universal quantification: from formulas one may form , , and , with the chosen fully parenthesized grammar. Only finite expressions obtained by these rules are formulas. No additional strings belong to either collection.
Terms denote elements under an assignment in a first-order structure; formulas receive truth values in a first-order structure. The two syntactic categories have different formation rules even when they use some of the same punctuation.
A set of sentences is satisfiable if some nonempty first-order structure in its language makes every sentence in the set true. Because the formulas are sentences, their truth is independent of the assignment in a first-order structure.
This is a semantic existence condition. Its equivalence with syntactic consistency is the content of the classical Gödel's completeness theorem, together with soundness.
A first-order structure for this language is , where is a nonempty set and is a total function. The logical equality symbol is interpreted as actual equality on ; there are no other nonlogical symbols to interpret.
Semantic consequence under an assignment means that for every first-order structure with the relevant first-order variable assignment into its domain,
More explicitly, in a fixed structure this is the satisfaction implication at ; logical consequence requires that implication in all structures and assignments. An assignment takes values in a particular domain, so a single set map is not silently shared between unrelated domains.
By induction on first-order formulas, their truth values depend only on the values of their free variables. A first-order sentence has none. If all formulas here are sentences, every displayed satisfaction statement, and therefore the consequence condition, is independent of .
In a two-element first-order structure, is false for every first-order variable assignment. Blind substitution of for yields , which is true. This does not express the original property evaluated at the value of the inserted term: it has changed a free parameter into a bound variable.
For a direct failure of the substitution axiom, use . On a two-element domain, is true, whereas the captured instance is false. Consequently an unrestricted A4 would prove a false implication. The free for substitution condition is necessary for soundness.
No such first-order axiom collection can force actual identity when the displayed symbol is treated as an ordinary relation. The duplication obstruction to axiomatizing identity proves this even for an infinite collection of extra axioms.
Start with any nonempty first-order structure in which the symbol is identity. Form and the surjection . Interpret each relation by pulling it back along ; in particular,
Interpret every function on first coordinates as in and choose second coordinate zero; likewise lift constants with second coordinate zero. Induction on first-order terms gives . Induction on first-order formulas then gives
The quantifier steps use surjectivity of , so every witness in lifts to .
Every proposed axiom valid with actual equality is therefore true in under every assignment, along with A1–A7. But holds for two different domain elements. Thus those axioms cannot enforce identity. The usual interpretation of logical equality as identity is a semantic requirement.
The saturated model condition in degree means that a first-order model realizes every one-variable complete type over a parameter set of size less than . Equivalently every finitely satisfiable such complete type is realized, since it can be extended to a complete type. Without a specified degree, saturated usually means -saturated. Countable saturation means -saturation, including complete types over countably many parameters.
Here is a general saturated elementary extension theorem, with proof: for every infinite regular cardinal , every first-order structure has a -saturated elementary extension. At a stage , list all complete types over its subsets of size less than . There is a set of them, since their formulas lie in a set-sized language. Add a witness constant for each complete type to the elementary diagram of , together with every formula in that complete type evaluated at its witness constant. A finite part mentions finitely many complete types and finitely many formulas from each; each finite conjunction is realizable in , and the witnesses for different complete types are unconstrained relative to each other. Thus the finite part is satisfiable. The compactness theorem produces an elementary extension realizing all those complete types. At limits take elementary unions, justified by the elementary chain theorem.
Iterate for stages and put . If has size below , regularity bounds the stages at which its elements enter, so for some . A complete type over consistent with is finitely satisfiable in : each finite conjunction is an existential formula with parameters from , and elementarity transfers its truth from . The complete type is therefore realized in . This proves
For a singular desired degree, apply the theorem at a larger regular cardinal. If is infinite and an uncountable regular satisfies , with and , the construction can keep every stage of size . There are then at most parameter sets and complete types, and downward Löwenheim-Skolem gives that size after each extension; adding distinct elements initially ensures final size exactly . The resulting model is saturated in the unqualified sense. The cardinal-arithmetic hypothesis belongs to this size refinement, not to the general existence theorem.
An explicit ultraproduct version is useful too. In a countable language let be a nonprincipal ultrafilter on and , where each factor is nonempty. Enumerate a countable finitely satisfiable complete type, including its chosen parameter representatives, as . By the Łoś theorem, the set of coordinates where the first formulas have a simultaneous witness belongs to . Put
These are decreasing members of . At coordinate , let be the greatest with , if there is one. Choose a witness to the first formulas there, and an arbitrary element when there is none. For fixed , every coordinate in has , so the chosen function satisfies on a -large set. Its ultraproduct class realizes the whole complete type. A countable language over a countable parameter set has only countably many formulas, so this proves countable saturation of a nonprincipal ultraproduct over omega.
For NFU, we give the rank-indiscernible construction of an NFU model explicitly. NFU has a unary predicate for sets, atoms have no members, extensionality applies to sets, and comprehension applies to every stratified formula. A stratification assigns integer types to variables so that equality uses equal types and requires . A unary set predicate adds no type difference.
Start with the actual set structure . This structure satisfies extensionality and every pure-membership separation instance: the subset defined in a set of rank below still has rank below . We do not assert that satisfies replacement or all of ZFC. Expand it by Skolem functions. In it use the sequence of rank objects , . For two such objects in sequence order, we have
with quantifiers in . The second statement holds because every subset of belongs to , and the later rank is at least .
Introduce constants , , and require them to be order indiscernibles in the Skolem language, satisfying these two assertions whenever . Also require for every ; this fixed rank object is first-order definable in . Every finite part of these requirements together with is satisfiable: color finite increasing tuples of the original rank sequence by the truth values of the finitely many formulas mentioned, and use Ramsey's theorem to get a homogeneous subsequence. The rank assertions hold for every increasing tuple there. The compactness theorem gives a model of the full theory. In its Skolem hull generated by the , the integer shift extends to an automorphism with , by the term-transport proof of the Ehrenfeucht-Mostowski theorem. Thus still satisfies extensionality and all pure-membership separation instances, and
This is a set-sized first-order model; no satisfaction predicate for a proper-class universe is being assumed.
Externally let . The automorphism bijects onto . Interpret a typed structure with sort equal to . At sort , declare a set exactly when ; otherwise it is an atom. Define adjacent-sort membership by
The guard is necessary: a typed atom might have some ordinary -members in , and those must not become its typed members. Set-extensionality follows from extensionality in , because the ordinary members of a typed set all lie in . For any typed formula on sort , its quantifiers can be restricted to the corresponding , its set predicates replaced by subset assertions, and its memberships replaced by the guarded relation. This is an ordinary pure-membership formula of with finitely many parameters. Separation gives its extension , and the displayed closure assertion gives . It is therefore a typed set witnessing comprehension. The automorphism shifts these sorted domains and preserves the set flags and guarded memberships.
Collapse the types onto . Define
Objects not satisfying have no -members. If two sets have the same -members, their images under are subsets of with the same ordinary members, so are equal by extensionality of ; injectivity of gives equality of the original objects.
To verify every stratified comprehension instance, assign a variable its stratification type and translate its value to . Equality is preserved. An atomic translates to the guarded adjacent-sort membership because ; the unary predicate translates to . Induction on formulas, using the domain bijections for quantifiers, preserves truth. If the free variable has type , typed comprehension produces its extension , with . Put . Then holds, and for every ,
This is exactly the required NFU set. No formula containing the external automorphism has been used in a separation or comprehension scheme; only transports values after the pure formula is formed.
The construction also permits the usual infinity requirement. The ordinary and its successor graph are definable in , hence fixed by , and lie below , so belong to all the required domains. Under , the members of are still its ordinary -members. The new Kuratowski pair satisfies
Since , membership of this pair in under is equivalent to . Thus is an internal injection of into itself omitting zero, giving a Dedekind-infinite set.
We have built a model of NFU, with infinity if it is included in the formulation, in ordinary ZFC metatheory:
In particular . This proof does not assume as an additional internal axiom: its starting structure is the set , not a model of ZFC.
A useful form of the Ehrenfeucht-Mostowski theorem says that, for an infinite first-order structure and any total order , there is a model of generated as a Skolem hull by distinct order indiscernibles . Every order automorphism of extends uniquely to an automorphism of the specified Skolem expansion of that hull. The model can be obtained inside an elementary extension of a Skolem expansion of ; the generated hull itself need not contain .
Choose a Skolem expansion by iteratively adjoining witness functions: for each existential formula in the current language choose a function returning a witness whenever one exists, with an arbitrary value otherwise. Repeat for countably many rounds. Every formula in the final language uses finitely many symbols, so has a witness function from a later round. Thus the expansion is Skolemized for its own formulas, as required for elementarity of its hull. Add constants for to the complete theory of , require them to be distinct, and impose the scheme
for every formula in the Skolem language. If an elementary extension of is desired, also add its elementary diagram with separate names for its elements.
Every finite part of this theory is satisfiable. Choose infinitely many distinct elements of . For each of the finitely many arities in that fragment, color increasing index tuples by the finite vector of truth values of the formulas occurring. Repeated applications of the infinite Ramsey theorem give an infinite subset on which all these vectors are constant. Interpret the finitely many in increasing-index order from that subset. This satisfies the finite indiscernibility requirements and distinctness, while the elementary diagram is satisfied by the named original structure. The compactness theorem gives a structure satisfying the whole theory.
Let be the closure of the under the Skolem functions, including nullary ones. It is elementary in : whenever an existential formula with parameters from is true in , its Skolem witness lies in . This is the Tarski-Vaught test, whose proof is induction on formulas, using precisely this witness property for the existential step. Hence the reduct of is a model of .
For an order automorphism , define
This is well-defined. If two terms denote the same element, write their equality as a formula on the combined increasing tuple of their indices; indiscernibility preserves that formula after transport by . The same argument preserves every relation and function. Applying gives the inverse, so is an automorphism. Since all elements are terms in the generators, it is the unique automorphism of this Skolem expansion extending . This proves the theorem.
One may require the indiscernibles to lie in any specified infinite sequence of the starting structure, or to satisfy additional finite-tuple properties holding along that sequence: the same finite satisfiability proof chooses its homogeneous subsequence there. This strengthened form is what the rank-domain construction of NFU uses. Uniqueness is asserted in the Skolem expansion, not for all automorphisms of its reduct.
For a relational first-order structure , form its Gaifman graph: distinct elements are adjacent when they occur together in a tuple of some interpreted relation. Let be graph distance, with distance infinite between different components. For a tuple , its radius- neighbourhood has universe
The neighbourhood structure is the induced relational structure on this set, expanded by constants marking the entries of in their original order. Its isomorphism type thus records the centres, not just the unmarked ball. For one binary graph relation, this is the usual union of the radius- graph balls. This formulation assumes the finite relational signatures used in the finite-model setting.
A complete type over is a maximal consistent set of first-order formulas in a fixed finite tuple of variables with parameters from , consistent with the theory of that parameter expansion. A first-order model is a saturated model of degree if every such type with is realized in . It suffices to require this for one-variable types and realize a finite tuple successively. Without a subscript, saturated commonly means -saturated; some contexts specify only finite-parameter saturation. We state the degree explicitly.
The saturated elementary extension theorem says that every first-order structure has a -saturated elementary extension for any specified infinite . It suffices to prove this for regular , since a larger regular degree implies the requested degree. At a single stage , list all complete one-variable types over all subsets of of size below . This collection is a set. Adjoin a witness constant for each type to the elementary diagram of and require that constant to satisfy its type. Every finite subset is satisfiable in : each type's finite conjunction has a witness there, and the finitely many new constants have no cross-constraints. The compactness theorem gives an elementary extension realizing all these types simultaneously.
Repeat this step along an elementary chain , taking unions at limit stages, and let be its union. The elementary chain theorem follows here by induction on first-order formulas: an existential statement true in the union has a witness in a later stage; elementarity brings an existential witness back to the earlier stage containing its parameters. Thus each stage is elementary in .
If has size below regular , all its elements lie in a single , by taking the supremum of their fewer-than- stage indices. Any complete type over consistent with is already consistent over , since these structures have the same parameter theory. It was therefore realized in . This proves -saturation of .
A corresponding theorem about full saturation is available with a stated cardinal-size hypothesis: if is uncountable regular, , and , then every infinite first-order model of size at most has an elementary extension of size which is -saturated. First adjoin pairwise distinct constants to the elementary diagram; every finite fragment is satisfiable because the original first-order model is infinite. A Skolem hull of their realizations and the original domain has size . There are at most small parameter sets and at most types over each of them. Compactness and the downward elementary-submodel construction keep each realization stage of size . Taking a Skolem hull of the preceding stage and the chosen witnesses closes under at most finite terms and proves this size bound and elementarity. The same length- chain is consequently a fully saturated model of size . The cardinal hypothesis is not silently asserted to hold for every cardinal.
We now prove consistency of NFU by the permitted alternative method of indiscernibles and a domain-shifting structure automorphism. This can start from an explicit set structure available in ZFC, so we need not assume that there is a first-order model of all ZFC. Let
and give the value off the natural numbers. Regard as a first-order structure, with a named object . The graph of is an external set in the metatheory; it need not be a member of . This structure is extensional and satisfies every separation instance in the pure membership language: any subset of has rank below and belongs to . It also satisfies, for natural ,
since a subset of has rank at most and hence belongs to .
Apply the indiscernible construction proved in question 7(i) to a Skolem expansion of this set structure, requiring to be increasing members of its named natural-number object. For every finite fragment use an increasing sequence of ordinary natural numbers in the initial structure in the Ramsey argument. The resulting generated elementary hull has an external structure automorphism with , preserving and the named . Put and . Then , and satisfies the displayed subset-containment assertion between successive domains. No claim that satisfies replacement is required.
All membership and subset statements about these objects are interpreted inside . The hull is necessarily externally nonstandard: the natural-number objects give an external descending chain. The external structure automorphism is not an object that must be definable within that first-order model.
On the external domain define
This is the rank-shifting NFU model with explicit set predicate. The guard is essential: an object not contained in could still have some ordinary members in , and must not thereby become a nonempty atom. The objects failing have no -members. If two objects satisfying have the same -members, their images under are subsets of with the same members, so extensionality in and injectivity of make the original objects equal. Thus set-extensionality and the atom condition hold.
It remains to prove every comprehension instance. Use the domains just constructed, equivalently , for integer sorts. The map is a bijection from the objects of to the objects of , and every subset of that exists in is an element of . In sort define the set predicate by ; from sort to define membership by ordinary membership guarded by .
For a stratified formula, assign integer types to its variables with equal types for equality and adjacent types for membership. Shift all types uniformly if necessary so the finitely many used types are nonnegative. Replace a variable of type by of its untyped value, quantify it over , and use the typed relations just described. Applying to the untyped definition shows that each atomic first-order formula has the same truth value under this translation; induction on connectives and quantifiers proves the same for the whole first-order formula. Importantly the translated first-order formula is an ordinary first-order formula of with finitely many domain and transformed-parameter constants, not a first-order formula containing the external structure automorphism as a predicate.
If the comprehension variable has type , separation in produces its extension . The subset-containment assertion gives . Put . Then , hence , and for every ,
This verifies stratified comprehension with arbitrary parameters. The empty extension gives a distinguished empty set; the always-true first-order formula gives a universal set. The unstratified Russell predicate is not an allowed comprehension instance. Thus
Starting from the actual set structure and applying compactness constructs a set first-order model, so this is a consistency proof in ZFC, not merely an assumption of Con(ZFC). It proves the requested consistency with an explicit interpretation; it does not depend on treating the much stronger full extensionality of NF as already consistent. The external is a tool of the construction, not an extra symbol permitted in NFU's comprehension scheme.
One useful form of the Ehrenfeucht-Mostowski theorem is this: for an infinite first-order structure and any total order , there is a first-order model of generated in a chosen Skolem expansion by an order-indiscernible sequence of distinct elements. Every order automorphism of induces an structure automorphism of this expanded hull. One can additionally obtain an elementary extension containing by including its elementary diagram. Uniqueness of the induced structure automorphism is asserted in the Skolem expansion, not among arbitrary structure automorphisms of the reduct.
Choose a Skolem expansion : for every existential first-order formula choose a witness function, satisfying . Iterate the expansion if necessary so witnesses are available for first-order formulas in the resulting language. Add constants and require for distinct indices. For every first-order formula of the expanded language and every two increasing index tuples, add
Together with , this is the indiscernibility theory.
Every finite fragment is satisfiable. It mentions only finitely many first-order formulas and index constants. Choose a countably infinite sequence of distinct elements of . For each relevant arity, colour increasing tuples from that sequence by the finite truth vector of all first-order formulas of that arity in the fragment. Successive applications of the infinite Ramsey theorem for r-sets leave an infinite subset homogeneous for each of these finitely many finite colourings. Interpret the finitely many index constants by distinct elements of that subset in increasing enumeration order. All the required truth-value equivalences then hold, and the original structure satisfies the finite part of its own theory.
If an actual elementary extension of is desired, include constants for its elements and the elementary diagram of . A finite fragment still contains only finitely many parameter instances; include those truth vectors in the same colourings. Thus finite satisfiability is unchanged. The compactness theorem now supplies a first-order model with the entire indiscernible sequence, and in the diagram version an elementary copy of .
Take the Skolem hull of the generators, including the diagram constants when present. The witness functions show directly that the hull is elementary: whenever an existential first-order formula with hull parameters is true in the ambient first-order model, its Skolem witness belongs to the hull. Induction on first-order formulas, or the Tarski-Vaught test, gives elementarity. Its reduct is therefore a first-order model of . In the version without diagram constants its cardinality is at most .
For an order automorphism , define
This is well defined. If two terms represent the same element, express their equality as a first-order formula on the increasing union of their generator indices. Indiscernibility and preservation of the index order carry that equality to the transported terms. The same argument for every relation shows preservation of the expanded structure; applying it to supplies the inverse. Every element is a term in the generators, so no other structure automorphism of the specified expansion can have the same action on them. Hence
For an application requiring the generators to lie in a definable infinite ordered class, impose that class predicate and its increasing-order first-order formulas too. The finite-fragment proof uses an increasing sequence in that class, so all these additional conditions are preserved. In particular the integer index order and its shift give the structure automorphism used in the NFU construction. The constants are order indiscernibles, not necessarily indiscernibles under arbitrary permutations of the index set.
An ultraproduct converts coordinatewise finite information into a single first-order structure. Let be nonempty structures in a common first-order language, and let be an ultrafilter on . In , set
The ultraproduct has these equivalence classes as its elements. Functions are interpreted coordinatewise; a relation holds of classes exactly when it holds on a -large set of indices. Intersecting finitely many large agreement sets shows that these interpretations are independent of representatives.
The Łoś theorem, which explains the construction's usefulness, says
Here is the proof. Induction on terms establishes the coordinatewise interpretation of atomic formulas. Finite intersections handle conjunction, and the ultrafilter property handles negation, since precisely one of a set and its complement is large. For an existential quantification, a witness class gives coordinate witnesses on a large set. Conversely, when the coordinate existential truth set is large, select a witness in each of those structures and a default element elsewhere. Its class is a witness in the ultraproduct. This uses choice. Structural induction on formulas now proves the theorem, with universal quantification obtained by negation.
Compactness. If every finite subset of a first-order theory has a model, take to be the finite subsets and choose . The cones for finite have the finite intersection property. Extend their filter to an ultrafilter by the ultrafilter lemma. For each , its cone is large, so the Łoś theorem makes the ultraproduct satisfy . This proves the compactness theorem, including theories of arbitrary set size.
Elementary extensions and nonstandard elements. An ultrapower uses a fixed structure at every coordinate. The diagonal map sending to the class of the constant function is an elementary embedding by the Łoś theorem. For a nonprincipal ultrafilter on , the class of in an ultrapower of the natural numbers exceeds every standard integer, because each corresponding tail is large. In an ultrapower of the real ordered field, the reciprocal of this element is positive and smaller than every positive standard reciprocal integer: an infinitesimal. These examples implement ordinary finite statements in a larger structure without claiming that every external subset or second-order assertion transfers.
Saturation. Such an ultraproduct over is countably saturated. To see the actual diagonal argument, list a finitely satisfiable type with parameters in the ultraproduct and fix representatives for those parameters. For each , the set of coordinates admitting a simultaneous witness to its first formulas belongs to by the Łoś theorem. Arrange that the decrease and put . The decrease, belong to , and have empty intersection. At coordinate , choose a witness to the first formulas, where is the largest with , or choose a default element if there is no such . For each fixed , on the large set . Therefore the resulting class realizes every formula. This proves countable saturation of an ultraproduct over omega; it does not assert saturation at all larger cardinalities.
Algebraic limits. Take finite fields indexed by the primes and a nonprincipal ultrafilter. Their ultraproduct is a field of characteristic zero: for every fixed positive integer , only finitely many primes divide , so on a large set. Every first-order sentence true in all finite fields holds in this infinite field, and more generally so does any sentence true for all but finitely many of the factors. This is a way to create an infinite field retaining uniform first-order information from finite fields. It does not make the field algebraically closed: the first-order sentence that every element is a square already fails in infinitely many of the factors.
Large cardinals. A countably complete ultrafilter gives a well-founded membership ultrapower of the universe. If it had an infinite descending chain represented by , each set
would be large. Countable completeness makes nonempty, giving an actual infinite membership descent at any index in the intersection, contrary to foundation. The Mostowski collapse therefore gives a transitive target and an ultrapower embedding .
For a measure on a measurable cardinal , every function with is constant on a large set: otherwise intersect the fewer than complements of all its fibres. Consequently fixes the ordinals below . The class of the identity function is below and above every constant class below , since all tails are large. Thus and its critical point is . Fine ultrafilters on that are normal ultrafilters on small subsets and kappa-complete yield the stronger embeddings witnessing supercompact cardinals.
These applications share a single principle: an ultraproduct preserves precisely the first-order information seen by its ultrafilter. Principal ultrafilters merely select a factor; nonprincipal ones can produce new sizes, elements and saturation. Existence of the needed ultrafilters and selection of coordinate witnesses are set-theoretic assumptions, and changing the ultrafilter may change the resulting model.
An ultraproduct assembles a family of nonempty first-order structures in one fixed language, using an ultrafilter to specify which coordinate statements hold almost everywhere. Its universe is
Functions are interpreted coordinatewise, and an -ary relation holds on when its coordinate truth set belongs to . Changing representatives changes such a truth set only off a -large set, so these definitions are well defined. A principal ultrafilter simply recovers its distinguished factor; a nonprincipal ultrafilter can produce new elements and structures.
The fundamental result is the Łoś theorem:
Prove it by structural induction on first-order formulas. Atomic formulas are the definition. Intersections handle conjunction, while exactly one of a set and its complement belongs to an ultrafilter, handling negation. For the existential step, if the coordinate existential truth set is in , use choice to select witnesses there and arbitrary values elsewhere; their product function is an ultraproduct witness. Conversely a product witness makes the coordinate existential truth set contain a -large set. Other connectives and universal quantification follow.
In an ultrapower, all factors are one structure . The diagonal map is an elementary embedding by the Łoś theorem. For a nonprincipal on , the class of in an ultrapower of the standard natural numbers is larger than every constant natural number, since each tail belongs to . This gives a nonstandard model of Peano arithmetic. Similarly, an ultraproduct of finite fields with distinct primes tending to infinity has characteristic zero: for every fixed positive integer , the equation fails in all sufficiently late factors. An infinite structure can therefore arise from finite factors.
Ultraproducts prove the compactness theorem. If each finite subset of a theory has a model , index these models by . The cones have the finite intersection property. Extend their filter to an ultrafilter using the ultrafilter lemma. The Łoś theorem makes the resulting ultraproduct satisfy every . This construction also gives elementary extensions realizing prescribed finitely satisfiable types.
A useful stronger property is countable saturation of an ultraproduct over omega. Let a countable type be finitely satisfiable in an ultraproduct over a nonprincipal on . Choose coordinate representatives of its parameters. Let be the coordinates where the first formulas have a simultaneous witness; then , the decrease, and we can replace by . At coordinate , choose a witness to the first formulas, where is the largest with , taking an arbitrary value if there is none. For each fixed , the set where is -large. Its class realizes the entire type. This proof uses countable incompleteness of , not arbitrary completeness or automatic saturation at larger cardinals.
Finally, complete ultrafilters connect ultraproducts to large cardinals. A countably complete ultrafilter prevents an externally infinite descending membership chain in an ultrapower of a well-founded universe: intersect the countably many coordinate truth sets and obtain an impossible descending chain at one coordinate. A kappa-complete nonprincipal ultrafilter on consequently supplies the ultrapower embedding associated with a measurable cardinal. Thus the same construction supports both elementary compactness arguments and large-cardinal embeddings, with the completeness hypothesis deciding which well-foundedness and closure properties survive.
Let be an externally countable model of ZFC, and let . In form the forcing order
This is the finite-function collapse to countable size. For every and , the internal sets
are dense: extend a finite function by assigning a missing input, and use a fresh input to put any required value in its range.
Externally enumerate all the dense subsets of which recognizes as dense. There are only countably many, because is countable. Recursively choose in the th such dense set and let be the upward closure of this descending chain. This produces a generic filter over . By the forcing theorem, its generic extension satisfies ZFC. The canonical forcing name is forced to be a function with domain and range : the dense sets and ensure exactly these assertions. Therefore
Its new first uncountable ordinal is accordingly different from .
For a transitive , ordinary evaluation of names gives the familiar literal extension. The question only assumes a countable model, so one must also cover externally ill-founded models. In that case use the quotient of the internally defined forcing names by forced equality modulo , with membership defined by forced membership. The internal forcing identities and the forcing theorem hold in and give a well-defined first-order structure satisfying every standard ZFC axiom. Check names embed the original membership structure, so identify their images with . Its domain is a quotient of a subset of the countable domain of , hence is externally countable. Thus the required extension exists even without assuming transitivity. It is a membership extension, not an elementary extension: the assertion that the parameter is uncountable changes truth value.