[Set Theory] Proving Cantor's Theorem by Contradicting Surjectivity on Power Sets

Let SS be a set, and let P(S)P(S ) be the power set of SS, which is the set of subsets of SS .

Suppose that f:SP(S)f: S \rightarrow P(S ) surjects. We define T={xS:x∉f(x)}.T = \{ x\in S: x \not\in f(x) \}. so that f(x)f(x) is an element of P(S) P(S), hence a subset of SS , and xx is an element of SS.

By assumption ff surjects, so there exists tSt \in S such that f(t)=T f (t) = T .

First, let tT t \in T. Then t{xS:x∉f(x)}, t \in \{ x \in S: x \not\in f(x) \},

so tS t \in S such that t∉f(t) t \not\in f(t) . But since tT=f(t) t \in T= f(t) , this is a contradiction because tT=f(t) t \in T = f(t) , but t∉f(t) t \not\in f(t) .

Now let t∉T t \not\in T . Then since tt is not in TT, tt cannot be an element of SS such that t∉f(x) t \not\in f(x) . So if tS t \in S , then tt must also be a member of f(t) f(t) . But supposing that ff surjects, there is a tS t \in S such that f(t)=T f(t) = T , which means that t∉T=f(t) t \not\in T = f(t) , but tf(t) t \in f(t) . This is a contradiction.

\therefore We conclude from both cases that ff cannot surject, because there exists no tS t \in S such that f(t)=T f(t) = T . In other words, Tf(t) T \not= f(t) for all tS t \in S .

In this note, we have shown that no map from set S S to its power set P(S) P(S ) can surject, which proves that there exists no bijection from S to its power set. This fundamental result means that for any set S, the set of all subsets of SS, P(S)P(S) ,has a strictly greater cardinality than SS. That

S<P(S) |S| < |P(S)| or Card(S)<Card(P(S)).Card(S) < Card(P(S)).

Note by Tasha Kim
1 year, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

You may also want to show that f f is injective. Otherwise, it is not obvious that SP(S) |S| \leq |P(S)| . (The surjective argument only shows that the cardinalities are not equal.)

Dan Wilhelm - 1 year, 5 months ago

Log in to reply

Thanks for pointing that out! Following your comment, constructing g:SP(S)g: S \rightarrow P(S) so that every element of SS is mapped to a singleton set, i.e. x{x}x \rightarrow \{x\} will do.

Tasha Kim - 1 year, 5 months ago

Log in to reply

You need to work in something like ZF\text{ZF} to guarantee the diagonal construction, and as mentioned below show that there be an injection SP(S)S\longrightarrow\mathcal{P}(S). Your proof is otherwise standard and fine. I would write it more compactly as follows:

Claim. There is no surjection f:SP(S)f:S\longrightarrow\mathcal{P}(S). Proof. Let f:SP(S)f:S\longrightarrow P(S). To show: ff is not surjective. By the replacement axiom there exists a set Δ:={xSxf(x)}P(S)\Delta:=\{x\in S\mid x\notin f(x)\}\in\mathcal{P}(S). It suffices to show that Δran(f)\Delta\notin\text{ran}(f). Suppose this not be the case, then there exists δS\delta\in S such that f(δ)=Δf(\delta)=\Delta. It holds that δf(δ)\delta\in f(\delta) f(δ)=Δ\overset{f(\delta)=\Delta}{\Longleftrightarrow} δΔ\delta\in\Delta defn. $\Delta$\overset{\text{defn. \$\Delta\$}}{\Longleftrightarrow} δf(δ)\delta\notin f(\delta). This is a contradiction. Hence Δran(f)\Delta\notin\text{ran}(f). \blacksquare

Note that without suitable axioms, one cannot carry through with Cantor’s diagonal argument. In under Quine’s NF\text{NF} set theory this proof breaks down right at this point, and not only this, there exists sets such that P(X)=X|\mathcal{P}(X)|=|X|.

R Mathe - 1 year, 4 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...