Contradiction vs Impossiblity

Question

When we do proof by contradiction we think in the following way:

Suppose we know that Q is true. We assume that not P is true and through implications we conclude not Q is true. Now how we proceed to conclude that P is true?

It is impossible that both Q and (not Q) are true. Therefore because we know Q is true, P must be true. My problem is how to interpret the word "impossible". Can we say that something impossible is something that is always false? Contradiction is a statement that is always false. So can we say that an impossibility is a contradiction? Does impossibility makes sense in logic/mathematics?

Answer 1

• Some propositions are contradictory absolutely , some are contradictory under a given assumption.

• (Q & not-Q) is absolutely contradictory.

• Now , if Q is true and if P implies not-Q , P is contradictory under the assumption that Q is true. It means that, under the assumption " Q is true" , P leads to a contradiction. That does not mean that P is contradictory by itself and absolutely. However, the simple fact that P leads to a contradiction is sufficient to rule out P , in the context of our assumption.

• We can recover " absolute contradiction " at the level of the whole proof. What would be absolutely contradictory would be to say :

(Q is true and P implies not-Q ), but nevertheless P is true.

Note : not all impossibility amounts to a contradiction; there are also physical impossibilities ( i.e. what violates laws of nature) (for example, it is impossible that my grand father be 230 years old; but it is not logically impossible , that is, contradictory).

Answer 2

You seem to have two different questions:

1. How do I interpret the word "impossible"
2. Suppose Q. We assume not P, and through implications, we conclude not Q. Now, how do we we proceed to conclude that P is true?

In mathematics, a proof by contradiction almost never uses any of the following terminology:

• "possible"
• "impossible" ( put this in bold, since it's the word you asked about)
• "necessary"
• "not necessary"

Use of the word "impossible" is completely unnecessary for writing a proof by contradiction. The word "impossible" is usually only used in:

• modal logic
• probability
• statistics

---

In Proof by Contradiction we prove P by:

1. assuming not P at the beginning
2. eventually finding a contradiction
3. finish by concluding P.

You said that you really did not understand why we are allowed to conclude P at the end.

Let us look at an example of proof by contradiction:

The following is a proof that "Joe was not absent from school on May 5th":

1. To get a contradiction, assume that Joe was absent from school on May 5th
2. If Joe was absent from school on May 5th, then Joe would not have taken a chemistry test on May 5th (assumption)
3. Joe did not take a chemistry test on May 5th (lines 1, 2 modus ponens)
4. Joe did take a chemistry test on May 5th (assumption)
5. Joe both did, and did not, take a chemistry test on May 5th (conjunction of lines 3 and 4)
6. Joe was not absent from school on May 5th (line 5 is a contradiction dependent on line 1. conclude negation of line 1)

I hope that after reading the example, you see why it is logically valid to conclude that Joe was not absent from school on May 5th.

---

Using rigorous logic, I will prove that that proof by contradiction is valid.

We shall prove that for any true/false statements P and Q that:
(Q and ([not P] implies [not Q])) implies P

PROOF:
1. Q and ([not P] implies [not Q])......... assumption
2. Q......... from line 1 and (α and β) → α
3. [not P] implies [not Q]......... from line 1 and (α and β) → β
4. Q implies P ..... contrapositive of line 3.
5. P ..... from line 2, line 4, and modus ponens

quod erat demonstrandum

---

Your other question was something like, "how do I interpret the word impossible"?

The word "impossible" smacks of modal logic.

• ♢P is short-hand notation for "it is possible that P"
• ~♢ P is it is not possible thatP`
• □ P is it is necessary thatP``
• ~□ P is it is not necessary thatP``

Note the following:

• ~□ P if and only if ♢(not P)
• Example: "it is not necessary that you wear a blue shirt if and only if it is possible that you not wear a blue shirt"
• ~♢ P if and only if □(not P)
• Example: It is not possible that I win the lottery if and only if it is necessary that I not win the lottery.

Note that "~♢" takes less time to write than "it is not possible." That is why diamond and box are "short-hand" notation. When mathematicians are want to use the same sentence fragment over and over again (or the same formula over and over again), the mathematicians will create a short-name for it. It gets tiresome to write the long-name over and over again. ♢ and □ are nice and short.

The following is one mathematician's definition what it means for a function to be "bounded-above."

For any real-valued function f and for any real number β, f is bounded-above by β if and only if there exists a real number x such that for all real x′ > x, f(x′) < β.

For example, if you look at a picture of the sin function, you will see that sin is always strictly below the horizontal line y = 1.5

If you are using "for all" and "there exists" a lot, then ♢ and □ can save some time and effort.

• ♢ is related to "there exists"
• □ is related to "for all"

I am going to start making big leaps, where I skip a lot of little steps in-between If you do not understand why the following is true, that is fine. I just want the take-away for the following to be that the symbols ♢ and □ can save some time and effort even if you don't really see how they work. A child knows that driving 50 kilometres in a car is faster that walking, even if the child doesn't know how to shift gears, or use the car's pedals.

The definition of what it means for a function to be "bounded-above" can shortened:

For any real-valued function f and for any real number β, f is bounded-above by β if and only if ♢ f(x) < β.

The following are two examples of the equivalent statements. One statement uses ♢ and □ and the other does not:

• ♢ □ ♢ f(x) < β
• There exists x_1 such that for all x_2 > x_1 there exists x_3 > x_2 such that f(x_3) < β

The following are equivalent statements.

• □ ♢ the stop light is green
• for every time t there exists a time t′ such that the stop light is green at time t′
• there will never be a time after which the stoplight never turns green again.
• no matter how far in the future you go, there will be a time even further in the future than that when the stoplight will turn green again.

Note that "□ ♢ the stop light is green" is very short.
Many mathematicians do not want to write long-winded phrases over and over again.

You can think of there being two languages:

• German and Spanish
• mandarin and English.

There are two languages:

1. logic which uses possibility and necessity operators ♢ and □
2. logic which does NOT use possibility and necessity operators ♢ and □

Modal logic using the symbols ♢ and □ is much less "verbose" that saying the same things using the phrases "There exists" or saying "for all"

By the way, ∃ is short-hand notation for "there exists."
It would be silly if ∃ and ♢ were the same.
Therefore, ♢ usually stands for ∃ plus some other stuff.