Re: Is Cantor's Diagonal Proof Impredicative?

On Jul 7, 2:20 pm, Herman Jurjus <hjur...@xxxxxxxxx> wrote:
PiperAlpha167 wrote:
On Jul 1, 10:09 am, LauLuna <laureanol...@xxxxxxxx> wrote:
A definition is called 'impredicative' iff it defines an object x by
reference to a set of which x is a member.

A proof is impredicative iff it involves an impredicative definition.

Cantor's theorem says that for all sets S there is no one-one function
from S to P(S), the set of all subsets of S. Cantor's diagonal proof
is a reductio that goes as follows:

Suppose there is a one-one function f:S -> P(S). Consider the set of
all members x of S such that ~xef(x). Call it D. D has to be in the
range of f; so there is a member d of S such that f(d)=D. Then deD <->
~deD.Q.E.D.

The definition of D involves f, which involves P(S), of which D is a
member if D exists. The keystone of the proof is that if f exists,
then D exists. But D seems to be impredicatively defined. If we ban
impredicative definitions, the proof fails.

Is that right? No predicativist accepts the diagonal proof? Are there
nuances as to what impredicative proofs are to be accepted according
to different predicativist stances?

Thanks

Based on your definitions, D is an impredicatively defined set.
If I chose to rule out all impredicative definitions, which would in
effect rule out impredicative proofs,
then I'd be forced to reject this particular proof of Cantor's
theorem.

The proof uses the diagonal method.  So this "diagonal proof" is not
acceptable.  But it's just one case.
I'd say other proofs based on the diagonal method would have to be
examined for acceptability on a case by case basis.

Can you give an alternative proof that according to you is not
impredicative?

--
Cheers,
Herman Jurjus- Hide quoted text -

- Show quoted text -

No, I can't.

But I have no problem with impredicative definitions unless they are
really circular. Many of them are not circular, as I see it, e.g. the
l.u.b. Concretely, Cantor's diagonal method seems OK to me.

Does any non diagonal proof of Cantor's general theorem exist?

Regards
.

Relevant Pages

  • Re: Is Cantors Diagonal Proof Impredicative?
    ... reference to a set of which x is a member. ... impredicative definitions, the proof fails. ... No predicativist accepts the diagonal proof? ... examined for acceptability on a case by case basis. ...
    (sci.logic)
  • Re: Is Cantors Diagonal Proof Impredicative?
    ... reference to a set of which x is a member. ... impredicative definitions, the proof fails. ... examined for acceptability on a case by case basis. ... case of a diagonal proof that happens to be an impredicative proof ...
    (sci.logic)
  • Re: Is Cantors Diagonal Proof Impredicative?
    ... reference to a set of which x is a member. ... impredicative definitions, the proof fails. ... examined for acceptability on a case by case basis. ... case of a diagonal proof that happens to be an impredicative proof ...
    (sci.logic)
  • Re: Is Cantors Diagonal Proof Impredicative?
    ... reference to a set of which x is a member. ... impredicative definitions, the proof fails. ... No predicativist accepts the diagonal proof? ... examined for acceptability on a case by case basis. ...
    (sci.logic)
  • Re: Is Cantors Diagonal Proof Impredicative?
    ... reference to a set of which x is a member. ... A proof is impredicative iff it involves an impredicative definition. ... No predicativist accepts the diagonal proof? ... to different predicativist stances? ...
    (sci.logic)