Purported Bijection Table

Window: [0, 9]

Negation Reference

Alphabet negation mapping:

Challenge: Identify the Diagonalized String

What is the diagonalized string that results from applying Cantor's diagonal argument to this table?

Parameters

Parameters

Alphabet

{0, 1}

Current alphabet symbols

Instructions

How to Use

1. Study the purported bijection table

2. Identify the diagonal elements (position i in row i)

3. Construct the diagonalized string by negating each diagonal element

4. Enter the diagonalized string as your answer

5. After a correct answer, a new table will be generated automatically

Controls

• Adjust alphabet size, window size, and window start

• Generate new table for a fresh challenge

• The diagonal construction is shown below the table

Cantor's Diagonal Argument

Cantor's diagonalization proves that no bijection can exist between ℕ (natural numbers) and the set of all infinite strings over any alphabet.

The Argument:

  1. Assume a bijection f: ℕ → Σ^ω exists
  2. Construct a diagonal string d
  3. For each position i, set d[i] ≠ f(i)[i]
  4. Then d differs from every f(n) at position n
  5. Therefore d is not in the range of f
  6. Contradiction! No such bijection exists

Countability vs Uncountability

Countable Sets:

  • ℕ (natural numbers)
  • ℤ (integers)
  • ℚ (rational numbers)
  • Finite strings over any alphabet

Uncountable Sets:

  • ℝ (real numbers)
  • Infinite strings over any alphabet Σ^ω
  • Power set of any infinite set
  • Set of all functions ℕ → ℕ

Key Insight:

The diagonal argument shows that some infinities are "larger" than others, establishing the hierarchy of infinite cardinalities.