Every essay — page 14
Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Ladders Concepts Search
Logic
What can be said in a system, what follows from it, and what it cannot settle about itself.
A formula is a corner of a cube
A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.
One connective is enough
Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.
The map that puts neighbours side by side
Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.
Four circles cannot do it
Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.
Twenty-four out of two hundred and fifty-six
Aristotle's syllogisms are four sentence forms in four arrangements, which makes 256 patterns of argument. Fifteen of them are valid. Nine more become valid if you assume the things being talked about exist, and the gap between those numbers is a two-thousand-year-old disagreement.
Every row, or one column
For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.
The tree that closes
To prove a formula, assume it false and take it apart. Every branch ends in a contradiction, or one of them describes exactly how it could have been false — and either way the tree is the answer, drawn.
Two worlds that both obey the rules
A statement is independent of a list of axioms when there is a structure satisfying the axioms where it holds and another where it fails. That is not a claim about what nobody has managed to prove — it is a proof that nobody can.
An infinite tree has an infinite path
A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.
The row that is not on the list
Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.
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.
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.
Two injections make a bijection
If each of two collections fits inside the other without collisions, they are the same size. That sounds obvious and is not, because neither injection needs to be onto — and the proof is a rule for deciding which of the two to follow, one chain at a time.
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.
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.
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.
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.
The axiom is the shape of the graph
Add one operator meaning necessarily and the choice of which axioms to accept stops being a matter of taste. Each candidate axiom is true of exactly those worlds-and-arrows diagrams whose arrows have a stated property, and a logic is a class of graphs.
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.
The arithmetic that loses subtraction
Adding one to an infinite collection changes nothing, and neither does doubling it, or squaring it. What that costs is the two operations that were doing the work — an equation between infinite sizes cannot be cancelled, and how many are left stops being a question.
A line with as many points as a square
Interleave the decimal places of two numbers and one number comes out; take every other place back and the two return. The square has no more points than the segment, and dimension turns out to be invisible to counting.
Countable, and everywhere
The numbers a polynomial can catch arrive in finite batches, so they can be listed. They are also in every interval, however short. Being listable turns out to say nothing whatever about being sparse.
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.
One step in front of infinitely many
Put one step before an infinite run of them and nothing has changed; put it after and something has. Ordinal addition records that difference, which is why it is not commutative — and why it keeps information that counting throws away.