Two and a half thousand years of trying to write down what it means for one thing to follow from another.
Logic studies valid inference — the patterns by which the truth of some claims would force the truth of another. It is not (mostly) the study of how people in fact reason. It is the study of how, when we reason well, our reasoning is structured.
An argument is valid iff: in any case in which the premises are true, the conclusion must be true. Validity is about form, not content. All A are B; all B are C; therefore all A are C is valid whatever A, B, C name.
A sound argument is valid AND has true premises. Validity is preserved under reinterpretation; soundness is not. Logic gives us the first; the world (and the special sciences) gives us the second.
(1) Aristotelian syllogistic — c. 350 BCE.
(2) Stoic propositional logic — c. 250 BCE.
(3) Boole's algebra of thought — 1854.
(4) Frege's Begriffsschrift & modern predicate logic — 1879.
(5) Gödel's incompleteness theorems — 1931.
Aristotle classified the valid moods of the categorical syllogism. Each premise has subject (S), middle (M), or predicate (P) terms, and is one of four kinds: A (universal affirmative), E (universal negative), I (particular affirmative), O (particular negative).
A: All S are P. · E: No S are P. · I: Some S are P. · O: Some S are not P.
Each valid mood was given a mnemonic name with a vowel-pattern indicating its premises and conclusion: Barbara (AAA-1), Celarent (EAE-1), Darii (AII-1), Ferio (EIO-1)... a thirteenth-century memory trick that lasted a millennium.
Where Aristotle worked with terms (S, M, P), the Stoics worked with whole propositions (P, Q, R) and connectives — and, or, if-then, not. They formulated five "indemonstrables" from which all else was supposed to follow.
| P | Q | P → Q | P ∧ Q | P ∨ Q | ¬ P |
|---|---|---|---|---|---|
| T | T | T | T | T | F |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
Wittgenstein presented the truth-table method in his Tractatus (1922). The technique was already in Frege and Peirce; Wittgenstein made it standard pedagogy.
George Boole's An Investigation of the Laws of Thought turns logic into algebra. Let 1 stand for the universe of discourse, 0 for the empty set, x for the class of x's. Then:
A century later, Claude Shannon noticed (1937) that Boolean algebra describes the behaviour of switching circuits. Every digital computer in the world today is the descendant of that observation — a Boolean engine etched in silicon.
¬ (P ∧ Q) ≡ (¬ P) ∨ (¬ Q)
"It is not the case that both P and Q" is equivalent to "either not-P or not-Q."
¬ (P ∨ Q) ≡ (¬ P) ∧ (¬ Q)
Augustus De Morgan (1806–71) — Boole's correspondent and friend.
Gottlob Frege's Begriffsschrift ("concept-script") of 1879 is the most consequential ninety pages in the history of logic. He invents the quantifier (∀, ∃), distinguishes function from object, distinguishes sense (Sinn) from reference (Bedeutung), and gives modern logic essentially its current shape.
"For every x, if x is human then x is mortal." Aristotle could express this only by the all-statement; Frege expresses it by binding a variable. The gain: arbitrary nesting.
Everyone loves someone-or-other.
There is some particular y whom everyone loves. The two are very different. Frege's notation makes the difference visible.
"The morning star" and "the evening star" have different senses (different ways of presenting their object) but the same reference (Venus). The puzzle "a = a is trivial; a = b is informative" turns on this distinction.
Frege's Grundgesetze (vol. II, 1903) was about to go to press when Russell wrote: "Let R be the set of all sets that are not members of themselves. Is R a member of itself?" If yes, no; if no, yes. The contradiction toppled Frege's system. He added a now-famous appendix beginning: "A scientist can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished."
Whitehead and Russell's three-volume Principia Mathematica (1910, 1912, 1913) was the heroic attempt to derive all of mathematics from logic — to repair Frege's project with the theory of types, to silence Russell's paradox, and to establish logicism on a footing.
This identity is, famously, not proved in Principia until volume I, page 379, with the cheerful annotation: "The above proposition is occasionally useful." The slow build is not a joke; it is what proving everything from logic looks like.
Russell's response to his paradox: stratify entities into types. Sets at type 1, sets-of-sets at type 2, and so on; "the set of all sets that are not members of themselves" is now ill-formed across types. Modern dependent type theories (Martin-Löf, Coq, Lean) descend from this idea.
The propositions of logic say nothing. They are the analytical propositions. Logic is not a body of doctrine, but a mirror-image of the world.
Tractatus Logico-Philosophicus, 1922
In 1931 a 25-year-old Viennese, Kurt Gödel, published "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I." It contained two theorems that ended the project of Principia.
Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete: there are statements of the language of F which can neither be proved nor disproved in F.
For any consistent system F as above, F cannot prove its own consistency.
Gödel encoded statements about the system as numbers (Gödel numbering). He then constructed a sentence G that, in effect, says "G is not provable in F." If F proves G, then G is true (by what G says) — but G says it isn't provable, so F is inconsistent. If F doesn't prove G, then G is true — and unprovable. Either way, F is incomplete.
It is hard to overstate the significance. Hilbert's programme — to provide a complete and consistent foundation for all of mathematics — was finished. Computability (Turing, 1936) and undecidability followed. The Halting Problem is a child of Gödel's argument.
If P implies Q, and P, then Q. Affirming the antecedent.
If P implies Q, and not Q, then not P. Denying the consequent.
Chain implication.
Either-or, not-this, so that.
If assuming P yields contradiction, infer not-P.
From "all," infer the particular case.
"This sentence is false." If it is true, it is false. If it is false, it is true. Known to Eubulides of Miletus, c. 350 BCE. Tarski's solution (1933): no consistent language can contain its own truth predicate; truth must be defined in a metalanguage.
The set R of all sets that are not members of themselves. R ∈ R iff R ∉ R. Solution: stratify (Russell), restrict comprehension (ZF set theory).
One grain of sand is not a heap. Adding a grain to a non-heap leaves a non-heap. So no number of grains makes a heap. Vagueness; the heart of much modern logic of borderline cases.
"If this sentence is true, then God exists." A purely logical derivation appears to prove an arbitrary claim. A test case for non-classical logics.
"The smallest positive integer not definable in fewer than twelve words." That phrase has eleven words. Contradiction. Hints that "definable" is not a well-defined predicate.
An infinite sequence of sentences, each saying "all subsequent sentences are false." No self-reference, but contradiction. Suggests the Liar's pathology is not fundamentally about self-reference.
Classical logic — bivalent, with excluded middle, with explosion (anything follows from a contradiction) — is one logic among many. Twentieth-century work has built dozens of alternatives, motivated by paradox, by foundations, or by application.
| Logic | Founder · year | What's relaxed | Application |
|---|---|---|---|
| Intuitionistic | Brouwer · 1907 | excluded middle (LEM) | constructive math, type theory |
| Modal logic | C. I. Lewis · 1918 | adds □ (necessity), ◇ (possibility) | metaphysics, computer science |
| Many-valued | Łukasiewicz · 1920 | bivalence (T/F only) | vagueness, fuzzy systems |
| Relevant logic | Anderson, Belnap · 1958 | "explosion" (ex falso quodlibet) | conditionals, paradox |
| Paraconsistent | da Costa · 1963 | non-contradiction | databases, dialetheism |
| Linear logic | Girard · 1987 | contraction, weakening | resources, concurrency |
The blackboard is older than print. The chalk is calcium carbonate — chemically a relative of the cliffs of Dover. Mathematics has been written on this surface, in this material, for some four hundred years. It is hard to think of a more efficient interface to philosophy: one cubic centimetre of carbonate becomes, on green slate, the law that two propositions cannot be both true and not.
| Author | Work | Year | What it did |
|---|---|---|---|
| Aristotle | Prior Analytics | c. 350 BCE | founded syllogistic |
| Chrysippus (lost; via Sextus) | Logical Investigations | c. 250 BCE | propositional logic |
| Boole | The Laws of Thought | 1854 | algebra of logic |
| Frege | Begriffsschrift | 1879 | quantifier; predicate logic |
| Frege | "On Sense and Reference" | 1892 | Sinn / Bedeutung |
| Whitehead & Russell | Principia Mathematica | 1910–13 | logicism, type theory |
| Wittgenstein | Tractatus Logico-Philosophicus | 1922 | logic as picture; truth tables |
| Gödel | "On formally undecidable propositions..." | 1931 | incompleteness theorems |
| Tarski | "The Concept of Truth in Formalised Languages" | 1933 | semantic theory of truth |
| Turing | "On Computable Numbers" | 1936 | Turing machines, halting problem |
| Quine | Methods of Logic | 1950 | standard textbook |
| Kripke | "Semantical Considerations on Modal Logic" | 1963 | possible-world semantics |
Crash Course Philosophy and Wireless Philosophy each cover the basics with great clarity; the BBC's In Our Time on Gödel is a high-water mark of public philosophy. Embed below.
Watch · BBC In Our Time · Gödel
Watch · Wireless Philosophy · Logic
Logic must take care of itself.
Wittgenstein, Tractatus 5.473