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

**Question 1.** This question was mostly fine. There was a bit of confusion between the symbols $\in$ and $\subseteq$, but on the whole not too much to worry about. A common error with both Question 1 and 2 was that people would write down facts that were irrelevant to the proof, which isn't necessarily a problem but it does give out the message that you don't really know what you're talking about; and sometimes people would conclude things before the justification was given, without connecting the facts together. A proof should flow, everything written should be relevant, and facts should be written down in roughly the order they're needed. (Of course, you can say you'll justify something later, provided you *do* justify it later, and you refer to where you justified it in the proof.)

**Question 2.** The main problem with this question, beside what I mentioned about Question 1, was either failing to actually provide examples, or providing examples without justification. You need to convince us that you understand what you're writing down and you're not just guessing. This is done by means of proof! So if you give an example of sets $A,B$ such that $(A \cap B)^c \ne A^c \cap B^c$ then you should write down two actual sets $A$ and $B$, calculate $(A \cap B)^c$ and $A^c \cap B^c$, and show they're not equal (i.e. by demonstrating that one has an element which isn't an element of the other set).

**Question 3.** Most people attempted this question using double-containment arguments. Some arguments were more vague than others. The best worked directly with the definitions, which is precisely what you're expected to do; the worst gave vague intuitive arguments involving statements like 'there must be'. I gave a model proof in recitation, so hopefully some of these facts will have been cleared up. Other common errors included mixing up notation: $A \times B$ makes sense when $A$ and $B$ are sets; the set $A \times B$ is the Cartesian product of $A$ and $B$; its *elements* are of the form $(a,b)$ where $a \in A$ and $b \in B$. Some people used notation like $(A,B)$, but this is an ordered pair of sets, not a Cartesian product of sets. There were also some issues regarding the use of 'some' and 'all'; a lot of people would write things like: "$a \in \bigcup_{i \in I} A_i$, therefore $a \in A_i$, $i \in I$". This is ambiguous; it it 'some' or 'all' $i \in I$? If it's 'all' then you get the intersection, not the union.

**Question 4.** The errors in this question were similar to in Question 1 and 2, where people would write their assumptions out of order. Proving one set is a subset of another really is an *implication*; that is, you're showing that *if* $x$ is an element of $(X \cup Y) - Z$ *then* $x$ is an element of $X \cup (Y-Z)$. Your proof should start from the assumption that $x$ is an (arbitrary) element of $(X \cup Y) - Z$, and based on these assumptions, deduce that $x$ must be an element of $X \cup (Y-Z)$. Some people tried to prove the reverse inclusion, which is odd given that you're told it's false and asked to provide an example to demonstrate this fact!

**Question 5.** Like with Question 3, correct answers to this question typically used double-containment arguments. A common error was placing the complement incorrectly; to clear this up: $$\bigcup_{n \in \mathbb{N}} [n]^c = \bigcup_{n \in \mathbb{N}} ([n]^c) \quad \text{and not} \quad \left( \bigcup_{n \in \mathbb{N}} [n] \right)^c$$ There were lots of answers involving people talking about 'largest sets' and 'smallest sets' without specifying what they meant, and talking about numbers being greater or smaller than each other, without specifying what impact this has on the unions and intersections of the sets involved.

The most common issue with this problem was people writing 'by definition' when they didn't mean it. Avoid writing 'by definition' on its own—always refer to something specific, such as saying 'by definition of indexed unions'. Moreover, if you *do* write 'by definition', then both the thing you're defining, and what it means for that thing to be the thing you're defining, should be written down. All components should be there. For instance: "$x \in \bigcup_{n \in \mathbb{N}} [n]$, so $x \in [n]$ for some $n \in \mathbb{N}$ by definition of indexed unions" is good; however "$x \in \bigcup_{n \in \mathbb{N}} [n]$, so $x \in \mathbb{N}$ by definition" is not good.