Technical Details in Proofs

Einstein is reported to have said that you should explain things as easy as possible, but not easier. In a talk, you may disobey this in favor of communicating the main ideas. But you should leave behind the impression that you know that there are some nasty details left for the reader.

An example is the following proof by Cantor that the reals have the same cardinality as the power set of the natural numbers. I heard it in a talk recently. The idea is to map any subset M of the natural numbers to a real number

\(0.i_1i_2i_3\ldots_2 = \sum\limits_{k=1}^\infty \dfrac{i_k}{2^k} \)

 in dual representation by the rule

\(i_k = \begin{cases} 1 & k \in M \\ 0 & k \notin M \end{cases}\)

The idea is that all numbers in [0,1] have a dual representation of this kind, and that we produce all subsets of the natural numbers with these representations and vice versa. It is an easy (?) geometrical task to show that [0,1] has the cardinality of the real numbers.

The problem of this idea is the small technical detail that the mapping constructed above is not really a bijection. It is merely surjective.  The problem is that e.g. the following representations produce identical reals.

\(0.0100110011111\ldots_2 = 0.01001101_2\)

So how can we fix the bijection? The reason we can do it is that the number of exceptions is countable. In general, any infinite set retains its cardinality, if we remove a countable set from it, but leave at least another countable set. This is a general result, and it is not too difficult to prove.

In our case, we are facing the problem that two subsets may map to the same real number, one of it finite and the other containing all elements k from some K on. The number of pairs of these subsets is countable however. So we can omit one subset of each pair. E.g., we can delete all finite sets from the power set first.

Set theory was never easy for me. There are various theorems, where I would not know if complicate proofs involving the axiom of choice are necessary or not. An example is the theorem that if you have a surjection from A to B and one from B to A, then there is a bijection between A and B. Tough!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.