Vector spaces

1. Preliminaries: the theory of vector spaces over a field

Throughout this section we fix a field $K$ and using this define a first-order language $L_{K}$ for $K$ -vector spaces (or left $K$ -modules) as follows. $L_{K}$ has all the usual logical symbols from first-order logic as well as a constant symbol $0$ for the zero vector, a binary function symbol $+$ for vector addition, a unary function symbol $-$ for additive inverse of vectors, and for each $λ \in K$ a unary function symbol $s_{λ}$ for scalar mulitiplication by $λ$ .

In this language we axiomatise the notion of $K$ -vector space of positive dimension. The axioms are,

Axioms for an abelian group:
- $\forall x \forall y \forall z (x + (y + z) = (x + y) + z)$
- $\forall x \forall y (x + y = y + x)$
- $\forall x (x + 0 = x)$
- $\forall x (x + (- x) = 0)$
Axioms for scalar multiplication:
- $\forall x (s_{λ} (s_{μ} (x)) = s_{λ μ} (x))$ , for all $λ, μ \in K$
- $\forall x (s_{λ} (x) + s_{μ} (x) = s_{(λ + μ)} (x))$ , for all $λ, μ \in K$
- $\forall x (s_{λ} (x + y) = s_{λ} (x) + s_{λ} (x))$ , for all $λ \in K$
- $\forall x (s_{1} (x) = x)$

Observe that there is no quantification over the field $K$ , and to avoid this disallowed quantification we need infinitely many axioms, at least if the field $K$ is infinite. However, the axioms above are all first order and (apart from the last) are all universal (i.e. the only quantifier present is $\forall$ and this only appears positively). It is immediate therefore that a substructure of a $K$ -vector space (as presented in this language) is also a $K$ -vector space.

Exercise.

Check you understand the comment about substructures of a $K$ -vector space. In particular, with this choice of language, what closure conditions are implicit in the notion of a substructure?

Because the notation $s_{λ} (x)$ is rather cumbersome and not in line with normal notation, we shall write it as $λ x$ . It is important therefore to keep in mind which numbers are elements of the field, and which are vectors.

We use the notation $T_{VS} (K)$ for the theory of vector spaces over $K$ , i.e. the $L_{K}$ -theory just given.

It is not clear at this stage how to specify in a first-order way the dimension of the vector space. We can, however, easily describe the case when the dimension is not zero, i.e. the space is not trivial:

\exists x \neg (x = 0)

Exercise.

If $K$ is finite there are finitely many axioms listed above. Show that in this case these axioms do not form a complete theory (even including the nontriviality axiom) by finding two models of the theory and exhibiting a $L_{K}$ -sentence true in one of your models and not the other.

2. Completeness and categoricity

We already know all the models of the theory $T_{VS} (K)$ . They are the vector spaces over $K$ of dimension $0, 1, 2, 3, \dots$ and of infinite dimensions $κ$ for all cardinals $κ$ . Applications of Zorn's lemma show that every $K$ -vector space has a basis and any two $K$ -vector spaces of the same dimension are isomorphic.

We are going to use this to determine some of the elementary properties of the theory $T_{VS} (K)$ . One of the first questions is: is it a complete theory?

Proposition.

If $K$ is finite, then $T_{VS} (K)$ is not complete. In fact the consistent completions of $T_{VS} (K)$ are $T_{VS} (K) \cup \{τ_{k}\}$ for $k = {|K|}^{n}$ , $n \in ℕ$ (where $τ_{k}$ says there are exactly $k$ elements, see Exercise 10.7 on page 146) and $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ (where $σ_{n}$ says there are at least $n$ elements).

Proof.

If $|K|$ is finite, then the vector space of dimension $n \in ℕ$ has exactly $k = {|K|}^{n}$ elements, and any two such vector spaces of dimension $n$ are isomorphic. Thus $T_{VS} (K) \cup \{τ_{k}\}$ is consistent and categorical (has exactly one model up to isomorphism) and hence by a variation of Theorem 11.32 on page 171 is complete.

Similarly, if $|K|$ is finite, then the vector space of countably infinite dimension has $ℵ_{0}$ elements, and any countably infinite vector space must have dimension $ℵ_{0}$ . (This is because, by standard results on cardinal arithmetic, if the dimension is $κ > ℵ_{0}$ the space would have $κ$ elements and if the dimension is $κ < ℵ_{0}$ the space would have ${|K|}^{κ} < ℵ_{0}$ elements.) Thus $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ is consistent and $ℵ_{0}$ -categorical and hence by Theorem 11.32 on page 171 is complete.

By and large, theories with only finite models (such as $T_{VS} (K) \cup \{τ_{k}\}$ ) are uninteresting from the point of view of model theory. We record a property of the interesting extension of $T_{VS} (K)$ in the next proposition. The proof has already been given.

Proposition.

If $K$ is finite, then the only complete extension of $T_{VS} (K)$ with infinite models is $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ . This theory is $κ$ -categorical (Definition 11.31) for all infinite $κ$ .

If $K$ is infinite, we have the following.

Proposition.

Suppose $K$ is infinite. Then $T_{VS} (K)$ is $κ$ -categorical for all $κ > max (|K|, ℵ_{0})$ and hence is complete. $T_{VS} (K)$ is not $λ$ -categorical for some other infinite cardinals such as $λ = |K|$ .

Proof.

If $κ > max (|K|, ℵ_{0})$ then by cardinal arithmetic every vector space of dimension $κ$ has $κ$ elements. (Exercise: check this, using the fact that the space is in one-to-one correspondence with the set of function $f : κ \to K$ of finite support.) Therefore $T_{VS} (K)$ is $κ$ -categorical and hence complete.

By cardinal arithmetic again, a space of dimension $n$ (where $n = 1, 2, \dots, ℵ_{0}$ ) over $K$ has cardinality $|K|$ . These are all nonisomorphic, and hence $T_{VS} (K)$ is not $|K|$ -categorical.

3. Model completeness and elimination of quantifiers

Here, I want to look in detail at $T_{VS} (K)$ when $K$ is infinite and particularly when $K$ is countably infinite and also at $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ when $K$ is finite. For an example of a countable field, one might take the field of rational numbers, or the rational numbers extended by adding $\sqrt{2}$ .

The specific questions to ask are how one model of the theory relates to another. In particular, if one model has dimension less than the other it embeds in it as a substructure. What more can we say about this embedding?

In model theory, the "nice" embeddings are so-called elementary embeddings:

Definition.

Let $L$ be a first order language and $M$ be a substructure of the $L$ -structure $N$ . Then $M$ is an elementary substructure of $N$ , $N$ is an elementary extension of $M$ , if the truth of every $L$ formula is preserved from $M$ to $N$ , i.e. $M ⊨ ϕ (\overline{a}) N ⊨ ϕ (\overline{a})$ for every $ϕ$ and every $\overline{a} \in M$ .

An embedding $f : M \to N$ of $L$ -structures is an elementary embedding if the image $f M$ of $f$ in $N$ is an elementary substructure of $N$ .

So we want to know which embeddings, substructures, extensions of models of our theory of vector spaces is elementary. Questions like this (especially for algebraic theories like the current one) are often solved by elimination of quantifiers. An example of elimination of quantifiers was given in Exercise 11.46. In that case, the quantifier elimination was given by a detailed construction by hand. Here we will use our knowledge of the models to make life easier for us. We start with some very general results that apply to all theories.

Definition.

A theory $T$ in a first order language $L$ has elimination of quantifiers if for every formula $ϕ (\overline{x})$ of $L$ there is a formula $ψ (\overline{x})$ of $L$ with the same free variables such that $T ⊢ \forall \overline{x} (ϕ (\overline{x}) ψ (\overline{x}))$ .

Not all theories have elimination of quantifiers, and some have elimination of quantifiers only when new functions or relations are added to the language.

Proposition.

Suppose $T$ is a complete $L$ -theory and the following property holds for all models $M$ of $T$ :

whenever $A$ is a substructure of $M$ and $f$ is an embedding from $A$ onto another substructure $f A$ of $M$ then there is an elementary extension $N ⊨ T$ of $M$ and an automorphism $h$ of $N$ such that $h$ restricted to $A$ is $f$ .

Then $T$ has elimination of quantifiers.

Proof.

We assume that $T$ does not have elimination of quantifiers and show the condition fails. So suppose $ϕ (\overline{x})$ is a formula not equivalent to any quantifier-free formula $ψ (\overline{x})$ . Obviously we must have that $T \cup \{\exists \overline{y} ϕ (\overline{y})\}$ is consistent, for else $ϕ (\overline{x})$ would be equivalent to $x_{1} \neq x_{1}$ or some other absurdity. By completeness of $T$ we may assume therefore that $T ⊢ \exists \overline{y} ϕ (\overline{y})$ .

We argue that by compactness there is a model $M ⊨ T$ with $\overline{a} \in M$ , $\overline{b} \in M$ such that:

$M ⊨ ϕ (\overline{a})$
$M ⊨ \neg ϕ (\overline{b})$
$M ⊨ ψ (\overline{a}) ψ (\overline{b})$ for every quantifier-free formula $ψ (\overline{x})$ .

Subproof.

Indeed, let $ψ_{1} (\overline{x}), \dots, ψ_{n} (\overline{x})$ be finitely many quantifier-free formulas of $L$ . Let us show that there is a model $M ⊨ T$ with $\overline{a}, \overline{b} \in M$ such that $M ⊨ ϕ (\overline{a}) \land \neg ϕ (\overline{b})$ and $M ⊨ ψ_{i} (\overline{a}) ψ_{i} (\overline{b})$ for $i = 1, \dots, n$ .

Let $S$ be the set of all $A \subseteq \{12 \dots n\}$ such that $T \cup \{ϕ (\overline{a})\} \cup \{\underset{i \in A}{} ψ_{i} (\overline{a}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{a})\}$ is consistent. We shall show that if there is no model as in the last paragraph then the formula $χ (\overline{x})$ defined to be $\underset{A \in S}{} (\underset{i \in A}{} ψ_{i} (\overline{x}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{x}))$ is a quantifier-free formula equivalent in $T$ to $ϕ (\overline{x})$ . Note that by the definition of the sets $A$ we already have $T ⊢ \forall \overline{x} (ϕ (\overline{x}) \to χ (\overline{x}))$ . For the other direction, if there were some $A \in S$ and model of $T$ with $\overline{b}$ such that $\neg ϕ (\overline{b}) \land \underset{i \in A}{} ψ_{i} (\overline{b}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{b})$ we'd be done, since $T ⊢ \exists \overline{x} (ϕ (\overline{x}) \land \underset{i \in A}{} ψ_{i} (\overline{x}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{x}))$ (as by definition of $A$ this is consistent with $T$ and $T$ is complete so proves all sentences consistent with it). This means there would be some suitable $\overline{a}$ in the same model as $b$ satisfying $ϕ (\overline{a})$ and the same $ψ_{i} (\overline{x})$ as $\overline{b}$ . Otherwise (by the completeness of $T$ again) $T ⊢ \forall \overline{x} (\neg ϕ (\overline{x}) \to \neg \underset{A \in S}{} (\underset{i \in A}{} ψ_{i} (\overline{x}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{x})))$ which gives the other direction of the equivalence, $T ⊢ \forall \overline{x} (\underset{i \in A}{} ψ_{i} (\overline{x}) \land \underset{i \notin A}{} \neg ψ_{i} (\overline{x})) \to ϕ (\overline{x})$ between $ϕ (\overline{x})$ and $χ (\overline{x})$ .

We let $M$ be the model of $T$ given by this compactness argument, and let $A$ be the substructure of $M$ generated by $\overline{a}$ , i.e., $A$ is the set of all $t (\overline{a})$ for $L$ -terms $t$ in $\overline{a}$ . We define the embedding $f : A \to M$ to be the map sending $\overline{a}$ to $\overline{b}$ , and sending all terms $t (\overline{a})$ to the corresponding term $t (\overline{b})$ . That this is an embedding follows from the fact that $\overline{a}$ and $\overline{b}$ satisfy the same quantifier-free formulas. But this shows that the condition in the the hypothesis of the proposition is incorrect, as in neither $M$ nor in any elementary extension of $M$ can we have $\overline{a}$ sent to $\overline{b}$ by an automorphism, since we have $ϕ (\overline{a})$ and $\neg ϕ (\overline{b})$ in $M$ and in any elementary extension, and automorphisms preserve structure and therefore necessarily preserve truth in the model.

Exercise.

Use saturated models to show a converse to the previous proposition and to give a model theoretic condition equivalent to a complete theory having elimination of quantifiers.

We now return to vector spaces.

Theorem.

Let $T$ be $T_{VS} (K)$ for an infinite field $K$ or $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ when $K$ is finite. Then $T$ has elimination of quantifiers.

Proof.

The condition in the proposition is an elementary fact about vector spaces proved using Zorn's lemma: given a subspace $U$ of $V$ and an embedding $f : U \to V$ (i.e. a $K$ -linear map $U \to V$ with kernel $0$ ) this $f$ can be extended to an automorphism of $V$ . To do this take a basis $B$ of $U$ , and simultaneously extend both $B$ and $f B$ to bases of $V$ so that the definition of $f$ is extended to the whole of $V$ .

Theorem.

Let $U$ of $V$ be infinite $K$ -vector spaces with $U$ a subspace of $V$ . Then $U$ is an elementary substructure of $V$ when considered as $L_{K}$ -structures.

Proof.

Write $T$ for the theory of $U, V$ , i.e. $T$ is $T_{VS} (K)$ or $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ . (Since this is complete, the theories of $U, V$ are the same.) Then for every $ϕ (\overline{x})$ of the language there is a quantifier-free $ψ (\overline{x})$ such that $T ⊢ \forall \overline{x} (ϕ (\overline{x}) ψ (\overline{x}))$ . Now let $\overline{a} \in U$ . Then $U ⊨ ϕ (\overline{a})$ iff $U ⊨ ψ (\overline{a})$ , and $V ⊨ ϕ (\overline{a})$ iff $V ⊨ ψ (\overline{a})$ since both satisfy $T$ . But also $U ⊨ ψ (\overline{a})$ iff $V ⊨ ψ (\overline{a})$ since $ψ (\overline{x})$ is quantifier-free. The theorem follows.

Definition.

A theory $T$ in a first-order language $L$ is said to be model complete if whenever $M, N ⊨ T$ and $M$ is an $L$ -substructure on $N$ then $M$ is an elementary substructure on $N$ .

The theories $T_{VS} (K)$ and $T_{VS} (K) \cup \{σ_{n}: n \in ℕ\}$ of infinite vector spaces over $K$ (where $K$ is infinite and finite, respectively) are model complete.