Proof:
Let $a, b \in \mathbb{Z}$ such that $a$ and $b$ are odd.Then by definition of odd $a = 2m + 1$ for $m \in \mathbb{Z}$ and $b = 2n + 1$ for $n \in \mathbb{Z}$.
So \begin{align*} ab &= (2m+1)(2n+1)\\ &= 4mn + 2m + 2n +1\\ &= 2(2mn + m + n) + 1 \end{align*} and since $m,n \in \mathbb{Z}$ it holds that $(2mn + m + n) \in \mathbb{Z},$ so $ ab = 2k+1$ for $k \in \mathbb{Z}, k = 2mn + m + n$. Thus $ab$ is odd by definition of odd
Consider this claim:
Claim: For any real numbers p,q, if p,q are rational, then p+q is rational.
Notice that we have a universal claim consisting of an if/then statement. The standard "direct proof" outline is to introduce the variables, then assume the information in the hypothesis, and reason from there to the conclusion. For our claim, this would look like:
Proof: Let p,q be real numbers.
Suppose p,q are rational.
....
So p+q is rational.
Notice that we've written out our goal for the end of the proof. It's important to write this down, so that you remember where you are headed when you're writing the middle of the proof. Write your goal where you can't mistake it for a fact that is known at the start of the proof. For example, write it at the bottom of your answer area. Some people write it to the side or on scratch paper.
You've probably watched instructors write proofs entirely in forwards order. This is because they already know how to do the proof and they are keeping the end goal in their head. So it's not a good model for doing a proof as a beginner, or a harder proof even when you are experienced.
Now we need to fill in the middle part of the proof. Very soon, we will be proving claims about unfamiliar concepts. But we haven't introduced any yet. So let's pretend that we know a lot about integers but don't yet know much about rational numbers. That's why we're trying to prove this very basic "closure" fact about the rationals.
To fill in the middle of this proof, we need a definition of "rational." Here's our textbook definition of "rational":
Definition: A real number x is rational if and only if it can be written as \(x=\frac{n}{m}\) where m and n are integers and m is not zero.
Let's use this definition to rewrite the two statements involving "rational" in terms of basic arithmetic.
Proof: Let p,q be real numbers.
Suppose p,q are rational.
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
...
So \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
So p+q is rational.
We used the definition of rational in three places. The first time, it happened that we could use the original variable names from the definition (n and m). However, we can't re-use these variable names when we do the other two substitutions. For example, if we wrote the following, we would be forcing p and q to be equal. That can't be right, because our claim was about any pair of rational numbers p and q.
\(p = \frac{n}{m}\), where n,m are integers, m non-zero.
\(q = \frac{n}{m}\), where n,m are integers, m non-zero.
Let's try to finish filling in the proof. Notice that our goal at the end of the gap involves finding a value for p+q. So let's try adding p and q, and see what we get.
...
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
Then \( p+q = \frac{n}{m} + \frac{j}{k} = \frac{nk+jm}{mk} \)
...
So if we set \(s=nk+jm\) and \(t = mk\), then \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
...
Now we clean up the details. There's a bit of missing reasoning in the middle, because we need to justify why s and t are integers, and t is non-zero. To do this, we'll use closure properties of the integers: adding two integers produces an integer, multiplying two non-zero integers produces a non-zero integer. Here's our final proof:
Proof: Let p,q be real numbers.
Suppose p,q are rational.
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
Then \( p+q = \frac{n}{m} + \frac{j}{k} = \frac{nk+jm}{mk} \)
\(nk + jm\) is an integer because n,k,j,m are integers
mk is an integer because m,k are integers.
mk is not zero because m,k are non-zero
So if we set \(s=nk+jm\) and \(t = mk\), then \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
So p+q is rational.
Recall that an if/then statement \(\forall x, p(x) \rightarrow q(x) \) is equivalent to its contrapositive \(\forall x, \neg q(x) \rightarrow \neg p(x)\). If we prove either one, we have proved the other. Sometimes the contrapositive of a claim is easier to prove than the original.
With some practice, you'll develop intuitions about when the contrapositive might be easier to prove. I usually compare p(x) to \(\neg q(x)\) and see which looks like a better starting point. For example, \(\neg q(x)\) might have an AND of two facts rather than an OR, or it might have separate facts about each variable where p(x) has a fact in which two variables are combined.
Consider this claim:
Claim: For any real number x, if \(x^2 - 2x - 15 \ge 0\), then \(x \ge 2\) or \(x \le -1\).
To write a proof by contradition, we tell the reader what we are doing, write out the contrapositive, and outline a direct proof of the contrapositive. So, for our claim, we have:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
....
So then \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Always tell the reader when you're using an outline other than direct proof. In this class, write out the contrapositive explicitly because it forces you to take a moment to make sure you have constructed it correctly.
Since it's not obvious how to move forwards from the given information, let's work backwards on scratch paper:
Scratch paper: Try factoring \(x^2 - 2x - 15\). It's equal to \((x-5)(x+3)\). So we need to show that \((x-5)(x+3) < 0\). That means that one of the two factors must be negative and the other positive. The bigger one (x+3) must be positive. So we need to show that \(x-5 < 0 \) and \(x+3 > 0\).
Let's rewrite this into forwards order and put it into our draft proof:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
....
So \(x-5 < 0 \) and \(x+3 > 0\).
So \((x+3)(x-5) < 0\).
Multiplying out the lefthand side, gives us \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Now we have a small algebra gap to fill in, and our final proof looks like this:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
Since \(x < 2\), \( x-5 < 2-5 = -3 < 0\).
Since \(x > -1\), \(x+3 > -1 + 3 = 2 > 0\).
So \(x-5 < 0 \) and \(x+3 > 0\).
So \((x+3)(x-5) < 0\).
Multiplying out the lefthand side, gives us \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Notice that filling this final gap required losing information. We know that \(x-5\) is less than -3 but our conclusion only requires that it's less than 0. And similarly for the other factor. Weakening information like this is a valid mathematical step, but it's one that we would never consider if we hadn't worked backwards from the desired conclusion.
Proof:
Let $x$ be a real number.$x^2-2x+1 = (x-1)^2$
Since $x-1$ is a real number and the square of a real number is non-negative there can not exist a real number x, x^2 - 2x +1 < 0$.
Proof:
Consider $x=-1,(x+1)^2 = 0$. So there exists a real number $x$ such that $(x+1)^2 \ngtr 0$ so the claim is invalid.