Ma’ruza 24: Rekrusiv to‘plam. Rekrusiv sanaluvchi to‘plam. Post teoremasi

5-teorema.Har qanday cheksiz rekursiv sanaluvchi to`plam cheksiz rekursiv qism to`plamiga ega. (84- bet)

Isbot. cheksiz rekursiv sanaluvchi to`plam bo`lsin.

sxema yordamida berilgan funksiyani qaraylik. Bu funksiyaning qiymatlari to`plami qandaydir B to`plamdan iborat bo`lib, uni o`sib borish tartibida sanab chiqadi. Oldingi teoremaga asosan B cheksiz va rekursiv to`plamdir. ekanligi funksiyaning aniqlanishidan kelib chiqadi.

Asosiy darsliklar va o’quv qo’llanmalar
1. Kenneth H. Rosen, Discrete mathematics and its applications, 7-edition, The McGraw-Hill Companies, 2012. (888-988 betlar)

2.Rodjers H. Teoriya rekursivnih funktsiy I effektivnaya vichislimost. Moskva.

,,Mir”-1972.

3.Lavrov I.A., Maksimova L.L. Zadachi po teorii mnojestv, matematicheskoy logike i teorii algoritmov. M. «Nauka» 1995