- #1

- 1,425

- 1

- Thread starter Werg22
- Start date

- #1

- 1,425

- 1

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Only in the philosophical sense of absolute knowledge. Mathematically, not only do we have relative consistency proofs, but I'm pretty sure there are examples of first-order theories capable of proving their own consistency. (Such a theory cannot be both recursively enumerable and include the theory of integer arithmetic, of course)Since it's impossible to know whether or not a consistent theory is indeed consistent,

It's a fairly direct consequence of the law of noncontradiction.how is a proof by contradiction a valid proof method?

A formal proof is valid if and only if it is built from the rules of deduction in whatever logic you're using.I would think a proof by contradiction is only valid if we are certain a theory is consistent, else a contradiction could mean that the theory is inconsistent.

Incidentally, in an inconsistent theory,

- #3

- 1

- 0

Reductio ad absurdum means, for example, that if you can prove black is white then the moon is made of green cheese. i.e. they both have the same truth value.

- #4

- 66

- 0

The following will show you why Now we must be very careful to distinguish between an implication and a logical implication. We say P implies Q noted as P---->Q and this can be true or false depending on the values of p and q. And if p is false and q true then P--->Q is true A thing that mattgrime so much insisted on

And we say that P logically implies Q denoted by P===>Q(DOUBLE ARROW) ,If the implication P---->Q IS ALWAYS TRUE no matter what are the values of p and q

Now let us see how contradiction works

Suppose we want to prove P===>Q BY the power invested on us by the rule in logic called conditional we can assume P and if prove Q we can say we have proved P===>Q

So let P

NOW it happens some time that we don't know how to arrive at Q

hence we reason by contradiction,hence we assume

notQ

THEN along down the steps of proof we come across two statement which are contradictory i.e R and notR A statement which is always false

And here now the doctrine (false LOGICALLY IMPLIES everything) can be used so we can get Q But why???????? AND HOW ????????

Let us see why:from R AND notR we can get notR (The law is called addition elimination)

Now from notR we can get (notR or Q) using the law Disjunction introduction.

But (notR or Q) is logically equivalent to ( R--->Q) The law is called material implication

But from( R and notR) we can get R.

Hence now from (R--->Q)and R by using the law called M.Ponens we get Q

HENCE P===>Q

Note T is logically equivalent to S Iff they logically imply each other y contradiction is valid:

CERTAINLY we must assume that the system within we work is consistent .Very few systems are consistent and then again it depends on the definition of consistency.

The propositional calculus for example is asystem which is CONSISTENT COMPLETE AND DECIDABLE while predicate calculus is CONSISTENT AND COMPLETE relative to the set of valid formulas

- #5

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

Theories prove statements. As you add axioms to theories, they can prove more statements (or as many, if you add something redundant). If you add enough powerful axioms the theory becomes inconsistent, that is, it proves every statement.

So proof by contradiction seems quite sensible to me. If the underlying theory is inconsistent you can prove everything anyway, so there's no problem with proof by contradiction (a problem would be not being able to prove something, since everything is provable).

- #6

- 15,393

- 685

The mathematicians at PF know what this means. Many readers will not. What CR is saying is that if both a proposition [itex]R[/itex] and its contradiction [itex]\lnot R[/itex] are provable in some theory thenIf you add enough powerful axioms the theory becomes inconsistent, that is, it proves every statement.

Suppose [itex]R[/itex] and its contradiction [itex]\lnot R[/itex] are both true in some theory. I will prove a statement [itex]S[/itex] in this theory using two tautologies and the rule of

- [tex]\lnot P \to (\lnot Q \to \lnot P)[/tex]

The contradiction of*P*implies (the contradiction of*Q*implies the contradiction of*P*). Material implication is bit of a strange beast. [tex]A\to B[/itex] means that if*A*is true then*B*must also be true. If*A*is true but*B*is false then*A*does not imply*B*. Material implication, on the other hand, does not place any limitations on*B*if*A*is false. The expression [tex]\lnot P \to (\lnot Q \to \lnot P)[/tex] is a tautology.

- [tex](\lnot Q \to \lnot P) \to (P \to Q)[/tex]

(The contradiction of Q implies the contradiction of P) implies (P implies Q). This is another tautology. These two tautologies fall out from the definition of material implication.

- [tex]A \to B, \, A\vdash B[/tex]

This is*modus ponens*, which says that if*A*implies*B*is true and if [/i]A[/i] is true then*B*is true.

The proof, using

- [tex]\lnot R\quad[/tex]

Given.

- [tex]\lnot S \to \lnot R[/tex]

From step 1 and tautology a.

- [tex]R \to S[/itex]

From step 2 and tautology b.

- [tex]R\qquad[/tex]

Given.

- [tex]S[/itex]

From step 4 and step 3, and QED.

- #7

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

I'll note that the conclusion only holds if you allow certain axioms -- in the above, two particular tautologies (contraposition and introduction) along with modus ponens. Just like the equivalence of the axiom of choice and Zorn's lemma (which requires a strong enough fragment of ZF), the existence of rectangles (requires the parallel postulate), and the incompleteness of consistent systems (requires a certain system strength), this can fail for weak enough systems. In the extreme, the empty theory can't draw any conclusions from P and not-P.

- #8

- 15,393

- 685

I knew those tautologies had a name, too. I just could not remember them for the life of me. Why I can remember the names of the Latin phrasescontraposition and introduction

- #9

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

Amusingly, I can never remember what *modus tollens* is despite having learned Latin.

- #10

- 15,393

- 685

Foward chaining rule systems like CLIPS and ART use

- #11

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

- #12

- 66

- 0

What actually happens is the following:

you read a couple of things in a couple of books and then you come here and you throw the stuff pretending that you are an expert.

Definitely nobody of you is knowledgeable enough in logic stuff to be able to put it in practice.

I ask you again: Do you know logic? If yes, here and now show me. Pick up any mathematical proof you like and show your expertise in applying the laws of logic in that proof.

- #13

- 15,393

- 685

In a prior career incarnation I worked in the field of AI, back in its hey-day. I had the monitor for Symbolics machine #2 sitting on my desk and the rest of the machine (wire-wrap boards and all) sitting down the hall. I worked with the developers of CLIPS on a first-name basis. So please, try again.The point with you guys is that you write nonsense all the time and if somebody asks you a question with respect to your nonsense and illogical mumbling you get angry.

- #14

- 15,393

- 685

No. Its another name for DH types too fast.Modus pollens? Is that another name formodus ponens?

- #15

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

I answered the question in post #5, though now I see Hurkyl gave the same answer (but shorter and better) in post #2. D H expanded on my answer in post #6.The point with you guys is that you write nonsense all the time and if somebody asks you a question with respect to your nonsense and illogical mumbling you get angry.

I'll admit to being confused about 'us' getting angry: where has anyone displayed annoyance, let alone anger on this thread? Or are you talking about a different thread, perhaps? Sometimes the PhDs get a bit huffy in response to thickheadedness, but usually this is a friendly place. Certainly I can't recall ever posting here in anger.

Wow, you're really throwing down the gauntlet.you read a couple of things in a couple of books and then you come here and you throw the stuff pretending that you are an expert.

Definitely nobody of you is knowledgeable enough in logic stuff to be able to put it in practice.

I ask you again: Do you know logic? If yes, here and now show me. Pick up any mathematical proof you like and show your expertise in applying the laws of logic in that proof.

1. [tex]1\stackrel{\mathrm{def}}{=}S(0)[/tex]

2. [tex]2\stackrel{\mathrm{def}}{=}S(1)[/tex]

3. [tex]1+0=1[/tex]

4. [tex]1+1=1+S(0)[/tex] (using 1)

5. [tex]1+1=S(1+0)[/tex] (using 4)

6. [tex]1+1=S(1)[/tex] (using 3 and 5)

7. [tex]1+1=2[/tex] (using 2 and 6)

There. Now let's see you do [tex]2\times2=4[/tex] in Peano arithmetic.

- #16

- 66

- 0

if the theory is not consistent, then a contradiction doesnt work.

I ask you again: Do you know how contradiction works?

I will show you for the last time how contradiction works.

In a proof by contradiction you ALWAYS END UP with 2 contradictory statements i.e.

[tex]R \wedge \neg R[/tex]

Then study carefully the following steps.

1) [tex]R \wedge \neg R[/tex]

2) [tex]R[/tex]................................(from step 1 and using conjuction elimination)

3) [tex] \neg R[/tex].............................(from step 1 and using conjuction elimination)

4) [tex]R \rightarrow R \vee Q[/tex].................(from step 2 and using disjunction introduction)

5) [tex]R \vee Q[/tex].........................(from step 2 and step 4 and using modus ponens)

6) [tex]R \vee Q \leftrightarrow \neg R \rightarrow Q[/tex]...... (from step 5 and using material implication)

7) [tex]\neg R \rightarrow Q[/tex].....................(from steps 5 and 6 and modus ponens)

8) [tex]Q[/tex] ...............................(from step 7 and step 3 and modus ponens)

So suppose you wanted to prove [tex]P \rightarrow Q [/tex]

By using the rule of the conditional proof we assume [tex]P[/tex] and also we assume [tex]\neg Q[/tex]

Then somewhere down along the proof we come with a contradictory statement [tex]P \wedge \neg P[/tex]

Then we follow the above steps to prove [tex]Q[/tex]

Take that home and study it carefully. Then I am sure you will change attitude

- #17

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

What does that mean?if the theory is not consistent, then a contradiction doesnt work.

- #18

- 66

- 0

I mean to explicitly mention the laws of logic involved in every step of your proof.I answered the question in post #5, though now I see Hurkyl gave the same answer (but shorter and better) in post #2. D H expanded on my answer in post #6.

I'll admit to being confused about 'us' getting angry: where has anyone displayed annoyance, let alone anger on this thread? Or are you talking about a different thread, perhaps? Sometimes the PhDs get a bit huffy in response to thickheadedness, but usually this is a friendly place. Certainly I can't recall ever posting here in anger.

Wow, you're really throwing down the gauntlet.

1. [tex]1\stackrel{\mathrm{def}}{=}S(0)[/tex]

2. [tex]2\stackrel{\mathrm{def}}{=}S(1)[/tex]

3. [tex]1+0=1[/tex]

4. [tex]1+1=1+S(0)[/tex] (using 1)

5. [tex]1+1=S(1+0)[/tex] (using 4)

6. [tex]1+1=S(1)[/tex] (using 3 and 5)

7. [tex]1+1=2[/tex] (using 2 and 6)

There. Now let's see you do [tex]2\times2=4[/tex] in Peano arithmetic.

Where is that?

- #19

- 66

- 0

It means that you cannot apply contradiction if the theory is incosistent.What does that mean?

Because in incosistent theories somewhere you will get a contradictory statement hence when you work by contradiction you will not know if you meet this particular statement and hence contadiction has no value.

- #20

- 66

- 0

Maybe not you CRGreathouse but in another thread where i was acussed of not knowing the number pi (the Greek invented number) when i responded back the got so ungry that they deleted my posts.Certainly I can't recall ever posting here in anger.

- #21

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

It's pretty evident, using two definitions, the two addition axioms, and the identity of indiscernibles.I mean to explicitly mention the laws of logic involved in every step of your proof.

Where is that?

I. n + 0 = n

II. m + S(n) = S(m + n)

1. [tex]1\stackrel{\mathrm{def}}{=}S(0)[/tex] (definition)

2. [tex]2\stackrel{\mathrm{def}}{=}S(1)[/tex] (definition)

3. [tex]1+0=1[/tex] (I)

4. [tex]1+1=1+S(0)[/tex] (identity of indiscernibles, using 1)

5. [tex]1+1=S(1+0)[/tex] (II, using 4)

6. [tex]1+1=S(1)[/tex] (identity of indiscernibles, using 3 and 5)

7. [tex]1+1=2[/tex] (identity of indiscernibles, using 2 and 6)

- #22

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

I don't follow at all. Of course you can get contradictions in inconsistent theories, that's the whole point. In fact inconsistent theories (unless paraconsistent or otherwise weak) prove all statements, so RAA/proof by contradiction correctly proves everything in those theories. Or rather, in that theory; other than the aforementioned weak theories, there is only one inconsistent theory. To be precise, there is a unique inconsistent theory containing first-order logic, which contains as theorems all the axioms of ZFC, Tarski's axiom, the generalized continuum hypothesis, the negation of the Riemann hypothesis, Martin's axiom, the existence of heaps of large cardinals, V = L, [tex]\beth_1=\aleph_3,[/tex] 1 + 1 = 7, and a host of other amazing statements.It means that you cannot apply contradiction if the theory is incosistent.

Because in incosistent theories somewhere you will get a contradictory statement hence when you work by contradiction you will not know if you meet this particular statement and hence contadiction has no value.

- #23

- 66

- 0

OK STEPS 1 AND 2 ,BY WHAT LAW YOU GET 3

ALSO EXPLAIN <identity of indiscemibles>

ALSO EXPLAIN <identity of indiscemibles>

- #24

- 66

- 0

if you cannot give a right proof i can give you one

- #25

- 66

- 0

for all x and for all y(x>=0 and y>=0 -------> ( sqroot(xy)=sqroot(x).sqroot(y) ))

CAN YOU DO IT STEP WISE??????

- Replies
- 2

- Views
- 2K

- Replies
- 1

- Views
- 1K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 2K

- Replies
- 3

- Views
- 24K

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 7K

- Replies
- 2

- Views
- 4K

- Replies
- 9

- Views
- 1K