Homework 3 was due on Thursday 6th February 2014. I graded Q3,5 and the grader graded Q1,2,4. All questions are marked out of 6.

**Question 1.** I believe most people did fine on this question. The real issues were negating the statements; some people wrote the contrapositive of an implication instead of its negation... this was covered in recitation, so hopefully that matter is cleared up now.

**Question 2.** Proving that an integer $z$ being even implies that $z^3$ is even is straightforward and can be done with the definition of evenness (divisibility by 2): most people had no problems here. What caused problems what proving the converse, i.e. that $z^3$ being even implies that $z$ is even. Many people resorted to arguments about factors, the most common of which actually *assumes* the result you're trying to prove! (Namely: a lot of people said that since $z^3$ is even, $2$ appears as a factor, so must appear three times.) The best way I can think of doing this that doesn't accidentally assume any number theoretic results is to prove the contrapositive, namely $$\neg E(z) \Rightarrow \neg E(z^3)$$ But 'not even' just means 'odd'. So the problem boils down to proving that if $z=2n+1$ (for some integer $n$) then $z^3$ is odd. But $$z^3 = 8n^3+12n^2+6n+1 = 2(4n^3+6n^2+3n)+1$$ and since $4n^3+6n^2+3n \in \mathbb{Z}$, $z^3$ is odd.

**Question 3.** The most common error here was people forgetting that $\mathbb{Z}$ includes *negative* numbers as well as positive numbers... either that, or forgetting that negative integers can be factors of positive ones. This was common amongst people who listed all the factors of $22$. Nevertheless, there is a much easier way of doing this problem. First, notice that $$x^2=22+y^2\quad \Leftrightarrow\quad x^2-y^2=22\quad \Leftrightarrow\quad (x-y)(x+y)=22$$ Now it's possible to prove that $x-y$ and $x+y$ are either both even or they're both odd. Why? Well $x+y = (x-y)+2y$, so we're adding an even number... you proved in class that odd+even=odd and even+even=even, so these two numbers have the same parity. This means that $22$ is either odd (if $x-y$ and $x+y$ are both odd) or is divisible by $4$ (if $x-y$ and $x+y$ are both even), but neither of these facts is true.

**Question 4.** Unsurprisingly, the thing people had most problems with here was translating the proposition from English into mathematical notation. The 'any two ... rational numbers' makes it reasonably clear we should start with $$\forall x \in \mathbb{Q}\ \forall y \in \mathbb{Q}\ \cdots$$ We need them to be 'distinct'; so whatever we want to conclude must be *implied by* $x \ne y$. So we can continue: $$\forall x \in \mathbb{Q}\ \forall y \in \mathbb{Q}\ (x \ne y \Rightarrow \cdots )$$ What we want to conclude is that another rational number lies between them. This is an existence result: $\exists z \in \mathbb{Q}$ such that $z$ 'lies between $x$ and $y$'. Well we don't know whether $x \lt y$ or $y \lt x$, but that's okay: we can account for either case by sticking an 'or' ($\vee$) in there. In summary, we have $$\forall x \in \mathbb{Q}\ \forall y \in \mathbb{Q}\ (x \ne y \Rightarrow \exists z \in \mathbb{Q}\ [x \lt z \lt y\ \vee\ y \lt z \lt x] )$$ The rest of the solution amounted to *finding*, given arbitrary distinct rational $x,y$, a number between them. The 'obvious choice' is their average, namely letting $z=\frac{x+y}{2}$. You were required to prove that $z$ is strictly between $x$ and $y$, and that $z$ is rational; both of these can be done straight from the definitions.

**Question 5.** The meat of this question was part (c), which asked you to prove associativity of the symmetric difference. The easiest way I could see to do this was using truth tables, though direct bashing with double-containment arguments was fine. Most attempts at this solution were convincing enough, and people who didn't get full credit were typically those who'd given up half-way through (or at the beginning). Some Venn diagrams were drawn incorrectly: the region corresponding to $A \cap B \cap C$, i.e. where all three circles overlap, *should* be shaded.