Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!brahms!weemba
From: weemba@brahms.BERKELEY.EDU (Matthew P. Wiener)
Newsgroups: net.math
Subject: Re: Relative Number Theory
Message-ID: <11727@ucbvax.BERKELEY.EDU>
Date: Thu, 6-Feb-86 18:49:04 EST
Article-I.D.: ucbvax.11727
Posted: Thu Feb  6 18:49:04 1986
Date-Received: Sun, 9-Feb-86 05:44:16 EST
References: <2314@umcp-cs.UUCP> <2232@pyuxd.UUCP> <2393@umcp-cs.UUCP> <1079@mmintl.UUCP> <4516@kestrel.ARPA>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: weemba@brahms.UUCP (Matthew P. Wiener)
Organization: University of California, Berkeley
Lines: 24

In article <4516@kestrel.ARPA> ladkin@kestrel.ARPA writes:
>>The question I don't know the answer to is the following: is there any
>>closed number-theoretic formula X, such that neither X nor not X is provable
>>in the system N(a) for any computable ordinal a?  
>
>What is N(a)? It can't be Peano Arithmetic relativised to a,
>since the induction axiom is false if a isn't omega. There
>are non-standard models of PA but they're not well-founded,
>and a is supposed to be an ordinal. It is also no longer
>true that every number except 0 has a predecessor, when there
>are limit ordinals in the domain.
>If the ordinal's computable, then there's a notation for it
>embedded in PA ( a recursive function coding the well-order),
>which would mean that, whatever N(a) might be, it seems to
>have the same proof theory as N ?
>I'm running out of guesses.

My guess is that N(a) is Peano Arithmetic + induction on well-orderings of
type less than a.  The proof strength does grow (like a step function) as
you increase a among the recursive ordinals.  For example, if e=epsilon_0,
ie, the limit of w,w^w,w^w^w,w^w^w^w,... (where w=omega), then N(e) is, by
Gentzen's theorem, able to prove the consistency of PA.

ucbvax!brahms!weemba	Matthew P Wiener/UCB Math Dept/Berkeley CA 94720