MHB A Very Standard Theorem in Set Theory

AI Thread Summary
The discussion centers on proving that there is no bijection between any set \( A \) and its power set \( \mathcal{P}(A) \), referencing Russell's paradox. The proof begins by assuming a bijection \( \varphi: A \to \mathcal{P}(A) \) and defining a function \( g \) based on the mapping of elements in \( A \). A contradiction arises when trying to identify an element \( y \) such that \( \varphi_y = g \), leading to an inconsistency with the definition of \( g \). This contradiction confirms that such a bijection cannot exist. The proof effectively demonstrates the relationship between a set and its power set, reinforcing foundational concepts in set theory.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
Let $A$ be any set. Show that there is no bijection between $A$ and the power set $\mathcal P(A)$ of $A$.

(The power set of a set is the set of all its subsets including the empty-set.)
 
Mathematics news on Phys.org
caffeinemachine said:
Let $A$ be any set. Show that there is no bijection between $A$ and the power set $\mathcal P(A)$ of $A$.

(The power set of a set is the set of all its subsets including the empty-set.)
The proof is a version of Russell's paradox.
Suppose (in order to get a contradiction) that $f:A\to \mathcal P(A)$ is a bijection. Let $X = \{ x\in A: x\notin f(x) \}$. Since $f$ is surjective, $X = f(x_0)$ for some $x_0\in A$. Now ask whether or not $x_0 \in X$.
 
Opalg said:
The proof is a version of Russell's paradox.
Suppose (in order to get a contradiction) that $f:A\to \mathcal P(A)$ is a bijection. Let $X = \{ x\in A: x\notin f(x) \}$. Since $f$ is surjective, $X = f(x_0)$ for some $x_0\in A$. Now ask whether or not $x_0 \in X$.
Here's my version of the same:

We interpret $\mathcal P(A)$ as the set of all the functions from $A$ to $\{0,1\}$. Assume for the sake of a contradiction that there is a bijection $\varphi:A\to \mathcal P(A)$. We write $\varphi_x$ instead of $\varphi(x)$ for $x\in A$. Define $g:A\to \{0,1\}$ as $g(x)=1$ if $\varphi_x(x)=0$ and $g(x)=0$ if $\varphi_x(x)=1$. Let $\varphi_y=g$. Then $\varphi_y(y)=g(y)$ (There exists such a $y$ by assumption). The last equality is impossible by definition of $g$ and thus we achieve a contradiction and the proof is complete.$\blacksquare$
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.

Similar threads

Replies
15
Views
2K
Replies
3
Views
2K
Replies
2
Views
2K
Replies
5
Views
2K
Replies
72
Views
7K
Back
Top