Andrew Cooper

[callout headingicon=”noicon” textalign=”textleft” url=”https://www.youtube.com/watch?v=Ws5klxbI87I&app=desktop” type=”basic”]I am he
as you are he
as you are me
and we are all together.

John Lennon and Paul McCartney, I Am the Walrus[/callout]

You’ve actually dealt with modular arithmetic for most of your life: the clock face represents arithmetic with modulus 12. If you’ve ever served in the military or listened to the BBC World Service, you’re familiar with arithmetic modulo 24 as well.

When we deal with time, we feel free to use the symbol $1:00$ to denote any time that is a multiple of 12 hours away from a particular 1 am or 1 pm. Notice that transitivity means we don’t actually care  which particular reference 1 am or 1 pm we choose — but if you’re worried about it, we could follow Bishop Ussher and say that our archetypal $1:00$ is 1 am on Sunday, 23 October 4004 BC. It is very useful to have a symbol for all of the one-o’clocks, a symbol for all of the two-o’clocks, etc., so that we can write things like

Seven hours after $8:00$ is $3:00$.

The following definition makes this idea precise.

Definition. Let $R$ be an equivalence relation on the set $A$, and let $a\in A$. The equivalence class of $a$ under the equivalence $R$ is the set \begin{equation*} [a]_R=\left\{x\in A\middle| x\operatorname{R}a\right\} \end{equation*} of all elements of $A$ which are equivalent to $a$.

E.g. Consider the relation on $\mathbb{R}$ given by $x\operatorname{R}y$ if $x^2=y^2$. Then $[0]_R=\{0\}$, $[1]_R=\{1,-1\}$, etc.

E.g. Consider the equivalence relation $C$ on $\mathbb{R}\times\mathbb{R}$ given by $(x,y)\operatorname{C}(z,w)$ if $x^2+y^2=z^2+w^2$. Then

\begin{align*} [(0,0)]_C&=\left\{(z,w)\middle|z^2+w^2=0\right\}=\{(0,0)\}\\ [(0,1)]_C&=\left\{(z,w)\middle|z^2+w^2=1\right\}\\ &=\text{circle of radius }1\text{ at the origin}\\ [(1,1)]_C&=\left\{(z,w)\middle|z^2+w^2=2\right\}\\ &=\text{circle of radius }\sqrt{2}\text{ at the origin} \end{align*}

and it’s easy to see that all other equivalence classes will be circles centered at the origin. Note that we have $[(0,1)]=[(1,0)]$.

Definition. Given an equivalence relation $R$ on $A$, the set of all equivalence classes is called the {\em quotient of $A$ by $R$}. We write \begin{equation*} A_{/R}=\left\{[a]_R\middle|a\in A\right\} \end{equation*}

Notice that the quotient of $A$ by an equivalence relation is a set of sets of elements of $A$.

E.g. Consider the relation on $\mathbb{R}$ given by $x\operatorname{R}y$ if $x^2=y^2$. Then $\mathbb{R}_{/R}=\left\{\{a,-a\}\middle|\ a\in\mathbb{R}\right\}$

E.g.  If $C$ is the equivalence relation on $\mathbb{R}\times\mathbb{R}$ given by $(x,y)\operatorname{C}(z,w)$ if $x^2+y^2=z^2+w^2$, then $\mathbb{R}\times\mathbb{R}_{/C}$ is the set of circles centered at the origin.

E.g. $\mathbb{Z}_{/\equiv_{12}}$ has 12 elements:

\begin{equation*} \begin{aligned}

\mathbb{Z}_{/\equiv_{12}}=&\left\{\{0,12,24,\ldots\},\{1,13,25,\ldots\},\{2,14,26,\ldots\}, \right.\\

&\{3,15,27,\ldots\},\{4,16,28,\ldots\},\{5,17,29,\ldots\},\\

&\{6,18,30,\ldots\},\{7,19,31,\ldots\},\{8,20,32,\ldots\},\\

&\left.\{9,21,33,\ldots\},\{10,22,34,\ldots\},\{11,23,35,\ldots\}\right\}\\

\end{aligned} \end{equation*}

A convenient way to represent them is $[0]$, $[1]$, $[2]$, etc. Notice that the mathematical convention is to start at 0 and go up to 11, which is different from how clocks are numbered.

Theorem. Let $R$ be an equivalence relation on $A$. Let $a,b\in A$. $[a]_R=[b]_R$ iff $a\operatorname{R} b$.

Proof. Suppose $[a]_R=[b]_R$. Since $a\in[a]_R$, we have $a\in[b]_R$, so by definition of $[b]_R$, we have $a\operatorname{R} b$.

Suppose $a\operatorname{R}b$. We’ll show $[a]_R\subseteq[b]_R$. Let $c\in[a]_R$. Then $c\operatorname{R}a$. Since $R$ is transitive, we have $c\operatorname{R}b$. Since $R$ is symmetric, this means $b\operatorname{R}c$, i.e. $c\in[b]_R$.

The proof that $[b]_R\subseteq[a]_R$ is similar. $\Box$.

Theorem. $\mathbb{Z}_{/\equiv_p}$ consists of exactly the elements $[0]$, $[1]$, \ldots, $[p-1]$.

Proof. We are asked to show set equality. It is clear that each $[k]$ for $0\leq k<p$ is an equivalence class, so we have one set inclusion.

To get the other set inclusion, suppose $S\in \mathbb{Z}_{/\equiv_p}$ is an equivalence class. Then there is some $k\in \mathbb{Z}$ with $[k]=S$. We apply the Division Algorithm to write

\begin{equation*}

k=q\cdot p + r

\end{equation*}

where $0\leq r<p$. Then $k-r$ is a multiple of $p$, so $k\equiv_pr$. Thus $S=[k]=[r]$, and since $0\leq r<p$, we have shown that $S$ is on our list of equivalence classes. $\Box$.

An important property of equivalence classes is they “cut up” the underlying set:

Theorem. Let $A$ be a set and $R$ be an equivalence relation on $A$. Then:

1. No equivalence class is empty.
2. The equivalence classes cover $A$; that is, $A\subseteq \displaystyle\bigcup_{a\in A}[a]_R$.
3. Equivalence classes do not overlap.

Proof. The first two are fairly straightforward from reflexivity.

1. Any equivalence class is $[x]_R$ for some $x\in A$. Since $R$ is reflexive, $x\operatorname{R}x$, i.e. $x\in[x]_R$. So $[x]_R$ is nonempty.
2. Let $x\in A$. We need to show that $x\in\displaystyle\bigcup_{a\in A}[a]_R$. That is, we need to find some $a\in A$ for which $x\in[a]_R$. Using $a=x$ and the observation above, we have $x\in[x]_R$.

The third clause is trickier, mostly because we need to understand what it means. Consider the case of $A=\mathbb{Z}$, $R=\equiv_{12}$. Then $[3]_{\equiv 12}$ and $[15]_{\equiv 12}$ certainly overlap–they both contain $-9$, for example. So if we take “equivalence classes do not overlap” too literally it cannot be true.

But notice that $[3]_{\equiv 12}$ and $[15]_{\equiv 12}$ not only overlap, but in fact are equal. So we’ll amend

equivalence classes do not overlap

to

distinct equivalence classes do not overlap

that is,

Theorem. If $[x]_R\neq [y]_R$ then $[x]_R\cap[y]_R=\varnothing$.

Proof. We’ll prove the contrapositive: if $[x]_R\cap[y]_R\neq\varnothing$, then $[x]_R=[y]_R$.

Assume $[x]_R\cap[y]_R$ is nonempty. Then there is some $z\in[x]_R\cap[y]_R$. So $z\operatorname{R}x$ and $z\operatorname{R}y$.

Since $R$ is symmetric, $x\operatorname{R}z$.

Since $R$ is transitive, $x\operatorname{R} y$. So $[x]_R=[y]_R$. $\Box$.

This theorem shows, for example, that there are in no redundancies on the list $[0]$, $[1]$, \ldots, $[p-1]$ of equivalence classes modulo $p$.

An example from arithmetic: rational numbers

Exercise. Consider the relation on $\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)$ given by: $(m,n)\operatorname{CP}(r,s)$ if $ms=nr$. Show that $CP$ is an equivalence relation. Do not use fractions in your proof.

What are the equivalence classes under the relation $CP$?

Claim. $[(0,1)]$ is the set of all pairs of the form $(0,k)$.

Proof. First we show that every $(0,k)\in[(0,1)]$. This is equivalent to showing $(0,k)\operatorname{CP}(0,1)$. But by definition of $CP$, all we need to show is $0\cdot 1 = k\cdot 0$–which is clear since both sides are $0$.

Now we show that if $(m,n)\in[(0,1)]$, then it must be the case that $m=0$. $(m,n)\in[(0,1)]$ means that $(m,n)\operatorname{CP}(0,1)$, i.e. that $m=m\cdot 1=n\cdot 0=0$. $\Box$.

Exercise. Show that $[(1,1)]$ is the set of all pairs of the form $(k,k)$.

We write $\frac{m}{n}$ for the equivalence class $[(m,n)]_{CP}$, and we define:

Definition. The set of rational numbers $\mathbb{Q}$ is $\left(\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)\right)_{/CP}$. That is, a rational number is an equivalence class of pairs of integers.

[callout headingicon=”noicon” textalign=”textleft” type=”basic”]All men are created equal.

Thomas Jefferson, Declaration of Independence

I don’t hold with equality in all things, just equality before the law, nothing more.

character of Rep. Thaddeus Stevens in the film Lincoln

[/callout]

We ordinarily are completely comfortable writing things like $$\frac{1}{2}=\frac{2}{4}=\frac{500}{1000}$$ The symbols $\frac{3}{2}$ and $\frac{1500}{1000}$, though, are definitely not the same. One of them, for example, has four digits in the denominator, whereas the other has only one digit in the denominator. So in what sense is it the case that these three symbols are the same? Intuitively, they represent the same thing.

Children are usually introduced to fractions as being parts of a whole. What is half a pizza? It’s what happens when you divide one pizza into two parts. Then we think of fractions like $\frac{2}{4}$ as either: one piece, if you divide two pizzas into four parts, or two pieces if you divide one pizza into four parts. But these are manifestly not the same thing! Two halves of a Ming vase are not the same as a whole Ming vase, and if you ordered a pizza at the pizza shop, you’d be very upset when they brought out a pizza in a million little pieces.

Yet we write $\frac{2}{2}=1=\frac{1000000}{1000000}$ and don’t really think about it. We’re choosing to ignore some differences between two things, and treat them like they’re equal. Like Thaddeus Stevens, we are not asserting equality in all things, only equality before the law (of fractions).

An equivalence relation is a way of formalizing this process of picking what to ignore and what to pay attention to.

Equality

The following properties are true for the identity relation $I$ (we usually write $(x,y)\in I$ as $x=y$):

• $I$ is {\em reflexive}: for any object $x$, $x=x$ (or $(x,x)\in I$).
• $I$ is {\em symmetric}: for any objects $x$ and $y$, if $x=y$ then it must be the case that $y=x$.
• $I$ is {\em transitive}: for any objects $x$, $y$, and $z$, if $x=y$ and $y=z$ then it must be the case that $x=z$.

Equality also has the replacement property: if $A=B$, then any occurrence of $A$ can be replaced by $B$ without changing the meaning. So for example, when we write $1+1=2$, we know that $\sin(1+1)=0$ is false, because $\sin(2)=0$ is false.

Notice that Thomas Jefferson’s claim that all men are created equal does not have this property. Michael Jackson is a man, and Bill Nye is a man, so if all men are equal, we should be able to replace any occurrence of “Michael Jackson” with “Bill Nye” without loss of meaning. It’s true that

Michael Jackson is the King of Pop.

But we can’t say that this means

Bill Nye is the King of Pop.

So it seems like we at least have to give up the replacement property, if we want to make sense of notions like equal before the law.

Equivalence

We want to treat different things as though they were the same, so we need the properties of equality. This motivates the following definition:

Definition. A relation $R$ on the set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive, that is, if:

• $\forall x\in A, x\operatorname{R}x$
• $\forall x,y\in A,\left(x\operatorname{R}y\Leftrightarrow y\operatorname{R}x\right)$
• $\forall x,y,z\in A, \left((x\operatorname{R}y\wedge y\operatorname{R}z)\Rightarrow x\operatorname{R}z\right)$

E.g. Equality is an equivalence relation.

E.g. Consider the relation $R$ on $\mathbb{R}$ given by $x \operatorname{R} y$ iff $x^2=y^2$. We’ll show $R$ is an equivalence relation.

Proof. First show that $R$ is reflexive. Let $x$ be a real number. Then $x^2=x^2$, so $x \operatorname{R}x$.

Now show that $R$ is symmetric. Suppose $x$ and $y$ are real numbers with $x \operatorname{R} y$. Then $x^2=y^2$, so $y^2=x^2$, so $y\operatorname{R} x$.

Finally, show that $R$ is transitive. Suppose $x$, $y$, and $z$ are real numbers with $x\operatorname{R} y$ and $y\operatorname{R}z$. Then $x^2=y^2$ and $y^2=z^2$, so $x^2=z^2$, i.e. $x\operatorname{R} z$. $\Box$

In fact, it’s easy to come up with equivalence relation on any set $A$, given a function $f$: define $x\operatorname{R}_f y$ to mean $f(x)=f(y)$.

E.g. Let $C$ be the relation on $\mathbb{R}\times\mathbb{R}$ given by: $(x,y) \operatorname{C} (z,w)$ iff $x^2+y^2=z^2+w^2$. Then $C$ is an equivalence relation.

E.g. Let $T$ be the relation on $\mathbb{Z}$ given by $x \operatorname{T} y$ if $x$ and $y$ have the same parity (i.e. are either both even or are both odd). Then $T$ is an equivalence relation.

An example from algebra: modular arithmetic

The following generalizes the previous example $T$:

Definition. Let $p$ be an integer. We say $m$  is equal to $n$ modulo $p$ if $m-n$ is a multiple of $p$, i.e. if there is $k\in\mathbb{Z}$ with $m-n=kp$.

Theorem. Equality modulo $p$ is an equivalence relation.

Proof.  First we’ll show that equality modulo $p$ is reflexive. Let $m\in \mathbb{Z}$. Then $m-m=0=0\cdot p$, so $m$ is equal to $m$ modulo $p$.

Now we’ll show that equality modulo $p$ is symmetric. Suppose $m$ is equal to $n$ modulo $p$. Then there is some $k$ with $m-n=kp$. So $n-m=(-k)\cdot p$, which shows that $n-m$ is a multiple of $p$, hence $n$ is equal to $m$ modulo $p$.

Now we’ll show that equality modulo $p$ is transitive. Suppose $m$ is equal to $n$ modulo $p$ and $n$ is equal to $\ell$ modulo $p$. Consider $$m-\ell= m-n + n-\ell$$

so $m-\ell$ is the sum of two multiples of $p$, hence a multiple of $p$ itself. Thus $m$ is equal to $\ell$ modulo $p$. $\Box$.

It turns out that the arithmetic of $\mathbb{Z}$–that is, addition, subtraction, and multiplication–makes sense if consider equality-modulo-$p$ instead of ordinary equality. We call this {\em modular arithmetic} and refer to $p$ as the modulus.

The following are standard notations for “$m$ is equal to $n$ modulo $p$”:

\begin{equation*}

\begin{aligned}

m&=n\mod p\\

m&=_pn\\

m&\equiv_pn

\end{aligned}

\end{equation*}

Theorem. If $m\equiv_pn$ and $r\equiv_ps$, then $m+r\equiv_pn+s$ and $mr\equiv_pns$.

Proof. Suppose $m\equiv_pn$ and $r\equiv_ps$. That is, suppose $m-n$ and $r-s$ are multiples of $p$. Then

\begin{equation*}(m+r)-(n+s)=(m-n) + (r-s)\end{equation*}

is the sum of multiples of $p$, hence a multiple of $p$. So $m+r\equiv_pn+s$. Also

\begin{equation*}\begin{aligned}mr-ns&=mr-ms+ms-ns\\

&=m(r-s)+(m-n)s\end{aligned}\end{equation*}

so that $mr-ns$ is the sum of two terms, each of which is a multiple of $p$, hence $mr-ns$ is a multiple of $p$, which is to say $mr\equiv_pns$. $\Box$.

Exercise.Show that if $m\equiv_pn$ and $r\equiv_ps$, then $m-r\equiv_pn-s$.

There are two ways to think about drawing a picture of a relation on a set $A$.

if $A=\mathbb{R}$

We can draw relations on $\mathbb{R}$, because they are subsets of $\mathbb{R}\times\mathbb{R}$ — i.e., subsets of the plane. Actually you’ve been drawing these pictures since way back.

For example, let’s consider the relation $S$ given by $x\operatorname{S}y$ if $x^2-y^2\leq 1$. The picture looks like:

Here I’ve put $S$ in blue, and its complement $S^c$ in red.

What does $S^{-1}$ look like? $x\operatorname{S}^{-1}y$ means $y\operatorname{S}x$, i.e. $y^2-x^2\leq 1$. Here’s that, in green.

Notice that $S^{-1}$ and $S^c$ are general rather different things (that’s as we saw before).

To get $S^{-1}$ from $S$, we swap the roles of $x$ and $y$. visually, this looks like reflection across the line $y=x$. Here’s another example, with the line $y=x$ draw on explicitly:

We can use such a visual depiction to compute the domain and range of a relation: the domain is the “horizontal shadow” and the range is the “vertical shadow:

We can also use such a depiction to check some properties of relations. For example: for $R$ to be reflexive on $\mathbb{R}$ means every $x\in\mathbb{R}$ has $x\operatorname{R}x$. That is, every pair $(x,x)\in R$. All of the pairs of the form $(x,x)$ constitute the diagonal line $y=x$. Thus we can check reflexivity by asking: does the relation contain the diagonal line?

Here the relation $R$ is reflexive — it contains the line $y=x$ — and the relation $S$ is not.

We can also check symmetry. For $R$ to be symmetric means $x\operatorname{R}y$ guarantees $y\operatorname{R} x$. That is, if we reflect $R$ across the line $y=x$, we should land in in $R$ again. That is, $R$ being symmetric means $R$ is symmetric about the line $y=x$. Neither $R$ nor $S$ above is symmetric.

Transitivity is a bit more fun to check. Transitivity is relevant to pairs $(x,y)$ and $(y,z)$ both in $R$. Here we’ll check whether $S$, given by $x\operatorname{S}y$ if $x^2-y^2\leq 1$, is transitive. We have $.8\operatorname{S}.6$ and $.6\operatorname{S}.2$, so we check to see if $.8\operatorname{S}.2$. Here, $(.8,.2)$ is indicated in red — it’s in $S$. But we need this to hold for every such pair of points in $S$.

Unfortunately, it does not:

It’s a bit hard to see visually just what transitivity means, but you can see that it’s got something to do with right triangles.

if $A$ is a finite set

If $A$ is a finite set, we can draw what’s called a directed graph, or digraph, of the relation $R$. A directed graph is a collection of vertices, which we draw as points, and directed edges, which we draw as arrows between the points. For example, let’s take the set $A=\{2,3,4,5,6,7,8,9\}$ and the relation $(x,y)\in R$ if $x|y$.

The digraph corresponding to this relation is draw like this: we know $2|4$, $2|6$, and $2|8$. So we draw three arrows starting from 2. We also know that $3|6$ and $3|9$, so we draw those:

But that’s not all. We also know that $9|9$, for example. So we need to add arrows that start and end at each vertex:

Observe that divides, as a relation on this set, is transitive: whenever we have $x|y$ and $y|z$, we automatically have $x|z$. We can recognize this in the digraph by checking that, whenever there are two arrows connected head to tail, the third leg of that triangle is present:

Exercise. What do symmetry and reflexivity look like in the digraph?

[callout headingicon=”noicon” textalign=”textleft” type=”basic”]Assumptions are the termites of relationships.

character of Arthur Fonzarelli, Happy Days

[/callout]

Now we are ready to consider some properties of relations. Our interest is to find properties of, e.g. motherhood. To do this, remember that we are not interested in a particular mother or a particular child, or even in a particular mother-child pair, but rather motherhood in general.

We’ll start with properties that make sense for relations whose source and target are the same, that is, relations on a set.

Definition. Let $R$ be a relation on the set $A$.

• We call $R$ reflexive if every element of $A$ is related to itself; that is, if every $x\in A$ has $x\operatorname{R} x$.
• We call $R$ irreflexive if no element of $A$ is related to itself.
• We call $R$ symmetric if $x\operatorname{R} y$ means the same thing as $y\operatorname{R} x$.
• We call $R$ asymmetric if $x\operatorname{R} y$ guarantees that $\sim(y \operatorname{R} x)$.
• We call $R$ antisymmetric if the only way for $x\operatorname{R} y$ and $y\operatorname{R} x$ to both be true is if $x=y$.
• We call $R$ transitive if $x\operatorname{R} y$ and $y\operatorname{R} z$ together guarantee $x\operatorname{R} z$.

Exercise. Explain why none of these relations makes sense unless the source and target of $R$ are the same set.

Exercise. Which of the above properties does the motherhood relation $M$ have?

Exercise. Write the definitions above using set notation instead of infix notation.

Exercise. Write the definitions of reflexive, symmetric, and transitive using logical symbols.

Checking whether a given relation has the properties above looks like:

E.g. `Divides’ (as a relation on the integers) is reflexive and transitive, but none of: symmetric, asymmetric, antisymmetric.

Proof. We’ll show reflexivity first. Suppose $m$ is an integer. Then $m=m\cdot 1$, so $m$ divides $m$.

Now we’ll show transitivity. Suppose $m$ divides $n$ and $n$ divides $p$. Then there are $k_1$ and $k_2$ so that $n=k_1m$ and $p=k_2 n$. Then $p=k_2k_1m$, so $m$ divides $p$.

Note that 2 divides 4 but 4 does not divide 2. This counterexample shows that `divides’ is not symmetric.

Note that 4 divides 4. This counterexample shows that `divides’ is not asymmetric.

Note that $-2$ divides $2$ and $2$ divides $-2$, but $-2\neq 2$. This counterexample shows that `divides’ is not antisymmetric. $\Box$

E.g. $<$ is irreflexive, asymmetric, transitive, and antisymmetric, but neither reflexive nor symmetric.

Exercise. Show that `divides’ as a relation on $\mathbb{N}$ is antisymmetric.

Besides the ordinary set operations, there are special operations we can perform on relations.

Definition. The inverse of a relation $R$ from $A$ to $B$ is the relation from $B$ to $A$ defined by: $$R^{-1}=\left\{ (b,a)\middle| (a,b)\in R\right\}$$ That is, $b \operatorname {R^{-1}} a$ iff $(b,a)\in R^{-1}$ iff $(a,b)\in R$ iff $a\operatorname{R} b$.

E.g. $x\operatorname{LT^{-1}} y$ iff $y \operatorname{LT} x$ iff $y<x$.

That is, the inverse of the less-than relation is the greater-than relation.

Note that the inverse and the complement are very different things, because the complement of less-than is greater-than-or-equal-to.

Exercise. What is the inverse of the identity relation?

Definition. If $R$ is a relation from $A$ to $B$ and $S$ is a relation from $B$ to $C$, we define the {\em composite relation} $S\circ R$ from $A$ to $C$ by: $$S\circ R=\left\{ (a,c)\middle| \exists b\in B: (a,b)\in R\wedge (b,c)\in S\right\}$$

Note that the source of $S\circ R$ is the source of $R$ and the target of $S\circ R$ is the target of $S$.

We can think of $b$ as a stepping stone between $a$ and $c$. $S\circ R$ consists of all the pairs $(a,c)$ such that there is such a stepping stone, as we pass from the source of $R$ to the target of $S$.

Observe that unless the target of $T$ and the source of $V$ are the same, we can’t even make sense of $V\circ T$. So most composites aren’t defined, and we must first check that two relations are compatible before we try to compose them. Even if $S\circ R$ is defined, $R\circ S$ usually isn’t.

In lower mathematics courses, you probably only encountered relations on $\mathbb{R}$, so that all sources and targets were the same—thus, all compositions were defined. The sole exception to this is in multivariable calculus. This is precisely why the multivariable Chain Rule is so much more complicated than its single-variable counterpart.

Exercise. Formulate the definition of $S\circ R$ in infix notation. That is, explain what $x \operatorname{S\circ R} y$ means.

Exercise.  Consider the set $P$ of all people, and the relations $M$ and $F$ on $P$ given by: $x\operatorname{M} y$ iff $x$ is $y$’s mother and $x\operatorname{F} y$ iff $x$ is $y$’s father. Explain what the following relations mean: $F^c$, $M\cap F$, $M\circ M$, $F\circ F$, $F^{-1}$, $M\circ F$, $F\circ M$, $M\circ F^{-1}$, $F^{-1}\circ M$.

Theorem. Let $R$ be a relation from $A$ to $B$, $S$ a relation from $B$ to $C$, and $T$ a relation from $C$ to $D$. Then

• $\left(R^{-1}\right)^{-1}=R$
• $T\circ(S\circ R)=(T\circ S)\circ R$
• $I_B\circ R=R$ and $R\circ I_A=R$
• $\left(S\circ R\right)^{-1}=R^{-1}\circ S^{-1}$
• $I_{\operatorname{Domain}(R)}\subseteq R^{-1}\circ R$ and $I_{\operatorname{Range}(R)}\subseteq R\circ R^{-1}$.

Proof. We’ll prove the last clause, and leave the others as exercises.

Since we need to prove $I_{\operatorname{Domain}(R)}\subseteq R^{-1}\circ R$, let $x\in I_{\operatorname{Domain}(R)}$. Then $x=(a,a)$ for some $a\in \operatorname{Domain}(R)$. Since $a\in\operatorname{Domain}(R)$, there is some $b\in B$ with $(a,b)\in R$. So $(b,a)\in R^{-1}$. So $x=(a,a)\in R^{-1}\circ R$.

To show $I_{\operatorname{Range}(R)}\subseteq R\circ R^{-1}$, let $x\in I_{\operatorname{Range}(R)}$. Then $x=(b,b)$ for some $b\in \operatorname{Range}(R)$. Since $b\in\operatorname{Range}(R)$, there is some $a\in A$ with $(a,b)\in R$. Then $(b,a)\in R^{-1}$. So $x=(b,b)\in R\circ R^{-1}$.

What’s a relation?

Definition.  A relation from the set $A$ to the set $B$ is a(ny) subset of $A\times B$. We call $A$ the source and $B$ the target or codomain of the relation.

A relation from $A$ to $A$ is called a {\em relation on $A$}.

If $R$ is a relation from $A$ to $B$, and $(x,y)\in R\subseteq A\times B$, we say that $x$ is $R$-related to $y$, and sometimes write  $x\operatorname{R}y$. If $(x,y)\notin R$, we sometimes write $x\cancel{\operatorname{R}} y$.

The notation $x\operatorname{R}y$ is called infix notation; the notation $(x,y)\in R$ is called set notation or postfix notation or reverse Polish notation. The term infix comes from linguistics. An infix is a grammatical feature that gets inserted into the middle of a word, as opposed to the beginning or the end. The examples of this in English are almost all obscenities. The term reverse Polish refers to the school of logicians founded by Jan Łukasiewicz and Kazimierz Twardowski at the Universities of Lwów and Warsaw in the early 1900s.

Exercise. A relation on $\mathbb{R}$ is a subset of $\mathbb{R}\times\mathbb{R}$. What is a relation on $\mathbb{R}\times\mathbb{R}$?

Eg. The identity relation $I_A$ on any set $A$ is defined by: $$I_A=\left\{(a,a)\middle | a\in A\right\}$$

Then $x\operatorname{I_A}y$ means $(x,y)\in I_A$, i.e. that there is some $a\in A$ with $(x,y)=(a,a)$. But then $x=a$ and $y=a$, so $x=y$.

Thus the identity relation is nothing more than equality.

If we draw a picture of the identity relation, we get a diagonal line, so the identity relation is sometimes also called the  diagonal relation on $A$.

Exercise. If $A$ has exactly $n$ elements and $B$ has exactly $m$ elements, how many relations are there from $A$ to $B$?

Since relations are sets, we can do set operations to them (although this is usually not so interesting), for example:

Eg. Consider the relation on $\mathbb{R}$ given by:$$LT=\left\{(x,y)\middle| x<y\right\}$$

Then $x \operatorname{(LT)^c} y$ iff $(x,y)\in (LT)^c$ iff $(x,y)\notin LT$ iff $x\geq y$.

We could summarize this all by saying  the complement of the less-than relation is the greater-than-or-equal-to relation.

Note that ${}^c$ has a fairly natural meaning in terms of relationships: to say two elements are $R^c$-related is precisely to say they are not $R$-related.

Exercise. Explain what the intersection and union of two relations would mean.

Domain, Range, and Fibers of a Relation

To any relation $R$ from a set $A$ to a set $B$, we can associate the following sets:

Definition. The domain of $R$ is the set of its first coordinates. That is: $$Domain(R)=\left\{x\middle\vert \exists y:(x,y)\in R\right\}$$The range of $R$ is the set of its second coordinates. That is: $$Range(R)=\left\{y \middle\vert \exists x:(x,y)\in R\right\}$$

Observe that the domain is automatically a subset of the source $A$, and the range is automatically a subset of the target $B$. We can also focus on particular first coordinates:

Definition. The horizontal fiber at $d\in B$ is $$A_d^R=\left\{x\middle\vert (x,d)\in R\right\}$$The vertical fiber at $c\in A$ is $$B_c^R=\left\{y\middle\vert (c,y)\in R \right\}$$

That is, the horizontal fiber is all the first coordinates with $d$ as their corresponding second coordinate.

Theorem. The domain and the range are unions of the corresponding fibers. That is,

• $Domain(R)=\bigcup_{d\in B} A_d^R$
• $Range(R)=\bigcup_{c\in A} B_c^R$

[callout headingicon=”noicon” textalign=”textleft” type=”basic”]Society does not consist of individuals, but expresses the sum of interrelations, the relations within which these individuals stand.

Karl Marx, Grundrisse der Kritik der Politischen Ökonomie

[/callout]

If two young people are seeing each other romantically, we usually say something like Frank and Jeremy are in a relationship. The word in suggests we should use the notion of set membership to record what a relationship means.

Overview of Relations

• Relations and Set Products (this page) Relations are sets of pairs, so we must think about sets of pairs.
• Basics of Relations.
• Operations on Relations. Relations can be combined in interesting ways.
• Graphing Relations. We can draw visual representations of relations in several different ways.
• Properties of Relations.
• Equivalence Relations. Relations which generalize $=$.
  • Equivalence Classes.
  • Partitions.
• Ordering Relations. Relations which generalize $\leq$.

Pairs of Elements, Products of Sets

Since a relation is a set of pairs, let’s try to understand sets of pairs.

Definition. The ordered pair with coordinates $a$ and $b$ is the symbol $(a,b)$. Two ordered pairs $(a,b)$ and $(x,y)$ are the same iff $a=x$ and $b=y$.

Definition. The product of sets $A$ and $B$ is $$A\times B=\left\{(x,y)\middle\vert x\in A \wedge y\in B\right\}$$

That is, $A\times B$ is the set of all pairs whose first coordinate comes from $A$ and whose second coordinate comes from $B$.

We’ve seen set products before: $\mathbb{R}\times\mathbb{R}=\left\{(x,y)\middle\vert x\in \mathbb{R},y\in\mathbb{R}\right\}$ is the set of all pairs of real numbers, i.e. the Cartesian plane. In fact $A\times B$ is sometimes called the Cartesian product of $A$ and $B$. (Both the plane and the more general product are named for the philosopher and mathematician Rene Descartes.)

Since $A\times B$ is a set, we should ask, what does it mean to be an element of $A\times B$? That is, let’s unpack $t\in A\times B$. This should mean: $$t=(x,y)$$ But $x$ and $y$ are new variables, so they require new quantifiers. In fact,

$t\in A\times B$ means $\exists x\in A:\exists y\in B: t=(x,y)$

Theorem. For any sets $A$, $B$, $C$, and $D$,

•  $\left(A\times B\right)\cap\left(C\times D\right)=\left(A\cap C\right)\times\left(B\cap D\right)$
• $\left(A\times B\right)\cup\left(C\times D\right)\subseteq\left(A\cup C\right)\times\left(B\cup D\right)$

Note that the second clause is not set equality, merely subset. This is not an omission.

Proof. We’ll prove the first clause and leave the second as an exercise.

First we’ll show that $\left(A\times B\right)\cap\left(C\times D\right)\subseteq \left(A\cap C\right)\times\left(B\cap D\right)$. To this end, let $x\in\left(A\times B\right)\cap\left(C\times D\right)$. So $x\in A\times B$ and $x\in C\times D$. Then there are $a\in A$ and $b\in B$ with $x=(a,b)$. On the other hand, there are $c\in C$ and $d\in D$ with $x=(c,d)$. Since $(a,b)=(c,d)$, we see that $a=c$ and $b=d$. So $a\in C$, hence $a\in A\cap C$. Similarly, $b\in D$, so $b\in B\cap D$. Thus $x=(a,b)\in (A\cap C)\times(B\cap D)$.

Now we’ll show the other inclusion, $\left(A\cap C\right)\times\left(B\cap D\right)\subseteq \left(A\times B\right)\cap\left(C\times D\right)$. To this end, let $x\in \left(A\cap C\right)\times\left(B\cap D\right)$. Then there are $y\in A\cap C$ and $z\in B\cap D$ with $x=(y,z)$. Since $y\in A\cap C$, we know $y\in A$ and $y\in C$. Similarly $z\in B$ and $z\in D$. So $x=(y,z)\in A\times B$ and $x=(y,z)\in C\times D$, hence $x\in \left(A\times B\right)\cap \left(C\times D\right)$. $\Box$

Exercise. Is $\times$ commutative or associative? That is, is either of the following equalities automatic?

$$A\times B = B\times A$$

$$\left(A\times B\right)\times C = A\times \left( B\times C\right)$$

There’s one more thing to note about set products, which is why we use the word product at all:

Theorem. If $A$ has exactly $n$ elements and $B$ has exactly $m$ elements, then $A\times B$ has exactly $n\cdot m$ elements.

That is, the size of the product is the product of the sizes.