5. Саналмайтын жиындар
R
жиынын қарастырайық.
Оны N
жиынымен салыстырайық.
Nболатындығы
айқын. Расында да, [0;1]
кесіндісінің құрамында
саналымды
ішкі жиындар бар, онда ол санаымды дерлік
болады. [0;1] және N
жиындары тең қуатты жиын емес екендігін
көрсетейік,
.
Теорема. [0;1] кесіндісінің нүктелер жиыны саналымды емес.
Теореманы кері жору әдісімен
дәлелдейік. 
Айталық
[0;1] жиыны саналымды болсын, яғни N-нің
[0;1]-ге биекциясы бар,және кесіндінің
әрбір элементіне бір нөмірді тағайындауға
болады:
N}.
Каждый элемент отрезка [0;1] кесіндісінің
әрбір элементі ақырсыз ондық бөлшек
түрінде келтіріледі
,
мұндағы
–
i-ші
элементтің j-ші
ондық цифры.
N
барлық элементтерін нөмірлерінің өсу
реті бойынша жазамыз. [0;1]
кесіндісіне тиісті, бірақ бірде бір
нөмірленген
N
элементтерге
сәйкес келмейтін b
элементі табылатындығын
көрсетейік. Осындай
элементтерді құру әдісі Кантордың
диагональды процедурасы деп аталады
және оның негізіне мынау жатады. b
элементін ақырсыз ондық бөлшек түрінде
келтірейік
,
мұндағы
–
i-ші
ондық сан.
ретінде
сәйкес келмейтін кез келген санды
аламыз,
–
сәйкес келмейтін кез келген сан, ... ,
кез келген
N
(рис. 1.24). Осындай жолмен құрылған b
элементі [0;1] кесіндісіне тиісті болады,
бірақ әрбір нөмірленген
элементінен ең болмағанда бір сан
бойынша ерекшеленеді. Бұдан,
N
[0;1] биекциясы бар болады деген тұжырымымыз
қате және [0;1] жиыны саналымды емес.
Сонымен, біз [0;1]>Nболатындығын көрсеттік, яғни [0;1] кесіндісі тиісті болатын эквиваленттік класс қуаттар қатарында 0 саналымды жиындар классының оң жағында орналасқан (1.23 сурет). Бұл классты деп белгілейік (индекссіз). Осы классқа тиісті жиынды саналмайтын немесе континуум қуатты жиындар деп атайды. (континуум – үзіліссіз). Осы классқа (0;1) интервалы және R нақты сандар жиыны, және жазықтықтағы дөңгелетің нүктелер жиыны жатады.
Мысал. R
жиыны континуум қуатты,
себебі ол [0;1] кесіндісіне теңқуатты.
Расында да, Кантор-Бернштейн теоремасы
бойынша (1.4.4 қараңыз) [0;1]=
(0;1).
Биекцию интервала (0;1) интервалының R
жиынына биекциясын
күрделі функцияныың көмегімен беруге
болады, мұндағы
түріне ие болады және (0;1) интервалын
интервалына бейнелейді, ал
интервалын R-ға
заңы бойынша бейнелейді.
Нәтиже
Сонымен, «қуат» түсінігін қолдана отырып, біз өзара тек қана ақырлы жиындарды емес, сонымен қатар ақырсыз жиындарды да салыстырамыз. Біз жиынның қуаты 0 болады дегеніміз, бұл натурал сандар жиыны қай классқа жатса бұл да сол эквиваленттік классқа жатады дегенді білдіреді; біз жиын континуум қуатты деп айтамыз, бұл дегеніміз ол [0;1] кесіндісі қай классқа жатса бұл да сонда жатады (кесте 1.5).
Кесте 1.5
Жиынның қуаты
-
Жиын
Эталон
Қуат
Ақырлы
{1, 2, … ,n}
n
Саналымды
N
0
Саналмайтын
[0;1]
Біз саналмайтын жиындардың қуаты саналатын жиындардыкіне қарағанда үлкен болатынын көрсеттік. Ал қуаты үлкен болатын жиындар бола ма? Бұл сұраққа төменде дәлелдеусіз берілген теорема жауап береді.
Теорема. Айталық X – ақырсыз жиын болсын. Х жиынының булеанының қуаты Х жиынының қуатынан үлкен.
Осы теореманың негізінде біз ең үлкен қуатты жиын болмайды деп тұжырымдай аламыз: әрбір Х жиыны үшін біз оның булеанын ұқра аламыз, яғни қуаты үлкен жиын. Бұл дегеніміз қуаттар қатары шексіз. (1.23 сурет)
Ұсынылған әдебиеттер:
1. Нұрсұлтанов Қ.Н., Дискретті математика және математикалық логика. – Семей 2002.
2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. –М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.
3. Смыслова З.А.. Дискретная математика (Учебное пособие), Томск, 2000.
4. Қ.Жетпісов., Математикалық логика және дискретті математика. Алматы, 2011.
5. Шапорев С.Д. Математическая логика. Курс лекций и практических заниятий.- СПБ.: БХВ-Петербург 2005. - 416стр.
6. Тишин В.В. Дискретная математика в задачах и примерах. БХВ-Петербург 2008.
Дәріс 5
Дәріс сабақтың құрылымы:
Комбинаторика
Комбинаторика есептері. Іріктеме типтері. Комбинаториканың негізгі ережелері.
Қайталамалы орналастырулар. Қайталаусыз орналастырулар
Қайталаусыз алмастырулар. Қайталаусыз алмастырулар.
Қайталаусыз алмастырулар. Қайталаусыз алмастырулар.
Теру. Қайталамалы теру
6. Ньютон биномы