Zbiór skończony - Finite set

W matematyce (szczególnie w teorii mnogości ) zbiór skończony to zbiór, który ma skończoną liczbę elementów . Nieformalnie zbiór skończony to zbiór, który w zasadzie można by policzyć i zakończyć liczenie. Na przykład,

to skończony zbiór pięciu elementów. Liczba elementów zbioru skończonego jest liczbą naturalną ( nieujemną liczbą całkowitą ) i nazywana jest mocą zbioru. Zbiór, który nie jest skończony nazywamy nieskończonym . Na przykład zbiór wszystkich dodatnich liczb całkowitych jest nieskończony:

Zbiory skończone są szczególnie ważne w kombinatoryce , matematycznej nauce liczenia . Wiele argumentów dotyczących zbiorów skończonych opiera się na zasadzie szufladki , która mówi, że nie może istnieć funkcja iniektywna z większego zbioru skończonego do mniejszego zbioru skończonego.

Definicja i terminologia

Formalnie zbiór S nazywamy skończonym, jeśli istnieje bijekcja

dla pewnej liczby naturalnej n . Liczba n to moc zbioru, oznaczona jako | S | . Zbiór pusty {} albo ∅ jest uważany za ograniczony z liczności zerowego.

Jeśli zbiór jest skończony, jego elementy można zapisać — na wiele sposobów — w sekwencji :

W kombinatoryki , skończony zestaw z n elementów jest czasami nazywany n -Set i podgrupa o k elementów jest nazywany K -subset . Na przykład zbiór {5,6,7} jest zbiorem trójek – skończonym zbiorem trzech elementów – a {6,7} jest jego podzbiorem 2.

(Osoby zaznajomione z definicją samych liczb naturalnych jako konwencjonalną w teorii mnogości, tzw. konstrukcją von Neumanna , mogą preferować istnienie bijekcji , która jest równoważna.)

Podstawowe właściwości

Każdy podzbiór właściwy zbioru skończonego S jest skończony i zawiera mniej elementów niż samo S. W konsekwencji nie może istnieć bijekcja między zbiorem skończonym S a podzbiorem właściwym zbioru S . Każdy zestaw z tą właściwością nazywa się Dedekind-finite . Używając standardowych aksjomatów ZFC dla teorii mnogości , każdy zbiór Dedekind-skończony jest również skończony, ale tej implikacji nie można udowodnić w samym ZF (aksjomaty Zermelo-Fraenkla bez aksjomatu wyboru ). Aksjomat wyboru policzalnych , słaba wersja aksjomatu wyboru, wystarczy udowodnić tę równoważność.

Każda funkcja iniekcyjna między dwoma skończonymi zbiorami o tej samej kardynalności jest również funkcją surjektywną (surjekcją). Podobnie każda surjekcja między dwoma skończonymi zbiorami o tej samej kardynalności jest również zastrzykiem.

Unia dwóch zbiorów skończonych jest skończony, z

W rzeczywistości, zgodnie z zasadą włączenia-wykluczenia :

Bardziej ogólnie, suma dowolnej skończonej liczby zbiorów skończonych jest skończona. Iloczyn kartezjański zbiorów skończonych jest skończony, z:

Podobnie iloczyn kartezjański skończenie wielu zbiorów skończonych jest skończony. Skończony zbiór składający się z n elementów ma 2 n odrębnych podzbiorów. Oznacza to, że zbiór potęgowy zbioru skończonego jest skończony o mocy 2 n .

Każdy podzbiór zbioru skończonego jest skończony. Zbiór wartości funkcji po zastosowaniu do elementów zbioru skończonego jest skończony.

Wszystkie zbiory skończone są policzalne , ale nie wszystkie zbiory policzalne są skończone. (Niektórzy autorzy jednak używają słowa „policzalny” w znaczeniu „przeliczalnie nieskończony”, więc nie uważaj zbiorów skończonych za policzalne.)

Darmo semilattice ciągu skończonego zbioru jest zbiorem jej niepustych podzbiorów, z przyłączyć operacja jest podana przez zadanej unii.

Warunki konieczne i wystarczające dla skończoności

W teorii mnogości Zermelo-Fraenkla bez aksjomatu wyboru (ZF) wszystkie następujące warunki są równoważne:

  1. S jest zbiorem skończonym. Oznacza to, że S można umieścić w korespondencji jeden do jednego ze zbiorem tych liczb naturalnych mniejszym niż pewna konkretna liczba naturalna.
  2. ( Kazimierz Kuratowski ) S ma wszystkie własności, które można udowodnić indukcją matematyczną zaczynając od zbioru pustego i dodając jeden nowy element na raz. (Patrz poniżej dla teorii mnogości sformułowania skończoności Kuratowskiego.)
  3. ( Paul Stäckel ) S można nadać całkowite uporządkowanie, które jest uporządkowane zarówno do przodu, jak i do tyłu. Oznacza to, że każdy niepusty podzbiór S ma zarówno najmniejszy, jak i największy element w podzbiorze.
  4. Każda funkcja jeden do jednego z P ( P ( S )) do siebie jest na . Oznacza to, że powerset powerset S jest Dedekind-skończony (patrz niżej).
  5. Każda funkcja surjektywna od P ( P ( S )) do siebie jest równa jeden do jednego.
  6. ( Alfred Tarski ) Każda niepusta rodzina podzbiorów S ma minimalny element w odniesieniu do inkluzji. (Równoważnie każda niepusta rodzina podzbiorów S ma maksymalny element w odniesieniu do włączenia.)
  7. S może być dobrze uporządkowane, a dowolne dwa dobrze uporządkowane na nim są uporządkowane izomorficznie . Innymi słowy, prawidłowe uporządkowania na S mają dokładnie jeden typ zamówienia .

Jeśli aksjomat wyboru jest również założyć (the aksjomat wyboru policzalnych wystarczy), to następujące warunki są równoważne:

  1. S jest zbiorem skończonym.
  2. ( Richard Dedekind ) Każda funkcja jeden do jednego z S do siebie jest na.
  3. Każda funkcja surjektywna od S do siebie jest jeden do jednego.
  4. S jest pusty lub co porządek częściowy z S zawiera element maksymalny .

Kwestie podstawowe

Georg Cantor zapoczątkował swoją teorię zbiorów w celu matematycznego traktowania zbiorów nieskończonych. Tak więc rozróżnienie między skończonym a nieskończonym leży u podstaw teorii mnogości. Niektórzy fundamentaliści, surowi finityści , odrzucają istnienie zbiorów nieskończonych i tym samym zalecają matematykę opartą wyłącznie na zbiorach skończonych. Matematycy głównego nurtu uważają ścisły finizm za zbyt ograniczający, ale uznają jego względną spójność: wszechświat dziedzicznie skończonych zbiorów stanowi model teorii mnogości Zermelo-Fraenkla z aksjomatem nieskończoności zastąpionym przez jego negację.

Nawet dla tych matematyków, którzy przyjmują zbiory nieskończone, w pewnych ważnych kontekstach formalne rozróżnienie między skończonym a nieskończonym może pozostać sprawą delikatną. Trudność wynika z twierdzeń Gödla o niezupełności . Można interpretować teorię dziedzicznych zbiorów skończonych w ramach arytmetyki Peano (i na pewno również odwrotnie), więc niekompletność teorii arytmetyki Peano implikuje teorię dziedzicznych zbiorów skończonych. W szczególności istnieje mnóstwo tzw. niestandardowych modeli obu teorii. Pozornym paradoksem jest to, że istnieją niestandardowe modele teorii dziedzicznie skończonych zbiorów, które zawierają zbiory nieskończone, ale te nieskończone zbiory z wewnątrz modelu wyglądają na skończone. (Może się to zdarzyć, gdy w modelu brakuje zbiorów lub funkcji niezbędnych do obserwacji nieskończoności tych zbiorów.) Ze względu na twierdzenia o niezupełności, żaden predykat pierwszego rzędu, ani nawet żaden rekurencyjny schemat predykatów pierwszego rzędu nie może scharakteryzować standardu. część wszystkich takich modeli. Tak więc, przynajmniej z punktu widzenia logiki pierwszego rzędu, można mieć jedynie nadzieję na opisanie skończoności w przybliżeniu.

Mówiąc bardziej ogólnie, pojęcia nieformalne, takie jak zbiór, a szczególnie zbiór skończony, mogą być interpretowane w szeregu systemów formalnych różniących się ich aksjomatykami i aparatem logicznym. Najbardziej znane aksjomatycznej teorii należą aksjomaty zermelo-fraenkela (ZF), aksjomaty zermelo-fraenkela z aksjomatu wyboru (ZFC), Von Neumann-Bernays-Gödel teoria mnogości (NBG), Non-uzasadnionej teorii mnogości , Bertrand Russell „s Typ teoria i wszystkie teorie ich różnych modeli. Można też wybierać pomiędzy klasyczną logiką pierwszego rzędu, różnymi logikami wyższego rzędu oraz logiką intuicjonistyczną .

Formalista może zobaczyć sens ustawionej waha się od systemu do systemu. Niektórzy platonicy mogą postrzegać poszczególne systemy formalne jako przybliżające leżącą u ich podłoża rzeczywistość.

Mnogościowe definicje skończoności

W kontekstach, w których pojęcie liczby naturalnej znajduje się logicznie przed jakimkolwiek pojęciem zbioru, można zdefiniować zbiór S jako skończony, jeśli S dopuszcza bijekcję do pewnego zbioru liczb naturalnych o postaci . Matematycy częściej wybierają podstawy pojęć liczby w teorii mnogości , na przykład mogą modelować liczby naturalne według typów uporządkowanych skończonych zbiorów dobrze uporządkowanych . Takie podejście wymaga strukturalnej definicji skończoności, która nie zależy od liczb naturalnych.

Różne własności, które wyróżniają zbiory skończone spośród wszystkich zbiorów w teorii ZFC, okazują się logicznie nierównoważne w słabszych systemach, takich jak ZF lub intuicjonistyczne teorie zbiorów. W literaturze poczesne miejsce zajmują dwie definicje, jedna autorstwa Richarda Dedekinda , druga dla Kazimierza Kuratowskiego . (Definicja Kuratowskiego jest użyta powyżej.)

Zbiór S nazywamy Dedekind nieskończonym, jeśli istnieje iniektywna, niesuriektywna funkcja . Taka funkcja wykazuje bijekcję między S a odpowiednim podzbiorem S , czyli obrazem f . Mając nieskończony zbiór Dedekind S , funkcję f i element x , którego nie ma na obrazie f , możemy utworzyć nieskończoną sekwencję odrębnych elementów S , mianowicie . Odwrotnie, biorąc pod uwagę sekwencja S składa się z różnych elementów , można określić funkcję F tak, że na elementy w sekwencji i f zachowuje się jak funkcja tożsamości inaczej. Tak więc zbiory nieskończone Dedekinda zawierają podzbiory odpowiadające bijektywnie liczbom naturalnym. Dedekind finite oznacza naturalnie, że każda iniekcyjna samomapa jest również surjektywna.

Skończoność Kuratowskiego definiuje się następująco. Biorąc pod uwagę dowolny zbiór S , binarna operacja unii nadaje powersetowi P ( S ) strukturę półsieci . Pisząc K ( S ) dla podsemilattyki generowanej przez zbiór pusty i singletony, nazwijmy zbiór S Kuratowski skończonym, jeśli samo S należy do K ( S ). Intuicyjnie K ( S ) składa się z ograniczonymi podzbiorów S . Co najważniejsze, nie potrzeba indukcji, rekurencji ani definicji liczb naturalnych, aby zdefiniować generowane przez, ponieważ można uzyskać K ( S ) po prostu biorąc przecięcie wszystkich podsemilatacji zawierających zbiór pusty i singletony .

Czytelnicy niezaznajomieni z półsieciami i innymi pojęciami algebry abstrakcyjnej mogą preferować całkowicie elementarne sformułowanie. Skończone oznacza Kuratowskiego S leży w zbiorze K ( S ), skonstruowanym w następujący sposób. Napisz M dla zbioru wszystkich podzbiorów X z P ( S ) takiego, że:

  • X zawiera pusty zbiór;
  • Dla każdego zbioru T w P ( S ), jeśli X zawiera T, to X zawiera również sumę T z dowolnym singletonem.

Następnie K ( S ) może być określona jako przecięcie M .

W ZF Kuratowski skończony implikuje Dedekind skończony, ale nie odwrotnie. W żargonie popularnego sformułowania pedagogicznego, gdy aksjomat wyboru zawodzi, można mieć nieskończoną rodzinę skarpet, w których nie ma możliwości wyboru jednej skarpetki z więcej niż skończenie wielu par. To sprawiłoby, że zestaw takich skarpet Dedekind byłby skończony: nie może być nieskończonego ciągu skarpet, ponieważ taki ciąg pozwalałby na wybór jednej skarpetki na nieskończenie wiele par, wybierając pierwszą skarpetkę w ciągu. Jednak skończoność Kuratowskiego zawiedzie dla tego samego kompletu skarpetek.

Inne koncepcje skończoności

W teorii mnogości ZF bez aksjomatu wyboru następujące koncepcje skończoności dla zbioru S są odrębne. Są one ułożone w kolejności ściśle malejącej siły, tzn. jeśli zbiór S spełnia kryterium z listy, to spełnia wszystkie poniższe kryteria. W przypadku braku aksjomatu wyboru wszystkie odwrotne implikacje są niedowodliwe, ale jeśli założy się aksjomat wyboru, wszystkie te pojęcia są równoważne. (Zauważ, że żadna z tych definicji nie wymaga zdefiniowania zbioru skończonych liczb porządkowych; wszystkie są czystymi definicjami „mnogościowymi” w kategoriach równości i relacji członkostwa, bez użycia ω).

  • Ja-skończoność . Każdy niepusty zbiór podzbiorów S ma element ⊆-maksymalny. (Jest to równoważne wymaganiu istnienia elementu ⊆-minimalnego. Jest to również równoważne standardowej numerycznej koncepcji skończoności).
  • Ia-skończona . Dla każdego podziału S na dwa zbiory przynajmniej jeden z tych dwóch zbiorów jest ja-skończony.
  • II-skończona . Każdy niepusty ⊆-monotoniczny zbiór podzbiorów S ma ⊆-maksymalny element.
  • III-skończona . Zbiór potęg P ( S ) jest skończony przez Dedekinda.
  • IV-skończona . S to Dedekind skończony.
  • V-skończona . ∣ S ∣ = 0 lub 2⋅∣ S ∣ > ∣ S |.
  • VI-skończona . ∣ S ∣ = 0 lub ∣ S ∣ = 1 lub ∣ S2 > ∣ S ∣.
  • VII-skończona . S to ja-skończony lub niemożliwy do uporządkowania.

Implikacje w przód (od silnego do słabego) to twierdzenia wewnątrz ZF. Kontrprzykłady do odwrotnych implikacji (od słabych do silnych) w ZF z urelementami można znaleźć za pomocą teorii modeli .

Większość z tych definicji skończoności i ich nazwy przypisuje Tarskiemu 1954 przez Howarda i Rubina 1998 , s. 278. Jednak definicje I, II, III, IV i V zostały przedstawione w Tarski 1924 , s. 49, 93, wraz z dowodami (lub odniesieniami do dowodów) dla przyszłych implikacji. W tamtym czasie teoria modeli nie była wystarczająco zaawansowana, aby znaleźć kontrprzykłady.

Każda z własności od I-skończony do IV-skończony jest pojęciem małości w tym sensie, że każdy podzbiór zbioru o takiej własności również będzie miał tę własność. Nie dotyczy to V-skończonych do VII-skończonych, ponieważ mogą one mieć przeliczalnie nieskończone podzbiory.

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne