# 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

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.
• Oops, I was thinking about the union of $Z$, which is also countable, assuming countable AC. – JDH Dec 19 '17 at 12:15