- #1
- 14,922
- 28
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)
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:
\chi_Y(p) := \left\{<br /> \begin{array}{ll}<br /> 0 \quad & p \notin Y \\<br /> 1 \quad & p \in Y<br /> \end{array}<br />
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:
<br /> h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))<br />
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:
f(f^{-1}(h)) = h
so if we apply both functions to an element of X, we have:
f(f^{-1}(h))(x) = h(x)
Anyways, going back to the computation:
h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))
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.
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:
\chi_Y(p) := \left\{<br /> \begin{array}{ll}<br /> 0 \quad & p \notin Y \\<br /> 1 \quad & p \in Y<br /> \end{array}<br />
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:
<br /> h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))<br />
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:
f(f^{-1}(h)) = h
so if we apply both functions to an element of X, we have:
f(f^{-1}(h))(x) = h(x)
Anyways, going back to the computation:
h(f^{-1}(h)) = 1 - f(f^{-1}(h))(f^{-1}(h)) = 1 - h(f^{-1}(h))
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.
Last edited:
