“P if and only if Q” works by breaking the statement into two different statements “if P then Q” and “if Q then P”. We prove both of these statements as if they were the statement before.
Proposition: Let be an integer, is not evenly divisible by 3 if and only if evenly divisible by 3.
We start by dividing this into two statements. This gives us our first statement: “if is evenly divisible by 3 then is not evenly divisible by 3.”
Proof: If is not evenly divisible by 3 then is it will have a remainder of 1 or 2 when divided by 3. This means that if the remainder is 1 then is divisible by 3 since is now a multiple of 3. If the remainder is 2 then is now a multiple of 3 so thus is divisible by 3. Thus we have that if is not evenly divisible by 3 then is not evenly divisible by 3.
Now for the second statement: “if is evenly divisible by 3 then is not evenly divisible by 3.”
Proof: if is divisible by 3 then this means either is divisible by 3 or , not both since . Now if is divisible by 3 then cannot be divided evenly by 3 since will give us a remainder of 1. This means that is evenly divisible by 3 then is not evenly divisible by 3.
Now that we have proved both parts of the original statement. This means that our original statement is true.
Finally, if a theorem is a fact about a specific definition or theorem, we simply have to derive that fact from relevant definitions and theorems. Here is a quick example.
Proposition: 2 is the only even prime number.
Proof: even numbers are defined as which means that for all then is a composite number which means 2 is the only even prime number.
- What is a proof?
- Direct Proof Part I
- Direct Proof Part II
- Proof by Contradiction
- Proof by Induction
- Proof by Induction example
- Proof by Contrapositive
- Proof of Existence
- Proof of Uniqueness
Filed under : Mathematics