- #1

Werg22

- 1,427

- 1

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Werg22
- Start date

- #1

Werg22

- 1,427

- 1

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 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

Mathsbaby

- 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

LAVRANOS

- 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,842

- 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,450

- 688

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,842

- 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,450

- 688

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,842

- 0

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

- #10

- 15,450

- 688

Foward chaining rule systems like CLIPS and ART use

- #11

CRGreathouse

Science Advisor

Homework Helper

- 2,842

- 0

- #12

LAVRANOS

- 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,450

- 688

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,450

- 688

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

- #15

CRGreathouse

Science Advisor

Homework Helper

- 2,842

- 0

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 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.

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.

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.

- #16

LAVRANOS

- 66

- 0

if the theory is not consistent, then a contradiction doesn't 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,842

- 0

if the theory is not consistent, then a contradiction doesn't work.

What does that mean?

- #18

LAVRANOS

- 66

- 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.

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.

I mean to explicitly mention the laws of logic involved in every step of your proof.

Where is that?

- #19

LAVRANOS

- 66

- 0

What does that mean?

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.

- #20

LAVRANOS

- 66

- 0

Certainly I can't recall ever posting here in anger.

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.

- #21

CRGreathouse

Science Advisor

Homework Helper

- 2,842

- 0

I mean to explicitly mention the laws of logic involved in every step of your proof.

Where is that?

It's pretty evident, using two definitions, the two addition axioms, and the identity of indiscernibles.

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,842

- 0

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.

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.

- #23

LAVRANOS

- 66

- 0

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

ALSO EXPLAIN <identity of indiscemibles>

ALSO EXPLAIN <identity of indiscemibles>

- #24

LAVRANOS

- 66

- 0

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

- #25

LAVRANOS

- 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?

- #26

LAVRANOS

- 66

- 0

Sorry I Did Not Notice That You Want Me To Do 2x2=4 In Peano Arithmetic

- #27

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

Stop shouting. :grumpy:OK STEPS 1 AND 2 ,BY WHAT LAW YOU GET 3

ALSO EXPLAIN <identity of indiscemibles>

If you're challenging others to write explicit and complete formal proofs from scratch (i.e. without invoking known theory) -- the least you could do is to fully and accurately present what it is you want others to prove.

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

CAN YOU DO IT STEP WISE?

e.g. what is the range of the variables

Also, note that if

Last edited:

- #28

LAVRANOS

- 66

- 0

O.K IWAITED to long and it is getting late .Here is aproof that 1+1=2

1)for all x and for all y(x +Sy =S( x+y)) A peano axiom

2) 1 +S(0) = S( 1+ 0) from 1 and using Univ.Elim. where we put x=1 and y=0

3) for all x (x + 0 =x ) A peano axiom

4) 1 + 0 = 1 from 3 and using Univ.Elim where we put x=1

5) 1+S(0) = S(1) BY substituting 4 into 2

6) S(0)=1 BY definition

7) S(1)=2 By definition

8) 1+1=2 By substituting 6 and 7 into 5

SO HERE WE USED TWO LAWS OF LOGIC namely Universal Elimination and the substitution law and two peano axioms together with two definitions

1)for all x and for all y(x +Sy =S( x+y)) A peano axiom

2) 1 +S(0) = S( 1+ 0) from 1 and using Univ.Elim. where we put x=1 and y=0

3) for all x (x + 0 =x ) A peano axiom

4) 1 + 0 = 1 from 3 and using Univ.Elim where we put x=1

5) 1+S(0) = S(1) BY substituting 4 into 2

6) S(0)=1 BY definition

7) S(1)=2 By definition

8) 1+1=2 By substituting 6 and 7 into 5

SO HERE WE USED TWO LAWS OF LOGIC namely Universal Elimination and the substitution law and two peano axioms together with two definitions

Last edited by a moderator:

- #29

HallsofIvy

Science Advisor

Homework Helper

- 43,021

- 971

- #30

peos69

- 102

- 0

If for example the real Nos system is not consistent then nature itself is not consistent

- #31

CRGreathouse

Science Advisor

Homework Helper

- 2,842

- 0

If for example the real Nos system is not consistent then nature itself is not consistent

I'm not even sure what it would mean for nature to be inconsistent. In a formal system it means that there is a proposition P such that both P and not-P can be proved. Any inconsistent system containing classical first-order logic can, in fact, prove any statement. But what would the analogue for 'nature' be?

- #32

peos69

- 102

- 0

FOR all m and for all h [ if air resistance is 0 then the time taken for m to reach the ground will be, t=sqroot(2h/g)].

Now the negation of this P WOULD be that there exist an m and an h such that t=/=sqroot(2h/g),where g =10m/sec^2,provided of course that again air resistance is 0.

Here is your analogue

- #33

CRGreathouse

Science Advisor

Homework Helper

- 2,842

- 0

So nature's inconsistency would mean that everything can, and does, happen?

- #34

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

How? This is, for sure, a theorem of Newtonian mechanics, but how can you prove it for 'nature itself'?then you can prove the following proposition P

- #35

peos69

- 102

- 0

How? This is, for sure, a theorem of Newtonian mechanics, but how can you prove it for 'nature itself'?

I am not sure i get you point please be a bit more specific

Share:

- Last Post

- Replies
- 2

- Views
- 191

- Last Post

- Replies
- 12

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 315

- Replies
- 9

- Views
- 1K

MHB
Set proof

- Last Post

- Replies
- 5

- Views
- 656

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 1K

- Replies
- 14

- Views
- 596

- Replies
- 2

- Views
- 269