What a system cannot say — page 1
Logic
A list that cannot contain itself
The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.
Logic
The sentence that says it has no proof
Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.
Logic
A sequence that explodes and still stops
Goodstein's sequence starting at 4 climbs past any number you care to name and reaches zero after about ten to the hundred and twenty million steps. The proof that it stops is a second sequence, running alongside it, that goes down.
Logic
The middle that is not excluded
Either it is raining or it is not. Drop that as an axiom and what is left is still a logic — one with models made of open sets and of stages of knowledge, in which a set and its negation between them miss the boundary.
Computation
The circle that will not square
The other three impossibilities are a number having the wrong degree. This one is a number having no degree at all — and that is a claim no finite search can establish, which makes it the one place in this field where the picture has to admit what it is not doing.
Applied
Four conditions, and no rule that has all of them
Five reasonable rules can return five different winners on one set of ballots, which invites the obvious question of which one is right. The answer is that the conditions anybody would write down cannot all hold at once — and here each named rule's own violation is found by search rather than quoted.
Applied
No stable rule is safe from a lie
A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.
Topology
The solid where the answer is not two
A slab with a hole through it has flat faces, straight edges and sixteen corners, and its alternating sum is zero. It is not a trick and not a degenerate case — it is the object that shows the theorem had a hypothesis nobody had written down.
Logic
A game that decides what can be said
Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.
Logic
A proof with one rule
Two clauses that disagree about exactly one variable can be combined into a third that forgets it; repeat, and if the clauses cannot all be true the empty clause eventually appears — a complete proof system with a single move.
Logic
The choice nobody can write down
Given finitely many pairs, picking one thing from each is a finite list of decisions and needs no justification. Given infinitely many, the list cannot be finished — and whether one exists anyway is an axiom, independent of everything else, whose consequences include a theorem most people refuse to believe.
Algebra
The group that will not come apart
Solving an equation by radicals means building a tower of roots, and a tower of roots corresponds to a chain of subgroups with abelian steps. For the general equation of degree five that chain would have to descend through a group of sixty elements with no normal subgroup in it — so there is no formula, and the obstruction is a finite object that can be written out.
Logic
The size that cannot be pinned down
There is no largest infinity, because no collection has as many members as it has sub-collections. What is not settled is whether anything sits between the first two — and that is not an open problem but a proved absence of an answer.
Logic
Every ordinal in base omega
Every ordinal below a certain point is a descending sum of powers of ω, in exactly one way. That notation makes comparison mechanical, it is what hereditary base notation becomes when the base is replaced, and it stops at the first ordinal it cannot name.
Logic
Reached from below, or not at all
Every limit ordinal anybody meets is the end of an increasing sequence — ω, ω·2, ω^ω, all of them approached one step at a time. The first uncountable ordinal is not, and the reason it is not constrains the size of the continuum.
Logic
An ordinal as a growth rate
Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.
Logic
Two diagrams the language cannot tell apart
A modal formula sees a diagram of worlds and arrows through a very narrow window. Exactly how narrow is settled by a game: where one player can answer every move, no formula whatever separates the two starting worlds, however different the diagrams look.
Logic
Necessity that means provable
Read the box as "the theory proves" and one modal logic stops being a proposal about what necessity might mean. It becomes a complete description of what a formal system can prove about its own proofs — and its frames run forward, compose, and stop.
Logic
Nearly always, or nearly never
Toss a coin for every pair of points and ask whether the graph that results has some property. For a property a first-order sentence can state, the answer in the limit is never a genuine probability — it is zero or it is one, and the game is what proves it.
Logic
The distance a sentence can see
A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.
Logic
A language that can name a set
Allow a sentence to quantify over sets of positions as well as positions, and on words the answer changes completely: the sets buy exactly the languages a finite automaton recognises. Whether the number of letters is even is the smallest example of what the sets are for.
Number
The sieve that cannot finish
Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.
Logic
A lemma, and the proof that never mentions one
Proving something by first proving a lemma is what makes mathematics readable, and it is exactly what makes a proof system impossible to search — because the lemma can be any formula at all. Gentzen proved the step can always be removed, and the removal is not free.
Logic
The instance that has to be guessed
Every rule of a propositional tableau replaces a formula by shorter ones, which is why it stops. The rule for a universal claim does not replace it — it keeps it and adds an instance — and one word changing turns a decision procedure into a search that may run forever.