Path: utzoo!news-server.csri.toronto.edu!rutgers!sun-barr!ccut!wnoc-tyo-news!ascwide!ascgw!sh8810!okilab!icot32!hitgw!harl86!kondoh
From: kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH)
Newsgroups: comp.theory
Subject: Re: dreams...
Message-ID: <1721@harl86.harl.hitachi.co.jp>
Date: 12 Mar 91 10:47:49 GMT
References: <3002@charon.cwi.nl> <1971@virgo.csl.sony.co.jp>
Organization: Advanced Research Laboratory, Hitachi, Ltd.
Lines: 36
In-reply-to: kono@csl.sony.co.jp's message of 23 Feb 91 13:07:10 GMT
Return-Receipt-To: kondoh@harl.hitachi.co.jp




In article <1971@virgo.csl.sony.co.jp> kono@csl.sony.co.jp (Shinji Kono) writes:
   >>In article <3002@charon.cwi.nl>  
   >>	     , lambert@cwi.nl (Lambert Meertens) writes 
   >>>Actually, if the P=NP? question will ever be settled, of the two possible
   >>>verdicts: a proof that P != NP, and a proof that P = NP
   >>
   >>or it may one of the independent problem, like continuum hypothesis.

No, I think it is not the case, since with 2nd-order formulation of
the mathematical induction (i.e.
    \forall X [X(0) & \forall v [X(v) -> X(s(v))] -> \forall v X(v)]
), the axiom system of Peano arithmetic is categorical (having unique
model except for non-standard models, which do not interpret \in 
(membership-predicate symbol) as the membership relation), and 
"P = NP" problem would be able to be formulated in this 2nd-order
Peano arithmetic, so that problem must be either true or false in
its unique standard model.   

(In the case of the continuum hypothesis, there are standard models
of ZF set theory in some of which the hypothesis comes true and
in others it is given falsity.)

Of course, due to the Incompleteness theorem of Godel, there are
many sentences which are independent of the categorical 2nd-order
Peano arithmetic, but in the unique standard model of the theory
can give true or false decisively to each of those sentences.

--
-- 
Hidetaka KONDOH (kondoh@harl.hitachi.co.jp)	Advanced Research Laboratory
						Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328)		Hatoyama, Saitama  350-03
Fax:   +81-492-96-6005				JAPAN