# Show that the power set of a set A has too many elements to be able to be put in a one-to-one correspondence with A

Show that the power set of a set $$A$$, finite or infinite, has too many elements to be able to be put in a one-to-one correspondence with A. Explain why this intuitively means that there are an infinite number of infinite cardinal numbers. [Hint: Imagine a one-to-one function $$\phi$$ mapping $$A$$ into $$\mathscr{P}(A)$$ to be given. Show that $$\phi$$ cannot be onto $$\mathscr{P}(A)$$ by considering, for each $$x \in A$$, whether $$x \in \phi(x)$$ and using this idea to define a subset S of A that is not in the range of $$\phi$$.] Is the set of everything a logically acceptable concept? Why or why not? - pg 9 A First Course in AbstractAlgebra, Fraleigh

Suppose that $$\phi: A\to\mathscr{P}(A)$$ is one-to-one. Then in this function, for every $$x\in\phi$$, there is a corresponding $$y\in\mathscr{P}(A)$$ as an output.

However, the definition $$\mathscr{P}(A)$$ means that the set $$A\subset \mathscr{P}(A).$$ This implies that the co-domain of $$\mathscr{P}(A)$$ > domain of $$\phi$$ and that there is a subset $$S\subset \mathscr{P}(A)$$ such that $$S$$ is the complement of $$A$$ and is not in the range of $$\phi$$.

Therefore $$A$$ cannot be one-to-one with $$\mathscr{P}(A)$$ because there are $$x\in A$$ that would not map to its complement $$S$$.

I think my proof and reasoning is correct, but what I can't piece together is how to explain intuitively that there are an infinite number of infinite cardinal numbers. What about the empty set or another finite set? How does a finite set of an infinite number of infinite cardinal numbers??

Re the set of everything: I think this is a logically acceptable concept. We could call it the Power>9000 set lol

Thank you for your help in advance. This was not an assigned homework problem, I am attempting it out of curiosity and am not confident my professor would give me a satisfactory answer.

• you use dangerous and false reasononing, as you transform an inclusion into a strictly smaller which in general does not need to hold (even numbers in $\mathbb{N}$ are an immediate counter example) I would recommend you literally construct $S$ by defining it. you proof implicitly assumes A to be finite, which you definetely should avoid for the rest of your question. For the other part, build yourself the natural numbers and use those as a starting point for your cardinals – Enkidu Mar 19 '19 at 14:07
• This exercise comes down to two things, the diagonal argument for the first part and Russels Paradox for the second. – Floris Claassens Mar 19 '19 at 14:12
• @FlorisClaassens What is the diagonal argument you are referring to? – Evan Kim Mar 19 '19 at 14:29
• @Enkidu I see what you are saying regarding your first part. Could you elaborate more about the other part, building the natural numbers? Is the reasoning that in an infinite set (natural numbers), then there will be an infinite amount of cardinal numbers? – Evan Kim Mar 19 '19 at 14:29
• @Evan Kim, I was referring to Cantor's diagonal argument which he used to proof that the cardinality of $\mathbb{R}$ is larger than the cardinality of $\mathbb{N}$, You'll need to make some adjustment to fit your setting, but otherwise it should work: en.wikipedia.org/wiki/Cantor%27s_diagonal_argument. – Floris Claassens Mar 19 '19 at 15:02

The usual proof is as follows. Since $$\phi$$ is onto, by comprehension the set $$B:=\{x\in A|x\notin f(x)\}$$ is equal to $$\phi(y)$$ for some $$y\in A$$. Since any $$z\in A$$ satisfies $$z\in B\iff z\not\in f(z)$$, the case $$z=y$$ gives the contradiction $$y\in B\iff y\not\in B$$.
• Hey could you clarify some notation for this? $B:=\{x\in A|x\notin f(x)\}$ What is :, what is | – Evan Kim Mar 19 '19 at 14:25
• @EvanKim $:=$ is used instead of $=$ to mean "is defined as", so this is me naming something $B$ rather than making a claim about something previously named $B$. A common alternative to $:=$ is $\stackrel{\text{def}}{=}$, which has the disadvantage of requiring me to write \stackrel{\text{def}}{=}. $\{x\in A|p(x)\}$ is the set of $x$ in $A$ for which $p(x)$ is true. – J.G. Mar 19 '19 at 14:37