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

One Response to An Easy Fallacy

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

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: