Prove cardinality of a finite set is different than that of its power set I was hoping someone could check my work and confirm whether it's a valid proof by induction.
For this problem we're allowed to use that $\left|P(A)\right|$ = $2^\left|A\right|$ for part of our proof
We want to prove $\left|P(A)\right|$ > $\left|A\right|$ for any finite set
That is that: $2^\left|A\right|$ > $\left|A\right|$
Base case $\left|A\right|$ = 1
$2^1$ > $1$, therefore this relation holds for $\left|A\right|$ = 1
Let us assume that the relation is true for the value $n = k$
That is that $2^k$ > $k$
For $2^{k+1} > k + 1$ we can rearrange this algebraically to get
2 > $({k + 1})^{1 / (k + 1)}$
lim k → ∞ $({k + 1})^{1 / (k + 1)} = 1$
As such, it is true that $2^{k+1} > k + 1$
Therefore $\left|P(A)\right|$ > $\left|A\right|$ and as such $\left|P(A)\right|$ != $\left|A\right|$
 A: No, your proof's not valid. Yes, it's true that $\lim_{k\to\infty}(k+1)^{1/(k+1)}=1$, but this doesn't imply $(k+1)^{1/(k+1)}<2$ for all $k$. It's much easier to note $2^k>k\implies2^{k+1}=2\cdot2^k>2k\ge k+1$ provided $k\ge1$, giving an inductive step that works for $k\ge1$. We then just need $k=0,\,k=1$ to both be include in the base case.
A: If you can use that $|\mathcal{P}(A)|=2^{|A|}$ things can become easier than in the proof you show. We must show that $2^{|A|}>|A|$, or what is equivalent, that for any $k\in\mathbb{N}\setminus\{0\}$, $2^{k}>k$ (where $|A|=k$; I do not know why you haven't considered the case $|A|=0$, but this one is quite simple, so I will ignore it).

*

*Base case: $k=1$
In this case, $2^{k}=2^{1}=2$, which is greater than $k=1$.

*

*Induction hypothesis: assume the result holds for some $j\in\mathbb{N}$ such that $j\geq 1$
Then, $2^{j+1}=2.2^{j}$, and since $2^{j}>j$ (by induction hypothesis), we obtain
$$2^{j+1}=2.2^{j}>2.j\geq j+1$$
(where $2.j\geq j+1$ since $j\geq 1$), meaning $2^{j+1}>j+1$. This ends the proof by induction that $|\mathcal{P}(A)|>|A|$ whenever $A$ is a finite, non-empty set.
Notice, however, that this is not the standard proof of such a result: one shows that $|\mathcal{P}(A)|\geq |A|$ by considering the injective function $f:A\rightarrow\mathcal{P}(A)$ taking an element $a\in A$ to the singleton $\{a\}$; one then shows that we cannot have $|A|\geq|\mathcal{P}(A)|$ (and therefore $|\mathcal{P}(A)|>|A|$) by a diagonal argument à la Cantor.
