Кантор – Бернштейн теоремасы - Студент үшін

Кантор – Бернштейн теоремасы - Студент үшін

Алдымен жиындар қуаттарының арасында төмендег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. теңдігінің орындалатынын көрсетеміз.

Солдан оңға. . Онда  болғандықтан,  немесе  болады.  болсын. Онда  Егер  болса, онда  болатындай  саны табылады. Ал  (1.8-ші лемма) болғандықтан,  Демек,  Сонымен  болатынын көрсеттік.

Оңнан солға.  болсын. Онда  немесе  болады.  болса, онда  жиынының анықтамасы бойынша  Егер  болса, онда . Ал  болғандықтан, . Сонымен . Ендеше .

  1. бейнелеуін келесі тәртіппен құрамыз:

Яғни  бейнелеуі  жиынында бірлік (тепе-тең) бейнелеу және ол жиынында  бейнелеуімен бірдей болады.  болғандықтан,

Ал  болғандықтан,  және  инъекция себепті . Демек . Ендеше  инъекция, әрі . Лемма дәлелденді.

Келесі теорема жиындар теориясының іргесін бекітетін негізгі тұжырымдардың бірі болып саналады.

Теорема 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= a00  a01  a02

a1= a10  a11  a12

a2 = a20  a21  a22

  • мұндағы 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.

скачать dle 12.1

Көп қаралған материалдар