• You might first wish to show, given a universal set \( U \) and \( A\subseteq U, \),that \( \overline{(\overline{A})}=A.\)
• The problem asks the reader to find \(\theta^{-1}.\) I did not grade this part of the problem. Had I: It is not sufficient to simply state that \( \theta^{-1}(X)=\overline{X} = \theta(X)\) or even solve for the inverse. Rather, once a candidate for the inverse is identified, verify that it satisfies the definition of inverse function (a simple task in this example).

• Show, if \( n\in\mathbb N \) is not prime, then there exists \( [a], \, [b] \in \mathbb Z_n\) such that \( [a]\ne [0] \ne [b] \), but \( [a]\cdot [b] = [0]. \)
• Show, if \( p\in\mathbb N \) is prime, \( [a], \, [b] \in \mathbb Z_p\) and \( [a]\ne [0] \ne [b] \), then \( [a]\cdot [b] \ne [0]. \)

Let \( a_1=1, \, a_2=8,\) and \( a_n= a_{n-1}+2a_{n-2}\) for \( \ge 3. \) Prove \( a_n = (3)(2^{n-1})+2(-1)^n\) for all \( n\in \mathbb N.\)

• 1. Show it suffices to prove: If \( p\mid ab\) and \( p\not\mid a\), then \( p\mid b.\)
• In what follows, suppose \( p \) is prime, \( p\mid ab\) and \( p\not\mid a\).
• 2. Show \( \gcd(a,p)=1. \)
• 3. From (2) and the proposition on page 152, there exists \( k,\ell\in\mathbb Z\) such that \( ak+p\ell =1.\)
• 4. Invoke the assumption \( p\mid ab\) and use a bit of algebra to show \( p\mid b,\) completing the proof.

Which pairs of the following four statements are logically equivalent? \( (a) \sim (P\Rightarrow Q), \ \ (b)\, (Q\Rightarrow P), \ \ (c)\, P \wedge (\sim Q), \ \ (d)\, P \vee (\sim Q). \) Explain.

Suppose \( X,Y \) are sets, \( A,C \subseteq X \) and \( B,D\subseteq Y. \) Compare \( (A\times B)\setminus (C\times D)\) with \(\left((A\setminus C)\times B\right ) \bigcup \left( A\times (B\setminus D) \right ).\)

Homework grading abbreviations