Klines O - Kleenes O - Wikipedia

Yilda to'plam nazariyasi va hisoblash nazariyasi, Kleen "s ning kanonik qismidir natural sonlar sifatida qaralganda tartibli yozuvlar. U o'z ichiga oladi tartibli yozuvlar har bir kishi uchun rekursiv tartib, ya'ni quyida joylashgan tartib qoidalari Cherkov-Kleene tartibli, . Beri elementlarining hisoblash tartibli tizimida ifodalanmaydigan birinchi tartibdir kanonik tartibli belgilar sifatida qaralishi mumkin.

Kleene (1938) barcha rekursiv ordinallar uchun yozuvlar tizimini tavsifladi (ulardan kam bo'lganlar) Cherkov-Kleene tartibli ). Buning pastki qismidan foydalaniladi natural sonlar belgilarning cheklangan satrlari o'rniga. Afsuski, umuman yo'q samarali qandaydir tabiiy son tartibni anglatadimi yoki ikkita raqam bir xil tartibni anglatadimi, buni aniqlash usuli. Biroq, tartib summasi, mahsulot va quvvatni ifodalovchi yozuvlarni samarali ravishda topish mumkin (qarang tartibli arifmetik ) Kleenning har qanday ikkita belgisidan ; va tartib uchun har qanday yozuv berilgan bo'lsa, u erda mavjud rekursiv ravishda sanab o'tiladigan to'plam har bir kichik tartib uchun bitta elementni o'z ichiga olgan va samarali tartiblangan yozuvlar.

Kleinniki

Kleenning tartibli notatsiyalar tizimining asosiy g'oyasi - tartibli tartiblarni samarali tarzda yaratishdir. A'zolar uchun ning , buning uchun tartib bu yozuv . va (a qisman buyurtma berish Kleennikidan ) quyidagilar bajariladigan eng kichik to'plamlardir.

  • Natural 0 raqami Kleennikiga tegishli va .
  • Agar Klenga tegishli va , keyin Klenga tegishli va va .
  • Aytaylik bo'ladi -chi qisman rekursiv funktsiya. Agar jami bo'lib, oralig'i ichida va har bir tabiiy son uchun , bizda ... bor , keyin Klenga tegishli , har biriga va , ya'ni tartib sonining chegarasi uchun yozuvdir qayerda har bir tabiiy son uchun .
  • va nazarda tutmoq (bu buni kafolatlaydi o'tish davri.)

Ushbu ta'rif afzalliklarga ega, chunki berilgan tartibning o'tmishdoshlarini rekursiv ravishda sanab o'tish mumkin (garchi buyurtma berish) va yozuvlar pastga qarab yopilganligi, ya'ni agar uchun yozuv mavjud bo'lsa va keyin uchun yozuv mavjud .

Ning asosiy xususiyatlari

  • Agar va va keyin ; ammo aksincha, ushlab turilmasligi mumkin.
  • daraxt tuzilishini keltirib chiqaradi , shuning uchun bu asosli.
  • faqat chegara tartibidagi filiallar; va har bir chegara tartibli belgisida, cheksiz tarvaqaylab ketgan.
  • Har bir rekursiv funktsiya juda ko'p indekslarga ega bo'lganligi sababli, har bir cheksiz tartib ko'p sonli yozuvlarni oladi; cheklangan tartiblar noyob yozuvlarga ega, odatda belgilanadi .
  • Nota olmagan birinchi tartib, deyiladi Cherkov-Kleene tartibli va bilan belgilanadi . Rekursiv funktsiyalar soni juda ko'p bo'lgani uchun, tartibli aniq hisoblanishi mumkin.
  • Kleinning yozuvlari bo'lgan ordinallar aynan shunday rekursiv tartiblar. (Har bir rekursiv tartibning yozuvga ega bo'lishi ushbu tartibli notalar tizimining voris va samarali chegaralar ostida yopilishidan kelib chiqadi.)
  • emas rekursiv ravishda sanab o'tish mumkin, lekin bunga mos keladigan rekursiv ravishda sanab o'tiladigan munosabatlar mavjud aniq a'zolariga .
  • Har qanday belgi uchun , to'plam Quyidagi yozuvlar rekursiv ravishda sanab o'tiladi. Biroq, Kleeniki , umuman olganda, shunday bo'ladi (qarang analitik ierarxiya ).
  • Aslini olib qaraganda, bu - to'liq va har biri pastki qismi samarali ravishda bog'langan (Spector natijasi).
  • tartibli belgilarning universal tizimi bo'lib, unda har qanday aniq tartibli belgi to'plamini unga to'g'ri xaritada tushirish mumkin. Aniqrog'i, rekursiv funktsiya mavjud agar shunday bo'lsa bu rekursiv yaxshi buyurtma uchun indeks, keyin a'zosi va to'plamning boshlang'ich segmentiga tartib-izomorfikdir .
  • Rekursiv funktsiya mavjud , bu, a'zolari uchun , tartib qo'shimchasini taqlid qiladi va shunday xususiyatga ega . (Jokush)

Yo'llarning xususiyatlari

Yo'l pastki qismdir ning bu butunlay buyurtma qilingan va o'tmishdoshlar ostida yopiladi, ya'ni agar yo'lning a'zosi va keyin ham a'zosi . Yo'l ning elementi bo'lmasa maksimal bo'ladi yuqoridagi (ma'nosida ) ning har bir a'zosi , aks holda maksimal emas.

  • Yo'l va agar shunday bo'lsa maksimal emas rekursiv ravishda sanab o'tiladi (r.e.). Yuqoridagi so'zlar bilan har bir element ning maksimal bo'lmagan yo'lni belgilaydi ; va har bir maksimal bo'lmagan yo'l shu qadar aniqlangan.
  • Lar bor maksimal yo'llar ; chunki ular maksimal, ular noaniq.
  • Aslida bor maksimal yo'llar ichida uzunlik . (Krossli, Shyutte)
  • Har bir nolga teng bo'lmagan tartib uchun , lar bor ichida maksimal yo'llar uzunlik . (Aczel)
  • Bundan tashqari, agar uzunligi bo'lgan yo'l emas ning ko'paytmasi keyin maksimal emas. (Aczel)
  • Har bir r.e. daraja , a'zosi bor ning shunday yo'l ko'p darajali darajaga ega . Aslida, har bir rekursiv tartib uchun , yozuv bilan mavjud . (Jokush)
  • Mavjud orqali yo'llar qaysiki . Yagona aks ettirishni takrorlashga asoslangan rekursiv ravishda sanab o'tiladigan nazariyalarning rivojlanishini hisobga olgan holda, har bir bunday yo'l haqiqat to'plamiga nisbatan to'liq emas jumlalar. (Feferman & Spector)
  • Mavjud orqali yo'llar har bir boshlang'ich segmenti shunchaki r.e. emas, balki rekursivdir. (Jokush)
  • Boshqa turli yo'llar ularning har biri o'ziga xos kamaytirilish xususiyatlariga ega ekanligi ko'rsatilgan. (Quyidagi ma'lumotlarga qarang)

Shuningdek qarang

Adabiyotlar

  • Cherkov, Alonzo (1938), "Ikkinchi raqamli konstruktiv sinf", Buqa. Amer. Matematika. Soc., 44 (4): 224–232, doi:10.1090 / S0002-9904-1938-06720-1
  • Kleene, S. C. (1938), "Oddiy sonlar uchun yozuvlar to'g'risida", Symbolic Logic jurnali, Symbolic Logic assotsiatsiyasi, 3 (4): 150–155, doi:10.2307/2267778, JSTOR  2267778
  • Rojers, Xartli (1987) [1967], Rekursiv funktsiyalar nazariyasi va samarali hisoblash, MITning dastlabki qog'ozli nashri, ISBN  978-0-262-68052-3
  • Feferman, Sulaymon; Spector, Clifford (1962), "Nazariyalar progresiyalaridagi yo'llarning to'liqsizligi", Symbolic Logic jurnali, 27 (4): 383–390, doi:10.2307/2964544