Questions tagged [relations]

A relation $R$ on a set $X \times Y$ (sometimes also called a relation between $X$ and $Y$) is any subset of $X\times Y$. So a relation is any set of ordered pairs $(x,y)$ such that $x\in X$ and $y \in Y$. Often we write $x\mathrel R y$ instead of $(x,y)\in R$. Sometimes we say a relation is defined on a single set $X$, but this just means that we're letting the relation $R$ be a subset of $X \times X$.

Here are some examples of relations:

• For a very abstract example of a relation, take $X = \{1,2,3\}$ and $Y = \{a,b,c,d\}$, and let $R = \{(1,b),(3,c),(3,d),(2,c),(2,d)\}$. This $R$ is a relation on $X \times Y$. Fun fact, there are $2^{12}$ distinct relations you could put on $X \times Y$.

• A function $f\colon X\to Y$ can be defined as a relation on $X \times Y$. The pairs in $X \times Y$ that are members of the relation are the input-output pairs $(x, f(x))$.

• A partial order is a relation that mimics the notion of one element being greater/less than the other. An example of a partial order is the relation $\leq$ on $\mathbf{Z} \times \mathbf{Z}$ where for two integers $n$ and $m$ we say $n \leq m$ if $n$ is less than or equal to $m$.

• Given a set $X$, let $\mathcal{P}(X)$ denote the set of all subsets of $X$. We can define a partial order $\subseteq$ on $\mathcal{P}(X)$ by saying that for two susbsets $A$ and $B$ of $X$, $A \subseteq B$ if $A$ is a subset of $B$.

• An equivalence relation is a relation that mimics the notion of two things being "equal". For example, on the set $\mathbf{Z}$ of integers let's define the relation $\equiv_{37}$ on $\mathbf{Z}\times \mathbf{Z}$ by saying $a\equiv_{37} b$ if both $a$ and $b$ give the same remainder when divided by $37$. If $a \equiv_{37} b$ we say that $a$ and $b$ are congruent modulo $37$.

• Let $T$ be the set of all triangles in the plane. An example of an equivalence relation on $T$ is the relation of two triangles being congruent.