You seem to have two different questions:
- How do I interpret the word "impossible"
- 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:
- assuming
not P
at the beginning
- eventually finding a contradiction
- 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":
- To get a contradiction,
assume
that Joe was absent from school on May 5th
- If Joe was absent from school on May 5th, then Joe would not have taken a chemistry test on May 5th (
assumption
)
- Joe did not take a chemistry test on May 5th (
lines 1, 2 modus ponens
)
- Joe did take a chemistry test on May 5th (
assumption
)
- Joe both did, and did not, take a chemistry test on May 5th (
conjunction of lines 3 and 4)
- 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 that
P`
□ P
is it is necessary that
P``
~□ P
is it is not necessary that
P``
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:
- logic which uses possibility and necessity operators
♢
and □
- 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.