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?

  • $\begingroup$ What do you mean by $Z\sim\mathbb{N}$? $\endgroup$ – Leo163 Dec 19 '17 at 11:41
  • 1
    $\begingroup$ If $X$ and $Y$ are finite, distinct, and $X\subset Y$, then what can you say about their respective cardinalities? $\endgroup$ – Not Mike Dec 19 '17 at 11:41
  • $\begingroup$ @Leo163 I edited $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.