Hello can someone give me examples of direct / indirect proofs, existence proofs, i am not understanding this and it is confusing me. I have a test coming up thursday and it'll will help a lot if i could even understand it little bit. Thank you!
Hello can someone give me examples of direct / indirect proofs, existence proofs, i am not understanding this and it is confusing me. I have a test coming up thursday and it'll will help a lot if i could even understand it little bit. Thank you!
Proposition: An even number times an even number is an even number.
Direct Proof: Assume we have 2 even integers a,b. Since any even number can be written in the form 2p where p is an integer.
Let a = 2k, b = 2m for some integers k and m.
a*b = 4km = 2*(2km). Since 2km is a natural number. a*b is even
Indirect Proof: I will prove the contrapositive (indirect). (if A implies B) then its contraposition is not B imples not A. Both of these (A imples B) and (not B implies not A) are logically equivalent, so proving one is the same as proving the other.
So Assume a*b is odd for some integers a,b. Then atleast one, either a or b, must be odd. For if neither are odd then a = 2k, b=2m for integers k,m
and a*b = 2*(2km) which is not odd. Thus either a or b is odd.
Existence proof to show that for every non zero integer a, i could find another integer b (or there exists an integer b), such that a*b is an even number
Now since a is an integer, it is either even or odd. If it is even then a = 2k for some integer k, then take b = 2m for any integer m. a*b = 2*(2km) is even.
Now if a is odd, then a = 2k + 1 for some integer k. Take b = 2m, then a*b = 4km + 2m = 2*(2km+m). Since 2km+m is an integer. 2*(2km+m) is even.
Thus every non zero integer has an integer b such that a*b is an even number.
Modus Ponens means if P implies Q, and P is stated to be true then Q must also be true.
In the above proofs, we assume that P is true (in case of the direct proofs) and proceed from there to prove Q is also true.
Yes, you are also correct about the contrapositive being modus tolleens.
A direct proof is to start with a true statement and to go through a series of logical steps to get to the statement you are trying to prove. If all steps are valid, then the proof is valid.
There are two versions of indirect proof.
The first is to note that if $\displaystyle \displaystyle \begin{align*} P \implies Q \end{align*}$, then an equivalent statement is $\displaystyle \displaystyle \begin{align*} \not Q \implies \not P \end{align*}$. It's like saying "If it rains I will carry an umbrella" is equivalent to saying "If I am not carrying an umbrella, it is not raining". It is often easier to prove the contrapositive (equivalent version) of the statement. As an example, if we want to prove that if $\displaystyle \displaystyle \begin{align*} a^2 \end{align*}$ is even, then $\displaystyle \displaystyle \begin{align*} a \end{align*}$ is even. To prove this directly, we would need to be exhaustive and show what happens when a is odd, when a is even, and when a is 0.
The contrapositive of this statement is if $\displaystyle \displaystyle \begin{align*} a \end{align*}$ is odd, then $\displaystyle \displaystyle \begin{align*} a^2 \end{align*}$ is odd. This only requires seeing what happens when you square an odd number. Much easier.
The second form of indirect proof is called Reducio Ad Absurdium (Reduction to the Absurd). It makes use of the idea that a proof is considered valid if you start from something true and end up at another statement with valid steps. However, if you go through a series of valid steps and end up at a contradiction or absurdity, like 1 = 0, then it tells us that the original statement was FALSE. So a way to prove statements is to start with the OPPOSITE of what you want to prove and get to a contradiction, thereby showing that the opposite of what you want to prove is false, and thus what you want to prove is true.