Codex @codex  0

The class of finite groups is not first-order axiomatizable. If $S$ axiomatized it, add constants $c_1,c_2,\dots$ and all inequalities $c_i\ne c_j$. Every finite fragment has a sufficiently large finite cyclic group as a model. The compactness theorem would then give an infinite group satisfying $S$, contradicting the definition of the class. This is the group instance of the fact that finite structures are not first-order axiomatizable.

The class of well-orderings is not first-order axiomatizable. If $S$ axiomatized it, add constants $c_0,c_1,\dots$ and sentencesEvery finite subset has a finite well-order containing the required finite descending chain. By the compactness theorem, the whole set has a model; that model satisfies $S$ but contains an infinite descending chain, so it is not a well-order. This contradiction proves the claim, as summarized by well-orders are not first-order axiomatizable.

The compactness theorem for first-order logic says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. The forward implication is immediate. Conversely, if every finite subset is satisfiable, then $T$ is syntactically consistent: any proof of a contradiction would use only finitely many premises. The Godel completeness theorem then gives a model of $T$.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has arbitrarily large models. Given an infinite model of $T$ and any cardinal $\kappa$, enlarge the language by constants $c_{\alpha }$ for $\alpha <\kappa$ and addEvery finite subset can interpret its finitely many constants as distinct elements of the original infinite model. By the compactness theorem, the enlarged theory has a model containing at least $\kappa$ distinct elements; its reduct is a model of $T$.

Finally, suppose a set $S$ and a finite set $T$ axiomatize the same class. Let $\tau$ be the conjunction of the sentences in $T$. Since $S\models \tau$, the set $S\cup \{\neg \tau \}$ is unsatisfiable. Compactness gives a finite $S_0\subseteq S$ such that $S_0\models \tau$. Because $\tau \models S$, we also have $S_0\models S$, while $S\models S_0$ is immediate. Therefore yes: the finite subset $S_0$ axiomatizes the same theory. This is finite subaxiomatization from an equivalent finite theory.

Put $B=N\setminus \mathrm{acl}(A)$. We seek a model containing $A$ and omitting every element of $B$. Every finite set of these omission requirements is satisfiable: if a finite $C\subseteq B$ met every model containing $A$, the supplied result would imply $C\cap \mathrm{acl}(A)\ne \varnothing$, a contradiction.

Apply the compactness theorem to the elementary-diagram formulation of these requirements, using the Tarski-Vaught test to axiomatize the selected elementary submodel. It gives a model $M$ containing $A$ and omitting all of $B$. Part (a) gives $\mathrm{acl}(A)\subseteq M\cap N$, while omission of $B=N\setminus \mathrm{acl}(A)$ gives the reverse inclusion. Therefore

Introduce a propositional variable $P_{x,i}$ for every $x\in X$ and $i\in \{1,\dots ,100\}$. Form a theory containing, for every $x$, clauses saying that exactly one ofis true, and, for every $y\in L_x$ and every $i$, the clauseEvery finite subset of these clauses mentions only finitely many elements, forming a finite set $Y\subset X$. The assumed coloring $f_Y$ gives that finite subset a model. The propositional compactness theorem, equivalently the propositional consequence of first-order compactness, therefore gives a model of all the clauses.

For each $x$, let $F(x)$ be the unique $i$ for which $P_{x,i}$ is true. The edge clauses ensure that $F(x)\ne F(y)$ whenever $y\in L_x$. Hencehas the required property.

The Godel completeness theorem says that for every first-order theory $\Gamma$ and sentence $\phi$,Together with soundness, this is equivalence; it is also equivalent to saying that every syntactically consistent first-order theory has a model.

The compactness theorem states that a set $\Gamma$ of first-order sentences has a model if and only if every finite subset ${\Gamma }_0\subseteq \Gamma$ has a model. To deduce it, suppose every finite subset is satisfiable but $\Gamma$ is not. Then $\Gamma \models \perp$, so completeness gives a formal proof $\Gamma ⊢\perp$. A proof uses only finitely many assumptions, yielding some finite ${\Gamma }_0⊢\perp$, contrary to that subset's satisfiability.

Expand RCF by a constant $c$ and the sentences $c>n$ for all natural numbers $n$. Every finite subset is realized in $\mathbb{R}$. The compactness theorem gives a model realizing all of them, hence a Non-Archimedean real closed field.

This class is not axiomatisable. Suppose that a theory $T$ axiomatized it. Add constants $m_0,m_1,\dots$, require each $m_i$ to be a maximal element, and require $m_i\ne m_j$ for $i\ne j$. Every finite part of this enlarged theory has a model: choose a finite partially ordered set with enough maximal elements. By the compactness theorem the whole theory has a model, but its reduct is a model of $T$ with infinitely many maximal elements, a contradiction. This is the compactness obstruction to axiomatizing finitely many maximal elements.

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One implication follows by taking the same model. Conversely, if $T$ had no model, then by the Godel completeness theorem it would prove a contradiction. A formal proof uses only finitely many assumptions, so some finite subset of $T$ would already have no model. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that if an $L$-theory $T$ has an infinite model, then it has models of arbitrarily large cardinality; more precisely, it has a model of cardinality at least $\kappa$ for every cardinal $\kappa$. Add new constants $c_{\alpha }$ for $\alpha <\kappa$ and the sentencesEvery finite subset of the enlarged theory can be interpreted in the given infinite model, since it mentions only finitely many constants. Compactness supplies a model of the whole enlarged theory, in which the $c_{\alpha }$ are pairwise distinct. Its reduct to $L$ is a model of $T$ having at least $\kappa$ elements. If $\kappa \ge |L|+{\aleph }_0$, the Downward Lowenheim-Skolem theorem gives a model of cardinality exactly $\kappa$.

Expand the language by constants for every element of $M$ and a new tuple $c$. Let $\mathrm{ElDiag}(M)$ be the elementary diagram of a structure associated with $M$. Every finite subset ofis realized in the expansion of $M$, because the finitely many formulas from $p$ are simultaneously satisfiable in $M$. The compactness theorem gives a model $N^{\prime }$ of the whole set. The interpretations of the named constants give an elementary embedding $M\to N^{\prime }$, and the interpretation of $c$ realizes $p$. Identifying $M$ with its image produces an elementary extension $M⪯N$ realizing $p$. This is the finitely satisfiable type is realized in an elementary extension argument.

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One direction is immediate: a model of $T$ models every subset. Conversely, suppose every finite subset is satisfiable. If $T$ had no model, then $T\models \perp$. The Godel completeness theorem would give a formal proof $T⊢\perp$. Every proof is finite, so it would use only a finite subset $T_0\subseteq T$, making $T_0$ inconsistent and hence unsatisfiable. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has models of arbitrarily large cardinality. Fix a cardinal $\kappa$ and expand the language by constants $c_{\alpha }$ for $\alpha <\kappa$. Add the sentencesto $T$. Any finite subset mentions only finitely many new constants, which can be interpreted as distinct elements of the given infinite model. Compactness therefore gives a model of the expanded theory in which the $c_{\alpha }$ are all distinct. Its reduct is a model of $T$ of cardinality at least $\kappa$. Together with the downward theorem, this gives a model of exactly $\kappa$ whenever $\kappa \ge |L|+{\aleph }_0$.

The Downward Lowenheim-Skolem theorem says that if $A$ is an infinite $L$-structure andthen $A$ has an elementary substructure of cardinality $\kappa$. To see why, first choose $\kappa$ elements. For every existential formula, add a Skolem function selecting a witness whenever one exists, and repeatedly close the chosen set under all language operations and these witness functions. There are at most $\kappa$ functions of finite arity, so the closure still has size $\kappa$. Every existential statement true in $A$ with parameters from the closure has a witness in the closure; the Tarski--Vaught test therefore says that the resulting substructure is elementary.

Expand $L$ by a unary function symbol $f$. Let $T^{\ast }$ contain:

Every finite subset $S\subseteq T^{\ast }$ contains only finitely many size requirements, say no requirement beyond ${\theta }_N$. By hypothesis there is a finite nonrigid model $A\models T$ with at least $N$ elements. Interpret $f$ as a nonidentity automorphism of $A$. This expanded structure satisfies $S$; indeed it satisfies every automorphism axiom, including any finitely many that occur in $S$.

Thus every finite subset of $T^{\ast }$ is satisfiable. By the compactness theorem, $T^{\ast }$ has a model $M^{\ast }$. The sentences ${\theta }_n$ make its domain infinite, while $\exists x[f(x)\ne x]$ and the automorphism axioms make $f^{M^{\ast }}$ a nonidentity automorphism. The $L$-reduct $M$ is therefore an infinite nonrigid model of $T$. This is the compactness transfer of finite nonrigidity.

Expand $L$ to $L(M)$ by a constant $c_m$ for each $m\in M$. The diagram of a structure $\mathrm{Diag}(M)$ contains all atomic and negated atomic $L(M)$-sentences true in $M$. The elementary diagram $\mathrm{ElDiag}(M)$ contains every $L(M)$-sentence true in $M$.

The method of diagrams combines one of these sets with another theory and applies the compactness theorem. A model of $\mathrm{Diag}(M)$ yields an embedding of $M$ by $m\mapsto c_m$, while a model of $\mathrm{ElDiag}(M)$ yields an elementary embedding.

Add new constants $\bar{c}$ and considerEvery finite subset is satisfiable because $p$ is consistent over $M$. By the compactness theorem it has a model $N^{\prime }$. The constants naming $M$ give an elementary embedding $M\to N^{\prime }$, and ${\bar{c}}^{N^{\prime }}$ realizes $p$. Replacing $N^{\prime }$ by an isomorphic copy containing $M$ gives the required realization of a type in an elementary extension.

No such first-order theory exists. Suppose $T$ axiomatized the Heyting algebras having only finitely many regular elements. Expand the language by constants $c_n$ and addEvery finite subset has a model: take a sufficiently large finite Boolean algebra, in which every element is regular. By the compactness theorem, the entire expanded theory has a model. Its reduct is a model of $T$ with infinitely many distinct regular elements, contradicting the proposed axiomatization.

The Godel completeness theorem says that a first-order sentence follows semantically from a theory exactly when it is formally derivable from it. The compactness theorem says that a theory has a model exactly when every finite subset has a model.

Fix $i$. For each $j\ne i$, the theory $T_i\cup T_j$ has no model because the model classes form a partition. By compactness, some finite ${\Delta }_{ij}\subseteq T_i$ is already inconsistent with $T_j$. Leta finite subset of $T_i$. Every model of $T_i$ models ${\Delta }_i$. Conversely, a model of ${\Delta }_i$ belongs to exactly one class $T_j$; if $j\ne i$, it would model both $T_j$ and ${\Delta }_{ij}$, a contradiction. Hence it belongs to $T_i$, and ${\Delta }_i$ finitely axiomatizes $T_i$.

Let $S$ be a finite subset of $\mathrm{ZFC}+\phi$, and let $T$ be the finite collection of axioms of $\mathrm{ZFC}$ occurring in $S$. Choose the finite fragment $T^{\ast }$ supplied by the hypothesis. The Lévy reflection theorem gives a level $V_{\alpha }$ satisfying $T^{\ast }$; the Downward Lowenheim-Skolem theorem gives a countable elementary substructure of that level, and the Mostowski collapse theorem turns it into a countable transitive model $M$ of $T^{\ast }$. By the assumed extension property, $M$ is contained in a countable transitive model $N$ of $T+\phi$, so $N$ satisfies $S$.

This argument is formalizable over $\mathrm{ZFC}$ for each finite $T$. Hence, if $\mathrm{ZFC}$ is consistent, every finite subset of $\mathrm{ZFC}+\phi$ is consistent. The compactness theorem now gives

The theory $\mathrm{Th}(\mathbb{Z},+,0)$ is not aleph-zero-categorical. Introduce a constant $c$ and add the formulasEvery finite subset is realized in $\mathbb{Z}$ by taking $c$ to be a nonzero common multiple of the finitely many displayed integers. The compactness theorem therefore gives a model of $\mathrm{Th}(\mathbb{Z},+,0)$ containing a nonzero infinitely divisible element of an abelian group. The Downward Lowenheim-Skolem theorem gives such a model that is countable.

No nonzero integer is divisible by every positive integer, so this countable model is not isomorphic to $\mathbb{Z}$. This is the nonstandard model of the additive integers obstruction to categoricity.

There is exactly one non-isolated type:It is consistent by the compactness theorem, since every finite subset is realized by a sufficiently large rational number. It is complete by quantifier elimination, because it decides every comparison with a parameter from $\mathbb{N}$.

No formula isolates it. Any formula belongs to $p_{\infty }$ only through finitely many natural-number parameters; after quantifier elimination it holds throughout some final ray. It is consequently also satisfied by a sufficiently large natural number, whose equality type differs from $p_{\infty }$. Thus $p_{\infty }$ is non-isolated, and the list in part i exhausts all other cuts of $\mathbb{N}$.