Second power of an infinite set is Dedekind-infinite

Question

It's mentioned here https://math.stackexchange.com/a/815199 that if $X$ is infinite, then $\mathcal P(\mathcal P(X))$ is Dedekind infinite.

I tried proving this without using the Axiom of Choice nor the Axiom of infinity, but failed and couldn't find a proof online.

'Infinite set' could mean a Tarski-infinite set or a set not equinumerous to any natural number.

A set S is Tarski-finite iff every non-empty family of subsets of S has a $\subseteq$-maximal element. n is a natural number iff n is the empty set or n is a successor ordinal whose non-empty members are successor ordinals.

Answer 1

The key point is that if $X$ is infinite, then for any natural number $n$, $X$ has a subset of size $n$. This is an easy proof by induction, and it's choice free. One might be tempted to think it implies that there is an injection from $\omega$ into $X$, but for that we actually do need some choice, and the induction is only giving us information about "each natural number".

But now, simply map $n$ to the set of all $n$-sized subsets of $X$.

Answer 2

$X$ is an infinite set iff $X$ is not equinumerous to any natural number, where $n$ is a natural number iff $n$ is the empty set or $n$ is a successor ordinal whose non-empty members are successor ordinals.

We can use Transfinite Induction to show that Induction on the natural numbers is valid without needing the Axiom of Infinity.

Assume $\phi (0)$ and $\phi (n) \to \phi (n+1)$ for every natural number $n$.

Let $\psi (n)$ be ($\phi (n)$ or $n$ is not a natural number).

Assume that $\psi (\alpha)$ holds for every $\alpha \in \gamma$, where $\gamma$ is an ordinal number.

Case I: $\gamma = 0$. $\phi(\gamma)$ and $\psi (\gamma) $ both hold

Case II: $\gamma = \beta + 1$. If $\gamma$ is a natural number, then $\beta$ is a natural number and $\psi(\beta)$ and $\phi(\beta)$ hold, and so $\phi(\gamma)$ and $\psi(\gamma)$ both hold.

If $\gamma$ is not a natural number, then $\psi(\gamma)$

Case III: $\gamma$ is a limit ordinal. $\gamma$ is not a natural number and so $\psi(\gamma)$

Therefore, $\psi(\gamma)$ holds for every ordinal number $\gamma$ and $\phi(\gamma)$ holds for every natural number $\gamma$.

Define the Hartog's number of $X$, $H(X)$, to be { $\alpha$ |$\alpha$ is an ordinal number and there is an injection from $\alpha$ to $X$}

Define $\omega$ to be {$n \in H(X)$| $n$ is a natural number}

Let $\phi (n)$ be $n \in \omega$.

$0$ is a natural number and $0 \in H(X)$. Therefore, $0 \in \omega$ and $\phi (0)$

Assume that $\phi (n)$ holds. $n$ is a natural number and $n \in H(X)$.

There exists an injective function $f$ from $n$ to $X$. $X$ is not equinumerous to $n$ because $X$ is infinite. Therefore, $f$ is not surjective. Let $c \in X \setminus Ran(f)$

Let $g:n+1 \to X$ such that $g(m)=f(m)$ for every $m \in n$ and $g(n)=c$. $g$ is injective and $n+1 \in H(X)$. $n+1$ is a natural number and $n+1 \in H(X)$, and so $n+1 \in \omega$. $\phi (n+1)$ holds

By induction, $\phi (n)$ holds for every natural number $n$ and $\omega$ contains every natural number. Therefore, $\omega$ is the set of all natural numbers.