Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: A Diagonal Explorer

Build a small toolkit that enumerates sequences, constructs diagonal escapes, and visualizes a Cantor-style table with a plot, step by step in Python.

In this project you will build a small diagonal explorer: code that takes any list of infinite binary sequences and produces one that is guaranteed to be missing. Then you will turn the idea into a picture, so you can see the diagonal.

You will practice three ideas from this chapter: sequences as functions โ„• โ†’ {0, 1}, subsets of โ„• as sequences, and Cantor's diagonal argument.

Plan

  1. Represent an infinite sequence as a Python function n โ†ฆ bit.
  2. Write a function diagonal(listing) that returns a new sequence missing from the list.
  3. Test it against several listings, including a clever one.
  4. Plot the table and highlight the diagonal.
  5. Extend it: find where the diagonal sequence would be if you tried to add it.

Step 1: sequences and listings

A listing is a function L(i) that returns the i-th sequence. Our sequences are also functions.

Python Step 1 and 2: the diagonal escape

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the list L above is not even trying to be clever: it lists only sequences with finitely many 1s. The diagonal sequence d turns out to be all 1s (bit n of the number n is always 0), so it has infinitely many 1s and is not among them.

Step 3: attack the explorer with a clever listing

Can you build a listing that covers d? Let us try an adaptive listing: after seeing the diagonal, we add it as L'(0) and shift everything else by one. The new diagonal is a different sequence.

Python Step 3: adding the diagonal to the list does not help

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is the heart of why P(โ„•) cannot be listed: every list, however patched, has a diagonal missing from it.

Step 4: draw the table

Now we draw the first rows and columns of the table as an image. Each cell is a square: dark for 1, light for 0. We outline the diagonal.

Python Step 4: plot the table and its diagonal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 5: from sequences to subsets

A binary sequence is the characteristic function of a subset of โ„•: n โˆˆ S when the bit at n is 1. The diagonal sequence is therefore the subset

Text
D = { n : n โˆ‰ S_n }

which is exactly the set D from Cantor's theorem. Let us check that the two views agree.

Python Step 5: the diagonal sequence is the diagonal set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Extensions

  • Modify diagonal so that it avoids ending in all 1s, to mimic the decimal argument that avoids trailing 9s.
  • Use base 10 digits and generate the real number 0.dโ‚dโ‚‚dโ‚ƒ... with the 5/6 rule from the diagonal lesson.
  • Try diagonal on a listing that repeats sequences. Does the escape still work?
  • Replace {0, 1} with {0, 1, 2} and show that the construction generalizes.

A program can only represent sequences that follow a rule. There are only countably many programs, so there are only countably many computable sequences, but uncountably many sequences. Most sequences have no program. That idea leads to the theory of computation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the function diagonal(L) return?

    It flips the n-th bit of the n-th sequence, so it differs from each listed sequence somewhere.
  2. 2. If you add the diagonal sequence to the list, what happens?

    Any listing, however patched, has its own diagonal. The process never completes.
  3. 3. A binary sequence corresponds to which set?

    That set is a subset of โ„•; the sequence is its characteristic function.
  4. 4. Why can a program not produce every binary sequence?

    Programs are finite strings, which are countable, while binary sequences are as numerous as P(โ„•).

Summary

  • A diagonal explorer takes any listing of sequences and returns a sequence guaranteed to be missing.
  • Patching the list with the diagonal only creates a new diagonal: the process never ends.
  • The table of a listing can be drawn as a grid; the diagonal is the set of cells (n, n).
  • Binary sequences and subsets of โ„• are the same objects, and the flipped diagonal is Cantor's set D.
  • Countably many programs cannot name uncountably many sequences.

Next: Project: The Hereditarily Finite Universe