Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mmintl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!linus!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem: a meaty response
Message-ID: <1139@mmintl.UUCP>
Date: Mon, 3-Feb-86 22:28:59 EST
Article-I.D.: mmintl.1139
Posted: Mon Feb  3 22:28:59 1986
Date-Received: Sun, 9-Feb-86 05:24:20 EST
References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <1070@mmintl.UUCP> <4374@kestrel.ARPA>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Distribution: net
Organization: Multimate International, E. Hartford, CT
Lines: 37
Xref: watmath net.ai:3262 net.philosophy:4108

In article <4374@kestrel.ARPA> ladkin@kestrel.ARPA writes:
>(wiener)
>> >There are problems now known which are believed forever insoluble.
>> 
>(adams)
>> There does not seem to be any way to know that a problem
>> is definitely insoluble (as distinct from undecidable in a formal system).
>
>There are theorems such as Kruskal's, the Paris-Harrington
>version of the Ramsey Theorem, and Friedman's various principles
>that are provable stronger than the generally acceptable
>principles of arithmetic, and recursive set theory. They are
>arguably consistent, since there are `proofs' of them. 
>These proofs must depend upon stronger principles than all
>mathematicians are willing to accept (e.g. intuitionists).
>If you believe these proofs, you will nevertheless be
>unable to persuade those who are sceptical of their validity,
>and furthermore, there is a proof of this fact.
>
>This point is even valid for Peano Arithmetic.
>If you believe that Peano Arithmetic is consistent, as I do,
>then there is a proof that proving the consistency of P.A.
>from elementary principles is an insoluble problem. 
>This is different from deciding the 
>consistency of P.A. If you believe Gentzen's proof, as I do,
>then the consistency is already decided.

But if you do *not* accept the postulate, that means you are in real
doubt about it.  That, in turn, means you don't know whether or not
it is undecidable.  Because if Peano Arithmetic is not consistent,
then there actually exists a counterexample, which can be demonstrated.
You can, perhaps, know that someone else's problem is unsolvable *by
them*, but you cannot know the same for yourself (for this class of
problems, at least).

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108