a relation

A relation tells you, for any two things, whether they are connected in some chosen way. 'Is a sibling of', 'is less than', 'is the same colour as' — each is a relation, a rule that for each pair of items answers yes (they are related) or no (they are not). The trick of mathematics is to make this exact by simply listing all the pairs that count as 'yes'.

Formally, a binary relation R on sets A and B is just a subset of the Cartesian product A × B: it is a set of ordered pairs. We write x R y, or (x, y) ∈ R, to mean 'x is related to y'. For the relation 'less than' on {1, 2, 3}, the pairs that hold are (1,2), (1,3), (2,3), so as a set the relation is {(1,2), (1,3), (2,3)}. When A and B are the same set we call it a relation on A, and we can describe useful properties: a relation is reflexive if every element relates to itself (x R x for all x), symmetric if x R y always forces y R x, and transitive if x R y and y R z together force x R z.

Relations are the quiet workhorse of automata theory. A nondeterministic machine's transitions form a relation rather than a function (one input can relate to several next states). The 'one step of computation' of a Turing machine or pushdown automaton is captured by a move relation between configurations. And the three properties just named — reflexive, symmetric, transitive — combine into the single most important relation in the whole subject, the equivalence relation, defined next.