About the Cardinality of Sets

Even though it “only” was an assignment in Computational Models, it has a rather nice solution. The Problem:

Show that for every set A it holds that |A| < |2^A|.

A proof: The basic idea is to generalize Cantor’s diagonal argument. Assume that there is a set A such that |2^A| \leq |A|. Then there is a surjective mapping \varphi : A \to 2^A. Define some mappings:

  • \psi_a : 2^A \to \mathbb{F}_2 with \psi_a(S) = 1 :\Leftrightarrow a \in S;\ 0 otherwise
  • \rho : A \times A \to \mathbb{F}_2, \ (a,b) \mapsto \rho(a,b) := \psi_a(\varphi(b))
  • \delta : A \to \mathbb{F}_2, \ a \mapsto \delta(a) := 1 + \psi_a(\varphi(a))

Then: \rho(a,a) \neq \delta(a) for all a \in A. This means: There is no element a \in A such that

\left\{ a \in A \mid \delta(a) = 1 \right\} = \underbrace{\{ b \in A \mid \rho(b,a) = 1 \}}_{=\varphi(a)},
hence \varphi cannot be surjective. \square

One amazing impact of that fact: There are problems that cannot be decided by a Turing Machine. How to see this? The set of all Turing Machines, denoted by \mathcal{S}, is enumerable, hence there is a surjection \phi : \mathbb{N} \to \mathcal{S}. But since the set of all languages \mathcal{L} is equal to 2^\mathbb{N}, there are languages which are undecidable by Turing Machines. Stunning, eh?

Related Articles

Leave a Reply