\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,hyperref,enumitem,amsthm,cancel}

%\usepackage[margin=1.0in]{geometry}

\newtheorem{theorem}{Theorem}

\theoremstyle{definition}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}

\author{Math 300 -- Spring 2019 (Hachtman)}
\title{Solutions to Assignment 4}

\begin{document}
\maketitle

\begin{proposition} Let $B$ be the relation on the set of people: $x \mathbin{B} y$ iff $x$ and $y$ have the same birthday.
  
  Then $B$ is an equivalence relation.
\end{proposition}

\begin{proof}
  It is clearly reflexive, as every person has one and only one birthday, which is clearly the same birthday as their own birthday!  
  
  If $x$ and $y$ are people that have the same birthday, then of course $y$ and $x$ have the same birthday; so $B$ is symmetric.
  
  Finally, if $x$ and $y$ both have the same birthday, and $y$ and $z$ both have the same birthday, then all three share the same birthday (since everyone has exactly one birthday); so $x \mathbin{B} z$.  This shows $B$ is transitive.
  
  We have verified the three defining properties of being an equivalence relation.
\end{proof}

\begin{proposition} Let $C$ be a relation on the set of people, defined by $x \mathbin{C} y$ iff $x$ and $y$ have citizenship in the same country.
 \end{proposition} 

\begin{proof}  $C$ is \emph{not} an equivalence relation.  The point is that, unlike the case with birthdays, someone need not have citizenship in a \emph{unique} country (there is such a thing as \emph{dual} citizenship).  We will see how it follows that $C$ is not transitive.
  
  I am a U.S.\ citizen.  Actress Salma Hayek, known for her roles in such  films as \emph{Desperado}, \emph{Frida} and \emph{Wild Wild West}, is a dual Mexican-American citizen; so Salma Hayek and I have citizenship in the same country: Sherwood $\mathbin{C}$ Salma Hayek.  
  
  Also, director Guillermo del Toro (\emph{Hellboy}, \emph{Pacific Rim}) is a sole citizen of Mexico.  So Salma Hayek $\mathbin{C}$ Guillermo del Toro.
  
  But Sherwood ${\mathbin{\cancel{C}}}$ Guillermo del Toro.  So $C$ is not transitive.

  (Note that $C$ is not even reflexive, as can be seen by the existence of \emph{stateless persons} who have no recognized nationality; for example, Albert Einstein was a stateless person from 1896 to 1901.)
 \end{proof}

\begin{proposition} Let, for $x,y \in \mathbb{R}$, $x \mathbin{R} y$ iff $x-y$ is a rational number.

Then $R$ is an equivalence relation.
\end{proposition}
\begin{proof}
  $R$ is reflexive: for any real  number, $x-x = 0 \in \mathbb{Q}$.
  
  $R$ is symmetric: Suppose $x-y = q \in \mathbb{Q}$.  Then $y-x = -(x-y) = -q$, which is rational.
  
  Finally, we show $R$ is transitive.  Suppose $x,y,z$ are reals with $x \mathbin{R} y$ and $y \mathbin{R} z$.  Let $q = x-y$ and $r = y-z$; so $q,r$ are rationals.  Then
    \[
      x-z = (x-y)+(y-z) = q + r.
    \]
Since $\mathbb{Q}$ is closed under addition, we have $q+r \in \mathbb{Q}$, so that $x \mathbin{R} z$.  This shows $R$ is transitive.

  Since $R$ is reflexive, symmetric, and transitive, we have that $R$ is an equivalence relation.
\end{proof}
  
\begin{proposition} Let, for $\mathbf{u}, \mathbf{v}\in\mathbb{R}^3$,  $\mathbf{u} \mathbin{S} \mathbf{v}$ iff $\mathbf{u} \cdot \mathbf{v} = 0$.  Then $S$ is not an equivalence relation.
\end{proposition}
\begin{proof}
  Much like the citizenship example, $S$ is neither reflexive nor transitive (but is symmetric).
  
  To see $S$ is not reflexive, consider $\mathbf{u} = \langle 1, 2, 3 \rangle$.  Then 
   \[
   \mathbf{u}\cdot \mathbf{u}  = \langle 1, 2, 3 \rangle \cdot \langle 1, 2, 3 \rangle = 1^2 + 2^2 + 3^2 = 15 \neq 0,
   \]  
so $\mathbf{u} \cancel{\mathbin{S}} \mathbf{u}$.  (Note the same argument shows $\mathbf{u} \cancel{\mathbin{S}} \mathbf{u}$ whenever $\mathbf{u}$ does not equal the zero vector $\mathbf{0}= \langle 0,0,0 \rangle$.
\end{proof}

\end{document}