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<F_n.}

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.

Advertisement

This entry was posted on Monday, February 1st, 2010 at 4:36 pm and is filed under 403/503: Linear Algebra II. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

5 Responses to 403/503 – Dimension

  1. Nick Davidson says:
    February 2, 2010 at 11:09 am

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

    Thanks,
    Nick

    Reply
  2. andrescaicedo says:
    February 2, 2010 at 11:48 am

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

    Reply
  3. Andrew Misseldine says:
    February 3, 2010 at 7:39 am

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

    Reply
  4. andrescaicedo says:
    February 3, 2010 at 10:49 am

    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. 🙂

    Reply
  5. andrescaicedo says:
    January 27, 2011 at 4:21 pm

    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.)

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: