0

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?

7
  • At least in a one world environment it is enough for a statement to be false in order to be impossible. In other words, in a one world environment: impossible=false.
    – user14511
    May 23, 2020 at 12:37
  • "Impossible" means not holding in any model of a theory, it is a semantic notion. "Contradictory" means implying something and its negation, it is a syntactic notion. So no, they are not the same concept. However, Goedel's completeness theorem states that for a large class of theories absence of contradictions is equivalent to having a model.
    – Conifold
    May 23, 2020 at 13:20
  • Contradiction has more than one context. In Mathematical logic a contradiction does not necessarily mean impossible. It just means a proof that has a positive variable with its negation somewhere along a sub proof within the proof. You are likely trying to use the term contradiction outside of the math class in reality & see it's different in reality. In reality we can use the context a contradiction is something impossible. It is impossible for me to be age 28 and 30 simultaneously. So in ordinary language a contradiction is a RELATIONSHIP between 2 propositions.
    – Logikal
    May 23, 2020 at 14:46
  • In language a contradiction directly states there is a relationship or pattern between two different propositions where exactly one of them MUST BE TRUE & the other proposition NECESSARILY MUST BE FALSE. There is no middle ground or other alternatives under a contradiction. To be specific you cannot call two propositions where they are both false contradictory. You cannot call two propositions where they are both true contradictory. Contradiction must have the result one is true while the other is false & if one is false the other is true. In this way one of the propositions is impossible.
    – Logikal
    May 23, 2020 at 14:50
  • 1
    See Modal Logic: impossible means "always false". Thus, a contradictory formula "describes" an impossible situation, because there is no situation such that the contradiction is true. May 23, 2020 at 15:42

2 Answers 2

3
  • 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).

0
-1

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .