# Rigorous proof of '${\{A \Rightarrow B}\} \iff {\{\neg B \Rightarrow \neg A}\}$' for a high school student

One method to prove the statement 'If A, then B' is to prove that 'If not B, then not A'. First time that I saw this method it was not (and still isn't) obvious. So I used a more obvious example to understand it: 'If temperature of water is $100\ ^{o}C$, then it is boiling' is as same as to say 'If water is not boiling, so its temperature is not $100\ ^{o}C$'; but there are two problems here:

1- the mentioned statements (about water) are equivalent under only ONE circumstance which is that the only reason for boiling water is $100\ ^{o}C$-temperature. So one needs to check this also in the proofs of maths (~bijection).

2- The water case is just an example from intuition, and I am not sure if I can extend professionally to mathematics, and I mean to any area of mathematics.

My questions are:

1- How can I (as someone who knows nothing about Logic and its complicated symbols and terminologies - like what a high school student thinks about Logic,) understand why the guaranteed equivalence between 'If A, then B' and 'If not B, then not A' holds always in every mathematical proof?

2- If the only way to guarantee the mentioned equivalence is to guarantee a bijective 'function' between A and B (is it?), how can I know that there is no other choice except for A/B if I choose B/A (especially when I can't see other choices since I don't see the bigger picture since I am in the process of learning not passed that level for much more advanced level and much bigger picture to be sure of existence of a bijective 'function')? In some cases it is very obvious [i.e. two choices conclusion: no/yes] but not always, and one needs to know a bigger picture.

Thank you very much for any clear but rigorous explanation.

• Do you understand how proof by contradiction works? – Doug Spoonwood Jun 27 '15 at 23:06

Make a truth table!

We consider 4 cases.

1) $A$ true, $B$ true. Then $A \implies B$ is true, and ~$B \implies$~$A$ is true.

2) $A$ true, $B$ false. Then $A \implies B$ is false, and ~$B \implies$~$A$ is false.

3) $A$ false, $B$ true. Then $A \implies B$ is true, and ~$B \implies$~$A$ is true.

4) $A$ false, $B$ false. Then $A \implies B$ is true, and ~$B \implies$~$A$ is true.

Notice how the implications have the same status for every combination. This shows you the two are logically equivalent.

• Thanks a lot. Because of understanding better, I would appreciate it if please give me examples from everyday life in each of the cases you've written. For example second part of the case 3: A false B true the $B\implies A$ true, means water boils at 100C $\implies$ black is same as red; which is not true. – L.G. Jun 28 '15 at 23:17
• It is amazing how I was upvoted when my "not" symbols were not appearing. This post was definitely wrong before, but now it is corrected. Moreover, it is of critical importance that you don't worry about these examples, because the natural logic that you do day to day is not at all the same as the logic you do when discussing material implications of classical logic. – Alfred Yerger Jun 29 '15 at 14:40
• If $A$ is false and $B$ is true, then $B \Rightarrow A$ is indeed false. As explained by Alfred, his not symbols were not appearing, he meant $\neg B \Rightarrow \neg A$. – Jonathan Hebert Jun 29 '15 at 14:45
• For an every day example of the truth values of implications, if I said: "If you cut my grass, I will give you fifteen dollars." - in what scenario could you call me a liar? – Jonathan Hebert Jun 29 '15 at 14:47
• @Alfred Yerger: (Now,) I understand your answer [A] then I upvote it [B]; (but yesterday) I didn't upvoted it since I haven't understood your answer; It's another example of my question ${\{A \Rightarrow B}\} \iff {\{\neg B \Rightarrow \neg A}\}$ ! Thank you for your answer. – L.G. Jun 30 '15 at 0:20

Your claim, "the mentioned statements are equivalent under only one circumstance that the only reason for boiling water is 100 degree Celsius temperature" is false. They are equivalent anyway. Suppose water boils when it is $100$ degrees OR [property $A$] is met.

We claim "If the water is $100$ degrees, then it is boiling." and "If the water is not boiling, then it is not $100$ degrees." are logically equivalent.

You counter with "but if the water is boiling, it could be because of [Property $A$]."

Then we have that "the water is boiling", so "If the water is $100$ degrees, then it is boiling" is a true statement, because the consequent is true. We have that "If the water is not boiling, then it is not $100$ degrees" is a true statement, because the antecedent is false. [Property $A$] doesn't even get a mention.

Including another reason that could lead to the boiling of water only gives us another truth value combination that could happen "in reality" where water is boiling and it is not 100 degrees, but this has absolutely nothing to do with the logical equivalence of the statements.

Without including [Property $A$] as a possible cause of water boiling, we could have still considered the truth values of the statements when water is boiling but is not $100$ degrees and we would have gotten the same result, it just wasn't a truth value that could happen in reality, but that's utterly irrelevant.

Example: Consider the statement: If it is raining, then it is cloud.

$Raining \implies Cloudy$

This does not mean that rain causes cloudiness, or that cloudiness causes rain. Neither is the case. It means only that it is not both raining and not cloudy.

$\neg [Raining \land \neg Cloudy]$

In mathematics then, if not in everyday usage, $A\implies B\equiv \neg[A\land \neg B]$.

Then $\neg B \implies \neg A\equiv \neg[\neg B\land \neg\neg A] \equiv \neg[ \neg B\land\ A] \equiv \neg[ A\land\neg B] \equiv A\implies B$

• +1 for a direct derivation of the equivalence from the definitions. – Alfred Yerger Jun 30 '15 at 6:14

In Logic, "If A, then B" is often written as $$A\implies B,$$ which can be read as"A implies B".

This relation $\implies$ is called "material implication" and is defined as a function of the truth values of A and B:

Whenever A is false, $A\implies B$ is defined to be true.

Whenever B is true, $A\implies B$ is defined to be true.

The only remaining possible case is when A is true but B is false. In this case $A\implies B$ is defined to be false.

It follows that $A\implies B$ is true if this final case does not hold. That is, if we do not have $A$ true and $B$ false at the same time. Thus if A is false whenever B is false (not B implies not A), then $A\implies B$ is true.

I must stress that although this makes sense intuitively (if you think about it the right way), it is strictly a matter of definition of the "material implication" in logic.

If you're interpreting "if...then..." intuitively when thinking about logic you're going to confuse yourself. $p \implies q$ (i.e. "$p$ implies $q$") has a very particular meaning in propositional logic, which is essentially that the same as $\neg(\neg p \land q)$ (i.e. "never not p and q"). To express this fact the type of implication we use in propositional logic is called "material" implication.

In plain language this means $p$ implies $q$ if and only if it's never possible to have $p$ true and $q$ false. The implication sign $\implies$ is just a shorthand way to write this.

Hence if the temperature of water being $100^\circ$ implies it will boil, then it's impossible for water to be $100^\circ$ and not boil.

In logic the meaning of connectives are given by truth tables.

$\begin{array}{cc|cccccc@{}cccc@{}c} p&q&p&\rightarrow&q&\leftrightarrow&\lnot&(&p&\land&\lnot&q&)\\\hline 1&1&1&1&1&\mathbf{1}&1&&1&0&0&1&\\ 1&0&1&0&0&\mathbf{1}&0&&1&1&1&0&\\ 0&1&0&1&1&\mathbf{1}&1&&0&0&0&1&\\ 0&0&0&1&0&\mathbf{1}&1&&0&0&1&0& \end{array}$

Each row in the truth table above specifies a single "possible world" where if a proposition is true then it's value in that row is $1$, and if it's false then it's value in that row is $0$.

As you can see in the truth table, every row where the "main connective" (which you can think of as the one surrounded by at most one set of brackets) of $p \implies q$ has value of $1$, the main connective of $\neg(\neg p \land q)$ (the outer '$\neg$' not symbol) also has the value of $1$, and likewise when the one expression resolves to a value of $0$ so does the other. This is expressed by the fact that the column containing the mutual implication symbol contains $1$ in every possible world (i.e. row).

Hopefully this is clear enough for you to follow along. It's easy to miscalculate what someone else will become confused over, so if this is unclear please ask for clarification!

• I got most of basic logic intuitively. I am not sure why you say doing so would "confuse someone". – Hasan Saad Jun 27 '15 at 23:40
• Due to the paradoxes of material implication, such as the principle of explosion, which lead many people to object that material implication doesn't capture the true spirit of implication (since human beings will not conclude from $\neg$(Fermat's Last Theorem) that the moon is made of cheese. If you stick strictly to the semantics of logical connectives, you're hemming in your expectations of what you should be able to state concisely within the propositional calculus. Further paradoxes are outlined at en.wikipedia.org/wiki/Paradoxes_of_material_implication – Dion Bridger Jun 27 '15 at 23:47
• You have a point there, but it still works for me for some reason. But yeah, you have a point. – Hasan Saad Jun 27 '15 at 23:50

Here is the question:

1- How can I (as someone who knows nothing about Logic and its complicated symbols and terminologies - like what a high school student thinks about Logic,) understand why the guaranteed equivalence between 'If A, then B' and 'If not B, then not A' holds always in every mathematical proof?

Others have provided a truth table. Here is a diagram showing the relationship between $$A$$ and $$B$$ when $$A$$ is a sufficient condition for $$B$$, that is, whenever we have $$A$$ we have $$B$$, that is, when $$A\Rightarrow B$$:

Note that $$A$$ is completely inside the circle $$B$$. The $$\neg B$$ part of the diagram is outside the $$B$$ circle. It would also be outside the $$A$$ part of the circle. That means that $$\neg B$$ is a sufficient condition for $$\neg A$$, or whenever we have $$\neg B$$ we also have $$\neg A$$, or $$\neg B \Rightarrow \neg A$$.

If we start with $$A$$ and $$B$$ as in the diagram we get this relationship:

$${\{A \Rightarrow B}\} \Rightarrow {\{\neg B \Rightarrow \neg A}\}$$

We can use the same diagram and look at it from the perspective of $$\neg A$$ and $$\neg B$$. We get the following relationship:

$${\{A \Rightarrow B}\} \Leftarrow {\{\neg B \Rightarrow \neg A}\}$$

Since we used the same diagram for both conclusions, we have both directions of the biconditional and we can conclude:

$${\{A \Rightarrow B}\} \iff {\{\neg B \Rightarrow \neg A}\}$$