E.1 Workshop exercises from week 1

Exercise 1.1.$A\cap B=\{2,4\}$, $A\cup B=\{1,2,3,4,5,6,8,10\}$, $A\setminus B=\{1,3,5\}$ and $B\setminus A=\{6,8,10\}$.

Exercise 1.2. As there are $2$ statement variables involved, the truth table must have $2^{2}=4$ rows and the following columns.

Exercise 1.3.

1. (i)

   $B=\{0,1,2,3\}$ because

   $$(3n+1\in A)\ \Leftrightarrow\ (1\leqslant 3n+1\leqslant 10)\ \Leftrightarrow\ (0\leqslant 3n\leqslant 9)\ \Leftrightarrow\ (0\leqslant n\leqslant 3)$$

   for each $n\in\mathbb{Z}$;

2. (ii)

   $C=\{3\cdot 1+1,3\cdot 2+1,3\cdot 3+1,3\cdot 4+1,3\cdot 5+1,3\cdot 6+1,3\cdot 7+1,3\cdot 8+1,3\cdot 9+1,3\cdot 10+1\}$
   $\phantom{C}=\{4,7,10,13,16,19,22,25,28,31\}$;

3. (iii)

   $D=\{1,2,3,4,5,6,7,8,9,10\}=A$ because $3n+1\in\mathbb{Z}$ for all $n\in A$.

Exercise 1.4.

1. (i)

   $(\exists\,m\in\mathbb{Z})(\forall n\in\mathbb{Z})(m+n\in\mathbb{N})$.

2. (ii)

   $(\forall m\in\mathbb{Z})(\exists\,n\in\mathbb{Z})(m+n\not\in\mathbb{N})$.

3. (iii)

   We claim that the statement is false. In other words, we must prove that its negation found in (ii) is true. To this end, let $m\in\mathbb{Z}$ be given. Choosing $n=-m\in\mathbb{Z}$, we have $m+n=0\not\in\mathbb{N}$, as desired.

Exercise 1.5. There is no model solution to this exercise (or any of the subsequent exercises concerning the Self-explanation strategy) because correct answers can vary substantially. The main point is that your answer should support your understanding of the proof. You may find it useful to get together in a small group to discuss and compare your answers. In particular, seeing the answers of others may inspire you to explore alternative approaches to the proof.

Exercise 1.6. We construct the truth tables.

As the fifth and eighth columns are the same, we conclude that the statements ‘‘$p\ \&\ (q\ \text{or}\ r)$’’ and ‘‘$(p\ \&\ q)$ or $(p\ \&\ r)$’’ are logically equivalent.

Exercise 1.7.

1. (a)
   1. (i)

      $(\exists\,n\in\mathbb{Z})(n^{3}=18)$.

   2. (ii)

      $(\forall r\in\mathbb{Q})(\exists\,m\in\mathbb{Z})(\exists\,n\in\mathbb{Z})\bigl((n\neq 0)\ \&\ (r=m/n)\bigr)$.

      Note: repeated quantifiers of the same type and over the same set are often combined into a single one, so that this statement can also be written

      $$(\forall r\in\mathbb{Q})(\exists\,m,n\in\mathbb{Z})\bigl((n\neq 0)\ \&\ (r=m/n)\bigr).$$

      A third way of writing it would be $(\forall r\in\mathbb{Q})(\exists\,m\in\mathbb{Z})\bigl(\exists\,n\in\mathbb{Z}\setminus\{0\}\bigr)(r=m/n)$.

   3. (iii)

      $(\exists\,x\in\mathbb{R})(3x^{2}-2x+9=0)$.

2. (b)
   1. (i)

      $(\forall n\in\mathbb{Z})(n^{3}\neq 18)$.

   2. (ii)

      $(\exists\,r\in\mathbb{Q})(\forall m\in\mathbb{Z})(\forall n\in\mathbb{Z})\bigl((n=0)\ \text{or}\ (r\neq m/n)\bigr)$.

      Alternatives: $(\exists\,r\in\mathbb{Q})(\forall m,n\in\mathbb{Z})\bigl((n=0)\ \text{or}\ (r\neq m/n)\bigr)$;
      Alternatives: $(\exists\,r\in\mathbb{Q})(\forall m\in\mathbb{Z})\bigl(\forall n\in\mathbb{Z}\setminus\{0\}\bigr)(r\neq m/n)$.

   3. (iii)

      $(\forall x\in\mathbb{R})(3x^{2}-2x+9\neq 0)$.

3. (c)

   Statement (i) is false because the function $f\colon\mathbb{R}\to\mathbb{R}$ given by $f(x)=x^{3}$ is increasing and $f(2)=8<18$, whereas $f(3)=27>18$.

   Statement (ii) is true; this is the fundamental way of expressing rational numbers.

   Statement (iii) is false because the discriminant of the quadratic polynomial
   $3x^{2}-2x+9$ is negative: $D=(-2)^{2}-4\cdot 3\cdot 9=-104<0$.

Exercise 1.8. We construct the truth tables; as there are $2$ statement variables involved, they have $2^{2}=4$ rows.

Since the third and fifth columns are the same, we conclude that the statements ‘‘$p\Rightarrow q$’’ and ‘‘$(\neg p)$ or $q$’’ are logically equivalent.

Exercise 1.9. As there are $2$ variables involved, the parity table must have $2^{2}=4$ rows and the following columns.

Exercise 1.10.   $\displaystyle{C\cap D=\biggl\{\frac{1}{2},\frac{1}{\sqrt{2}},e\biggr\}}$,  $\displaystyle{C\cup D=\biggl\{-1,\frac{1}{3},\frac{1}{2},\frac{1}{\sqrt{2}},\frac{2\pi}{3},e,\pi,\log 32\biggr\}}$,
$C\setminus D=\{-1,\pi,\log 32\}$  and  $\displaystyle{D\setminus C=\biggl\{\frac{1}{3},\frac{2\pi}{3}\biggr\}}$.
Note: $\displaystyle{\frac{\sqrt{2}}{2}=\frac{\sqrt{2}}{\sqrt{2}^{2}}=\frac{1}{\sqrt{2}}}$.

Exercise 1.11. As there are $3$ statement variables involved, the truth table must have $2^{3}=8$ rows and the following columns.

Exercise 1.12. As there are $3$ statement variables involved, the truth tables have $2^{3}=8$ rows and the following columns.

Since the fifth and eighth columns of this table are the same, the compound statements ‘‘$p\ \hbox{or}\ (q\ \&\ r)$’’ and ‘‘$(p\ \hbox{or}\ q)\ \&\ (p\ \hbox{or}\ r)$’’ are logically equivalent.

Exercise 1.13.

1. (i)

   We construct the truth tables.

   $p$	$q$	$p\ \&\ q$	$\neg(p\ \&\ q)$	$\neg p$	$\neg q$	$(\neg p)$ or $(\neg q)$
   $T$	$T$	$T$	$F$	$F$	$F$	$F$
   $T$	$F$	$F$	$T$	$F$	$T$	$T$
   $F$	$T$	$F$	$T$	$T$	$F$	$T$
   $F$	$F$	$F$	$T$	$T$	$T$	$T$

   As the fourth and seventh columns are the same, we conclude that the statements ‘‘$\neg(p\ \&\ q)$’’ and ‘‘$(\neg p)$ or $(\neg q)$’’ are logically equivalent.

2. (ii)

   Consider the two basic statements
   

   • $p:$

     ‘‘I closed the windows’’;
     

   • $q:$

     ‘‘I closed the door’’.
     

   Then ‘‘$\neg(p\ \&\ q)$’’ represents

   ‘‘I did not close the windows and the door’’,

   while ‘‘$(\neg p)$ or $(\neg q)$’’ represents

   ‘‘I did not close the windows or I did not close the door’’.

   These two sentences have the same meaning. Many other examples are of course possible.

Exercise 1.14.

1. (i)

   $(\forall a\in\mathbb{Z})(\forall b\in\mathbb{Z})(\exists\,x\in\mathbb{Q})(ax=b)$.

   Alternatively, we can combine the first two quantifiers and write this statement as $(\forall a,b\in\mathbb{Z})(\exists\,x\in\mathbb{Q})(ax=b)$.

   The negation is $(\exists\,a\in\mathbb{Z})(\exists\,b\in\mathbb{Z})(\forall x\in\mathbb{Q})(ax\neq b)$, or alternatively just
   $(\exists\,a,b\in\mathbb{Z})(\forall x\in\mathbb{Q})(ax\neq b)$.

2. (ii)

   $(\forall n\in\mathbb{Z})\bigl((n>9)\Rightarrow(\sqrt{n}>3)\bigr)$.

   Alternatively, this could be written $\bigl(\forall n\in\{10,11,12,\ldots\}\bigr)(\sqrt{n}>3)$.

   Negation: $(\exists n\in\mathbb{Z})\bigl((n>9)\ \&\ (\sqrt{n}\leqslant 3)\bigr)$, or alternatively
   $\bigl(\exists\,n\in\{10,11,12,\ldots\}\bigr)(\sqrt{n}\leqslant 3)$.

3. (iii)

   $(\exists\,n\in\mathbb{Z})(-27=n^{3})$.

   Negation: $(\forall n\in\mathbb{Z})(-27\neq n^{3})$.

4. (iv)

   $(\forall n\in\mathbb{N})(\exists\,x\in\mathbb{R})(n=x^{4})$.

   Negation: $(\exists\,n\in\mathbb{N})(\forall x\in\mathbb{R})(n\neq x^{4})$.

Exercise 1.15.

1. (i)

   No triangle is isosceles. (Or: there does not exist an isosceles triangle.)

2. (ii)

   There exist triangles that are not similar. (Or: there exist triangles $T$ and $S$ such that $T$ is not similar to $S$.)

3. (iii)

   $\bigl(\forall p\in\mathbb{P}\setminus\{2\}\bigr)(\exists\,n\in\mathbb{N})\bigl((p=4n+1)\ {\hbox{or}}\ (p=4n-1)\bigr).$