\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 11}
\date{Wednesday June 6, 2012}
\newcommand{\df}{\textbf}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\begin{document}
\maketitle
\section{Relations}
Today, we begin by investigating properties of relations. We use a few toy relations as examples.
\subsection{Examples of Relations}
There are a few relations that particularly capture different notions. Let us define those relations, and then every time we talk about a property we will decide whether each of our relations satisfies those properties.
\begin{eg}
Our first example of a relation is a very familiar one: equality with, well, anything. In particular, let us take equality on the natural numbers $\N$. Equality may be the first relation we ever heard of in math class.
\end{eg}
\begin{rmk}
If one thinks of math as a programming language, equality is probably one of the built in methods that every class inherits; there may be lots of different notions of equality (and we'll talk about this), but no matter what mathematical structures you are talking about, one usually always has access to the question: are these two objects the same?
\end{rmk}
\begin{eg}
Our next example is one that we talked about last time. It is divisibility on $\Z$. That is $a \mid b$ is a relation that is true exactly when there is some integer $c$ such that $a\cdot c = b$.
We will also talk about this relation on the set $\N$.
\end{eg}
\begin{eg}
Our next example will $\leq$ on any of the sets that we are used to being ordered. There are four: $\N$, $\Z$, $\Q$, and $\R$. Although they are all similar relations (and even extend each other) each of the 4 has distinct properties.
We will also talk about the strict order $<$.
\end{eg}
\begin{rmk}
The symbol $\leq$ , like $=$, is very \df{overloaded}, meaning that it is used for a lot of different things, and you must be able to tell from context what relation it refers it.
\end{rmk}
\begin{eg}
Our last example is going to be a relation on $\R \times \R$. Fix some positive real number $\epsilon$. For $(x_1,y_1),(x_2,y_2)\in\R\times\R$, define the function
\[
d((x_1,y_1),(x_2,y_2)) = \sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }
\]
Define a relation $R_\epsilon$, where
\[
R_\epsilon( (x_1,y_1),(x_2,y_2) ) \iff d((x_1,y_1),(x_2,y_2)) < \epsilon
\]
\begin{question}
Can you think of the intended meaning for this relation?
\end{question}
\begin{ans}
\Hide{1cm}{
It the relation will be true exactly when the two points are within $\epsilon$ of each other.
}
\end{ans}
\end{eg}
\subsection{Properties}
\subsubsection{Reflexive}
\begin{dfn}
A relation $R$ on a set $A$ is \df{reflexive} if for every $a\in A$ we have $a$ is $R$-related to $a$.
Similarly, a relation $R$ on a set $A$ is \df{irreflexive} if for every $a\in A$ we have that $a$ is not $R$-related to $a$.
\end{dfn}
\begin{question}
Is irreflexive the negation of reflexive?
\end{question}
\begin{ans}
\Hide{.5cm}{
No; irreflexive says nothing is related to itself, where as not reflexive would mean there is a at least one thing that is not related to itself
}
\end{ans}
{\noindent \bf Our Examples }
\begin{enumerate}
\item For equality: It is of course reflexive. Take $n\in \N$. Clearly $n=n$.
\item For divisibility: Divisible is reflexive, on both $\N$ and $\Z$. Take $a\in \Z$. Then $a = a\cdot 1$. Therefore, it is clear that $a$ divides $a$, and therefore we have $a\mid a$. So $\mid$ is reflexive.
\item For $\leq$: This is of reflexive on any of the sets we have talked about, since equality is. For $<$: This is not reflexive. In fact, it is irreflexive. Take $a\in \R$. Then $a \not < a$ as they are equal.
\item Fix $\epsilon > 0$. For the $R_\epsilon$ relation, it is reflexive. $d( (x,y), (x,y) ) = 0 < \epsilon$ as $\epsilon > 0$.
\end{enumerate}
\begin{question}
Can a relation $R$ which is reflexive be empty?
\end{question}
\begin{ans}
\Hide{.5cm}{
Yes; namely if the set itself the relation is over is empty. If however, the set is nonempty then a reflexive relation is never empty. Can you prove this?
}
\end{ans}
\subsubsection{Symmetric}
\begin{dfn}
A relation $R$ on $A$ is \df{symmetric} if for every $a,b\in A$, if $aRb$ then $bRa$.
A relation $R$ on $A$ is \df{asymmetric} if for every $a,b\in A$, if $aRb$ then $\neg(bRa)$. Meaning, symmetry never holds.
A relation $R$ on $A$ is \df{anti-symmetric} if for every $a,b\in A$ if $aRb$ and $bRa$ then $a=b$. In other words, the only time we have symmetry is when it is from reflexivity.
\end{dfn}
{\noindent \bf Our Examples }
\begin{enumerate}
\item For equality: Equality is symmetric. If $a = b$ then of course we also know $b=a$.
\item For divisibility: Over $\N$, divisibility is anti-symmetric.
\begin{proof}
Take $a, b\in \N$, and suppose that $a \mid b$ and $b\mid a$. We wish to show that $a=b$. Well, as $a\mid b$ we know that there is some $k$ such that $ak = b$. Similarly, as $b\mid a$ we know there is some $l$ such that $bl = a$.
Substituting, we get that $akl = a$; this either means that means that $kl = 1$ or $a=0$. If $a=0$ it is easy to see that $b=0$ as well since $0$ divides nothing except itself. Otherwise, $kl=1$. As we are working over the naturals, $kl = 1$ certainly implies that $k=l=1$, so $a=b$.
\end{proof}
Over $\Z$ however, we do not have anti-symmetry; $-1\mid 1$ and $1\mid -1$. So over $\Z$ all we have is that the relation is not symmetric ($1\mid 2$ but $2\mid\!\!\!\!/ 1$)
\item For $\leq$: We have anti-symmetry.
\begin{proof}
Let $a,b$ be real numbers where $a \leq b$ and $b\leq a$. Clearly this means that $a=b$. Otherwise, either $a > b$ or $b > a$. Without loss of generality, $a > b$. But then $a - b > 0$, which contradictions $a \leq b$.
\end{proof}
For $<$: we have asymmetry
\begin{proof}
This is a straightforward property of the real numbers called \df{trichotomy}. For every pair of reals $a,b$ exactly one of the following is true: $a=b$, $a < b$, $a > b$. Therefore, if we had $a$ and $b$ reals where $a < b$ and $b < a$ we would contradict this property as then two of the above would be true.
\end{proof}
\item Fix $\epsilon > 0$. For $R_\epsilon$ we have symmetry.
\begin{proof}
Take $(x_1,y_1)$, $(x_2,y_2)$ in the real numbers arbitrary. Suppose that $R_\epsilon ((x_1,y_1),(x_2,y_2))$. Want to show $R_\epsilon ((x_2,y_2),(x_1,y_1))$. Then $d( (x_1,y_1), (x_2,y_2) ) < \epsilon$, ie.
\[
\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 } < \epsilon
\]
But then obviously, by factoring out a negative $1$ in each of the squares:
\[
\sqrt{ (x_2 - x_1)^2 + (y_2 - y_1)^2 }
\]
Which gives that $d( (x_2,y_2), (x_1,y_1) ) < \epsilon$, and so $R_\epsilon ((x_2,y_2),(x_1,y_1))$
\end{proof}
\end{enumerate}
\begin{question}
Can a relation $R$ which is symmetric be empty?
\end{question}
\begin{ans}
\Hide{.5cm}{
Yes, in fact the empty relation is always symmetric. Can you see why?
}
\end{ans}
\subsubsection{Transitive}
\begin{dfn}
A relation $R$ on $A$ is transitive if and only if for every $a,b,c\in A$ we have if $aRb$ and $bRc$ then $aRc$.
\end{dfn}
{\noindent \bf Our Examples }
\begin{enumerate}
\item For equality: $=$ is transitive. If $a=b$ and $b=c$ then clearly $a=c$.
\item For divisibility: divisibility is transitive.
\begin{proof}
Take $a,b,c\in \Z$ and suppose that $a\mid b$ and $b\mid c$. Then we get a $k$ such that $ak= b$ and an $l$ such that $bl = c$. Substituting $b$ from the first equation into the second, we get that $akl = c$, which shows that $a\mid c$.
\end{proof}
\item For $\leq$ and $<$: these are transitive. This is straightforward. If $a < b$ and $b < c$ then $c$ is larger than $b$ which is larger than $a$, and so $c$ is larger than $a$.
\item Fix $\epsilon > 0$. $R_\epsilon$ is not transitive.
\begin{proof}
To show it is not transitive, we must give $a,b,c\in \R\times \R$ that work. Notice, we will not control what $\epsilon$ is. If we do this, we will show that some $R_\epsilon$'s are not transitive; but we want to show the stronger statement: this relation is never transitive, not matter what $\epsilon$ is.
Take the points $a = (0,0)$, $b=(0,\frac{\epsilon}{2})$, and $c=(0,\epsilon)$.
Calculating, we get $d(a,b) = \frac{\epsilon}{2}$, $d(b,c) = \frac{\epsilon}{2}$, and $d(a,c) = \epsilon$. Therefore, we have $R_\epsilon(a,b)$, and $R_\epsilon(b,c)$, but not $R_\epsilon(a,c)$. This shows this is not transitive.
\end{proof}
\end{enumerate}
\begin{question}
Can a relation $R$ which is transitive be empty?
\end{question}
\begin{ans}
\Hide{.5cm}{
Yes, in fact the empty relation is always transitive. Can you see why?
}
\end{ans}
\subsection{Other Properties}
There are lots of other properties that are looked at. The ones previewed above are very broad with respect to all of math. We will take a brief detour to talk about a few properties.
\begin{dfn}
For the following definitions, let $R$ be a relation over a set $A$.
\begin{itemize}
\item \df{Totality}: We say $R$ is \df{total} if for every $a, b \in A$, we have $aRb$ or $bRa$.
Examples: $\leq$ is a total relation on any of the ones we've talked about. This was mentioned at the principle of trichotomy. To contrast, $<$ is not total, since neither $1 < 1$ and the revered $1 < 1$ are true.
\item \df{Well-Founded}: We say $R$ is \df{well-founded} if there is no infinite descending chain; that is there is no $a_1,a_2,a_3,\ldots$ all distinct such that:
\[
(a_2 R a_1) \mbox{ and } ( a_3 R a_2 ) \mbox{ and } (a_4 R a_3) \cdots
\]
Examples: $\N$ with $\leq$ is well-founded. Can you prove it?
To contrast, $\R$ with $\leq$ is not wellfounded.
\[
1 > \frac{1}{2} > \frac{1}{4} > \frac{1}{8} > \cdots
\]
\item \df{Density}: We say $R$ is \df{dense} if for every $a, b$ not equal where $aRb$, there is a $c$ not equal to $a$ or $b$ such that $a R c$ and $c R b$.
Examples $\Q$ with $\leq$ is dense. For every $x, y$ where $x \leq y$ and $x\neq y$ there is something different in between, namely $\frac{x+y}{2}$.
To contrast, $\Z$ and $\N$ are not dense; $1$ and $2$ have nothing in between.
\end{itemize}
\end{dfn}
There is an entire class of relations called \df{order relations}.
\begin{itemize}
\item A relation is a \df{partial order} if it is reflexive, transitive, and anti-symmetric. This is supposed to capture the properties of $\mid$.
\item A relation is a \df{linear order} if it is a partial order which is total. This is suppose to capture the properties of $\leq$ on $\Z$ (or any of the sets really).
\item A relation is a \df{well-ordering} if is a linear order which is wellfounded. This is supposed to capture the properties of $\leq$ on $\N$.
\item A relation is a \df{dense linear order} or \df{DLO} if it is a linear order that is dense. This is suppose to capture the properties of $\leq$ on $\Q$.
\end{itemize}
\begin{rmk}
As it turns out, induction can be done on any well-ordered set. In future math classes, you may see applications of this fact.
\end{rmk}
\section{Equivalence Relations}
Now, we begin talking about equivalence relations. This will occupy our time for the rest of the week, essentially.
\begin{dfn}
Equivalence relations are meant to capture the properties of equality on sets. $\sim$ is an equivalence relation on a set $A$ if and only if it is
\begin{itemize}
\item Reflexive: $\A a \in A \stt a \sim a$.
\item Symmetric: $\A a,b\in A \stt (a\sim b) \to (b\sim a)$.
\item Transitive: $\A a,b,c\in A \stt ( (a\sim b) \oand (b\sim c) ) \to (a \sim c)$.
\end{itemize}
\end{dfn}
\begin{eg}
There are many examples of equivalence relations. We will use the following toy relation to begin.
Define $\sim$ on the real numbers by
\[
a \sim b \iff \sin(a) = \sin(b)
\]
We first prove this is an equivalence relation.
\begin{proof}
First we show that it is reflexive. Let $a\in \R$ be arbitrary. We seek to show that $a\sim a$. Well, this is clear, as $\sin(a) = \sin(a)$.
Next, we show that it is symmetric. Like $a,b\in \R$, and suppose that $\sin(a) = \sin(b)$. Then of course, $\sin(b) = \sin(a)$, thus $b\sim a$.
Finally, suppose that $a\sim b$ and $b\sim c$. Then $\sin(a) = \sin(b)$ and $\sin(b) = \sin(c)$. Then of course $\sin(a) = \sin(c)$, and we are done.
\end{proof}
This proof was very straightforward. This is mostly a testament to $\sim$ being defined in terms of equality on $\R$.
\end{eg}
\begin{dfn}
Let $\sim$ be a an equivalence relation on a set $A$. Then if $a\in A$ the \df{equivalence class of $a$ with respect to $\sim$}, which we denote $[a]_\sim$ is:
\[
[a]_\sim = \set{ b\in A \mid a \sim b }
\]
That is, the equivalence class of $a$ is all of the things in $a$ that are related to $a$.
We say $a$ is the \df{representative} of the class $[a]_\sim$.
\end{dfn}
\begin{eg}
Consider the above equivalence class.
\[[0]_\sim = \set{ \ldots, -2\pi, -\pi, 0, \pi, 2\pi , \ldots }\]
Note then that $[0]_\sim = [2\pi]_\sim$. Can you write down what $[\frac{\pi}{2}]_\sim$ is?
\end{eg}
The set of equivalence classes form a partition of a set.
\begin{dfn}
If $A$ is a set then a family of sets $\set{ \fancy{F}_\alpha \mid \alpha\in \Lambda }$ is a \df{partition} if
\begin{itemize}
\item The sets span $A$: that is for every $a\in A$, there is some $\alpha$ such that $a\in F_\alpha$. More concisely \[A = \bigcup_{\alpha\in\Lambda} \fancy{F}_\alpha\]
\item The sets are pairwise disjoint: that is, for each $\alpha,\beta\in\Lambda$ we have $\fancy{F}_\alpha \cap \fancy{F}_\beta = \emptyset$.
\item The sets are nonempty: that is for each $\alpha\in \Lambda$, $\fancy{F}_\alpha \neq \emptyset$.
\end{itemize}
\end{dfn}
\begin{thm}
If $A$ is a set and $\sim$ is an equivalence relation on $A$ then the set of equivalence classes $\set{ [a]_\sim \mid a\in A }$ is a partition.
\end{thm}
\begin{proof}
First we show that the sets span $A$. Take $a\in A$. Want to show that $a$ is in some equivalence class. Well, by reflexivity, $a\sim a$, so $a\in [a]_\sim$.
Clearly each equivalence class is nonempty as it at least has the representative in there.
Finally, we show they are disjoint. Suppose that $E_1$ and $E_2$ are two distinct equivalence classes. As they are distinct and nonempty (by last sentence) we can take $a\in E_1$ and $b\in E_2$ such that $a\not\sim b$. Want to show they are disjoint. Otherwise, there is a $c\in E_1 \cap E_2$. Then $a\sim c$ and $b\sim c$. By symmetry, we have $a\sim c$ and $c\sim b$. By transitive, we get $a\sim b$, which is a contradiction.
\end{proof}
\end{document}