Егер А жиыны натурал сандар жиынымен тең қуатты болса, оны саналымды жиын деп атаймыз. Белгiлеуi: |A| = w.
Жоғарыдағы анықтама бойынша, егер А жиыны саналымды болса, оның элементтерiн натурал сандар арқылы нөмiрлеуге болады. Яғни символды түрде А={}.
Бүтiн сандар жиыны Z және жұп натурал сандар жиыны 2N={0,2,4,…} саналымды жиындар мысалдары болады. Төмендегi теорема саналымды жиындардың көп қолданылатын қарапайым қасиеттерiн жинақтайды.
Теорема 1.6 (Саналымды жиынның қасиеттері туралы)
- Саналымды жиынның кез келген iшкi жиыны саналымды немесе ақырлы жиын болады.
- Кез келген ақырсыз жиынның саналымды iшкi жиыны болады.
- Саналымды жиындардың қиылысуы саналымды немесе ақырлы жиын болады. Саналымды жиындардың саналымды бiрiгуi де саналымды жиын болады.
Дәлелдеуi. 1) A = {a0, a1, a3, …} саналымды жиынының қандай да бір ішкі жиыны В-ны қарастырайық.А жиынынан В жиынына жатпайтын элементтерді алып тастасақ, қалған тізбек ақырлы немесе ақырсыз болады. Ол ақырлы болса, онда теореманың тұжырымы бірден орындалады. Ал қалған тізбек ақырсыз болса, ол тізбекті бірінші элементтен бастап нөмірлеуге натурал сандар жиыны толығымен жетеді және ол нөмірлеу өзара бірмәнді сәйкестік болады.
2) Енді ақырсыз А жиынын алайық. Ол бос емес жиын, яғни оның ең болмағанда бір элементі бар. Оны а0 арқылы белгілейік. Онда А ақырсыз болғандықтан А\{a0} жиыны бос емес. Ондағы қандай да бір элементті а1 арқылы белгілейміз. А ақырсыз болғандықтан, А\{a0, a1} жиыны бос емес. Бұл жиыннан а3 элементін аламыз және т.с.с. Дәл осылай кез келген iÎN үшін А\{a0, a1, …, ai} жиыны да бос емес, яғни ai+1ÎA элементін таңдап алуға болады. Осы тәртіппен құрылған ақырсыз {a0, a1, а3, …} жиыны саналымды ақырсыз жиын.
3) Енді саналымды жиындардың саналымды (*) A1, A2, A3,… тізбегін қарастырайық. Кез келген iÎN үшін Ai жиынын ai0, ai1, ai2, …элементтерінен тұрады деп есептейік. Онда жоғарыдағы жиындардың элементтерін төмендегі кестеге топтастыра аламыз.
a00, a01, a02, a03, …
a10, a11, a12, a13, …
a20, a21, a22, a23, …
a30, a31, a32, a33, …
Саналымды жиындардың қиылысуы ондағы әр жиынның ішкі жиыны болғандықтан, ол ақырлы жиын немесе 1-ші пункт бойынша саналымды. Енді саналымды жиындардың бірігуі де саналымды болатынын көрсетейік.
Егер бұл кестедегі элементтерді диагоналдық әдіспен төмендегідей тізбек
a00, a01, a10, a20, a11, a02, a03, a12, a21, a30, … (1)
түрінде жазсақ, ондағы элементтерден құрылған жиынның саналымды болатыны оның құрылу тәсілінен айқын. Егер (*) тізбегіндегі жиындар қиылыспайтын болса, онда (1) тізбегіндегі элементтер жиыны (*) тізбегіндегі жиындардың бірігуін береді. Ал жоғарыдағы жиындарының кейбіреулері қиылысқан жағдайда, олардың бірігуінен (1) тізбектегі қайталанатын элементтердің бірін ғана қалдырып, қалғандарын алып тастау арқылы келтірілген жиындардың бірігуін аламыз. Теорема дәлелденді.
Ендi жоғарыдағы теореманың тұжырымдарын ескере отырып, төмендегi жиындардың саналымды жиындар болатынына оңай көз жеткiзуiмiзге болады.
Мысалдар.
- Q = – рационал сандар жиыны саналымды жиын болады. Бұл жиындағы өзара тең бөлшектерді бір элемент деп есептейміз. Онда бұл жиынды саналымды жиындардың саналымды бiрiгуiнен тұратын жиын деп есептеуiмiзге болады, өйткенi әрбiр таңдалған kÎN (k¹0) үшiн келесі қысқармайтын бөлшектер жиындарын Qk= арқылы белгілесек, онда Q саналымды жиындардың саналымды бірігуі болады . Яғни рационал сандар жиыны саналымды жиын болады.
- Nm арқылы натурал сандардың m элементтен тұратын барлық реттелген тізбектер жиынын (m-дiктер жиыны) белгiлесек , онда Nm саналымды жиын болады. Бұл тұжырымның дұрыстығын жоғарыдағыдай жолмен немесе берiлген жиын мен натурал сандар жиынының арасында өзара әрмәнді сәйкестiктi тiкелей орнату арқылы көрсете аламыз. Бұл сәйкестiктi тағайындайтын өрнекті n =2 үшiн келтiрейiк. Іздеген сәйкестiгіміз кез келген x,yÎN элементтерi үшiн натурал сандар парынанатурал санын сәйкес қояды және с :N2®Nсәйкестiгi өзара әрмәнді сәйкестiк болады. Ендеше бұл жиындар теңқуатты .
- Кез келген саналымды A жиынының ақырлы тiзбектерiнен тұратын жиын саналымды жиын болады. Ол жиынды A<w арқылы белгiлеймiз. Мысалы, қазақ тiлiнің алфавитінде жазылған барлық сөздер немесе барлық компьютерлiк программалар жиындары саналымды жиындар мысалы болады.
Біз бұрын жиындар қуатын салыстыру реттік қатынас болатынын айтқанбыз (реттік қатынастың дәл анықтамасы кейінірек беріледі). Төмендегi теорема аталған рет бойынша саналымды жиындардың қуаты барлық ақырсыз жиындардың қуаттарының iшiндегi “ең кiшiсi“ болатынын көрсетедi.
Теорема 1.7 Егер A жиыны ақырсыз жиын, ал B жиыны саналымды болса, онда AÈB жиыны A жиынымен тең қуатты болады.
Дәлелдеуi. Алдымен AÇB = Æ деп есептейiк. R жиыны A жиынының қандай да бiр саналымды iшкi жиыны, ал Q оның қалған элементтерiнен тұратын iшкi жиын болсын. Онда A=RÈQ және R ÇQ =Æ болады. Сонымен бірге B, R, Q жиындары өзара қиылыспайтын жиындар болады. БiзгеBÈR ÈQ жиыны мен R ÈQ жиындары тең қуатты болатынын көрсетсек жеткілікті. Ал BÈR жиыны саналымды, өйткені ол саналымды жиындардың бірігуінен тұрады. Демек, ол саналымды R жиынымен тең қуатты болады. Онда B ÈR È Q және RÈQ жиындары да тең қуатты, яғни AÈB және A жиындары тең қуатты жиындар. Енді AÇB =C ¹ Æ болған жағдайда, B\Х және A\Х жиындары қиылыспайтын жиындар. Демек, (АÈB)\Х және A\Х жиындары жоғарыдағы жағдайға сай, сондықтан ол жағдайды дәлелдеуіміз бойынша тең қуатты жиындар болады. Онда келесі АÈB=((АÈB)\Х)ÈХ жиыны мен A=(A\Х)ÈC жиындары да тең қуатты болатыны түсінікті. Біздің де дәлелдемегіміз осы еді. Теорема дәлелденді.