0

Let X be the set of all finite subset of $\Bbb N$. Then

let the set $S = \{\xi \mid \xi \approx X, \xi \leqslant 2^X\}$ then

Card(X) is the least element of S.

First, I can't start with how to exhaust all the element of S.

Any advice?

Daschin
  • 675
  • 1
    Is the question just to find the cardinality of the set of all finite subsets of $\mathbb N$? Not sure what we need all the initial ordinal mumbo jumbo (I assume that's why you wrote down about $S$?) Here's a hint: it's countable. If you can find a bijection from the naturals then you know $\omega$ is the smallest ordinal $\approx$ to it, so $Card(X) = \omega$ by the initial ordinal definition. – spaceisdarkgreen Jun 07 '17 at 03:22
  • @spaceisdarkgreen had shown that X is countable, thus card(X) $\le \aleph_0$ now, I want to show that card(X) $\ge \aleph_0$. Any suggetions? – Daschin Jun 07 '17 at 03:33
  • That's the easy direction. $X$ isn't finite, is it? Find an injective function $\aleph_0 \to X.$ – spaceisdarkgreen Jun 07 '17 at 03:38
  • @spaceisdarkgreen oh.. that's hard.. how could one deal with the infinite case of $\Bbb N$.. and maps it to the set of finite subset of $\Bbb N$ – Daschin Jun 07 '17 at 03:41
  • Associate to each integer a unique finite subset of the integers. There's a painfully obvious way to do this. It's one of those things that might be hard to come up with but once you find it you'll kick yourself for not thinking of it sooner. – spaceisdarkgreen Jun 07 '17 at 03:47
  • Also I'm curious how you did $|X| \ge \aleph_0 $ without finding a bijection. If you found a bijection $X\leftrightarrow \mathbb N$ (which proves $|X|=\aleph_0$) and not (say) an injective function $X\to \mathbb N$ (which would only show $|X| \ge \aleph_0$), you're done. But in any event, as I said before, it's really easy to find an injective function $\mathbb N \to X.$ – spaceisdarkgreen Jun 07 '17 at 03:54

1 Answers1

1

$\mathbb{N} \approx \mathbb{N}^2$ should be classical. (e.g. using the bijection $f(n,m) = (2n+1)2^m.)$

By induction: $\mathbb{N} \approx \mathbb{N}^k$ for every $k \in \mathbb{N}$. This only uses that $\approx$ is an equivalence relation.

The set of (non-empty) finite subsets of $\mathbb{N}$ has an injection into the set $T = \cup_{k \in \mathbb{N}} \mathbb{N}^k$, mapping each finite set to its unique ordered tuple in $T$ when writing it in increasing order. A countable union of countable sets is countable. It follows that $S$ is at most $\aleph_0$ (and as least $\aleph_0$ too, mapping $n$ to $\{n\}$ is an injection from $\mathbb{N}$ into $S$.). So it's exactly $\aleph_0$ by Cantor-Bernstein.

Henno Brandsma
  • 242,131