Exercise before.3.a

Exercise

What is the truth value of the following propositions?

• $\exists x \in \mathbb{R}, x^2 = 2$
• $\exists x \in \mathbb{R}, x^2 = -1$
• $\forall x \in \mathbb{R}, x^2+2 \ge 1$
• $\forall x \in \mathbb{R}, x^2 \neq x$

Answer

• ${\color{green}\textbf{true}​}$: since $x = \sqrt{2}$ satisfies the equation (also $x = -\sqrt{2}$)
• ${\color{red}\textbf{false}​}$: since we know that $x^2 \ge 0 > -1, \forall x \in \mathbb{R}$
• ${\color{green}\textbf{true}​}$: since we know that $x^2 \ge 0, \forall x \in \mathbb{R}$ and then $x^2+2 \ge 2 \ge 1, \forall x \in \mathbb{R}$
• ${\color{red}\textbf{false}​}$: since $x=0$ is a counterexample for which $0^2 = 0$

Exercise before.3.b

Exercise

What is the truth value of the following propositions?

• $\exists! n \in \mathbb{Z}, n > 1$
• $\exists! n \in \mathbb{Z}, n^2 = 1$
• $\exists! n \in \mathbb{Z}, n+3 = 2n$
• $\exists! n \in \mathbb{Z}, n = n+1$

Answer

• ${\color{red}\textbf{false}​}$: while it is ${\color{green}\textbf{true}​}$ that there exists at least one, this is not unique; for example $n= 2$ and $n =3$ both satisfy the inequality
• ${\color{red}\textbf{false}​}$: while it is ${\color{green}\textbf{true}​}$ that there exists at least one, this is not unique; for example $n= 1$ and $n =-1$ both satisfy the equation
• ${\color{green}\textbf{true}​}$: first note that $n = 3$ satisfies the equation $3+3 = 6 = 2 \cdot 3$. To prove that this is unique we proceed as follows, suppose by contradiction there is an $m \neq 3$ such that $m+3 = 2m$, however by subtracting $m$ from both sides of the equation we get $m = 3$, which is a contradiction
• ${\color{red}\textbf{false}​}$: note that the predicate is equivalent to $0 = 1$, which is ${\color{red}\textbf{false}​}$. By definition, the existential quantifier over a ${\color{red}\textbf{false}​}$ proposition is always ${\color{red}\textbf{false}​}$

Exercise before.4.a

Exercise

Let $P(x,y)$ be the predicate "$x$ loves $y$" and assume $U$ is a set containing all people. Use quantifiers to write the following propositions

• Everyone loves Batman
• Everyone loves someone

Answer

• $\forall x \in U, P(x, \text{Batman})$
• $\forall x \in U, \exists y \in U, P(x,y)$

Exercise before.4.b

Exercise

Write the following propositions using mathematical and logical operators, predicates, and quantifiers. Consider the domain to be all integers

• The sum of two negative integers is negative
• The difference of two positive integers is not necessarily positive

Answer

• $\forall n, m \in \mathbb{Z}, n<0 \land m<0, n+m < 0$
• $\neg \forall n, m \in \mathbb{Z}, n>0 \land m>0, n-m > 0$, equivalently

$$\begin{align*} & &\neg \forall n, m \in \mathbb{Z}, n>0 \land m>0, n-m > 0 &\\ \equiv & &\neg \forall n, m \in \mathbb{Z}, (n>0 \land m>0) \Rightarrow n-m > 0 &\\ \equiv & &\exists n, m \in \mathbb{Z}, \neg ( (n>0 \land m>0) \Rightarrow n-m > 0) & \\ \equiv & & \exists n, m \in \mathbb{Z}, (n>0 \land m>0) \land \neg (n-m > 0) & \\ \equiv & &\exists n, m \in \mathbb{Z}, (n>0 \land m>0) \land n-m \le 0 & \\ \end{align*}$$

Exercise during.3.a

Exercise

What is the truth value of the following propositions? ($\forall$ and $\exists$ quantify over $\mathbb{Z}$)

• $\forall n, \exists m, n^2 < m$
• $\exists n, \forall m, n<m^2$
• $\forall n, \exists m, n+m = 0$

Answer

• ${\color{green}\textbf{true}​}$: let $n$ be an integer, then there exists $m = n^2+1$ such that $n^2 < n^2 + 1 = m$
• ${\color{green}\textbf{true}​}$: there exists $n = -1$ such that $-1 = n < 0 \le m^2, \forall m$
• ${\color{green}\textbf{true}​}$: let $n$ be an integer, then there exists $m = -n$ such that $n + m = n - n = 0$

Exercise during.3.b

Exercise

Rewrite the proposition $\neg \forall x, \exists y, P(x, y)$ so that the negation is not preceding a quantifier

Answer

$$\begin{align*} & &\neg \forall x, \exists y, P(x, y)\\ \equiv & &\exists x, \neg \exists y, P(x,y)\\ \equiv & &\exists x, \forall y, \neg P(x, y) \end{align*}$$

Exercise during.3.c

Exercise

Find a counterexample to the following proposition $\forall x,y \in \mathbb{Z}, x^2 = y^2 \Rightarrow x = y$

Answer

Note that a counterexample for this proposition requires two integers whose squares are equal, but the numbers themselves are not. A simple (counter)example is $x = 1, y= -1$.