Path: utzoo!mnetor!uunet!mcvax!enea!ttds!draken!kth!sics!torkel
From: torkel@sics.se (Torkel Franzen)
Newsgroups: sci.philosophy.tech
Subject: Re: Classifying the Axiom of Choice
Message-ID: <1787@sics.se>
Date: 4 Mar 88 01:14:51 GMT
References: <8802251655.AA06216@duchamps.ads.arpa> <9759@shemp.CS.UCLA.EDU>
Reply-To: torkel@sics.se (Torkel Franzen)
Organization: Swedish Institute of Computer Science, Kista
Lines: 47

In article <9759@shemp.CS.UCLA.EDU> hbe@math.ucla.edu (H. Enderton) writes:
>
>For us to *know* a truth of arithmetic, we'll need to see some
>effectively verifiable supporting argument--a proof.  If the set
>of acceptable proofs is decidable (or even r.e.), then the set
>of provable statements is r.e.  Here we are considering not simply
>proofs according to some fixed rules, but arguments that could
>*ever* be accepted (in theory) by human mathematicians.  Even so,
>this still seems to lead to an r.e. set.

  It makes little sense to say or suppose that "the set of acceptable
proofs" is or is not decidable or r.e., for there is no such set. The same is
true of "the set of provable statements". "Acceptable proof" is
not a concept with a determinate extension, any more than "definable
set". (As opposed to "proof in the formal system S", "definable in the
formal language L".)

  The idea expressed in the quoted passage crops up here and there in the
philosophical literature. Thus e.g. Putnam:

      ...the statements that can be proved from axioms which are 
      evident to us can only be a recursively enumerable set
      (unless an infinite number of irreducibly different
      principles are at least potentially evident to the human
      mind, a supposition I find quite incredible).

Why are such arguments inconclusive? Well, first, if a principle is not
formal, its consequences do not form a recursively enumerable set. 
Informal principles have no definite set of consequences at all, but
only applications (formal principles among them) which are more or less
direct, far-fetched, imaginative, convincing, etc. Mach's principle and
the set-theoretic reflection principle ("anything true in the universe is
true in some set") are examples of such informal principles. In the same
vein one may object that there is no definite number at all of principles
potentially evident to the human mind, any more than there is a definite
number of potential scientific theories or works of art. Finally, it
seems only too likely that any principle at all is potentially
a c c e p t a b l e to the human mind. The distinction between what is
evident and what is merely accepted is dubious when applied to 
hypothetical principles. 
  
  It is of course possible to take the view that there nevertheless i s
a determinate concept of "proof", "valid argument", "conclusive
reasoning" in terms of which it makes good sense to suppose that 
"the set of provable statements" is or is not recursively enumerable.
This very problematic view is held by some in the philosophy of
mathematics.