Rekursiv va

4-teorema. ^A cheksiz to`plam bo`lsin. ^A rekursiv to`plam bo`lishi uchun u


_{o`sib borish tartibida rekursiv sanaluvchi to`plam bo`lishi zarur va yetarli.}

Isbot.Zarurligi: A cheksiz va rekursiv to`plam bo`lsin. funksiyasi

 _A ning harakteristik

f (0)   y _ _A ( y)_  1
f ( x  1)   y _ _A ( y)  1  ( y 


f ( x))_

Sxema yordamida hosil qilingan funksiya umumrekursiv hamda ^A to`plam bu funksiya qiymatlari to`plamidan iborat ekanligi 2-teoremadan ma‘lum. f ( x) o`suvchi funksiya ekanligi ravshandir. Demak A o`sib borish tartibida rekursiv sanaluvchi to`plamdir.

_Yetarliligi: f (x) ni A _{o`sib borish tartibida sanovchi funksiyasi deymiz. a}

_{natural sonnig A ga kirish yoki kirmasligini aniqlash uchun}
f ( x)
_{ning qiymatlarini}

_{hisoblay boshlaymiz. Bu jarayonni}
f ( x)
_{ning a dan katta qiymati paydo bo`lguncha}

_{davom ettiramiz.} f (0), f (1),..... f (x)... _{larni hisoblab, a dan katta son paydo bo`lsa}

_{a  A, paydo bo`lmasa a  A
ekanligi ayondir. Demak</sub> A <sub>to`plamning harakteristik}

funksiyasi hamma yerda aniqlangan aniqlangan funksiya bo`lib, uning qiymatlarini hisoblaydigan jarayon mavjuddir. Demak u umumrekursiv funksiya, <sup>A</sup> esa rekursiv to`plam ekan.

5-teorema.Har qanday cheksiz rekursiv sanaluvchi to`plam cheksiz rekursiv <sup>qism to`plamiga ega.</sup> ² ^{(84- bet)}
_{Isbot. A cheksiz rekursiv sanaluvchi to`plam bo`lsin.}

<sub>g (0) 


f (0)</sub>

_{g ( x  1) 
f ( y[ f ( y)  g ( x)})}

_{sxema yordamida berilgan funksiyani qaraylik. Bu funksiyaning qiymatlari to`plami}

<sub>qandaydir B to`plamdan iborat bo`lib,


g ( x)


uni o`sib borish tartibida sanab chiqadi.</sub>

Oldingi teoremaga asosan B cheksiz va rekursiv to`plamdir. B  A ekanligi ^{g ( x)}


funksiyaning aniqlanishidan kelib chiqadi.