Dziedzicznie zbiór skończony - Hereditarily finite set

W matematyce i teorii zbiorów , dziedzicznie skończonych zestawy są zdefiniowane jako ograniczonych zestawach , których elementy są dziedzicznie skończonych odbiorników. Innymi słowy, sam zbiór jest skończony, a wszystkie jego elementy są zbiorami skończonymi, rekurencyjnie aż do zbioru pustego.

Formalna definicja

Rekurencyjna definicja uzasadnionych zbiorów dziedzicznie skończonych jest następujący:

Przypadek podstawowy : zbiór pusty jest zbiorem dziedzicznie skończonym.

Reguła rekurencji : Jeśli a ₁ ,..., a _k są dziedzicznie skończone, to tak samo jest { a ₁ ,..., a _k }.

Zbiór jest przykładem takiego dziedzicznie skończonego zbioru, podobnie jak zbiór pusty . Z drugiej strony zbiory lub są przykładami zbiorów skończonych, które nie są dziedzicznie skończone. Na przykład pierwszy nie może być dziedzicznie skończony, ponieważ zawiera jako element co najmniej jeden zbiór nieskończony, gdy . ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$${\displaystyle \emptyset =\{\}}$${\ Displaystyle \ {7, {\ mathbb {N}}, \ pi \}}$${\ Displaystyle \ {3, \ {{\ mathbb {N}} \} \}}$${\ Displaystyle {\ mathbb {N}} = \ {0,1,2, \ kropki \}}$

Dyskusja

Symbolem klasy dziedzicznie skończonych zbiorów jest , oznaczająca liczność każdego z jej członków mniejszą niż . To, czy jest zbiorem i stwierdzenia o kardynalności, zależą od kontekstu teorii. ${\ Displaystyle H_ {\ aleph _ {0}}}$${\displaystyle \aleph_{0}}$${\ Displaystyle H_ {\ aleph _ {0}}}$

Bijection Ackermanna

Klasa jest policzalna . Ackermann (1937) podał następującą bijekcję naturalną f od liczb naturalnych do , znanego jako kodowanie Ackermanna . Jest definiowany rekursywnie przez ${\ Displaystyle H_ {\ aleph _ {0}}}$${\ Displaystyle H_ {\ aleph _ {0}}}$

${\ Displaystyle f (2 ^ {a} +2 ^ {b} + \ cdots) = \ {f (a), f (b), \ ldots \}}$jeśli a , b , ... są różne.

Np

${\ Displaystyle f (5) = f (4 + 1) = f (2 ^ {2} +2 ^ {0}) = \ {f (2), f (0) \} = \ {f (2 ^) {1}),\{\}\}=\{\{f(1)\},\{\}\}=\{\{f(2^{0})\},\{\}\ }=\{\{\{f(0)\}\},\{\}\}=\{\{\{\{\}\}\},\{\}\}}$

Mamy f ( m ) ∈ f ( n ) wtedy i tylko wtedy, gdy m- ta cyfra binarna n (licząc od prawej, zaczynając od 0) wynosi 1.

Reprezentacja

Ta klasa zbiorów jest naturalnie uszeregowana według liczby par nawiasów niezbędnych do reprezentowania zbiorów:

• ${\ Displaystyle \ {\}}$(tj. liczba porządkowa Neumanna „0”),${\displaystyle \pusty zestaw}$
• ${\displaystyle \{\{\}\}}$(tj. lub , liczba porządkowa Neumanna „1”),${\displaystyle \{\pusty zestaw \}}$${\ Displaystyle \ {0 \}}$
• ${\displaystyle \{\{\{\}\}\}}$,
• ${\displaystyle \{\{\{\{\}\}\}\}}$a następnie także (tj. liczba porządkowa Neumanna „2”),${\displaystyle \{\{\},\{\{\}\}\}}$${\ Displaystyle \ {0,1 \}}$
• ${\displaystyle \{\{\{\{\{\}\}\}\}\}}$, jak również ,${\displaystyle \{\{\{\},\{\{\}\}\}\}}$${\displaystyle \{\{\},\{\{\{\}\}\}\}}$
• ... zbiory reprezentowane parami nawiasów, np. ,${\ Displaystyle 6}$${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$
• ... zbiory reprezentowane parami nawiasów, np. ,${\ Displaystyle 7}$${\displaystyle \{\{\{\{\{\{\{\}\}\}\}\}\}\}}$
• ... zbiory reprezentowane przez pary nawiasów, np. lub (tzn. liczba porządkowa Neumanna „3”)${\ Displaystyle 8}$${\displaystyle \{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}}$${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}$${\ Displaystyle \ {0,1,2 \}}$
• ...itp.

W ten sposób liczba zestawów z parami nawiasów wynosi${\ Displaystyle n}$${\ Displaystyle 1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,\kropki}$

Aksjomatyzacje

Teorie zbiorów skończonych

Zbiór reprezentuje również pierwszą liczbę porządkową von Neumanna , oznaczoną . I rzeczywiście, wszystkie skończone liczby porządkowe von Neumanna należą do klasy zbiorów reprezentujących liczby naturalne, czyli zawiera każdy element w standardowym modelu liczb naturalnych . Robinson arytmetyka może już być interpretowane w ST , bardzo mały sub-theory of z aksjomatów podanych przez ekstensjonalności , zbiór pusty i Adjunction . ${\displaystyle \pusty zestaw}$${\ Displaystyle 0}$${\ Displaystyle H_ {\ aleph _ {0}}}$${\ Displaystyle Z ^ {-}}$

Rzeczywiście, ma konstruktywne aksjomatyzacje obejmujące te aksjomaty i np. Indukcję zbioru i Zastąpienie . ${\ Displaystyle H_ {\ aleph _ {0}}}$

Ich modele spełniają wówczas również aksjomaty składające się z aksjomatów teorii mnogości Zermelo-Fraenkla bez aksjomatu nieskończoności . W tym kontekście można dodać negację aksjomatu nieskończoności, dowodząc tym samym, że aksjomat nieskończoności nie jest konsekwencją innych aksjomatów teorii mnogości.

ZF

Zbiory dziedzicznie skończone stanowią podklasę wszechświata Von Neumanna . Tutaj klasę wszystkich dobrze uzasadnionych zbiorów dziedzicznie skończonych oznaczamy V _ω . Zauważ, że jest to również zestaw w tym kontekście.

Jeśli oznaczymy przez ℘ ( S ) z zestawem zasilania z S , i V ₀ pustego zestawu, a V _ω mogą być uzyskane przez ustawienie V ₁ = ℘ ( V ₀ ) V ₂ = ℘ ( V ₁ ) .. ., V _k = ℘( V _{k -1} ),... i tak dalej.

Zatem V _ω można wyrazić jako . ${\ Displaystyle V_ {\ omega} = \ bigcup _ {k = 0} ^ {\ infty} V_ {k}}$

Widzimy ponownie, że istnieje tylko przeliczalnie wiele zbiorów dziedzicznie skończonych: V _n jest skończone dla dowolnego skończonego n , jego kardynalność wynosi ^{n -1} 2 (patrz tetracja ), a suma przeliczalnie wielu zbiorów skończonych jest policzalna.

Równoważnie zbiór jest dziedzicznie skończony wtedy i tylko wtedy, gdy jego zamknięcie przechodnie jest skończone.

Modele wykresów

Klasa może być postrzegana jako dokładnie korespondująca z klasą drzew ukorzenionych , a mianowicie tych bez nietrywialnych symetrii (tj. jedynym automorfizmem jest tożsamość): Wierzchołek korzenia odpowiada nawiasowi najwyższego poziomu, a każda krawędź prowadzi do elementu (kolejny taki zestaw), który może działać jako wierzchołek główny sam w sobie. Nie istnieje automorfizm tego grafu, co odpowiada faktowi, że identyfikowane są równe gałęzie (np. trywializacja permutacji dwóch podgrafów kształtu ). Ten model grafowy umożliwia implementację ZF bez nieskończoności jako typów danych, a tym samym interpretację teorii mnogości w ekspresyjnych teoriach typów . ${\ Displaystyle H_ {\ aleph _ {0}}}$${\ Displaystyle \ {\ kropki \}}$${\ Displaystyle \ {t, t, s\} = \ {t, s \}}$${\displaystyle t}$

Modele grafowe istnieją dla ZF, a także teorie zbiorów różniące się od teorii zbiorów Zermelo, takie jak teorie nieuzasadnione . Takie modele mają bardziej skomplikowaną strukturę krawędzi.

W teorii grafów grafem, którego wierzchołki odpowiadają dziedzicznie skończonym zbiorom, a krawędziom przynależności do zbioru, jest graf Rado lub graf losowy.

Zobacz też

• Zestaw dziedziczny
• Zestaw dziedzicznie policzalny
• Własność dziedziczna
• Ukorzenione drzewa
• Konstruktywna teoria mnogości
• Skończony zbiór

Bibliografia

• Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen , 114 (1): 305-315, doi : 10.1007/BF01594179 , S2CID  120576556