Solutions Sets Basic

6.8. Solutions Sets Basic#

Solutions to Section 4.1

Solution to Exercise (1†)

The possibilities are 2,3,4 and 5 different elements.

2: In the case that $a=b=c$. Then the set can be written as:

\[\{a, a, \{a\}, \{a, a\}, \{a,a,a\}\}=\{a, \{a\}\}\]
3: In the case that $a=b\neq c$. Then the set can be written as:

\[\{a, a, \{a\}, \{a, c\}, \{a,c\}\}=\{a, \{a\}, \{a, c\}\}\]
4: In the case that $a\neq b$ and $a=c$. Then the set can be written as:

\[\{a, b, \{a\}, \{a, a\}, \{a,b,a\}\}=\{a, b, \{a\}, \{a, b\}\}\]
5: In the case that $a\neq b\neq c$. Then the set can be written as:

\[\{a, b, \{a\}, \{a, c\}, \{a,b,c\}\}\]

.

Solution to Exercise (2†)

$A \cup B = \{a,b,c\}; A \cap B = \emptyset; A \smallsetminus B = \{a,b,c\}$
$A \cup B = \{1,2,3,4,5,6,8,10\}; A \cap B = \{2,4\}; A \smallsetminus B = \{1,3,5\}$
$A \cup B = \{a,b,c,d\}; A \cap B = \{a,b\}; A \smallsetminus B = \emptyset$
$A \cup B = \{a,b,\{a\},\{a,b\}\}; A \cap B = \{\{a,b\}\}; A \smallsetminus B = \{a,b\}$

Solution to Exercise (3†)

Solution to Exercise (4†)

$X\cap Y=\{5,6,7,8,9,10\}$
$X\cup Y=\mathbb{N}$
$X\smallsetminus Y=\{11,12,13,...\}$
$\mathbb{N}\smallsetminus Z=\{1,3,5,...\}$
$X\cap Z=\{6,8,10,...\}$
$Y\cap Z=\{0,2,4,6,8,10\}$
$Y\cup Z=\{0,1,2,3,4,5,6,7,8,9,10,12,14,16...\}$
$Z\smallsetminus \mathbb{N}=\emptyset$

Solution to Exercise (5†)

$\mathscr{P}(\{1,2,3\})=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

Solution to Exercise (6†)

False. Although $b$ is part of the two sets that are elements of $A$, namely $\{b\}$ and $\{a,b\}$, the element $b$ itself is not a part of $A$.
False. In order for $\{a,b\}$ to be a subset of $A$, both $a$ and $b$ should be elements of $A$. Like we specified in a), $b\notin A$, hence $\{a,b\}\lnot\subseteq A$.
True. In order for $\{a,b\}$ to be a subset of $A$, both $a$ and $b$ should be elements of $A$, which they are.
False. Although $a$ and $b$ are both individual elements of $B$, the combined set $\{a,b\}$ is not.
False. Although $a$ and $\{b\}$ are both individual elements of $B$, the combined set $\{a,\{b\}\}$ is not.
True. $\{a, \{b\}\}$ is an element of $B$.

Solution to Exercise (7†)

Yes, this is possible.

\[\mathscr{P}(\mathscr{P}(\emptyset))=\mathscr{P}(\{\emptyset\})=\{\emptyset, \{\emptyset\}\}\]

\[\begin{split}\begin{align*} \mathscr{P}(\mathscr{P}(\{a,b\}))=&\mathscr{P}(\{\emptyset, \{a\}, \{b\}, \{a,b\}\})\\ =&\{\emptyset,\\ &\{\emptyset\},\{\{a\}\}, \{\{b\}\},\{\{a,b\}\},\\ &\{\emptyset, \{a\}\}, \{\emptyset, \{b\}\}, \{\emptyset, \{a,b\}\}, \{\{a\}, \{b\}\}, \{\{a\}, \{a,b\}\}, \{\{b\}, \{a,b\}\},\\ & \{\emptyset, \{a\}, \{b\}\}, \{\emptyset, \{a\}, \{a,b\}\}, \{\emptyset, \{b\}, \{a,b\}\}, \{\{a\}, \{b\}, \{a,b\}\},\\ &\{\emptyset, \{a\}, \{b\}, \{a,b\}\}\} \end{align*}\end{split}\]

Solution to Exercise (8†)

The sentence ““She likes dogs that are small, cuddly, and cute” talks about dogs that are both small, and cuddly, and cute. Hence, the dogs she likes has to be in the set of small dogs, the set of cuddly dogs and the set of cute dogs. Therefore, the set of dogs she likes is the intersection of the three sets.\ On the other hand, the sentence “She likes dogs that are small, dogs that are cuddly, and dogs that are cute” talks about dogs that are either small, cuddly, or cute. Hence, the set of liked dogs is the union of these three sets.

Solution to Exercise (9†)

$A \cup A = A$ (remember that sets have no duplicates)\ $A \cap A = A$ (after all everything in $A$ that is also in $A$, is everything)\ $A \smallsetminus A = \emptyset$ (removing from $A$ everything that is in $A$ leaves us nothing)

Solution to Exercise (10†)

We know that $A\subseteq B$. This means that each element of $A$ is in $B$ as well. Therefore, if we take $A\cup B$ we have a set which is equal to $B$, as all elements of $A$ are in $B$. With the same reasoning, $A\cap B$ is equal to $A$, as all elements of $A$ are in $B$. Moreover, because of this, $A\smallsetminus B$ renders the empty set, as no elements are left when removing all elements from $A$ which are in $B$ as well.

Solution to Exercise (11†)

Proof. In order to prove that $C\subseteq A\cap B\leftrightarrow (C\subseteq A\land C\subseteq B)$, we have to show that $C\subseteq A\cap B\rightarrow (C\subseteq A\land C\subseteq B)$ and $(C\subseteq A\land C\subseteq B)\rightarrow C\subseteq A\cap B$.

$C\subseteq A\cap B\rightarrow (C\subseteq A\land C\subseteq B)$:\ We assume that $C\subseteq A\cap B$. Take an arbitrary element $x$ in $C$. Because $C\subseteq A\cap B$, $x$ is in the intersection of $A$ and $B$. Because this is the case, $x$ is in both $A$ and in $B$. Because this holds for an arbitrary element in $C$, it holds for all elements in $C$. Therefore, all elements of $C$ are an element of both $A$ and $B$, and hence $C\subseteq A\land C\subseteq B$.
$(C\subseteq A\land C\subseteq B)\rightarrow C\subseteq A\cap B$:\ We assume that $C\subseteq A$ and $C\subseteq B$.Take an arbitrary element $x$ in $C$. Because $C\subseteq A$ and $C\subseteq B$, $x$ is both in $A$ and in $B$. Because of this, $x$ is in the intersection of $A$ and $B$ ($A\cap B$) as well. Because this holds for an arbitrary element in $C$, it holds for all elements in $C$. Therefore, all elements of $C$ are in $A\cap B$ and hence $C\subseteq A\cap B$.

□

Solution to Exercise (12†)

Proof. Assume that $A\subseteq B$ and $B\subseteq C$, i.e. that $\forall x(x\in A\rightarrow x\in B)$ and $\forall x(x\in B\rightarrow x\in C)$. Take an arbitrary element $x$ in $A$. Because $A\subseteq B$, $x$ is in $B$ as well. Moreover, because $B\subseteq C$, we have that $x$ is in $C$ as well. Because $x$ is an arbitrary element of $A$, it holds for all elements of $A$ that they are in $C$ as well. Therefore, $A\subseteq C$.

□

Solution to Exercise (13†)

Proof. Let us assume that $A\subseteq B$. Let us take an arbitrary element $a$ in $\mathscr{P}(A)$. Since $a$ is in the power set of $A$, it is a subset of $A$. From $a\subseteq A$, $A\subseteq B$ and the previous question, we know that $a\subseteq B$. Because of this, $a\in\mathscr{P}(B)$. Because $a$ is an arbitrary element from $\mathscr{P}(A)$, this is true for all elements in $\mathscr{P}(A)$ and hence, $\mathscr{P}(A)\subseteq\mathscr{P}(B)$.

□

Solution to Exercise (14†)

Proof. We proof this by proof by contradiction. Therefore, assume that $P(M)$ and $P(k)\rightarrow P(k+1)$. We assume that $P(n)$ is not true for all $n\geq M$. Then there exists at least one number $s\geq n$ for which $P(s)$ is false. Let us take the smallest number $s^*\geq n$ such that $P(s^*)$ is false. Now, because $s^*$ is the smallest number, we have that $s^*-1$ is true. However we know that $P(k)\rightarrow P(k+1)$ holds for all $k\geq M$, thus also for $s^*-1$. Thus $P(s^*-1)\rightarrow P(s^*)$ holds, we now have that $P(s^*)$ is true, leading to a contradiction. Therefore, $P(n)$ must be true for all $n\geq M$.

□

Solution to Exercise (15†)

Proof. Let $C(\phi)$ denote the number of connectives in $\phi$, and $V(\phi)$ denote the number of propositional variables. Let $P(\phi)$ be the statement that $V(\phi)\leq C(\phi)+1$, i.e. the number of propositional variables is at most one more than the number of connectives.

Base Case: $V(x)=1$

By the Atoms rule by the definition of $PROP$, $C(\phi)=0$. Therefore, the number of variables ($1$) is obviously at most one more than the number of connectives ($0$). Therefore, $P(\phi)$ holds.

Inductive Case:

Assume that we have two formulas $x,y\in PROP$, for which $P(x)$ and $P(y)$ are true, i.e. $V(x)\leq C(x)+1$ and $V(y)\leq C(y)+1$. We want to show that $P(\lnot x)$ and $P(x * y)$ for $*\in \{\rightarrow, \land, \lor\}$ holds as well. We will split the prove into a proof for the negation and the other connectives:

$\lnot$:

We want to show that $P(\lnot x)$ holds.

\[V(\lnot x)=V(x)\overset{\text{IH}}\leq C(x)+1\leq C(x) + 2 = C(\lnot x) + 1\]

From this, we see that $V(\lnot x)\leq C(\lnot x) + 1$, hence $P(\lnot x)$ holds.
$\rightarrow, \land, \lor$:

In this case, we want to show that $P(x * y)$ holds for $*\in \{\rightarrow, \land, \lor\}$.

\[V(x * y)=V(x) + V(y)\overset{\text{IH}}\leq C(x) + 1 + C(y) + 1=C(x)+C(y)+2=C(x*y) + 1\]

This shows that $V(x*y)\leq C(x*y)+1$, and hence, $P(x*y)$ is true for $*\in \{\rightarrow, \land, \lor\}$.

Altogether, we have shown that $P(x)$ holds for an atom $x$ and that for all $x,y\in PROP$ and $*\in \{\rightarrow, \land, \lor, \lnot\}$, $P(x)\land P(y)\rightarrow P(\lnot x)\land P(x*y)$. Therefore, by the principle of structural induction, $P(\phi)$ is true for all $\phi\in PROP$, so for all propositional formula the number of propositional variables is at most one more than the number of connectives. This completes the proof by structural induction.

□

6.9. Solutions 4.2#

Solution to Exercise (1†)

\[\begin{split}\begin{align*} x\in A\cup (B\cup C)&\leftrightarrow x\in A \vee (x\in B \vee x\in C) &&\text{(definition of $\cup$)}\\ &\leftrightarrow (x\in A\vee x\in B)\vee x\in C &&\text{(associativity of $\vee$)}\\ &\leftrightarrow x\in (A\cup B) \cup C &&\text{(definition of $\cup$)} \end{align*}\end{split}\]

\[\begin{split}\begin{align*} x\in A\cap (B\cap C)&\leftrightarrow x\in A \wedge (x\in B \wedge x\in C) &&\text{(definition of $\cap$)}\\ &\leftrightarrow (x\in A\wedge x\in B)\wedge x\in C &&\text{(associativity of $\wedge$)}\\ &\leftrightarrow x\in (A\cap B) \cap C &&\text{(definition of $\cap$)} \end{align*}\end{split}\]

Solution to Exercise (2†)

\[\begin{split}\begin{align*} x\in A&\rightarrow x\in A \vee x\in B\\ &\leftrightarrow x\in A\cup B &&\text{(definition of $\cup$)} \\ \\ x\in A\cap B&\leftrightarrow x\in A\wedge x\in B && \text{(definition of $\cap$)}\\ &\rightarrow x\in A \\ \end{align*}\end{split}\]

Solution to Exercise (3†)

\[\begin{split}\begin{align*} A\bigtriangleup B&\leftrightarrow \{x| (x\in A)\oplus (x\in B)\} && \text{(definition of $\bigtriangleup$)}\\ &\leftrightarrow \{x| (x\in A \wedge \lnot(x\in B)) \vee (\lnot(x\in A)\wedge x\in B)\} &&\text{(definition of $\oplus$)}\\ &\leftrightarrow \{x | (x\in A \wedge x\not\in B) \vee (x\not\in A\wedge x\in B)\} &&\text{(definition of $\not\in$)}\\ &\leftrightarrow \{x | (x\in A\smallsetminus B) \vee (x\in B\smallsetminus A)\} &&\text{(definition of $\smallsetminus$)}\\ &\leftrightarrow (A\smallsetminus B)\cup (B\smallsetminus A) &&\text{(definition of $\cup$)} \end{align*}\end{split}\]

Solution to Exercise (4†)

Solution to Exercise (5†)

\[\begin{split}\begin{align*} \overline{\overline{A}} &\leftrightarrow \{x\in U| x\not\in \overline{A}\} && \text{(definition of complement)}\\ &\leftrightarrow \{x\in U| \lnot(x\in \overline{A})\} && \text{(definition of $\not\in$)}\\ &\leftrightarrow \{x\in U| \lnot(x\not\in A) \} && \text{(definition of complement)}\\ &\leftrightarrow \{x\in U| \lnot\lnot(x\in A)\} && \text{(definition of $\not\in$)}\\ &\leftrightarrow \{x\in U| x\in A\} && \text{(definition of double negation)}\\ &\leftrightarrow A\\ \\ A\cup \overline{A} &\leftrightarrow \{x \in U| x\in A \vee x\in \overline{A}\} &&\text{(definition of $\cup$)}\\ &\leftrightarrow \{x\in U| x\in A \vee x\not\in A\} && \text{(definition of complement)}\\ &\leftrightarrow \{x\in U| x\in A \vee \lnot(x\in A)\} && \text{(definition of $\not\in$)}\\ &\leftrightarrow \{x\in U| \mathbb{T}\} &&\text{(excluded middle ($p\vee \lnot p\equiv \mathbb{T}$))}\\ &\leftrightarrow U \end{align*}\end{split}\]

Solution to Exercise (6†)

\[\begin{split}\begin{align*} \overline{A\cap B} &\leftrightarrow \{x\in U| x\not\in A\cap B \} &&\text{(definition of complement)}\\ &\leftrightarrow \{x\in U| \lnot (x\in A\cap B)\} &&\text{(definition of $\not\in$)}\\ &\leftrightarrow \{x\in U| \lnot (x\in A\wedge x\in B)\} &&\text{(definition of $\cap$)}\\ &\leftrightarrow \{x\in U| (\lnot (x\in A))\vee (\lnot (x\in B))\} &&\text{(DeMorgan's Law for logic)}\\ &\leftrightarrow \{x\in U| (x\not\in A)\vee (x\not\in B)\} &&\text{(definition of $\not\in$)}\\ &\leftrightarrow \{x\in U| (x\in\overline{A})\vee (x\in\overline{B})\}&&\text{(definition of complement)}\\ &\leftrightarrow \overline{A}\cup\overline{B}&&\text{(definition of $\cup$)} \end{align*}\end{split}\]

Solution to Exercise (7†)

\[\begin{split} \begin{align*} (p\wedge q)\leftrightarrow p&\equiv((p\wedge q)\rightarrow p) \wedge (p\rightarrow (p\wedge q)) && \text{(definition of $\leftrightarrow$)}\\ &\equiv (\lnot(p\wedge q) \vee p)\wedge (\lnot p \vee (p\wedge q)) && \text{(definition of $\rightarrow$)}\\ &\equiv (\lnot p \vee \lnot q \vee p)\wedge ((\lnot p \vee p) \wedge (\lnot p \vee q)) && \text{(DeMorgan's law and Distributive law)}\\ &\equiv \mathbb{T} \wedge (\lnot p\vee q) &&\text{($p\vee\lnot p\equiv \mathbb{T}$)}\\ &\equiv p\rightarrow q &&\text{(definition of $\rightarrow$)}\\ \\ (p\vee q)\leftrightarrow q&\equiv ((p\vee q)\rightarrow q) \wedge (q\rightarrow (p\vee q)) && \text{(definition of $\leftrightarrow$)}\\ &\equiv (\lnot (p\vee q) \vee q) \wedge (\lnot q \vee (p\vee q)) &&\text{(definition of $\rightarrow$)}\\ &\equiv (\lnot p\vee q)\wedge \mathbb{T} &&\text{(DeMorgan's law and Distributive law)}\\ &\equiv p\rightarrow q \end{align*}\end{split}\]
In order to show that these three statements are equivalent, we show that $A\subseteq B \rightarrow A\cap B= A$, $A\cap B= A\rightarrow A\cup B= B$, and $A\cup B = B\rightarrow A\subseteq B$:- $A\subseteq B \rightarrow A\cap B= A$:\ We show this by contradiction, and therefore assume that $A\subseteq B$ and that $A\cap B\neq A$. Because of the latter, we know that there is an element in $A$ which is not in $B$. However, this contradicts our assumption that $A\subseteq B$, hence we know that the original implication is true.

$A\cap B= A\rightarrow A\cup B= B$:\ We show this by contradiction, and therefore we assume that $A\cap B= A$ and $A\cup B\neq B$. From the latter, we know that there now exists an element in $A$ which is not in $B$, lets say $x$. However, this means that $x$ should also be excluded from $A\cap B$, and hence $A\cap B\neq A$, contradicting our assumption. Therefore, the original implication is true.
$A\cup B = B\rightarrow A\subseteq B$:\ We show this by contradiction, and therefore assume that $A\cup B = B$ and that $\lnot(A\subseteq B)$. Because of the latter, there exists at least one element, let say $x$, such that $x\in A$ and $x\not\in B$. This means that $C=A\smallsetminus B\neq\emptyset$. However, this means that $A\cup B = B\cup C$. This contradicts our other assumption that $A\cup B = B$, which states that $A\cup B$ only contains elements of $B$, whereas we have derived that this is not possible. Because of this contradiction, we conclude that $A\cup B = B\rightarrow A\subseteq B$.

Because we have shown that all three implications hold, we have now shown that the three statements are logically equivalent.

Solution to Exercise (8†)

\[\begin{split}\begin{align*} \overline{A}&\leftrightarrow \{x\in U| x\not\in A\} &&\text{(definition of $\overline{A}$)}\\ &\leftrightarrow \{x| x\in U \wedge x\not\in A\}\\ &\leftrightarrow U\smallsetminus A&&\text{(definition of $\smallsetminus$)}\\ \\ C\smallsetminus (A\cup B)&\leftrightarrow \{x| x\in C \wedge x\not\in (A\cup B)\} &&\text{(definition of $\smallsetminus$)}\\ &\leftrightarrow \{x| x\in C\wedge\lnot (x\in (A\cup B))\}&&\text{(definition of $\not\in$)}\\ &\leftrightarrow \{x| x\in C\wedge\lnot (x\in A\vee x\in B)\}&&\text{(definition of $\cup$)}\\ &\leftrightarrow \{x| x\in C \wedge (x\not\in A \wedge x\not\in B)\}&&\text{(DeMorgan's law)}\\ &\leftrightarrow \{x| (x\in C\wedge x\not\in A)\wedge (x\in C\wedge x\not\in B)\}&&\text{(Distributive law)}\\ &\leftrightarrow \{x| (x\in C\smallsetminus A)\wedge (x\in C\smallsetminus B)\}&&\text{(definition of $\smallsetminus$)}\\ &\leftrightarrow \{x| x\in (C\smallsetminus A)\cap (C\smallsetminus B)\}&&\text{(definition of $\cap$)}\\ &\leftrightarrow (C\smallsetminus A)\cap (C\smallsetminus B)\\ \\ C\smallsetminus (A\cap B)&\leftrightarrow \{x| x\in C \wedge x\not\in (A\cap B)\} &&\text{(definition of $\smallsetminus$)}\\ &\leftrightarrow \{x| x\in C\wedge\lnot (x\in (A\cap B))\}&&\text{(definition of $\not\in$)}\\ &\leftrightarrow \{x| x\in C\wedge\lnot (x\in A\wedge x\in B)\}&&\text{(definition of $\cap$)}\\ &\leftrightarrow \{x| x\in C \wedge (x\not\in A \vee x\not\in B)\}&&\text{(DeMorgan's law)}\\ &\leftrightarrow \{x| (x\in C\wedge x\not\in A)\vee (x\in C\wedge x\not\in B)\}&&\text{(Distributive law)}\\ &\leftrightarrow \{x| (x\in C\smallsetminus A)\vee (x\in C\smallsetminus B)\}&&\text{(definition of $\smallsetminus$)}\\ &\leftrightarrow \{x| x\in (C\smallsetminus A)\cup (C\smallsetminus B)\}&&\text{(definition of $\cup$)}\\ &\leftrightarrow (C\smallsetminus A)\cup (C\smallsetminus B) \end{align*}\end{split}\]

Solution to Exercise (9†)

\[\begin{split}\begin{align*} A\cup (A\cap B)&\leftrightarrow (A\cup A)\cap (A\cup B)&&\text{(Distributive law)}\\ &\leftrightarrow A\cap (A\cup B)&&\text{(Idempotent law)}\\ &\leftrightarrow A &&\text{($A\subseteq A\cup B$ (see 2))} \end{align*}\end{split}\]

Solution to Exercise (10†)

\[\begin{split} \begin{align*} X\cup (Y\cup X)&\leftrightarrow (X\cup (X \cup Y)) &&\text{(Commutative law)}\\ &\leftrightarrow (X\cup X)\cup Y &&\text{(Associative law)}\\ &\leftrightarrow X\cup Y &&\text{(Idempotent law)} \end{align*}\end{split}\]
\[\begin{split} \begin{align*} (X\cap Y)\cap\overline{X}&\leftrightarrow (Y\cap X)\cap\overline{X}&&\text{(Commutative law)}\\ &\leftrightarrow Y\cap (X\cap\overline{X})&&\text{(Associative law)}\\ &\leftrightarrow Y\cap \emptyset&&\text{(Miscellaneous law $A\cap \overline{A}=\emptyset$)}\\ &\leftrightarrow \emptyset &&\text{(Miscellaneous law $A\cap\emptyset=\emptyset$)} \end{align*}\end{split}\]
\[\begin{split} \begin{align*} (X\cup Y)\cap \overline{Y}&\leftrightarrow(X\cap \overline{Y})\cup (Y\cap\overline{Y})&&\text{(Distribution law)}\\ &\leftrightarrow (X\cap\overline{Y})\cup\emptyset&&\text{(Miscellaneous law $A\cap\overline{A}=\emptyset$)}\\ &\leftrightarrow X\cap\overline{Y}&&\text{(Miscellaneous law $A\cup\emptyset = A$)} \end{align*}\end{split}\]
\[\begin{split} \begin{align*} (X\cup Y)\cup (X\cap Y)&\leftrightarrow(X\cup (X\cap Y)\cup (Y\cup (X\cap Y))&&\text{(Distributive law)}\\ &\leftrightarrow((X\cap X)\cup (X\cap Y))\cup((Y\cap X)\cup (Y\cap Y))&&\text{(Distributive law)}\\ &\leftrightarrow (X\cup (X\cap Y))\cup ((Y\cap X)\cup Y)&&\text{(Idempotent law)}\\ &\leftrightarrow X\cup Y&&\text{($A\subseteq A\cup B$ (see 2))} \end{align*}\end{split}\]

Solution to Exercise (11†)

\[ \begin{align*} \overline{A\cup B\cup C}&\leftrightarrow \overline{A}\cap\overline{B}\cap\overline{C}&&\text{(Theorem 4.5)} \end{align*}\]
\[\begin{split} \begin{align*} \overline{A\cup (B\cap C)}&\leftrightarrow\overline{A}\cap\overline{B\cap C}&&\text{(DeMorgan's law)}\\ &\leftrightarrow\overline{A}\cap(\overline{B}\cup\overline{C})&&\text{(DeMorgan's law)} \end{align*}\end{split}\]
\[\begin{split} \begin{align*} \overline{\overline{A\cup B}}&\leftrightarrow\overline{\overline{A}\cap\overline{B}}&&\text{(DeMorgan's law)}\\ &\leftrightarrow A\cup B&&\text{(DeMorgan's law)} \end{align*}\end{split}\]
\[ \begin{align*} \overline{B\cap\overline{C}}&\leftrightarrow\overline{B}\cup C&&\text{(DeMorgan's law)} \end{align*}\]
\[\begin{split} \begin{align*} \overline{A\cap\overline{B\cap\overline{C}}}&\leftrightarrow\overline{A\cap\overline{B}\cup C}&&\text{(DeMorgan's law)}\\ &\leftrightarrow\overline{A\cap \overline{B}}\cap\overline{C}&&\text{(DeMorgan's law)}\\ &\leftrightarrow(\overline{A}\cup B)\cap\overline{C} \end{align*}\end{split}\]
\[\begin{split} \begin{align*} A\cap\overline{A\cup B}&\leftrightarrow A\cap\overline{A}\cap\overline{B}&&\text{(DeMorgan's law)}\\ &\leftrightarrow \emptyset\cap\overline{B}&&\text{(Miscellaneous law $A\cap\overline{A}=\emptyset$)}\\ &\leftrightarrow\emptyset&&\text{(Miscellaneous law $A\cap\emptyset = \emptyset$)} \end{align*}\end{split}\]

Solution to Exercise (12†)

Proof. We give a proof by induction. In the base case, $n=2$, the statement is that $\overline{X_1\cap X_2}=\overline{X_1}\cup\overline{X_n}$. This is true since it is just an application of DeMorgan’s law for two sets.

For the inductive case, suppose that the statement is true for $n=k$. Hence, we assume the induction hypothesis: $\overline{X_1\cap X_2\cap \cdots \cap X_{k}}=\overline{X_1}\cup\overline{X_2}\cup\cdots\cup\overline{X_{k}}$, for $X_1$, $X_2$, … , $X_{k+1}$ being any $k+1$ sets. Then we have:

\[\begin{split}\begin{align*} \overline{X_1\cap X_2\cap \cdots \cap X_{k+1}} &= \overline{(X_1\cap X_2\cap \cdots \cap X_k) \cap X_{k+1}}\\ &= \overline{(X_1\cap X_2\cap \cdots \cap X_k)}\cup\overline{X_{k+1}}\\ &= (\overline{X_1}\cup\overline{X_2}\cup\cdots\cup\overline{X_k})\cup\overline{X_{k+1}}&&\text{(IH)}\\ &= \overline{X_1}\cup\overline{X_2}\cup\cdots\cup\overline{X_{k+1}} \end{align*}\end{split}\]

In this computation, the second step follows by DeMorgan’s Law for two sets, while the third step follows from the induction hypothesis. Therefore by the principle of induction we have proven the theorem.

□

Solution to Exercise (13†)

For any natural number $n\geq 2$ and any sets $Q, P_1, P_2,... , P_n$: $Q\cap (P_1\cup P_2\cup ... \cup P_n)=(Q\cap P_1)\cup (Q\cap P_2)\cup... \cup (Q\cap P_n)$

Proof. We proof this by using induction. In the base case, $n=2$, the statement is that $Q\cap (P_1\cup P_2)=(Q\cap P_1)\cup (Q\cap P_2)$. This is true since this is just an application of the Distributive law for three sets.

For the inductive case, suppose that the statement is true for $n=k$, where $k$ is an arbitrary integer bigger or equal to $2$. Hence, we assume the induction hypothesis: $Q\cap (P_1\cup P_2\cup ... \cup P_k)=(Q\cap P_1)\cup (Q\cap P_2)\cup... \cup (Q\cap P_k)$, for $Q$, $P_1, P_2,... P_{k+1}$ being any $k+2$ sets. Then we have:

\[\begin{split}\begin{align*} Q\cap (P_1\cup P_2\cup ... \cup P_{k+1})&=(Q\cap (P_1\cup P_2\cup ... \cup P_k))\cup (Q\cap P_{k+1})\\ &=((Q\cap P_1)\cup (Q\cap P_2)\cup... \cup (Q\cap P_k))\cup (Q\cap P_{k+1})&&\text{(IH)}\\ &=(Q\cap P_1)\cup (Q\cap P_2)\cup... \cup (Q\cap P_{k+1}) \end{align*}\end{split}\]

In this computation, the second step follows by Distributive law for three sets, while the third step follows from the induction hypothesis. Therefore by the principle of induction we have proven the theorem.

□
For any natural number $n\geq 2$ and any sets $Q, P_1, P_2,... , P_n$: $Q\cup (P_1\cap P_2\cap ... \cap P_n)=(Q\cup P_1)\cap (Q\cup P_2)\cap... \cap (Q\cup P_n)$

Proof. We proof this by using induction. In the base case, $n=2$, the statement is that $Q\cup (P_1\cap P_2)=(Q\cup P_1)\cap (Q\cup P_2)$. This is true since this is just an application of the Distributive law for three sets.

For the inductive case, suppose that the statement is true for $n=k$, where $k$ is an arbitrary integer bigger or equal to $2$. $Q\cup (P_1\cap P_2\cap ... \cap P_k)=(Q\cup P_1)\cap (Q\cup P_2)\cap... \cap (Q\cup P_k)$, for $Q$, $P_1, P_2,... P_{k+1}$ being any $k+2$ sets. Then we have:

\[\begin{split}\begin{align*} Q\cup (P_1\cap P_2\cap ... \cap P_{k+1})&=(Q\cup (P_1\cap P_2\cap ... \cap P_k))\cap (Q\cup P_{k+1})\\ &=((Q\cup P_1)\cap (Q\cup P_2)\cap... \cap (Q\cup P_k))\cap (Q\cup P_{k+1})&&\text{(IH)}\\ &=(Q\cup P_1)\cap (Q\cup P_2)\cap... \cap (Q\cup P_{k+1}) \end{align*}\end{split}\]

In this computation, the second step follows by Distributive law for three sets, while the third step follows from the induction hypothesis. Therefore by the principle of induction we have proven the theorem.

□

6.10. Solutions 4.4#

Solution to Exercise (1†)

\[\begin{split}\begin{align*} A\times B&=\{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a),(3,b),(3,c),(4,a),(4,b),(4,c)\}\\ B\times A&=\{(a,1),(a,2),(a,3),(a,4),(b,1),(b,2),(b,3),(b,4),(c,1),(c,2),(c,3),(c,4)\} \end{align*}\end{split}\]

Solution to Exercise (2†)

\[\begin{align*} g\circ f=\{(a,c), (b,c),(c,b),(d,d)\} \end{align*}\]

Solution to Exercise (3†)

\[\begin{split}\begin{align*} B^A=&\{\{(a,0), (b,0), (c,0)\}, \{(a,0), (b,0), (c,1)\}, \{(a,0), (b,1), (c,0)\}, \{(a,0), (b,1), (c,1)\},\\ &\{(a,1), (b,0), (c,0)\}, \{(a,1), (b,0), (c,1)\}, \{(a,1), (b,1), (c,0)\}, \{(a,1), (b,1), (c,1)\}\} \end{align*}\end{split}\]

Solution to Exercise (4†)

$f$ is not onto, as there exists no element $x$ in $\mathbb{Z}$ such that $f(x)=2x=3$, because this means that $x=1.5$, which is not an integer. However, it is one-to-one. Take two arbitrary $a$ and $b$ such that $f(a)=f(b)$. Hence, $2a=2b$, which can only be true if $a=b$.
$g$ is onto; take an arbitrary $y$ in $\mathbb{Z}$. Then there exists an $x$ for which $g(x)=y$, namely $x=y-1$ ($g(x)=g(y-1)=y-1+1=y$), which is integer and thus in $ \mathbb{Z}$. Moreover, $g$ is one-to-one as well. Take two arbitrary $a$ and $b$ such that $g(a)=g(b)$. Hence $a+1=b+1$, which can only be true when $a=b$.
$h$ is not onto, as there exists no element $x$ in $\mathbb{Z}$ such that $h(x)=x^2+x+1=4$. This is because $x^2+x+1=4\leftrightarrow x=\frac{\pm\sqrt{13}-1}{2}$, which is not an integer. It is not one-to-one either, as solving $x^2+x+1=a$ gives two solutions for every $a$. Let us take $a=3$, then both $x=-2$ and $y=1$ give $h(x)=h(y)=3$, however, $x\neq y$.
$s$ is onto; take an arbitrary $y\in\mathbb{Z}$. Then there exists an $x$ for which $s(x)=y$, namely $x=2y$ ($s(x)=s(2y)=\frac{2y}{2}=y$). However, it is not one-to-one. Take an arbitrary even integer $a$ and $b=a-1$. $s(a)=\frac{a}{2}=\frac{(a-1)+1}{2}=s(b)$, however, $a\neq b$.

Solution to Exercise (5†)

For any $x\in A$:

\[\begin{align*} ((h\circ g)\circ f)(x)=(h\circ g)(f(x))=(h(g(f(x))))=h((g\circ f)(x))=(h\circ (g\circ f))(x) \end{align*}\]

Solution to Exercise (6†)

To prove: $g\circ f$ is one-to-one $\rightarrow f$ is one-to-one

Proof. We use proof by contradiction. We assume that $g\circ f$ is one-to-one, but $f$ is not. Because $f$ is not one-to-one, so there exists an $a,b\in A$ such that $f(a)=y=f(b)$, but $a\neq b$. However, since $g: B\to C$, we have an element $x\in C$ such that $g(y)=x$. However, this would mean that for both $a$ and $b$, $(g\circ f)(a)=(g\circ f)(b)=x$, showing that $g\circ f$ is not one-to-one. However, this contradicts our assumption that $g\circ f$ is one-to-one, which mean that it cannot hold that $g\circ f$ is one-to-one, but $f$ is not. Hence, the statement that has to be proven is true.

□
Let $A=\{1\}, B=\{a, b\}, C=\{c\}, f(1)=a, g(a)=g(b)=c$. Although $g$ is not one-to-one, as both $g(a)=g(b)=c$, we have that $g\circ f(1)=c$, which is one-to-one.

Solution to Exercise (7†)

To prove: $g\circ f$ is onto $\rightarrow g$ is onto

Proof. We use proof by contradiction. We assume that $g\circ f$ is onto, but $g$ is not. Because $g$ is not onto, this means that there is an element $c\in C$ such that for all elements in $b\in B: g(b)\neq c$. However, this would mean that $g\circ f$ cannot be onto, as there is no element in $B$ that $f$ can map to such that $g\circ f(x)=c$. However, this contradicts our assumption that $g\circ f$ is onto, which mean that it cannot hold that $g\circ f$ is onto, but $g$ is not. Hence, the statement that has to be proven is true.

□
Let $A=\{a\}, B=\{b,c\}, C=\{d\}, f(a)=b, g(b)=d$. Although $f$ is not onto, as there is no $x\in A$ such that $f(x)=c$, we have that for all elements in $C$, namely $d$, that there exists an element in $A$, namely $a$, such that $(g\circ f)(a)=d$. Hence $g\circ f$ is onto.

Solutions Sets Basic

Contents

6.8. Solutions Sets Basic#

6.9. Solutions 4.2#

6.10. Solutions 4.4#