Matpic
mathematics, in pictures
Concept

Equivalence relation

A relation that is reflexive, symmetric and transitive, and therefore cuts a set into classes with every element in exactly one. It is the standard way of declaring two things the same for a stated purpose without them being identical.

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

The classes, a selection from them, and the translates that cannot have a length. Points of several classes of the unit interval under translation by rationals, drawn one class per row, above rows showing rational translates of a selection that never overlap.

A set that has no size at all

Slide the unit interval along itself by every rational and the points fall into classes. Choose one point from each and the resulting set has no length — not zero, not positive, none: countably many disjoint copies of it would have total length nought or infinity, and the union needs something in between.

analysis · Measure 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 The same loop, seen from two places. An annulus with two marked points and a loop based at the first. Two paths join the points, differing by a full turn round the hole, and each carries the loop to a loop based at the second point.

The group a space has at a point

The loops of a space form a group once a starting point is fixed, and the fixing looks like an arbitrary choice that ought to be removable. It is removable, but only up to conjugation, and the residue is exactly what makes a non-commutative fundamental group harder to state than to compute.

topology · Homotopy A chain of 18 worlds, and the 3 the formulas can tell apart. A row of 18 circles for the worlds of the model, shaded by which of the 3 classes each falls into, above the quotient model's 3 worlds with the arrows the collapse gives them.

How many worlds a formula can need

A modal formula can be true in a model with infinitely many worlds. It can also be true in a small one — and the small one is built from the large one by throwing away every distinction the formula was never able to make.

logic · Modal logic A subword can be checked with one quantifier block; a factor cannot. Subword aba: monoid 7, J-trivial, degree 3; factor aba: monoid 12, aperiodic, not J-trivial; witness abab / abba.

One block of quantifiers, read off an algebra

Which properties of words can be stated with existential quantifiers alone — 'there are positions, in this order, carrying these letters' — and Boolean combinations of such statements? Imre Simon answered in 1975: exactly those whose syntactic monoid is J-trivial. Of the 57,068 languages that automata of up to four states recognise, 848 pass the test, and every one of them is decided by which words of length three or less it contains as scattered subwords.

logic · Ehrenfeucht–Fraïssé games Fifteen logics from five axioms. K: rank 0, covered by D, KB, K4, K5; D: rank 1, covered by T, KDB, D4, D5; T: rank 2, covered by B, S4; KB: rank 1, covered by KDB, KB5; KDB: rank 2, covered by B; B: rank 3, covered by S5; K4: rank 1, covered by D4, K45; D4: rank 2, covered by S4, KD45; S4: rank 3, covered by S5; KB5: rank 3, covered by S5; S5: rank 4, covered by nothing; K5: rank 1, covered by D5, K45; D5: rank 2, covered by KD45; K45: rank 2, covered by KB5, KD45; KD45: rank 3, covered by S5.

Five axioms and fifteen logics

Five familiar axioms of modal logic can be added to the basic system in thirty-two combinations. Only fifteen different logics come out, because the axioms are properties of arrows between worlds and some properties force others. Checking every frame with up to four worlds finds the fifteen, the order among them, and the small pictures that tell each from its neighbours.

logic · Modal logic

Named alongside it

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

Exhaustive searchModal logicBisimulationCompletenessDecision procedureExpressive powerKripke modelAccessibilityAssociativityAxiomAxiom of choiceBase point

All concepts