An -type over a first-order theory is a set of logical formulas in the displayed free variables first-order consistent with . A complete type chooses exactly one of and for each such logical formula. Equivalently it is a maximal consistent such set. For parameter-free partial types the logical formulas use the original first-order language; partial types over parameters use additional names for those parameters.
A partial type is principal if some logical formula first-order consistent with implies every member of modulo :Such a is a principal formula of a type of the partial type. For a complete type it isolates that partial type, so principal complete types are exactly isolated types.
For a tuple in a first-order structure , its parameter-free partial type isIt is a complete type over because the first-order structure decides the truth of every logical formula at that tuple.
Use the first-order language with one equivalence relation . Let have exactly two equivalence classes, one countably infinite and one uncountable, with no further first-order structure. Its complete theory says that there are exactly two classes and both are infinite.
This first-order theory has quantifier elimination. To eliminate one existential logical variable from a conjunction of atomic formulas and negated atomic formulas, a logical equality either fixes its value, or finitely many inequalities exclude finitely many points. Its required equivalence-class membership is determined by the finitely many existing classes represented among the parameters. A required unused class exists exactly when fewer than two classes have already been used. Once its class is possible, infinitude supplies a point avoiding the finite exclusions. These tests are quantifier-free logical equality and equivalence conditions on the parameters. Disjunctive normal form and induction eliminate all quantifiers and also show completeness.
Thus a finite tuple's complete type is isolated by its finite equality-and-equivalence pattern. Every realized finite-tuple partial type is principal, so is atomic. In particular all individual elements have the same complete one-type, isolated by .
Choose in the countable class and in the uncountable class. Any automorphism taking to would give a bijection from their whole equivalence classes, impossible because their cardinalities differ. ThereforeIts uncountability is precisely what avoids the conclusion of (iii).
Adjoin to the negations of all closed-term instances of . If the resulting set had a first-order model , its ground-term substructure from (ii) would still first-order model . The assumed existential consequence therefore supplies a tuple in satisfying . Each is the value of a closed term .
Quantifier-free agreement between a substructure and its ambient first-order structure givescontradicting the adjoined negation of this very ground instance. Thusis unsatisfiable. Compactness theorem gives a finite unsatisfiable subset. Its finitely many ground negations imply that, for some finite list of first-order term tuples,If the finite subset already shows itself inconsistent and supplies no ground negations, choose any one closed-term tuple using the available constant; then any first-order sentence is a consequence of , so suffices. Otherwise the selected list is nonempty. This also explains why the conclusion contains a finite disjunction rather than necessarily one universal choice of a witness first-order term.
Here means a substructure, so the smaller carrier contains all named constants, is closed under every function symbol, and has each relation restricted from the larger first-order structure. First-order term evaluation on tuples from agrees in the two first-order structures. Consequently atomic formulas agree, and induction on Boolean connectives makes every quantifier-free formula agree as well.
Write an arbitrary universal sentence of as with quantifier-free matrix. Every tuple from is also a tuple from , so holds at that tuple in . Quantifier-free agreement transfers it to . Since the tuple was arbitrary, satisfies the universal sentence. ThusAn arbitrary subset without the substructure operations and relation restrictions would not be the hypothesis used by this formal proof.
The set is satisfiable if there is one -structure satisfying every first-order sentence in simultaneously. It is finitely satisfiable if each finite subset has a first-order model; that first-order model is allowed to depend on the chosen finite subset.
Thus the two statements have different quantifier orders:Satisfiability immediately implies finite satisfiability by using the same first-order structure for every finite subset. The converse is the substantive content of compactness theorem.
An -structure has a nonempty underlying set . It assigns to each constant symbol an element , to each -ary function symbol a function , and to each -ary predicate symbol a relation contained in . Logical equality, when included as logical equality, is interpreted as actual identity.
The arities belong to the specification of the first-order language. An assignment of logical variables to elements of then evaluates first-order terms recursively and determines satisfaction of logical formulas through the logical connectives and quantifiers. A first-order sentence has no free variables, so its truth in the first-order structure is independent of the assignment.
If , interpret each new constant in as the same element . Atomic logical formulas and their negations then have exactly their truth values in , so the expansion satisfies the diagram of a structure. If the inclusion is elementary, every logical formula with those named parameters has the same truth value, so the expansion satisfies the elementary diagram.
Conversely, from any expansion satisfying the diagram of a structure defineThe diagram of a structure contains whenever , so is injective. It contains every true function-value equation, so commutes with all operations and constants. Positive and negative relation instances ensure both preservation and reflection of the relations. Thus is an embedding of first-order structures. If the expansion satisfies the elementary diagram, for every logical formula and tuple it also givesso is an elementary embedding of first-order structures.
The precise conclusion for an arbitrary expansion is an embedding of first-order structures, rather than a literal inclusion of the original carriers. The source's inclusion notation is correct when one uses the customary identification of with its embedded copy, or requires the expansion to interpret as the actual element of a carrier already containing . With that naming convention, is the inclusion and the requested two equivalences follow exactly.
Without the convention the literal wording fails, even in the first-order language of logical equality: singleton first-order structures with carriers and have a diagram-satisfying expansion by sending the first first-order structure's named point to , but the first carrier is not a subset of the second. The embedding of first-order structures formulation proved above states the invariant result and makes the intended inclusion formulation precise.
Yes. In the additive first-order structure, the quantifier-free formulaholds exactly at zero, because cancellation in the additive group gives . This first-order formula uses only the permitted function symbol and equality; it does not require a constant symbol for zero.
Yes. Zero is the unique absorbing element of the multiplicative first-order structure. It is defined byZero satisfies this universal formula. Conversely, substituting the actual integer zero for in the semantic verification forces . This use of zero in the verification does not insert a constant symbol into the first-order formula.
For the additive first-order structure, letIt defines . These sets are pairwise distinct: if , the integer belongs to but not to . Thus there are infinitely many inequivalent one-variable first-order formulas modulo the complete theory of the additive integers. The Ryll-Nardzewski theorem implies that first-order theory is not aleph-zero-categorical.
For the multiplicative first-order structure define divisibility by . For , the first-order formulaasserts the existence of at least distinct integer divisors. The integer has exactly such divisors, namely for , so it satisfies but not any with . Again there are infinitely many inequivalent one-variable first-order formulas. The Ryll-Nardzewski theorem therefore implies the first-order theory of the multiplicative integers is not aleph-zero-categorical.
If is model-complete, the inclusion of a substructure of a first-order structure , both first-order models of , is a structure embedding and hence elementary. Therefore .
Conversely, assume every such inclusion is elementary, and take any structure embedding between first-order models of . Its image , with the induced first-order structure, is a substructure of isomorphic to , so it is itself a first-order model of . By hypothesis . The isomorphism preserves all first-order formulas, and composing it with this elementary inclusion shows that is an elementary embedding. Thus .
Take a countable elementary substructure of containing the named constant, using the Downward Lowenheim-Skolem theorem. Its reduct has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of is exactly the singleton-class predicate.
Choose new distinct elements . DefineIn , make a new singleton class. In , make a new doubleton class; keep every old class of unchanged. All three reducts are first-order models of the complete theory, and .
Expand by interpreting as singleton-class membership and retaining the original named constant from . The resulting countable first-order structures are each isomorphic to : all have infinitely many classes of each size, and the bijections of classes can be chosen to preserve the constant and its class. Hence they are first-order models of . Both inclusions and are genuine structure embeddings, since no class meeting was changed. The given quantifier elimination, together with the preceding implication to first-order model completeness, yieldsTaking reducts gives . Butso . There is no conflict with quantifier elimination in the expanded language: changes truth value, so is not a substructure of .
WriteThese are first-order formulas in the original language, not new predicate symbols. An axiomatization consists of the equivalence relation axioms for , the boundand, for every , the two sentencesThe first scheme supplies infinitely many singleton classes. The second supplies infinitely many distinct non-singleton classes; the size bound makes these doubletons.
Every countable first-order model has countably infinitely many classes of each size. A bijection between singleton classes, and another between doubleton classes followed by a bijection inside each matched pair, gives an isomorphism between any two countable first-order models. To infer completeness, suppose a sentence had different truth values in two arbitrary first-order models. The Downward Lowenheim-Skolem theorem supplies countable elementary substructures of those first-order models, which would still disagree on the sentence, contradicting the isomorphism just constructed. Thus all first-order models satisfy the same sentences. Since the original first-order structure satisfies the axioms, these axioms form a complete axiomatization of its first-order theory. This is the theory of infinitely many singleton and doubleton equivalence classes.
An omega-saturated model realizes every complete one-type over every finite subset of its domain that is consistent with the first-order structure's first-order theory with those named parameters. Equivalently, every partial type in a finite tuple over finitely many parameters that is finitely satisfiable in the first-order structure has a realization there. The equivalence follows by extending a partial type to a complete type; finite tuples can be handled one coordinate at a time.
For an example, take a countably infinite set in the language of equality alone. Over finitely many named elements, a complete one-type either requires equality with one of them or inequality with all of them. Both possibilities are realized. quantifier elimination for an infinite pure set follows by choosing a quantified variable either equal to one of the finitely many named values or distinct from all of them. Indeed every permutation fixing the parameters is a structure automorphism, and all other elements have the same type, so there are no further one-types. This first-order structure is omega-saturated.
For a counterexample, take , where . The parameter-free partial typeis finitely satisfiable: choose an integer beyond the finitely many excluded numerals. It is not realized in the first-order structure, because every natural number is one of those numerals. Any complete extension of this partial type is therefore omitted as well. Thus the standard successor first-order structure is not omega-saturated.
Write the ultrafilter as to distinguish it from first-order structure domains. On the direct product , putThe domain of the ultraproduct is the quotient . Its elements are classes . A constant is interpreted by , and a -ary function symbol byFor a -ary relation symbol,These definitions are independent of representatives: if finitely many input representatives are changed, the coordinates where all old and new inputs agree form a set in the filter. At those coordinates the interpreted outputs and relation truth values agree. Filter closure and upward closure therefore preserve the resulting quotient elements and truth conditions.
Totality of the binary relation is expressed byWhen is already an order, this adds comparability and makes it a total order. In fact this first-order sentence alone entails .
By the definition of semantic entailment, means that every first-order structure satisfying also satisfies . Let be any such first-order structure, and let be any element of its domain of a first-order structure. The instance of with gives , which is true only if is true. Since was arbitrary, . ThereforeThere is no exception for in the displayed totality axiom; that case is exactly what forces the reflexive relation property.
In this first-order structure, says and . Thus is an upper bound of . The universally quantified clause says that if is any other upper bound, then . Therefore is their least upper bound. In the usual total order on the natural numbers, this is their maximum:This describes a condition on the values assigned to the free variables ; itself is not a closed first-order sentence.
Use the intended first-order structure of real arithmetic, with
Int selecting the integers; is the parameter in . A suitable first-order formula isThe first condition requires a real square root of . The second excludes every representation as a rational number with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular, is written and there is no extra division symbol. A square root exists exactly when , and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on does not affect the claim about the principal square root. At the formula is false; for there is no real witness. The meanings of and as real arithmetic, not just the meaning of Int, are part of this interpretation.Two unary predicates suffice. Require all four unary predicate types to be inhabited:There are no constants, no logical equality and no nonunary predicates. Any two of these conditions disagree on at least one predicate, so one domain element cannot witness both. Hence every satisfying first-order structure has at least four elements, by distinct witnesses from incompatible unary predicates. Conversely take domain , and : the four elements realize the four displayed unary predicate types, respectively. These element names describe the example; they are not constants in the first-order sentence.
On the universe , interpret the first-order signature byThis assigns both constants, a total binary function, a unary relation and a binary relation, so it specifies a complete first-order structure. If and both hold, then , and hence , proving the consequent. If either premise fails, the implication is true. Thus the universally quantified implication holds for every pair of integers, nonvacuously for every pair of nonnegative integers. Distinct constant symbols need not denote distinct objects unless a separate axiom requires it.