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

Usunięte 23 bajty ,  7 lat temu
drobne redakcyjne
(zbiór liczb naturalnych {0,..,n-1} -> podzbiór liczb naturalnych postaci {0,...,n-1})
(drobne redakcyjne)
{{spis treści}}
'''Zbiór skończony''' − w [[matematyka|matematyce]] [[zbiór]] o skończonej liczbie elementów lub dokładniej: zbiór skończonej [[moc zbioru|mocy]], tzn. mocy mniejszej od [[skala alefów|pierwszej nieskończonej liczby kardynalnej]] <math>\scriptstyle \aleph_0</math> (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 [[kombinatoryka|kombinatoryką]], pośrednio zajmują się nim również [[teoria liczb]] oraz [[Kryptologia|kryptografia]], w ogólności zbiory jako takie bada się w [[teoria mnogości|teorii mnogości]]. Bliskim pojęciem zbioru skończonego jest [[ciąg (matematyka)|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świat|wszechświecie]], którą szacuje się na ok. <math>\scriptstyle 10^{80}</math> (zob. [[widzialny wszechświat]]; wymiary [[wszechświat]]a mogą być nieskończone) – z jednej strony wynika to ze skończonej podzielności [[Materia (fizyka)|materii]] (zob. [[kwant]]), a z drugiej ze skończonej [[prędkość światła|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ą [[Arystoteles]]a operowano wyłącznie zbiory skończone traktując nieskończoność jako proces, który można w razie potrzeby bez przeszkód kontynuować (w [[geometria euklidesowa#Aksjomaty Euklidesa|geometrii euklidesowej]] [[prosta]] traktowana była jako [[odcinek]], który można było nieograniczenie przedłużać); przełom przyniosły prace [[Georg Cantor|Georga Cantora]], który potraktował zbiory nieskończone jako osobne byty o własnej hierarchii (zob. [[nieskończoność|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 [[finityzm]]u, [[konstruktywizm (matematyka)|konstruktywizmu]], czy [[intuicjonizm (matematyka)|intuicjonizmu]] odrzucających pojęcie nieskończoności aktualnej (zob. [[aksjomat nieskończoności|aksjomat Cantora]], nazywany też aksjomatem nieskończoności<ref>Aksjomat ten wzbudza kontrowersje, gdyż jest niezależny od pozostałych [[aksjomaty Zermelo-Fraenkela|aksjomatów Zermelo-Fraenkela]] [[teoria mnogości|teorii mnogości]] – również [[aksjomat wyboru|aksjomatu wyboru]] – o ile są one [[niesprzeczność|niesprzeczne]] (zob. [[twierdzenie Gödla]]).</ref>).
 
== Definicje formalne ==
{{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 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>.
; Definicja Dedekinda (alternatywna 1) : Zbiór jest ''skończony'', gdy nie istnieje [[funkcja różnowartościowa]] zbioru liczb naturalnych w ten zbiór<ref>Por. [[zasada szufladkowa Dirichleta]].</ref>.
; Definicja Dedekinda (alternatywna 2) : Zbiór jest ''skończony'', gdy nie zawiera [[zbiór przeliczalny|zbioru przeliczalnie nieskończonego]].
 
Definicje pochodzące od [[Alfred Tarski|Alfreda Tarskiego]] i [[Richard Dedekind|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 [[Georg Cantor|Georga Cantora]] (a więc do XIX wieku) niemal powszechnie przyjmowane jako równoważne definicji naturalnej. Na gruncie [[aksjomaty Zermelo-Fraenkela|aksjomatyki Zermelo-Fraenkela]] (ZF, bez [[aksjomat wyboru|aksjomatu wyboru]] AC) [[teoria mnogości|teorii mnogości]] równoważne są definicje naturalna i Tarskiego, równoważne są wtedy także warianty definicji Dedekinda. Na mocy [[indukcja matematyczna|zasady indukcji]] definicja naturalna pociąga za sobą definicję Dedekinda, jednak pociąganie w drugą stronę wymaga użycia [[aksjomat wyboru|aksjomatu wyboru]] (AC), a przynajmniej [[zasada wyborów zależnych|aksjomatu wyborów zależnych]] (DC).