\documentclass{article}
\input{../preamble.tex}
\title{Exam 2 - Technique Questions}
\date{June 18, 2012}
\begin{document}
\maketitle
The following are Exam 2 technique questions. Of this list, you will be asked to prove a specific few of them on the exam. This will constitute the majority of the points on Exam 2. Therefore, it is highly advised that you know these questions very well. It is not advised that you simply memorize the proof, as there are too many problems here to make that feasible.
You are welcome to study these problems with each other, and use any resources as per the Homework Resource Policy on the syllabus. You may not ask me any questions about them specifically except if you think there is an error or poor phrasing. However, as always, if you feel like you are having difficulties with a concept, you should come to me for help.
\begin{enumerate}
\item Suppose that $R$ is a symmetric and transitive relation on $S$. Prove that the following are equivalent:
\begin{enumerate}
\item $R$ is reflexive.
\item For every $a\in S$ there is a $b\in S$ such that $aRb$.
\end{enumerate}
\item Define the relation $\sim$ on $\Z$ by
\[
a\sim b \iff \gcd(a,b) \neq 1
\]
Is $\sim$ an equivalence relation? Justify your answer. If it is, describe the equivalence classes.
\item Define the relation $\sim$ on $\Z$ by
\[
a\sim b \iff a^2 = b^2
\]
Is $\sim$ an equivalence relation? Justify your answer. If it is, describe the equivalence classes.
\item Fix a nonempty set $\Omega$. Define a relation $\iso$ on $\wp(\Omega)$ by
\[
A \iso B \iff A \sbs B
\]
Is $\iso$ an equivalence relation? Justify your answer. If it is, describe the equivalence classes.
\item Prove if $a \equiv b \mod n$ then $a^2 \equiv b^2 \mod n$
\item State and Prove Fermat's Little Theorem (Question 1 on Homework 5).
\item Let $f:A \to B$. Prove that for all $X,Y\sbs A$
\[
f[X\cup Y] = f[X]\cup f[Y]
\]
\item Let $f:A\to B$. Prove that for every $X,Y\sbs A$
\[
f[X\minus Y] \sps f[X]\minus f[Y]
\]
Show that equality need not hold. Show that equality holds if $f$ is injective.
\item Let $f:\Z_6 \to \Z_2$ by
\[
f([x]_6) = [x]_2
\]
Prove that $f$ is well defined. Is it surjective? Injective?
\item Let $f:\Z_2 \to Z_6$ by
\[
f([x]_2) = [x]_6
\]
Show that $f$ is not a well-defined function.
\item Let $f:\Z^+ \times \Z^+ \to \Z^+$ by
\[
f(a,b) = a+b
\]
Is $f$ surjective? Injective?
\item Fix $A,B$ nonempty sets. Define $f:\wp(A\cup B) \to \wp(A)$ by
\[
f(X) = X\cap A
\]
Show that $f$ is well-defined. Is it surjective? Injective?
\item Let $f:A\to B$. Prove that the following are equivalent:
\begin{itemize}
\item $f$ is not surjective.
\item $\E C\sbs B \stt (B\minus C\neq \emptyset) \oand ( f^{-1}[C] = A )$
\end{itemize}
\item Suppose $f:A\to A$. Prove that $f$ is injective if and only if $f\circ f$ is injective.
\item Suppose that $f:A\to B$ and $g: B\to C$. Prove that if $g\circ f$ is injective then $f$ must be injective. Show that the converse is not true, in general.
\item Suppose that $f:A\to B$ and $g: B\to C$. Prove that if $g\circ f$ is surjective then $g$ must be surjective. Show that the converse is not true, in general.
\item Fix a function $f:A\to B$. Define a relation $\sim$ on $A$ by
\[
a\sim b \iff f(a) = f(b)
\]
Prove that $\sim$ is an equivalence relation. What are the equivalence classes if $f$ is injective?
\item Fix a function $f:A\to B$ Define a relation $\sim$ on $B$ by
\[
a \sim b \iff f^{-1}[\s{a}] = f^{-1}[\s{b}]
\]
Prove that $\sim$ is an equivalence relation. What are the equivalence classes? What are the equivalence classes if $f$ is surjective?
\item Prove that $\N\times\N$ is countable.
\item Let $S$ be the set of infinite binary sequence, ie. sequences of $0$'s and $1$'s indexed by natural numbers. Prove that $|S\times S| = |S|$.
\item Construct an explicit bijection between (0,1) and [1,2].
\item Prove that the set $\set{ x\in \R \mid \sin(x) = \cos(x) }$ is countable. Does this imply that $\set{x\in \R \mid \sin(x) \neq \cos(x) }$ is uncountable? Why or why not?
\end{enumerate}
\end{document}