Model theory course of the University of Oxford (C1.1b)

Here parameter-free definability is intended: parameters are not silently added to the first-order language. A subset $D\subseteq A^n$ is a definable set when some $L$-first-order formula $\phi (x_1,\dots ,x_n)$ satisfiesA definable function is one whose graph is a definable set. Thus $f:A^n\to A$ is definable when an $L$-formula $\theta (\mathbf{x},y)$ satisfiesIn particular $\mathcal{A}\models \forall \mathbf{x}\exists !y\theta (\mathbf{x},y)$. Definability over a parameter set $B$ permits parameters from $B$ in these first-order formulas, equivalently new constants naming those parameters. That is a different requirement: allowing a parameter naming an element would immediately define its singleton.

Yes. In the additive first-order structure, the quantifier-free formulaholds exactly at zero, because cancellation in the additive group gives $x=0$. This first-order formula uses only the permitted function symbol and equality; it does not require a constant symbol for zero.

No. The map $s(x)=-x$ is an automorphism of a first-order structure for the additive integers, but it sends one to minus one. By automorphism invariance of parameter-free definability, every parameter-free definable singleton is fixed by every structure automorphism. The singleton containing one is not fixed, so it is not definable.

No. Definability of a function means definability of its graph. The same additive structure automorphism $s(x)=-x$ would have to preserve the graph of multiplication. It sends the graph point $(1,1,1)$ to $(-1,-1,-1)$, which is not a multiplication-graph point because $(-1)(-1)=1\ne -1$. This contradicts automorphism invariance of parameter-free definability.

No. Interpreting the printed ${\mathbb{Z}}^{⩾}$ as the nonnegative integers, negation is an additive structure automorphism carrying the positive integer one outside that set. The set is therefore not invariant under structure automorphisms and cannot have parameter-free definability. The same argument would apply if the notation were taken to mean the strictly positive integers.

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 $y$ in the semantic verification forces $x=0$. This use of zero in the verification does not insert a constant symbol into the first-order formula.

Yes. One is the unique identity element of multiplication, defined byThe integer one satisfies the first-order formula, and testing at the actual integer one forces any satisfying $x$ to equal one. Thus this is a parameter-free universal formula even though the language has no named identity.

No. Use the prime-sign automorphism of the multiplicative integerswhere $v_2(n)$ is the exponent of two in $|n|$, a P-adic valuation. For nonzero integers, $v_2(mn)=v_2(m)+v_2(n)$, so $s(mn)=s(m)s(n)$; the identity also holds when a factor is zero. The exponent of two is unchanged by changing the sign, hence $s(s(n))=n$. Thus $s$ is a multiplicative structure automorphism.

It fixes one and sends two to minus two. The addition-graph point $(1,1,2)$ is sent to $(1,1,-2)$, outside the graph of addition. By automorphism invariance of parameter-free definability, addition is not definable in the multiplicative reduct.

No. The prime-sign automorphism of the multiplicative integers from the preceding part sends the positive integer two to minus two. It therefore does not preserve the nonnegative integers, contradicting the necessary automorphism invariance of parameter-free definability. This also excludes definability of the strictly positive integers if that convention for the printed notation is used.

For the additive zero singleton, $x+x=x$ is already a quantifier-free formula, so it is also an existential formula and a universal formula with an empty quantifier block. If a nonempty block is required, add a dummy $\exists y$ or $\forall y$; first-order domains are nonempty.

For the two definable multiplicative singletons, existential formulas areIn the integers, the equation $x^2=x$ restricts $x$ to zero or one. In the first line, one never satisfies the inequality, whereas zero does with $y=1$. In the second, zero never satisfies it, whereas one does with $y=0$. The respective universal formulas are $\forall y(xy=x)$ and $\forall y(xy=y)$, as already verified.

Neither multiplicative singleton has a quantifier-free formula. In this constant-free, multiplication-only language, every term in the sole free variable $x$ is $x^k$ for a positive integer $k$. Every atomic formula $x^r=x^s$ is true at both zero and one. Every Boolean combination consequently has the same truth value at those two points, and cannot separate their singletons. This is the fact that zero and one have the same quantifier-free type in the multiplicative integers.

Thus additive zero admits all three forms; multiplicative zero and one admit existential and universal forms, but no quantifier-free form. All remaining cases were excluded from definability itself by structure automorphisms.

An aleph-zero-categorical theory has, up to isomorphism, exactly one first-order model of cardinality ${\aleph }_0$.

The Ryll-Nardzewski theorem says that, for a complete theory $T$ in a countable first-order language, with infinite first-order models, the following conditions are equivalent: $T$ is aleph-zero-categorical; for every positive integer $n$, its type space $S_n(T)$ of complete types over the empty set is finite; and, for every $n$, there are only finitely many $L$-formulas in $n$ free variables modulo equivalence over $T$. Here $\phi$ and $\psi$ are equivalent over $T$ when $T\models \forall \mathbf{x}(\phi \leftrightarrow \psi )$.

A partial type $p(\mathbf{x})$ is a set of $L$-first-order formulas in a fixed tuple $\mathbf{x}=(x_1,\dots ,x_n)$ jointly consistent with $T$. A complete type, the usual meaning of an $n$-type here, is maximal among such consistent sets: for each first-order formula $\phi (\mathbf{x})$ it contains exactly one of $\phi ,\neg \phi$.

Add new constants $\mathbf{c}$ and considerEvery finite subset is satisfiable by consistency of the type. The compactness theorem gives a first-order model of the full set. Its $L$-reduct is a first-order model of $T$, and the interpretations of $\mathbf{c}$ realize $p$. This proof applies to partial as well as complete types.

For a complete theory in a countable language, the types realized in every first-order model are exactly the isolated types. An isolated type has a consistent first-order formula $\theta \in p$ such that $T\models \forall \mathbf{x}(\theta \to \phi )$ for every $\phi \in p$. Completeness forces $T\models \exists \mathbf{x}\theta$, so every first-order model realizes $p$; the converse is the omitting types theorem. Countability is a hypothesis of that converse, not of the preceding compactness realization argument. For a partial type the corresponding criterion is an isolating consistent first-order formula, together with its existence in every first-order model; it need not itself belong to the partial type.

If $T$ is not complete, no one complete $n$-type can be realized in every first-order model of $T$: a complete type decides sentences, and two completions of $T$ disagree on some sentence. Thus the completeness and countability hypotheses must be retained when using the isolated-type characterization.

For the additive first-order structure, letIt defines $n\mathbb{Z}$. These sets are pairwise distinct: if $m>n>0$, the integer $n$ belongs to $n\mathbb{Z}$ but not to $m\mathbb{Z}$. 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 $d(y,x):=\exists z(yz=x)$. For $k\ge 1$, the first-order formulaasserts the existence of at least $2k$ distinct integer divisors. The integer $2^{k-1}$ has exactly $2k$ such divisors, namely $\pm 2^j$ for $0\le j\le k-1$, so it satisfies ${\psi }_k$ but not any ${\psi }_{\ell }$ with $\ell >k$. 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.

A complete theory is a consistent first-order theory deciding every sentence in its language:Equivalently, every two first-order models of $T$ are elementarily equivalent. Consistency excludes the vacuous situation in which a first-order theory has no first-order models and entails both alternatives.

A first-order theory has quantifier elimination if every first-order formula is equivalent over the first-order theory to a quantifier-free formula with the same free variables:Logical truth and falsity may be treated as the empty Boolean combinations when considering sentences in a language without closed terms. The assertion concerns first-order formulas with free variables, not merely sentences.

A model-complete theory is a first-order theory for which every structure embedding between two of its first-order models is an elementary embedding. Thus, if $f:\mathcal{A}\hookrightarrow \mathcal{B}$ is such an embedding, then for every first-order formula $\phi (\mathbf{x})$ and tuple $\mathbf{a}$ from $A$,first-order model completeness does not assert that every two first-order models are elementarily equivalent: it constrains embeddings that exist between first-order models, whereas completeness constrains all first-order models.

If $T$ is model-complete, the inclusion of a substructure of a first-order structure $\mathcal{A}\subseteq \mathcal{B}$, both first-order models of $T$, is a structure embedding and hence elementary. Therefore $\mathcal{A}⪯\mathcal{B}$.

Conversely, assume every such inclusion is elementary, and take any structure embedding $f:\mathcal{A}\to \mathcal{B}$ between first-order models of $T$. Its image $f[A]$, with the induced first-order structure, is a substructure of $\mathcal{B}$ isomorphic to $\mathcal{A}$, so it is itself a first-order model of $T$. By hypothesis $f[A]⪯\mathcal{B}$. The isomorphism $\mathcal{A}\to f[A]$ preserves all first-order formulas, and composing it with this elementary inclusion shows that $f$ is an elementary embedding. Thus $\boxed{T\text{ is model-complete}⟺(\mathcal{A}\subseteq \mathcal{B}\models T\Rightarrow \mathcal{A}⪯\mathcal{B})}$.

A structure embedding preserves and reflects all atomic formulas, hence all quantifier-free formulas by induction on Boolean combinations. If $T$ has quantifier elimination, replace any $\phi (\mathbf{x})$ by a quantifier-free $\theta (\mathbf{x})$ equivalent over $T$. For $\mathcal{A}\subseteq \mathcal{B}\models T$ and a tuple $\mathbf{a}$ from $A$,Thus $\mathcal{A}⪯\mathcal{B}$, and the preceding criterion proves $\boxed{\text{quantifier elimination implies model completeness}.}$

WriteThese are first-order formulas in the original language, not new predicate symbols. An axiomatization consists of the equivalence relation axioms for $E$, the boundand, for every $n\ge 1$, 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.

No. Let $S$ be the displayed infinite axiom set. Any finite subset $S_0\subseteq S$ mentions only finitely many of the two infinitude requirements. Choose $N\ge 1$ at least as large as every index mentioned. A finite equivalence relation with exactly $N$ singleton classes and $N$ doubleton classes satisfies $S_0$, but is not a first-order model of the complete theory.

If a finite axiomatization existed, let $\sigma$ be the conjunction of its axioms. Then $S\models \sigma$, so the compactness theorem gives a finite $S_0\subseteq S$ with $S_0\models \sigma$. Every first-order model of $S_0$ would then satisfy the full first-order theory, contradicting the finite first-order model above. This is the finite subaxiomatization from an equivalent finite theory argument: finite axiomatizability would force one finite fragment of the explicit axioms to suffice.

Take a countable elementary substructure ${\mathcal{B}}^{\prime }$ of ${\mathcal{A}}^{\prime }$ containing the named constant, using the Downward Lowenheim-Skolem theorem. Its reduct $\mathcal{B}$ has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of $P$ is exactly the singleton-class predicate.

Choose new distinct elements $u,v\notin B$. DefineIn $\mathcal{C}$, make $u$ a new singleton class. In $\mathcal{D}$, make $\{u,v\}$ a new doubleton class; keep every old class of $\mathcal{B}$ unchanged. All three reducts are first-order models of the complete theory, and $\mathcal{B}\subseteq \mathcal{C}\subseteq \mathcal{D}$.

Expand $\mathcal{C},\mathcal{D}$ by interpreting $P$ as singleton-class membership and retaining the original named constant from $B$. The resulting countable first-order structures ${\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime }$ are each isomorphic to ${\mathcal{B}}^{\prime }$: 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 $\mathrm{Th}({\mathcal{A}}^{\prime })$. Both inclusions ${\mathcal{B}}^{\prime }\subseteq {\mathcal{C}}^{\prime }$ and ${\mathcal{B}}^{\prime }\subseteq {\mathcal{D}}^{\prime }$ are genuine structure embeddings, since no class meeting $B$ was changed. The given quantifier elimination, together with the preceding implication to first-order model completeness, yieldsTaking reducts gives $\boxed{\mathcal{B}⪯\mathcal{C},\mathcal{B}⪯\mathcal{D}}$. Butso $\boxed{\mathcal{C}⋠\mathcal{D}}$. There is no conflict with quantifier elimination in the expanded language: $P(u)$ changes truth value, so ${\mathcal{C}}^{\prime }$ is not a substructure of ${\mathcal{D}}^{\prime }$.

The inclusion $\mathcal{C}\subseteq \mathcal{D}$ is a structure embedding between first-order models of the same complete theory, but it is not an elementary embedding, as the existential partner first-order formula at $u$ shows. Therefore the first-order theory is not model-complete. The facts $\mathcal{B}⪯\mathcal{C}$ and $\mathcal{B}⪯\mathcal{D}$ do not make the intervening inclusion elementary.

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 $(\mathbb{N};0,S)$, where $S(n)=n+1$. 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.

Here fixed means fixed setwise: $\sigma [D]=D$ for every structure automorphism $\sigma$, not that each point must be fixed individually. A parameter-free definable set has this invariance by automorphism invariance of parameter-free definability.

For the converse, first establish the needed saturation implies homogeneity step. In a countable omega-saturated model, a finite partial elementary map can be extended to include any prescribed additional element in its domain. Transfer the element's complete type over the old finite domain along the map. Each finite part of this transported type has a witness because the old map is elementary; the omega-saturated model realizes the full transported type. The inequalities in the type maintain injectivity. Apply the same construction to the inverse map to enlarge the range. Alternating these steps through an enumeration of the countable domain is the back-and-forth method, giving a structure automorphism. In particular, any two elements with the same complete type over the empty set are related by a structure automorphism.

Assume now that $D$ is finite and invariant, and fix $a\in D$. All realizations in $A$ of $p_a=\mathrm{tp}(a/\varnothing )$ belong to $D$, by the preceding homogeneity and the invariance assumption. Suppose that no parameter-free first-order formula ${\theta }_a\in p_a$ has all its realizations in $D$. Then every finite subset ofis satisfiable in $A$: conjoin the finitely many first-order formulas from $p_a$, and use the assumed absence of a defining neighbourhood inside $D$ to find a witness outside $D$. This is a partial type over the finite parameter set $D$. The omega-saturated model would realize it by an element outside $D$ with the same empty-set type as $a$, a contradiction. Hence such a ${\theta }_a$ does exist.

There are only finitely many $a\in D$, soFor $D=\varnothing$, use $x\ne x$. Thus finite invariant sets in a countable saturated structure are definable. Finiteness is used twice: the extra parameters form a finite set, and the final disjunction is a first-order formula rather than an infinite disjunction.

A filter on a set $I$ means a proper family $\mathcal{F}\subseteq \mathcal{P}(I)$ with $I\in \mathcal{F}$, $\varnothing \notin \mathcal{F}$, closure under finite intersections, and upward closure under inclusion. An ultrafilter is a maximal proper filter; equivalently, for every $X\subseteq I$, exactly one of $X$ and $I\setminus X$ belongs to it. A principal ultrafilter is $\{X\subseteq I:i\in X\}$ for some $i\in I$. A nonprincipal ultrafilter is one not of that form, equivalently one containing no finite set.

To prove the ultrafilter lemma using Zorn's lemma, order all proper filters containing $\mathcal{F}$ by inclusion. The union of any chain is a proper filter: finitely many members lie together in one filter of the chain, and no chain member contains the empty set. Thus every chain has an upper bound, and Zorn's lemma gives a maximal member $\mathcal{U}$.

For completeness, its decision property follows from maximality. If $X\notin \mathcal{U}$, adjoining $X$ cannot generate a proper filter. Hence some $F\in \mathcal{U}$ has $F\cap X=\varnothing$. Upward closure gives $I\setminus X\in \mathcal{U}$. Both complements cannot be members, since their intersection is empty. Therefore $\boxed{\mathcal{F}\subseteq \mathcal{U}\text{ for an ultrafilter }\mathcal{U}}$. Properness is essential; a family containing the empty set cannot extend to an ultrafilter.

Write the ultrafilter as $\mathcal{U}$ to distinguish it from first-order structure domains. On the direct product ${\prod }_{i\in I}{A}_i$, putThe domain of the ultraproduct is the quotient $({\prod }_i{A}_i)/\sim$. Its elements are classes $[\mathbf{a}]$. A constant $c$ is interpreted by $[(c^{{\mathcal{A}}_i}{)}_i]$, and a $k$-ary function symbol byFor a $k$-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.

The Łoś theorem states that, for every first-order formula $\phi (\mathbf{x})$ and product representatives ${\mathbf{a}}^1,\dots ,{\mathbf{a}}^r$,It extends the defining relation-symbol rule to arbitrary first-order formulas, including quantified ones.

Identify the countable index set with $\mathbb{N}$. A nonprincipal ultrafilter on it contains every cofinite set. Let $p(x)$ be a type over a finite parameter set in the ultraproduct $\mathcal{M}$, finitely satisfiable in $\mathcal{M}$. Because the language and parameter set are countable, enumerate it as ${\phi }_0(x),{\phi }_1(x),\dots$, with chosen product representatives for the parameters. By finite satisfiability and Łoś,Make these large sets decrease while forcing their intersection to be empty:For each index $i$, let $r(i)$ be the largest $n\le i$ with $i\in Y_n$, if one exists. Choose $b_i\in A_i$ satisfying the first $r(i)+1$ first-order formulas; this is possible because $i\in X_{r(i)}$. If no such $n$ exists, choose any $b_i$.

For each fixed $n$, every $i\in Y_n$ has $r(i)\ge n$, so $b_i$ satisfies ${\phi }_n$. Its coordinate truth set contains $Y_n$ and belongs to $\mathcal{U}$. Another use of Łoś gives $\mathcal{M}\models {\phi }_n([\mathbf{b}])$ for every $n$. Thus $[\mathbf{b}]$ realizes the type. This proves the countable saturation of an ultraproduct over omega, and in particular the ultraproduct is omega-saturated. The construction chooses a finite number of requirements at each coordinate; it does not presume the whole infinite type has a witness in any factor.

Let $P_1$ and $P_3$ be the sets of primes congruent to one and three modulo four. Both are infinite. For $P_1$, if a finite list contained them all, put $N=(2p_1\cdots p_r{)}^2+1$. Any prime divisor $q$ of this odd number is new and has minus one as a square modulo $q$, hence belongs to $P_1$ by the given criterion. For $P_3$, use $N=4p_1\cdots p_r-1$. It is three modulo four, so at least one of its odd prime divisors is three modulo four; none of the listed primes divides $N$. These are elementary Euclidean proofs of infinitely many primes in each odd residue class modulo four.

On the set of all primes, the cofinite sets together with $P_1$ have the finite intersection property; so do the cofinite sets together with $P_3$. Extend the generated filters to ultrafilters ${\mathcal{U}}_1$ and ${\mathcal{U}}_3$ using the ultrafilter lemma. They are nonprincipal because they contain every cofinite set, including the complement of any singleton. FormEvery sentence of $\Sigma$ has a cofinite truth set, hence belongs to both ultrafilters. The Łoś theorem shows $F_1,F_2\models \Sigma$. In particular they are fields, since each field axiom holds in every factor.

For each fixed positive integer $n$, the sentence $n\cdot 1\ne 0$ holds in ${\mathbb{F}}_p$ unless $p$ divides $n$. Its truth set is cofinite, so both fields satisfy it. Therefore $\boxed{\mathrm{char}{F}_1=\mathrm{char}{F}_2=0}$.

Finally the sentence $\exists x(x^2+1=0)$ holds at exactly the primes in $P_1\cup \{2\}$. This set belongs to ${\mathcal{U}}_1$, whereas its complement contains $P_3$ and belongs to ${\mathcal{U}}_3$. Łoś therefore givesThus minus one is a square in the first characteristic-zero first-order model of $\Sigma$ and is not a square in the second. The construction also shows why eventual truth over all primes need not decide a sentence whose truth splits along two infinite prime subsequences.