prove: $\mathrm|{A}|=|\cup_{n\in\mathbb{N^{\mathrm{+}}}}\mathrm{A}^{n}|$ when $\mathrm{|A|\geq|A\times A|}$

104 Views Asked by At

Let $$\mathrm{|A|\geq|A\times A|}$$ as $A$ is a given set such that $|A| > 1$.

For every $n\geq1$, let $\mathrm{A^{n}}$ be the set of function from $\{0,1,....,n-1\}$ to $\mathrm{A}$.

prove: $$\mathrm|{A}|=|\cup_{n\in\mathbb{N^{\mathrm{+}}}}\mathrm{A}^{n}|$$

if we look on any object: $\mathrm{A^{i}}\in\mathrm{A^{n}}$ as $i\in\mathbb{N}$ and $\sum_{i=1}^{n-1}\mathrm{A^{i}}=\mathrm{A^{n}}$ , than any $\mathrm{A^{i}}:i\longrightarrow\mathrm{A}$ as I understand is defined to be onto, therefore $\mathrm{A^{n}}$ is onto $A$, so $$|\mathrm{A}|\leq|\cup_{n\in\mathbb{N^{\mathrm{+}}}}\mathrm{A}^{n}|$$ (this is just some ideas I had because I didn't really found any information about how to solve this type of Q).

after that, it is clear that I'll need to use the fact $\mathrm{|A|\geq|A\times A|}$ in some way so I could use CBS, but i really can't find the way to solve this.

1

There are 1 best solutions below

5
On

As noted in the comments, let us suppose that $A$ is neither a singleton nor empty, so that it has to be infinite (it is trivial for the empty set and false for a singleton).

The inequality $|A| \leq |\bigcup A^n|$ can be seen even easier by noting that there is a trivial bijection between $A$ and $A^1$. Next, note that $A^n$ can be identified with the $n$-fold cartesian product $\underbrace{A \times \dots \times A}_{n \text{ times}}$, in particular, $A^{n+1} = A^n \times A$. Using the hypothesis, you can show by induction that $|A| = |A^n|$ for every $n \geq 1$. Now we construct an injection $f \colon \bigcup A^n \rightarrow A$. Let me first explain what we want to do. Imagine $A$ as a square in the plane. Then we will embedd $A^1$ in one half of the square, embedd $A^2$ in one half of the half, i.e. a quarter, of the square, embedd $A^3$ in one eigth of the square and so on. There probably are quicker proofs but mine is explicit.

Consider the sets $A^n$ as subsets of $A^{n+1}$ simply by embedding them via $(a_1,\dots,a_n) \mapsto (a_1,\dots,a_n,x)$ for some fixed element $x \in A$. Since $|A| = |A^2|$, there is a bijection $f_2 \colon A_2 \rightarrow A$. Given an element in $a \in A^1$ define $f(a)$ to be $f_2(a)$. This way, $f$ maps $A_1$ onto the set $f_2(A^1)$. Convince yourself that $A \setminus f_2(A^1)$ still has the same cardinality as $A$ since we have $|A| = |A^2|$. Thus, $|A \setminus f_2(A^1)| = |A| = |A^3|$ and there is a bijection $f_3 \colon A^3 \rightarrow A \setminus f_2(A^1)$. Given $a \in A^2 \subset A^3$ define $f(a) = f_3(a)$. As before, $A \setminus (f_2(A^1) \cup f_3(A^2))$ still has the same cardinality as $A$ and we can proceed this procedure indefinitely.