403/503- Homework 2

February 11, 2011

This homework is due February 28.

1. From the textbook: Solve exercises 2.14, 3.3, 3.4, 3.9, 3.10, 3.16, 3.25.

2. a.Suppose  that T:{\mathbb R}^n\to {\mathbb R}^m satisfies linearity (i.e., what the book calls additivity). Suppose also that T is continuous. Show that T is linear (i.e., it also satisfies homogeneity).
b. Give an example of a T that is additive but not homogeneous.

3. The goal of this exercise is to state and prove the rank-nullity theorem (Theorem 3.4 from the book) without the assumption that V is finite dimensional. What we want to show is that if V,W are vector spaces and T:V\to W is linear, then

V/{\rm null}(T)\cong {\rm ran}(T).

First, we need to make sense of V/{\rm null}(T). Recall that if A is a set, an equivalence relation \sim on A is a relation \sim\subseteq A\times A such that:

  • a\sim a for any a\in A (reflexivity),
  • Whenever a\sim b, then also b\sim a (symmetry),
  • If a\sim b and b\sim c, then also a\sim c (transitivity).

Given such an equivalence relation, the equivalence class of an element a\in A is the subset {}[a]\subseteq A consisting of all those b\in A such that a\sim b. The quotient A/\sim is the collection of all equivalence classes, so if {\bf x}\in A/\sim then there is some a\in A such that {\bf x}=[a].

The point is that the equivalence classes form a partition of A into pairwise disjoint, non-empty sets: Each {}[a] is nonempty, since a\in[a]. Clearly, the union of all the classes is A (again, because any a is in the class {}[a]), and if {}[a]\cap[b]\ne\emptyset, then in fact {}[a]=[b] (check this).

Ok. Back to T:\to W. Define, in V, an equivalence relation \sim by: v_1\sim v_2 iff Tv_1=Tv_2 (Check that this is an equivalence relation). Then, as a set, we define V/{\rm null}(T) to be V/\sim. The reason why the null space is even mentioned here is because of the following (check this): v_1\sim v_2 iff v_1-v_2\in{\rm null}(T).

We want to define addition in V/{\rm null}(T) and scalar multiplication so that V/\sim is actually a vector space.

  • Given {\bf x} and {\bf y} in V/{\rm null}(T), set {\bf x}+{\bf y}={\bf z}, where if {\bf x}=[a] and {\bf y}=[b], then {\bf z}=[a+b]. The problem with this definition is that in general there may be infinitely many c such that {}[c]=[a] and infinitely many d such that {}[d]=[b]. In order for this definition to make sense, we need to prove that for any such c,d, we {}[a+b]=[c+d]. Show this.
  • Given {\bf x}\in V/{\rm null}(T), and a scalar \alpha, define \alpha{\bf x}={\bf y}, where if {\bf x}=[a], then {\bf y}=[\alpha a]. As before, we need to check that this is well-defined, i.e., that if {}[a]=[b], then also {}[\alpha a]=[\alpha b].
  • Check that V/{\rm null}(T) is indeed a vector space with the operations we just defined.

Now we want to define a linear transformation from V/{\rm null}(T) to {\rm ran}(T), and argue that it is an isomorphism. Define {\bf T}:V/{\rm null}(T)\to W by {\bf T}({\bf x})=Tv where {\bf x}=[v]. Once again, check that this is well-defined. Also, check that this is indeed linear, and a bijection.

Finally, to see that this is the “right” version of Theorem 3.4, we want to verify that {\rm dim}(V/{\rm null}(T))={\rm dim}(V)-{\rm dim}({\rm null}(T)) if V is finite dimensional. Prove this directly (i.e., without using the statement of Theorem 3.4).

2 Comments | 403/503: Linear Algebra II | Permalink
Posted by andrescaicedo

580- Specker trees

February 11, 2011

In his proof that the axiom of infinity holds in Quine’s New Foundations, Specker associated to each set {X} a tree, now called the Specker tree of {X}. (The name is due to Randall Holmes.)

In order to make sense of the definition without needing to appeal to the axiom of choice, let us define an equivalence relation {\sim} on subsets of {X} by saying that {A\sim B} iff {|A|=|B|}. The nodes of the tree are equivalence classes of subsets of {X} under {\sim}. Specifically, at the root we have the class of {X}, and the immediate successors of a class {[Y]} are the classes {[Z]} such that {|{\mathcal P}(Z)|=|Y|}.

Of course, under choice we can simply use cardinals {|Y|} as nodes, rather than the classes {[Y]}.

If {X} is a set, let {\aleph(X)}, the Hartogs function of {X}, be the set of all ordinals {\alpha} that inject into {X}, so {\aleph(X)} is the first ordinal that cannot inject. Sierpiński proved that {\aleph(X)\preceq{\mathcal P}^3(X)} and therefore {\aleph(X)<\aleph({\mathcal P}^3(X))}. This observation gives us immediately that the Specker tree of any set {X} is well-founded.

Under choice, it follows that all trees have finite rank. This is because any branch through the tree is finite (its nodes being a strictly decreasing sequence of cardinals). Moreover, the smallest cardinal in a branch is larger than the smallest cardinal in any larger branch. But an infinite-rank tree must have arbitrarily large branches, so there is no smallest cardinal in the tree, which is absurd.

Remarkably, it is still open whether in the absence of choice it is consistent that there is a Specker tree of infinite rank.

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

Leave a Comment » | 580: Topics in set theory | Permalink
Posted by andrescaicedo

507- Plünnecke inequalities and sumset estimates

February 10, 2011

George Petridis, a student of Gowers, has found very nice new arguments for the Plünnecke-Ruzsa sumset inequality (If A is a finite subset of an Abelian group G, and {}|A+A|\le C|A|, then {}|kA-lA|\le C^{k+l}|A| for any k,l\in{\mathbb N}) and for the Plünnecke graph inequalities.

In lecture we went through the nice standard argument. But the new proofs are significantly simpler. For example, the graph inequalities are no longer needed for the sumset ones, and Menger’s theorem is no longer needed fro the graph inequalities. Gowers has posted the nice proof in his blog, with links to Petridis’s papers on the ArXiv.

Leave a Comment » | 507: Advanced number theory | Permalink
Posted by andrescaicedo