Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2009 / B / 5

A theory is $\kappa$-categorical if it has a model of cardinality $\kappa$ and any two models of that cardinality are isomorphic. The existence clause prevents vacuous categoricity at cardinalities where there is no model.

To show that infinite-cardinal categoricity forces completeness, suppose $T$ were incomplete. Then some sentence $\sigma$ has both $T+\sigma$ and $T+\neg \sigma$ satisfiable, by completeness of first-order logic. Their models must be infinite because $T$ has no finite models. For an infinite $\kappa \ge |L|$, the upward and downward Löwenheim-Skolem theorems produce a model of each extension of cardinality exactly $\kappa$: pass to an elementary submodel of size at most $\max (|L|,{\aleph }_0)$ and then to the desired size, or reduce a larger model to that size. Categoricity makes these two models isomorphic, but one satisfies $\sigma$ and the other its negation. Contradiction. Therefore $T$ is complete. If language size is defined without automatically including ${\aleph }_0$, the infinite-cardinal qualification is explicit; the assumed existence of a $\kappa$-sized model and absence of finite models already force it here.

Let $F_n$ be the formulas whose free variables are among $x_1,\dots ,x_n$. Define $\varphi E_n(T)\psi$ when $T\models \forall \bar{x}(\varphi \leftrightarrow \psi )$. The n-variable Lindenbaum algebra quotient is a Boolean algebra, with meet, join and complement induced by conjunction, disjunction and negation; its zero and one are contradiction and truth classes. Its order is $[\varphi ]\le [\psi ]$ exactly when $T\models \forall \bar{x}(\varphi \to \psi )$.

The Ryll-Nardzewski theorem states that for a complete theory with infinite models in a countable language, the following are equivalent: the theory is countably categorical; for every finite $n$ there are only finitely many complete $n$-types over the empty set; and every Boolean algebra $F_n/E_n(T)$ is finite. Equivalently each such type is isolated. The countable-language and completeness hypotheses are essential parts of this formulation.

For each fixed finite tuple length $n$, use the finite conjunctionIt asserts that no nontrivial scalar combination vanishes, exactly linear independence. It is an $L$-formula because the field is finite and every scalar multiplication is named. Scalar coefficients are indices of function symbols, not variables ranging over a separate field sort. There is no single finite formula with arbitrarily many free variables; the assertion is a formula for each prescribed finite $n$.

Use the vector-space axioms: addition is an abelian group operation with identity zero; ${\lambda }_1(x)=x$; ${\lambda }_a{\lambda }_b(x)={\lambda }_{ab}(x)$; ${\lambda }_a(x+y)={\lambda }_a(x)+{\lambda }_a(y)$; and ${\lambda }_{a+b}(x)={\lambda }_a(x)+{\lambda }_b(x)$, with ${\lambda }_0(x)=0$. Group inverses may be expressed by ${\lambda }_{-1}$, so no extra inverse symbol is needed.

Add the dimension-unbounded schemeOver a finite field, a finite-dimensional space has finitely many Elements, while every infinite-dimensional space is infinite. Hence this scheme axiomatizes exactly the infinite underlying vector spaces requested. In this finite-field case the vector-space axiom list itself is finite; the infinitude of the additional dimension scheme is substantive.

No. Universal sentences are preserved under substructures. Every infinite $K$-vector space has its zero subspace as an $L$-substructure, since zero is named and every scalar multiplication preserves it. This one-element structure is not infinite and is not a model of $T$. Thus the model class is not closed under substructures and has no universal axiomatization, even relative to the vector-space axioms.

No. If a finite conjunction $\varphi$ axiomatized the infinite spaces, it would follow from the vector-space axioms together with all the $D_n$. Compactness would make it follow from finitely many of those axioms and dimension requirements. Let $N$ be at least every dimension mentioned there. The finite-dimensional space $K^N$ satisfies all vector-space axioms and those finitely many $D_n$, hence would satisfy $\varphi$. But it is a finite set and so cannot be a model of the purported axiomatization. This contradiction proves failure of finite axiomatizability, including finite axiomatizability relative to vector spaces.

For quantifier elimination for infinite underlying vector spaces, we first justify that formulas cannot make finer distinctions than their linear-equation data. In any infinite underlying vector space, eliminate an existential variable from a disjunction of conjunctions of linear equations and inequations. If an equation has a nonzero coefficient of that variable, solve for it and substitute. If none does, the inequations forbid only finitely many values, leaving an available value in the infinite domain; the remaining equations concern only the other variables. Terms are linear combinations, so induction gives quantifier elimination for $T$ and completeness, since closed terms reduce to zero.

For one variable there are two possible complete types, zero and nonzero. Both are isolated, and every definable set is their union. ThusFor types of pairs of vectors over a finite field, the linear relation kernel $\{(a,b)\in K^2:ax+by=0\}$ determines the complete type. If $q=|K|$, the possibilities are one rank-zero pair, $q+1$ rank-one directions, and one rank-two independent type. Concretely these are $(0,0)$; $x\ne 0$ with $y={\lambda }_a(x)$ for each $a\in K$; $x=0,y\ne 0$; and the independent pairs. Their isolating formulas are finite because $K$ is finite. HenceEvery class is the union of a selection of these atoms. Basis extension also shows that pairs with the same relation kernel are conjugate by a linear automorphism within any infinite-dimensional model.

Every vector space has a basis and is classified up to linear isomorphism by its dimension. Over a finite field, a vector is a finite linear combination of basis Elements. If the basis has infinite cardinality $\lambda$, the set of finite such combinations has cardinality $\lambda$: there are at least $\lambda$ basis vectors and at most a countable union of finite powers of $\lambda$, each of size $\lambda$. Thus the underlying cardinality of an infinite space equals its dimension.

Any two models of cardinality $\kappa \ge {\aleph }_0$ therefore have bases of cardinality $\kappa$. A bijection between their bases extends uniquely to an $L$-isomorphism. A space with that basis size exists, giving the required existence clause as well. Hence $T$ is categorical in every infinite cardinal.

The cardinality of a vector space is central: here “infinite” must continue to refer to the underlying set. Over a countably infinite field, every nonzero finite-dimensional space is already infinite. Thus the model class now consists of all nonzero $K$-vector spaces, not only infinite-dimensional ones.

Since independence of a pair is not definable over an infinite field, for (i), independence of a single vector is still $x\ne 0$, but independence of tuples of length at least two is not definable by one formula in this one-sorted language. Quantifier elimination follows from the linear-equation argument in the preceding part for all these infinite domains. Any candidate two-variable formula therefore involves only finitely many linear equations. Take an independent pair, and compare it with $(x,{\lambda }_{a}x)$, where $x\ne 0$ and $a\in K$ avoids the finitely many ratios making one of those nontrivial equations vanish. Both pairs satisfy the same listed atomic formulas, contradicting a proposed definition of independence. Longer tuple independence would define pair independence by existentially completing a pair inside an infinite-dimensional model, giving the same obstruction.

For (ii), the vector-space axiom schema together with $\exists x(x\ne 0)$ axiomatizes the infinite underlying spaces. For (iii), there is again no universal axiomatization, because the zero subspace is a substructure.

For finite axiomatizability with infinitely many scalar symbols, in (iv) there is no finite axiomatization in the full language: any finite axiom set mentions only finitely many scalar symbols. In a nonzero vector space alter an unused nonzero ${\lambda }_a$ to send zero to a nonzero vector, retaining all mentioned interpretations. The finite sentences keep their truth values, but a vector-space axiom is now false. Relative to the already imposed vector-space axioms, the extra condition is finitely axiomatized by the single nonzero-vector sentence. These absolute and relative answers must be distinguished.

For (v), the one-variable algebra still has two atoms and four Elements. In two variables the isolated atoms are $(0,0)$ and the countably many rank-one directions, represented by $x\ne 0,y={\lambda }_{a}x$ and by $x=0,y\ne 0$. There is also a nonisolated complete type of an independent pair. A formula using finitely many linear equations either picks finitely many isolated atoms, or contains that independent type and all but finitely many isolated atoms. Therefore $F_2/E_2(T)$ is the finite-cofinite Boolean algebra on a countably infinite set of atoms, with the independent type the extra nonisolated point in its Stone space. In particular this algebra is countably infinite, rather than the full power set of its atoms.

For (vi), dimension can be $1,2,3,\dots$ or ${\aleph }_0$ while the domain is countable, producing pairwise nonisomorphic countable models. Thus $T$ is not countably categorical. For an uncountable $\kappa$, a vector space over this countable field has cardinality $\kappa$ exactly when its dimension is $\kappa$, since in general a nonzero space has size $\max (|K|,\dim V)$ when that maximum is infinite. Basis bijections then give categoricity in every uncountable cardinal. Quantifier elimination also shows that these different positive dimensions are elementarily equivalent; independence of an arbitrarily long tuple is not being silently treated as definable over this infinite field.