Beware: Proof Ahead

[noahgibbs]

A thought-provoking post by internet_addict got me onto a different topic. I was taking a Boolean logic class back in college. We had a little logical solver, and we'd tell it what transformations to apply in what order to get from the givens to the result. It was nifty. One of the ones I had trouble with was to prove that given inconsistent premises, you can prove anything. In other words, if your given propositions contradict, there is *nothing* you can't prove. To put it in formal terms:

Given: P && ^P (that means: P and not P)
Prove: Q (any unrelated assumption)

And you can do that, knowing nothing about Q. Here's how:

Q || ^Q (Tautology -- every proposition must be either true or false)
^Q => P (Tautology -- if P is true then anything implies P, by definition of logical "implies")
^P => ^^Q (Contrapositive of the previous -- if ^Q implies P then ^P implies ^^Q)
^P => Q (not not Q is the same as Q)

You know that ^P is true from the given: (P && ^P).
So, from only (P && ^P) you have proven the unrelated proposition Q.

It's easier if you do a proof by negation, of course. But we were explicitly not allowed to do that on this problem, since it'd make it trivial.

Comments

Nitpick

[sui66iy.livejournal.com]

So, from only (P || ^P) you have proven the unrelated proposition Q.

Is a typo.

Re: Nitpick

[angelbob.livejournal.com]

True. Fixed.

[internet-addict.livejournal.com]

My interpretation of this post probably stems from a problem of defining scope. I have problems with your second postulate, ^q => p. In strict Boolean logic terms this is fine. However, in reality your statement would be open to serious causality falacies, ala "the train comes when there are enough people on the platform."

I suspect you may have had scope definition problems with my post too, although your answer in and of itself was elucidating.

[angelbob.livejournal.com]

Ah. You're treating it as a generality, which is to say, you're treating Q as a class of propositions. Rather, it needs to be something exact.

If the train, for whatever reason, *always* came when there were enough people on the platform (say you were in Italy under Mussolini, and for some reason your scope was restricted in years) then that would be effectively true.

More to the point, the tautology is "if the second one is always true, then anything implies it."

In other words, if there were *always* enough people on the platform, then when the train didn't come there would always be enough people on the platform. Similarly, when the train came, there would *still* always be enough people on the platform, even if the train ever actually shows up.

That's called "vacuously true". In Boolean logic, if not necessarily in life, you call any "false implies something" statement true. So if you say "If Ronald Reagan were a black woman, James Watt would be an ostrich", that's vacuously true.

[internet-addict.livejournal.com]

Which is just as useful as Schroedinger's original purpose for his famous cat. It was originally intended not as a teaching tool, but as a demonstration of how rediculous it would be to apply quantum concepts to the macro universe.

Hrm... in Schroedinger's Cat, does the mechanism to gas the cat qualify as an observer? Although I suspect the point is irrelevant given that the mechanism is based on radioactive decay, not uncertainty.

[angelbob.livejournal.com]

Which is just as useful as Schroedinger's original purpose for his famous cat.

Well, it's more useful given that it keeps the logic nice and regular. It's like having a number zero -- not very useful on the surface, but *very* useful once you've had it around for a bit. It makes your rules work without lots of ugly glaring exceptions.

But mainly it's because that's the definition of "implies" in a logical sense. "Implies" means "if the first one is true, the second one must be also." Which says nothing about what happens if the first one is false.

[plymouth.livejournal.com]

but if you're saying P && ^P you can't make P be something like "there are always people on the platform" because there are also then always NOT enough people on the platform. Of course I can't think of an example where P is silmultaneously both true and ^P is also true. Or was that your point in the first place?

[angelbob.livejournal.com]

Right, so P && ^P is nonsensical. It can't happen, at least in Boolean logic.

So it's interesting that if you start with one false premise, anything can be proven. Why is that interesting? Well, if you're an atheist, it shows that if God doesn't exist, Christians could use that one false premise (which presumably contradicts something else in the world) to prove essentially anything. Ditto for whatever flavor of person you debate whose premises you don't agree with.

You may already believe that arguing from premises you don't agree with is stupid, and lets the other person potentially say whatever they want, but it's nice to have a formal proof of why it's a bad idea and how bad :-)

[terpsichoros.livejournal.com]

I'm not familiar with all the rules of Boolean logic, but I think your fallacy is in the "implies". The statement "A implies B" is not necessarily true for all true A and B.

A: I exist.
B: You exist.

A and B are both true, but A does not imply B. There is no therefore there.

So your statement:
^Q => P (Tautology -- if P is true then anything implies P, by definition of logical "implies")
is incorrect, and your chain of reasoning fails.

However, within the scope of Ps and Qs where ^Q => P or ^Q => ^P, you can use contradictory premises to prove Q and also prove ^Q.

[angelbob.livejournal.com]

Actually, under the rules of Boolean logic, "implies" is defined very specifically. It is, in fact, correct in this case. A Boolean "implies" says nothing about causation, which is outside the scope of formal algebraic logic anyway.

In a Boolean logic sense, the word "implies" means only: if the first is true, the second is true. If the first is false, it's meaningless ("vacuously true"). If the second is always true, then you've automatically satisfied it.

So you're right, that would be false if we used the Webster's Dictionary definition of "implies", but that'd be as silly as trying to derive algebra from the dictionary definitions of "add", "multiply" and so on -- there are a lot of connotations in English that are different from the mathematical meaning.

[terpsichoros.livejournal.com]

First - can you point me to an online resouece for Boolean algebra which includes that definition for "implies"?

Second - either there is some sort of logical (not necessarily causal) link in the definition of "implies", or the operation you've performed on the statement cannot be valid in all cases.

[angelbob.livejournal.com]

I can't find anything impressive, but here's on link to what looks like a student tutorial about 'implies'.

Second - either there is some sort of logical (not necessarily causal) link in the definition of "implies", or the operation you've performed on the statement cannot be valid in all cases.
I'm not sure what to say to this. In Boolean algebra, 'and' is an operation that is true if both of its arguments are true, and false otherwise. 'Or' and 'xor' have similar but different definitions. 'Implies' is a perfectly good operator defined in terms of the truth or falsehood of its arguments. That seems like a perfectly good logical definition of 'implies' to me, though you're welcome to disagree. 'Implies' is, again, true if either its first argument is false or its second argument is true (or both). Seems pretty well-defined to me.

If the first or second argument is a statement whose value is yet to be proven, that'd be more or less like standard algebra -- just because you don't know the value of b doesn't mean that "a=b*3 + 7" is necessary incorrect.

[r-transpose-p.livejournal.com]

Wait a minute, isn't (Q || ^Q) simply a restatement of ^(P && ^P), which you've explicitly assumed to be false?

I thought there was an entire branch of logic built around not using the law ^(P && ^P), or does that branch simply refuse to use said axiom, rather then saying "what if it were false?"

[angelbob.livejournal.com]

No, (P && ^P) isn't true of *everything*, just one premise. So even if (P && ^P), Q can be either true or false.

There's a branch of logic built around the idea that ^^P != P. Interestingly, even in that branch of logic, ^^^P == ^P, though that's something else again.

But I could believe that there's a branch built around (P && ^P). I will tell you for certain that it's not Boolean, though, or if it is it's not very interesting since every proposition is true by definition.

You couldn't get very far in Boolean logic by just not using it because there are a lot of other rules that depend on it. Maybe you could rederive which ones still worked, but it would have very little in common with the usual kind of Boolean logic. Your verification methods would almost all be unusable, for starters.

[r-transpose-p.livejournal.com]

Okay, there's a branch of logic that assume the law of the excluded middle is "not true" which is distinct from assuming it to be "false"

intuitionist logic

"/forall A. (A ^ \not A)" is referred to, btw, as "the law of the excluded middle".

[finagler.livejournal.com]

Of course, (P && ^P) is automatically a false statement, so you can simplify it as:

• (P && ^P) => false => Q (can't have both P && ^P, and false implies anything)
• (P && ^P) => true (initial assumption)
• ergo Q (Quod Est Demonstratum, cogito ergo sum)

At first glance it would seem the problem is with (P && ^P) being both true and false, but that's not really the case. The best way to see why is with a concrete example: Say P is the statement "this logical argument is valid" and Q is the statement "Noah's boolean-logic skills aren't worth a load of dingo's kidneys." Put formally:

(logic-valid && logic-invalid) ==> (Noah's logic sux. Fin rulez.)

We also know the following:

1. (valid argument) ==> (valid result) (obvious)
2. (invalid argument) ==> (invalid result) (negation of #1)
3. (unskilled logician) ==> (produces bad argument) (by definition and by union bylaws)
4. (skilled logician) ==> (produces good argument) (ibid, ob. cit., and ditto)

Now if we assume Noah's logic is valid we have the following:

• (logic-valid && logic-invalid) ==> (Noah's ski11z are n0t 1337) (assumed)
• (logic-valid && logic-invalid) ==> (logic-invalid) (from #3)

Contrawise, if we assume Noah's logic is invalid we have:

• (logic-invalid) ==> (still no love for Noah) (combo of #3 and #4)
• (still no love for Noah) ==> (correct result from Noah's statement) (by original definition)
• (correct result) ==> (Noah R0x0rs!) (combo of #3 and #4)
• (Noah R0x0rs!) ==> (logic-valid) (#4)

Thus we have (logic-invalid) <==> (logic-valid), and thus that the logic is always both valid and invalid. Plugging back in to our original problem statement we see that (P && ^P) is not only valid statement but can even be true.

(Now if you'll excuse me, I need to go work on the new Bush tax plan.)

fin

[angelbob.livejournal.com]

Wow. You go beyond circular logic to cyclic logic. I'm in awe. It's like reclaiming Boolean logic from the accountants and making it Pagan and Hippie. Or, y'know, menstrual. Or something.

At this point I find myself imagining when your Boolean equations get PMS, and I think it's time to find something else to think about :-)