Tulajdonságok megszámlálható halmazok - studopediya
Tekintsük a sor minden molekulák a légkörben. Ez a készlet tartalmaz egy nagyon nagy számú elemet (körülbelül 1,02 77.010.541 0), de ez véges, azaz van egy állandó, amely nagyobb, mint ahány eleme ez a készlet. Amellett, hogy a természetesen vannak végtelen halmazok. Az egyik a kitűzött célok elmélet, hogy meghatározza az elemek száma a készletben, és a tanulmány azt a kérdést, összehasonlítva egymással két száma elemekkel.
Véges készlet nagyon különböző természetű ez a probléma könnyen megoldható közvetlen számítása. Mert végtelen halmazok a kérdés az összehasonlítás nem lehet eldönteni, hogy a végére, a számolás. Ezért Cantor javasolt összehasonlítani két végtelen halmazok létrehozása egy-egy (bijektív) leképezés között. Tekintsük a példát leképezés létrehozása.
1. példa Amint az A vizsgálni az intervallum a számegyenesen, legyen A = (- 1, 1), valamint több V - a valós számok halmaza R. Ez állítja azonos teljesítmény, mert a leképezés f (x) = tg (px / 2), XÎÉs ez lehetővé teszi, hogy a szükséges egy-egy levelezés.
2. példa Legyen a = [-1,1], B = (-1,1). Épület egy térkép f. A ® B a következő szabály szerint: Egy válasszuk sorrendben 1, 1, 1/2, 1/3, 1/4. 1 / n, és hagyja, hogy az f (-1) = 1/2, F (1) = 1/3, F (1/2) = 1/4, F (1/3) = 1/5, azaz f (1 / n) = 1 / (n + 2), és az összes pont nem tartalmazza ezt a térképen a szekvenciát maguk, azaz f (x) = = x. Ennélfogva, a nyitott és zárt intervallumok egyenértékű.
Számosságú általánosítása száma halmaz elemeit. Ha egy bijektív leképezés készletek telepítve, akkor értelemszerűen, a mindkét az azonos számú elemet vagy több teljesítmény egyenlő a erejét egy másik.
Teljesítmény - ez a teljes, hogy a két azonos készletek. A több teljesítmény jelöljük m (A) vagy | A |. Így, m (A) = m (B), ha A
Ha több Egy egyenértékű néhány részhalmaza B, a kimenet egy nem nagyobb kapacitású B (azaz m (A) £ m (B)). Ha a beállított B nem egyenértékűek bármely alcsoportja A halmaz, akkor m (A) A legegyszerűbb között végtelen halmazok a természetes számok halmaza N. Meghatározás. Hívjuk a készlet minden megszámlálható egyenértékű sor N. Más szóval, a számolás minden halmaz, amelynek elemei lehet számozni, vagy hogy ezek egy végtelen sorozatot. Példák megszámlálható halmazok. 1. az egész számok Z = .Postroim szekvenciája annak elemei: a1 = 0; a2 = -1; a3 = -1; a4 = -2; a5 = 2;. A képlet kiszámításához általános kifejezés felírható 2. Egy beállítani Q minden racionális számok. Lássuk be a countability a készlet. Mint ismeretes, a racionális szám - egy töredéke a forma p / q, ahol pÎZ. qÎN. Írunk ezeket egy táblázatban a végtelen számú sorok és oszlopok Ebből a táblázatból a elemek össze egy szekvenciát a következő szabály a1 = 0/1; a2 = 1/1; a3 = -1 / -1; a4 = 1/2; a5 = -2 / -1; a6 = 2/1, stb mozog a nyilak által jelzett irányokban. Nyilvánvaló, hogy ebben a sorrendben tartalmazza az összes racionális számok. Sőt, sok a számok ismét sor kerül rá. Ezért a számossága eleme ez a szekvencia nem kevesebb, mint a hatalom a racionális számokat. Másrészt, ez ugyanaz, mint a természetes számsor, azaz részhalmaza Q. és ezért nem lehet nagyobb befogadóképességű Q. Így a racionális számok megszámlálható. A végtelen számú, nem megszámlálható hívják megszámlálhatatlan. 1. Minden részhalmaza egy megszámlálható halmaz véges vagy megszámlálható. Bizonyítás. Legyen - egy megszámlálható halmaz és BÍA. Mivel A megszámlálható, akkor felsorolni annak elemei és építeni egy szekvenciát közülük Ebből a szekvenciából, jelölje ki az összes elemet tartozó meghatározott B, azaz úgy a szekvencia Az alábbi esetekben: 1) A beállított B véges; 2) több B végtelen. Mivel elemei B vannak számozva, a második esetben ez megszámlálható, QED. 2. Az Unió bármely véges vagy megszámlálható halmaza megszámlálható halmazok újra a számlálást. Bizonyítás. Hagyja, hogy a készletek A1. A2. AN. - számolás. Ha a szám nem több, mint megszámlálható, a készletet is számozott és intézkedik tartozó elemek a táblázatban Legyen B =. Construct szekvencia, mint ahogy ez történt Sec. 4 bizonyíték megszámlálható Q. Ha diszjunkt Ai (Ai Çaj ¹Æ), A szekvencia (1) nem tartalmazza azokat az elemeket, amelyek már számozva. Így a beépített egy megfeleltetés halmazai között B és N. Következésképpen, a beállított B megszámlálható. 3. Minden végtelen halmaz megszámlálható részhalmaza. Bizonyítás. Legyen M - bármely végtelen. Úgy döntünk, hogy önkényes első elemet és jelöljük a1. majd - a2 elem, stb Kapunk egy sorozat a1. a2. amely nem törik le egy bizonyos elem, hiszen M végtelen. Ezért, ez a szekvencia képezi egy részhalmazát megszámlálható M. Ez a tétel lehetővé teszi számunkra azt, hogy egy megszámlálható halmaz a leginkább között végtelen halmazok „kis”. Ha a beállított véges vagy megszámlálható azt mondjuk, hogy ez nem több, mint megszámlálható. Ezek a példák és tulajdonságait a benyomást keltheti, hogy minden végtelen halmazok megszámlálható. Azonban nem ez a helyzet, és ennek bizonyítására elegendő építésére egy ellenpélda, vagyis hogy készítsen egy végtelen halmaz, amely nem megszámlálható. Tétel. A készlet minden végtelen bináris szekvenciák, azaz a álló 0 és 1, megszámlálhatatlan. Bizonyítás. Tegyük fel, hogy éppen ellenkezőleg, azaz Ezek a szekvenciák számozott. Let P1. P2. - szekvenciák, ahol P1 = 11. a12. A13.>, P2 = 21. a22. a23.> stb = Aij ahol Aij = 0 vagy 1. Készítünk egy sorozata P nem tartalmaz ebben a listában. Egy ilyen szekvencia létezik, például, a P = 11. 1-A22. 1-A33.>. Nyilvánvaló, annak elemei értéke 0 vagy 1, és ez nem egyenlő bármely más, a listán, mert ez eltér a szekvencia P1 legalább az első eleme a P2 - legalább a második, stb Így, az épített szekvencia különbözik minden a felsorolt szekvenciák legalább egy elem. Következésképpen a készlet minden bináris sorozatok számozott lehetetlen, ami azt jelenti, hogy megszámlálhatatlan.Kapcsolódó cikkek