No way to hand out true and false

Every logic in this sequence of essays has so far kept one thing fixed while changing others. The middle that is not excluded dropped the law that every statement is true or false and found models made of open sets. No table of truth values is enough asked how many truth values a logic needs. A contradiction that stays where it is added a value meaning both true and false and stopped a contradiction from spreading. In each case the logic was invented first and its models found afterwards, and in each case the models existed: some assignment of values to statements made the logic’s laws hold.

There is one non-classical logic that was not invented but found, in the mathematics of a physical theory, and its defining property is the opposite. Its statements cannot be assigned the values true and false in any consistent way at all. The statements are the yes-or-no questions that can be asked of a quantum system, and the theorem that they have no truth values was proved by Simon Kochen and Ernst Specker in 1967. Its first proof used 117 directions in three-dimensional space and a long geometric argument. The proof drawn here, found by Adán Cabello, José Estebaranz and Guillermo García-Alcaine in 1996, uses eighteen directions in four dimensions, and its core is the fact that nine is an odd number.

Propositions as subspaces #

In quantum mechanics the state of a system is a vector in a space with complex coordinates, and the yes-or-no questions that can be asked of it — is the particle’s spin up along this axis, is the photon polarised horizontally — correspond to subspaces of that space. The answer is certainly yes when the state lies in the subspace, certainly no when it lies in the subspace’s orthogonal complement, and otherwise it is yes with a probability given by the squared length of the state’s shadow on the subspace. A complete measurement is a choice of orthonormal basis: it asks, in effect, which of the basis directions the system is found along, and exactly one answer comes back.

Garrett Birkhoff and John von Neumann proposed in 1936 that these subspaces be treated as the propositions of a logic. The meet of two propositions is their intersection, the subspace of states for which both are certain. The join is the span, the smallest subspace containing both. The negation of a proposition is its orthogonal complement. The result is a lattice with a complement, like the lattice of subsets of a set that underlies classical logic — but with one law missing.

The missing law is distribution. Take three different lines $a$, $b$ and $c$ through the origin of a plane. Any two different lines span the whole plane and meet only at the origin, so $b \vee c$ is the plane, and $a \wedge (b \vee c)$ is $a$ itself. But $a \wedge b$ and $a \wedge c$ are both the origin, and so is their join. In the logic of sets, and in every Boolean algebra, $a \wedge (b \vee c)$ and $(a \wedge b) \vee (a \wedge c)$ are always equal; here they differ as much as two propositions can. Physically, the failure says that knowing a photon is polarised along $a$, and that every photon is polarised either along $b$ or along $c$ in the sense that those two directions together span the space, does not make it polarised along $b$ or along $c$ individually.

What survives in place of distribution is a weaker law, orthomodularity: if $a$ is contained in $b$, then $b$ is the join of $a$ with the part of $b$ orthogonal to $a$. Every Boolean algebra satisfies it, and so do the subspaces of any space of states. Not one step but a continuum found uncountably many logics between the constructive and the classical, each a class of lattices satisfying distribution and more; the orthomodular lattices are a different branch altogether, lattices in which distribution fails and the complement is perfectly well behaved.

A logic with no two-valued model #

A lattice failing to be distributive does not by itself rule out truth values. Any Boolean algebra, however large, can be mapped onto the two values true and false in a way that respects “and”, “or” and “not”; that is the classical completeness theorem in algebraic form. For the quantum propositions the question is whether a weaker kind of map exists, one that only respects the operations within each complete measurement. Inside one orthonormal basis everything commutes and the propositions do form a Boolean algebra; across different bases they do not. So the natural minimal demand is a valuation: an assignment of true or false to every direction such that every orthonormal basis has exactly one true member, the one the measurement would find.

In two dimensions such a valuation exists trivially. Each basis is a pair of perpendicular lines, different bases share no lines, and choosing one line from each pair independently satisfies every basis. In three or more dimensions bases overlap — two different bases can share a direction — and the choices constrain each other. Kochen and Specker’s theorem is that, from dimension three on, the constraints cannot all be met. There is no valuation.

The proof in four dimensions is the hero figure. Cabello and his colleagues listed eighteen directions, each a vector with entries 0, 1 or $-1$, and nine sets of four that are orthonormal bases once the vectors are scaled to unit length. The arrangement has one special property, checked in the figure by computation: every direction lies in exactly two of the nine bases. Draw the bases as nine points and each direction as an edge joining the two bases that contain it. Every point gets four edges, one for each direction in its basis, and the graph has eighteen edges in all.

A valuation would call some directions true, and the condition that each basis has exactly one true direction says that the true edges touch every point exactly once. Such a set of edges is a perfect matching, and a perfect matching pairs the points off, so the number of points must be even. There are nine. The argument can also be written as a count: summing the number of true directions over the nine bases gives $9 \times 1 = 9$, while each true direction is counted once for each basis it lies in, twice, so the sum is even. Nine is not even. No valuation exists.

The parity argument checked by brute force #

The argument is short enough to be checked completely. Eighteen directions can be called true or false in $2^{18} = 262{,}144$ ways, and for each of them it takes a moment to count how many of the nine bases end up with exactly one true direction.

The census confirms the parity argument and shows how far a random assignment is from satisfying it. Most assignments satisfy between one and three bases; the distribution falls steeply from there, to 5,748 assignments satisfying six bases, 792 satisfying seven and 234 satisfying eight. The bar at nine is empty. No ingenuity could fill it: the obstruction is counting, and the count does not depend on which directions are chosen.

The 234 near-solutions are worth examining in their own right, because they show the obstruction in a second way. If eight bases are satisfied, which basis fails, and how?

Each of the nine bases is the odd one out in exactly 26 near-solutions, so the failure can be put anywhere: there is no particular basis to blame, and removing any one of the nine makes the remaining eight satisfiable. In the language of the graph, deleting any point leaves eight, and eight points have perfect matchings. But the failure always has the same shape. The basis left over holds zero, two or four true directions, never one and never three. The reason is the same count: the eight satisfied bases contribute eight true memberships, an even number, the total over all nine must be even because every true direction is counted twice, and so the ninth basis must contribute an even number as well. The contradiction can be moved from basis to basis, but its parity cannot be changed.

This is the shape of a contradiction that is only a sum, which put a variable on every edge of a graph and asked every vertex for a given parity of true edges. There, the demands added up to an odd number while every edge was counted twice; here, the demands are “exactly one” at nine vertices, which is a stronger condition than “odd”, and the sum is again nine against twice something. Kochen and Specker’s theorem in Cabello’s form is a Tseitin formula with a quantum mechanical origin, and the same proof that no assignment satisfies it — add everything up — is the proof that quantum propositions have no truth values. It is also, at bottom, the observation Euler made about the seven bridges: the degrees of a graph add up to twice the number of edges, so something counted at the vertices that must be odd in total cannot be.

What a state does instead #

Quantum mechanics does assign the propositions something consistent. It assigns probabilities. A state vector $\psi$ gives each direction $v$ the probability $|\langle v, \psi\rangle|^2 / (|v|^2 |\psi|^2)$ that a measurement in any basis containing $v$ finds the system along $v$. That probability does not depend on which basis $v$ is measured in — the other three directions of the basis do not enter it — and the four probabilities of any orthonormal basis add up to one.

The figure computes this for one state on Cabello’s eighteen directions. Each direction appears in two columns, with the same probability in both, and every column sums to one. What no assignment of 0 and 1 could do, an assignment of fractions does without strain: it is a valuation in which “exactly one true direction per basis” has been softened to “probabilities adding up to one per basis”. The parity argument has nothing to grip on, because 9 is a perfectly good total when the summands are fractions.

Andrew Gleason proved in 1957 that this is the only way to do it. In three or more dimensions, every assignment of non-negative numbers to the directions that adds up to one on every orthonormal basis comes from a quantum state, or from a probabilistic mixture of states. Such assignments are continuous in the direction, and a continuous function on the sphere of directions cannot jump between 0 and 1, so none of them is a valuation. John Bell noticed in 1966 that this already implies a form of the Kochen–Specker theorem, and that the point of the theorem is not that measurements have random outcomes but that their outcomes cannot be thought of as pre-existing values independent of which other measurements are made alongside them. A property whose value would have to depend on the measurement context is called contextual, and the theorem says quantum mechanics is contextual in dimension three and up.

Nine measurements whose products disagree #

There is a second form of the same argument, which trades directions for measurements with values $\pm 1$ and uses multiplication in place of counting. It was found independently by David Mermin and Asher Peres in 1990.

Each cell of the square is a measurement on a pair of two-state systems, a tensor product of two Pauli matrices, with outcomes $+1$ and $-1$. The three measurements in any row or column commute with one another and can be made together. Multiplying the three matrices in each row and column — which the figure does, as $4 \times 4$ complex matrices — gives the identity for every row and for the first two columns, and minus the identity for the third column. The products are the tell-tale: any values found together must multiply to the eigenvalue of their product, so the values in each row multiply to $+1$, those in the first two columns to $+1$, and those in the third column to $-1$.

Suppose each of the nine measurements had a value of its own, $+1$ or $-1$, regardless of which row or column it was measured with. Multiply all nine values together. Grouped by rows the product is $(+1)^3 = +1$; grouped by columns it is $(+1)(+1)(-1) = -1$. It cannot be both. The figure’s census of all 512 assignments shows the same thing by exhaustion, and shows it with the same parity structure as before. The number of conditions met is always odd — one, three or five — because changing any single value flips exactly one row product and one column product, two conditions at once, and the all-plus assignment meets five. Ninety-six assignments meet five, and none meets six. The non-commuting of the Pauli matrices, which five-eighths of the pairs, and no more measured as a group-theoretic property, is what puts the minus sign in exactly one product.

The square has been realised in laboratories, with trapped ions and with neutrons among other systems, and the measured products come out as quantum mechanics predicts: the rows and two columns near $+1$, the last column near $-1$. Since no assignment of fixed values can reproduce that, the experiments rule out every theory in which the nine quantities have values independent of their context.

Where this logic sits among the others #

Seen from the logics earlier in this sequence, the quantum propositions are strange in a particular direction. Refutable in something small showed that a constructive non-theorem fails in some finite algebra, and a contradiction that stays where it is gave the logic of paradox a three-valued table in which every classical law survives. In both cases the non-classical logic has more models than classical logic, not fewer: a statement that classical logic decides is merely left open. The quantum propositions have fewer: the two-valued models that every Boolean algebra has are gone entirely, and only the continuous, probabilistic ones Gleason classified remain.

Kochen and Specker framed their theorem in exactly these terms. They described the propositions as a partial Boolean algebra — a family of Boolean algebras, one for each complete measurement, glued along their overlaps — and proved that this structure, unlike every Boolean algebra, has no homomorphism onto true and false. The eighteen directions are a finite piece of that structure on which the failure can already be seen. A finite piece exists in every dimension from three up, and in four dimensions the computer searches of Mladen Pavičić and his colleagues in 2005 found no set of directions smaller than eighteen that does the job.

Still open: the smallest proof in three dimensions #

In three dimensions, the setting of Kochen and Specker’s original proof, the smallest known set of directions has come down from 117 to Asher Peres’s 33 in 1991 and to a set of 31 found by John Conway and Simon Kochen. Whether 31 is the true minimum has not been settled. Lower bounds come from exhaustive search: every candidate arrangement of directions and bases is a finite set of “exactly one per basis” constraints, and showing that none of the small ones is contradictory means deciding a great many instances of satisfiability. Recent searches have handed exactly that work to satisfiability solvers, and the lower bound has been pushed into the twenties, still short of 31.

The three-dimensional search is hard partly because the shortcut used above is not available there, and the reason takes one line. A parity proof needs every direction to lie in an even number of bases and the number of bases to be odd. Count memberships two ways: each of $B$ bases has three directions, so there are $3B$ memberships, and each direction contributes an even number of them, so $3B$ is even and $B$ is even too. In any odd dimension the same count forbids a parity proof, which is why Cabello’s argument needs four. In three dimensions the impossibility has to be shown by genuine case analysis — directions forced true, others forced false, until some basis is left with none — and a short proof of that kind is exactly what a contradiction that is only a sum showed cannot be guaranteed when the contradiction is not a simple sum. How short the shortest three-dimensional proof can be is open, and it is a question about a logic whose two-valued models were taken away by the arithmetic of a physical theory.