Ma’ruza 3: universal funktsiyalar. Ku’ZG’almas nuqtalar. Klini va rays teoremalari rekursiv va rekursiv sanaluvchi to`plamlar reja

1-misol.

1.Toq sonlar to`plami, 3ga bo`lganda 2qoldiq beradigan natural sonlar:5,8,11,….,

barcha natural sonlar to`plami rekursiv sanab chiqiluvchi to`plamdir. Ularni mos ravishda

funksiyalar sanab chiqadi.

ham rekursiv sanab chiqiluvchi to`plamlardir ularni sanab chiquvchi funksiyalari mos ravishda

lardir.

Rekursiv sanab chiqiluvchi to`plam ta’rifidan ko`ramizki, rekursiv sanab chiqiluvchi to`plam, uni sanab chiquvchi umumrekursiv funksiyasi bo`lsa u holda bo`lib u sanoqlidir.Rekursiv sanab chiqiluvchi to`plamlarning birlashmasi va kesishmasi yana rekursiv sanab chiqiluvchi to`plam bo`ladi.

Masalan: va mos ravishda rekursiv sanab chiqiluvchi va to`plamlarning sanab chiquvchi funksiyasi bo`lsin.

funksiya ni sanab chiqadi.

Rekursiv sanab chiquvchi to`plamning to`ldiruvchisi rekursiv sanab chiqiluvchi to`plam bo`lmasligi mumkin.

Umumrekursiv funksiyalar sinfi sanoqli to`plam bo`lganligi, har bir umumrekursiv funksiya esa faqat bitta to`plamni sanab chiqa olishi sababli rekursiv sanab chiqiluvchi to`plamlar sinfi sanoqlidir. Ma’lumki barcha natural sonlar to`plamining barcha to`plamostilari sinfi sanoqsiz to`plamdir. Bu esa rekursiv sanab chiqilmaydigan to`plamlar mavjud deyishga asos bo`ladi.