\documentclass[11 pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\title{Foundations of Mathematics Exam 1 Take-Home Corrections}
\author{Sarah Moroney}
\date{November 5, 2018}
\begin{document}
\begin{titlepage}
\maketitle
\thispagestyle{empty}
\begin{center}
\end{center}
\end{titlepage}
\noindent 2. Let $x,y \in \mathbb{R}$. Prove or disprove the following statements.\par
\noindent (a) If both $x$ and $y$ are irrational, then $xy$ is rational.\par
\smallskip
This statement is false and can be disproven by providing a counterexample: If $x =\sqrt{2}$ and $y=\sqrt{3}$, then $xy = \sqrt{6}$, which is irrational.\par
\smallskip
\noindent (b) If exactly one of $x$ and $y$ is rational, then $x+y$ is irrational.\par
\smallskip
\begin{proof}
We will use the method of proof by contradiction to show that if exactly one of $x$ and $y$ is rational, then $x+y$ is irrational. Suppose $x+y$ is rational, so $x+y=\frac{a}{b}$ where $a$ and $b$ are integers and $b \neq 0$ by the definition of rational numbers. Rearranging, we obtain $y =\frac{a}{b} - x$. Let $x$ be a rational number $\frac{c}{d}$ where $c$ and $d$ are integers and $d \neq 0$. We then have $y =\frac{a}{b} - \frac{c}{d}$. The number $bd$ is an integer and since both $b$ and $d$ are integers and the product of two integers is an integer.The number $bd$ is also non-zero since both $b$ and $d$ are non-zero. The number $ab-cd$ is an integer since $a, b, c$, and $d$ are integers, the product of two integers is an integer, and subtracting two integers results in an integer. Therefore, $y = \frac{ad-bc}{bd}$ and $y$ is rational since the form $\frac{ad-bc}{bd}$ fits the definition of a rational number $(\frac{p}{q}$, where $p,q \in \mathbb{Z}$ and $q\neq0)$. This is a contradiction of our assumption that $y$ is irrational, so we must conclude that if exactly one of $x$ and $y$ is rational, then $x+y$ is irrational.
\end{proof}
\noindent 3. Let $A, B$, and $C$ be sets. Determine if the following is true or false.\\
(a) $(B \setminus A)=(C \setminus A)$ if and only if $B = C$.\par
\smallskip
Statement (a) is false, since we can provide a counterexample. Let $A = \{2, 3\}$, $B = \{1\}$, and $C = \{1,3\}$. Then, $B \setminus A = \{1\}$ and $C \setminus A=\{1\}$. Therefore, there exists a $(B \setminus A)=(C \setminus A)$ such that $B \neq C$.\par
\smallskip
\noindent (b) $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$\par
\smallskip
Statement (b) is true.
\begin{proof}
We will use the method of proof in cases to show that $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$.\par
\smallskip
The statement $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$ means that $(A \cup B) \setminus (A \cap B) \subseteq (A \setminus B) \cup (B \setminus A)$ and $(A \setminus B) \cup (B \setminus A) \subseteq (A \cup B) \setminus (A \cap B)$. Thus, we must prove both containments in order to assert that the original statement is true.\par
\smallskip
First, we will show that $(A \setminus B) \cup (B \setminus A) \subseteq (A \cup B) \setminus (A \cap B)$. Let $x \in (A \setminus B) \cup (B \setminus A)$. This is equivalent to the statement that $x \in A \setminus B$ or $x \in B \setminus A$ by the definition of a union of sets. Therefore, we may proceed by breaking the above into cases:\par
\smallskip
Assume that $x \in A\setminus B$. Then, $x \in A$ and $x \notin B$ by the definition of a set difference. This implies that $x \in A\cup B$ and $x \notin A\cap B$, which means that $x \in (A\cup B)\setminus (A\cap B)$. Thus, we have shown that $(A \cup B) \setminus (A \cap B) \subseteq (A\cup B)\setminus (A\cap B)$ in this case. \par
\smallskip
Next, suppose that $x \in B\setminus A$. Then $x \in B$ and $x \notin A$. This implies that $x \in A\cup B$ and $x \notin A\cap B$, which means that $x \in (A\cup B)\setminus (A\cap B)$. Thus, we have that $(A \cup B) \setminus (A \cap B) \subseteq (A\cup B)\setminus (A\cap B)$ in this case.\par
\smallskip
Lastly, assume that $x \in A \setminus B$ and $x \in B \setminus A$. This is equivalent to the statement that $x \in (A \setminus B)\cap (B \setminus A)$. The sets $A \setminus B$ and $B \setminus A$ are disjoint, so their intersection is the empty set. Assume to the contrary that $(A \setminus B)\cap (B \setminus A) \neq \emptyset$. Let $A=\{x, y\}$ and $B =\{y, z\}$, where $x,y$,and $z$ are arbitrary elements of the sets $A$ and $B$. Then, $A\setminus B=\{x\}$ and $B \setminus A = \{z\}$. This means $(A \setminus B)\cap (B \setminus A) = \emptyset$, and we have a contradiction. Therefore, we must conclude that $x \in A \setminus B$ and $x \in B \setminus A = \emptyset$. The empty set is a subset of all other sets, so we have proven that $(A \cup B) \setminus (A \cap B) \subseteq (A\cup B)\setminus (A\cap B)$ for this case.
\par
\smallskip
Taking into account all of the above cases, we can conclude that $(A \setminus B) \cup (B \setminus A) \subseteq (A \cup B) \setminus (A \cap B)$, and we have proven the first containment.\par
\smallskip
Next, we will show that $(A \cup B) \setminus (A \cap B) \subseteq (A \setminus B) \cup (B \setminus A)$. Let $y \in (A \cup B) \setminus (A \cap B)$. This is equivalent to stating that $y \in A$ or $y \in B$ and $y \notin A$ and $y \notin B$. This implies that $y \in A$ and $y \notin B$ or $y \in B$ and $y \notin A$, which is equvalent to the statement $(A \setminus B) \cup (B \setminus A)$ by the definitions of the set operations. Thus, we have proven the second containment and can conclude that $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$.
\end{proof}
\noindent 4. Prove the following.\\
Let $x$ and $y$ be integers. If $x + y$ is even, then either both $x$ and $y$ are even or both $x$ and $y$ are odd.
\begin{proof}
We will use proof by contrapositive to show that if $x + y$ is even, then either both $x$ and $y$ are even or both $x$ and $y$ are odd. The contrapositive is: ``If exactly one of $x$ and $y$ is even and the other is odd, then $x+y$ is odd.'' Let $x = 2n$ and $y = 2m+1$ where $n$ and $m$ are integers. Then we have $x + y = 2n +2m +1$, which is equal to $2(n+m)+1$, which is of the form $2k +1$ where $k \in \mathbb{Z}$ (the definition of an odd number). The quantity $n+m \in \mathbb{Z}$ since the sum of two integers is an integer. Therefore, we have proven the contrapositive and can assert that the original statement is also true.
\end{proof}
\noindent 5. Consider the result given in \#4.\\
(a) State the converse of the statement given in \#4.\par
\smallskip
Converse: If either both $x$ and $y$ are even or both $x$ and $y$ are odd, then \par $x+y$ is even.\par
\smallskip
\noindent (b) Is the converse of the statement given in \#4 true or false?\par
\smallskip
The converse of the statement given in \#4 is true.
\begin{proof}
We will use proof by cases to show that if If either both $x$ and $y$ are even or both $x$ and $y$ are odd, then $x+y$ is even.\par
\smallskip
First, suppose that $x$ and $y$ are both even. Then $x = 2n$ and $y = 2m$ for some integers $n$ and $m$. Therefore, $x + y = 2n + 2m$, which is equal to $2(n + m)$ where $n+m \in \mathbb{Z}$ since the sum of two integers is an integer. Therefore, $x + y$ is even and the result is proven in this case.\par
\smallskip
Then, suppose that both $x$ and $y$ are odd. Then $x = 2n + 1$ and $y = 2m + 1$ for some integers $n$ and $m$. Therefore,
$x + y = 2n + 2m + 2$, which equals $2(n + m + 1)$ where $n+m+1 \in \mathbb{Z}$ since the sum of several integers is also an integer. Therefore, $x + y$ is even and the result is proven in this case.\par
\smallskip
Thus, we have shown that for all applicable cases, both $x$ and $y$ being even or both $x$ and $y$ being odd implies that $x+y$ is even.
\end{proof}
\noindent 6. Prove that $\sqrt{3}$ is irrational.
\begin{proof}
We will use proof by contradiction to show that $\sqrt{3}$ is irrational, and therefore assume to the contrary that $\sqrt{3}$ is rational. Let $\sqrt{3} = \frac{p}{q}$, where $p$ and $q$ are integers and $q \neq 0$. We may also assume that $p$ and $q$ have no common factors. From the equality $\sqrt{3} = \frac{p}{q}$, we can obtain $\sqrt{3}q = p$ by multiplying both sides by $q$. Squaring both sides produces the equality $3q^2 = p^2$, which implies that $p^2$ is divisible by 3. \par
\smallskip
An integer $n$ has a remainder of 0,1, or 2 when divided by 3. Thus, for some integer $k$, $n=3k$, $n=3k+1$, or $n=3k+2$. If we square each value of n, we have $n^2=(3k)^2 =9k^2$, $n^2 = (3k+1)^2 = 9k^2+6k+1$, and $n^2 = (3k+2)^2=9k^2+12k+4$. The only case for which $n^2$ is divisible by 3 is when $n=3k$, so if $n^2$ is divisible by 3, then $n$ must also be divisible by 3.\par
\smallskip
Therefore, since the divisibility of the square of an integer by 3 implies that the integer itself is also divisible by 3, $p = 3n$ for some integer $n$ and we have $3q^2 = (3n)^2$. This tells us that $p$ and $q$ have a common factor of 3, which is a contradiction since we made the assumption that $p$ and $q$ have no common factors. Thus, we must conclude that $\sqrt{3}$ is irrational.
\end{proof}
\noindent 7. Let $n \in \mathbb{Z}$. Prove that 3 divides $(2n^2 + 1)$ if and only if 3 does not divide $n$.
\begin{proof}
We will use the methods of proof by contrapositive and proof to show that 3 divides $(2n^2 + 1)$ if and only if 3 does not divide $n$. The statement is a logical biconditional, so we must show that 3 divides $(2n^2 + 1)$ if 3 does not divide $n$ and that 3 does not divide $n$ if 3 divides $(2n^2 + 1)$ in order to prove the result.\par
\smallskip
First, we will show that if 3 divides $(2n^2 + 1)$, then 3 does not divide $n$ using proof by contrapositive. The contrapositive of this statement is: "If 3 divides $n$, then 3 does not divide $(2n^2 + 1)$." A nonzero integer $a$ divides an integer $b$ if there exists an integer $k$ such that $b=ak$. Using this definition, if we assume that 3 divides $n$, we have $n=3k$, where $k$ is an integer. \par
\begin{align*}
n&=3k\\
2n&=6k\\
2n^2&=(6k)^2=36k^2\\
2n^2 + 1&=36k^2 + 1 = 3(12k^2+\frac{1}{3})
\end{align*}
The number 3 does not divide $2n^2 + 1$ if $2n^2 + 1 \neq 3m$, where $m$ is an integer, which is the case since an integer added with a fraction is not an integer. Thus, 3 does not divide $2n^2 + 1$, and we have proven the contrapositive. Therefore, we can infer that the original statement is true.\par
\smallskip
Then, we will show that if 3 does not divide $n$, then 3 divides $(2n^2 + 1)$ using the method of proof by cases. \par
\smallskip
\noindent First, suppose that $n = 3m +1$, where $m$ is an integer. Then, we have:
\begin{align*}
n &= 3m +1\\
n^2&=(3m+1)^2=9m^2+6m+1\\
2n^2&=2(9m^2+6m+1)=18m^2+12m+2\\
2n^2 + 1&=18m^2+12m+3 = 3(6m^2+4m+1)
\end{align*}
The expression $2n^2 + 1=3(6m^2+4m+1)$ implies that if $n = 3m +1$, then 3 divides $(2n^2 + 1)$, since $2n^2 + 1=3(6m^2+4m+1)$ is of the form $b=3k$, where $k$ is an integer. We can assert that $k = 6m^2+4m+1$ is an integer in this case because multiplying and adding integers always results in an integer. Thus, we have proven the result in this case.\par
\smallskip
\noindent Next, suppose that $n =3t+2$, where $t$ is an integer. Then, we have:
\begin{align*}
n &=3t+2\\
n^2&=(3t+2)^2=9t^2+12t+4\\
2n^2&=2(9t^2+12t+4) = 18t^2+24t+8\\
2n^2+1&= 18t^2+24t+9 = 3(6t^2+8t+3)
\end{align*}
The expression $2n^2 + 1=3(6t^2+8t+3)$ implies that if $n =3t+2$, then 3 divides $(2n^2 + 1)$, since $2n^2 + 1=3(6t^2+8t+3)$ is of the form $b=3k$, where $k$ is an integer. We can assert that $k = 6t^2+8t+3$ is an integer in this case because multiplying and adding integers always results in an integer. We have now established the result for all possible cases where $n \neq 3m$, since an integer $n$ only has non-zero remainders of 1 and 2 when divided by 3.\par
\smallskip
\noindent Both directions of the implication have been proven, and thus we can conclude that 3 divides $(2n^2 + 1)$ if and only if 3 does not divide $n$.
\end{proof}
\end{document}