The world of predicate logic interests me, especially how it provides a foundation for understanding the logic behind many mathematical proofs. It is interesting to know how the negation, contrapositive and inverse are defined with respect to some implication ( and respectively). What got me thinking about predicate logic again was when I asked myself, “What is a contradiction?”
My big Collins Dictionary and Thesaurus defines ‘contradict’ as “to declare the opposite of (a statement) to be true” (verbatim). But, this leaves some room for debate as the meaning of the word “opposite” is not logically clear. Is the negation true? Is the inverse true? My reasoning says that a contradiction of the above implication is defined as . In a less formal way (and also less strongly), .
Let me briefly pause here for the sake of those unfamiliar with the symbols I have already used. denotes ‘not’, denotes ‘implies’, denotes ‘and’, and A and B are symbols which represent a statement, such as “dogs are black” or “black animals are dogs”. A and B are either true or false, there being no in-between. So, for example, if I can find one dog that is white the the statement “dogs are black” is said to be false, while from that information we cannot tell if the statement “black animals are dogs” is true or not. Similarly, the statement “all numbers greater than or equal to 0 are positive” is false, since the statement is not necessarily true, 0 being neither positive nor negative. I digress. The following truth table shows how implications (propositions) can be true or false (i.e. correct or incorrect) based on whether the hypothesis (A) or consequent (B) are true or false.
The original question I posed was, “What is a contradiction?” To answer this, let us look at one of the most common methods of proving a proposition, proof by contradiction. The method of proof by contradiction is to assume that A is true, then assume that ¬B is true. If I arrive at a conclusion that is false (i.e. absurd or incorrect), then I have proved that is necessarily true. I.e. if
then this is clearly an absurdity and our original assumption that ¬B is true is incorrect, so ¬B is false and B is true:
The above table is logically correct. Using Table 1, we can see that being false when A and B are both true implies that is true, concluding the proof.
‘A’ will usually be true because a proposition that has a false hypothesis is not useful. As you can see from Table 1, a false hypothesis implying anything will be a true (correct) implication (“If pigs could fly…” – if you are confused about this, see this page). Thus, we are only concerned with the cases when A is true.
On the other hand, if I can prove that is true (correct) when A and ¬B are (assumed to be) true, then I have proved that is false (incorrect). This disproves . See the third line of T’s and F’s in Table 1.
For example, let A be the statement and B be the statement . If I can prove that then I have proved that the following implication is incorrect: .
One can also disprove the truth of an implication or statement by citing a single instance to the contrary. In the third paragraph, I did that with the white dog and with the numeral 0. With our last example, I could let to see that is clearly false.
In the first paragraph, I mentioned that the negation of A implies B is A and not B. This can be verified by drawing a truth table. The negation of A implies B needs to be false when A is false, so that is why it is different to A implies not B (what I have used as the definition of a contradictory proposition).