One thing in each region is enough

Twenty-four out of two hundred and fifty-six decided every syllogism by a count. Three classes cut the world into eight regions, a region is either empty or not, and so there are 256 ways the world can be as far as three classes are concerned; an argument is valid when no one of the 256 makes the premises true and the conclusion false. It ended by listing what a syllogism cannot say, and naming the change that ended the method: Frege’s logic of 1879, with quantifiers over individuals and relations between them, in which “validity is no longer decidable by exhaustion”.

That change has two parts, and they can be separated. One is the quantifiers — “for every $x$ there is a $y$ such that…”, nested as deeply as anybody likes. The other is the relations — predicates that take two or more arguments. Keep the first and refuse the second, and exhaustion still works. A sentence of any complexity, with every quantifier Frege allowed, is still decided by the regions of a diagram, provided all its predicates take a single argument. Leopold Löwenheim proved it in 1915; the logic is called monadic.

A sentence the syllogisms could not write #

The sentence above is out of reach of the four sentence forms. Its first clause says that if anything is $A$, there exists something that is $B$ and not $C$ — a universal with an existential inside it, relating two different things. Its second says something is both $A$ and $C$; its third, that nothing is both $B$ and $A$. No syllogism has a quantifier inside another quantifier, and no syllogism can say “if there is one of these, there is one of those”.

Yet the diagram decides it. The drawn model has one thing in the region $A \wedge C \wedge \neg B$ and one in the region $B$ alone, and everything else empty. Evaluating the sentence there is a small computation. The second clause is true, because the first thing is $A$ and $C$. The third is true, because the only $B$ is not $A$. The first requires, for each thing that is $A$ — only the first — some thing that is $B$ and not $C$, and the second thing is exactly that.

The model is also the smallest possible, and the reason is visible. The second clause forces something into a region inside both $A$ and $C$; the first then forces something that is $B$ and not $C$; and the third forbids that second thing from being $A$. Two things, in two regions, and nothing else needed. The shape of the argument is the shape of the drawing: each clause either empties regions or demands that one be occupied.

Why a predicate cannot count #

Everything turns on one observation. A one-place predicate is a property of a single thing, so the only information a monadic sentence can have about a thing is which region it is in — which of the predicates it satisfies. Two things in the same region satisfy exactly the same predicates, and no formula in the language can tell them apart.

So take any model, however large, and delete duplicates: keep one thing from each occupied region and throw the rest away. A universal claim that was true of everything is still true of what is left, because what is left is a subset. An existential claim that found a witness still finds one, because the witness’s region is still occupied, by a representative that satisfies every predicate the witness did. The argument runs by induction through the formula, one quantifier at a time, and it needs nothing but the fact that a formula’s truth for a thing depends only on that thing’s region.

The figure runs it on a model of fifteen things spread over five regions — four things in $B$ alone, three in $A$ alone, two in $C$ alone, three things in $A$ and $C$, three in $B$ and $C$. The sentence is true there. Collapsed to five things, one per region, it is still true. The collapse cannot change a verdict, and that single fact makes the logic decidable: every model has a collapsed twin with at most eight things, one per region, and there are only finitely many of those.

This is the same phenomenon as a game that decides what can be said measures: two structures a language cannot distinguish are, for that language, the same structure. There the indistinguishability has to be won round by round in a game; here it is immediate, because a monadic formula looks at one thing at a time and a thing is nothing but its region.

Every model, drawn at once #

With the collapse in hand, the whole space of models is a finite object. Three predicates cut the world into eight regions; a collapsed model is a choice of which regions are occupied; there are $2^8 = 256$ choices, and the one with nothing occupied is excluded because first-order logic assumes the world has at least one thing in it. The grid shows all 255, each lit where the sentence is true.

Sixteen are lit. They are the occupancies that include the region $A \wedge C \wedge \neg B$ and the region $B \wedge \neg A \wedge \neg C$ — the two the smallest model used — and leave both regions inside $A$ and $B$ empty, with the other four regions free: $2^4 = 16$. The pattern in the grid is that structure made visible: two blocks of eight, in the rows and columns those bits dictate.

This is a decision procedure, and a complete one. A monadic sentence with $n$ predicates is satisfiable exactly when one of the $2^{2^n} - 1$ occupancies makes it true, and it is valid exactly when all of them do. For three predicates that is 255 evaluations; for four, 65,535; for five, over four billion. The number is doubly exponential in the number of predicates, and nobody would decide a large monadic sentence this way — but the procedure always finishes, and that is the whole difference between this logic and the full one.

A valid sentence that sounds false #

The sentence $\exists x\,\forall y\,(Ax \to Ay)$ is known as the drinker’s paradox, in Raymond Smullyan’s phrasing: in any non-empty pub there is someone such that, if that person is drinking, everyone in the pub is drinking. It sounds like a claim about a remarkable person. It is a theorem of logic, and the search proves it by lighting every square.

The reason is a case split the grid performs 255 times. If everyone is $A$, any person will do as $x$, because the conclusion “everyone is $A$” is true. If someone is not $A$, choose that person as $x$: the condition “$x$ is $A$” is false, so the implication holds whatever the others do. Either way a witness exists. The paradox is only the gap between the English “if” and the logical one — the material conditional is true whenever its condition fails, and the witness in the second case is chosen precisely because it fails.

What the search adds is certainty without insight: it does not find the case split, it simply checks every model. For a sentence whose validity is surprising, that is exactly the kind of evidence worth having alongside the argument, and it is available only because the logic is monadic. The same sentence with a two-place predicate in it could not be checked this way at all.

A truth table one level up #

The grid has a second reading, and it turns monadic logic into something already familiar. Each square is a choice, for each of the eight regions, of occupied or empty. Call “region $r$ is occupied” a proposition $p_r$. Then a square is an assignment of true or false to eight propositions, and the grid is nothing but the truth table of a propositional formula in $p_0, \ldots, p_7$ — one row per square, a corner of an eight-dimensional cube for each.

Heinrich Behmann made that exact in 1922. Every monadic sentence is equivalent to a Boolean combination of statements of the form “region $r$ is occupied”, and the equivalence can be computed by pushing quantifiers inward until each one governs a single region. $\exists x\,(Ax \wedge Cx)$ becomes “region 5 is occupied or region 7 is occupied”; $\forall x\,(Bx \to \neg Ax)$ becomes “regions 3 and 7 are both empty”; and even the nested first clause of the sentence at the top unwinds, because the inner $\exists y$ does not mention $x$ and can be pulled out, into “if some $A$-region is occupied, then region 2 or region 3 is”.

So the lit squares of the grid are the satisfying assignments of an ordinary propositional formula, and every question about the monadic sentence is a question about that formula. The syllogisms were the special case in which the formula has two clauses; the drinker’s paradox is a formula that happens to be a tautology. Monadic first-order logic is propositional logic about which regions are occupied, and the quantifiers are only a compact way of writing it.

The same collapse appears in modal logic under another name. How many worlds a formula can need shrinks a model of a modal formula by merging worlds that the formula’s subformulas cannot tell apart — filtration — and gets a finite model for the same reason: a language that sees only finitely many distinctions cannot need infinitely many things.

Equality lets a sentence count #

The collapse argument used one fact: a formula cannot tell two things in the same region apart. Add the equality symbol and that stops being true.

“There are at least two things that are $A$ and not $B$” is a monadic sentence with equality, and it is true of the fourteen-thing model drawn with it, which has three things in the region $A$ alone. Collapse the model to one thing per region and there is only one such thing left. The sentence becomes false, and the collapse has changed a verdict — the one thing it was never supposed to do.

The repair is to collapse less. A sentence with $q$ quantifiers can count only up to $q$: it can say “at least $q$ things are here”, never “at least $q + 1$”, because it has only $q$ variables to point with. So keeping up to $q$ things in each region preserves every verdict, and the figure keeps two for a sentence with two quantifiers and gets agreement again. Monadic logic with equality is still decidable, with models of at most $q \cdot 2^n$ things. Equality buys counting, and counting to a fixed number costs a fixed factor.

Where the pictures run out #

The whole method rests on a thing being nothing but its region. A two-place predicate destroys that. “$x$ is taller than $y$” is not a property of $x$ or of $y$ but of the pair, and two things that satisfy every one-place predicate alike can differ completely in how they relate to the rest.

The damage is total, and it happens at once. With a single two-place predicate $R$, the sentence “$R$ is irreflexive and transitive, and everything has something $R$-above it” is satisfiable — the whole numbers under “less than” satisfy it — but it has no finite model at all. Any finite model would have to climb forever without repeating, which a finite set cannot do. No bound on model size exists, so no finite list of models can decide the logic — and nothing else can either. Church and Turing proved in 1936 that first-order logic is undecidable, and László Kalmár showed the same year that a single two-place predicate is already enough to make it so.

The boundary at three variables traces the line more finely. Relations are allowed there, but the number of variable names is limited, and two names keep a small-model property while three lose it. The instance that has to be guessed shows the loss from the side of proof rather than models: a universal statement can be instantiated forever without a search closing. Monadic logic sits on the safe side of both lines. Its quantifiers are as nested as anyone likes, but they can only ever ask about one thing at a time, and a thing is a region.

What the grids cannot show #

The grids are for three predicates. Everything drawn here uses eight regions and 255 occupancies. The argument for four or more predicates is the same, and four circles cannot do it shows that the diagram itself needs ellipses by then; the grid would need 65,535 squares. The claim for $n$ predicates is proved, and drawn only for $n = 3$.

The collapse is proved, and checked on examples. The induction that makes a verdict survive the collapse is stated in words above; the figures confirm it on particular models, where the sentence was evaluated in the large model and in the small one independently. A figure cannot confirm it for every model — there are infinitely many large ones — and it is the proof, not the agreement on fifteen things, that carries the weight.

And the method’s cost is not drawn. The search is doubly exponential in the number of predicates, and the smart procedures are better but not by as much as one would hope: deciding satisfiability for monadic sentences is complete for non-deterministic exponential time, a result of Harry Lewis from 1980.

Still open: whether the search can avoid guessing #

Lewis’s classification has a sharp consequence. A non-deterministic algorithm decides monadic satisfiability in exponential time — guess a small model, check it — and no algorithm does fundamentally better, since every problem solvable that way reduces to this one. Whether a deterministic algorithm can decide it in exponential time, without the guess, is therefore the question of whether $\mathrm{EXPTIME} = \mathrm{NEXPTIME}$.

That is open, and it is a scaled-up cousin of P versus NP: if deterministic and non-deterministic polynomial time were equal, the exponential classes would be equal too, so a proof that the exponential classes differ would also prove that P and NP differ — one measure of how hard it is expected to be. It is widely believed they differ. The grid of 255 squares is a guessing procedure made deterministic by trying every guess, and whether the double exponential of that brute force can be brought down to a single exponential for every monadic sentence is not known.

What can be said is where the cost comes from. The propositional form of a sentence can be far longer than the sentence, because unwinding its quantifiers into statements about regions can multiply its length, and the number of regions doubles with every predicate added. The grid shows the space every procedure is searching, and the open question is whether that space ever has to be searched square by square.

A logic that is one region wide #

Monadic logic is what first-order logic becomes when it can only ever look at one thing at a time. That is a severe restriction on what can be said — no “taller than”, no “supervises”, no order — and a complete compensation in what can be decided. Every sentence has a smallest model of at most one thing per region, the regions are finite in number, and so the models are too.

The syllogisms showed that the regions settle arguments with three classes and two premises; this essay shows that they settle every sentence about classes at all, however its quantifiers are stacked. The tree that closes reaches the same verdicts by a different road, a search for a contradiction rather than a list of models, and on monadic sentences the two roads always meet.

When a language cannot tell two things apart, a model needs only one of them. The collapse is a general move — find what the language can see, and throw away everything it cannot — and here it reduces an infinite logic to a grid of 255 squares. The same move with equality keeps a few copies instead of one, and the same move with a relation fails outright, which is the exact point at which the logic stops being a picture.