Exercise · ZW-CANTOR-S-DIAGONAL-THEOREM-010 · ★★★ Advanced

Let \(f\colon\mathbb{N}\to\{0,1\}^{\mathbb{N}}\) be any function. Which of these sequences is guaranteed not to lie in the image of \(f\), for every choice of \(f\)?

Choose one option.

Show answer
  • C. \(u(n)=1-f(n)(n)\).

Explanation

\(u(n)=1-f(n)(n)\) differs from \(f(n)\) at position \(n\) for every \(n\), so it never equals any \(f(n)\). The other options may coincide with some \(f(k)\) depending on the chosen function.

Study Set theory in ZWMath →

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-009