A binary relation from a set A to a set B is a subset $R \subseteq A \times B$. It is a collection of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. When $(a, b) \in R$, we say a is related to b by R, written $a \mathrel{R} b$.

A relation is more general than a function. A function requires that each element of A appears in exactly one pair. A relation has no such constraint. An element of A may be related to many elements of B, to one, or to none. An element of B may be related to by many elements of A, one, or none.

A relation on a single set — a subset $R \subseteq A \times A$ — is called a relation on A. Relations on a single set can have properties that relations between two different sets cannot:

• Reflexive: every element is related to itself. $\forall a \in A : a \mathrel{R} a$.
• Symmetric: if a is related to b then b is related to a. $a \mathrel{R} b \Rightarrow b \mathrel{R} a$.
• Antisymmetric: if a is related to b and b is related to a, then they are the same. $a \mathrel{R} b \wedge b \mathrel{R} a \Rightarrow a = b$.
• Transitive: if a is related to b and b is related to c, then a is related to c. $a \mathrel{R} b \wedge b \mathrel{R} c \Rightarrow a \mathrel{R} c$.

These properties combine into named structures. A relation that is reflexive, symmetric, and transitive is an equivalence relation — it partitions A into classes of equivalent elements. A relation that is reflexive, antisymmetric, and transitive is a partial order.

The identity relation on A is $\{(a, a) : a \in A\}$ — every element related only to itself. The empty relation is $\emptyset$ — no element related to any other. The total relation is $A \times A$ — every element related to every other.

Relations compose. If $R \subseteq A \times B$ and $S \subseteq B \times C$, the composition $S \circ R \subseteq A \times C$ contains $(a, c)$ whenever there exists $b \in B$ with $(a, b) \in R$ and $(b, c) \in S$. Composition is associative. The identity relation is neutral under composition.

In the category Set, a relation from A to B is equivalently a function $A \times B \to \{0, 1\}$ — a characteristic function that says yes or no for each pair. In a topos, this generalizes: a relation is a morphism $A \times B \to \Omega$ into the subobject classifier, where $\Omega$ may have more truth values than just true and false.