\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 12}
\date{Thursday June 7, 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{A Word on Well-Ordering}
	
	We talked about the principle of induction. Given a formula $\phi(n)$ then to prove $\A n \st \phi(n)$ then it is sufficent to prove
	\begin{itemize}
		\item $\phi(0)$. 
		\item $\A n \st \phi(n) \to \phi(n+1)$
	\end{itemize}
	
	We mentioned that $\N$ is a \df{well-ordering}, that is that $\leq$ is a linear ordering (total, transitive, reflexive, anti-symmetric) on $\N$ and that it is well-founded (no infinite descending chains). All of these properties are obvious on $\N$. There is another property that is quite useful:
	
	\begin{dfn}[The Well-Ordering Property]
		A set $A$ with a linear ordering $\preceq$ has the \df{well-ordering property} if and only if for every $S\sbs A$, where $S\neq \emptyset$, there is an $a\in S$ which is minimum with respect to $\preceq$, that is every $b\in S$ is such that $a\preceq b$. 
	\end{dfn}
	
	As it turns out, a set is a well-ordering if and only if it has the well-ordering property. 
	
	\begin{proof}
		Suppose that $A$ with $\succeq$ is well ordered. Then it is a linear order and there are no infinite descending chains. We want to show that it has the well-ordering property. So take $S\sbs A$ nonempty. We want to show that $S$ has a least element. 
		
		We go by contradiction. Suppose not. Then take $x_1\in S$, which is possible as $S$ is nonempty. As $x_1$ is not minimal, we can find $x_2\in S$ such that $x_1 \succeq x_2$. Similarly, $x_2$ is not minimal, so we can find $x_3$ such that $x_1 \succeq x_2 \succeq x_3$ continuing in this way we get a infinite descending chain, which contradicts well-foundedness. 
		
		Conversely, suppose that we have the well-ordering property. Suppose for contradiction, the set was no well-founded. So take an infinite descending chains
		\[
			a_1 \succeq a_2 \succeq a_3 \succeq \cdots
		\]
		Take the set of all elements in this chain $\set{ a_i \mid i\in \Z^+}$. By the well-ordering property, this has a least element, which is $a_k$ for some $k\in \Z^+$. So then the infinite descending chain must just be $a_k$ past $k$, which contradicts the chain is strictly descending. 
	\end{proof}
	
	Why is this important? It illustrates an important characteristic of $\N$: every nonempty subset of $\N$ has a least element. Now, using this property, we can prove induction. 
	
	\begin{proof}
		We want to show that induction is valid. That is
		\[
			(\phi(0) \oand (\A n \st \phi(n) \to \phi(n+1) )) \to (\A n\st \phi(n))
		\]
		
		Suppose this is false. So we have
		\[
		(\phi(0) \oand (\A n \st \phi(n) \to \phi(n+1) )) \oand (\E n\st \neg \phi(n))
		\]
		
		Well, as $\E n \st \neg \phi(n)$ we have an $m$ that satisfies $\neg \phi(m)$. In fact, we may have lots of counterexamples. Let $S$ be the set of counterexamples, ie. like $m\in S$ if and only if $\neg \phi(m)$. As $\E n \st \neg\phi(n)$ we know $S$ is nonempty. 
		
		By the well-ordering property $S$ has a least element, call it $m$. We now do cases:
		
		If $m = 0$, we get a contradiction, because we have $\phi(0)$. 
		
		Otherwise, $m = k+1$ for some $k$. Instantiating the universal statement we are assuming at $k$ and we get $\phi(k) \to \phi(k+1)$. As $m$ is least, we know $\phi(k)$ holds, and thus we know $\phi(k+1)$, ie. we know $\phi(m)$. 
	\end{proof}

	As an application, anytime we take natural numbers, we can assume that they are the smallest such. 
	
	\begin{thm}
		$\sqrt{2}$ is irrational. 
	\end{thm}
	\begin{proof}
		Suppose not; then we can find $n$ and $m$ naturals such that $\sqrt{2} = \frac{n}{m}$. We may assume that $n$ and $m$ are the least such. Then we have that $2 m^2 = n^2$. Thus $n$ is even, so $n = 2k$ for some $k\in \N$. And so $2 m^2 = 4k^2$, ie. $m^2 = 2k^2$.
		
		Then $m$ is even, so $m = 2l$ for some $l\in \N$. 
		
		So we have $m = 2l$ and $n = 2k$, so $\sqrt{2} = \frac{2l}{2k} = \frac{l}{k}$; as $l < m$ and $k < n$, we have a contradiction, as we chose these numbers as small as possible!
	\end{proof}
	
	This style of proof is called \df{proof by infinite descent}
	
	\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 a = b + 2\pi k \mbox{ for some $k\in \Z$}
		\]
		
		Geometrically, $a$ and $b$ are related if $a$ and $b$ represent the same angle.
		
		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 $ a = a + 2\pi \cdot 0$. 
			
			Next, we show that it is symmetric. Like $a,b\in \R$, and take $k$ such that $a = b + 2\pi k$. Then of course, $b = a + 2\pi (-k)$, so $b\sim a$. 
			
			Finally, suppose that $a\sim b$ and $b\sim c$. Then take $k,l\in\Z$ such that $a = b + 2\pi k$ and $b = c + 2\pi l$. Then we have $a - 2\pi k = c + 2\pi l$, an so $a = c + 2\pi( k + l )$
		\end{proof}
	\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,-4\pi, -2\pi, 0, 2\pi , 4\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}


	\newpage

	\section{Group Work}

Today, we will work in groups to talk about different relations. For each of the following relations, you should answer two questions:                                                      
\begin{itemize}                                                                               
\item Prove that it is an equivalence relation. 
\item Describe it's equivalence classes
\end{itemize}

Some are easier than others, and they are presented in what I feel is increasing difficulty.

\subsection{Complex Magnitude}

Recall the complex numbers are numbers of the form $a + b i$ where $i = \sqrt{-1}$. The \df{magnitude} of a complex number $a+bi$ is
\[
        | a + bi | = \sqrt{ a^2 + b^2 } 
\]

Define the relation $\circ$ on $\mathbb{C}$ by : If $z_1,z_2\in\mathbb{C}$ then $z_1 \circ z_2$ if and only if $|z_1| = |z_2|$

\subsection{Odd Factors}

Consider the positive integers (that is: natural numbers, without $0$). We can write every positive integer $n$  uniquely as some odd number times a power of $2$. This odd number is the largest odd number that divides $n$. For example, for $18$, the largest odd number that divides it is $9$. 

So define the relation $\equiv$ on $\Z^+$ by $n \equiv m$ if and only if $n$ and $m$ have the same largest odd number factor (for example: $9\equiv 18$, but $9\not\equiv 27$). 

\subsection{Powers of Two}

Similar as above, we have that every positive integer $n$ can be unique written as some odd numbers times a power of $2$. So we define a relation $\frown$ on the positive integers $\Z^+$ by $n\frown m$ if and only if the $n$ and $m$ have the same largest power of two (eg. $2\frown 6$, but $2\not\frown 12$) 

\subsection{Periodic Sine}

Recall that $\sin(x)$ is a function on the real numbers that takes in a real numbers, reads it as an angle, and then returns the $y$-coordinate of the point on the unit circle corresponding to that angle. This is a periodic function that has period $2\pi$. But besides its periodicity, it is still not 1-1, as $\sin(0) = \sin(\pi)$. 

So, we make a relation $\approx$ on real numbers and say $x\approx y$ if and only if $\sin(x) = \sin(y)$. 

\subsection{Differing by a Rational}

The real numbers $\R$ contain both rationals and irrationals. But, the rationals have nice closure properties (the sum and difference of two rationals is rational) where as the irrationals do not. 

So, define a relation on $\R$ by relating two numbers if they differ by a rational; that is define $\cong$ on $\R$ by $x\cong y$ if and only if $x - y \in \Q$. 

\subsection{Infinite Binary Sequence}

An \df{infinite sequence} is a sequence of numbers indexed by $\Z^+$. For example: $(2,4,6,8,10,\ldots)$ is a sequence. From the pattern, it looks like the $6$th element of the sequence is $12$. 

An \df{infinite binary sequence} is a sequence of just $0$'s and $1'$. For example $(1,0,1,0,1,0,1,\ldots)$ is a sequence, where it looks like the $i$th element of the sequence of $1$ if $i$ is odd and $0$ if $i$ is even. 

We write sequence as $(a_n)_{n\in\Z^+}$, and then we say $a_i$ when referring to the $i$th element of the sequence. So, if we name the first sequence above $(b_i)_{i\in\Z^+}$, then we would say $b_1 = 2$ and $b_6 = 12$. 

We define $\sim$ on the set of infinite binary sequences as follows: 

\[
	(a_n)_{n\in\Z^+} \sim (b_n)_{n\in\Z^+} \iff \E N\in \Z^+ \st \A m > N \stt a_m = b_m
\]
That is, two binary sequences are equivalent if they are ``eventually equal,'' ie. there is a point for which after then they are equal. For example, 
\[
	(1,0,1,1,0,0,0,0,0,\ldots) \sim (1,1,0,0,0,0,0,0,\ldots)
\]
Where both of the above sequences continue to be $0$'s forever. 


\end{document}
