Chekli to`plamlar yig`indisining Quvvati aniqlash usullari O`zbekiston respublikasi axborot texnologiyalari

Element to`plamlarvabirma-biryozishmalar
A va B to'plamlar bo'lsin .

• A to'plam B to'plamga ekvivalentA bo'ladi , agar A to'plamdan B to'plamgaikkilanishmavjudbo'lsa . Buholdabiz A \thickapprox B yozamiz .BABA≈B

  
  

• A \thickapprox B bo'lganda , A to'plami B to'plambilan birma-birmos kelishiniva A to'plami B to'plambilan bir xil kardinallikkaA≈B egaekanligini ham aytamiz .ABAB

  
  

Eslatma: Agar A BA ga ekvivalentbo'lmasa , biz A \not\thickprox B niyozamiz .BA≉B

1. Har birto'plamuchun , .AA≈A

   
   

2. va to'plamlariuchun , agar , keyin .ABA≈BB≈A

   
   

3. Barcha , va to'plamlariuchun va bo'lsa, .ABCA≈BB≈CA≈C

   
   

Preview Activity da biz ekvivalentto'plamlartushunchasinikiritdik. Ushbuta'rifningmotiviikkitato'plamda "birxilmiqdordagielementlargaega" yokiyo'qliginianiqlashningrasmiyusuligaegabo'lishedi. Bu g'oyabirto'plamdanikkinchito'plamgayakkama-yakkayozishmalar (bijection) nuqtainazaridantasvirlangan. Bu g'oyacheklanganto'plamlaruchunoddiybo'libtuyulishimumkin, lekin biz ko'ribturganimizdek, cheksizto'plamlarbilanshug'ullanganimizdabug'oyahayratlanarlioqibatlargaolibkeladi.

Oldindanko‘rishfaoliyati 9.1 teoremasida biz isbotlaganuchtaxususiyatrefleksiv, simmetrikvao‘tishmunosabatlaritushunchalarigajudao‘xshash. to'plamdagiekvivalentlikmunosabati deb hisoblamaymiz, chunkiekvivalentlikmunosabatiasosli (universal) to'plamini talab qiladi . Bundayholda, bizningelementlarimiz , va to'plamlaribo'ladivaularkeyinchalikqandaydir universal W to'plaminingkichikto'plamlaribo'lishikerak (W quvvatto'plaminingelementlari . , va to'plamlarini talab qilmaymiz9.1.2UUABCVABCbir xil universal to'plamningkichikto'plamlaribo'lsin. Shuninguchun biz to'plamlarningekvivalentligiganisbatanmunosabatatamasidanfoydalanmaymiz. Biroq, agar va to'plamlarva bo'lsa, biz ko'pincha va ekvivalentto'plamlar deb aytamiz.ABA≈BAB
5.1 - bo'limda biz to'plamdagielementlarningsonibo'lishiuchun karta( )bilanbelgilanganchekli to'plaminingkardinalligini aniqladik . Endi biz funktsiyalarvabijeksiyalarhaqidabilganimizdanso'ng, biz ushbukontseptsiyaniyanadarasmiyroqvaqat'iyroqbelgilashimizmumkin. Birinchidan, harbir gachabo'lganbarcha natural sonlarto'plamisifatida aniqlaymiz . Anavi,AAAk∈NNkk
Nk={1,2,...,k} .
Biz cheklito'plamnianiqlashuchun Preview Activity da kiritilganekvivalentto'plamlar tushunchasidanfoydalanamiz .

• A to'plami A yoki k sonimavjudbo'lganda cheklanganto'plamdir .AA=∅kA≈Nk

  
  

• To'plamcheksizto'plamdir , agar u cheklito'plambo'lmasa.

  
  

• Agar bo'lsa , to'plamningasosiyligi (yoki asosiyraqam ) deb aytamiz ) deb yozamiz .A≈NkAkkA=k

  
  

Bundantashqari, biz bo'shto'plamning kardinalligi 0 (yoki asosiyraqam0 )ekanliginiaytamizva biz yozamiz .karta(∅)=0

E'tiborbering, buta'rifgako'ra, bo'shto'plamcheklito'plamdir. Bundantashqari, harbir dagiidentifikatsiyafunksiyasibijeksiya hisoblanadivashuninguchunta'rifgako'ra kardinallikkaegacheklito'plamdir .k∈NNkNkk
to'plamigaekvivalentbo'lganharqandayto'plamcheklito'plam bilanbirxilkardinallikkaega .AA
teoremada “aniq” natijaniisbotlashuchun biz ko'pishqilgandektuyulishimumkin. Bu bo'limdagiqolgannatijalarga ham xuddishundaybo'lishimumkin, ularcheklito'plamlarhaqidaqo'shimchanatijalarberadi. Maqsadlardanbiri - cheklanganto'plamuchunkardinalliktushunchasito'plamdagielementlarsonihaqidagibizningintuitivtushunchamizgamoskelishigaishonchhosilqilishdir. Yana birmuhimmaqsad - cheksizto'plamlarga biz ilgariduchkelganimizdanko'raqat'iyroqvamatematikishlovberishuchunzaminyaratishdir. Yo'ldavomida biz cheklivacheksizto'plamlaro'rtasidagimatematikfarqniko'ramiz.
Cheklito'plamningharbirkichikto'plamichekliekanliginibildiruvchiteoremaniisbotlashuchunquyidagiikkitalemmadanfoydalaniladi.
Agar cheklito'plambo'lsava bo'lsa, u holda cheklito'plamva .Ax∉AA∪{x}karta(A∪{x})=karta(A)+1
Har bir natural son uchun , agar boʻlsa, u holda cheklitoʻplamva .mA⊆NmAkarta(A)≤m
Agar cheklito'plambo'lsava ningkichikto'plamibo'lsa , u holda cheklito'plamva .SASAkarta(A)≤karta(S)
Cheklito'plamgabitta element qo'shishuningkardinalligini 1 ga oshirishininazardatutadi. Cheklanganbo'shbo'lmaganto'plamdanbittaelementniolibtashlashkardinallikni 1 ga kamaytirishi ham haqiqatdir.
Agar cheklito'plambo'lsava , u holda cheklito'plamvaAx∈AA−{x}karta(A−{x})=karta(A)−1
Keyingixulosakeyingibo'limdacheklivacheksizto'plamlaro'rtasidagimatematikfarqnita'minlashuchunishlatiladi.
Cheklanganto'plamuningto'g'rito'plamlariningbirortasiga ham ekvivalentemas.
Ushbubo'limda biz ko'ribchiqadigancheklito'plamlarningoxirgixususiyatiko'pincha " Kabutarlaruyasiprintsipi " deb ataladi . Bu xususiyatning “kabutarteshigi” versiyasidashundaydeyilgan: “Agar kabutar teshigigava ga kirsa ,kamidabittakaptardabirnechtakaptarbor”.mrm>r
Bundayvaziyatda biz kaptarlarto‘plamini m kardinallikkaegabo‘lgan P to‘plamga, r to‘plamiesa r ga tengbo‘lgan H to‘plamiga ekvivalent mumkin . funktsiyasinianiqlashimizmumkin, u harbirkaptarnio'zteshigigamoslashtiradi. Pigeonhole Principle bufunktsiyain'ektsiyaemasliginibildiradi. (Bu birma-biremas, chunkibittakaptarteshigigakamidaikkita "xaritaqilingan" kaptarbor.)PHrf:P→H

Foydalanilganadabiyotlar internetsaytlari

1.turaev x.matematikmantiqvadiskritmatematika<>nashriyoti, t., 2003.
2.Abdurahmanova ydeskritmatematikao`quvqullanma .2014-yil

Internet saytlari

1.http://www.uni-dubna.ru/~mazny/kurses/odm/lekcii/
2. http://www.lvf2004.com/dop_t2r1part2.html
3.
https://www.fayllar.org
http://fayllar.org