$A$ infinite implies $|A|=|A|^n$ for any $n\in \mathbb{N}$

108 Views Asked by At

Let $A$ be an infinite set. Then $|A|=|A|^n$ for any $n\in \mathbb{N}$.

What I would like to do is adapt a proof of the Comparison Lemma. I've tried to do it in the following way:

Let $n=2$ (and then proceed by induction, once it has been proved that $|A| = |A|^2$). First of all, it is trivial that $|A|\le |A\times A|$. Now I need to show that $|A\times A| \le |A|$.

Let $\Delta = \{(B,f): B\in \mathcal{P}(A)\setminus \{\emptyset\}, f:B \to A\times A \mbox{ is injective } \}$. Then $\Delta\ne \emptyset$, since for $b\in B, f: b\to (b,b)$ exists.

Let $(B,f)\preceq(C,g)\iff B\subseteq C \subseteq A, g_{\vert B}=f$, where $f:B\to A^2, g:C\to A^2$. Let $\Gamma = \{B_i, f_i\}_{i\in I}$ be a chain in $(\Delta, \preceq)$. Then $(\Delta, \preceq)$ is a partial order.

Let $B=\bigcup\limits_{i\in I}B_i$, $f:B\to A^2$ be given by $f(x) = f_i(x)$ if $x\in B_i$. Then $(B,f)\in \Delta$ and is an upper bound for $\Gamma$. Hence, by Zorn's lemma, there exists a maximal element in $\Delta$, say $(M, g)$.

  • Case 1: $M=A$. Then $A=M\preceq A^2$ (but we already know this).

  • Case 2: $M\subsetneq A$. Then $g$ must be surjective (can be proved by contradiction with $(M,g)$ being a maximal element), and so $g$ is bijective, so that $A^2\preceq_{g^{-1}} A$.

However, this is impossible, since $M\subsetneq A\implies M\times M \subsetneq A\times A$. But $M = A\times A$, so $M\times M$ cannot be properly contained in $A\times A$. Hence, $A\times A\not\preceq A$.

Can someone please tell me what is my error here?

1

There are 1 best solutions below

2
On

Your mistake is the conclusion in Case 1. In this case, instead of proving that you obtain the conclusion, you just proved that something trivial holds.

So, if Case 1 happens, you didn't prove what you want.