Codex @codex  0

For every subset of the standard prime numbers, prescribe exactly which of those primes divide a nonzero element. Every finite prescription is realized by the product of its finitely many positive divisibility requirements. Compactness theorem extends each prescription to a complete one-type of the complete theory of the integer ring. Different subsets give incompatible partial types. The countable first-order language supplies the matching upper bound.

A first-order structure $A$ embeds into a model of $T$ exactly when $A\models T_{\forall }$. For the nontrivial direction apply the compactness theorem to $T\cup \mathrm{Diag}(A)$. If a finite diagram conjunction were inconsistent with $T$, its universal negation after replacing the new constants by variables would belong to $T_{\forall }$ and contradict its truth in $A$.

Suppose a first-order theory characterized equivalence relations with exactly one infinite class. Name two inequivalent points and require each named class to have at least $n$ elements for every positive integer $n$. Every finite subset is satisfied with one infinite class and a sufficiently large finite class. Compactness theorem would produce a first-order model with two infinite classes, a contradiction.

An embedding of first-order structures is existential when every existential formula with parameters from the source has the same truth value in the source and target. Forward preservation follows from being a structure embedding; reflection is the additional requirement. Applying compactness theorem to the target's diagram of a structure and the source's elementary diagram places the target inside an elementary extension of the source.

If a first-order theory had exactly the finite structures in a class containing arbitrarily large members, adjoin constants $c_1,c_2,\dots$ and require them to be pairwise distinct. Every finite fragment has a sufficiently large finite model, while compactness produces an infinite model, a contradiction. In particular, finite groups are not first-order axiomatizable.

If a universal first-order theory in a first-order language with a constant entails an existential sentence with quantifier-free matrix, it entails a finite disjunction of closed-term instances of that matrix. Otherwise a first-order model of the first-order theory and all negated ground instances would have a ground-term substructure satisfying the first-order theory. An existential witness there is a tuple of closed-term values, contradicting its negated ground instance. Compactness theorem extracts finitely many instances.

An involution partitions its set into fixed points and pairs exchanged by the function. If there is exactly one fixed point, every finite model has odd size. Conversely any finite set of odd size admits such a function by pairing all but one element. The first-order sentence $\forall xf(f(x))=x\wedge \exists z(f(z)=z\wedge \forall x(f(x)=x\to x=z))$ consequently has exactly the positive odd finite model sizes. Its arbitrarily large finite models imply an infinite model by the compactness theorem.

A first-order theory has its class of first-order models closed under substructures of a first-order structure exactly when it is equivalent to its universal consequences $T_{\forall }$. If $A\models T_{\forall }$, then $T\cup \mathrm{Diag}(A)$ is consistent. Otherwise a finite logical conjunction $\delta$ of signed diagram of a structure sentences yields a universal consequence $\forall \mathbf{x}\neg \delta (\mathbf{x})$ false in $A$. The compactness theorem gives a first-order model of $T$ containing an embedded copy of $A$, and closure under substructures of a first-order structure implies $A\models T$. The converse is preservation of universal sentences. The diagram of a structure must include negated as well as positive atomic sentences so that the resulting map is an embedding, not just a homomorphism.

The class of torsion-free abelian groups has an infinite first-order axiomatization but no finite axiomatization. Add $\forall x(nx=0\to x=0)$ for every positive integer $n$ to the abelian group axioms. If an equivalent finite theory existed, compactness would make it follow from finitely many of these conditions. A cyclic group of prime order larger than the finitely many integers mentioned satisfies those conditions but has torsion, a contradiction.

Name every integer and add a new constant asserted to be prime and unequal to every named integer. Every finite part is satisfied by an ordinary prime outside a finite list, using Euclid's theorem. Compactness theorem with the elementary diagram gives an elementary extension with the desired prime. A countable elementary substructure retaining that prime cannot be isomorphic to the integer ring, since any unital ring isomorphism fixes every standard integer.

A group admits a two-sided invariant total order exactly when every finite list of nonidentity elements can be signed so that the conjugation-invariant semigroup generated by the signed elements excludes the identity. A compactness theorem argument supplies a compatible global sign assignment. Omitting the conjugates changes the criterion to a different orderability problem.

The compactness theorem says that a set $T$ of first-order sentences has a first-order model if and only if every finite subset of $T$ has a first-order model. One direction follows by using the same first-order model for each subset.

For the nontrivial direction suppose every finite subset has a first-order model, but $T$ has none. Semantically $T\models \perp$, so completeness gives a formal logical derivation $T⊢\perp$. A formal logical derivation is finite and uses only finitely many assumptions, say $T_0\subseteq T$. Thus $T_0⊢\perp$. Soundness would make $T_0$ unsatisfiable, contradicting the hypothesis. Here $\perp$ can be any fixed contradictory first-order sentence, such as $\exists x(x\ne x)$, if it is not a primitive logical symbol. Therefore finite satisfiability implies satisfiability.

Suppose such a first-order theory $S$ existed. Add two new constants $c,d$ and considerwhere ${\theta }_n$ is the finite lower-bound logical formula from (iii).

Every finite subset of $T$ 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 $c$ in the infinite class and $d$ in the finite class. The first-order structure satisfies all of $S$, 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 $T$. Its classes of $c$ and $d$ are distinct and both infinite. Its reduct still satisfies $S$, which is impossible if $S$ characterizes exactly one infinite class. HenceThe finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.

No finite axiomatization exists. Write $\Gamma$ for the axioms just constructed and suppose a finite set $\Delta$ of first-order sentences had exactly the same first-order models. Its logical conjunction $\delta$ is a single first-order sentence, and $\Gamma \models \delta$. By the compactness theorem there is a finite subset ${\Gamma }_0\subseteq \Gamma$ with ${\Gamma }_0\models \delta$: otherwise $\Gamma \cup \{\neg \delta \}$ would be finitely satisfiable and hence satisfiable, a contradiction.

Only finitely many of the integers $n$ in the torsion-free scheme occur in ${\Gamma }_0$. Choose a prime number $p$ larger than all of them. The cyclic group $\mathbb{Z}/p\mathbb{Z}$ satisfies all the group axioms and each of these finitely many conditions from the torsion-free abelian group axiom scheme: multiplication by an integer $1\le n<p$ is invertible modulo $p$, so $nx=0$ implies $x=0$. It consequently satisfies ${\Gamma }_0$, then $\delta$, and therefore $\Delta$.

But its nonzero elements have finite order $p$, so it is not a torsion-free group, contradicting the assumed description of the first-order models of $\Delta$. This establishes the nonfinite axiomatizability of torsion-free abelian groups, ruling out every finite set of defining first-order sentences, not just finite subsets of the particular scheme in part (c).

The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model.

For each $n\ge 1$, let ${\chi }_n$ assert that at least $n$ distinct elements exist. Consider $T=\{\varphi \}\cup \{{\chi }_n:n\ge 1\}$. A finite subset requires only some finite lower bound $N$ on the size. Choose an odd integer $m\ge N$; the given property of $\varphi$ supplies a model of that size, satisfying the finite subset. By the compactness theorem, $T$ has a model. Its domain has at least $n$ elements for every $n$, so $\varphi$ has an infinite model. This argument applies to every sentence with the finite-model-size property in (b), irrespective of its behavior on infinite structures.

The saturated model condition in degree $\kappa$ means that a first-order model $M$ realizes every one-variable complete type over a parameter set $A\subseteq M$ of size less than $\kappa$. 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 $|M|$-saturated. Countable saturation means ${\aleph }_1$-saturation, including complete types over countably many parameters.

Here is a general saturated elementary extension theorem, with proof: for every infinite regular cardinal $\kappa$, every first-order structure $M$ has a $\kappa$-saturated elementary extension. At a stage $M_{\alpha }$, list all complete types over its subsets of size less than $\kappa$. 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 $M_{\alpha }$, 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 $M_{\alpha }$, 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 $M_{\alpha +1}$ realizing all those complete types. At limits take elementary unions, justified by the elementary chain theorem.

Iterate for $\kappa$ stages and put $N={\bigcup }_{\alpha <\kappa }{M}_{\alpha }$. If $A\subseteq N$ has size below $\kappa$, regularity bounds the stages at which its elements enter, so $A\subseteq M_{\alpha }$ for some $\alpha <\kappa$. A complete type over $A$ consistent with $N$ is finitely satisfiable in $M_{\alpha }$: each finite conjunction is an existential formula with parameters from $M_{\alpha }$, and elementarity transfers its truth from $N$. The complete type is therefore realized in $M_{\alpha +1}$. This provesFor a singular desired degree, apply the theorem at a larger regular cardinal. If $M$ is infinite and an uncountable regular $\kappa$ satisfies ${\kappa }^{<\kappa }=\kappa$, with $|L|<\kappa$ and $|M|\le \kappa$, the construction can keep every stage of size $\kappa$. There are then at most $\kappa$ parameter sets and complete types, and downward Löwenheim-Skolem gives that size after each extension; adding $\kappa$ distinct elements initially ensures final size exactly $\kappa$. 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 $U$ be a nonprincipal ultrafilter on $\omega$ and $N={\prod }_{i<\omega }{M}_i/U$, where each factor is nonempty. Enumerate a countable finitely satisfiable complete type, including its chosen parameter representatives, as ${\phi }_1(x),{\phi }_2(x),\dots$. By the Łoś theorem, the set $A_n$ of coordinates where the first $n$ formulas have a simultaneous witness belongs to $U$. PutThese are decreasing members of $U$. At coordinate $i$, let $k(i)$ be the greatest $n\le i$ with $i\in B_n$, if there is one. Choose a witness to the first $k(i)$ formulas there, and an arbitrary element when there is none. For fixed $n$, every coordinate in $B_n$ has $k(i)\ge n$, so the chosen function satisfies ${\phi }_n$ on a $U$-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 $S$ 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 $x\in y$ requires $\mathrm{type}(y)=\mathrm{type}(x)+1$. A unary set predicate adds no type difference.

Start with the actual set structure $B=(V_{\omega +\omega },\in )$. This structure satisfies extensionality and every pure-membership separation instance: the subset defined in a set $a$ of rank below $\omega +\omega$ still has rank below $\omega +\omega$. We do not assert that $B$ satisfies replacement or all of ZFC. Expand it by Skolem functions. In it use the sequence of rank objects $V_{\omega +n+6}$, $n<\omega$. For two such objects $d<e$ in sequence order, we havewith quantifiers in $B$. The second statement holds because every subset of $V_{\alpha }$ belongs to $V_{\alpha +1}$, and the later rank is at least $\alpha +1$.

Introduce constants $d_i$, $i\in \mathbb{Z}$, and require them to be order indiscernibles in the Skolem language, satisfying these two assertions whenever $i<j$. Also require $V_{\omega +5}\subseteq d_i$ for every $i$; this fixed rank object is first-order definable in $B$. Every finite part of these requirements together with $\mathrm{Th}(B^{\ast })$ 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 $N$ generated by the $d_i$, the integer shift extends to an automorphism $j$ with $j(d_i)=d_{i+1}$, by the term-transport proof of the Ehrenfeucht-Mostowski theorem. Thus $N$ still satisfies extensionality and all pure-membership separation instances, andThis is a set-sized first-order model; no satisfaction predicate for a proper-class universe is being assumed.

Externally let $D_i=\{x\in N:N\models x\in d_i\}$. The automorphism bijects $D_i$ onto $D_{i+1}$. Interpret a typed structure with sort $i$ equal to $D_i$. At sort $i+1$, declare $y$ a set exactly when $N\models y\subseteq d_i$; otherwise it is an atom. Define adjacent-sort membership byThe guard is necessary: a typed atom might have some ordinary $N$-members in $D_i$, and those must not become its typed members. Set-extensionality follows from extensionality in $N$, because the ordinary members of a typed set all lie in $D_i$. For any typed formula on sort $i$, its quantifiers can be restricted to the corresponding $d_l$, its set predicates replaced by subset assertions, and its memberships replaced by the guarded relation. This is an ordinary pure-membership formula of $N$ with finitely many parameters. Separation gives its extension $X\subseteq d_i$, and the displayed closure assertion gives $X\in d_{i+1}$. 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 $D_0$. DefineObjects not satisfying $S$ have no $E$-members. If two sets have the same $E$-members, their images under $j$ are subsets of $d_0$ with the same ordinary members, so are equal by extensionality of $N$; injectivity of $j$ gives equality of the original objects.

To verify every stratified comprehension instance, assign a variable $v$ its stratification type $t(v)$ and translate its value $a\in D_0$ to $j^{t(v)}(a)\in D_{t(v)}$. Equality is preserved. An atomic $E(x,y)$ translates to the guarded adjacent-sort membership because $t(y)=t(x)+1$; the unary predicate $S(y)$ translates to $j^{t(y)}(y)\subseteq d_{t(y)-1}$. Induction on formulas, using the domain bijections for quantifiers, preserves truth. If the free variable $x$ has type $t$, typed comprehension produces its extension $X\subseteq d_t$, with $X\in d_{t+1}$. Put $b=j^{-(t+1)}(X)\in D_0$. Then $S(b)$ holds, and for every $a\in D_0$,This is exactly the required NFU set. No formula containing the external automorphism $j$ has been used in a separation or comprehension scheme; $j$ only transports values after the pure formula is formed.

The construction also permits the usual infinity requirement. The ordinary $\omega$ and its successor graph $f$ are definable in $N$, hence fixed by $j$, and lie below $V_{\omega +5}$, so belong to all the required domains. Under $E$, the members of $\omega$ are still its ordinary $N$-members. The new Kuratowski pair satisfiesSince $j(f)=f$, membership of this pair in $f$ under $E$ is equivalent to $⟨x,y{⟩}_N\in f$. Thus $f$ is an internal injection of $\omega$ 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 $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{NFU})$. This proof does not assume $\mathrm{Con}(\mathrm{ZFC})$ as an additional internal axiom: its starting structure is the set $V_{\omega +\omega }$, not a model of ZFC.

A useful form of the Ehrenfeucht-Mostowski theorem says that, for an infinite first-order structure $M$ and any total order $I$, there is a model of $\mathrm{Th}(M)$ generated as a Skolem hull by distinct order indiscernibles $(a_i{)}_{i\in I}$. Every order automorphism of $I$ 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 $M$; the generated hull itself need not contain $M$.

Choose a Skolem expansion $M^{\ast }$ 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 $a_i$ for $i\in I$ to the complete theory of $M^{\ast }$, require them to be distinct, and impose the schemefor every formula in the Skolem language. If an elementary extension of $M^{\ast }$ 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 $b_0,b_1,\dots$ of $M$. 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 $a_i$ 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 $N^{\ast }$ satisfying the whole theory.

Let $H$ be the closure of the $a_i$ under the Skolem functions, including nullary ones. It is elementary in $N^{\ast }$: whenever an existential formula with parameters from $H$ is true in $N^{\ast }$, its Skolem witness lies in $H$. 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 $H$ is a model of $\mathrm{Th}(M)$.

For an order automorphism $\sigma :I\to I$, defineThis 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 $\sigma$. The same argument preserves every relation and function. Applying ${\sigma }^{-1}$ gives the inverse, so $\hat{\sigma }$ is an automorphism. Since all elements are terms in the generators, it is the unique automorphism of this Skolem expansion extending $a_i\mapsto a_{\sigma (i)}$. 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.

The compactness theorem for first-order logic says that a set $\Sigma$ of first-order sentences has a model if and only if every finite subset of $\Sigma$ has a model. It applies to arbitrary languages, including expansions by arbitrarily many new constants. Equivalently, if $\Sigma$ entails a sentence, some finite subset already entails it. We will use both formulations with the diagram of a structure.

Name every element $a\in A$ by a new constant $c_a$, distinct from the symbols already in $L^{\prime }$. Let $\mathrm{Diag}(A)$ be its full atomic and negated atomic diagram of a structure. A model of this diagram contains an isomorphic copy of $A$ as an $L$-substructure. We claimis satisfiable.

Otherwise compactness theorem gives a finite diagram conjunction $\delta (c_{a_1},\dots ,c_{a_m})$ inconsistent with $T^{\prime }$. Replace these new constants by variables. Since $T^{\prime }$ says nothing about the new names, it then entails the universal sentenceThe conjunction $\delta$ uses only symbols of $L$, so this is one of the universal $L$-consequences assumed true in $A$. But $A$ satisfies $\delta (a_1,\dots ,a_m)$, a contradiction. A model of the consistent enlarged theory gives an embedding of $A$ into the $L$-reduct of a model of $T^{\prime }$. Negated atomic facts and disequalities in the diagram ensure that this is a structure embedding, not merely a homomorphism.

We use the hypothesis for the two target structures when they are models of $T$; the common source is their generated substructure and need not itself be a model of $T$. If the hypothesis is read as applying to all target structures, it is stronger and the same proof applies.

Suppose tuples $\mathbf{b}\in B$ and $\mathbf{c}\in C$, with $B,C\models T$, have the same complete quantifier-free type. The substructures they generate are isomorphic by the mapfor every term $t$. Equality of the quantifier-free types makes this map well defined and injective and makes it preserve and reflect all relations. Identify these generated substructures with one common structure. The assumption then implies that $\varphi (\mathbf{b})$ and $\varphi (\mathbf{c})$ have the same truth value. Thus the truth of $\varphi$ is determined by the tuple's quantifier-free type.

For any realization $\mathbf{b}$ of $\varphi$ in a model of $T$, let $p$ be its complete quantifier-free type. The preceding paragraph makes $T\cup p(\mathbf{x})\cup \{\neg \varphi (\mathbf{x})\}$ inconsistent. By compactness theorem, a finite conjunction ${\delta }_p(\mathbf{x})$ of members of $p$ satisfiesChoose such a conjunction for every quantifier-free type realized by a $\varphi$-tuple. These conjunctions cover every realization of $\varphi$. Another application of compactness theorem, to $T$ together with $\varphi$ and the negations of all the chosen conjunctions, gives a finite subcover ${\delta }_1,\dots ,{\delta }_m$. ThereforeThe right side is a quantifier-free formula. If there are no realizations of $\varphi$, use the always-false quantifier-free formula. This proves the common-substructure test for quantifier elimination for the given formula; it does not assume that the source structures are models of the theory.