Which one of the sets $\mathcal {P}(X \times X) \times \mathcal {P}(X \times X)$ and $\mathcal {P}(\mathcal {P}(X))$ has more elements?

Question

This is Exercise 3.3.22 from Ethan Bloch's book Proofs and Fundamentals which I'm currently self studying.

Let $X$ be a set. Suppose $X$ is finite. Which of the two sets $\mathcal {P}(X \times X) \times \mathcal {P}(X \times X)$ and $\mathcal {P}(\mathcal {P}(X))$ has more elements?

If $|X|=n$ then

$|(X \times X)|=n^2$, and

$|\mathcal {P}(X \times X)|=2^{n^2}$, and

$|\mathcal {P}(X \times X) \times \mathcal {P}(X \times X)|= 4^{n^2}$.

If $|X|=n$ then

$|\mathcal {P}(X)|=2^n$, and

$|\mathcal {P}(\mathcal {P}(X))|=2^{2^n}$.

So the question becomes

which of the two numbers $4^{n^2}$ and $2^{2^n}$ is larger, for a finite $n$, $n \ge 0$.

By plugging in numbers from $0$ onwards, the numbers are

$4^{0^2}=1$

$4^{1^2}=4$

$4^{2^2}=256$

$4^{3^2}=262144$

...

and

$2^{2^0}=2$

$2^{2^1}=4$

$2^{2^2}=16$

$2^{2^3}=256$

...

So if $n \ge 1$ then $4^{n^2} \ge 2^{2^n}$, but for $n=0$ (i.e. for the case when $X$ is the empty set) $4^{n^2} \lt 2^{2^n}$.

So my answer to this exercise would be that $\mathcal {P}(X \times X) \times \mathcal {P}(X \times X)$ $\ge$ $\mathcal {P}(\mathcal {P}(X))$, for $|X|$ $\ge$ $1$ and $\mathcal {P}(X \times X) \times \mathcal {P}(X \times X)$ $\lt$ $\mathcal {P}(\mathcal {P}(X))$ when $X=\varnothing$. Is this correct? I was expecting that one of the two sets would always have more elements (or the same amount) than the other, so I'm kind of sceptical of my answer. If I am correct, how would I rigorously prove/show that $4^{n^2} \ge 2^{2^n}$, $n \ge 1$?

Answer 1

Your conjecture is false. There are actually only finitely many $n$ with $4^{n^2}\geq 2^{2^n}$: $n=1,2,3,4,5,6$.

This is why mathematicians learn to prove things, because conjectures about "all numbers" tend to be hard to be sure about just by looking at the first few of them.

This problem is much easier to see if you don't replace $2^2$ with $4$. Then you are trying to compare $2^{2n^2}$ with $2^{2^n}$, and thus really trying to compare $2n^2$ with $2^{n}$. This lets you explore more small values than just $n=0,1,2,3$. For example, when $n=7$, $2n^2=98, 2^{n}=128$.