A theorem is a statement that can be shown to be true. A theorem is demonstrated to be true with a proof.
A direct proof of a conditional statement is constructed when the first step is the assumption is true and subsequent steps are constructed using rules of inference, with the final step showing that must also be true.
Propositions of the form "If , then " are called implications.
Its often rephrased as
In order to prove :
Theorem:
Scratchwork: We can factor to get .For between 0 and 2, all the terms on the right side are nonnegative. We can organize our observations into a formal proof.
Proof: Assume . Then, , , and are all nonnegative. Therefore, the product of these terms is also nonnegative. Adding 1 to this product gives a positive number, so:
Multiplying out on the left side proves that
as claimed.
Note: Proofs typically begin with the word "Proof" and end with some sort of delimiter like , , or "QED".
Theorem: For all integers , , and , if and , then .
Scratch: We have to explain the meaning of and , and why this gives us the conclusion . Another way of saying is to say for some integer (in other words, is a multiple of . We are going for the fact that for some integer (because we want to be a multiple of ).
Proof:
Let , , and be integers. Assume that and .
(Our assumption)
In other words, is a multiple of and is a multiple of .
(Division is the inverse of multiplication. is defined to be the unique solution to the equation )
So there are integers and such that and .
(Follows from line 2)
Combining these(through substitution) we get that .
(Just some straightforward algebra here)
But is an integer, so this says that is a multiple of .
(Integers under multiplication are a closed operation, so an integer times an integer is always an integer )
Therefore .
(Since is a multiple of , is divisible by ).
An implication is logically equivalent to its contrapositive IMPLIES .
Theorem: .
Scratchwork: A number is irrational when there is no quotient of integers to which it is equal. We must show that if r is not a ratio of integers, then is also not a ratio of integers. We can eliminate both not's and simplify the proof by using the contrapositive instead.
Proof: We prove the contrapositive: if is rational, then is rational. Assume that is rational. Then there exists integers and such that:
Squaring both sides gives:
Since and are integers, r is also rational.
Theorem: For all integers, if is even, then is even
Proof:
We prove the contrapositive: for all integers , if is odd, then is odd.
(Our converse statement)
Let be an arbitrary integer.
(Fix to an arbitrary value in the domain of all integers)
Suppose that is not even, and thus odd.
(Follows from line 1)
Then for some integer .
(General form of an odd number)
Now .
(algebra)
Since is an integer, we see that is odd and therefore not even.
( is an integer we can set to . , which is also in the general form of an odd number, thus proving the contrapositive).
Theorem: For all integers and , if is odd, then is odd or is odd.
Scratch:
The statement is in the form of .
The contrapositive of our statement is
Using DeMorgans law for NOT OR we get
Our contrapositive statement is then: "If and are even, then is even.
Proof:
We prove the contrapositive: for all integers and , if and are even, then is even.
(Our converse statement)
Let and be two arbitrary even integers
(Fix and to two arbitrary even values of our domain)
and for some integers and .
(Definition of an even number)
Now
(Substituting in our representations for and )
Since is an integer, we see that is even.
( is an integer since the set of integers is closed under addition. We see that now also takes on the general form of an even number, completing the proof. )
Theorem: For every prime number , if , then is odd.
Proof:
We prove the contrapositive: for every prime number , if is even then .
(Our converse statement)
Let be an arbitrary prime number in our domain and assume it is not odd.
is divisible by .
(Definition of an even number)
Since is prime, it must have only two divisors. We know that is a divisor, so must be divisible by and .
(Definition of prime number)
Therefore, , completing the proof.
Theorem: Suppose , , and are real numbers . If then .
Proof:
Theorem: If where and are positive integers, then or .
Proof:
We prove the contrapositive: suppose and .
We can multiply these inequalities together (using the fact that if and then ) to obtain . This shows that , which contradicts the statement .
Because the negation of the conclusion of the conditional statement implies that the hypothesis is false, the original conditional statement is true. Our proof by contraposition succeeded; we have proved that if , where and are positive integers, then or .
Many theorems assert that two statements are logically equivalent; that is one holds if and only if (iff) the other does.
That is, to prove a statement of the form , we show that and are both true.
The statement is equivalent to the two statements and . You can prove "iff" by proving two implications.
The standard deviation of a sequence of values is defined to be:
where is the average/mean of the values.
Theorem: The standard deviation of a sequence of values is zero iff all the values are equal to the mean.
For example, the standard deviation of class scores is 0 iff everyone scored exactly the class average.
Proof: We construct a chain of "iff" implications, starting with the statement that the standard deviation is zero.
Now since zero is the only number whose root is 0, the above equation holds iff
Squares of real numbers are always nonnegative, so every term on the left hand side is nonnegative. This means that the above equation holds iff
Every term on the left-hand side is zero.
But a term is zero iff , so the preceding statement is true iff every equals the mean.
Otherwise known as proof by exhaustion.
Theorem: If an integer is a perfect cube, then it must be either a multiple of 9, 1 more than a multiple of 9, or 1 less than a multiple of 9.
Proof: The proof is by case analysis. Each perfect cube is the cube of some integer n, where n is either a multiple of 3, 1 more than a multiple of 3, or 1 less than a multiple of 3. So these three cases are exhaustive:
Another type of indirect proof. You show that if a proposition were false, then some false fact would be true. Since a false fact by definition can't be true, then the proposition must be true.
Theorem: is irrational.
Proof: We use proof by contradiciton. Suppose that the claim is false and
is rational. We can write as a fraction in lowest terms.
Squaring both sides gives us so 2d^2 = n^2. This implies that n is a multiple of 2. Therefore must be a multiple of 4. But since , we know is a multiple of 4 and so is a multiple of 2. That implies d is a multiple of 2.
So, the numerator and the denominator have 2 as a common factor, which contradicts that fact that is in lowest terms. Thus, must be irrational.
Theorem: There are infinitely many primes.
Proof:
We use proof by contradiction. Suppose the theorem is false, that there are actualy a finite number of primes. Then there must be a last, largest prime .
Consider the number
is certainly larger than and not divisible by any number less than or equal to , since every number less than or equal to divides . Thus, the prime factorization of contains prime numbers (possibly just itself) all greater than . So is not the largest prime, a contradiction. Therefore there are infinitely many primes.
Theorem: There are no integers and such that .
Proof:
Theorem: If more than pigeons fly into pigeon holes, then at least one pigeon hole will contain at least two pigeons.
Proof:
A vacuous proof of the conditional statement is a proof showing that is false. Remember that is true if is false.
Show that is true, where is "If , then " and the domain consists of all integers.
Note that is "If , then ". We can show using a vacuous proof. The hypothesis is false. This tells us that is automatically true.
Prove that if is an integer with which is a perfect square, then is also a perfect cube.
Note that there are no perfect squares with , because and . Hence, the statement that n is an integer with which is a perfect square is false for all integers . Consequently, the statement to be proved is true for all integers .
A trivial proof of the conditional statement is a proof showing that is true. Remember that is true if is true.
Let be "If and are positive integers with , then ", where the domain consists of all nonnegative integers. Show that is true.
The proposition is “If , then .” Because , the conclusion
of the conditional statement “If , then ” is true. Hence, this conditional statement, which is , is true. This is an example of a trivial proof. Note that the hypothesis, which is the statement “,” was not needed in this proof.
Take on the form where is a predicate.
Sometimes an existence proof of can be given by finding a witness, an element of that makes true. This type of existence proof is constructive.
A nonconstructive existence proof is one that proves in some other way. One common method of giving a nonconstructive existence proof is to use proof by contradiction and show that the negation of the existential quantification implies a contradiction.
Show that there is a positive integer that can be written as
the sum of cubes of positive integers in two different ways.
Using a computer, we find that .
There exist irrational , such that is rational.
(we know is irrational from a previous proof) Consider . If it is rational, then . On the other hand, if it is not rational, then we can let and so that .
This proof is conconstructive because we have not found an explicit pair of numbers and such that is rational. Rather, we have shown either
, , or , have the desired property but we don't know which of the two pairs work.
Proofs for theorems that assert the existence of a unique element with a particular property. We need to show
Showing that there is a unique element such that is the same as proving the statement
Show that if and are real numbers and , then there is a unique real number such that
Note that the real number is a solution of because . A real number exists for which . This is the existence part of the proof.
Suppose is a real number such that . Then , where . Subtracting from both sides, we find that .Dividing both sides by , which is nonzero, we see that . This establishes the uniquess part of the proof.