Two questions I encountered in my last Set Theory HW.

1) Let T be a set of all Binary sequences that do not contain 2 consecutive zeros (ex. $100111010\notin T$). Let B be a set that contains all Binary sequences. Do B and T have the same Cardinality? Does T have the same Cardinality as the set that contains all natural series ($|T|=|\mathbb{N}^\mathbb{N}|$)?

To the first question I answered yes since:

Each binary number can be view as a natural number , B is an infinite subset of $\mathbb{N}$ thus $|B|= \aleph_0$. I very similarly take care of T and prove $|T|=\aleph_0$.

To the seconed I answered no since Cantor's Diagonal Argument proves $|\mathbb{N}|<|\mathbb{N}^\mathbb{N}|$.

Is this the way to go about it? am I correct?

2) Prove $|X|<|\{0,1,2\}^X|$. I know Cantor's Theorem gives $|X|<|\{0,1\}^X|$ but I don't know how to proceed.

  • 2
    $\begingroup$ Is $B$ the set of finite binary sequences, or the set of all binary sequences (including infinite sequences) ? $\endgroup$ – Peter Dec 22 '15 at 18:28
  • 2
    $\begingroup$ For $(2)$, do you see why $\vert \{0, 1\}^X\vert\le \vert \{0, 1, 2\}^X\vert$? $\endgroup$ – Noah Schweber Dec 22 '15 at 18:30
  • $\begingroup$ @peter the question doesn't expand on it, but I guess they mean finite numbers since infinite ones aren't technically binary numbers.... how would it alter the answer? $\endgroup$ – Rubenz Dec 22 '15 at 23:30
  • $\begingroup$ @noahschweber cause there's the obvious 1:1 function from one to the other? $\endgroup$ – Rubenz Dec 22 '15 at 23:31
  • $\begingroup$ @user254509 Yup, that's right. So if Cantor's theorem tells you that $\vert X\vert<\vert \{0,1 \}^X\vert$, and you know $\vert \{0, 1\}^X\vert\le\vert\{0, 1, 2\}^X\vert$, then . . . $\endgroup$ – Noah Schweber Dec 22 '15 at 23:32

Your Answer

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

Browse other questions tagged or ask your own question.