Matpic
mathematics, in pictures
Concept

Bisimulation

A relation between two labelled graphs matching worlds that carry the same labels and can answer each other's moves along arrows, forever. Two worlds related by one satisfy exactly the same modal formulas, of every depth.

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

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 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

Named alongside it

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

Decision procedureEquivalence relationKripke modelModal logicAccessibilityCompletenessExhaustive searchExpressive powerFinite model propertyQuotient

All concepts