TransWikia.com

Cardinality of finite sequences of infinite set

Mathematics Asked by avir_12 on November 27, 2020

I want to prove that if $A$ is a infinite set, then $|Fin(A)|=|FS(A)|=|A|$, where $Fin(A)$ is the set of all finite subsets of $A$ and $|FS(A)|$ is the set of all finite sequences. Firstly, to prove $|Fin(A)|=|A|$,
$$|Fin(A)|=|bigcup_{n < omega}[A]^{n}|=|bigcup_{n < omega}A|=sum_{n <omega}|A|=|A|aleph_0=|A|$$
where in the second equality i use that $|[A]^{n}|=|A^{n}|=|A|$ (i’m also using that $|A times A|=|A|$, thanks axiom of choice).
For the second, I would to use a similar argument and write $FS(A)=bigcup_{n < omega}A^{n}$, but i’m not truly sure about that equality.

One Answer

It appears to me that you are asking about the case of finite sequences as you worked out the finite subsets yourself. There are also other questions that think about finite sets: The cardinality of the set of all finite subsets of an infinite set. Here is my proof of your theorem.

If $Card(A) = kappa$ is an infinite cardinal then $Card(A times A) = Card(A^{< omega}) = kappa$.

Proof

$Card(A times A) = Card(A) cdot Card(A) = kappa cdot kappa = max(kappa,kappa) = kappa$.

Clearly, by finite induction, it follows that $Card(A^n) = kappa$ for all $n < omega$.

Now, observe that $A^{< omega} = bigcup_{n < omega} A^n$ is bijective with $mathbb{N} times A$ or equivalently with $mathbb{N} times kappa$. So: $Card(A^{< omega}) = Card(mathbb{N} times kappa) = mathbb{N} cdot A = max(mathbb{N}, kappa) = kappa$.

The bijection seems easy, choose $x in bigcup_{n < omega} A^n$ then $x in A^i$ for a unique $i$ (indeed, this union must be disjoint since each component has a different length). Then assign $x$ to $(i,x)$. The inverse would assign $(i,x)$ to the element $x$ of $A^i$.

Answered by Rodrigo on November 27, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP