Test zestawów liczb. Metody definiowania zbiorów

Test na temat „Zestawy”

INSTRUKCJE:

opcja 1

1. Określ, który z zestawów jest podzbiorem A = (10, 20, 30, 40, 50, 60)

a) (10, 20, 30, 40, 50, 60, 70) b) (10) c) (10, 35)

2. Który z zestawów określa, czy A = (1, 2, 3, 4, 5), B = (3, 4, 5, 6, 7)

a) (1, 4, 5) b) (1, 2, 3, 4, 5) c) (1, 2, 3, 4, 5, 6, 7)

jeśli A = (1, 3, 5, 7, 9), B = (1, 2, 3, 4)

a) (1, 3, 5, 7) b) (1, 2, 3, 4, 5, 7, 9) c) (1, 3)

4. Zbiór trójkątów został podzielony na podzbiory trójkątów uniwersalnych, trójkątów równoramiennych i trójkąty równoboczne... Czy zbiór trójkątów został podzielony na klasy?

a) tak b) nie

5. Który rysunek przedstawia połączenie zbiorów A i B ()?

Test na temat „Zestawy”

Test z wyborem poprawnej odpowiedzi.

INSTRUKCJE: Wybierz literę z poprawną odpowiedzią i wpisz ją na arkuszu odpowiedzi.

Opcja 2

1. Określ, który z zestawów jest podzbiorem

A = (5, 15, 25, 35, 45, 55)

a) (55) b) (5, 25, 50) c) (25, 55, 75)

2. Który z zestawów określa, czy A = (2, 4, 6, 8, 10), B = (8, 10, 12, 14)

a) (2, 4, 6, 8, 10, 12, 14) b) (8, 10, 12, 14) c) (8, 10)

3. Który z zestawów decyduje?
jeśli A = (2, 4, 6, 8, 10), B = (2, 4, 8, 9)

a) (2, 4, 6, 8, 10) b) (2, 4, 8, 9) c) (2, 4, 8)

4. Zbiór wszystkich kątów podzielono na podzbiory proste, rozwarte i ostre. Czy zbiór kątów został podzielony na klasy?

a) tak b) nie

5. Który rysunek przedstawia przecięcie zbiorów A i B (
)?

Federalna Agencja ds. Edukacji

Czuwaski Uniwersytet stanowy im. W. Uljanow

Oddział Alatyr

Wydział Zarządzania i Ekonomii

Wydział Matematyki Wyższej i Technologie informacyjne

Kurs pracy

według dyscypliny: Logika matematyczna

Elementy teorii mnogości

Robi student

1 kurs

grupy - AFT 61-06

kierownik

prof. Merlin A.V.

Wstęp

Teoria mnogości – gałąź matematyki zajmująca się badaniem ogólnych własności zbiorów. Teoria mnogości jest rdzeniem większości dyscyplin matematycznych; miała głęboki wpływ na rozumienie samego przedmiotu matematyki.

Do drugiego połowa XIX wieku pojęcie „zestawu” nie było uważane za matematyczne (wiele książek na półce, wiele cnót ludzkich itp. - wszystko to są wyrażenia czysto codzienne). Sytuacja zmieniła się, gdy niemiecki matematyk Georg Cantor (ryc. 1) opracował swój program standaryzacji matematyki, w ramach którego każdy obiekt matematyczny musiał być takim lub innym „zestawem”.

Na przykład liczbę naturalną, zdaniem Cantora, należy rozpatrywać jako zbiór składający się z jednego elementu innego zbioru, zwanego „ciągiem naturalnym” – który z kolei sam jest zbiorem spełniającym tzw. aksjomaty Peano. . W której ogólna koncepcja„Zbiór”, który uważał za kluczowy w matematyce, Cantor podał niewiele definiujących definicji, takich jak „zbiór to wiele, co można traktować jako jeden” itp. Było to całkiem zgodne z mentalnością samego Cantora, który podkreślał, że jego program nie nazywa się „teorią mnogości” (termin ten pojawił się znacznie później) i nauczanie o zestawach ( Mengenlehre).

Program Cantora wywołał ostre protesty wielu czołowych matematyków jego czasów. Leopold Kronecker był szczególnie godny uwagi ze względu na swój nieprzejednany stosunek do niej, który uważał, że tylko liczby naturalne i to, co bezpośrednio do nich sprowadza, można uznać za obiekty matematyczne (jego powiedzenie znane jest, że „Bóg stworzył liczby naturalne, a wszystko inne jest dziełem człowieka ręce" ). Niemniej jednak kilku innych matematyków - zwłaszcza Gottlob Frege i David Hilbert - poparło Cantora w jego zamiarze przetłumaczenia całej matematyki na język teorii mnogości.

Szybko jednak okazało się, że stosunek Cantora do nieograniczonej arbitralności w operowaniu zbiorami (wyrażony przez niego w zasadzie „istotą matematyki jest jej wolność”) jest początkowo wadliwy. Mianowicie odkryto szereg antynomii mnogościowych: okazało się, że stosując reprezentacje mnogościowe, można udowodnić pewne twierdzenia wraz z ich negacjami (a wtedy, zgodnie z regułami klasycznej logiki zdań, absolutnie każde zdanie może być "sprawdzone"!). Antynomie oznaczały całkowitą porażkę programu Cantora.

Jednak Cantor jest uważany za twórcę teorii mnogości i wniósł duży wkład we współczesną matematykę. Posiada on następującą cechę pojęcia „zbiór”: Zbiór jest połączeniem pewnych, różnych przedmiotów, zwanych elementami zbioru, w jedną całość.

Rozdział 1. Zestawy

1.1 Elementy i zestawy

Pojęcia zbioru i elementu zbioru odnoszą się do pojęć, które nie są wyraźnie zdefiniowane, takich jak np. punkt i prosta. Słowa „zbiór”, „rodzina”, „system”, „zestaw” itp. - synonimy słowa „zestaw”. Wynika to z faktu, że niektóre pojęcia w matematyce powinny być początkowe, służyć jako te „cegiełki”, które składają się ogólna teoria... Określamy jedynie, w jaki sposób te początkowe pojęcia odnoszą się do siebie, nie wspominając o naturze przedmiotowych obiektów. Myślenie ludzkie jest skonstruowane w taki sposób, że świat jest przedstawiany jako składający się z oddzielnych „obiektów”. Dla filozofów od dawna było jasne, że świat jest jedną nierozerwalną całością, a dobór w nim przedmiotów jest niczym innym, jak arbitralnym aktem naszego myślenia, który pozwala nam ukształtować obraz świata dostępny do racjonalnej analizy. Tak czy inaczej, selekcja obiektów i ich agregatów jest naturalnym (lub nawet jedynym możliwym) sposobem organizowania naszego myślenia, nic więc dziwnego, że leży u podstaw głównego narzędzia opisu wiedzy dokładnej - matematyki.

Możemy to powiedzieć wiele - jest to dowolny określony zbiór przedmiotów. Przedmioty, z których składa się zestaw, nazywamy go elementy. Elementy zestawu są odrębne i odróżnialne od siebie. Przykładami zestawów mogą być: wiele osób, zwierząt, roślin na naszej planecie, a także wiele N liczby naturalne 1, 2, 3, ..., zbiór P liczby pierwsze 2, 3, 5, 7, 11, ... Zbiór Z liczb całkowitych: ..., -2, -1, 0, 1, 2, ..., zbiór R liczb rzeczywistych itd. Zestaw, który nie zawiera żadnych elementów, nazywany jest pustym. Notacja: Pusty zbiór jest podzbiorem dowolnego zbioru. Kardynalność pustego zestawu wynosi zero. Pojęcie zbioru pustego (podobnie jak pojęcie „zera”) wynika z potrzeby, aby wynik jakiejkolwiek operacji na zbiorach był również zbiorem.

Zwykle w rozumowaniu konkretnym elementy wszystkich zbiorów są brane z jednego, dostatecznie szerokiego zbioru U, który nazywamy zbiorem uniwersalnym (lub wszechświatem).

Jeżeli przedmiot x jest elementem zbioru M, to mówimy, że x należy do M. Notacja: xÎM. W przeciwnym razie mówią, że x nie należy do M. Notacja: xÏM. Zauważ, że elementy zestawu mogą same być zestawami. Na przykład wiele grup uczniów składa się z elementów (grup), które z kolei składają się z uczniów.

Niech będą dane dwa zbiory A i B (rysunek 1.1.1), wtedy:

Podzbiór – koncepcja części w teorii mnogości. Zbiór C jest podzbiorem zbioru B (rys. 1.1.1, oznaczony CÌB), jeśli każdy element zbioru C jest również elementem zbioru B. Na przykład zbiór wszystkich liczb parzystych jest podzbiorem zbiór wszystkich liczb całkowitych. Jeśli C jest podzbiorem B, to B nazywamy nadzbiorem C.

Zazwyczaj zestawy są oznaczane wielkimi literami alfabetu łacińskiego, a elementy zestawów są oznaczane małe litery.

Pojęcia nastawienia, elementu i przynależności, które na pierwszy rzut oka wydają się intuicyjnie jasne, przy bliższym przyjrzeniu się tej jasności tracą. Po pierwsze, rozróżnialność elementów jest problematyczna. Na przykład znaki „e” i „a”, które pojawiają się na tej stronie, są jednym z elementów zestawu A czy dwa różne elementy? Po drugie, problematyczna jest możliwość (bez dodatkowego wysiłku) wskazania, czy dany element należy do danego zbioru. Na przykład, czy liczba 86958476921537485067857467 jest liczbą pierwszą?

Zbiory, podobnie jak przedmioty, mogą być elementami innych zbiorów. Zbiór, którego elementy są zbiorami, nazywa się zwykle klasa lub rodzina.

Rodziny zestawów są zwykle oznaczane wielkimi „odręcznymi” literami alfabetu łacińskiego, aby odróżnić je od zestawów, które nie zawierają zestawów jako elementów.

1.2 Metody określania zestawów

Nieracjonalność liczb postawiła nas przed koniecznością pracy ze zbiorami nieskończonymi. Ale tak naprawdę cały czas masz do czynienia z nieskończonością, na przykład dowolna figura geometryczna - wiele punktów: odcinek, okrąg, trapez, stożek ... - wszystkie te figury zawierają nieskończoną liczbę punktów . Na tej podstawie konieczne staje się określenie zestawów dla wygody pracy z nimi. Aby zdefiniować zestaw, musisz wskazać, które elementy do niego należą. Można to zrobić na różne sposoby. Wskazujemy dwie najczęstsze formy określania (definiowania) zbiorów

Wyliczenie elementów, czyli wskazanie wszystkich elementów zbioru, które zazwyczaj ujęte są w nawiasy klamrowe. Jeżeli elementy: Ò, Â,, À, w - należą do zbioru M, to piszemy M = (Ò, Â, Á, À, w);

Własność charakterystyczna, gdy wśród elementów zbioru za pomocą wyrażenia wyróżnia się elementy, które posiadają określoną własność (charakteryzującą ten zbiór). Niech P(x) będzie jakąś własnością liczby x. Wtedy zapis (x | P(x)) oznacza zbiór wszystkich takich liczb, które mają własność P(x). Na przykład zbiór (x | x2 - 3x + 2 = 0) jest zbiorem pierwiastków równania x2 - 3x + 2 = 0, czyli ten zbiór składa się z dwóch elementów: 2 i 1; (x | 3 12 i x<3} = Æ;

Jednak przy określaniu zestawów w taki czy inny sposób mogą pojawić się problemy. Na przykład niech zbiór A składa się z rosyjskich słów „stół”, „świat” i symbolu „$” w standardowych symbolach, czyli A = (stół, świat, $). Zbiór A ^, składający się z tych samych znaków, ale w języku angielskim, będzie inny A ^ = (stół, pokój, $). Musisz więc być precyzyjny w wyliczeniu (czyli określaniu zestawów przez wyliczenie). I jeszcze jeden przykład związany z dowolnym podręcznikiem lub książką. Jest wiele egzemplarzy książki, jeśli chodzi o konkretną książkę (np. należącą do określonej osoby), dostajemy jedną opcję, jeśli chodziło nam o wszystkie egzemplarze, które wyszły z drukarni (np. nakład 100 tysięcy książek) - inna opcja, jeśli wziąć pod uwagę tylko te, które przetrwały do chwili obecnej - trzecia opcja. Dlatego konieczne jest precyzyjne określanie zestawów przez wyliczenie.

Ale metoda określania zbioru za pomocą charakterystycznych właściwości elementów jest obarczona pewnymi niebezpieczeństwami, ponieważ „niepoprawnie” określone właściwości mogą prowadzić do sprzeczności. Oto jeden z najbardziej typowych paradoksów teorii mnogości: Paradoks Russella. Rozważ zbiór wszystkich zbiorów, które nie zawierają siebie jako elementu:

Jeżeli zbiór Y istnieje, to powinniśmy być w stanie odpowiedzieć na pytanie: YÎY? Niech YÎY, wtedy musi być spełniona własność definiująca zbiór Y, czyli YÏY. Niech więc YÏY, skoro własność definiująca Y jest spełniona, dochodzimy do tego, że YÎY, a to jest sprzeczne z założeniem. Okazuje się, że jest to nieusuwalna logiczna sprzeczność. Oto trzy sposoby na uniknięcie tego paradoksu.

1. Ogranicz używane predykaty cech do widoku

P (x) = xÎA i Q (x),

gdzie A jest znanym, świadomie istniejącym zbiorem (wszechświatem). Zwykle stosuje się notację (xÎA | Q(x)). Dla Y wszechświat nie jest określony, a zatem Y nie jest zbiorem;

2. Teoria typów. Obiekty są typu 0, zbiory typu 1, zbiory zbiorów typu 2 itd. Y nie ma typu i nie jest zbiorem;

3. Charakterystyczną właściwość P(x) podaje się w postaci funkcji obliczalnej (algorytmu). Metoda obliczania wartości właściwości XÎX nie jest określona, a zatem Y nie jest zbiorem.

Ostatnia z wymienionych metod leży u podstaw tzw konstruktywizm - kierunków w matematyce, w ramach których rozważane są tylko takie obiekty, dla których znane są procedury (algorytmy) ich generowania. W matematyce konstruktywnej pewne pojęcia i metody matematyki klasycznej, obarczone możliwymi paradoksami, są wyłączone z rozważań.

1.3 Liczba elementów w zestawie

Kardynalność to uogólnienie pojęcia ilości (liczby elementów w zbiorze), które ma sens dla wszystkich zbiorów, w tym nieskończonych.

Są duże, są mniejsze nieskończone zbiory, wśród nich zbiór policzalny jest najmniejszy.

W teorii mnogości zbiór przeliczalny jest zbiorem nieskończonym, którego elementy można ponumerować liczbami naturalnymi. Bardziej formalnie: zestaw x jest policzalny, jeśli istnieje bijekcja, gdzie oznacza zbiór wszystkich liczb naturalnych. Innymi słowy, zbiór przeliczalny jest zbiorem równym zbiorowi liczb naturalnych.

Zbiór policzalny to „najmniejszy” nieskończony zbiór, to znaczy w każdym nieskończonym zbiorze istnieje podzbiór policzalny.

Nieruchomości:

1. Każdy podzbiór zbioru policzalnego jest skończony lub policzalny;

2. Połączenie skończonej lub policzalnej liczby zbiorów policzalnych jest policzalne;

3. Iloczyn bezpośredni skończonej liczby zbiorów policzalnych jest policzalny;

4. Zbiór wszystkich skończonych podzbiorów zbioru przeliczalnego jest przeliczalny;

5. Zbiór wszystkich podzbiorów zbioru przeliczalnego jest ciągły, aw szczególności niepoliczalny.

Zbiór niepoliczalny to zbiór nieskończony, który nie jest policzalny. Zatem każdy zbiór jest albo skończony, policzalny, albo niepoliczalny. Zbiór liczb wymiernych i zbiór liczb algebraicznych są przeliczalne, ale zbiór liczb rzeczywistych jest ciągły, a zatem niepoliczalny. Mówi się, że dwa zestawy mają równą siłę, jeśli istnieje między nimi bijekcja. Istnienie bijekcji między zbiorami jest relacją równoważności, a kardynalność zbioru jest odpowiednią klasą równoważności.

Nieruchomości

· Dwa skończone zbiory są równe wtedy i tylko wtedy, gdy składają się z tej samej liczby elementów. Te. dla zbioru skończonego pojęcie kardynalności pokrywa się ze zwykłym pojęciem ilości.

W przypadku zbiorów nieskończonych moc zbioru może pokrywać się z mocą jego własnego podzbioru, na przykład

Z (zbiór liczb całkowitych) = (-3, -2, -1,0,1,2,3...);

N (zbiór liczb naturalnych) = (1,2,3,4,5,6,7...);

0,1, -1,2, -2,3, -3 ... tyle liczb całkowitych ile liczb naturalnych

1,2, 3,4, 5, 6, 7…

· Twierdzenie Cantora gwarantuje istnienie potężniejszego zbioru dla dowolnego zadanego zbioru: zbiór wszystkich podzbiorów zbioru A jest potężniejszy od zbioru A, lub | 2A | > | |.

Korzystając z kwadratu Cantora, można również udowodnić następujące użyteczne stwierdzenie: Iloczyn kartezjański zbioru A z samym sobą jest równy A.

Za Cantorem moc zbioru nazywamy liczbą kardynalną, a moc zbioru A oznaczamy | | (Sam Kantor użył notacji). Czasami jest oznaczenie.

Kardynalność zbioru liczb naturalnych jest oznaczona symbolem („alef-zero”). Zbiór nazywamy nieskończonym, jeśli jego kardynalność, zatem zbiory policzalne są „najmniejszymi” ze zbiorów nieskończonych. Wskazano następujące liczby główne w porządku rosnącym.

Mówi się, że zbiory równe zbiorowi wszystkich liczb rzeczywistych mają moc kontinuum, a moc takich zbiorów jest oznaczona symbolem c (continuum). Hipoteza kontinuum stwierdza to.

Dla kardynałów, podobnie jak w przypadku zbiorów skończonych, istnieją pojęcia: równość, więcej, mniej. Te. dla dowolnych zestawów A i B możliwy jest tylko jeden z trzech:

1. | | = | B | lub A i B są równe;

2. | | > | B | lub A jest silniejszy niż B, to znaczy, A zawiera podzbiór równy B, ale A i B nie są równe;

3. | |< | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

Niemożliwa jest sytuacja, w której A i B nie mają równej władzy i żadne z nich nie ma części równej drugiej. Wynika to z twierdzenia Zermelo. W przeciwnym razie oznaczałoby to istnienie nieporównywalnych zdolności (co w zasadzie jest możliwe, jeśli aksjomat wyboru nie zostanie zaakceptowany).

Sytuacja, w której | | > | B | i | |< | B |, невозможна по теореме Кантора - Бернштейна.

Dwa zestawy nazywane są równoważnymi, jeśli ich elementy można podzielić na pary, tak aby żaden element tych zestawów nie pozostał poza tymi parami.

Zbiór regularnych ułamków dodatnich zawiera tyle elementów, ile jest liczb naturalnych.

Rozdział 2. Operacje na zbiorach

Na zbiorach, a także na wielu innych obiektach matematycznych można wykonywać różne operacje. W wyniku operacji z oryginalnych zbiorów uzyskuje się nowe zbiory.

2.1 Porównanie zestawów

przynależność aksjomatyczna elementu zestawu

Zbiór A jest zawarty w zbiorze B (zestaw B zawiera zbiór A), jeśli każdy element A jest elementem B:

Jeśli u, to A nazywamy właściwym podzbiorem B. Zauważ, że. A-priorytet.

Mówi się, że dwa zestawy są równe, jeśli są podzbiorami siebie nawzajem:

Twierdzenie o porównaniu zestawów... Dla dowolnych zbiorów A i B istnieje jedna i tylko jedna z następujących możliwości: |A | = |B |, |A |<|B|, |A|>|

2.2 Podstawowe operacje na zestawach

Podstawowe operacje na zestawach są wymienione poniżej:

· Związek:

Skrzyżowanie:

Różnica:

Różnica symetryczna:

· dodatek:

Operacja dopełnienia implikuje pewien wszechświat (zbiór U zawierający A):

Aby lepiej zrozumieć znaczenie tych operacji, stosuje się diagramy Eulera - Venna, które pokazują wyniki operacji na figury geometryczne jako zbiory punktów.

Suma dwóch zbiorów AÈB (rys. 2.2.1) jest trzecim zbiorem, którego każdy element należy do co najmniej jednego ze zbiorów A i B

Przecięcie zbiorów A∩B (rysunek 2.2.2) jest zbiorem składającym się ze wszystkich tych elementów, które należą jednocześnie do wszystkich danych zbiorów.

Różnica zbiorów A \ B = A - B (rys. 2.2.3) jest zbiorem, którego każdy element należy do zbioru A, ale nie należy do zbioru B.

Różnica symetryczna ADB (rys. 2.2.4)

Dopełnienie zbioru A nazywamy zbiorem wszystkich elementów nie wchodzących w skład zbioru A (rysunek 3.2.5)

2.3 Własności operacji na zbiorach

Niech wszechświat będzie dany U . Następnie dla wszystkich A, B, CÌ U spełnione są następujące właściwości (tabela 2.3.1):

Własności operacji na zbiorach

Aby połączyć (È)	Przekroczyć (Ç)
Idempotencja
A A = A	A A = A
Przemienność
A È B = B È A	A Ç B = B Ç A
Łączność
A (BÈC) = (A È B) ÈC	A (BÇC) = (A Ç B) ÇC
Dystrybucja
A È (BÇC) = (A È B) Ç (A È C)	A Ç (BÈC) = (A Ç B) È (A Ç C)
Wchłanianie
(A Ç B) ÈA = A	(A È B) ÇA = A
Zero właściwości
=	A = Æ
Właściwości jednostek
A U = U	A U = U
Inwolucja
= A
Prawa de Morgana

Dodatkowe właściwości

Wyrażenie różnicy

Wyrażenie dla różnicy symetrycznej

Ważność wymienionych właściwości można zweryfikować na różne sposoby. Na przykład narysuj diagramy Eulera dla lewej i prawej strony równości i upewnij się, że się pokrywają, lub przeprowadź formalne rozumowanie dla każdej równości. Rozważmy na przykład pierwszą równość: A È A = A. Weźmy dowolny element NS, należący do lewej strony równości, NS Î A È A... Z definicji działania związku È mamy NS Î A È NS Î A.W każdym razie NS Î A . Biorąc dowolny element ze zbioru po lewej stronie równości, stwierdziliśmy, że należy on do zbioru po prawej stronie. Stąd z definicji inkluzji zbiorów otrzymujemy: A È A Ì A. Niech teraz NS Î A . Wtedy to oczywiście prawda NS Î A È NS Î A . Stąd zgodnie z definicją działania związku mamy NS Î A È A... Zatem, A Ì A È A... Dlatego, zgodnie z definicją równości zbiorów, A È A = A... Podobne rozumowanie jest łatwe do przeprowadzenia dla pozostałych równości.

Udowodnijmy własność rozdzielności dla działania sumy na diagramach Eulera-Venna (rysunek 2.3.1):

A È (BÇC) = (A È B) Ç (A È C)

Rozdział 3. Aksjomatyczna teoria mnogości

3.1 Naiwna teoria mnogości

Na początku XX wieku Bertrand Russell, studiując naiwną teorię mnogości, doszedł do paradoksu (znanego wówczas jako paradoks Russella). W ten sposób wykazano niepowodzenie naiwnej teorii mnogości i związanego z nią programu Cantora dla standaryzacji matematyki. Mianowicie odkryto szereg antynomii mnogościowych: okazało się, że stosując reprezentacje mnogościowe, można udowodnić pewne twierdzenia wraz z ich negacjami (a wtedy, zgodnie z regułami klasycznej logiki zdań, absolutnie każde zdanie może być "sprawdzone"!). Antynomie oznaczały całkowitą porażkę programu Cantora.

Po odkryciu antynomii Russella niektórzy matematycy (np. LE Ya Brouwer i jego szkoła) zdecydowali się całkowicie zrezygnować z używania reprezentacji mnogościowych. Inna część matematyków, na czele z D. Hilbertem, podjęła szereg prób uzasadnienia tej części reprezentacji mnogościowych, która wydawała im się najmniej odpowiedzialna za powstawanie antynomii, na podstawie oczywiście wiarygodnej matematyki skończonej. W tym celu opracowano różne aksjomatyzacje teorii mnogości.

Cechą podejścia aksjomatycznego jest odrzucenie podstawowej idei programu Cantora o rzeczywistym istnieniu zbiorów w jakimś idealnym świecie. W ramach teorii aksjomatycznych zbiory „istnieją” wyłącznie formalnie, a ich „właściwości” mogą zasadniczo zależeć od wyboru aksjomatyki. Fakt ten zawsze był przedmiotem krytyki ze strony tych matematyków, którzy nie zgadzali się (jak upierał się Hilbert) na uznanie matematyki za grę symboli pozbawioną jakiejkolwiek treści. W szczególności NN Luzin napisał, że „siła kontinuum, choćby myśleć o nim jako o zbiorze punktów, jest jednym rodzajem rzeczywistości”, której miejsce w szeregu liczb kardynalnych nie może zależeć od tego, czy kontinuum hipoteza jest uznawana za aksjomat lub jej zaprzeczenie.

Obecnie najbardziej rozpowszechnioną aksjomatyczną teorią mnogości jest ZFC - teoria Zermelo - Fraenkla z aksjomatem wyboru. Pytanie o spójność tej teorii (a tym bardziej o istnienie dla niej modelu) pozostaje nierozwiązane.

3.2 Aksjomaty teorii mnogości

Teraz mamy wszelkie środki, aby sformułować system aksjomatów teorii mnogości ZFC, w ramach którego można przedstawić wszystkie metody rozumowania ogólnie przyjęte we współczesnej matematyce i żaden ze znanych paradoksów teorii mnogości nie przemija. Ten system pozwala zbudować wszystko obiekty matematyczne na podstawie pustego zestawu. Reprezentujemy system aksjomatów Zermelo - Fraenkel (ZF).

1. Aksjomat istnienia zbioru pustego: Istnieje zbiór pusty Æ;

2. Aksjomat istnienia pary: Jeżeli istnieją zbiory aib, to zbiór istnieje (a,b);

3. Aksjomat sumy: Jeśli istnieje zbiór X, to istnieje zbiór ÈX = (a | aÎb dla pewnego bÎX);

4. Aksjomat nieskończoności: Istnieje zbiór w = (0, 1,…, n,…), gdzie 0 = Æ, n + 1 = nÈ (n);

5. Aksjomat zbioru wszystkich podzbiorów: Jeżeli istnieje zbiór A, to istnieje zbiór:

P(A) = (B | BÍA);

6. Zmień aksjomat: Jeśli P (x, y) jest pewnym warunkiem na zbiorach x , w tak, że dla dowolnego zbioru x istnieje co najwyżej jeden zbiór w spełniające P (x, y), to dla dowolnego zbioru a istnieje zbiór (b | P (c, b) dla niektórych c Î a);

7. Aksjomat rozszerzalności:

Dwa zestawy, które mają te same elementy, są równe, każdy zestaw jest określony przez jego elementy:

8. Aksjomat regularności:

Każdy niepusty zbiór x ma element a x dla którego

Z aksjomatu regularności wynika, że każdy zbiór jest uzyskiwany na pewnym etapie „regularnego procesu” formowania zbioru wszystkich podzbiorów, rozpoczynającego się od Æ i podobnego do konstrukcji liczb naturalnych ze zbioru pustego zgodnie z aksjomatem nieskończoności . Oznacza to, że każdy element dowolnego zbioru jest zbiorem skonstruowanym ze zbioru pustego.

Pokażmy, w jaki sposób aksjomatyka ZF pozwala na zdefiniowanie operacji mnogościowych.

1. Zdefiniujmy zbiór AÈ B wychodząc ze zbiorów A do B. Z aksjomatu istnienia pary tworzymy zbiór (A, B). Wykorzystując aksjomat sumy, otrzymujemy zbiór È (A, B), który z definicji pokrywa się ze zbiorem AÈB.

2. Przecięcie A Ç B zbiorów A i B jest określone przez aksjomat zmiany za pomocą następującej własności P (x, y): x = y i x Î A. Mamy zbiór (b | P (c, b ) i c B) = (b | c = b i c A i c Î B) = (c | c Î A i c Î B).

3. Pokażmy, że aksjomaty 5 i 6 implikują istnienie zbioru A2 = ((a, b) | a, bÎ A) dla dowolnego zbioru A. Ponieważ (a, b) = ((a), (a, b) ), następnie A2 ÍP (P (A)). Niech własność P (x, y) oznacza, że istnieją takie a, b A takie, że x = ((a), (a, b)) i y = x. Wtedy zbiór A2 jest równy (b | P (c, b), cÎ P (P (A))) i zgodnie z Aksjomatem 6 istnieje.

Układ aksjomatów ZFC tworzy się z ZF przez dodanie jednego z dwóch następujących równoważnych aksjomatów, które z jednej strony są najmniej „oczywiste”, a z drugiej najbardziej znaczące,

1. Aksjomat wyboru.

Dla dowolnego niepustego zbioru A istnieje odwzorowanie j: P (A) \ (Æ) ®A takie, że j (X) ÎX | dla wszystkich XÍ A, X¹Æ.

2. Zasada pełnego zamówienia. Dla każdego niepustego zbioru A istnieje relacja binarna £ na A, dla której (A, £) jest zbiorem uporządkowanym.

W systemie ZFC obowiązuje zasada indukcji pozaskończonej, która jest uogólnieniem zasady indukcji zupełnej: jeśli (A, £) jest zbiorem uporządkowanym, P (x) jest pewną własnością, to ważność własności P (x) na wszystkich elementach x Î A wynika z tego, że dla dowolnego z А spełnialność własności P na elementach y, gdzie y< z, влечет выполнимость P(z):

Rozdział 4. Reprezentacja zbiorów w komputerze

Termin „prezentacja” (używają oni również terminu „implementacja”) w odniesieniu do programowania oznacza co następuje. Ustawić reprezentację obiektu (w tym przypadku zbioru) oznacza opisanie w kategoriach używanego systemu programowania struktury danych służącej do przechowywania informacji o reprezentowanym obiekcie oraz algorytmów nad wybranymi strukturami danych, które realizują operacje nieodłącznie związane z ten obiekt. W tym artykule założono, że w używanym systemie programowania dostępne są wspólne struktury danych, takie jak tablice, struktury (lub rekordy) i wskaźniki. Zatem w odniesieniu do zbiorów definicja reprezentacji implikuje opis sposobu przechowywania informacji o przynależności elementów do zbioru oraz opis algorytmów obliczania sumy, przecięcia i innych wprowadzonych operacji.

Należy podkreślić, że z reguły jeden i ten sam obiekt można przedstawić na wiele różnych sposobów i nie sposób wskazać metody, która jest najlepsza we wszystkich możliwych przypadkach. W niektórych przypadkach warto zastosować jeden pogląd, w innych inny. Wybór prezentacji zależy od wielu czynników: charakterystyki reprezentowanego obiektu, składu i względnej częstotliwości korzystania z operacji w Szczególnym zadaniem itp. Umiejętność wyboru najbardziej odpowiedniej reprezentacji dla danego przypadku jest podstawą sztuki praktycznego programowania. Dobry programista różni się tym, że zna wiele różnych sposobów prezentacji i umiejętnie wybiera ten najbardziej odpowiedni.

4.1 Implementacja operacji na podzbiorach danego uniwersum U

Niech wszechświat U- skończone, a ilość zawartych w nim elementów przekracza pojemność komputera: | U | < n. Элементы универсума нумеруются: U = (u1 ... un). Podzbiór A wszechświata U jest reprezentowany przez kod (słowo maszynowe lub skalę bitową) C, w którym

1 jeśli u1

0 jeśli nie

gdzie C [i] to i-ta ranga kod C;

Kod przecięcia zbiorów A i B jest bitowym iloczynem logicznym kodu zbioru A i kodu zbioru B. Kod łączący zbiory A i B jest bitową sumą logiczną kodu zbioru A i kod zestawu B. W większości komputerów istnieją odpowiednie instrukcje maszynowe dla tych operacji. Dzięki temu operacje na małych zbiorach wykonywane są bardzo sprawnie. Jeśli liczność wszechświata przekracza rozmiar słowa maszynowego, ale nie jest bardzo duża, to do reprezentowania zbiorów używane są tablice skal bitowych. W tym przypadku operacje na zbiorach są realizowane za pomocą pętli na elementach tablicy.

4.2 Generowanie wszystkich podzbiorów wszechświata

W wielu algorytmach wyliczania wymagane jest sekwencyjne uwzględnianie wszystkich podzbiorów danego zbioru. W większości komputerów liczby całkowite są reprezentowane przez kody w systemie liczb binarnych, a liczba 2k - 1 jest reprezentowana przez kod zawierający k jedynek. Tak więc liczba 0 jest reprezentacją zbioru pustego Æ, liczba 1 reprezentacją podzbioru pierwszego elementu i tak dalej. Poniższy trywialny algorytm wymienia wszystkie podzbiory zestawu n-elementowego.

Algorytm generowania wszystkich podzbiorów zbioru n-elementowego:

Wejście: n³ 0 to liczność zbioru;

Wyjście: sekwencja kodów podzbiorów i;

dla i od 0 do 2n - 1;

dawać i ;

kończyć się dla ;

Algorytm wyprowadza 2n różnych liczb całkowitych, a więc 2n różnych kodów. Wraz ze wzrostem liczby zwiększa się liczba bitów potrzebnych do jej przedstawienia. Największa (z wygenerowanych) liczba 2n - 1 wymaga reprezentacji dokładnie w n cyfrach. W ten sposób generowane są wszystkie podzbiory i to dokładnie raz. Wadą tego algorytmu jest to, że kolejność generowania podzbiorów nie ma nic wspólnego z ich kompozycją. Na przykład po podzbiorze o kodzie 0111 zostanie wyświetlony podzbiór o kodzie 1000.

4.3 Reprezentacja zbiorów według uporządkowanych list

Jeśli wszechświat jest bardzo duży (lub nieskończony), a rozważane podzbiory wszechświata nie są bardzo duże, to reprezentacja przy użyciu skal bitowych nie jest wydajna pod względem oszczędzania pamięci. W tym przypadku zbiory są reprezentowane przez rekord z dwoma polami: informacyjnym i wskaźnikiem do kolejnego elementu. Cała lista jest reprezentowana przez wskaźnik do pierwszego elementu.

elem = nagrywać ;

i : informacje ; (pole informacyjne);

n : n(wskaźnik do następnego elementu);

kończyć się nagrywać ;

Przy takiej reprezentacji złożoność operacji Î wyniesie O (n), a złożoność operacji Ì, Ç, È wyniesie O (n × m), gdzie n i m są mocami zbiorów uczestniczących w operacja.

Jeżeli elementy na listach są uporządkowane, na przykład, w porządku rosnącym według wartości pola i, to złożoność wszystkich operacji będzie O (n). Sprawna realizacja operacji na zbiorach reprezentowanych w postaci uporządkowanych list opiera się na bardzo ogólny algorytm znany jako algorytm scalania. Algorytm typu scalającego przegląda równolegle dwa zestawy, reprezentowane przez uporządkowane listy, i na każdym kroku następuje postęp w zestawie, w którym bieżący element jest mniejszy.

Wniosek

Projekt kursu realizowany jest na temat „Elementy teorii mnogości”. Odnosi się do problemów:

Zbiory: elementy i zbiory, metody określania zbiorów, liczba elementów w zbiorze;

Operacje na zbiorach: porównywanie zbiorów, podstawowe operacje na zbiorach, własności operacji na zbiorach;

Aksjomatyczna teoria mnogości: naiwna teoria mnogości, aksjomaty teorii mnogości;

Reprezentacja zbiorów w komputerze: Implementacja operacji na podzbiorach danego wszechświata U , Generowanie wszystkich podzbiorów wszechświata Reprezentacja zbiorów przez uporządkowane listy;

Na podstawie znalezionych informacji (podręczniki, Internet) podkreśliłem główne punkty, które najpełniej i najdokładniej dają wyobrażenie o teorii mnogości. Podczas wykonywania pracy podano przykłady zestawów, a także te przykłady, które prowadzą do sprzeczności, gdy inny sposób ich zadania. Badając własności operacji na zbiorach, udowodniłem jedną z własności (dystrybutywność) za pomocą diagramów Eulera-Venna. I myślę, że w ostatnim rozdziale trzeba było zwrócić uwagę na związek między zbiorami i ich reprezentacją na komputerze, jest to moim zdaniem szczególnie ważne dla specjalności matematyk-programista.

Po wykonanej pracy możesz zrobić następne wyjście:

Pojęcia „zbiorów” i „elementów zbiorów” stanowią podstawowy słownik logiki matematycznej. To właśnie te koncepcje kładą podwaliny niezbędne do dalszych konstrukcji.

Lista wykorzystanej literatury

1. Matematyka dyskretna dla programistów / FA Novikov. - SPb .: Piotr, 2002 .-- 304 s.

2. Zholkov S.Yu. Matematyka i informatyka dla nauk humanistycznych: Podręcznik. - M .: Gardariki, 2002 .-- 531 s.

3. Sudoplatov S.V., Ovchinnikova E.V. Elementy Matematyka dyskretna: Podręcznik. - M .: INFRA-M, Nowosybirsk: Wydawnictwo NSTU, 2002 .-- 280 s. - (Seria " Wyższa edukacja»)

4. Shipachev V.S. Wyższa matematyka... Podręcznik. Dla uniwersytetów. - 4 wydanie, skasowane. - M .: Szkoła podyplomowa... 1998 .-- 479 s.

5. Materiał z Wikipedii - wolna encyklopedia. Georg Cantor (http://www.peoples.ru/science/mathematics/kantor/)

Test: Podstawy teorii mnogości Zestaw, który nie zawiera żadnych elementów.

Odpowiedź:

pusty zestaw

Zestaw zawierający skończoną liczbę elementów.

Odpowiedź:

zbiór skończony

Zbiór, który nie jest ani skończony, ani pusty.

Odpowiedź:

nieskończony zestaw

Wiele rzek w Rosji.

pusty

Mnóstwo ludzi mieszkających na Marsie.

finał

Zbiór punktów na okręgu.

nieskończony

zbiór liczb naturalnych

zbiór liczb całkowitych

zbiór liczb wymiernych

zbiór liczb rzeczywistych

Przemienność

AIB = BIA

Łączność

AИ (B∩C) = (AИB) ∩ (AИC)

Dystrybucja

(AIB) ИC = AИ (BIC)

Metody określania zestawów:

wyliczenie wszystkich elementów zbioru

za pomocą kręgów Eulera

wskazanie charakterystycznej właściwości elementów zbioru

określenie pierwszego i ostatniego elementu zbioru

uzupełnienie zestawu

Uniwersalny zestaw

równy

podzbiór

Zbiór A jest podzbiorem zbioru D

Zbiór D jest podzbiorem zbioru A

Zbiór A i zbiór D są równe

Zbiór A - stopień zbioru D

(0;1)

(3;1)

(2;0)

(1;0)

wielu studentów wydziału z domowym komputerem osobistym

pusty zestaw

zbiory A i B są równe

Niech zbiór M = (- 1; 1) będzie przedziałem, a zbiór N = [- 1; 0] będzie odcinkiem osi liczbowej, to zbiór K = M З N, jako przedział liczbowy będzie równy do ...

K = [- 1, 1]

K = (- 1,0]

K = (- 1,0)

K = (- 1, 1]

		(-1;0)
		(1;1)
		(0;1)
		(-1;1)

symetryczna różnica

dodatek

równy

Wybierz prawidłowe stwierdzenia:

Nieskończone niepoliczalne zbiory są mniej potężne niż nieskończone niepoliczalne zbiory.

Nieskończone zbiory niepoliczalne są potężniejsze niż nieskończone zbiory policzalne.

Nieskończone zbiory przeliczalne to zbiory, które osiągnęły liczność kontinuum.

Każdy skończony zbiór będzie słabszy niż jakikolwiek nieskończony zbiór policzalny.

zestawy A i B składają się z tych samych elementów

zbiory A i B są równe

zestaw A zawiera zestaw B

zbiór A jest podzbiorem zbioru B

Uprość, jeśli A = B, A∩C =∅ :

(((AИB) ∩ (C∩C)) \ (B∩A) ∩B)) ∆A =…

pusty zestaw

Uprość, jeśli A = B, A∩C =∅ :

((D \ (A∩B)) ∩ ((CIC) ∩B) =…

pusty zestaw

Uprość, jeśli A = B, A∩C =∅ :

(C∩B) ∆ ((AИB) ORAZ (C∩A)) =…

pusty zestaw

X = (1,5); Y = (1,2,4); Z = (2,5)

Znajdź zbiór: XИ (Y∩Z)

{1,2,4,5}

{1,2,5}

{1,4,5}

{1,2,4}

Niech podane zostaną następujące zbiory:

X = (1,2,3,4,5); X = (1,5); Y = (1,2,4); Z = (2,5)

Znajdź zbiór: (XИY) ∩ (XИZ)

{1,2,4,5}

{1,5}

{1,2,5}

{2,5}

A = (5, 7, 9) I (5,12, 15)

Postępuj zgodnie z instrukcjami i określ liczność otrzymanego zestawu:

b = {5, 7, 9, 12} Z{5,12, 15}

Postępuj zgodnie z instrukcjami i określ liczność otrzymanego zestawu:

A = (5, 7, 9) З{5, 57, 59}

Postępuj zgodnie z instrukcjami i określ liczność otrzymanego zestawu:

b = {5, 7, 9} ORAZ{5, 57, 59}

Postępuj zgodnie z instrukcjami i określ liczność otrzymanego zestawu:

{1, 2, 3}\ {2, 3}

Postępuj zgodnie z instrukcjami i określ liczność otrzymanego zestawu:

{1, 2, 3}\ {4, 5}

x ≤ 3

x (1, 2, 3)

1 < x < 5

x (2, 3, 4)

3 < x ≤ 6

x (4, 5, 6)

2 ≤ x ≤ 4

1 ≤ x< 4

Ilu uczniów wykonało wszystkie zadania?

W Olimpiadzie Matematycznej dla kandydatów wzięło udział 40 uczniów, którzy zostali poproszeni o rozwiązanie jednego zadania z algebry, jednego z geometrii i jednego z trygonometrii. W algebrze problem rozwiązało 20 osób, w geometrii - 18 osób, w trygonometrii - 18 osób.

7 osób zdecydowało się na algebrę i geometrię, 9 osób na algebrę i trygonometrię. Żaden problem nie został rozwiązany przez 3 osoby.

Ilu uczniów rozwiązało tylko dwa problemy?

7 osób zdecydowało się na algebrę i geometrię, 9 osób na algebrę i trygonometrię. Żaden problem nie został rozwiązany przez 3 osoby.

Ilu uczniów rozwiązało tylko jeden problem?

Pierwszą lub drugą pracę testową z matematyki napisało z powodzeniem 33 uczniów, pierwszą lub trzecią - 31 uczniów, drugą lub trzecią - 32 uczniów. Co najmniej dwa sprawdziany wypełniło 20 uczniów.

Ilu uczniów pomyślnie rozwiązało tylko jednego? test?

W klasie jest 35 uczniów. Każdy z nich korzysta z co najmniej jednego z rodzajów transportu publicznego: metra, autobusu i trolejbusu. Ze wszystkich trzech rodzajów transportu korzysta 6 uczniów, metro i autobus - 15 uczniów, metro i trolejbus - 13 uczniów, trolejbus i autobus - 9 uczniów.

Ilu uczniów korzysta tylko z jednego środka transportu?

Odpowiedź:

Niech A = (1,2,3,8) i B = (a, b, c)