ordinal

a

r

Xi

v

:

m

a

t

h

/

0

3

0

7

0

9

0

v

1

[

m

a

t

h.

G

M]

8

J

u

l

2

0

0

3

KIMS-2003-07-07

DoesChurch-KleeneordinalωCK

1

exist?

HitoshiKitada

GraduateSchoolofMathematicalSciences

UniversityofTokyo

Komaba,Meguro-ku,Tokyo153-8914,Japan

e-mail:kitada@

July7,2003

Abstract:Aquestionispropodifanonrecursiveordinal,theso-calledChurch-Kleene

ordinalωCK

1

reallyexists.

WeconsiderthesystemsS(α)definedin[2].

Let˜q(α)denotetheG¨odelnumberofRosrformulaoritsnegation

A

(α)

(=A

q(α)(q(α))or¬A

q(α)(q(α))),iftheRosrformulaA

q(α)(q(α))is

well-defined.

By“recursiveordinals”wemeanthodefinedbyRogers[4].Thenthat

αisarecursiveordinalmeansthatα<ωCK

1

,whereωCK

1

istheChurch-

Kleeneordinal.

ber˜q(α)isrecursivelydefinedforcountablerecursive

ordinalsα<ωCK

1

.Here‘recursivelydefined’meansthat˜q(α)isdefined

inductivelystartingfrom0.

ginalmeaningof‘recursive’is‘inductive.’Themean-

ingoftheword‘recursive’inthefollowingistheonethatmatchesthe

spiritofKleene[3](especially,thespiritoftheinductiveconstructionof

metamathematicalpredicatesdescribedinction51of[3]).

l-definednessof˜q(0)isassuredbyRosr-G¨odeltheoremas

explainedin[2].

Wemakeaninductionhypothesisthatforeachδ<α,theG¨odelnum-

ber˜q(γ)oftheformulaA

(γ)

(=A

q(γ)(q(γ))or¬A

q(γ)(q(γ)))withγ≤δis

recursivelydefinedforγ≤δ.

1

WewanttoprovethattheG¨odelnumber˜q(γ)isrecursivelywell-defined

forγ≤α.

i)Whenα=δ+1,byinductionhypothesiswecandeterminerecursively

whetherornotagivenformulaA

r

withG¨odelnumberriqualtoone

oftheaxiomformulasA

(γ)

(γ≤δ)ofS(α).Infact,wehaveonlytoe,

forafinitenumberofγ’swith˜q(γ)≤randγ≤δ,ifwehaveA

(γ)

=A

r

ctionhypothesisthat˜q(γ)isrecursivelywell-definedfor

γ≤δ,thisisthendecidedrecursively.

ThusG¨odelpredicateA(α)(a,b)andRosrpredicateB(α)(a,c)with

superscriptαarerecursivelydefined,andhencearenumeralwiexpress-

ibleinS(α).ThentheRosrformulaA

q(α)(q(α))iswell-defined,andthe

G¨odelnumber˜q(α)ofRosrformulaoritsnegationA

(α)

(=A

q(α)(q(α))

or¬A

q(α)(q(α)))isdefi˜q(γ)isrecursivelywell-defined

forγ≤α.

ii)Ifαisacountablerecursivelimitordinal,thenthereisanincreasing

quenceofrecursiveordinalsα

n

<αsuchthat

α=

∞