Ordinal va kardinallar. Kantor teoremasi. Transfinit induksiya. Maksimum prinsipi

Misol 1. Avtobusda 15 nafar yo’lovchi ketyapti. Ulardan hech bo’lmaganda 2 tasining tug’ilgan kuni bir xil oyda bo’lishi mumkinligini ko’rsating.
Yechilishi: Avtobusdagi odamlar to’plamini A , 12 ta oy nomlarini esa B

deb belgilaymiz.
f : A  B
funktsiya avtobusdagi har bir kishiga uning tug’ilgan

oyini mos qo’ysin.
A  15 ,
B  12
demak,
A  B . Dirixle printsipiga ko’ra, f

funktsiya takrorlanuvchi qiymatga ega. Bundan esa, hech bo'lmaganda 2 ta kishining tug’ilgan kuni bir xil oyda bo’lishi kelib chiqadi.
Misol 2. Agar hech bo’lmaganda 2 ta kishining familiyasi bir xil harfda boshlanib, bir xil harf bilan tugaydigan bo’lsa, telefon ma’lumotnomasiga yozilgan familiyalarning minimal soni qanday bo’ladi?
Yechilishi: A - ma’lumotnomadagi familiyalar to’plami,
B - o’zbek alifbosi 26 ta harfidan olingan harflar juftligi

to’plami.
f : A  B
bir xil familiyalarning birinchi va oxirgi harflarini mos

qo’yuvchi funktsiya. Masalan, f (Abdullayev)=(a,v).

B to’plam
26  26  676
juft harfdan iborat. Dirixle printsipiga ko’ra, agar

A  B  676 bo’lsa, familiyasi bir xil harfda boshlanib, bir xil harf bilan

tugaydigan hech bo’lmaganda 2 ta kishi topiladi. Shuning uchun telefon ma’lumotnomasi 676 tadan kam bo’lmagan familiyadan tuzilgan bo’lishi kerak.

2. To‘plamlarning quvvati va kardinal sonlar.

Har qanday ^A to‘plam uchun uning barcha qism to‘plamlari to‘plami

P(A) =2^A mavjud bo’lib, ushbu to‘plamlar oilasini tahlil qilish juda mihim ahamiyatga ega.
Teorema 1. n ta elementdan iborat X ={x₁, x₂, ..., x_n } to‘plamning barcha qism to‘plamlari to‘plami X to‘plamda aniqlangan, soni 2ⁿ ta bo‘lgan binar funktsiyalar to‘plamiga biyektiv bo‘ladi.

1.3. Akslantirishlar