\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 16 Questions}
\begin{document}
\maketitle
\begin{enumerate}
\item [1.] Let $A=\{1, 2, 3, 4, 5, 6\}$ and $B=\{\pi, e, \sqrt{2}\}$. Define a function $f:A \rightarrow B$ by
\begin{center}
$f(1)=f(2)=f(4)=\pi$ \hskip 0.3in $f(5)=e$ \hskip 0.3in $f(3)=f(6)=\sqrt{2}$
\end{center}
Give a relation $\mathcal{R}$ on $A$ with the property that $a\mathcal{R}b \iff f(a)=f(b)$. That is, list out the elements of $\mathcal{R}$.
\vskip 0.2in
{\bf Solution:} The relation is
$$\mathcal{R}=\{(1,1),(2,2),(4,4),(1,2),(2,1),(1,4),(4,1),(2,4),(4,2),(5,5),(3,3),(6,6),(3,6),(6,3)\}$$
A more abstract way this could be written is
$$(f^{-1}(\pi)\times f^{-1}(\pi))\cup (f^{-1}(e)\times f^{-1}(e))\cup (f^{-1}(\sqrt{2})\times f^{-1}(\sqrt{2}))$$
\vskip 0.2in
\item [2.] Prove the following statement: For an equivalence relation $\mathcal{R}$ on $A$, $a\mathcal{R}b \iff [a]_{\mathcal{R}}=[b]_{\mathcal{R}}$.
\vskip 0.2in
\begin{proof}
First, suppose $a\mathcal{R}b$ (and so also $b\mathcal{R}a$, by symmetry). Pick any $x\in [a]_{\mathcal{R}}$. Then $a\mathcal{R}x$. Since $b\mathcal{R}a$, it follows by transitivity that $b\mathcal{R}x$, and so $x\in [b]_{\mathcal{R}}$. Thus, $[a]_{\mathcal{R}}\subseteq [b]_{\mathcal{R}}$. A similar argument shows $[b]_{\mathcal{R}}\subseteq [a]_{\mathcal{R}}$. So $[a]_{\mathcal{R}}=[b]_{\mathcal{R}}$.
\vskip 0.2in
Now suppose that $[a]_{\mathcal{R}}=[b]_{\mathcal{R}}$. By the reflexive property, $b\mathcal{R}b$, so $b\in [b]_{\mathcal{R}}$. So $b\in [a]_{\mathcal{R}}$. Thus, $a\mathcal{R}b$.
\end{proof}
\vskip 0.2in
\item [3.] Let $\mathcal{R}$ be an equivalence relation on $A$, and consider the function $f:A \rightarrow A/\mathcal{R}$ defined by $f(a)=[a]_{\mathcal{R}}$. Suppose that $f$ is injective. Then what can you say about $\mathcal{R}$?
\vskip 0.2in
{\bf Solution:} If $f$ is injective, then for any two distinct elements $a, b\in A$, $f(a)\neq f(b)$. So, from the previous question, this means $a$ and $b$ are not related by $\mathcal{R}$. Hence, this means $\mathcal{R}$ consists of only pairs $(a,a)$.
\vskip 0.2in
\item [4.] Consider the function $f:\mathbb{Z}_5 \rightarrow \mathbb{Z}_5$ given by $f([x])=[3x+1]$. Prove that $f$ is both injective and surjective. (Note: you only need to prove one of injectivity and surjectivity to deduce the other. Why?)
\vskip 0.2in
\begin{proof}[Proof 1]

If $x\equiv 0\pmod{5}$ then $x=5k$ for some integer $k$. Then $3x+1=15k+1\equiv 1\pmod{5}$. Thus, $f([0])=[1]$. Similarly, one can show that $f([1])=[4]$, $f([2])=[2]$, $f([3])=[0]$, and $f([4])=[3]$. Thus, the function is explicitly seen to be bijective.
\end{proof}
\begin{proof} [Proof 2]
We prove that the function is injective. We must show that if $f([x])=f([y])$, then $[x]=[y]$. Suppose that $x, y \in \mathbb{Z}$ are such that $f([x])=f([y])$, i.e. $[3x+1]=[3y+1]$. Then $3x+1\equiv 3y+1\pmod{5}$, so $3x\equiv 3y\pmod{5}$. Then $5\mid 3(x-y)$. Thus, $5\mid x-y$, so $x\equiv y\pmod{5}$ and so $[x]=[y]$. So $f$ is an injective function.

Now we prove the function is surjective. Pick any $x\in\mathbb{Z}$. We claim that $f([2x-2])=[x]$. Indeed,
$$f([2x-2])=[3(2x-2)+1]=[6x-5]=[x+5(x-1)]=[x]$$
\end{proof}
\vskip 0.2in
\item [5.] Let $A=\mathbb{R}$, and consider the equivalence relation $\mathcal{R}$ on $A$ given by $a\mathcal{R}b$ iff $b-a\in\mathbb{Z}$. How many equivalence classes are there? Can you describe them?
\vskip 0.2in
{\bf Solution:} There are infinitely many equivalence classes, each represented uniquely by a real number in the interval $[0,1)$. For example, $2.37, 5.37,$ and $-0.63$ are all elements in the equivalence class $[0.37]$. For any real number $x$, its representative in the interval $[0,1)$ is called its \emph{fractional part}, and is often denoted $\{x\}$.

You can imagine the set of equivalence classes as the interval $[0,1)$, but when you approach the right endpoint $1$, you are instantly transported back to $0$.
\vskip 0.2in
\item [6.] Let $A$ be the set of lines in $\mathbb{R}^2$, and consider the equivalence relation where two lines are equivalent if they are either the same line, or are parallel. How many equivalence classes are there? Can you describe them?
\vskip 0.2in
{\bf Solution:} Again, there are infinitely many equivalence classes. Each line is equivalent to one through the origin (you can translate a line and it remains parallel), so there is one equivalence class for each line through the origin. (You might think this means there is one equivalence class for each \emph{direction} (i.e. each unit-length vector) going radially outward from the origin, but that's not quite true, because opposite vectors are represented by the same line!)

Here's one way to think of it: any line through the origin is the graph of the equation $y=ax$ where $a$ is its slope, unless the line is vertical (in which case the equation is $x=0$). So you have one line for every real number, and then an additional `$\infty$' line. Meaning the set of equivalence classes is $\mathbb{R} \cup \{\infty\}$. ($\{\infty\}$ is a one-element set where we are calling the element `$\infty$'.)
\end{enumerate}
\end{document}