# An infinite chain of finite set is countably infinite

Let $Z$ be an infinite set of finite sets.

For all $X,Y\in Z$ we have $X\subseteq Y$ or $Y\subseteq X$.

I am trying to prove that $Z\sim\mathbb{N}$ where $\sim$ represents equivalence of sets.

I think I need to think of a function $f$ from $Z$ to $\mathbb{N}$ that is a bijection and that will prove this theorem, but I can't think of one. Hints?

• What do you mean by $Z\sim\mathbb{N}$? – Leo163 Dec 19 '17 at 11:41
• If $X$ and $Y$ are finite, distinct, and $X\subset Y$, then what can you say about their respective cardinalities? – Not Mike Dec 19 '17 at 11:41
• @Leo163 I edited – kickstart Dec 19 '17 at 11:44

## 1 Answer

Prove that if $X\in Z$, and $|X|=n$, then there is no other $Y\in Z$ with $|Y|=n$.

This lets you define a natural injection from $Z$ into $\Bbb N$, and the fact that $Z$ is infinite should be enough to conclude the rest.

• I'm surprised that you didn't mention that countable choice is required here. – JDH Dec 19 '17 at 12:13
• I'm surprised that it's required here. :) – Asaf Karagila Dec 19 '17 at 12:14
• Oops, I was thinking about the union of $Z$, which is also countable, assuming countable AC. – JDH Dec 19 '17 at 12:15
• Yeah, that's a whole other thing. :P it took me a moment when I read the question for the first time. :) – Asaf Karagila Dec 19 '17 at 12:15
• @AsafKaragila Can you explain little more? I didn't not quite catch it – kickstart Dec 20 '17 at 21:27