Prove a diagonal obstruction for infinite binary sequences, transfer it to subsets and languages, and diagnose failed domain and computability arguments.
Suppose someone offers a list containing every infinite sequence of zeros and ones. We will construct a sequence that disagrees with the first row at position zero, the second row at position one, and so on. One disagreement is enough to distinguish two sequences; we need not compare all their entries.
Start with three finite row prefixes: 001, 110, 101. Number rows and columns from zero. The diagonal entries are 0,1,1, so flip them to obtain 100. Check the three mismatch positions yourself. This calculation produces a three-bit word. It does not yet produce an infinite sequence or prove a theorem about all infinite sequences.
Predict
Predict whether duplicate rows could defeat the construction. What if the list is reordered? Each displayed row still has its own indexed entry to flip. But the resulting antirow depends on the table. A particular sequence might be absent from one list and appear first in another. The general claim will be: for every proposed complete listing, there exists a sequence missing from that listing.
There is another obligation. If a list claims to cover only sequences that eventually become zero, our constructed sequence must also eventually become zero before its absence could contradict that claim. Predict whether flipping a diagonal automatically preserves such a restriction.
Experiment
Edit the finite table below. Before revealing its antirow, record the diagonal entries and predict their complements. For each row, name the column witnessing the disagreement. Change an off-diagonal entry and explain why the antirow stays unchanged; then change a diagonal entry and predict the affected bit.
Construct a word missing from these rows
Enter a square table of one to eight binary rows, one row per line. Row and column indices begin at zero. Repeated rows are permitted. Predict the opposite diagonal before revealing it.
At most 80 characters. Each row must have as many bits as the table has rows. Interior blank rows and nonbinary characters are rejected.
No result revealed. Editing the input clears the earlier result.
Temporary practice, with no saved response or mastery credit. Input is treated only as binary text and is never executed as code.
The explorer supplies finite evidence only. Here is a separate worked table, using the three prefixes from Try:
Row index
Row prefix
Diagonal bit
Antirow bit at that index
0
001
0
1
1
110
1
0
2
101
1
0
Any infinite extension of 100 still differs from these three rows at the displayed positions, irrespective of the rows’ unseen tails. However, there are many such extensions. A bounded table neither specifies every entry of an infinite antirow nor executes infinitely many comparisons.
Understand
Write N₀ for the natural numbers starting at zero. An infinite binary sequence is a function from N₀ to the two-element set of bits. Assume F assigns one such sequence F(n) to each natural index n. This is a proposed listing; repeated sequences are allowed. Define a sequence s by the rule s(n)=1−F(n)(n), where the final n selects the nth bit of row n.
First check the domain: each value of s is a bit, and the formula specifies one for every natural n. Thus s is indeed an infinite binary sequence. Next take an arbitrary row index k. At position k, s(k) and F(k)(k) are different. Consequently s is not row F(k). Since k was arbitrary, s is missing from the entire listing. Therefore no function from N₀ onto all infinite binary sequences exists. This is a universal mathematical argument, not an instruction to finish an infinite computation.
The same objects encode subsets: associate s with the set of indices where s has value one. Conversely, every subset supplies an indicator sequence. Checking each index shows these maps undo each other. Thus no natural-number list covers every subset of N₀ either.
To interpret this as a statement about languages, fix an enumeration of all finite words over a finite nonempty alphabet, by increasing length and then a fixed lexicographic order. Include the empty word. A language is any set of those words, not one word. Its membership bits form an infinite binary sequence. The finite words are countable; their arbitrary subsets, the languages, are not. Restricting attention to languages specified by finite programs changes the family and requires a separate argument.
Apply
Consider eventually-zero sequences, meaning sequences with only finitely many one bits. They can be listed: row n records the positions of one bits in the ordinary binary expansion of n. Every finite support S has the natural code obtained by summing 2^j over its members j, so every eventually-zero sequence appears.
For this enumeration, row n has zero at position n because 2^n is greater than n, including n=0. Its antirow is therefore the all-ones sequence. The mismatch argument remains correct, but the antirow is not eventually zero. Nothing contradicts the claimed listing. The lesson is not “diagonal arguments sometimes fail mysteriously”; the missing step is precisely membership in the proposed target domain.
Now suppose one total computable bit-valued function E(n,k) lists all total computable binary sequences as its rows. Total means it halts on every pair of natural inputs. Then d(k)=1−E(k,k) is also total and computable. Coverage would place d at some row j, contradicting its value at j. Therefore no such uniform total computable listing exists.
This does not make total computable sequences uncountable. Their finite program descriptions are countable. The distinction is between a set-theoretic listing and a single effective evaluator guaranteed to halt for every row and input. An enumeration of arbitrary program texts provides no such guarantee: a program may run forever or return a non-bit. A timeout makes evaluation bounded but can destroy the diagonal mismatch when the timed-out program later returns the default bit. This conditional proof establishes an obstruction to the specified uniform enumeration; it does not implement a halting or totality test.
Continue
For every diagonal argument, record four things: the proposed listing, the diagonal definition, membership of the new object in the claimed domain, and the indexed witness against an arbitrary row. Then state the quantifiers and any effectiveness assumptions. The practice asks you to transfer this proof to languages, explain a genuine domain failure, and distinguish program descriptions from total behaviors. Finite table manipulation supports the idea; the full proof and its hypotheses carry the infinite conclusion.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Four displayed row prefixes, with columns indexed 0 through 3, are 1010, 0011, 1110, 0101. Form the flipped diagonal and supply a distinct mismatch witness for each row. State exactly what this finite calculation proves and what it cannot establish about unspecified infinite tails.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let F:N₀→{0,1}^N₀ be any function. Prove F is not onto by defining a new sequence. State the quantifiers, establish membership in the target set, and explain why duplicate rows or a different ordering cannot evade the argument.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove a bijection between binary sequences and subsets of N₀. Then fix an enumeration w₀,w₁,… of all finite words over {p,q}, ordered by length and then lexicographically with p before q. Use it to prove that the set of languages over this alphabet cannot be listed by N₀. Distinguish a word from a language.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
An eventually-zero sequence has only finitely many 1 bits. Enumerate these sequences by letting row n have 1s at the positions of 1 bits in the binary expansion of n, with the least significant position indexed 0. Prove this listing is onto. Show its flipped diagonal is the all-ones sequence and explain why that does not contradict the listing.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Suppose a total computable bit function E(n,k) is claimed to list every total computable binary sequence: for every such sequence f there is n with E(n,k)=f(k) for all k. Prove this impossible. Explain why the conclusion does not say that the family of total computable sequences is uncountable.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A proposed program lists every program text P₀,P₁,… and computes d(n) by running P_n on input n, then flipping its output. Diagnose two reasons this may fail to define a total binary sequence. A repair allows n+1 steps, flips a bit if one is returned, and otherwise outputs 0. Does the repaired total procedure necessarily disagree with every total bit program on its own index? Explain with the timing assumption, not a claim about any particular programming language.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
