Answer to Question #136825 in Discrete Mathematics for Promise Omiponle

Question

Let A be a set, and let P(A) denote the power set of A. Prove that|A|<|P(A)|.
Hint: Proceed in two steps.
1. First show that|A| <= |P(A)|. Try defining the function g: A-> P(A) by g(a) ={a}, and verify that g is one-to-one.
2. Then show that we can't have |A|=|P(A)|. Assume not, i.e., suppose that in fact |A|=|P(A)|. Then there exists a bijection f: A->P(A). Let B={aϵA|a Ɇf(a)} ϵ P(A)

Since f is onto, there exists an a0ϵA such that f(a0) =B. How does this lead to a contradiction?

Answer 1

First show that $|A| \leq |P(A)|$. Define the function $g: A\to P(A), g(a)=\{a\}$. Since inequality $a\ne b$ implies inequality $\{a\}\ne \{b\}$, that is $g(a)\neq g(b)$, $g$ is one-to-one. Therefore, $|A| \leq |P(A)|$.

Show that we can't have $|A|=|P(A)|.$ Assume not, i.e., suppose that in fact $|A|=|P(A)|.$ Then there exists a bijection $f: |A|\to |P(A)|.$ Let $B=\{a\in A|a\notin f(a)\}\in P(A)$.

Since f is onto, there exists an $a_0\in A$ such that $f(a_0) =B$. Then we have the following.

If $a_0\in B$, then by definition of $B$, $a_0\notin f(a_0)$, i.e. $a_0\notin B$. If $a_0\notin B$, then $a_0\in f(a_0)$, i.e. $a_0\in B$.

This contradiction prove that $|A|<|P(A)|.$