Matpic
mathematics, in pictures
Concept

Quantifier elimination

Replacing every formula that says some value exists by an equivalent formula with no quantifier in it at all. In a theory that allows it every question reduces to checking quantifier-free facts, which is how the arithmetic of addition alone was shown to be decidable.

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

"There is an x" is a shadow: x² + ax + 1 = 0 has a solution exactly when |a| ≥ 2. A grid with a horizontal and x vertical, marking the cells the curve x squared plus a x plus one equals zero passes through; beneath it, a strip marking the columns that contain a mark, which are exactly those with a at least two in size.

A quantifier is a shadow

'There is an x such that …' asks whether a column of a grid contains a mark — which is the same as asking whether a shape casts a shadow on the axis below it. Over the real numbers every such shadow can be described without the quantifier, by polynomial inequalities: 'x² + ax + 1 = 0 has a solution' is just a² ≥ 4. Over the whole numbers the same kind of shadow can carve out the primes, and any set a computer can list.

logic · Quantifiers Whole-number points in a strip, and the shadow they cast. The lattice points satisfying 2x ≤ 5y ≤ 2x + 1 for x from 0 to 30, and their projection onto the x-axis, which repeats every 5.

Arithmetic with addition alone

Over the real numbers, a quantifier's shadow is described by inequalities. Over the whole numbers with addition and multiplication, a shadow can be any set a computer can list. In between lies arithmetic with addition and no multiplication, and there the shadows are always the same kind of thing: a finite exception, then a pattern that repeats. The whole numbers made from coins worth 6, 9 and 20 are every number from 44 on; the squares, which need multiplication, never repeat at all.

logic · Quantifiers

Named alongside it

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

QuantifierCompletenessDecidabilityDecision procedureDiscriminantFrobenius numberIncompletenessModular arithmeticPeriodicityPolynomialPresburger arithmeticPrimes

All concepts