No question, or deep answers to be found here! I just wanted to share with you a pretty formulation of Cantor's diagonal argument that there is no bijection between a set X and its power set P(X). (the power set is the set of all subsets of X)(adsbygoogle = window.adsbygoogle || []).push({});

It's based on the idea of a characteristic function: a function whose values are only 0 and 1. If Y is a subset of X, then I can describe Y by this function:

[tex] \chi_Y(p) := \left\{

\begin{array}{ll}

0 \quad & p \notin Y \\

1 \quad & p \in Y

\end{array}

[/tex]

So that the statement "p is in Y" is equivalent to the equation "χ_{Y}(p) = 1".

With a little thought, you should be able to convince yourself that there is a one-to-one correspondence between subsets of X and characteristic functions on X.

So, the question "Is there a bijection between X and P(X), the set of all subsets of X?" is equivalent to the question "Is there a bijection between X and the set of all characteristic functions on X?"

Once you get to this point, the proof becomes much cleaner.

We now assume that such a bijection exists, and we call it f. So, if x is an element of X, then f(x) is a characteristic function on X.

If you haven't seen them before, function valued functions can be a little tricky to understand... for this proof, the only thing you need to know is that we can write f(x)(y), with both x and y in X, and f(x)(y) will either be a 0 or a 1.

The next step is to write a function that represents the "diagonal": we define the function g by:

g(x) := f(x)(x)

And the key step is that we can now construct the function h:

h(x) := 1 - g(x) = 1 - f(x)(x)

The values of h are either 0 or 1, so it is a characteristic function on X. Now, since f is an invertible function (it's a bijection!), we can make this computation:

[tex]

h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))

[/tex]

We can write f^{-1}(h) because f is invertible, and the range of f is the set of all characteristic functions on X, and h is one of those things.

The first step in the calculation is simply the definition of h. The second step uses the definition of invertibility, and will probably take a bit of thought to work through for those not comfortable with function valued functions. The key fact is this:

[tex]f(f^{-1}(h)) = h[/tex]

so if we apply both functions to an element of X, we have:

[tex]f(f^{-1}(h))(x) = h(x)[/tex]

Anyways, going back to the computation:

[tex]h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))[/tex]

This is a contradiction, because the far left and the far right can never be equal. (Remember that the values of h can only be a 0 or a 1, and this would require it to take 1/2 as a value)

So, our initial assumption that there exists a bijection, f, from X to the set of all characteristic functions must have been incorrect, because we derived a contradiction. So, by the initial remarks, we have thus proven:

There does not exist a bijection from any set X to P(X), the set of all subsets of X.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Cantor's diagonal method

**Physics Forums | Science Articles, Homework Help, Discussion**