\newlec

\hdc

Consider the following statement.
\[ \{2k : k \in \mathbb{N}\} \supseteq \{n \in \mathbb{Z} : 8 \mid (n+4)\} \]

A well written and correct direct proof of this statement could begin with

\begin{enumerate}[A)]
\item We will show that the statement is true in both directions.
\item Assume that $8 \mid 2n$ where $n$ is an integer.
\item Let $m \in \{n \in \mathbb{Z} : 8 \mid (n+4)\} $. %Correct
\item Let $m \in \{2k: k \in \mathbb{N}\}$.
\item Assume that $8 \mid (2k+4)$.
\end{enumerate}

\vskip3em
\soln Let $m \in \{n \in \mathbb{Z} : 8 \mid (n+4)\} $.

\ic{This is the 5 minute mark}

\newpage

\hdc

Notes:
\vskip1em
\begin{enumerate}
\item A single counter example proves that $(\forall x \in S, P(x))$ is false.
\vskip0.1em
Claim: Every positive even integer is composite.
\vskip0.1em
 This claim is false since $2$ is even but $2$ is prime.
\item A single example does not prove that $(\forall x \in S, P(x))$ is true.
\vskip0.1em
Claim: Every even integer at least 4 is composite. 
\vskip0.1em
This is true but we cannot prove it by saying "6 is an even integer and is composite." We must show this is true for an arbitrary even integer $x$. (Idea: $2 \mid x$ so there exists a $k \in \mathbb{N}$ such that $2k=x$ and $k \neq 1$.)
\item A single example does show that $(\exists x \in S, P(x))$ is true.
\vskip0.1em
Claim: Some even integer is prime. 
\vskip0.1em
This claim is true since $2$ is even and $2$ is prime.
\item What about showing that $(\exists x \in S, P(x))$ is false?
\vskip0.1em
Idea:  $(\exists x \in S, P(x))$ is false  $\equiv \forall x\in S, \neg P(x)$ is true. This idea is central for proof by contradiction which we will see later.
\end{enumerate}
\vskip3em

\ic{This is the 10-13 minute mark}

\newpage
\textbf{Negating Quantifiers}
\ex Negate the following:
\begin{enumerate}
\item Everybody in this room was born before 2010.
\vskip0.1em
\soln Somebody in this room was not born before 2010.
\item Someone in this room was born before 1990
\vskip0.1em
\soln Everyone in this room was born after 1990.
\item $\forall x \in \mathbb{R}, |x| < 5$
\vskip0.1em
\soln $\neg (\forall x \in \mathbb{R}, |x| < 5) \equiv \exists x \in \mathbb{R}, |x| \geq 5 $
\item $\exists x \in \mathbb{R}, |x| \leq 5$
\vskip0.1em
\soln $\neg (\exists x \in \mathbb{R}, |x| \leq 5) \equiv \forall x \in \mathbb{R}, |x| > 5 $
\end{enumerate}

\ic{Let them validate the truth of the above statements. This could take you to the 20 minute mark easily}

\note A proof that a statement is false is called a disproof.
\vskip1em
\ex Prove or disprove: Let $a,b,c \in \mathbb{Z}$. If $a \mid bc$ then $a \mid b$ or $a \mid c$.
\vskip1em
\soln This is false! A counter example is given by $a=6$, $b=2$ and $c=3$. Then $a \mid bc$ BUT $6 \nmid 2$ and $6\nmid 3$.
\vskip1em
\note It turns out that this is true if you require additionally that $a$ is prime. This is called Euclid's Lemma. We'll see a proof of this in 5 weeks. It is actually very nontrivial to prove.

\ic{ Get them to think about the prime condition. The proof of this requires GCDs in the prime case to the best of my knowledge. This is the 27 minute mark.}



\newpage
\hdc

\thispagestyle{empty}
Which of the following are true?
\begin{enumerate}
\item $\forall x\in\mathbb{R}, \forall y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\exists x\in\mathbb{R}, \exists y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\forall x\in\mathbb{R}, \exists y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\exists x\in\mathbb{R}, \forall y \in \mathbb{R}, x^{3}-y^{3}=1$
\end{enumerate}

\vskip3em
\soln
\begin{enumerate}
\item False (Choose $x=y=0$)
\item True (Choose $x=1$ and $y=0$)
\item True. 
\vskip1em
\pf Let $x \in \mathbb{R}$ be arbitrary. then choose $y = \sqrt[3]{x^{3}-1}$. Then 
\[
x^{3}-y^{3} = x^{3} - (\sqrt[3]{x^{3}-1})^{3} = x^{3} -(x^{3} -1) = 1
\]
\item False. Idea: Negate and show the negation is true!
\[
\neg(\exists x\in\mathbb{R}, \forall y \in \mathbb{R}, x^{3}-y^{3}=1) \equiv \forall x\in\mathbb{R}, \exists y \in \mathbb{R}, x^{3}-y^{3}\neq1
\]
\pf Let $x \in \mathbb{R}$ be arbitrary. Take $y=x$. Then $x^{3} - y^{3} = x^{3} - x^{3} = 0 \neq 1$. 
\end{enumerate}
\ic{This is the 40 minute mark}

\newpage

\hdc

List all elements of the set:
\small{
\begin{align*}
\{ n\ \in \mathbb{Z} &: n > 1 \wedge ((m \in \mathbb{Z} \wedge m > 0 \wedge m \mid n) \Rightarrow (m=1 \vee m=n))\}  \cap \{n \in \mathbb{Z} : n \mid 42\} 
\end{align*}}

\vskip3em

\soln The first set is the set of all primes. The second set is the set of all divisors of 42, namely $$\{\pm1 , \pm2, \pm3, \pm6, \pm7, \pm14, \pm21, \pm42\}.$$
The intersection is therefore $\{2,3,7\}$.

\newpage

Check out \url{http://www.cemc.uwaterloo.ca/~cbruni/Math135Resources.php} for symbol cheat sheets and theorem cheat sheets and other goodies!

\ic{End of class}

