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

2-teorema.Agar rekursiv to`plam bo`lsa u holda u rekursiv sanaluvchi to`plam bo`ladi. (82- bet)

Isbot. Mumkin bo`lgan 3ta holni qaraymiz.

a) bo`lsa teorema o`rinli ekani ma’lum

b) chekli to`plam bo`lsin. U holda bu to`plamni sanab chiquvchi funksiya

bo`ladi.

v) cheksiz to`plam ning harakteristik funksiyasi bo`lsin, u holda

yordamida aniqlangan funksiya to`plamning sanab chiquvchi funksiyasidir.

2-misol. -rekursiv sanaluvchi to`plam lekin rekursiv to`plam emas.

3-misol.

-rekursiv sanaluvchi to`plam emas. (83- bet)