403/503 – Dimension

I refer to the textbook for the basic notion and properties of vector spaces. A field is a triple ${{\mathbb F}=(F,+,\times)}$ satisfying the axioms listed in pages 2, 3 of the textbook as properties of ${{\mathbb C},}$ see also https://andrescaicedo.wordpress.com/2009/02/11/305-4-fields/ and surrounding lectures, in this blog. I am writing this note mostly to record the exercise, the question, and the statement of Steinitz lemma, so I am not recording the proofs we discussed in lecture.

The following example, that I want to leave as a (voluntary) exercise, is due to John Conway.

Exercise 1 Define Nim-addition ${\oplus}$ and Nim-multiplication ${\otimes}$ on ${{\mathbb N}}$ as follows:

1. ${n\oplus m}$ is the result of adding without carrying the binary expansions of ${n}$ and ${m}$. For example, ${9\oplus1=1001_2\oplus1=1000_2=8.}$
2. ${n\otimes m}$ is computed by applying the following rules:
• ${\otimes}$ is commutative.
• ${\otimes}$ distributes over ${\oplus.}$
• Letting ${F_n=2^{2^n},}$ we have ${\displaystyle F_n\otimes F_n=\frac32F_n}$ and ${F_n\otimes m=F_n\times m}$ for ${m

Show that ${({\mathbb N},\oplus,\otimes)}$ is a field.

In lecture, the basic properties of vector spaces were presented. Recall the following notions:

Definition 1 Let ${V}$ be a vector space over a field ${{\mathbb F},}$ and let ${A\subseteq V.}$

1. The span of ${A,}$ ${{\rm span}(A),}$ is the collection of all finite linear combinations of elements of ${A.}$ The empty combination is understood as the vector ${0.}$ We say that ${A}$ spans ${W\subseteq V}$ iff ${{\rm span}(A)=W,}$ and that ${A}$ spans (or that ${A}$ is spanning) iff ${A}$ spans ${V.}$
2. The set ${A}$ is independent iff for all vectors ${a\in A,}$ we have that ${a\notin{\rm span}(A\setminus\{a\}).}$
3. The space ${V}$ is finite dimensional iff there is a finite spanning set ${A.}$ Otherwise, ${V}$ is infinite dimensional.
4. ${A}$ is a basis for ${V}$ iff it is independent and spans.

The following is very useful; in many algebraic context, it is taken as a basic property that any decent independence relation must satisfy:

Lemma 2 (Steinitz exchange lemma) For any subset ${A}$ of a vector space ${V,}$ and any vectors ${a,b\in V,}$ if

$\displaystyle a\notin{\rm span}(A\cup\{b\}),$

then

$\displaystyle b\notin{\rm span}(A\cup\{a\})\setminus{\rm span}(A).\ \Box$

Corollary 3 If a subset ${A}$ of a vector space ${V}$ is independent, and ${a\in V}$ is such that ${a\notin{\rm span}(A),}$ then ${A\cup\{a\}}$ is independent. ${\Box}$

Theorem 4 Any vector space admits a basis. ${\Box}$

Remark 1 The result is true for all vector spaces, whether they are finite dimensional or not, but the argument in the infinite dimensional case involves Zorn’s lemma. In lecture, we only proved the finite dimensional case. The argument shows that any spanning set contains a basis. The proof we gave in lecture does not seem to adapt to the infinite dimensional case. In particular, in principle we could need to deal with the following pathological situation:

Question 1 Can we have a vector space ${V}$ and a set of vectors ${A=\{a_n\mid n\in{\mathbb N}\}}$ such that the ${a_i}$ are pairwise distinct and yet

$\displaystyle a_n\in{\rm span}(\{a_m\mid m>n\})$

for all ${n\in{\mathbb N}}$?

(I encourage you to think about this question, although just as with the exercise, I am not requesting that you turn it in.)

Steinitz exchange lemma can be used to prove the following fundamental result, with the proof of which we will begin the next lecture.

Lemma 5 If ${V}$ is a finite dimensional vector space, and ${B_1,B_2}$ are bases for ${V,}$ then ${|B_1|=|B_2|<\infty.}$ ${\Box}$

Remark 2 If ${V}$ is infinite dimensional, and ${B_1,B_2}$ are bases for ${V,}$ then it is still the case that ${|B_1|=|B_2|}$ in the sense that there is a bijection between ${B_1}$ and ${B_2.}$

Definition 6 In light of Lemma 5 and the subsequent remark, we can define the dimension of a vector space ${V,}$ ${{\rm dim}(V),}$ as the size of any basis for ${B.}$

Typeset using LaTeX2WP. Here is a printable version of this post.

5 Responses to 403/503 – Dimension

1. Nick Davidson says:

In the exercise, when we define the Fermat numbers, can n be 0, or is it strictly greater than 0.

Thanks,
Nick

2. Hi Nick.
$n$ can be 0 there, so $2\otimes2=3$ for example.

3. I was also curious about one property about the nim-multiplication. Is $1\otimes 1$ defined by the above definition?

4. I guess we need to add that $\otimes$ is associative.

Then $1=3\oplus2$ and $1\otimes1$ $=1\otimes(3\oplus2)$ $=(1\otimes3)\oplus(1\otimes2)$ $=(1\otimes(2\otimes2))\oplus2$ $=((1\otimes2)\otimes2)\oplus2$ $=(2\otimes2)\oplus2$ $=3\oplus2=1.$ 🙂

5. I had erroneously claimed above that we obtain an algebraically closed field this way. This is incorrect. The definition is due to John Conway, who in fact defined $\oplus$, $\otimes$ for all ordinals. He showed that the ordinal $\omega^{\omega^\omega}$ is the algebraic closure of the field of two elements. (And ${\mathbb N}=\omega$ is a subfield of this, of course.)