Matpic
mathematics, in pictures
Concept

Venn diagram

A family of overlapping closed curves arranged so that every pattern of membership occupies exactly one region. It exists for any number of sets, though past three the curves cannot all be circles.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

4 circles, and the 14 patterns they realise. Closed curves overlapping in the plane, with each region of the arrangement identified by which curves contain it.

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.

logic · Class diagrams The 256 syllogistic forms, and the 24 that work. A grid with one cell per syllogistic form, marked according to whether it is valid and what it needs to be valid.

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.

logic · Class diagrams A smallest model of ∀x (Ax → ∃y (By ∧ ¬Cy)) ∧ ∃x (Ax ∧ Cx) ∧ ∀x (Bx → ¬Ax). Three overlapping circles with some regions shaded as empty and a single dot in each occupied region, forming a model of a sentence of monadic first-order logic.

One thing in each region is enough

Give first-order logic its full apparatus of nested quantifiers but only one-place predicates, and every question about truth is still settled by the regions of a diagram. A predicate cannot tell apart two things in the same region, so no model ever needs more than one thing per region — and with three predicates there are only 255 models to try.

logic · Class diagrams Carroll's babies and crocodiles, on four ellipses. Four overlapping ellipses labelled with the four classes of a sorites, the regions emptied by its premises shaded, and the regions its conclusion requires to be empty outlined.

The conclusion is what survives the erasing

Lewis Carroll's puzzles give three premises about four classes — babies, logical people, the despised, crocodile-managers — and ask what follows. Draw all four, shade what the premises rule out, then erase the classes the conclusion is not about: a region survives as empty only if everything above it was. What is left is the conclusion, and erasing a class turns out to be exactly one step of resolution.

logic · Class diagrams A random walk across the regions to the one that satisfies every clause. Four overlapping ellipses with a dot in each of their sixteen regions, one marked as the only assignment satisfying the clauses, and a path of arrows from a random starting region to it, each arrow crossing one ellipse.

A walk that beats trying everything

To decide whether clauses of three letters can all be satisfied, the obvious method tries all 2ⁿ assignments. Uwe Schöning's method, from 1999, starts at a random assignment and wanders: pick a clause that is false, flip one of its letters at random, and repeat three times as many times as there are letters. A single try usually fails, but it succeeds with chance at least about (3/4)ⁿ, so about (4/3)ⁿ tries are enough — and the reason is a walk on a line that goes the wrong way two times in three.

logic · Class diagrams

Named alongside it

The objects these essays reach for when they reach for this one.

SatisfiabilityDecision procedureExhaustive searchQuantifierSyllogismArrangementBoolean functionCategorical statementClauseClosed curveConvexityCounterexample

All concepts