4-teorema. cheksiz to`plam bo`lsin. rekursiv to`plam bo`lishi uchun u o`sib borish tartibida rekursiv sanaluvchi to`plam bo`lishi zarur va yetarli.
Isbot.Zarurligi:cheksiz va rekursiv to`plam bo`lsin. ning harakteristik funksiyasi
Sxema yordamida hosil qilingan funksiya umumrekursiv hamda to`plam bu funksiya qiymatlari to`plamidan iborat ekanligi 2-teoremadan ma’lum.o`suvchi funksiya ekanligi ravshandir. Demak o`sib borish tartibida rekursiv sanaluvchi to`plamdir.
Yetarliligi:o`sib borish tartibida sanovchi funksiyasi deymiz.natural sonnig ga kirish yoki kirmasligini aniqlash uchun ning qiymatlarini hisoblay boshlaymiz. Bu jarayonni ning dan katta qiymati paydo bo`lguncha davom ettiramiz.larni hisoblab, dan katta son paydo bo`lsa , paydo bo`lmasa ekanligi ayondir. Demakto`plamning harakteristik funksiyasi hamma yerda aniqlangan aniqlangan funksiya bo`lib, uning qiymatlarini hisoblaydigan jarayon mavjuddir. Demak u umumrekursiv funksiya, esa rekursiv to`plam ekan.
Do'stlaringiz bilan baham: |
