An Easy Fallacy

For a change of pace today, I’ll present an incorrect proof of a simple proposition. The diligent reader can work out the location of the mistake before reading on, where I will present a modified proposition, and correct proof, before discussing the mistake in detail.

Proposition: If $k$ is a field and $c$ is a cardinal less than $|k|$ , then a vector space over $k$ cannot be written as a union of $c$ of its proper subspaces.

Questionable Proof: Suppose that $\{V_\alpha\}$ is a collection of $c$ proper subspaces of $V$ , which cover $V$ . We can assume that no proper subcollection covers $V$ . (we can remove the superfluous elements from our collection if this is not the case) This implies that for each $\alpha$ , there exists some $v_\alpha \in V_\alpha$ such that $v_\alpha \not\in V_\beta$ for $\beta\neq\alpha$ .

Take any $\alpha\neq\beta$ , and consider the set $\{v_\alpha + \lambda v_\beta\ |\ \lambda \in k\}$ . This set has cardinality $k$ , and each element lies in some $V_\gamma$ , so by the pigeonhole principle, two of these elements must lie in the same $V_\gamma$ , say $v_\alpha + \lambda_1 v_\beta \in V_\gamma$ and $v_\alpha + \lambda_2 v_\beta \in V_\gamma$ .

Subtracting, we see that $(\lambda_1 - \lambda_2)v_\beta \in V_\gamma$ , so $v_\beta \in V_\gamma$ . Therefore $\beta = \gamma$ . Similarly, we see that $v_\alpha\in V_\gamma$ , so $\alpha=\gamma=\beta$ , contradiction.

The above proposition is, unfortunately, false. To see this, take $V$ to be a real vector space with countably infinite basis $e_1,e_2,\ldots$ , and for each $i$ , let $V_i$ be the vector space generated by $e_j$ , $j\neq i$ . Then $\{V_i\}$ covers $V$ , even though it is a set of cardinality $\aleph_0 < |\mathbb{R}|$ .

We need to add a condition to the proposition, but this time the proof is correct.

Modified Proposition: If $k$ is a field and $c$ is a cardinal less than $|k|$ , then a finite dimensional vector space over $k$ cannot be written as a union of $c$ of its proper subspaces.

Proof: We proceed by induction on the dimension. If $V$ has dimension $1$ , then any union of proper subspaces must be the zero space, so the statement is trivial. Now assume that $V$ has dimension $d \geq 2$ and the proposition has been proved for all vector spaces of dimension $d-1$ .

First, observe that there are at least $|k|$ subspaces of $V$ of dimension $d-1$ . For if $e_1,\ldots e_n$ are a basis for $V$ , then we can take the subspaces generated by $\lambda e_1 + e_2, e_3,\ldots e_n$ for $\lambda\in K$ .

Suppose that we are given a collection $\{V_\alpha\}$ of proper subspaces of $V$ of cardinality $c$ that covers $V$ . Since there are at least $|k|> c$ spaces of dimension $d-1$ , there must be such a space $W$ that is not equal to any $V_\alpha$ . Hence $\{V_\alpha \cap W\}$ is a collection of proper subspaces of $W$ of cardinality $c$ that covers $W$ , contradiction.

So what was the mistake in the original proof? You might question my use of the pigeonhole principle on infinite sets, but that can actually be made quite rigorous. No, the problem is the statement “We can assume that no proper subcollection covers $V$ “. Though an attractive idea, it is not true that we can reduce our collection to no longer be redundant.

Consider our earlier counterexample, a real vector space with a countably infinite basis. The given collection covers $V$ , but there is no non-redundant subcollection that does so. A slightly painful reminder that we must always modify our intuition when dealing with infinite sets.

We can salvage the original proof, however, when the collection is finite. Then, in fact, we can throw out elements of our collection, one at a time, until we have eliminated any redundancy. That gives us the following: (note that this is not strictly weaker than our modified proposition, since it applies to infinite-dimensional spaces as well)

Salvaged Proposition: If $k$ is an infinite field, a vector space over $k$ cannot be written as a union of finitely many proper subspaces.

About these ads

This entry was posted on Sunday, October 12th, 2008 at 11:16 am and is filed under Uncategorized. 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.

One Response to An Easy Fallacy

A Silly Prime Avoidance Lemma « Concrete Nonsense says:

November 15, 2008 at 10:45 pm

[...] Silly Prime Avoidance Lemma The other day I read this post over at Notational Notions. The main result is the [...]

Reply

Notational Notions

An Easy Fallacy

Like this:

One Response to An Easy Fallacy

Leave a Reply Cancel reply

Archives

Blogroll

Essential Reading

Follow “Notational Notions”