Perplexing Power Set Problem

Probability Level 3

Given any (measurable, non fuzzy, etc...) set of any size (could be any size infinity or any finite size), is its cardinality smaller that that of its power set?

(And yes, if you do get this question correct, I do expect you to post the proof of your result.)

No Yes This is an open problem Cannot be proved nor disproved

1 solution

Mark Hennings
Apr 7, 2019

If $X$ and $2^X$ had the same cardinality, let $f\;:\; X \to 2^X$ be a bijection. Consider the set $S \; = \; \{y \in X \,|\, y \not\in f(y)\}$ and find $u \in X$ such that $S = f(u)$ .

If $u \in S$ then $u \in f(u)$ and hence $u \not\in S$ . On the other hand, if $u \not\in S$ then $u \not\in f(u)$ , and so $u \in S$ . This contradiction shows that $X$ and $2^X$ do not have the same cardinality.

Since the map $x \mapsto \{x\}$ is an injective map $X \to 2^X$ , we deduce that $X$ has strictly smaller cardinality than does $2^X$ .

I believe you want $f:X\to 2^X$ .

Jordan Cahn - 2 years, 2 months ago

So true. Well spotted.

Mark Hennings - 2 years, 2 months ago

Perplexing Power Set Problem

1 solution

0 pending reports