1.3. Proofs

Now that we have a solid understanding of propositional and predicate logic, it is time to actually put them to use. In this section we will examine a few proof methods—strategies to formally prove something. Then, we will see lots of examples of putting them to use.

We have already seen equivalence proofs as one kind of proof. “Proof by truth table” is also another valid option for proving equivalence. Here, we look to prove more general statements that cannot (easily) be proved by a truth table.

---

1.3.1. Theorems

In mathematics, a proof is a very formal thing.

Definition (proof)

A proof is a precise, formal, and valid argument which establishes the truth of a statement.

Much like how satisfiability and consistency have direct applications to computer science, so too do mathematical proofs. For example:

• computer and software system verification;

• cybersecurity and cryptography;

• artifical intelligence; and

• guaranteeing algorithm correctness.

But to find a proof, we must first begin with something to prove. In mathematics we have several different categories of “provable” things.

Definition (theorem)

A theorem is a formal statement that can be shown to be true. It establishes a truth from which other theorems can be proved, or algorithms constructed.

Definition (lemma)

A lemma is a formal statement that can be shown to be true, and is used as part of the proof of another theorem. It is a “helper theorem”.

Definition (proposition)

A proposition is a formal statement that can be shown to be true, but the importance of this fact is less than that of a theorem.

Definition (corollary)

A corollary is a special case of a theorem, lemma, or proposition. It follows directly from a theorem and is not typically proved explicitly. Corollaries are stated to show an “important result” or “important implication” of of a theorem.

Definition (conjecture)

A conjecture is a formal statement that is likely to be true, but has not yet been proved to be true. Once proven to be true, it may become a formal theorem or lemma.

Regarless of whether we are dealing with a theorem, a lemma, or a proposition, the way they are stated and the way they are proved remains the same. So, all of the remaining content in this section applies to a theorem, lemma, etc. We will simply use “theorem” for consistency.

A rose by any other name would smell as sweet.

—Shakespeare

Theorem Statements

Theorems are typically stated as inferences or biconditionals. “If $P$ then $Q$” or “$P$ if and only if $Q$”. Often, mathematicians are not very good at writing so explicitly. They may write “Let $x$ be ‘something something something’ and $y$ have property ‘something’. There is $z$ that ‘something else’”.

Moreover, this structure of using “let $x$ be…” is an implicit universal quantifer. For all $x$ which satisfy this property, the inference (theorem) holds.

With a little practice, we can extract the impliciation from such statements. Indeed, the “language of mathematics” is itself a language, and we need to understand it through practice.

Implicit implications

Consider the following theorem statement.

Theorem

Let $x$, $y$ be positive real numbers such that $x>y$. Then, $x^2>y^2$.

This also means:

“If $x>y$, where $x$ and $y$ are positive real numbers, then $x^2>y^2$.”

Which also means:

“For all positive real numbers $x$ and $y$, if $x>y$, then $x^2>y^2$.”

Notice that the last statement in this previous example is the closest to being a direct translation to predicate logic. Let $P(x,y):=x>y$. Let $Q(x,y):=x^2>y^2$. If we let the domain of $x$ and $y$ be all positive real numbers, then the previous example states $\mathrm{\forall }x\mathrm{\forall }y(P(x,y)\to Q(x,y))$.

Checkpoint

Translating theorems

Translate the following theorems to quantified logic statements.

1. “$4x^4+1=(2x^2+2x+1)(2x^2-2x+1)$ holds for any real number $x$”

2. “Suppose $m$ and $n$ are integers such that $n^2+1=2m$. Then, $m$ must be the sum of squares of two integers.”

Solution

Translating theorems

1. Let $A(x):=4x^4+1=(2x^2+2x+1)(2x^2-2x+1)$. Let the domain of $x$ be all real numbers.

   $$\mathrm{\forall }xA(x)$$

2. Let $P(m,n):=n^2+1=2m$. Let $Q(m,x,y):=m=x^2+y^2$. The domains of $m,n,x,y$ are the integers.

   $$\mathrm{\forall }m\mathrm{\forall }n(P(m,n)\to \mathrm{\exists }x\mathrm{\exists }yQ(m,x,y))$$

---

Proving “obvious” theorems

Sometimes, certain statements are obviously true. Nonetheless, a simple and straight-forward proof is needed. Often, such proofs are used to prove larger or more complex theorems. Here, we will look at two such kinds of proofs before starting “real” proofs.

Consider the implication $p\to q$. If we know that $q$ is true, then the implication is trivially true. A trivial proof is thus a simple statement that shows $q$ to be obviously true.

Trivial proof

Proposition

If it is raining, then 1=1.

Proof:

This implication is trivially true since $1=1$ is known to be true. The truth value of the premise does not matter.

Another obvious proof for implications $p\to q$ relies on $p$ being false. Recall, “falsity implies anything”. If we know $p$ to be false, then the implication $p\to q$ is always true. A vacuous proof is thus a simple statement that shows $p$ to be obviously false.

Vacuous proof

Proposition

If the door is both open and closed, $2+2=5$.

Proof:

This implication is trivially true since the premise is always false (by the law of complementation). The truth value of the conclusion does not matter.

1.3.2. Direct Proofs

A direct proof is one of the most straight-forward types of proofs. If we wish to prove the statement $p\to q$, we assume that $p$ is true and use laws, axioms, and logical equivalences to show that $q$ must also be true.

Another way of defining a direct proof is the following. If we want to prove a statement $A\to B$, we assume $A$ is true and then prove a sequence of implications: $A\to A_1\to A_2\to \cdots \to B$ for some statements $A_1,A_2,\dots$.

Before we see some examples, lets consider a few mathematical definitions.

Definition (even and odd integers)

An integer $m$ is even if it satisfies the formula $m=2k$ for some integer $k$. An integer $n$ is odd if it satisfies the formula $n=2k+1$ for some integer $k$.

Definition (rational number)

A number $n$ is rational if there exists integers $p$ and $q$ such that $n=\frac{p}{q}$ and $q\ne 0$.

In the following two examples, we prove the statement through a direct proof. By assuming $p$ is true, and then showing $q$ must also be true, we have directly proven $p\to q$.

A first direct proof

Proposition

If $n$ is an odd integer, then $n^2$ is odd.

Proof:

Let $P(n):=$ “$n$ is odd”. Let $Q(n):=$ “$n^2$ is odd”. Letting the domain of $n$ be all integers, we look to prove $\mathrm{\forall }n(P(n)\to Q(n))$.

Let us assume $P(n)$ is true. Therefore, there exists some integer $k$ such that $n=2k+1$. Then, $n^2=(2k+1{)}^2=(4k^2+4k+1)=2(2k^2+2k)+1$. Letting $k^{\prime }=2k^2+2k$, we have that $k^{\prime }$ is an integer and $n^2=2k^{\prime }+1$. Therefore, $n^2$ is odd. $◼$

Note that we use the symbol $◼$ to mean “end of proof”. This is also called “Q.E.D.”.

A second direct proof

Proposition

The sum of two rational numbers is rational.

Proof:

Let $P(x):=$ “$x$ is a rational number”, where the domain of $x$ is all (real) numbers. We look to prove $\mathrm{\forall }x\mathrm{\forall }y(P(x)\wedge P(y)\to P(x+y)$.

Let us assume that $x$ and $y$ are rational numbers. Then, there exists integers $a,b,c,d$ such that $x=\frac{a}{b}$, $y=\frac{c}{d}$, $b\ne 0$, and $d\ne 0$. We have:

$$x+y=\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}=\frac{f}{g},$$

where $f=ad+bc$ and $g=bd\ne 0$ are integers. Therefore $x+y$ is rational. $◼$

Note that translating the statement to predicate logic is not required for the proof. These are just shown for the sake of extra practice of translating and understanding theorem statements.

Proving biconditionals

A theorem can also be stated as a conditional instead of just a single conditional, i.e. $p\leftrightarrow q$. In this case, our prove must consist of two parts. Remember that $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$. Therefore, we must prove two implications. In such a proof, proving $p\to q$ is called “proving the sufficient condition”; proving $q\to p$ is called: “proving the necessary condition”.

Note that each implication can be proved in a different way. For example, one implication may be vacuously true while the other requires a direct proof. For a different proof, you may prove on condition with a direct proof, and another condition with an indirect proof (see Indirect Proofs below).

Checkpoint

Translating theorems

Prove the following statement using a direct proof.

Proposition

“A non-zero number $q$ is rational if and only if there exists a non-zero integer $n$ such that $qn$ is an integer.”

Solution

Translating theorems

In this example we are proving a biconditional, an “if and only if”. Therefore, we must prove two conditionals:

1. “If $q$ is a non-zero rational number then there exists a non-zero integer $n$ such that $qn$ is an integer”, and

2. “If $qn$ is an integer for some number $q$ and some non-zero integer $n$, then $q$ is rational.”

Let us prove 1. Assume $q$ is rational. Therefore, $q=\frac{a}{b}$ for some integers $a$, $b$ with $b\ne 0$. Take $n=b$. Then, $nq=n\frac{a}{b}=a$. Since $a$ is an integer, so is $qn$.

Let us prove 2. Assume $n$ is a non-zero integer and $qn$ is an integer. That means there exists an integer $r$ such that $qn=r$. Since $n$ is non-zero, we can divide both sides by n and we get $q=\frac{r}{n}$. Since both $r$ and $n$ are integers, $q$ is a rational number. $◼$

1.3.3. Indirect Proofs

In an indirect proof we look to prove a statement like $A\to B$ without following a sequence of implications $A\to A_1\to \cdots \to B$ to prove $A\to B$. Instead, we proceed in an unexpected way.

There are two main types of indirect proofs. Proof by contrapositive and proof by contradition.

Proof by Contrapositive

To prove a statement $p\to q$ we will instead prove that $\mathrm{\neg }q\to \mathrm{\neg }p$. Indeed, recall from Implication, Inverse, Converse, and Contrapositive that an implication and its contrapositive positive are equivalent. That is, $p\to q\equiv \mathrm{\neg }q\to \mathrm{\neg }p$.

Proving the contrapositive can be done using any other proof method. Typically, one proves the contrapositive directly. But this is not always true. Let’s consider an example where we do prove the contrapositive directly.

Proof by contrapositive

Proposition

If $n$ is an integer such that $3n+2$ is odd, then $n$ is odd.

Proof:

We will proceed by proof by contrapositive. Assume $n$ is not odd. Then, we must prove $3n+2$ is not odd. Since $n$ is not odd, it is even and we have $n=2k$ for some integer $k$. Then, $3n+2=3(2k)+2=6k+2=2(3k+1)$. Letting $k^{\prime }=3k+1$ we have $3n+2=2k^{\prime }$. Hence, it is even. $◼$

In this previous example, notice that you may have interpreted the theorem statement as “if ($n$ is an integer AND $3n+2$ is odd) then ($n$ is odd)”. However, since odd and even are properties of the integers only, it makes more sense to interpret this theorem statement as “for any integer $n$, if $3n+2$ is odd then $n$ is odd”. That is, we restrict the domain of $n$ to be the integers.

Important

When reading and interpreting theorem statements, be sure to distinguish between what is part of the premise, and what is part of the domain of discourse.

Proof by Contradiction

In a proof by contradiction, we look to assume some fact and then find a contradiction. Recall that a contradiction is a statement is always false.

Typically, we are looking to prove some statement $p$. To do so by contradiction, we assume $\mathrm{\neg }p$ is true and derive a contradiction. That is, we show that $\mathrm{\neg }p\to A_1\to A_2\to \cdots \to \mathbf{F}$, for some statements $A_1,A_2,\dots$.

By contrapositive, if $\mathrm{\neg }p\to \mathbf{F}$ holds then $\mathbf{T}\to p$ holds. Therefore, $p$ must be true.

Proof by contradiction

Theorem

There is no largest integer.

Proof:

Proceed by proof by contradiction. Assume that there does exist some largest integer. Call such an integer $n$. But, $n+1$ is also an integer and $n+1$ is strictly larger than $n$. Therefore, our assumption that a largest integer exists is false. That is, there is no largest integer is true. $◼$

1.3.4. Strategies to help with proofs

In this section we will see some examples that will help with writing and deciphering proofs. These strategies can be incorporated into various different proof methods.

1. Finding errors in proofs

2. Proof by cases

3. Without loss of generality

4. Disproof by counterexample

Finding errors in proofs

Remember that a proof is a logical and sequential argument. A proof only holds is every step along the way is correct. A single “misstep” makes a proof invalid and thus, not proving anything. Try to find the error in the following proof.

Checkpoint

An incorrect proof

Proposition

$1=2$

Proof:

1. $a=b$

2. $a^2=ab$

3. $a^2-b^2=ab-b^2$

4. $(a-b)(a+b)=b(a-b)$

5. $a+b=b$

6. $2b=b$

7. $2=1$

1. Premise

2. Multiply both sides by $a$

3. Subtract $b^2$ from both sides

4. Factor both sides

5. Divide both sides by $a-b$

6. Since $a=b$, $a+b=2b$.

7. Divide both sides by $b$.

Solution

Translating theorems

Proof:

1. $a=b$

2. $a^2=ab$

3. $a^2-b^2=ab-b^2$

4. $(a-b)(a+b)=b(a-b)$

5. $a+b=b$

6. $2b=b$

7. $2=1$

1. Premise

2. Multiply both sides by $a$

3. Subtract $b^2$ from both sides

4. Factor both sides

5. Divide both sides by $a-b$

6. Since $a=b$, $a+b=2b$.

7. Divide both sides by $b$.

At step 5, we cannot divide by $(a-b)$! We assumed $a=b$, therefore $a-b=0$ and we cannot divide by 0.

Proof by cases

In a theorem, it is possible that the premise itself is a compound statement. The compound statement may be explicit, like “Let $a=1$ or $a=-1$”, or implicit, like “let $n$ be an integer”. In this latter statement, there are different kinds of cases you could apply. You could consider $n$ to be odd or even. You may consider $n$ to be zero, positive, or negative.

There are two steps in a proof by cases:

1. Extract from the theorem statement the possible cases; and

2. Prove each case independently.

The validity of a proof by cases comes from the following logical equivalence:

$$(p_1\vee p_2\vee \cdots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \cdots \wedge (p_n\to q)$$

Each of the “or” conditions in the premise is a separate case that we must prove.

Proof by cases

Proposition

Let $x$ and $y$ be real numbers. If $x\ne 0$ or $y\ne 0$ then $x^2+y^2\ne 0$.

Proof:

First, consider $x\ne 0$. Then, $x^2\ne 0$ and $x^2>0$. We also know $y^2\ge 0$ without any further assumptions. Therefore, $x^2+y^2$ is strictly greater than 0.

Second, consider $y\ne 0$. Again, $y^2\ne 0$ and $y^2>0$. Therefore, since $x^2\ge 0$, $x^2+y^2$ is strictly greater than 0. $◼$.

Notice in this previous proof that the proof for each case is identical, up to the “naming” of $x$ as the variable of interest or $y$ as the variable of interest. This brings us to our next idea: without loss of generality.

Without loss of generality

Without loss of generality, often abbreviated to w.l.o.g., is a way for provers to be lazy. When two cases are sufficiently similar, one only needs to give a proof to one of the cases.

What constitutes as “sufficiently similar”? Typically, it will be an arbitrary choice made throughout the proof for which the other choice would be equally as valid. Such an arbitrary choice should be symmetric.

For example, if proving a statement regrading two integers $a$ and $b$. One can assume, without loss of generality, that $a\ge b$. Since $a$ and $b$ do not have any other conditions imposed on them, it is an arbitrary choice to say “$a\ge b$”. It is equally valid to say “$b\ge a$”.

Without loss of generality

Proposition

For two integers $x$ and $y$, if $xy$ and $x+y$ are both even, then both $x$ and $y$ are even.

Proof:

We provide a proof by contrapositive. Suppose that it is not that case that both $x$ and $y$ are even. That is, one or both of $x$ and $y$ are odd. We then look to prove that $xy$ and $x+y$ are not both even. We will prove this contrapositive by cases.

Without loss of generality, assume that $x$ is odd. Thus, $x=2k+1$ for some integer $k$.

Case 1: $y$ is even and $y=2\ell$ for some integer $\ell$.

$$x+y=(2k+1)+2\ell =2(k+\ell )+1$$

Therefore, $x+y$ is odd.

Case 2: $y$ is odd and $y=2\ell$ for some integer $\ell$.

$$xy=(2k+1)(2\ell +1)=4k\ell +2k+2\ell +1=2(2k\ell +k+\ell )+1$$

Therefore, $xy$ is odd.

In either case, at least one of $x+y$ or $xy$ is odd. This proves the contrapositive and thus the proposition. $◼$

In this example, we used w.l.o.g. to state that we made an arbitrary choice. We chose that $x$ is odd. We could have equally made the choice that $y$ was odd and then proved the two cases that $x$ was even or $x$ was odd. Since either choice would follow the same proof, they are “sufficiently similar” and we only need to prove one of the choices.

Disproof by counterexample

We have seen that many theorems are stated in the form $\mathrm{\forall }xP(x)$. Rather than prove such a statement, one could also disprove the statement. That is, one can prove that $\mathrm{\forall }xP(x)$ is false. But, how?

From predicate logic we know that if $\mathrm{\forall }xP(x)$ is false, then $\mathrm{\neg }\mathrm{\forall }xP(x)$ is true. Moreover, $\mathrm{\neg }\mathrm{\forall }xP(x)\equiv \mathrm{\exists }x\mathrm{\neg }P(x)$.

A proof by example is a proof of $\mathrm{\exists }xQ(x)$ by finding a particular example for which $Q(x)$ is true. Letting $Q(x)$ be $\mathrm{\neg }P(x)$, we can thus disprove our original statement $\mathrm{\forall }xP(x)$.

Disproof by counterexample

Conjecture

For a real number $x$, if $x<1$, then $x^2<1$.

Let $P(x):=x<1$. Let $Q(x):=x^2<1$. We look to disprove $\mathrm{\forall }x(P(x)\to Q(x))$. That is, we should prove $\mathrm{\exists }x\mathrm{\neg }(P(x)\to Q(x))$. This implication is false if $P(x)$ is true and $Q(x)$ is false.

$x=-2$ is such a counterexample. $P(-2)$ is true since $-2<1$. However, $Q(-2)$ is false since $(-2{)}^2=4\nless 1$.

Therefore, this conjecture is false.

1.3.5. Even more types of proofs

Up to this point we have seen several different kinds of proofs and proof strategies:

• Direct proof

• Proof by contrapositive

• Proof by contradiction

• Proof by cases

• Disproof by counterexample

We will see even more proof methods in later chapters of this course. Most importantly, induction. To conclude this chapter we see two more kinds of closely related proofs. Existence proofs and uniqueness proofs.

Existence proofs

Existence proofs look to prove theorems of the form $\mathrm{\exists }xP(x)$. These are very similar to using counterexamples to disprove a statement.

There are two kinds of existence proofs for $\mathrm{\exists }xP(x)$.

1. A constructive proof finds a witness $a$ such that $P(a)$ is true. Thus proving that the statement with the existential quantifier is true. Constructive proofs may provide the witness itself or provide a method for “constructing” a witness.

2. A nonconstructive proof proves that a witness must exist (usually in some indirect way) without providing a particular witness.

Constructive proof

Theorem

There is a positive integer that is equal to two different sums of cubes of positive integers.

Proof:

$$1729={10}^3+9^3={12}^3+1^3◼$$

You might now say: where did that proof come from? Indeed, the difficulty with existence theorems is that finding a witness can be very challenging. Moreover, it is often equally as difficult to disprove an existence theorem. That is, it is just as difficult to prove that $\mathrm{\neg }\mathrm{\exists }xP(x)\equiv \mathrm{\forall }x\mathrm{\neg }P(x)$ is true.

Aside (open problems)

Such problems that have not yet been proven to be true, but also not yet proved to be false, are open problems. Open problems often have a conjecture associated with them. It is often the case that research continues in certain directions with the assumption that a conjecture is true.

If a conjecture is later found to be false, then all of that work which assumed the opposite is immediately invalidated. Such open problems are therefore very “high stakes”.

The Millenium Prize Problems are 7 open problems with particularly high stakes. In 2000, the Clay Mathematics Institute issued a bounty of $1,000,000 to each problem. The person who proved (or disproved) one of the problems would be awarded $1,000,000. In 22 years, only one of those problems has been solved: the Poincaré conjecture.

The biggest, and arguably most consequential, open problem is $\mathcal{P}\stackrel{?}{=}\mathcal{NP}$. This question says, can any problem which is easily verified be easily solved?

In some sense, this is related to existence proofs. Once we have a witness, it is very easy to verify if that witness satisfies the theorem. But, is it always easy to find a witness? That is the open question of whether or not $\mathcal{P}=\mathcal{NP}$.

Most of computer science has been developed under the assumption that $\mathcal{P}\ne \mathcal{NP}$. For example, everything related to cryptography and cybersecurity relies on $\mathcal{P}\ne \mathcal{NP}$. You’ll learn more about that in CS3331.

Another way of performing a constructive proof is a give a method or algorithm to construct/compute a witness. This is a core principle which underlies the theory of computer science. You start with a theorem statement, prove that a solution exists by providing an algorithm to compute one, and then and only then do you implement the algorithm in a programming language.

Going the other way may not work out for you. If you try to implement an algorithm before you have proven that thing you are trying to do exists, then you may never be able to finish the algorithm because no such algorithm exists.

Even without an algorithm to construct a witness, it may still be possible to prove an existence theorem. That kind of proof would be a nonconstructive existence proof.

Nonconstructive proof

Theorem

There exists irrational numbers $x$ and $y$ such that $x^y$ is rational.

Proof:

We know $\sqrt{2}$ is irrational (see Exercise 1.38). Let $x=y=\sqrt{2}$.

We have two cases: ${\sqrt{2}}^{\sqrt{2}}$ is rational or irrational. In the first case, the theorem is obviously true and we are done. Consider the second case. Let $x={\sqrt{2}}^{\sqrt{2}}$. Let $y=\sqrt{2}$. By assumption $x$ is irrational and we know $y$ to be irrational. Then, we have:

$$x^y={\sqrt{2}}^{{\sqrt{2}}^{\sqrt{2}}}={\sqrt{2}}^{\sqrt{2}\sqrt{2}}={\sqrt{2}}^2=2$$

Surely 2 is rational, and we have proved the statement in both cases. $◼$.

Notice that this proof does not provide a particular witness. Rather, the proof showed that either $x^y={\sqrt{2}}^{\sqrt{2}}$ is rational or $x^y={\sqrt{2}}^{{\sqrt{2}}^{\sqrt{2}}}$ is rational. But, we do not know which is the witness.

---

Uniqueness proofs

The last kind of proof we will discuss in this chapter is uniqueness proofs. These are a form of existence proofs where we want to prove a statement of the form “there exists a unique $x$ such that $P(x)$”.

This kind of theorem statement can be written using special notation: $\mathrm{\exists }!xP(x)$. $\mathrm{\exists }!$ means that there exists exactly one element from the domain of discourse that satisfies the predicate.

Proving uniqueness can be very tricky. Indeed, proving $\mathrm{\exists }!xP(x)$ is the same as proving a more complicated statement:

$$\mathrm{\exists }x(P(x)\wedge \mathrm{\forall }y(y\ne x\to \mathrm{\neg }P(y)))$$

or, equivalently:

$$\mathrm{\exists }x(P(x)\wedge \mathrm{\forall }y(P(y)\to y=x))$$

Therefore, there are two parts of a uniqueness proof.

1. Existence: we must show that an $x$ exists such that $P(x)$ is true.

2. Uniqueness: we must show if $y\ne x$ then $P(y)$ is false or we must show that if $P(y)$ is true then $y=x$ (they are contrapositives).

Uniqueness proof

Theorem

If $a$ and $b$ are real numbers such that $a\ne 0$, then there is a unique real number $r$ such that $ar+b=0$.

Proof:

Existence: Since $a\ne 0$ we have $ar+b=0⟹r=\frac{-b}{a}$.

Uniqueness: Proceed by contradiction. Suppose $s$ is a real number such that $s\ne r$ and $as+b=0$. Since this and the previous equation both equal $0$, we have:

$$\begin{array}{r}ar+b=as+b\\ ar=as\\ r=s\end{array}$$

Since we chose $s$ arbitrarily and arrived at the fact the $r=s$, we know that $r$ is unique. $◼$

1.3.6. Exercises

Exercise 1.33

Let $n$ be an integer. Prove that $n$ is even if and only if $n^2$ is even.

Solution to Exercise 1.33

First prove $n$ even $\to$ $n^2$ even.

Let $n=2k$ for some integer $k$. Then $n^2=(2k{)}^2=4k^2=2(2k^2)$. Therefore, $n^2$ is even.

Second, prove $n^2$ is even $\to$ $n$ is even. Let’s proceed by contrapositive.

Let $n$ be odd. Thus, $n=2k+1$ for some integer $k$. Then, $n^2=(2k+1{)}^2=4k^2+4k+1=2(2k^2+2k)+1$. If we let $k^{\prime }=(2k^2+2k)$, thus $k^{\prime }$ is an integer, $n=2k^{\prime }+1$ and, therefore, $n^2$ is odd. By contrapositive, $n^2$ is even $\to$ $n$ is even. $◼$

Exercise 1.34

Let $n$ be a positive integer. Prove that if $3n^2+8$ is even then $n$ is even.

Solution to Exercise 1.34

Proceed by contrapositive. Assume that $n$ is odd. Then there is an integer $k$ such that $n=2k+1$. Then, we have:

$$3n^2+8=3(2k+1{)}^2+8=3(4k^2+4k+1)+8=2(6k^2+6k+5)+1$$

Letting $k^{\prime }=6k^2+6k+5$, we have $3n^2+8=2k^{\prime }+1$. Since $k^{\prime }$ is an integer, $3n^2+8$ is odd. $◼$

Exercise 1.35

Let $n$ be a positive integer. Prove that if $n$ is even then $5n+3n^3$ is even.

Solution to Exercise 1.35

By hypothesis $n$ is even and thus there exists an integer $k$ such that $n=2k$. We directly prove $5n+3n^3$ is even:

$$5(2k)+3(2k{)}^3=10k+24k^3=2(5k+12k^3)$$

Letting $k^{\prime }=5k+12k^3$, we have $5n+3n^3=2k^{\prime }$. Since $k^{\prime }$ is an integer, $5n+3n^3$ is even. $◼$

Exercise 1.36

Prove the following by a direct proof.

Proposition

If $p$ is a prime number larger than $2$, then $p^2$ is odd.

Solution to Exercise 1.36

Assume $p$ is a prime larger than $2$. $p$ must be odd. If $p$ was even, it could be written as $2k$ for some integer $k$, and therefore not be prime.

Now, we know from Exercise 1.33 that an integer is even if and only if its square is even. This also means that an integer is odd if and only if its square is odd. Since $p$ is odd, so is $p^2$. $◼$

Exercise 1.37

Prove the following by contrapositive.

Proposition

Let $q$ be a number. If $5q$ is not rational then $q$ is not rational.

Solution to Exercise 1.37

Proceed by contrapositive. We look to prove that if $q$ is rational then $5q$ is rational.

By hypothesis, $q$ is rational, thus there exists integers $a$ and $b$ such that $q=\frac{a}{b}$ with $b\ne 0$.

Then, $5q=\frac{5a}{b}$. Since $a$ and $5$ are both integers, $5a$ is an integer. Since $5a$ and $b$ are integers with $b\ne 0$, then $5q$ is rational. $◼$

Exercise 1.38

Prove the following proposition using proof by contradiction.

Proposition

$\sqrt{2}$ is irrational.

Solution to Exercise 1.38

Suppose $\sqrt{2}$ is rational. Then there exists integers $a$ and $b$, $b\ne 0$, with $\sqrt{2}=\frac{a}{b}$. Moreover, $\frac{a}{b}$ is a reduced fraction written in lowest terms (i.e. $a$ and $b$ share no common factors).

Then, $(\sqrt{2}{)}^2=2=\frac{a^2}{b^2}⟹2b^2=a^2$. Thus, $a^2$ is even and thus $a$ is even (this is Exercise 1.33). Thus there exists an integer $c$ with $a=2c$. Then, $2b^2=(2c{)}^2=4c^2$.

Therefore, $b^2=2c^2$ and $b$ is even. Since both $a$ and $b$ are even, they both have 2 as a factor and $\frac{a}{b}$ was not written in lowest terms. Therefore, our assumption that $\sqrt{2}$ was rational is false. $◼$

Exercise 1.39

Prove the following proposition using proof by contradiction.

Proposition

Let $q$ be a non-zero rational number and $r$ be an irrational number. $qr$ is irrational.

Solution to Exercise 1.39

We look to prove “$q$ is a non-zero rational and $r$ is irrational” $\to$ “$qr$ is irrational”. Proceed by contradiction and assume that this implication is false. This only occurs when the premise is true and the conclusion is false, thus we assume $qr$ is rational.

Thus, there exists integers $m$, $n$ such that $qr=\frac{m}{n}$ and $n\ne 0$. Since $q$ is rational we also have that $q=\frac{a}{b}$ for integers $a$, $b$ with $b\ne 0$. Moreover, $q$ being non-zero means $a\ne 0$. Therefore, we have:

$$qr=\frac{m}{n}⟹r=\frac{m}{nq}⟹r=\frac{mb}{na}$$

Since $na\ne 0$, $r$ must be rational. This is a contradiction. Therefore, our assumption that $qr$ was rational is incorrect and $qr$ must be irrational. $◼$

Exercise 1.40

Prove that the following propositional formula is a tautology.

$$((p\to q)\wedge (q\to r))\to (p\to r)$$

Solution to Exercise 1.40

First, we replace all implications $a\to b$ with $\mathrm{\neg }a\vee b$. Then simplify using laws.

$$\begin{array}{r}(\mathrm{\neg }p\vee q)\wedge (\mathrm{\neg }q\vee r))\to (\mathrm{\neg }p\vee r)\\ \mathrm{\neg }((\mathrm{\neg }p\vee q)\wedge (\mathrm{\neg }q\vee r))\vee (\mathrm{\neg }p\vee r)\\ \mathrm{\neg }(\mathrm{\neg }p\vee q)\vee \mathrm{\neg }(\mathrm{\neg }q\vee r))\vee (\mathrm{\neg }p\vee r)\\ (p\wedge \mathrm{\neg }q)\vee (q\wedge \mathrm{\neg }r)\vee (\mathrm{\neg }p\vee r)\end{array}$$

We will prove the latter formula by cases. (You could also use a truth table).

Case 1: if $(p\wedge \mathrm{\neg }q)$ is true, the whole formula is true by disjunction and annihilation. Therefore, $p$ is true and $q$ is false, and $r$ can be anything.

Case 2: now, either $p$ is false or $q$ is true.

Case 2.a: if $p$ is false, $(q\wedge \mathrm{\neg }r)\vee (\mathrm{\neg }p\vee r)$ is always true, since $(\mathrm{\neg }p\vee r)$ is true, regardless of the truth values of $q$ or $r$.

Case 2.b: if $q$ is true, $(q\wedge \mathrm{\neg }r)\vee (\mathrm{\neg }p\vee r)$ reduces to $\mathrm{\neg }r\vee \mathrm{\neg }p\vee r$. Since we have $\mathrm{\neg }r\vee r$, this is true regardless of the truth value of $p$ or $r$.

Therefore, in all possible truth assignments, the formula is true. It is a tautology. $◼$

Exercise 1.41

Prove that ${\log }_2(9)$ is an irrational number.

Solution to Exercise 1.41

We proceed by proof by contradiction.

Suppose ${\log }_2(9)$ was rational, then there exists integers $m,n$ with $n\ne 0$ such that ${\log }_2(9)=\frac{m}{n}$. Moreover, ${\log }_2(9)>0$, therefore $m>0$ and $n>0$. By laws of logarithms we have the following equalities:

$$\begin{array}{r}{2}^{\frac{m}{n}}=9\\ 2^m=9^n\end{array}$$

Since $m$ and $n$ are both positive, $2^m\ge 2$ and $9^n\ge 9$. In the former case, $2^m$ is an even number for any $m>0$. In the latter case, $9^n$ is an odd number for any $n>0$. Indeed, $9^n={(3^2)}^n$ and it is easy to prove that the product of two or more odd numbers is odd. But, an even number cannot equal an odd number. Therefore, $2^m\ne 9^n$ for any choice of $m$ and $n$. A contradiction. Hence, ${\log }_2(9)$ must be irrational. $◼$

Exercise 1.42

Recall the absolute value function, $|x|$ is defined as:

$$\begin{array}{r}|x|=\{\begin{array}{rl}x,& \text{if }x\ge 0\\ -x,& \text{if }x<0\end{array}\end{array}$$

Prove that $|a+b|\le |a|+|b|$ for any real numbers $a$ and $b$.

Solution to Exercise 1.42

Proceed by cases.

1. $a\ge 0,b\ge 0$. Therefore, $a+b\ge 0$, and $|a+b|=a+b=|a|+|b|$

2. $a<0,b\ge 0$. Therefore, $a+b=b-|a|$ and $a+b$ is negative if and only if $|a|>b$.

   • 2.a: if $|a|>b$ then $a+b<0$ and $|a+b|=|a|-b\le |a|+b=|a|+|b|$

   • 2.b: if $|a|\le b$ then $a+b\ge 0$ and $|a+b|=b-|a|\le b+|a|=|a|+|b|$

3. Case 3 is the same as Case 2.

4. $a<0,b<0$. Therefore $a+b<0$ and we have $|a+b|=|a|-b\le |a|+|b|$. $◼$