Logic: Reductio Ad Absurdem Assumption

[mathewslauren]

When you are proving a valid argument using the assumption reductio ad absurdem, can you assume anything in the conclusion, and then put a not in front of it, or do you have to assume the whole conclusion with a not in front of it? For example:
1. p\supset q
2. p \lor q \therefore p and q

To prove this argument using reductio ad absurdem can you assume (not p) ,or maybe (not q), or do you have to assume (not p and q) with the not in front of the whole conjunct.

Note: That is example is not real and it may not actually be valid.

 

[solakis1]

When you are proving a valid argument using the assumption reductio ad absurdem, can you assume anything in the conclusion, and then put a not in front of it, or do you have to assume the whole conclusion with a not in front of it? For example:
1. p\supset q
2. p \lor q \therefore p and q

To prove this argument using reductio ad absurdem can you assume (not p) ,or maybe (not q), or do you have to assume (not p and q) with the not in front of the whole conjunct.

Note: That is example is not real and it may not actually be valid.

It depends on the problem.

For example in the following theorem :

0<ab => (0<a & 0<b)v(a<0 & b<0)

You can assume :

1) ~(0<a & 0<b)
...or...

2) ~(a<0 & b<0)
...or...

3) ~ [(0<a & 0<b)v(a<0 & b<0)]

 

[Evgeny.Makarov]

It depends on the problem.

For example in the following theorem :

0<ab => (0<a & 0<b)v(a<0 & b<0)

You can assume :

1) ~(0<a & 0<b)
...or...

2) ~(a<0 & b<0)
...or...

3) ~ [(0<a & 0<b)v(a<0 & b<0)]

No, a proof of $p$ using reductio ad absurdum proceeds by assuming $\neg p$ and deriving a contradiction. That is, one puts the negation in front of the whole statement that needs to be proved. In the case of
\[
0<ab\implies (0<a \land 0<b)\lor(a<0 \land b<0)
\]
we assume $0<ab$ and then prove the conclusion by reductio ad absurdum. To do this, we assume $\neg((0<a \land 0<b)\lor(a<0 \land b<0))$ and derive a contradiction using previously assumed $0<ab$. Assuming just $\neg(0<a\land 0<b)$, i.e., $a\le0\lor b\le0$, together with $0<ab$ does not lead to a contradiction.

Similarly, if you need to prove $p\land q$, you assume $\neg(p\land q)$, i.e., $\neg p\lor\neg q$, and derive $\bot$ (a contradiction). The statement $(\neg p\lor\neg q)\to\bot$ is equivalent to $(\neg p\to\bot)\land(\neg q\to\bot)$. Thus, you have to prove that assuming that $p$ is false leads to a contradiction and similarly for $q$. If you only prove $\neg p\to\bot$, then you leave the possibility that $p$ is true, but $q$ is false; therefore, $p\land q$ is not proved.

 

[Prove It]

When dealing with logic, there are some basic assumptions:

1. A statement can only ever be true or false. There is no in between.

2. If a statement is true, then its converse is false. And vice versa.

So a way you can prove a statement is true is to show that its converse is false. This is essentially what "reducio ad absurdium" is - where you make a statement and go through a series of logical steps to reach a contradiction (reduce to the absurd). This proves that the starting statement it is false, which at the same time proves that its converse is true.

As an example, let's prove that there are infinitely many prime numbers.

Make the initial statement "there are a finite number of prime numbers" and show that this statement is false.

If there are a finite number of prime numbers, then there must be some prime number that is the very largest (and the last if written in a sequence). Make a list of all the prime numbers up to the largest prime "P", so {2, 3, 5, 7, 11, 13, 17, 19, ... , P}.

Let's create a number by multiplying all the terms in this sequence, call it $\displaystyle \begin{align*} N = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \dots \times P \end{align*}$. If we add 1 to this number, we get $\displaystyle \begin{align*} N + 1 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \dots \times P + 1 \end{align*}$. If you tried to divide "N + 1" by any of the prime numbers up to "P", you will always have a remainder of 1. So this means that either "N + 1" is itself a prime number, or there is some prime number larger than "P" which divides it. Either way, this contradicts "P" being the largest prime number, and thus the original statement "there are a finite number of prime numbers" is false.

Therefore there are infinitely many prime numbers. Q.E.D.

 

[Ackbach]

I think negation is really the right concept here. In RA proofs, you assume the negation of what you want to prove. Once you get, as Evgeny mentioned, a contradiction, then outside the RA proof, you may infer what you wanted to prove. The term "converse" has a different meaning than "negation", and has more to do with interchanging the "if" and "then" parts of an implication. If I have the statement "Some men are married people", which is certainly true, then its converse is "Some married people are men", which is also true. The negation of "Some men are married people" would be "No men are married people".

 

[solakis1]

No, Assuming just $\neg(0<a\land 0<b)$, i.e., $a\le0\lor b\le0$, together with $0<ab$ does not lead to a contradiction.

Let 0<ab
let, ~(0<a & 0<b)..............1
let, 0<a
let, a<0
But 0<a & a<0 => 0<0 => 0<0 & ~(0<0) ,a contradiction
Hence ~(a<0)................2
For 0<a => 0<(1/a) => 0(1/a)< ab(1/a) => 0<b => 0<a & 0<b
And in conjuntion with (1) we have ~(0<a & 0<b).& (0<a & 0<b),contradiction
Thus ~(0<a)................3

Hence by (2) and (3) we have:

~(a<0) and ~(0<a) => ~(a<0 v 0<a) => a=0 .........4

And substituting (4) into (1) we hane 0<0b => 0<0 & ~ (0<0), a contradiction

Therefor ~~(0<a & 0<b) => (0<a & 0<b) =>( 0<a & 0<b)v (a<0 & b<0)

And finally ,

0<ab => ( 0<a & 0<b)v (a<0 & b<0)

 

[Evgeny.Makarov]

Your proof has incorrect scoping. Let's write the outline of your proof in Fitch calculus and make scoping explicit through offset. The subderivation of each formula depends on formulas labeled "assumption" that have strictly smaller offset. Also, to derive a formula $F$ using a derivation rule $\dfrac{F_1\quad\cdots\quad F_n}{F}$ one must only take $F_1,\dots,F_n$ with smaller or equal offset than $F$'s offset.

 1. 0 < ab			assumption
 2.     ~(0 < a & 0 < b)	assumption, (1)
 3.         0 < a		assumption
 4.             a < 0		assumption
                    ...
 5.                 _|_
 6.             ~(a < 0)	(2)
                ...
 7.             0 < a & 0 < b
 8.             _|_
 9.         ~(a < 0)		(3)
            ...
10.         a = 0		from (2) and (3)

The inference in line 10 breaks the second rule above about scoping: it uses (2) (i.e., line 6) whose offset is greater than that of line 10. At that point, one could only refer to (2) as $0 < a\to\neg (a<0)$ but not as $\neg(a<0)$ because the assumption $0<a$, which was essentially used in deriving (2), is already closed.

 

[solakis1]

 1. 0 < ab            assumption
 2.     ~(0 < a & 0 < b)    assumption, (1)
 3.         0 < a        assumption
 4.             a < 0        assumption
                    ...
 5.                 _|_
 6.             ~(a < 0)    (2)
                ...
 7.             0 < a & 0 < b
 8.             _|_
 9.         ~(a < 0)        (3)
            ...
10.         a = 0        from (2) and (3)

. At that point, one could only refer to (2) as $0 < a\to\neg (a<0)$ but not as $\neg(a<0)$ because the assumption $0<a$, which was essentially used in deriving (2), is already closed.

Assumtptions : 2,3,4,
Are subproofs assumptions for contradiction (RAA) AND none of them is assumption for Conditional proof
So when you close (discharge) assumption 3 to get $0<a\to\neg(a<0)$ automatically you are converting an assumption for (RAA) into a Conditional proof assumption to suit your wrong argumentation.

Besides , $0 < a\to\neg (a<0)$ is part of the law of trichotomy,why should i bother to prove that.

:

 

[Evgeny.Makarov]

First of all, I made a mistake in line 9, formula (3): it should be $\neg(0<a)$.

Assumtptions : 2,3,4,
Are subproofs assumptions for contradiction (RAA) AND none of them is assumption for Conditional proof
So when you close (discharge) assumption 3 to get $0<a\to\neg(a<0)$ automatically you are converting an assumption for (RAA) into a Conditional proof assumption to suit your wrong argumentation.

What I said about $0<a\to\neg(a<0)$ was not essential. It was a remark of the type, "You are doing something that is not allowed. You could possible circumvent this restriction, but then you need to do it in a different way". The important point is that you cannot use both formulas (2) and (3) (lines 6 and 9) to derive $a=0$ in line 10 because (2) uses an open assumption $0<a$ in line 3, which is closed in line 9.

It's like being a businessman who takes a loan to conduct a research project, for example, to develop a new medication formula. Using the money from the loan he builds an expensive research facility and does the necessary work. After obtaining the formula, he has to sell the facility to pay off the loan. As a result, he no longer has the facility or the ability to spend a big sum of money, but he has the formula instead. At this point it would be wrong for him to both use the formula and assert his rights on the building because it belongs to somebody else.

Finally, first-order logic is sound, that is, if $C$ is derived from $A$ and $B$, then $A\land B\to C$ is a valid formula. In your case, you derive $a=0$ from $0<ab$ and $\neg(0 < a\land 0 < b)$, but
\[
0<ab\land\neg(0 < a\land 0 < b)\to a=0
\]
is not valid.

 

[solakis1]

When you are proving a valid argument using the assumption reductio ad absurdem, can you assume anything in the conclusion, and then put a not in front of it, .

It depends on the problem.

Yes, you can assume anything of the conclusion, and then use RAA.

Look at the following proof in propositional calculus Where i use the NEGATION of whole OF THE CONCLUSION and the negation of part of the conclusion ~~P

Given :P=>Q , then prove: ~PvQ

Note there is no direct proof for the above.

proof: Without using D.Morgan

1. P=>Q.................Assumption

2. ~(~PvQ)..............Hypothesis for RAA

3. ~~P................Hypothesis for RAA

4. P...............3,Negation Elimination

5. Q.................1,4 M.Ponens

6. ~PvQ...............5,Addition

7. [~(~PvQ)]&(~PvQ)............2,6, Conjunction

8. ~P................3 to 7 RAA

9. ~PvQ................8,Addition

10. [~(~PvQ)]&(~PvQ)............2,9,Conjunction

11. ~~(~PvQ)..............2 to 10 RAA

12. (~PvQ).............11,Negation Elimination.In ANOTHER proof of the above we can use the negation of the whole conclusion and the negation of Q (~Q)

Look at avery simple proof :

Given : R => P,R,then prove PvQ

Here we can have a very simple direct proof ,however we can have an indirect proof by either assuming the negation of PvQ , OR the negation of P (~P) ,OR the negation of PvQ (~(PvQ) ) AND P ,OR the negation of PvQ AND the negation of P (~P) e.t.c,e.t.c.

 

[PeterJ1]

When dealing with logic, there are some basic assumptions:

1. A statement can only ever be true or false. There is no in between.

2. If a statement is true, then its converse is false. And vice versa.

So a way you can prove a statement is true is to show that its converse is false. This is essentially what "reducio ad absurdium" is - ...

As a philosopher rather than a mathematician I would add a proviso because it is a very important one that is often (perhaps usually) ignored by philosophers.

A statement can be true, false, meaningless or undecidable but the LEM and LNC can only be applied legitimately to true contradictory pairs where one of the pair is false and the other true. This can never be safely assumed but must be shown in logic. That is, for a reductio argument in the dialectic we must be sure right at the start that one of the two possibilities is false and the other true. If we cannot show this then the argument may be valid but it'll be an unreliable guide to the facts.

This avoids the danger of assuming that the LNC/LEM applies to a pair of statements when in fact it does not. Right here is one of the biggest problems in all of philosophy, assuming pairs of statements form true contradictory pairs when they do not, thus making category errors. You would be amazed at how poor philosophers are at using Aristotle's laws for this mistake is made all the time.

 

[solakis1]

As a philosopher rather than a mathematician

That is contradicting Plato's doctrine:

"Let no one who is ignorant of Goemetry enter my school"

... in the dialectic

What is dialectic

You would be amazed at how poor philosophers are at using Aristotle's laws for this mistake is made all the time.

Which are Aristotle's laws ??

 

[PeterJ1]

I think a dictionary would explain these things more effectively than I could here since it would be a long answer. A quick google will do it.