Re: Question about proof by contradiction

In article <1aad89d1-c21b-4e12-bbec-d7f19b34f74a@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<goodchild.trevor@xxxxxxxxx> wrote:
On Mar 9, 3:49 pm, magi...@xxxxxxxxxxxxxxxxx (Arturo Magidin) wrote:

"Actually", the mistake is not the decision that "sets should be
defined using predicates". Rather, the mistake is the assumption that
every predicate will define a set.

Are you seriously attacking my English here?

No. I am saying that what you said was not what I said. If it turns
out, as you say below, that what I say is what you meant to say, then
be aware that you did NOT say what you meant to say.

I mean, the language I
used isn't even precise enough to determine that I'm wrong! :)
Yes, you and I are in agreement about what the mistake is. What you
say is exactly what I meant.

That is not what you said, though.

What you said was that if you give a definition of a set, then this
definition must be in the form of a predicate. That is,

D--> P

where D is "this is a definition of a set" and P is "it is in the form
of a predicate.

The actual issue, however, is the assumption that P-->D holds: that if
you give a predicate, then this gives a set.

So what you asserted in words was the implication going the WRONG
way. If you mean to give the implication I stated, then it was not
just a matter of not being "precise enough": it was a matter of being
flat wrong! If we are going to communicate successfully, I can't be
required to guess what you meant, I can only go by what you said.


Proof by contradiction can be formalized as

(P -> (A and not(A))) -> not(P).

What you have here, however, is an instance of

(A and not(A)) -> B.

Which is something else.

Ok, you're right - maybe I need to be more explicit (and more
careful).

The proof in question, in fact, does not even use proof by
contradiction. It has the form

(P -> not(P)) -> not(P).

This is not a proof by contradiction.

You MAY be using the excluded middle, if you are using

not(not(A)) -> A

as well, which may be the case if your proposition P is of the form
"not(A)" and the conclusion you want is of the form A. Neither of
these, however, constitutes a proof by contradiction.

In any case, the issue is not whether a proof by contradiction is a
"valid method of proof". The problem you are finding resides not in
the "valid" methods of proof, but in your axioms. Even if you throw
away the underlying rules of inference and propositional logic that
make proof by contradiction valid, from the fact that you have
inconsistent axioms you can still derive anything. So you still have
your index finger pointing to the wrong thing when you focus on the
"methods of proof".

What you seem to be concerned about is whether a system is consistent
or not; that question is of course generally hard for non-trivial
systems. On the one hand, we know that a system is consistent if and
only if it has a model; but finding a model may not be an easy (or
even possible, in the case of infinite theories) matter. Thus, we know
the theory of groups is consistent because we have a model. And we
know that if Euclidean geometry is consistent then so are spherical
and parabolic geometries. But we do not know if ZFC is consistent.

If your questions are running more towards the philosophical issues of
why we choose one or another system or rules, I'll say that in general
we pick them for the same reason we do most of everything: it seems
like a good idea at the time. And for most of the systems we do use,
because they prove useful, fruitful, or interesting. Beyond that, I
will beg off and quote, with tongue firmly in cheek, Henri Lebesgue:
"In my opinion, in so far as a mathematician is doing mathematics he
should not concern himself with questions of philosophy; an opinion,
moreover, that has been forcefully expressed to me by many
philosophers."

Let me try again by saying that P is the statement "X does
not contain X" and A is also the statement "X does not contain X."
Then the following statements are true:

I. P -> A
II. P-> not(A)

(I) follows trivially since P and A are the same statement. (II)
follows by simply applying the definition of X: since X does not
contain X, X satisfies the predicate for X and hence X contains X.
Thus I have shown

P -> A and not(A),

You do not need that; the proposition

[P -> not(P)] -> not(P)

is a tautology of propositional logic. You never need to invoke proof
by contradiction.

But that is not really important.

hence not(P) holds, assuming that proof by contradiction is valid in
our system. As you mentioned, P also holds, which is not surprising
since the system is inconsistent. Certainly I agree that both
statements are theorems in the given system. But the fact that both
of these statements are theorems violates something that I'd *like* to
be true, which is the law of the excluded middle. This situation is
unsettling to me because it's not immediately obvious that the law of
the excluded middle can be violated in this system.

The law of the excluded middle is NOT violated in this system. The law
of the excluded middle states that A or Not(A) is true for every
A. This is still true in the system.

What you are really violating is the CONSISTENCY, which is that for
every A, "A AND not(A)" is not true in the system. But this is ->not<-
the law of the excluded middle! The law of the excluded middle (also
known as the law of "the excluded third") is that given any
proposition, at least one of the two possibilities of A and not(A)
must be true, and there is no third possibility.

It may seem like they are related (via de Morgan's laws), since

not( A and not(A) ) = not(A) or A

but in fact, what de Morgan's laws say is that

not( A and not(A)) = not(A) or not(not(A)).

To go from that to the usual excluded middle you need to go from
not(not(A)) to A; and that is exactly the law of the excluded middle
in a different guise.


(In fact, it took
Bertrand Russell until 1901 to figure it out!)

What Bertrand Russell figured out was that unrestricted comprehension
(every predicate defines a set) leads to an inconsistent
system. Nothing to do with the law of the excluded middle.

Perhaps my question should be restated as: how do I determine whether
the law of the excluded middle can be violated within a given
axiomatic system?

You are still asking the wrong question. The law of the excluded
middle is not violated in this system.

Your focus on the rules of inference or the underlying logical axioms
seems to be misguided; I think you really want to wonder about the
consistency of the axioms.

As to the law of the excluded middle, it is "violated" (in the sense
of not being true) in all sorts of circumstances, e.g. in trivalue
logic, or in intuitionistic logic. You can tell because it is not in
the included logical axioms and valid rules of inference.

(Sorry if you see a different reply; I've canceled it).


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org



.

Relevant Pages

  • Re: Question about proof by contradiction
    ... definition must be in the form of a predicate. ... You MAY be using the excluded middle, ... of these statements are theorems violates something that I'd *like* to ... which is the law of the excluded middle. ...
    (sci.math)
  • Re: Question about proof by contradiction
    ... you and I are in agreement about what the mistake is. ... X satisfies the predicate for X and hence X contains X. ... which is the law of the excluded middle. ... the excluded middle can be violated in this system. ...
    (sci.math)
  • Re: .99999... still=/= 1
    ... It violates the law of the excluded middle. ... Bob Kolker ...
    (sci.math)
  • Re: .99999... still=/= 1
    ... It violates the law of the excluded middle. ... >>Bob Kolker ...
    (sci.math)
  • Re: Confused about Intuitionistic provability
    ... |> in all models is equivalent to the law of excluded middle. ... Taking FOL to be classical FOL, ... |> sentences holding in all Kripke models and the set of validities ...
    (sci.logic)