April 25, 2024
When are two things equivalent in some sense even if they are not equal? Is one thing bigger than another? Is it even possible to compare them? Relations provide a systematic way to get insight into these questions. Partial functions are a special case of relations and functions are a special case of partial functions.
Given sets X and Y a relation is a subset of the cartesian product of X and Y, R\subseteq X\times Y. We write xRy if (x,y)\in R. The domain of a relation is \operatorname{dom}R = \{x\in X\mid xRy\text{ for some }y\in Y\}. The codomain of a relation is \operatorname{cod}R = \{y\in Y\mid xRy\text{ for some }x\in X\}. The left coset of y\in Y is Ry = \{x\in X: xRy\}. The right coset of x\in X is xR = \{y\in Y: xRy\}.
Exercise. Show \operatorname{dom}R = \cup_{y\in Y} Ry and \operatorname{cod}R = \cup_{x\in X} xR.
If R\subseteq X\times Y and S\subseteq Y\times Z are relations define the composition SR\subseteq X\times Z by x(SR)z if there exists y\in Y with xRy and ySz. It may seem more natural to denote the composition by RS instead of SR, and you would be right, but that is not the usual mathematical convention.
Exercise. Show x(SR)z if and only if the intersection of the cosets xR and Sz is nonempty.
Composition is closely related to the E. F. Codd definition of the join of two relations. The join of R and S on Y is \{(x,y,z)\mid xRy\text{ and } ySz\text{ for some }y\in Y\}.
The transpose of a relation R\subseteq X\times Y is the relation R'\subseteq Y\times X defined by yR'x = xRy, x\in X, y\in Y.
Exercise. If R is a relation on X\times Y and S is a relation on Y\times Z then (SR)' = R'S'.
Composition is associative.
Exercise. If R\subseteq X\times Y, S\subseteq Y\times Z, and T\subseteq Z\times W then (TS)R = T(SR).
If X is a set then the identity relation is $I_X = I = {(x,x)xX$}.
Exercise. If R\subseteq X\times Y is a relation then RI_X = R.
Exercise. If T\subseteq W\times X is a relation then I_XT = T.
We say R is a relation on X if R\subseteq X^2 = X\times X. A relation on X is transitive if xRy and yRz implies xRz, x,y,z\in X. Transitivity is the basic notion of ordering.
Exercise. R is transitive if and only if R^2 = RR\subseteq R.
Since composition is associative, the set of all transitive relations is a semigroup.
Given a set X let I^X = \{(x,x)\mid x\in X\}. We write I for I^X if X is clear from the context.
Exercise. Show I is transitive.
Exercise. Show RI = R = IR for any relation R.
This shows the set of transitive relations on a set X is a monoid with identity I.
A relation on X is reflexive if xRx, x\in X.
Exercise. R is reflexive if and only if I\subseteq R.
A relation on X is symmetric if xRy implies yRx, x,y\in X.
Exercise. A relation on X is symmetric if and only if R' = R.
A relation that is reflexive, symmetric, and transitive is an equivalence relation.
Exercise. If R is an equivalence relation then the left and right cosets {\{xR\mid x\in X\} = \{Ry\mid y\in Y\}} are a partition of X.
This is how to mathematically model equivalent but not equal things.
Hint: A partition of a set is a collection of pairwise disjoint subsets with union equal to the set.