Cantor's diagonal method

  • Thread starter Hurkyl
  • Start date
  • Tags
    Method
In summary, Cantor's diagonal argument shows that there is no bijection between a set X and its power set P(X). This is based on the idea of characteristic functions and the assumption of a bijection between X and the set of all characteristic functions on X. A contradiction arises when constructing a function that represents the "diagonal", leading to the conclusion that there cannot exist a bijection between X and P(X). This is a beautiful proof that highlights the concept of function valued functions.
  • #1
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,981
26
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:
Mathematics news on Phys.org
  • #2
That's very pretty in a way :smile:

Bit of an odd statement I know but I think so.
 
  • #3



Thank you for sharing this formulation of Cantor's diagonal method! It's always interesting to see different ways of presenting mathematical concepts. Your explanation is clear and easy to follow, and I appreciate the effort you put into breaking down the steps of the proof. It's amazing to think about how such a simple concept can have such far-reaching implications in mathematics. Cantor's diagonal method is definitely one of the most elegant and powerful arguments in set theory.
 

What is Cantor's diagonal method?

Cantor's diagonal method is a mathematical proof used to show that there are different sizes of infinity. It was developed by the mathematician Georg Cantor in the late 19th century.

How does Cantor's diagonal method work?

The diagonal method works by creating a list of elements, such as numbers or infinite sequences, and then constructing a new element that is not included in the list. This shows that the original list was incomplete and therefore, there must be more elements than originally thought.

Why is Cantor's diagonal method important?

Cantor's diagonal method is important because it revolutionized the understanding of infinity in mathematics. It also has many applications in other areas of mathematics, such as set theory and logic.

What are some common misconceptions about Cantor's diagonal method?

One common misconception is that the diagonal method is a proof that there are different sizes of infinity. However, it only proves that some sets are larger than others, but it does not determine the exact size of the sets.

Another misconception is that the diagonal method can be used to compare infinite sets of different types, such as real numbers and natural numbers. However, this is not possible as the diagonal method only works for sets that can be put into a list.

Can Cantor's diagonal method be applied to real-world situations?

Yes, Cantor's diagonal method can be applied to real-world situations. For example, it can be used in computer science to show that some infinite sets of data are larger than others, which has implications for data storage and algorithms. It can also be applied to language and linguistics to show that there are infinitely many possible sentences in a language.

Similar threads

  • General Math
Replies
2
Views
687
Replies
4
Views
285
  • General Math
Replies
3
Views
760
  • General Math
Replies
2
Views
852
Replies
3
Views
576
Replies
7
Views
1K
Replies
17
Views
2K
Replies
12
Views
939
Replies
1
Views
796
Replies
5
Views
1K
Back
Top