# FOM Assignment 3

This week we will be finishing Chapter 2, so set your reading radars on that material.  We will also begin our first attempts at writing and understanding proofs.  To reinforce your understanding of all of these concepts — logical statements, open sentences, the “and” operator, the “or” operator, if-then statements (i.e. the $\Rightarrow$ symbol), universal quantifiers ($\forall, \exists$), logically equivalent statements (i.e. $\iff$), the contrapositive of an implication, and basic strategies for proofs — please complete the following problems by Thursday, February 11th.

Problem 1.  One can use Venn diagrams to sense why, given any two sets $A, B$ it follows that

$\overline{A \cap B} = \overline{A} \cup \overline{B}$.

This statement claims that two sets are equal, and so a proof for it requires two parts.  First one must prove $\overline{A\cap B} \subseteq \overline{A} \cup \overline{B}$.  Next, one must also prove $\overline{A} \cup \overline{B} \subseteq \overline{A\cap B}$.  Consider the following proof of the first part.

Claim.  If $A$ and $B$ are sets, then $\overline{A \cap B} \subseteq \overline{A}\cup\overline{B}$.

Proof: Suppose $A$ and $B$ are sets.  To show that $\overline{A \cap B} \subseteq \overline{A}$ we will argue that every element $x \in \overline{A \cap B}$ must necessarily be an element $x \in \overline{A} \cup \overline{B}$.

To this end, let $x \in \overline{A \cap B}$.  This means that $x \notin A \cap B$.  In other words, $x$ is not an element that sets $A$ and $B$ have in common.  Specifically, it might happen that $x \in A$, in which case $x \notin B$; on the other hand, it might happen that $x \in B$ but $x \notin A$.  Or, indeed, it could happen that $x \notin A$ and $x \notin B$.  These are all of the options for our element $x$, and by definition of union, they are all captured by the statement

$x \in \overline{A} \cup \overline{B}$

which completes this proof.  $\square$

For this question, attempt your own proof that demonstrates why the opposite set containment claim must also be true, thereby completing the proof of the set equality claim.

Problem 2. Attempt a proof of the following.

Claim: If $A$ is a set, then $\overline{(\overline{A})} = A.$

(In other words, prove that the complement of a set’s complement is the original set again.)

Problem 3.  Exercise 2 from 2.3 (pg. 42)

Problem 4.  Exercises 3, 4 from 2.4 (pg. 44)

Problem 5.  Exercises 3, 5, and 9 from 2.5 (pg. 46)

Problem 6. Exercises 2, 3, and 9 from 2.6 (pg. 49)

Problem 7.  Exercises 1, 3 from 2.7 (pg. 51)

Problem 8. Exercises 2, 7, and 8 from 2.9 (pg. 55)

Problem 9.  Exercises 6, 7, and 11 from 2.10 (pg. 59)

Problem 10. Be sure to read Definition 2.1 on page 53.  This is where the book clarifies the meaning of “if $P$, then $Q$” where $P$ and $Q$ can be statements or they can be open sentences.  To make certain this idea makes sense, consider the two open sentences

$P$: $y = mx$ where $m \in \mathbb{Z}$ and $m \neq 0$

$Q$: $y/x \in \mathbb{Z}$

First note that neither $P$ nor $Q$ are statements.  Instead, they are open sentences.  Find values of the variables $x$ and $y$ that make $P$ true.  Similarly, find values of $x$ and $y$ that make $Q$ true.

According to Definition 2.1, $P \Rightarrow Q$ is, in fact, a statement since it involves a quantifier.  Write out this statement making this quantifier apparent, and then decide whether the resulting statement is true or false.