\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage{color}
\usepackage{verbatim}
%%% Margins
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}
%%% Environments %%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{define}{Definition}
\newtheorem{remark}[define]{Remark}
\newtheorem{example}{Example}
\newtheorem{question}{Question}
\newtheorem{algorithm}{Algorithm}
\numberwithin{equation}{section}
%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\begin{document}
\pagestyle{empty}
\begin{center}
{\large MATH 108 Winter 2019 \ - \ {\bf Problem Set 4}}
% Put your name and section here.
{\large due February 8}
\end{center}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Nim is a two-player game involving piles of coins. The players alternate taking turns, and on each turn the player chooses a nonempty pile and chooses a positive number of coins to remove from that pile. This continues until there are no coins left. In this version of Nim, at the start of the game there are two piles, each with $n$ coins. Whoever takes the last coin loses. Prove by induction that for all $n \geq 2$, the second player has a winning strategy, i.e. they can always win no matter what the first player does.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For positive integers $a$ and $b$, the {\em greatest common divisor} of $a$ and $b$ is the largest postive integer that divides both $a$ and $b$, denoted $\gcd(a,b)$.
For $p$ a prime number, prove that $p$ divides $a$ and $p$ divides $b$ if and only if $p$ divides $\gcd(a,b)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For positive integers $a$ and $b$ with $\gcd(a,b) = d$, prove that
\[ \{as + bt \mid s,t \in \ZZ\} = d\ZZ. \]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For each relation, list which of the following properties it has: symmetric, antisymmetric, transitive, reflexive, irreflexive.
\begin{enumerate}
\item $\leq$ on $\ZZ$.
\item $\neq$ on $\ZZ$.
\item $\subseteq$ on $\mathcal{P}(\ZZ)$.
\item ``is the child of'' on people.
\item $\{(1,5),(5,1),(1,1)\}$ on $A = \{1,2,3,4,5\}$.
\item $\{(x,y) \in \ZZ \times \ZZ \mid x+y = 10\}$ on $\ZZ$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Let $A = \{1,2,3,4,5\}$ and let $\sim$ be the relation on $\mathcal{P}(A)$ defined by $S \sim T$ if $|S| = |T|$. Prove that $\sim$ is an equivalence relation. How many equivalence classes does $\sim$ have and how big is each class?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Let $R$ and $S$ be relations on $A$. The {\em composition} of $R$ and $S$, denoted $R \circ S$, is defined as
\[ R \circ S = \{(x,z) \in A \times A \mid \exists y \in A \text{ with } x \mathbin{R} y \text{ and } y \mathbin{S} z \}. \]
\begin{enumerate}
\item Find a counterexample to the following statement: If $R$ and $S$ are symmetric, then $R \circ S = S \circ R$.
\item Prove that $R$ is transitive if and only if $R \circ R \subseteq R$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Find an equivalence relation on $\NN_1$ with set of equivalence classes equal to each partition.
\begin{enumerate}
\item $\{\{1,4,7,\ldots\},\{2,5,8,\ldots,\},\{3,6,9,\ldots\}\}$.
\item $\{\{1,2\},\{3,4\},\{5,6\},\{7,8\},\ldots\}$.
\item $\{\{1\},\{2,3\},\{4,5,6,7\},\{8,\ldots,15\},\{16,\ldots,31\},\ldots\}$.
\item $\{\NN_1\}$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{enumerate}
\end{document}