Zbiór skończony: Różnice pomiędzy wersjami

[wersja nieprzejrzana]

[wersja przejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 13:37, 21 paź 2014

Zbiór skończony − w matematyce zbiór o skończonej liczbie elementów lub dokładniej: zbiór skończonej mocy, tzn. mocy mniejszej od pierwszej nieskończonej liczby kardynalnej $\scriptstyle \aleph _{0}$ (w tym zbiór pusty). Zbiorem nieskończonym nazywa się zbiór, który nie jest skończony. Odpowiedzią na pytanie o liczbę zbiorów skończonych zajmuje się dział matematyki nazywany kombinatoryką, pośrednio zajmują się nim również teoria liczb oraz kryptografia, w ogólności zbiory jako takie bada się w teorii mnogości. Bliskim pojęciem zbioru skończonego jest ciąg skończony, w którym istotna jest kolejność elementów.

W świecie rzeczywistym można spotkać się wyłącznie ze zbiorami skończonymi, choć mogą mieć one bardzo dużo elementów − przykładem może być np. liczba możliwych do zaobserwowania atomów we wszechświecie, którą szacuje się na ok. $\scriptstyle 10^{80}$ (zob. widzialny wszechświat; wymiary wszechświata mogą być nieskończone) – z jednej strony wynika to ze skończonej podzielności materii (zob. kwant), a z drugiej ze skończonej prędkości światła. Zdawać by się mogło, że precyzyjne określenie czym jest zbiór skończony nie powinno nastręczać większych trudności, jednak istnieje kilka nierównoważnych definicji tego pojęcia.

Mimo to we współczesnej matematyce rozpatruje się zbiory nieskończone: można traktować to jako pewnego rodzaju wybieg mający na celu łatwiejsze uchwycenie wyników procesów dziejących się w bardzo krótkim, czy bardzo długim czasie, choć bywa to okupione mniejszą intuicyjnością rozumowań (zob. paradoks Hilberta). Historycznie do XIX wieku, zgodnie z myślą Arystotelesa operowano wyłącznie zbiory skończone traktując nieskończoność jako proces, który można w razie potrzeby bez przeszkód kontynuować (w geometrii euklidesowej prosta traktowana była jako odcinek, który można było nieograniczenie przedłużać); przełom przyniosły prace Georga Cantora, który potraktował zbiory nieskończone jako osobne byty o własnej hierarchii (zob. nieskończoności potencjalną i aktualną). Choć dziś idee teorii Cantora są szeroko akceptowane przez społeczność matematyków, to trudności w początkowej fazie jej rozwoju spowodowały opór w postaci finityzmu, konstruktywizmu, czy intuicjonizmu odrzucających pojęcie nieskończoności aktualnej (zob. aksjomat Cantora, nazywany też aksjomatem nieskończoności^[1]).

Definicje

Zobacz też: zawieranie zbiorów i równoliczność.

Definicja naturalna: Zbiór skończony to zbiór równoliczny z ograniczonym podzbiorem liczb naturalnych, tzn. zbiór, dla którego istnieje funkcja wzajemnie jednoznaczna tego zbioru z podzbiorem zbioru liczb naturalnych postaci $\scriptstyle \{0,1,2,\dots ,n-1\}$ dla pewnego $\scriptstyle n$ ^[2].
Definicja Tarskiego: Zbiór jest skończony wtedy i tylko wtedy, gdy każda niepusta rodzina jego podzbiorów ma element maksymalny ze względu na relację inkluzji^[3].
Definicja Dedekinda: Zbiór nazywa się skończonym, gdy nie jest równoliczny z żadnym swoim podzbiorem właściwym, tzn. nie istnieje funkcja zbioru w siebie, która byłaby iniekcją (różnowartościowa), lecz nie byłaby suriekcją („na”)^[4].
Definicja Dedekinda (alternatywna 1): Zbiór jest skończony, gdy nie istnieje funkcja różnowartościowa zbioru liczb naturalnych w ten zbiór^[5].
Definicja Dedekinda (alternatywna 2): Zbiór jest skończony, gdy nie zawiera zbioru przeliczalnie nieskończonego.

Definicje pochodzące od Alfreda Tarskiego i Richarda Dedekinda (niealternatywna) mają zasadniczą przewagę nad definicją naturalną, mianowicie nie wykorzystują pojęcia liczby naturalnej. Rozwiązanie Dedekinda, ze względu na swą intuicyjność było do czasów prac Georga Cantora (a więc do XIX wieku) niemal powszechnie przyjmowane jako równoważne definicji naturalnej. Na gruncie aksjomatyki Zermelo-Fraenkela (ZF, bez aksjomatu wyboru AC) teorii mnogości równoważne są definicje naturalna i Tarskiego, równoważne są wtedy także warianty definicji Dedekinda. Na mocy zasady indukcji definicja naturalna pociąga za sobą definicję Dedekinda, jednak pociąganie w drugą stronę wymaga użycia aksjomatu wyboru (AC), a przynajmniej aksjomatu wyborów zależnych (DC).

Przykłady

Zbiór liczb naturalnych jest równoliczny ze zbiorem liczb parzystych, który jest jego właściwym podzbiorem. Równoliczność ustala funkcja wzajemnie jednoznaczna $\scriptstyle n\leftrightarrow 2n.$ Podobnie zbiór liczb rzeczywistych jest równoliczny z podzbiorem dodatnich liczb rzeczywistych − wzajemnie jednoznaczną odpowiedniość elementów ustala np. odwzorowanie wykładnicze $\scriptstyle x\leftrightarrow \exp x.$ W ten sposób zbiory liczb naturalnych i rzeczywistych są nieskończone w sensie Dedekinda.

Liczba wszystkich podzbiorów zbioru $\scriptstyle n$ -elementowego jest równa $\scriptstyle 2^{n}$ (zob. zbiór potęgowy). Liczba podzbiorów $\scriptstyle k$ -elementowych zbioru $\scriptstyle n$ -elementowego jest równa $\scriptstyle {\binom {n}{k}}$ (zob. symbol Newtona).

Zobacz też

↑ Aksjomat ten wzbudza kontrowersje, gdyż jest niezależny od pozostałych aksjomatów Zermelo-Fraenkela teorii mnogości – również aksjomatu wyboru – o ile są one niesprzeczne (zob. twierdzenie Gödla).
↑ Przyjmując, że dla $\scriptstyle n=0$ wspomniany zbiór ma postać $\scriptstyle \{\}=\varnothing ,$ w myśl definicji naturalnej zbiór pusty jest również skończony.
↑ Zbiór pusty jest skończony w sensie definicji Tarskiego, gdyż spełnia on ją „w próżni”: zbiór pusty nie ma niepustej rodziny podzbiorów, zatem każda z nich ma element maksymalny ze względu na zawieranie.
↑ Warunek definicji Dedekinda, podobnie jak w definicji Tarskiego, jest również spełniony „w próżni” dla zbioru pustego, gdyż zbiór pusty nie ma podzbiorów właściwych, zatem żaden podzbiór właściwy zbioru pustego nie jest z nim równoliczny.
↑ Por. zasada szufladkowa Dirichleta.

[1] Aksjomat ten wzbudza kontrowersje, gdyż jest niezależny od pozostałych aksjomatów Zermelo-Fraenkela teorii mnogości – również aksjomatu wyboru – o ile są one niesprzeczne (zob. twierdzenie Gödla).

[2] Przyjmując, że dla $\scriptstyle n=0$ wspomniany zbiór ma postać $\scriptstyle \{\}=\varnothing ,$ w myśl definicji naturalnej zbiór pusty jest również skończony.

[3] Zbiór pusty jest skończony w sensie definicji Tarskiego, gdyż spełnia on ją „w próżni”: zbiór pusty nie ma niepustej rodziny podzbiorów, zatem każda z nich ma element maksymalny ze względu na zawieranie.

[4] Warunek definicji Dedekinda, podobnie jak w definicji Tarskiego, jest również spełniony „w próżni” dla zbioru pustego, gdyż zbiór pusty nie ma podzbiorów właściwych, zatem żaden podzbiór właściwy zbioru pustego nie jest z nim równoliczny.

[5] Por. zasada szufladkowa Dirichleta.

[1]

[2]

[3]

[4]

[5]

@@ Linia 8: / Linia 8: @@
 == Definicje ==
 {{zobacz też|podzbiór#Zawieranie|o1=zawieranie zbiorów|moc zbioru|o2=równoliczność}}
-; Definicja naturalna : ''Zbiór skończony'' to zbiór równoliczny z [[zbiór ograniczony|ograniczonym]] [[podzbiór|podzbiorem]]  [[liczby naturalne|liczb naturalnych]], tzn. zbiór, dla którego istnieje [[funkcja wzajemnie jednoznaczna]] tego zbioru ze zbiorem [[liczby naturalne|liczb naturalnych]] <math>\scriptstyle \{0, 1, 2, \dots, n-1\}</math> dla pewnego <math>\scriptstyle n</math><ref>Przyjmując, że dla <math>\scriptstyle n = 0</math> wspomniany zbiór ma postać <math>\scriptstyle \{\} = \varnothing,</math> w myśl definicji naturalnej [[zbiór pusty]] jest również skończony.</ref>.
+; Definicja naturalna : ''Zbiór skończony'' to zbiór równoliczny z [[zbiór ograniczony|ograniczonym]] [[podzbiór|podzbiorem]]  [[liczby naturalne|liczb naturalnych]], tzn. zbiór, dla którego istnieje [[funkcja wzajemnie jednoznaczna]] tego zbioru z podzbiorem zbioru [[liczby naturalne|liczb naturalnych]] postaci <math>\scriptstyle \{0, 1, 2, \dots, n-1\}</math> dla pewnego <math>\scriptstyle n</math><ref>Przyjmując, że dla <math>\scriptstyle n = 0</math> wspomniany zbiór ma postać <math>\scriptstyle \{\} = \varnothing,</math> w myśl definicji naturalnej [[zbiór pusty]] jest również skończony.</ref>.
 ; Definicja Tarskiego : Zbiór jest ''skończony'' wtedy i tylko wtedy, gdy każda niepusta [[rodzina zbiorów|rodzina]] jego podzbiorów ma [[Elementy minimalny i maksymalny|element maksymalny]] ze względu na relację [[podzbiór|inkluzji]]<ref>Zbiór pusty jest skończony w sensie definicji Tarskiego, gdyż spełnia on ją „w próżni”: zbiór pusty nie ma niepustej rodziny podzbiorów, zatem każda z nich ma element maksymalny ze względu na zawieranie.</ref>.
 ; Definicja Dedekinda : Zbiór nazywa się ''skończonym'', gdy nie jest równoliczny z żadnym swoim [[podzbiór|podzbiorem właściwym]], tzn. nie istnieje funkcja zbioru w siebie, która byłaby [[funkcja różnowartościowa|iniekcją]] (różnowartościowa), lecz nie byłaby [[funkcja "na"|suriekcją]] („na”)<ref>Warunek definicji Dedekinda, podobnie jak w definicji Tarskiego, jest również spełniony „w próżni” dla zbioru pustego, gdyż zbiór pusty nie ma podzbiorów właściwych, zatem żaden podzbiór właściwy zbioru pustego nie jest z nim równoliczny.</ref>.