Exercises

This page allows you to practice some exercises on Essentials of Logic and Set Theory. If you notice that you have difficulties, we advise you to go over the corresponding sections in the book.

These questions correspond to the following sections: - Section 1.1 - Essentials of Set Theory - Section 1.2 - Essentials of Logic - Section 1.3 - Mathematical Proofs - Section 1.4 - Mathematical Induction

Question 1

Let $A = \{ 2, 3, 4 \}$, $B = \{ 2, 5, 6 \}$, $C = \{5, 6, 2 \}$, and $D = \{ 6 \}$.

(a) Determine which of the following six statements are true: (i) $4 \in C$, (ii) $5 \in C$, (iii) $A \subseteq B$, (iv) $D \subseteq C$, (v) $B = C$, (vi) $A = B$.

(b) List all members of each of the following eight sets: (i) $A \cap B$, (ii) $A \cup B$, (iii) $A \setminus B$, (iv) $B \setminus A$; (v) $(A \cup B) \setminus (A \cap B)$, (vi) $A \cup B \cup C \cup D$, (vii) $A \cap B \cap C$, and (viii) $A \cap B \cap C \cap D$.

Show answer

(a) The true statements are (ii) $5 \in C$, (iv) $D \subseteq C$ and (v) $B = C$.

(b) Note that (i) $A \cap B = \{ 2 \}$, (ii) $A \cup B = \{ 2, 3, 4, 5, 6 \}$, (iii) $A \setminus B = \{3, 4 \}$, (iv) $B \setminus A = \{ 5, 6 \}$, (v) $(A \cup B) \setminus (A \cap B) = \{2, 3, 4, 5, 6 \} \setminus \{2\} = \{3, 4, 5, 6 \}$, (vi) $A \cup B \cup C \cup D = \{2, 3, 4, 5, 6 \}$, (vii) $A \cap B \cap C = \{ 2 \}$ and (viii) $A \cap B \cap C \cap D = \emptyset$.

Question 2

A survey revealed that 50 people liked coffee and 40 liked tea. Both these figures include 35 who liked both coffee and tea. Finally, ten did not linke either coffee or tea. How many people in all responded to the survey?

Show answer

Note that $50 - 35 = 15$ liked coffee, but not tea, and $40 - 35 = 5$ liked tea but not coffee. Because $35$ liked both and $10$ liked neither, there were $15 + 5 + 35 + 10 = 65$ respondents.

Question 3

Make a complete list of all the different subsets of the set $\{ a, b, c \}$. How many are there if the empty set and the set itself are included? Do the same for the set $\{a, b, c, d \}$.

Show answer

The $2^3 = 8$ subsets of $\{a, b, c \}$ are the set itself, and the empty set, together with the six subsets $\{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\},$ and $\{b, c\}$. The $2^4 = 16$ subsets of $\{a, b, c, d\}$ are the $8$ preceding sets together with $8$ more sets that include $d$ — namely $\{d \}, \{a, d\}, \{b, d\}, \{c, d\}, \{a, b, d\}, \{a, c, d\}, \{b, c, d\},$ and $\{a, b, c, d \}$. Apart from $\{a, b, c, d\}$ and the empty set, there are $14$ other subsets.

Question 4

Determine which of the following formulas are true. If any formula is false, find a counter example to demonstrate this. [Hint: drawing a Venn diagram can be helpful.] (a) $A \setminus B = B \setminus A$

(b) $A \cap (B \cup C) \subseteq (A \cap B) \cup C$

(c) $A \cup (B \cap C) \subseteq (A \cup B) \cap C$

(d) $A \setminus (B \setminus C) = (A \setminus B) \setminus C$

Show answer

Generally, only (b) is true. Let's consider them one-by-one:

(a) $A \setminus B \neq B \setminus A$ whenever $B \subseteq A$ with $\emptyset \neq B \neq A$. You can check it with an easy example. Take $A = \{ 1, 2\}$ and $B = \{2 \}$. Then $A \setminus B = \{ 1 \}$, while $B \setminus A = \emptyset$.

(b) True, because $A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \subseteq (A \cap B) \cup C$.

(c) Holds if and only if $A \subseteq C$.

(d) Is violated when $A = \{1, 2\}$, $B = \{1 \}$, and $C = \{1, 3 \}$. In that case, the lefthand side becomes $A \setminus (B \setminus C) = \{ 1, 2 \} \setminus \{ \emptyset \} = \{ 1, 2 \}$. However, the righthand side equals $(A \setminus B) \setminus C = \{ 2 \} \setminus \{1, 3 \} = \{ 2 \}$.

Question 5

Prove that

(a) $(A \cup B)^{c} = A^{c} \cap B^{c}$

(b) $(A \cap B)^{c} = A^{c} \cup B^{c}$

[Hint: drawing a Venn diagram can be helpful]

Show answer

(a) Let's consider an arbitrary element $x$. We will show that $x \in (A \cup B)^{c} \iff x \in A^{c} \cap B^{c}$. Consider the lefthand side. Note that $x \in (A \cup B)^{c}$ means that $x \notin A \cup B$. Thus, $x \notin A$ and $x \notin B$. For the right hand side, we have that $x \in A^{c} \cap B^{c}$ means that $x \in A^{c}$ and $x \in B^{c}$. This also means that $x \notin A$ and $x \notin B$. Thus, the two sets are equal.

(b) Let's consider an arbitary element $x$. We will show that $x \in (A \cap B)^{c} \iff x \in A^{c} \cup B^{c}$. Consider the lefthand side. If $x \in (A \cap B)^{c}$, then $x \notin A \cap B$. Thus, it is not true that $x \in A$ and $x \in B$. Therefore, $x \notin A$ or $x \notin B$. For the righthand side, $x \in A^{c} \cup B^{c}$ means that either $x \in A^{c}$ or $x \in B^{c}$. However, this also means that $x \notin A$ or $x \notin B$. Thus, the two sets are equal.

Question 6

Use appropriate implication or equivalence arrows to represent the following propositions:

(a) The equation $2x - 4 = 2$ is fulfilled only when $x=3$

(b) If $x = 3$, then $2x - 4 = 2$

(c) The equation $x^2 - 2x + 1 = 0$ is satisfied if $x=1$

(d) If $x^2 > 4$, then $|x| > 2$, and conversely

Show answer

(a) $2x - 4 = 2 \implies x = 3$.

(b) $x = 3 \implies 2x-4 = 2$.

(c) $x = 1 \implies x^2 - 2x + 1 = 0$.

(d) $x^2 > 4 \iff |x| > 2$.

Question 7

In each of the following implications, where $x$, $y$, and $z$ are numbers, decide: (i) if the implication is true; and (ii) if the converse implication is true.

(a) $x = \sqrt{4} \implies x = 2$

(b) ($x=2$ and $y=5$) $\implies x + y = 7$

(c) $(x-1)(x-2)(x-3) = 0 \implies x=1$

(d) $x^2 + y^2 = 0 \implies x=0$ or $y=0$

Show answer

(a) $\implies$true, $\impliedby$true.

(b) $\implies$true, $\impliedby$false.

(c) $\implies$false, $\impliedby$true.

(d) $\implies$true (actually both are zero), $\impliedby$false (only having one equal to zero is not enough).

Question 8

Consider the proposition $2x + 5 \geq 13$. Is the condition $x \geq 0$ necessary, or sufficient, or both necessary and sufficient for the inequality to be satisfied?

Show answer

Note that $2x + 5 \geq 13 \iff 2x \geq 8 \iff x \geq 4$. This means that $x \geq 0$ is necessary, but not sufficient.

Question 9

Which of the following statements are equivalent to the (dubious) statement: "If inflation increases, then unemployment decreases".

(a) For unemployment to decrease, inflation must increase.

(b) A sufficient condition for unemployment to decrease is that inflation increases.

(c) Unemployment can only decrease if inflation increases.

(d) If unemployment does not decrease, then inflation does not increase.

(e) A necessary condition for inflation to increase is that unemployment decreases.

Show answer

The statements (b), (d) and (e) all express the same condition. The remaining two statements, (a) and (c) are different.

Question 10

Prove the following two statements by induction:

(a) For all natural numbers $n$: $1 + 2 + 3 + \ldots + n = \frac{1}{2}n(n+1)$.

(b) For all natural numbers $n$: $n^3 + (n + 1)^3 + (n+2)^3$ of three consecutive cubes is always divisible by $9$.

Show answer

(a) For $n=1$, the left- and righthand side are both equal to $1$. Suppose the statement is true for $n=k$. Now,

$1 + 2 + 3 + \cdots + k + (k+1) = \frac{1}{2}k(k+1) + (k+1)$,

where the righthand side can be rewritten as

$\frac{1}{2}k^2 + 1\frac{1}{2}k + 1 = \frac{1}{2}(k^2 + 3k + 2) = \frac{1}{2}(k+1)(k+2)$. This is the original statement for $n=k+1$. Thus, by induction, the statement is true for all $n \in \mathbb{N}$.

(b) For $n=1$, the sum $n^3 + (n+1)^3 + (n+2)^3 = 36$, which is divisible by $9$. Suppose the statement is true for $n=k$, that is, $k^3 + (k+1)^3 + (k+2)^{3} = 9m$, for some $m \in \mathbb{N}$ (divisible by $9$, means that it can be written as a multiple of $9$). First, define $S_{k+1} = (k+1)^{3} + (k+2)^{3} + (k + 3)^3$ and $S_{k} = k^3 + (k+1)^3 + (k+2)^3$. Note that the difference is given by

$S_{k+1} - S_{k} = -k^{3} + (k+3)^3$.

Thus,

$(k+1)^3 + (k+2)^3 + (k+3)^3 = 9m -k^3 + (k+3)^3$.

With some simple algebra, the righthand side can be written as $9(m + k^2 + 3k + 3)$, which is clearly divisible by $9$. So, the statement also holds for $n = k+1$. Then, by induction, the statement is true for all $n \in \mathbb{N}$.