Part (b): Practice and Review Due Friday, February 10, at 10:00 pm

Question B1:

Prove that if the $\frac{p}{q}$ is in least terms, then so is $\frac{q}{p+q}$.

Hint: Try a contrapositive formulation. Show that if both $p$ and $p + q$ are multiples of $d$ then so is $q$.

<aside> 💡 Answer 4b1

$$ \begin{aligned}r:&\frac{p}{q}\text{ is in least terms}\\ t:&\frac{q}{p+q}\text{ is in least terms}\\&r\rarr t\equiv \neg t\rarr \neg r\\\text{then}\\\neg t:&\exist d\isin \Z\ \exist k_1\isin \Z(p=k_1d,p+q=k_2d)\\\neg r:&\exist k_3\isin \Z(q=k_3d)\\\text{since }& p+q=k_1d+k_3d=k_2d\\ &\underline{\exist k_1,k_2,k_3 (k_2=k_1+k3)}\\\therefore&\neg t\rarr\neg r \text{ is tautology, so } r\rarr t\end{aligned}\\\hspace{2in}Q.E.D $$

</aside>

Question B2:

Consider two sets, $A$ and $B$.

(a) Prove that $A ∩ B = ϕ$ if and only if $A − B = A$. (b) Prove that $A = (A ∩ \bar{B}) ∪ (B ∩ A)$.

Answer 4B2

<aside> 🔖 (a)

$$ p:A ∩ B = ϕ\\ q:A − B = A $$

$p$ iff $q$ $\equiv p\lrarr q$, first look at $p\rarr q$:

$A\cap B = \empty\rarr \forall x\isin A (x\notin B)$

$A-B=\{x|x\isin A \wedge x\notin B\} = A$

look at $q\rarr p$:

$A-B= A =\{x|x\isin A \wedge x\notin B\}\rarr \forall x\isin A (x\notin B)$

$A\cap B =\{x|x\in A \wedge x\in B\}=\empty$

(b)

$$ (A\cap\overline{B} )\vee (A\cap B)=A\cap(\overline{B}\cup B) = A\cap U=A $$

</aside>

Question B3:

Let $A = \{a, b\}$, $B = \{1, 2, 3\}$, and $C = \{r, s\}$.

(a) Use the roster method to list the elements of $A × B × C$. (b) List the elements of $A × (B × C)$. (c) What are the cardinalities of $A × B × C$ and $A × (B × C)$?

Answer 4B3

(a)

$$ \begin{aligned} A\times B\times C=\{(&a,1,r),(a,1,s),(a,2,r),(a,2,s),(a,3,r),(a,3,s),\\&(b,1,r),(b,1,s),(b,2,r),(b,2,s),(b,3,r),(b,3,s)\}\end{aligned} $$

(b)

$$ ⁍ $$

(c) $|A\times B\times C|=|A\times(B\times C)|=C^1_2C^1_3C^1_2=12$ ****

Question B4:

Suppose that $A$ is a set.

(a) Show that the function $f : A → \mathcal{P}(A)$ defined by $f(x) = {x}$ is an injection. (b) Show that the function $f : A × A → A$ defined by $f(x, y) = x$ is a surjection.

Answer 4B4

<aside> 🔖 (a)

Suppose ****$\exist x_1, x_2(f(x_1)=f(x_2))$,

then $x_1=f(x_1)=f(x_2)=x_2$,

so there no different $x_i, x_j$ make $f(x_i)=f(x_j)$,

thus function $f : A → \mathcal{P}(A)$ defined by $f(x) = {x}$ is an injection.

(b)

$\forall x\in A,$ $\exist(x,y) \in A\times A$

thus the function $f : A × A → A$ defined by $f(x, y) = x$ is a surjection.

</aside>