Negation elimination rule in natural deduction

[drguildo]

Can somebody please explain the negation elimination rule in natural deduction to me? I've read a few explanations and none of them make any sense whatsoever. Nor do I understand how you can (or why you would want to) be able to infer anything from a contradiction.

Thanks.

 

[Kittel Knight]

Suppose you have a set of preestablished facts.
If a new assumption leads you to a contradiction, then it is false.

 

[drguildo]

Suppose you have a set of preestablished facts.
If a new assumption leads you to a contradiction, then it is false.

Then surely that would just reinforce the original set of facts? Why should you be able to deduce anything from that contradiction?

 

[CRGreathouse]

Then surely that would just reinforce the original set of facts? Why should you be able to deduce anything from that contradiction?

I take it you've never played sudoku?

 

[Kittel Knight]

Suppose you have a set of preestablished facts.
If a new assumption leads you to a contradiction, then it is false.

Then surely that would just reinforce the original set of facts? Why should you be able to deduce anything from that contradiction?

What about an example?

Consider the pertinent preestablished facts , also known as axioms or theorems :
Axiom 1 : "If a guy knows Logic then he understands my first post."
Axiom 2 : "Peter doesn't understand my first post"Let's make the assumption Peter knows Logic.

So, since Peter is a guy and we are assuming he knows Logic, then, according to the Axiom 1, Peter understands my first post.

However, according to the Axiom 2, Peter doesn't understand my first post - which is a contradiction!

So, our assumption is false, and the final conclusion is that Peter doesn't know Logic.

 

[drguildo]

I take it you've never played sudoku?

I have played Sudoku, I don't see the relationship though. Especially not when it comes to being able to deduce anything from a contradiction.

 

[drguildo]

What about an example?

Thanks; that's a good intuitive example of how contradiction can be a useful tool in reasoning, but I think I'm being misunderstood when I say you can conclude "anything" from a contradiction. I literally mean anything. For example, the book I'm reading (Proof and Disproof in Formal Logic) states in regard to contradiction:

The technical way in which Natural Deduction deals with this situation is to say that in an impossible situation, you can conclude whatever you like in order to tidy things up.

 

[exk]

I have played Sudoku, I don't see the relationship though. Especially not when it comes to being able to deduce anything from a contradiction.

Sudoku provides with a set of numbers that whose position is predefined. If you try to place a number in a manner that breaks the rules of sudoku you receive a contradiction, which leads to the conclusion that placing the number in that manner is impossible.

 

[drguildo]

Sudoku provides with a set of numbers that whose position is predefined. If you try to place a number in a manner that breaks the rules of sudoku you receive a contradiction, which leads to the conclusion that placing the number in that manner is impossible.

Indeed, if a square has to be one of X, Y or Z, and you know it isn't X or Z, then it must be Y (queue Sherlock Holmes quote). But I don't understand how this relates to the formal rule of negation elimination and it's relationship with contradiction which states that should you encounter a contradiction, then you can conclude whatever you want.

 

[exk]

The definition you posted above states that in an "impossible" situation you can do that. Consider a situation with three 5s in one square in sudoku. If you encounter that situation you can conclude that the placement of the numbers was incorrect to tidy it up, or you can conclude that this is some special type of sudoku, or that the moon is made of cheese (if that somehow helps clear up the situation).

 

[LukeD]

Unless I'm mistaken, I think you're asking about this:

Let's say you have a few statements
P,Q,R
all of which you know as a fact are true.

Then $$P \Rightarrow Q$$ is a true statement. However,$$\neg P \Rightarrow Q$$ is also a true statement. In fact, $$\neg P \Rightarrow \neg Q$$ is also a true statement.

This is because in classical logic, you take it as an axiom that if you have statement of the form $$P \Rightarrow Q$$ and P is false, then the statement is true no matter what Q is. This is just basically taken as true so that the logic is consistent and you cover all of your bases as far as what sort of statements you can conclude from a false statement.

Let's say you have the statement $$1=2$$. Using the usual definitions of 1 and 2, this is a false statement. However, from this statement, you can conclude that $$2=1$$, and using both of these together with the transitive property, you can conclude that $$1 = 1$$, so you were able to conclude 1 false thing as well as 1 true thing.

In principle, however, if you are using "correct logic", then it is not possible to conclude "everything" from a false statement. It is just that in classical logic, concluding anything from a false statement is considered valid. There are other logical systems though where this is rejected. Try looking up paralogical systems in Wikipedia.

 

[drguildo]

What I don't get is how it's used to validate certain inferences. My understanding is that any path of reasoning that leads to a contradiction is fallacious and should be abandoned with nothing inferred from it except the opposite case (at least in classical logic which has the law of excluded middle).

For example arguing by cases in or-elimination. I don't know how to write it out in TeX and I would probably do a bad job of explaining it so I've attached a small snippet in the form of an image. I hope this is OK.

 

[LukeD]

Sorry, I meant paraconsistent logic

 

[Kittel Knight]

Well, there is nothing wrong in saying "If Marilyn Monroe kisses me tonight, then I will fly for 2 hours".
This is a true statement, isn't?
Of course, since we know MM is dead, I can say any thing as "the consequence" of being kissed by her.
In fact, I could say "then the Sun will disappear instantaneously", and the statement would be true, again.
Agreed?

 

[drguildo]

Well, there is nothing wrong in saying "If Marilyn Monroe kisses me tonight, then I will fly for 2 hours".
This is a true statement, isn't?
Of course, since we know MM is dead, I can say any thing as "the consequence" of being kissed by her.
In fact, I could say "then the Sun will disappear instantaneously", and the statement would be true, again.
Agreed?

So we're not really inferring anything from Marilyn Monroe kiss scenario, it's just that we can state whatever we like because it's impossible (cf. contradiction)?

 

[CRGreathouse]

I have played Sudoku, I don't see the relationship though. Especially not when it comes to being able to deduce anything from a contradiction.

Now hang on. I'm responding to your question "Why should you be able to deduce anything from that contradiction?" (1). That anything can be deduced from a contradiction (2) is a different principle:

1. Given A, suppose B. A and B imply not A. Thus, not B.
2. Given A and B. A and B imply not A. Thus, ___.


In Sudoku, there are many situations where I try a number and find that it forces a contradiction. This allows me to conclude that the number I chose is wrong.

 

[Kittel Knight]

So we're not really inferring anything from Marilyn Monroe kiss scenario, it's just that we can state whatever we like because it's impossible (cf. contradiction)?

Perfectly !

 

[drguildo]

Perfectly !

Okay, but this raises the question what is the point in deducing something from a situation that is never going to be able to arise in order to lead to it? I also still don't understand how it can be used to justify or-elimination.

 

[Kittel Knight]

I think I'm being misunderstood when I say you can conclude "anything" from a contradiction. I literally mean anything. For example, the book I'm reading (Proof and Disproof in Formal Logic) states in regard to contradiction:
The technical way in which Natural Deduction deals with this situation is to say that in an impossible situation, you can conclude whatever you like in order to tidy things up.

"If Marilyn Monroe kisses me tonight, then I will fly for 2 hours".
This is a true statement, isn't?

Of course, since we know MM is dead, I can say any thing as "the consequence" of being kissed by her.
In fact, I could say "then the Sun will disappear instantaneously", and the statement would be true, again.

Okay, but this raises the question what is the point in deducing something from a situation that is never going to be able to arise in order to lead to it?
...

Now,suppose MM really kisses me tonight... off course this is a contradiction!

And thanks to that, it is true I will fly for 2 hours.

As you see, if there is a contradiction, then we can conclude anything we want!

 

[drguildo]

As you see, if there is a contradiction, then we can conclude anything we want!

Yes, we've already been over that. What I want to know is what's the point.

 

[CRGreathouse]

Yes, we've already been over that. What I want to know is what's the point.

The point of being able to conclude "something" is that it allows proofs by contradiction, which are both common and fruitful. There is no point as such in the principle of explosion, that one can conclude anything from a conclusion; that simply follows from the first.

 

[drguildo]

The point of being able to conclude "something" is that it allows proofs by contradiction, which are both common and fruitful. There is no point as such in the principle of explosion, that one can conclude anything from a conclusion; that simply follows from the first.

Okay, so why not say: if we assume ¬F, blah, blah, blah, we reach a contradiction, therefore we conclude F must be true; rather than concluding anything we want.

 

[CRGreathouse]

Okay, so why not say: if we assume ¬F, blah, blah, blah, we reach a contradiction, therefore we conclude F must be true; rather than concluding anything we want.

That's the proof by contradiction I mentioned above.

To get from proof by contradiction to the principle of explosion (can't remember how to spell the Latin!), take F to be any proposition, assume ¬F, reach a contradiction (in whatever way you were going to before, not using F or ¬F), and conclude F.

Some people (not me) have trouble accepting this principle, thus the development (mentioned above, but not by me) of paraconsistent logics which permit contradictions but allow little to be derived from them. This obviously weakens the ability of a mathematician to argue with proofs by contradiction!

 

[drguildo]

To get from proof by contradiction to the principle of explosion (can't remember how to spell the Latin!), take F to be any proposition, assume ¬F, reach a contradiction (in whatever way you were going to before, not using F or ¬F), and conclude F.

I don't have a problem understanding this. It makes sense at least in the context of the law of excluded middle.

However the book I'm reading states more than this, as you can see in posts #7 and #12.

 

[Kittel Knight]

I don't have a problem understanding this. It makes sense at least in the context of the law of excluded middle.

However the book I'm reading states more than this, as you can see in posts #7 and #12.

You would like to understand your book. However, you have read the post #19, and don't know what is the point...

 

[drguildo]

You would like to understand your book.

I sure would.

However, you have read the post #19

From what I can gather, it was a restatement of previous posts, but yes. I have.

, and don't know what is the point...

Yes. What is the benefit of being able to conclude anything beyond the opposite of the proposition that led to the contradiction?

 

[CRGreathouse]

Yes. What is the benefit of being able to conclude anything beyond the opposite of the proposition that led to the contradiction?

The benefit is that, if you use a logic admitting proofs by contradiction, it is simple (as in my last post) to show that a proof by contradiction proves that any assertion follows from a contradiction. So if you accept proofs by contradiction, but not the principle of explosion ("draw any conclusion from a contradiction"), then you're holding an inconsistent position.

 

[FernBarc]

I'd suggest a culinary book...

 

[drguildo]

The benefit is that, if you use a logic admitting proofs by contradiction, it is simple (as in my last post) to show that a proof by contradiction proves that any assertion follows from a contradiction.

It seems to me you just restated proof by contradiction. I found this nice explanation on Everything2:

Suppose you grant me that both P and its negation -P are true (e.g. it is simultaneously true that I am and am not the Pope). Let R be any other statement (e.g. "roses are blue".) Then, the statement E = "either P or R is true" is itself true because P is true. However, P is also false (i.e. -P is true), thus we conclude that R is true because we have eliminated the case that P is true (this is a disjunctive syllogism). We conclude that if I am and am not the Pope, then roses are blue.

 

[FernBarc]

I found this nice explanation on Everything2:

You should read post #19 again...

(In fact, you should read all this thread again and again, and again...)

 

[drguildo]

You should read post #19 again...

(In fact, you should read all this thread again and again, and again...)

Why? Is the explanation I pasted incorrect?

 

[CRGreathouse]

drguildo, you asked what the benefit was to the principle of explosion. I told you it was because proofs by contradiction necessarily show the principle of explosion. Then you post a proof of the principle of explosion (by disjunctive introduction and quantifier elimination) and somehow this explains it for you? I thought you were after a reason, not a proof -- and haven't people posted proofs already?

You should read post #19 again...

(In fact, you should read all this thread again and again, and again...)

Actually, I don't think there's any special benefit to reading post #19. That essentially explains what explosion is, not why it's true or why we care.

 

[FernBarc]

Why? Is the explanation I pasted incorrect?

The both explanations are the samething.

 

[drguildo]

drguildo, you asked what the benefit was to the principle of explosion. I told you it was because proofs by contradiction necessarily show the principle of explosion. Then you post a proof of the principle of explosion (by disjunctive introduction and quantifier elimination) and somehow this explains it for you? I thought you were after a reason, not a proof -- and haven't people posted proofs already?

The explanation in your post was fine and answered my question, but only in the context of a proof of the principle of explosion which you said was contained in a previous post of yours, but which I couldn't (and still can't) "see". Once I read the proof I cited then it clicked. Not all explanations are equal and just because one (or two, or three) makes perfect sense to people who understand the concepts already, doesn't mean it will to somebody who doesn't.

I'm obviously still learning so it's probable that I have used certain terms in the wrong context and in an imprecise manor which has lead to wires getting crossed. I'm also searching around and making small bits of progress here and there and so things that didn't make sense earlier make sense now.

 

[FernBarc]

Actually, I don't think there's any special benefit to reading post #19. That essentially explains what explosion is, not why it's true or why we care.

Yes, there is nothing new in post #19. But it does more than explaining explosion: it proves it is true.
I've mentioned post #19 cause it was the last post explaining (or "proving", once more) the same as post #26.
And, if it is clearly proved, there is no need to "explain in other words".