1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor's diagonal method

  1. Jul 13, 2005 #1

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:

    [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.
     
    Last edited: Jul 13, 2005
  2. jcsd
  3. Jul 13, 2005 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    That's very pretty in a way :smile:

    Bit of an odd statement I know but I think so.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook