Exercise · ZW-CANTOR-S-DIAGONAL-THEOREM-006 · ★★☆ Intermediate
Why can the diagonal sequence \(t\) not appear in a list \(s_1,s_2,\dots\)?
Choose one option.
Show answer
- C. Because \(t\) differs from \(s_n\) at position \(n\), for every \(n\).
Explanation
If \(t=s_n\) for some \(n\), at position \(n\) we would have \(1-s_n(n)=s_n(n)\), which is impossible. The other reasons are not valid.
Review the concept: Cantor's diagonal theorem
Theorem proving that the set \(\{0,1\}^{\mathbb{N}}\) of binary sequences is not countable, by building a sequence that appears in no list.
\[t(n)=1-s_n(n)\]
More practice problems: cantor's diagonal theorem
- ZW-CANTOR-S-DIAGONAL-THEOREM-001 What does Cantor's diagonal theorem state?
- ZW-CANTOR-S-DIAGONAL-THEOREM-002 Which sequence does the diagonal proof build to escape a list?
- ZW-CANTOR-S-DIAGONAL-THEOREM-003 Is ℕ countable?
- ZW-CANTOR-S-DIAGONAL-THEOREM-004 Which of these sets is uncountable?
- ZW-CANTOR-S-DIAGONAL-THEOREM-005 With s_1=000…, s_2=111… and s_3=0101…, what are the first three terms of the diagonal sequence t, w…
- ZW-CANTOR-S-DIAGONAL-THEOREM-007 What does the diagonal argument imply for ℝ?
- ZW-CANTOR-S-DIAGONAL-THEOREM-008 Which of these statements is true?
- ZW-CANTOR-S-DIAGONAL-THEOREM-009 Let A be the set of binary sequences with finitely many ones. Is A countable?
← ZW-CANTOR-S-DIAGONAL-THEOREM-005 ZW-CANTOR-S-DIAGONAL-THEOREM-007 →