Matpic
mathematics, in pictures
Concept

Quantifier order

The difference between one thing serving every case and each case having its own, which swapping two quantifiers changes. It is the difference between continuity and uniform continuity, and between a bound existing and a single bound working everywhere.

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

j is one more than i, counting round — as a grid, with both quantifier readings. A grid of marks for a relation, with the row and column facts the two quantifier orders ask about.

Every row, or one column

For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.

logic · Quantifiers Every ranking 4 could submit, and the 4 that pay. One participant's true ranking, a cell for every ranking they could submit instead labelled with the partner it returns, the profitable misreports listed, and the same search run on the proposing side finding none.

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

applied · Stable matching 3 rounds on chains of 4 and 5. Two chains of dots with pebbles placed in turn, and the transcript of a play: Spoiler picks an element of one chain, Duplicator answers in the other, and the pebbles must keep the same order.

A game that decides what can be said

Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.

logic · Ehrenfeucht–Fraïssé games Six sentences from two quantifiers, and which imply which. A diagram of the six sentences that can be built from two quantifiers and a relation, arranged from strongest to weakest with arrows for implication, each labelled with how many of the 512 relations on three points satisfy it.

Six sentences from two quantifiers

One relation, two variables, 'for every' and 'there is': there are eight ways to arrange them and six different sentences come out. Which of them imply which is a small, complete diagram, found by checking all 512 relations on three points — and the diagram crosses over in the middle, which is where every confusion about the order of quantifiers lives.

logic · Quantifiers

Named alongside it

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

QuantifierCounterexampleExhaustive searchNegationPredicate logicRelationBlocking pairDecision procedureDeferred acceptanceDualityElementary equivalenceExpressive power

All concepts