3 of 5
added 1689 characters in body
  • 1
  • 15
  • 118
  • 216

The cardinality of the set of all finite subsets of an infinite set

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?

Addendum by LePressentiment: I have some supplementaries and recast the answer below.

$1.$ How and why, is that first red bracket, the upper bound on $|S_n|$?
$2.$ Whence does that equality in the 2nd red bracket originate?
$3.$ How would you envisage/prefigure/presage to define $S$ wrt $S_n$?
$4.$ If the question hadn't divulged that $Card(S) = |X|$, then how can $Card(S)$ be determined?

Since ● $X$ is given as infinite which means $|X| \le |\mathbb{N}|$
and ● $S \quad \supseteq \quad \{\emptyset, \{1\}, \{2\},...,\{n\},...\} = \{\text{singletons}\} = |\mathbb{N}|$ thus $\color{#009900}{|X| \le |\mathbb{N}| \le |S|}$.

For all $n \in \mathbb{N}$, define $S_n$ as did Prof Magidin: $S_n:= \{\text{all subsets of cardinality }n\} \subseteq S.$
This definition involves a subset of cardinality $n$ (ie with $n$ elements) so we now scrutinise it.
It has the form $\{(x_1, ..., x_n)\}$. The $n$ elements in this $n$-tuple can be chosen $n!$ ways, so every such subset determines $n!$ $n$-tuples of elements of $X$. Plainly, an $n$-tuple included in a set will produce a subset (of that set) of cardinality $\le n$. This paragraph implies: $ |S_n| \color{#B8860B}{\le} {\Large{\color{red}{[}}} \, n!|X|^n \, {\Large{{\color{red}{]}}}} = |X|$. In toto,

$ \begin{align} |X| \color{#009900}{\le} |S| & = \left|\biguplus_{n=0}^{\infty} S_n\right| = \sum_{n=0}^{\infty}|S_n| = |\underbrace{S_0}_{= \emptyset}| + \sum_{n=1}^{\infty}|S_n| \\ & = \sum_{n=1}^{\infty}|S_n| \\ & \color{#B8860B}{\le} \sum_{n=1}^{\infty}|X| = |\mathbb{N}||X| \; {\Large{\color{red}{[}}} = {\Large{{\color{red}{]}}}} \; |X| \end{align} $

  • 1.5k
  • 1
  • 15
  • 22