Matpic
mathematics, in pictures
Concept

Expressive power

What a language can and cannot distinguish, measured by the equivalence between structures it respects rather than by a list of what it can say. Naming that equivalence settles every question of the form *can this be expressed* at once.

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

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 · Ef games Two models the modal language cannot separate, and two it can. Four Kripke models in two pairs: the upper pair joined by a bisimulation and agreeing on every formula, the lower pair separated by a formula found by search.

Two diagrams the language cannot tell apart

A modal formula sees a diagram of worlds and arrows through a very narrow window. Exactly how narrow is settled by a game: where one player can answer every move, no formula whatever separates the two starting worlds, however different the diagrams look.

logic · Modal logic Axioms, the conditions on the arrows they answer to, and the one that answers to none. A table of modal axioms with the property of the accessibility relation each corresponds to, every row decided by sweeping all relations on up to four worlds.

The axiom with no property of the arrows

The first rung matched each axiom to a condition on the arrows by hand. There is a recipe that does it for a whole class of axioms, and there is an axiom the recipe cannot reach — not because nobody has looked, but because no condition on the arrows defines it at all.

logic · Modal logic

Named alongside it

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

Exhaustive searchAccessibilityDecision procedureKripke modelModal logicAxiomBisimulationDefinabilityElementary equivalenceEquivalence relationFrameModel

All concepts