## Section2.6Mathematical Statements

In the homework you started to think about mathematical statements, conjectures and proofs. Let's be more precise about what we mean with those terms.

###### Definition2.6.1.
A mathematical statement is a sentence that can logically be determined to be either true or false
###### Example2.6.2.

Which of the sentences below are statements? If they are statements, determine if they are true or false.

1. 8 is an even number.
2. 9 is an even number.
3. $x$ is an even number.
4. Do you like even numbers?
5. $2+4+6\text{.}$
6. An even number plus an even number is an even number.
7. An odd number plus an odd number is an even number.
8. I love even numbers.
1. 8 is an even number. This is a statement and it is true.
2. 9 is an even number. This is a statement but it is false.
3. $x$ is an even number. This is not a statement because $x$ is a variable and this statement could be either true or false based on the value for $x\text{.}$
4. Do you like even numbers? This is not a statement. It is a question and cannot be determined to be either true or false.
5. $2+4+6\text{.}$ This is not a statement. There is nothing to determine true or false.
6. An even number plus an even number is an even number. This is a statement and it is true.
7. An odd number plus an odd number is an odd number. This is a statement but it is false.
8. I love even numbers. This one is a little tricky. While we might consider this to be a sentence that we could determine true or false, it depends on my opinion towards even numbers and this is not generally something we can formally prove to be true or false. You can ask me, but you have to believe my answer rather than use logical deductions to determine if the sentence is true or false. We would not consider this a mathematical statement. OK, but do I love even numbers? Answer
As a mathematician, even I have trouble answering this question for myself. I like even numbers, but I think prime numbers and Fibonacci numbers are even cooler. What does it even mean to love a set of numbers? And so on. This is not a question where it's easy to say true or false based on some objective criteria. Hint
ZT HE UZ LE BL TH SF RC FH RC SC TD AH NL CL SN PB HU FB EZ TH RC HM MI HU BF ZT HE ME NU HK SF AL HC EL BN FN NK TH ZH ZP ON FQ ZT AE BG CP CD CL IN AD IB ZA HC ZA EZ YI FB EH HC ZA FE BH ZT UZ HE AS XQ LN NF UZ QB EH EZ CL NF UZ CN HR LH BW NH GF FB EH IB BH ZT UH AU GV QK BN EH BX NF HE KE BH CD UN CR HZ ZC EZ WG BW EF PU QI AL GI NK TH UK KD BQ SF EK CH NW HZ BG AU GV QK ZT AE CH RC HM

The discussion for the last example sentence really starts to talk about what a mathematical proof is.

###### Definition2.6.3.
A mathematical proof is a convincing argument that a statement is true. A proof requires using logical deduction to show that a statement follows from other previously accepted or proven statements.

To see what this means let's prove or disprove the mathematical statements in Example 2.6.2. All of these statements are about even numbers. So we must have an agreement about what an even number is. This is where we turn to definitions. A definition in mathematics is precise description for a term. Definitions are not the same as statements; they are neither true nor false. They are choices we make about how we want to talk about mathematical objects. We could define the word “even” to mean anything we like. But likely you already have a strong idea for what even and odd means. A definition must be precise enough that we can easily determine if an object satisfies that criteria or not.

###### Definition2.6.4.
An integer $n$ is even if $n=2k$ for some integer $k\text{.}$
###### Definition2.6.5.
An integer $n$ is odd if $n=2k+1$ for some integer $k\text{.}$

To show that 8 is even, we can write $8=2(4)\text{.}$ Since $k$ is an integer, we can see that 8 satisfies the definition of even. If we try to write $9=2(k)$ we would need $k=9/2=4.5$ which is not an integer, so 9 is not even and we have proven that the statement 9 is even is false. Once we have shown a statement is true we can call it a theorem (or proposition, lemma, corollary, etc). We will use that language for the other true statement in our example.

To show that an even number plus an even number is an even number, we will have to do a little more work. We will introduce some variables. Let $x,y$ be even numbers. Applying our definition of even, $x=2k$ for some integer $k$ and $y=2l$ for some integer $l\text{.}$ Note, we need two different variables $k,l$ here. Why would letting $y=2k$ for some integer $k$ be a problem? Answer
This would imply that $y=x$ so that it would only show the result for a special case and not the general statement for any two even numbers.
Then $x+y=2k+2l=2(k+l)\text{.}$ Since $k$ and $l$ are both integers, then $k+l$ is an integer, so $x+y$ also satisfies the definition of integer.

Note the importance of using definitions in a mathematical proof! To show that the statement an odd number plus an odd number is an odd number is is false, it suffices to provide a counterexample.

###### Definition2.6.7.
A counterexample is a specific example where the statement is false.

To give a counterexample to the statement an odd number plus an odd number is an odd number, let $x=3$ and $y=5\text{.}$ These numbers are odd since $3=2(1)+1$ and $5=2(2)+1\text{.}$ But $3+5=8$ which is even.

Note that to show a statement is false, a single counterexample is enough. However, to show a statement is true, it is never enough to produce examples. (Although working through examples is often useful as a background step to figure out how the proof should go!) We must show that it is true for all possible cases.

Many of the mathematical statements we want to prove will be in the form of an implication.

###### Definition2.6.8.

An implication is a statement of the form if A then B. This can be written as $A \Rightarrow B\text{.}$

Implications are compound statements. It is asking if statement A implies statement B. Let's begin with an example of slightly non-mathematical statements.

###### Example2.6.9.

Statement: If I am eating tacos, then I am eating guacamole.

There are four possible different scenarios that may apply.

1. I am eating tacos and I am eating guacamole.
2. I am not eating tacos and I am eating guacamole.
3. I am eating tacos and I am not eating guacamole.
4. I am not eating tacos and I am not eating guacamole.

Which of this scenarios makes the implication “If I am eating tacos, then I am eating guacamole” false? Answer

There is only one scenario that proves the implication is false, that is the scenario “I am eating tacos and I am not eating guacamole.” Note that if I am never eat tacos then this implication is always true, because there is no way to contradict the implication.

For a more mathematical version, we will rewrite the statement “an even number plus an even number is an even number” as an implication. If both $x,y$ are even, then $x+y$ is even.

Some important ideas related to an implication are the converse and contrapositive.

###### Definition2.6.10.

The converse of “If A then B” is “If B then A”. This can be written as $B \Rightarrow A\text{.}$

###### Definition2.6.11.

The contrapositive of “If A then B” is “If not B then not A”. This can be written as $\neg B \Rightarrow \neg A\text{.}$

###### Example2.6.12.

For the implication “if $x,y$ are even, then $x+y$ is even” state the converse and the contrapositive. Then determine if the converse and the contrapositive are true or false.

Converse: If $x+y$ is even then both $x,y$ are even.

The converse is false. We can show this with a counterexample. Let $x=3$ and $y=5\text{.}$ Then $x+y=3+5=8$ is even, but neither $x=3$ nor $y=5$ is even.

Contrapositive: If $x+y$ is not even then it is not the case that both $x,y$ are even.

The contrapositive is true. In this case we will do some rewriting to make this statement more clear using what we know about the relationship between odd and even. Not that we must be careful about it means that not both of $x,y$ are even.

Contrapositive: If $x+y$ is odd then at least one of $x,y$ is odd.

Assume $x+y$ is odd so $x+y=2k+1$ for some $k\text{.}$ Solving for $x$ we get $x=2k+1-y\text{.}$

Case 1: If $y$ is odd then we are done because at least one of $x,y$ is odd.

Case 2: If $y$ is even, then $y=2s$ for some integer $s\text{.}$ Then, $x=2k+1-y=2k+1-2s=2(k-s)+1$ satisfies the definition of odd since $k-s$ must be an integer. Thus in this case also at least one of $x,y$ is odd.

The important part of converse and contraposition is that the converse of a statement is a very different statement. It may or may not be true if a statement is true. However, the contrapositive of a statement is always the same as a statement. Let's examine why this is true in general. The only way that “if A then B” is false is if A is true and B is false. The converse “if B then A” is false only if B is true and A is false. These are different conditions and so an implication and its converse are very different statements. However the contrapositive “if not B then not A” is false only if not B is true and not A is false. This means B is false and A is true. This is exactly the same condition for making the original implication false. The contrapositive can be helpful in mathematical proofs because sometimes the contrapositive of an implication is easier to prove.

Let's do one more definition and example.

###### Definition2.6.13.

The greatest common divisor of integers $a$ and $b\text{,}$ $\gcd(a,b)=d$ if $d$ divides both $a$ and $b$ and for any other common divisor, $e\text{,}$ of $a$ and $b$ then $e \leq d\text{.}$

For example $\gcd(4,6)=2\text{,}$ $\gcd(6,21)=3\text{,}$ and $\gcd(4,9)=1\text{.}$ If the gcd of two numbers is one, this is such an important case that we have additional terminology. We say 4 and 9 are relatively prime.

###### Definition2.6.14.

The numbers $a$ and $b$ are relatively prime if $\gcd(a,b)=1\text{.}$

###### Example2.6.15.

For the implication, if $\gcd(x,2)=2\text{,}$ then $x$ is even, state the converse and the contrapositive. For all of the statements, determine if they are true or false.

Implication: If $\gcd(x,2)=2\text{,}$ then $x$ is even.

The implication is true. By definition of gcd, 2 divides $x\text{,}$ but this is also the definition of even.

Converse: If $x$ is even then $\gcd(x,2)=2\text{.}$

In this case, the converse is also true. If $x$ is even, then 2 divides $x\text{.}$ It is also true that 2 divides 2 and 2 is the largest possible divisor of 2. Thus, there cannot be a larger common divisor of 2 and $x\text{,}$ therefore $\gcd(x,2)=2\text{.}$

Contrapositive: If $x$ is odd then $\gcd(x,2) \neq 2\text{.}$

The contrapositive is true. We don't need to prove this since we know the contrapositive is the same as the implication and we proved the implication. However, it is a good example of a proof by contradiction. For a proof by contradiction we assume that the statement we are trying to show is is false and make logical arguments until we arrive at a contradiction. In this case, we assume that $x$ is odd, so $x=2k+1$ for some integer $k$ by definition of odd. Then for the purposes of making a contradiction we assume $\gcd(x,2) = 2\text{.}$ From the definition of gcd, this means that 2 divides $x\text{,}$ so $x=2s$ for some integer $s$ by definition of divide. But this means $x$ is even. A number cannot be both even and odd, so we have a contradiction. Thus our assumption that $\gcd(x,2) = 2$ must be wrong. Therefore, $\gcd(x,2) \neq 2$

Note in the case that an implication and its converse are both true, we have a stronger condition usually written as an “if and only if” statement. That is we could say $\gcd(x,2)=2$ if and only if $x$ is even. When we are trying to prove statements that have an if and only if, then we must prove both directions, the implication and its converse.

There is one last term that we should define. Throughout this class you will often be asked to make a conjecture. What is a conjecture and how do you make one? A conjecture is a guess. It is a mathematical statement that seems plausible but hasn't yet been proven. We usually make conjectures by looking at lots of examples, trying to identify a pattern, and stating the pattern as precisely as we can in a conjecture.

###### Example2.6.16.
Compute $1+2+3+\cdots +n$ for many values of $n$ and guess a formula for this sum in terms of $n\text{.}$
\begin{equation*} 1+2+3=6 \end{equation*}
\begin{equation*} 1+2+3+4=10 \end{equation*}
\begin{equation*} 1+2+3+4+5=15 \end{equation*}
\begin{equation*} 1+2+3+4+5+6=21 \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7=28 \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7+8=36 \end{equation*}

We are trying to find this in terms of $n$ so let's play around with getting $n$ into our equations. I'm choosing to factor a copy of $n$ because I notice that in some of the terms. There's no right answer for what to try first and you may have to try lots of things before the pattern emerges.

\begin{equation*} 1+2+3=6=3(2) \end{equation*}
\begin{equation*} 1+2+3+4=10=4\left(\frac{5}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5=15=5(3) \end{equation*}
\begin{equation*} 1+2+3+4+5+6=21=6\left(\frac{7}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7=28=7(4) \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7+8=36=8\left(\frac{9}{2}\right) \end{equation*}

Well, now we could rewrite a little more:

\begin{equation*} 1+2+3=6=3\left(\frac{4}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4=10=4\left(\frac{5}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5=15=5\left(\frac{6}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5+6=21=6\left(\frac{7}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7=28=7\left(\frac{8}{2}\right) \end{equation*}
\begin{equation*} 1+2+3+4+5+6+7+8=36=8\left(\frac{9}{2}\right) \end{equation*}

Aha! The pattern should be clear now!

Often making a conjecture requires calculating lots of examples and examining lots of different cases. It may take many rounds of trial and error to figure out the pattern. But that is part of what makes mathematics really fun! You will get lots of practice making conjectures in this course.