The Implication Connector And Proofs
If you are not familiar with this logical operator yet, then I hope I can introduce you to it today! I am currently learning about the implication operator in logic (=>) and it is a very curious operator. First off I plan on trying to dispel any ambiguous rhetoric along the way and I hope it doesn’t become too tedious in doing so.
We are all familiar with logical operators in natural language. For instance if you said “John and Mary are white” then you could write it with the logical operator ‘^’ (and) like so: ‘John ^ Mary are white.’ The implication statement in language is used like this: ‘If John is white then Mary is also white.’ This can be written also as “John is white => Mary is white.”
Evaluating the truth values of how many possible outcomes such a statement can have is the next focal point. I want to start with the statement: ‘If it is not raining then we will go hiking.’ Let us pretend we are talking with a friend and this plan is stated and agreed upon. So we can then evaluate all the possible outcomes of this plan that the two hypothetical friends have established like so:
- If it is not raining then we will go hiking.
- If it is not raining then we will not go hiking.
- If it is raining then we will go hiking.
- If it is raining then we will not go hiking.
Now to pose the question: what is the truth value of these outcomes? Well we know that if it is not raining then they agreed upon going hiking, so if they do indeed go then we can say that the statement is true. If it is not raining and they do not hike then someone either lied or broke the agreement, and the statement becomes false. What if it is raining outside? Well the two friends never discussed what would happen in the case that it was raining. So now we are left with two scenarios that seem to pose an issue. How can we determine whether they are true or false? We do know that the decision of going hiking is only dependent on the fact that it is not raining, and has no relation to a day in which it is raining. It seems sensible to conclude that if it is raining then they will not go hiking. This leads us to conclude that this statement is true. What if they decide to go hiking even though it is raining? That is still a possible outcome, and if they did indeed choose to do that then we could have to conclude that if it was raining and they did not go hiking would be false, which is the opposite of what we just considered to be true.
This appears to get very confusing because of how we naturally evaluate how to determine the truth value of all the possible conditions. We start to see a contradiction crop up regarding the last two points: ‘if it is raining then we will go hiking, and if it is raining then we will not go hiking.’ If one is true then the other is false and vice versa. So it appears that we can only know the truth value of the first two options in regards to what they agreed upon to begin with which was: ‘if it is not raining then we will go hiking, and if it is not raining then we will not go hiking.’
I'd like to remind you here of what I said a bit earlier. The idea of hiking is only related to the idea of them going if it is not raining but it contains no information as to what they might decide if it is raining. Since there is no connection between the two we no longer are concerned with speculation upon what it is that they might do in the case that it is raining. We can then say, if they choose to go hiking or not in the case that it is raining, either situation will be considered true. This fact seemed very strange to when I first learned about it. But I hopefully clarified why this is by hopefully making it clear that the idea of going hiking is not dependent upon the weather in the case that is it raining because there was never any information relating these two ideas to start with. Since it is now raining we now accept that either choice of going hiking or not is valid (true) because the previous agreement regarding the rain is of no consequence.
If we were to set P = if it is not raining, and Q = we will go hiking, we can then make a small table that will show the truth values of the implication statement between the two friends.
| P | Q | P=>Q |
| T | T | T |
| F | T | T |
| T | F | F |
| F | F | T |
Now that we have outlined how the implication operator works I now want to turn to proofs. First I’d like to start with direct proofs. The first example I’d like to demonstrate that uses this implication operator is the statement: Let x and y be integers. Prove that if x and y are even, then x + y is even.
With this information we can start by saying that P = x ^ y is even, and that Q = x + y is even. We have the following setup: P=>Q. We must first assume that x and y are even to start with, meaning we are assuming P to already be true. Now we know from the table above that if P is true then the only case in which P=>Q is then true is when Q is also true. We must find a way to show that x + y is even by using the information given to us that P is true.
Since P is true and P = x ^ y are even we then need to know what that means exactly. We know that 2 times any integer (k) will give us an even number. We then can say by definition that x = 2k and that y = 2k. K being any integer.
Now that we have the definition of what it means to be even and we have set that equal to both x and y we can use that to investigate x + y and whether or not it is even.
Since we know that x = 2k and y = 2k then we can also infer that x + y = 2k + 2k.
From this point we can then say that 2k + 2k = 2(k+k).
This shows that 2 times k+k (which is just some integer) will always give us an even number.
This is the direct proof to demonstrate how in mathematics we can use a implication statement to directly prove Q by definition P.
At this point I want to now turn to an idea called proof by contradiction. I will start this section off by doing a little thought experiment to try and make this as clear as I can (because I find it very interesting to explain. I am looking through my wallet and I say “If my license says my name is Taylor then my name is Taylor”. I put my wallet away and a few minutes later I reopen it and say, “my license says my name is Taylor and my name is not Taylor." So our P = “If my license says my name is Taylor then my name is Taylor” while our ~P = “my license says my name is Taylor and my name is not Taylor.” Our first assumption is that the sensible version of me that claimed P, never lies and has adequate evidence that his license is accurate, and his memory is correct in recalling my name. Since this is the case then I am then contradicting myself by saying that I acknowledge that my license says my name is Taylor but my name is not Taylor. Since my license says my name is Taylor then it must follow that my name is Taylor, and because of this lying or contradicting we then can say that the entire claim of ~P is definitely not true so it follows that P is then proven to be true.
This seems really odd in regards to being able to prove something as true especially since we assume that P is true to begin with. Doesn’t it seem to be rather silly to ask oneself that question? Like in the experiment above I started with, if my license says my name is Taylor then my name is Taylor. So if I assume that the state knows my identity, and I know my own name, then what is there to prove? Well let’s say I just wanted to be sure that the things I viewed as concrete truths about my name were worth putting some faith into. So I then can consider the opposite, and by doing so I am immediately met with a nonsensical representation ~P. So the point of proving the validity of something by contradiction is to explore the idea of looking at the opposite of what we begun with (and assumed to be true) and see how it relates to what it is we want to prove. In this case I suppose it is possible that I did forget my name and my license is incorrect, but that is normally considered nonsense, or being delusional. Plus the next example should help demonstrate a more pure mathematical representation of this proving method.
P = if n is a natural number then n/n+1 > n/n+2
A natural number is a positive whole integer and sometimes zero, and they ascend an increment of 1. We can write this as an ascending sequence: 1, 2, 3, …, n.
And we can also observe the hierarchy of ascending integers:
1 < 2 < 3 < … < n.
So we Assume ~P:
~P = n is a natural number and n/n+1 <= n/n+2
We also assume the definition of a natural numbers:
1, 2, 3, 4 ...
So our Q is the following:
n/n+1 <= n/n+2
= n(n+2) <= n(n+1)
= n+2 <= n+1
Our ~Q is then the reverse:
n+2 > n+1
This shows that since ~P is impossible that P must then be true. When we look at ~P we see that is stated both that n is a natural number and that n/n+1 < n/n+2. We found that for n/n+1 < n/n+2 = n+2 < n+1 and that only if we negated Q could we obtain a sensible definition. Because of this we have a contradiction in regards to ~P. So since the opposite of P is nonsense then we can be confident that the P that we assumed to always be true is.