## Equivalence Classes

Standard post by ancoop on November 2, 2018
Comments are off for this post

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.

## Equivalence Relations

Standard post by ancoop on October 31, 2018
Comments are off for this post

[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$.

## Graphing Relations

Standard post by ancoop on October 24, 2018
Comments are off for this post

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?

## Properties of Relations

Standard post by ancoop on October 24, 2018
Comments are off for this post

[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.

## Operations on Relations

Standard post by ancoop on October 17, 2018
Comments are off for this post

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}$.

## Basics of Relations

Standard post by ancoop on October 16, 2018
Comments are off for this post

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$

## Relations

Standard post by ancoop on October 16, 2018
Comments are off for this post

[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.

### 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.

Standard post by ancoop on October 15, 2018
Comments are off for this post

A few years ago I got turned on to Geogebra, probably the world’s most awesome and low-barrier-to-entry mathematical software. The best part of Geogebra is that you can do most everything through the web client or the mobile app. (I have the desktop client, but I never use it!)

Here are some doodads I’ve built with Geogebra.

### Visualizing Directional Derivatives

This gadget illustrates one way to think about the directional derivative. There are versions of this same gadget for partial derivatives and the tangent plane, too.

### 3D Riemann Sums over a Rectangle

A tool for visualizing how the Riemann sums obtained by taking a product partition of the rectangle $[0,2]\times[0,3]$ approximate the volume under the graph. You can specify how many subintervals to partition $[0,2]$ and $[0,3]$ into, and change the function $f(x,y)$.

### 3D Riemann Sums over a Non-Rectangular Region

The same as the previous applet, but this one is over the region $0\leq y\leq 2$, $0\leq x\leq 3-\frac{3}{4}y^2$.

### Level Sets

A tool for visualizing the relationship between the level curves of a function $f(x,y)$, the graph of $f(x,y)$, and the intersection of the graph with horizontal planes.

### The Frenet-Serret Frame

You specify a curve, and this applet animates its Frenet-Serret frame.

### The Matrix of a Reflection

Change the slider to alter the slope of the line; watch as the reflections of the points $(1,0)$ and $(0,1)$ — and the image of Satan from the Codex Gigas — move along with the line. The matrix representing the reflection is obtained from the coordinates of the reflected points.

### Constructing Lines in the Poincaré Disk

This isn’t a Geogebra gadget itself, but it shows how awesome Geogebra is for doing exploratory assignments.

## Families of Sets and Generalized’ Set Operations

Standard post by ancoop on October 12, 2018
Comments are off for this post

### Finite Set Operations

The operations $\cup$ and $\cap$ apply to two sets; we can however use them to combine more than one set. If we have a finite collection of sets $A_1,A_2,\ldots,A_N$, we write

\begin{aligned}\bigcup_{i=1}^N A_i&=A_1\cup A_2\cup \cdots\cup A_N\\\bigcap_{i=1}^N A_i&=A_1\cap A_2\cap \cdots\cap A_N\end{aligned}

Activity. Give a better definition of $\displaystyle\bigcup_{i=1}^NA_i$ and $\displaystyle\bigcap_{i=1}^NA_i$ . (Hint. What did we say about definitions involving $\cdots$?)

De Morgan’s Laws. For any finite collection of sets $A_1,\ldots, A_n$,

\begin{align*}\left(\bigcup_{i=1}^N A_i\right)^c=&\bigcap_{i=1}^NA_i^c\\\left(\bigcap_{i=1}^N A_i\right)^c=&\bigcup_{i=1}^NA_i^c \end{align*}

Exercise. Prove this version of de Morgan’s Laws.

### Transfinite Operations

There is no reason to restrict our attention to {\em finite} collections of sets. For example, we might consider

the collection of intervals of the form $[n,n+1]$, where $n$ is allowed to be an natural number,

or perhaps

the set of all disks centered at the origin

each of which consists of an infinite number of sets. We usually use set-builder notation to write something like

$$\left\{[n,n+1]\middle\vert n\in\mathbb{N}\right\}$$

or

$$\left\{D_r\middle\vert r\in(0,\infty) \right\}$$

to emphasize that what we are dealing with is a(n infinite) set of sets. (Here we have written $D_r=\left\{(x,y)\middle\vert x^2+y^2<r^2\right\}$ for the disk of radius $r$ centered at the origin.) We call the set to the right of the pipe the index set: in these collections  the index sets are $\mathbb{N}$ and the interval $(0,\infty)$, respectively.

We can define unions and intersections of such infinite collections of sets by recalling that $\exists$ acts like a souped-up version of $\vee$ and $\forall$ acts like a souped-up version of $\wedge$.

Given a collection of sets $\mathcal{A}=\left\{A_\lambda\middle\vert \lambda\in\Lambda\right\}$, we set

Definition. \begin{align*}\bigcup\mathcal{A}&=\bigcup_{\lambda\in\Lambda}A_\lambda=\left\{x\middle\vert \exists\lambda\in\Lambda:x\in A_\lambda\right\}\\\bigcap\mathcal{A}&=\bigcap_{\lambda\in\Lambda}A_\lambda=\left\{x\middle\vert \forall\lambda\in\Lambda,x\in A_\lambda\right\}\end{align*}

E.g. $\displaystyle\bigcup_{n\in\mathbb{N}} [n,n+1]=[1,\infty)$

Proof. Let $x\in[1,\infty)$. Then there is some $n\in\mathbb{N}$ with $n\leq x\leq n+1$, so $x\in[n,n+1]$. Thus $\displaystyle x\in\bigcup_{n\in\mathbb{N}} [n,n+1]$.

Now let $\displaystyle x\in\bigcup_{n\in\mathbb{N}} [n,n+1]$. Then there is some $n\in\mathbb{N}$ with $x\in[n,n+1]$. But $[n,n+1]\subseteq [1,\infty)$, so $x\in[1,\infty)$. $\Box$

E.g. $\displaystyle\bigcap_{r\in(0,\infty)} D_r=\{(0,0)\}$

Proof. Certainly the origin $(0,0)$ is in each disk $D_r$. We will show it is the only such point.

Consider any point $(x,y)$ in the plane. Let $r_1=\sqrt{x^2+y^2}$ be the distance between $(x,y)$ and the origin. Then if we select $r=\frac{1}{2}r_1$, we see that $(x,y)\notin D_r$. Thus $(x,y)$ cannot be in every $D_r$.

de Morgan’s Laws. For any collection $\{A_\lambda|\lambda\in\Lambda\}$, we have \begin{align*}\left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)^c=&\bigcap_{\lambda\in\Lambda}A_\lambda^c\\ \left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)^c=&\bigcup_{\lambda\in\Lambda}A_\lambda^c \end{align*}

Exercise. Prove this version of de Morgan’s Laws.

Exercise. What is each of the following sets?

1. $\displaystyle\bigcap_{n\in\mathbb{N}} [n,n+1]$
2. $\displaystyle\bigcup_{r\in(0,\infty)} D_r$
3. $\displaystyle\bigcup_{n\in\mathbb{N}}\left[\frac{1}{n},1\right]$
4. $\displaystyle\bigcap_{n\in\mathbb{N}}\left[\frac{1}{n},1\right]$

Exercise Express each set below as either a generalized union or a generalized intersection, and also express it in set-builder notation.

1. $\displaystyle B\setminus\left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)$
2. $\displaystyle B\setminus\left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)$
3. $\displaystyle \left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)\setminus B$
4. $\displaystyle \left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)\setminus B$

## Set-Builder Notation

Standard post by ancoop on October 10, 2018
Comments are off for this post

Recall that, by definition, $S$ being a set is equivalent to “$x\in S$” being an open sentence. This means that the theory of sets and the theory of logic are basically the same–differing only by notation and perspective. One can exploit this correspondence by using open sentences to define sets. Given an open sentence $P(t)$, we can define the corresponding set $S_P$, which consists of all values $t$ so that $P(t)$ is true. We write $$S_P=\left\{t\middle\vert P(t)\right\}$$ and read aloud “$S_P$ is the set of all $t$ such that $P(t)$.” In other words, $S_P$ is the set so that $x\in S_P$ means exactly $P(x)$. This way of defining sets has the unfortunately puerile name set-builder notation. It’s how most sets in most mathematics texts are defined. By way of example, we’ll rephrase some previous definitions.

Definition.

• $A^c=\left\{x\middle\vert x\notin A\right\}$
• $A\cup B= \left\{p\middle\vert p\in A\vee p\in B\right\}$

Activity Complete the list of set operations by giving set-builder descriptions of each of the following set operations.

• $A\cap B$
• $A\setminus B$
• $\left(A\setminus B\right)\cup\left(B\setminus A\right)$
• $2^B$

Exercise. Consider two sets, $A=\left\{x\middle\vert P(x)\right\}$ and $B=\left\{t\middle\vert Q(t)\right\}$. What can we say about the open sentences $P$ and $Q$ if we know each of the following facts about the sets $A$ and $B$?

• $A=B$
• $A\subseteq B$
• $A=\varnothing$
• $B$ is the universe

The last exercise referenced the universe, which naturally leads to the question of how to specify the universe in set-builder notation. An even number is an integer which is twice some other integer. So we could write

Definition. \begin{equation*}\left\{n\middle\vert n\in\mathbb{Z}\wedge\exists k:\left(k\in \mathbb{Z}\wedge n=2k\right) \right\}

But the right-hand side (after the pipe symbol $\vert$) is a little crowded. Doing the same trick as we did in, we want to handle the conditions $n\in\mathbb{Z}$ and $k\in\mathbb{Z}$ by changing the universe. We do this as follows:

Definition. The set of even numbers is the set \begin{equation*}\left\{n\in\mathbb{Z}\middle\vert \exists k\in\mathbb{Z}:n=2k\right\}\end{equation*}

We would read this aloud “The set of all integers $n$ such that there is an integer $k$ with $n=2k$.” In this version of set-builder notation, the left-hand side (before the pipe) is about what kind of objects the elements of the set being defined are; the right-hand side gives a condition that describes the set.

There is yet another way to use set-builder notation to define a set, as exemplified:

Definition. \begin{equation*} \left\{2k\middle\vert k\in\mathbb{Z}\right\} \end{equation*}

We would read this aloud “The set of a numbers of the form $2k$, where $k$ is an integer.” Notice that $n$ has disappeared entirely from this version. In this version of set-builder notation, the left-hand side gives the general form of the elements of the set, and the right-hand side tells us which elements of that form actually occur in the set.

### Learning to let go of your $x$s

An open sentence like $$E(x):\ \ \ \exists k: x=2k$$
has two variables and one quantifier. The two variables are used in quite different ways. First, notice that the only variable that’s eligible for plugging in to $E$ is $x$: we can sensibly ask Is it true that $E(2)$? and Is it true that $E(3)$?. But substituting for $k$ like this:$$\exists 7: x=2\cdot 7$$ yields nonsense.

What’s going on here? Variables where we can plug in values and get something sensible (like $x$ here) are called free. The other kind of variable (like $k$ here) is called a bound variable, from the verb bind. The idea is that the quantifier $\exists$ has a binding effect on the variable. You can recognize bound variables in three ways:

• Substituting for a bound variable results in nonsense; substituting for a free variable does not.
• Bound variables almost always occur exactly twice; free variables occur once.
• There is always a way to read a mathematical formula containing a bound variable in a way that makes the bound variable go away.

I’ll illustrate these checks by giving some examples of bound variables, one of which you’ve seen before:

Consider the integral $$\int_a^b x^2\ dx$$ The variables $a$ and $b$ are free; the variable $x$ is bound.

• We could substitute in for $a$ and $b$: $\int_1^3x^2\ dx$. If we substitute for $x$, we get $\int_a^b 7^3\ d7$, which is nonsense.
• The variable $x$ occurs twice: once in the integrand and once in the differential.
• We could read this integral aloud as “The integral, from $a$ to $b$, of the squaring function.”

Consider the (true) statement $$\forall x, x^2<9 \Rightarrow x^3<27$$ Here, the variable $x$ is bound and there are no free variables.

• If we tried to substitute, we’d get something like $\forall 4, 4^2<9 \Rightarrow 4^3<27$, which doesn’t make sense.
• The variable $x$ occurs twice: once in the open sentence $x^2<9 \Rightarrow x^3<27$, and once in the quantifier.
• We could read this aloud as “If a number’s square is less than 9, its cube is less than 27.”

One very important trick to do with a bound variable is to replace it, across the board, with another variable. I call this letting go of your $x$s. So for example, in an integral we can change the integrating variable at whim: $$\int_1^3 x^2\ dx=\frac{26}{3}=\int_1^3 y^2\ dy$$ We can do the same with quantified statements and open sentences: $$\forall x, x^2<9 \Rightarrow x^3<27\text{ means the same thing as } \forall q, q^2<9 \Rightarrow q^3<27$$

What does all this have to do with sets and set-builder notation? Observe that the variables that appear in set-builder notation are almost all bound, which we can tell because they occur twice (once on each side of the pipe). For example:$$\left\{x\middle\vert -1<x<1\right\}$$ is the same set as $$\left\{g\middle\vert -1<g<1\right\}$$ which in turn is the same set as $$\left\{t\middle\vert -1<t<1\right\}$$

The point is that the particular choice of variable $x$ or $y$ or $Z$ or $p$ or $\varphi$ has no significance at all. By way of example, if $A=\left\{ x \middle\vert x^2 \in[1,3)\right\}$, then $$t\in A\text{ means that } t^2\in[1,3)$$ $$F\in A\text{ means that } F^2\in[1,3)$$
In particular, our definition of $A$ does not create any particular link between the letter $x$ and the set $A$. We could just as well have defined $A=\left\{ z \middle\vert z^2 \in[1,3)\right\}$.