Relation

A relation on a set is a condition that may or may not hold true between two elements of that set.

In particular, a binary relation \(R\) between two sets \(A\) and \(B\) is a subset of the Cartesian product \(A \times B.\) It contains all ordered pairs \((a, b)\), where \(a \in A\) and \(b \in B\), such that \(aRb\), which is read as "a is related to b." It's possible for the two sets \(A\) and \(B\) to be the same set. If that's the case, the relation is said to be "on" that set.

What we know as a function is really a special type of relation between two sets called the domain and target, where each element of the domain is related to exactly one element of the target.

Arrow diagram

For a relation \(R\) on a set \(A\), if \(xRy\), then an arrow will be drawn from \(x \in A\) to \(y \in A.\) If \(yRx\), another arrow will point in the opposite direction.

If an element is related to itself, you can visualize this by drawing an arrow that leaves the element but then loops back to point at it. This is called a self-loop.

Matrix representation

Relations between two sets can also be visualized as a matrix, where each row corresponds to one element of the first set, and each column corresponds to one element of the second set. If two elements are related, their overlapping cell will hold \(1\), otherwise, it'll hold \(0.\)

Let \(A = \set{2, 7, 5, 4}\) and \(B = \set{1, 4, 5}.\) Define a relation \(R\) between \(A\) and \(B\) where \(aRb\) if and only if \(a \in A\) and \(b \in B\) have the same parity. Here's the matrix representation of \(R\):

Properties

Properties of relations include reflexivity, anti-reflexivity, symmetry, anti-symmetry, and transitivity. Any of these properties can be disproven with a single counterexample.