Алдымен жиындар қуаттарының арасында төмендегiдей қатынас орнатайық.
Егер A жиыны B жиынының қандай да бiр iшкi жиынымен тең қуатты болса, онда A жиынының қуаты B жиынының қуатынан кiшi немесе тең деп (|A|£|B|) есептейміз. Осылай анықталған £қатынасы төмендегiдей қасиеттерге ие.
- Егер A және B жиындары тең қуатты болса, онда |A|£|B| болады. Жеке жағдайда |A|£|А.| (рефлексивтілік).
- |A|£|B| және |B|£|С| болса, онда |A|£|С| (транзитивтiлiк).
- Егер |A| £ |B| және |B| £ |A| болса, онда |A|=|B| (антисимметриялық).
Келтірілген қасиеттердiң бiрiншiсi анықтамадан тiкелей шығады. Транзитивтiлiк қасиет инъективті бейнелеулердің композициясы (бернесі) да инъективті болатындығынан шығады.
Үшінші қасиет Кантор-Бернштейн теоремасы атымен белгiлi және бұл қасиетті дәлелдеу оңай емес.
Кантор-Бернштейн теоремасының дәлелдеуi
Лемма 1.8– инъективті бейнелеу болсын. Егер– индекстік жиын және кез келгенүшінболса, онда .
Дәлелдеуі. Кез келгенэлементін алайық. Онда қандай да біртабылып,болады. Алболғандықтан,және . Онда , яғни . Кері тиістілікті дәлелдеу үшін келтірілген дәлелдеудің соңынан бастап кері қарай жүреміз.
Лемма 1.9 Егер–жиынының қандай да бірішкі жиынына биекция болса, онда кез келгенішкі жиыны үшінболатындайбиекциясы табылады.
Дәлелдеуі. , ,…, белгілеулерін енгізейік жәнежиынын қарастырайық.
- теңдігінің орындалатынын көрсетеміз.
Солдан оңға. . Ондаболғандықтан,немесеболады.болсын. ОндаЕгерболса, ондаболатындайсаны табылады. Ал(1.8-ші лемма) болғандықтан,Демек,Соныменболатынын көрсеттік.
Оңнан солға.болсын. Онданемесеболады.болса, ондажиынының анықтамасы бойыншаЕгерболса, онда . Алболғандықтан, . Сонымен . Ендеше .
- бейнелеуін келесі тәртіппен құрамыз:
Яғнибейнелеуіжиынында бірлік (тепе-тең) бейнелеу және ол жиынындабейнелеуімен бірдей болады.болғандықтан,
Алболғандықтан,жәнеинъекция себепті . Демек . Ендешеинъекция, әрі . Лемма дәлелденді.
Келесі теорема жиындар теориясының іргесін бекітетін негізгі тұжырымдардың бірі болып саналады.
Теорема 1.10 (Кантор-Бернштейн). Егержиынынанжиынының меншікті ішкі жиынына,жиынынанжиынының меншікті ішкі жиынына биекциялар табылса, ондажиынынанжиынына биекция табылады.
Дәлелдеуі. ,биекциялар жәнеболсын.композициясын қарастырайық. Мұндаболады.жәнеинъекциялар болғандықтан, олардың композициясы (бернесі)та инъекция болады. Онда 2 лемма бойынша кез келгенүшінбиекциясы табылады.деп алайық. Онда . Бұдан . Ендешеинъективті функция болғандықтан,бейнелеуіжиынынанжиынына биекция болады. Теорема дәлелденді.
Кантор-Бернштейн теоремасы жиындардың тең қуаттылығын мейлінше тиімді жолмен көрсетуге мүмкіндік береді. Мысалы, машина дөңгелегі мен кез келген шар тең қуатты болады. Өйткені кез келген шардан дөңгелек қиып алуға болады. Өз кезегінде дөңгелектен де шар қиып алуға болады. Демек, олар Кантор – Бернштейн теоремасы бойынша тең қуатты болады.
Енді қуаттары тең болмайтын жиындар болатынын көрсетуге арналған Кантордың диагоналдық тәсілімен танысайық.
Теорема 1.11 (Кантор). 0 мен 1-ден тұратын ақырсыз тiзбектер жиыны саналымсыз, яғни бұл жиын натурал сандар жиынымен тең қуатты болмайды.
Дәлелдеуi. Керi жору әдiсiн қолданамыз. Берiлген жиын саналымды деп есептейiк. Онда 0 және 1-ден тұратын барлық ақырсыз тiзбектердi натурал сандар арқылы нөмiрлеуiмiзге болады. Егер бұл тізбектерден тұратын жиын саналымды болса, ол жиынның элементтерін натурал сандар арқылы нөмірлеуге болады (кері жору!). Демек, осындай тізбектерді a0,a1,a2,… арқылы белгілеп, олардан келесі ақырсыз саналымды ( өлшемді) кесте құруға болады.
a0= a00a01a02…
a1= a10 a11a12…
a2 = a20 a21a22…
- мұндағы aij элементі i-шi тiзбектiң j-шi мүшесiн бiлдiредi.
Ендi a00, a11, a22, … диогоналдық элементтерден тұратын a=a00a11a22… тiзбегi бойынша, bi = 1–aii тәртiбiмен b = b0b1b2… тiзбегiн құрайық. Мұндағы bi ¹ aii, ендеше b тiзбегi кестедегi кез келгенai тiзбегiнен i-шi элементi бойынша өзге болады, яғни bi¹ai, немесе b тiзбегi жоғарыдағы кестеде кездеспейдi. Демек 0 мен 1-ден тұратын ақырсыз тiзбектер жиынын саналымды кесте арқылы бере алмаймыз. Бұл бiздiң жорумызға қайшы. Теорема дәлелдендi.
Теорема1.12 (Кантордың жалпы теоремасы). Ешбiр X жиыны өзiнiң барлықiшкi жиындарының жиынымен тең қуатты болмайды.
Дәлелдеуi. Р(X) арқылы X жиынының барлық iшкi жиындарының жиынын белгілейік. Керi жоримыз. Кері жорып, қандай да бір j бейнелеуi X және Р(X) жиындарының арасындағы өзара әрмәнді сәйкестiк болсын дейік. Z={аÎC½ аÏj(а) } жиыны X жиынының өз бейнесiне тиiстi емес элементтерден тұратын iшкi жиыны болсын. Онда Z жиыны j бейнелеуi бойынша, X жиынының ешбiр элементiнiң бейнесі болмайтынын көрсетейiк. Егер олай болмаса, j(z) = Z болатындай zÎX элементi табылады. Онда zÎZ Û zÏj(z) Û zÏZ.
(Бiрiншi Û парапарлық Z жиынын анықтау жолынан, ал екiншi Û парапарлық j(z)=Z шартынан шығады). Осы қайшылық, жоғарыдағы жоруымыздың қателігiн, яғни X және Р(X) жиындарының арасында еш уақытта өзара әрмәнді сәйкестiк болмайтынын көрсетедi. Теорема дәлелдендi.