1 Propositions and Proofs

Yue Shi 999027873 92

Exercise 1 (10 points): Write the converse and the contrapositive of each of the following sentences.

(a) If 5 is prime, then $\sqrt{2}$ is irrational.

$P=$ 5 is prime, $Q=$ $\sqrt2$ is irrational

The proposition is the form like $P\Rightarrow Q$

Since we know that if $P\Rightarrow Q$, then the converse is $Q\Rightarrow P$ and the contrapositive is $\neg Q\Rightarrow \neg P$

Converse $Q\Rightarrow P$ : If $\sqrt2$ is irrational, then 5 is prime

Contrapositive $\neg Q\Rightarrow \neg P$: If $\sqrt2$ is rational, then 5 is not prime

(b) The fish bite only when the moon is full.

Since only when indicates that "the moon is full" is necessary, then the proposition is equivalent to "If the fish bite, then the moon is full"

$P=$ If the fish bite, $Q=$ the moon is full

The proposition is the form like $P\Rightarrow Q$

Since we know that if $P\Rightarrow Q$, then the converse is $Q\Rightarrow P$ and the contrapositive is $\neg Q\Rightarrow \neg P$

Converse $Q\Rightarrow P$ : If the moon is full, then the fish bite.

Contrapositive $\neg Q\Rightarrow \neg P$ : If the moon is not full, then the fish don't bite.

(c) To qualify for the Olympic team, a time of 3 minutes, 48 seconds or less is necessary.

Since "a time of 3 minutes, 48 seconds or less is necessary."

Then the proposition is equivalent to "If the athlete is qualified for the Olympic team, then the time is less or equal than 3 minutes, 48 seconds."

Since we know that if $P\Rightarrow Q$, then the converse is $Q\Rightarrow P$ and the contrapositive is $\neg Q\Rightarrow \neg P$

Converse $Q\Rightarrow P$ : If the time is less or equal than 3 minutes, 48 seconds, then the athlete is qualified for the Olympic team.

Contrapositive $\neg Q\Rightarrow \neg P$ : If the time is greater than 3 minutes, 48 seconds, then the athlete is not qualified for the Olympic team.

Exercise 2 (10 points): Translate the following English sentences into symbolic sentences with quantifiers. The universe in each case is given in parentheses.

(a) Not all precious stones are beautiful. (Universe: all stones)

Let the universe $U$ is all stones, the element $x$ in the universe is one stone.

The proposition $A(x)$ is "$x$ is precious."

The proposition $B(x)$ is "$x$ is beautiful."

All precious stones means $\forall x\in U,A(x)$

All precious stones are beautiful means $\forall x\in U,A(x)\Rightarrow B(x)$

Not all precious stones are beautiful means $\neg (\forall x\in U,A(x)\Rightarrow B(x))$

Thus it is equivalent to $\neg (\forall x\in U,A(x)\Rightarrow B(x))$

(b) Every nonzero real number is positive or negative. (Universe: real numbers)

Let the universe $\R$ is real numbers, the element $x$ in the universe $\R$ is one real number.

The real number is positive means $x>0$

The real number is negative means $x<0$

The real number is positive or negative means $x>0\vee x<0$

Every nonzero real number means $\forall x\neq 0,x\in\R$

Every nonzero real number is positive or negative means we need to use implication $\Rightarrow$

Thus it is equivalent to $\forall x\neq0,x\in\mathbb{R}\Rightarrow x>0\vee x<0$

(c) Every integer is greater than some other integer. (Universe: integers)

Let the universe $\Z$ is integers, the element $x$ in the universe is one integer.

Every integer means $\forall x\in\Z$

Some other integer means $\exists x^{\prime}\in\mathbb{Z}$

greater than means $x>x'$

Thus it is equivalent to $\forall x\in\mathbb{Z},\exists x^{\prime}\in\mathbb{Z},x>x^{\prime}$

(d) Between any real number and any larger real number, there is a rational number. (Universe: real numbers)

Let the universe $\R$ is real numbers, the element $x,y$ in the universe are real numbers.

Any real number means $\forall x\in \R$

Any larger real number means $\forall y\in \R,x<y$

There is a rational number means $\exists q\in\mathbb{Q}$

Between......, there is... means $x<q<y$

Thus it is equivalent to $\forall x\in\mathbb{R},\forall y\in\mathbb{R},x<y\Rightarrow\exists q\in\mathbb{Q},x<q<y$

Exercise 3 (20 points): Which of the following are true in the universe of real numbers?

(a) $(\forall x)(\exists y)(x + y = 0)$

True.

Let $A=\{\exists x,\forall y:x+y\neq 0\}$, we need to prove $A=\emptyset$.

Suppose $A\neq\emptyset$, then let $x_0$ be the minimum element in the set.

Then $\exists x_0,\forall y:x_0+y\neq0$

Let $\forall\varepsilon>0,x_0-\varepsilon<x_0$ is not in the set.

Thus $\exists y^{\prime}:x_0-\varepsilon+y^{\prime}=0\Rightarrow x_0+y^{\prime}-\varepsilon=0$

Then let $y=y'-\varepsilon$, we have $x_0+y^{\prime}-\varepsilon\neq0$, which is a contradiction!

Then $A=\emptyset$, then $(\forall x)(\exists y)(x + y = 0)$

(b) $(\exists x)(\forall y)(x \leq y)$

False.

Suppose it is true.

First we choose specific $x\in\R$, then we can choose any $y\in\R$

Then we can choose $y=x-\varepsilon,\forall\varepsilon>0,\varepsilon\in\mathbb{R}$. Then $x\leq x-\varepsilon\Rightarrow\varepsilon\leq0$, contradiction!

Thus the proposition is false.

(c) $(\forall y)(\exists! x)(x = y^2)$

True.

(Existence) Since $x\in \R$ and $y^2\geq 0$, then there must exists $x$ such that $x=y^2$ for any $y\in\R $

(Uniqueness) Suppose there are two element $x$ and $x'$ such that for any $y$, $x=y^2$ and $x^{\prime}=y^2$

Then we have $x=x'$, contradiction!

Thus the proposition is true.

Exercise 4 (20 points): Prove that if $x, y$ are real numbers, then $x^2 - xy + y^2 \geq 0$.

If $x=0$, then $0-0+y^2=y^2\geq 0$ $\checkmark$

If $x\neq 0$, then we can multiply a positive number $\frac{1}{x^2}$ on both side, which is $1-\frac{y}{x}+\frac{y^2}{x^2}\geq0$

Then $\frac{y}{x}$ is also a real number, we need to prove $\frac{y^2}{x^2}-\frac{y}{x}+1\geq0$

$\frac{y^2}{x^2}-\frac{y}{x}+1\geq0,\forall x,y\in\R $ iff $\Delta<0$ (discriminant of a quadratic function)

$\Delta=(-1)^2-4\cdot1\cdot1=1-4=-3<0$

Thus if $x, y$ are real numbers, then $x^2 - xy + y^2 \geq 0$.

Exercise 5 (20 points): Let $n \in \mathbb{Z}$. Prove that $n^2 + 4n + 7$ is odd if and only if $n$ is even.

$\Rightarrow$) Goal: $n^2 + 4n + 7$ is odd $\Rightarrow$ $n$ is even

We prove it by contrapositive, which is to prove "$n$ is odd $\Rightarrow$ $n^2 + 4n + 7$ is even"

Since $n$ is odd, then $n=2k+1,k\in\Z$

Then $n^2+4n+7=(2k+1)^2+4\left(2k+1\right)+7=4k^2+4k+1+8k+4+7=4k^2+12k+12=2\left(2k^2+6k+6\right)$ is even

Thus $n$ is odd $\Rightarrow$ $n^2 + 4n + 7$ is even which is equivalent to $n^2 + 4n + 7$ is odd $\Rightarrow$ $n$ is even by contrapositive

$\Leftarrow$) Goal: $n$ is even $\Rightarrow$ $n^2 + 4n + 7$ is odd

Let $n=2k,k\in\Z$, then $n^2 + 4n + 7=4k^2+8k+7=2(2k^2+4k+3)+1$ with $2k^2+4k+3\in\Z$

Thus $n^2 + 4n + 7$ is odd

Thus $n^2 + 4n + 7$ is odd if and only if $n$ is even.

Exercise 6 (20 points): Decide if the following statements are true or false. If the statement is true, prove it. If the statement is false, give a counterexample. Let $a, b, c$ be integers:

(a) If $a + b$ is even, then $a$ and $b$ have the same parity. (Definition: $a$ and $b$ have the same parity if they are both even or both odd.)

True.

Suppose $a$ and $b$ don't have the same parity, then let $a$ is even and $b$ is odd.

Let $a=2k,k\in\Z$ and $b=2t+1,t\in\Z$.

Then $a+b=2k+2t+1=2(k+t)+1,(k+t)\in\Z$

Thus $a+b$ is odd, which is a contradiction.

Thus the proposition is true.

(b) If $a$ divides $bc$, then $a$ divides $b$ and $a$ divides $c$.

False.

$3\mid 2\times 6$ but $3 \nmid 2$

(c) If $a$ divides $bc$, then $a$ divides $b$ or $a$ divides $c$.

False.

$6\mid 2\times 3$ but $6\nmid 2$ and $6\nmid 3$

‍