Zestaw zagnieżdżony - Nested set

Zagnieżdżony zestaw z rosyjskich lalek .

Zestaw zagnieżdżony reprezentujący przykład taksonomii biologicznej . Na zewnątrz: porządek, rodzina, rodzaj, gatunek.

W naiwnych teorii zbiorów , A zagnieżdżony zbiór jest zbiorem zawierającym łańcuch z podzbiorów, tworząc strukturę hierarchiczną, jak rosyjskie lalki .

Jest on stosowany jako odniesienia-koncepcji we wszystkich naukowych hierarchii definicji, a wiele rozwiązań technicznych, takich jak drzewa w obliczeniowych struktur danych lub model zbiorów zagnieżdżonych z relacyjnych baz danych .

Czasami pojęcie jest mylone z „zbiorem zbiorów” o własności dziedzicznej (jak skończoność w dziedzicznie skończonym zbiorze ).

Formalna definicja

Niektórzy autorzy wolą używać terminu Kolekcja zestawów zagnieżdżonych , ponieważ jest to formalna definicja zbiorowej właściwości wielu zestawów. Inni wolą klasyfikować tę relację jako kolejność włączenia . Kolekcja to „zestaw zestawów”.

Niech B będzie zbiorem niepustym, a C zbiorem podzbiorów B . Wtedy C jest zbiorem zagnieżdżonym, jeśli:

• ${\ Displaystyle B \ w C}$(i )${\ Displaystyle \ pusty zestaw \ notin C}$
• ${\ Displaystyle \ forall H, K \ w C ~: ~ H \ czapka K \ neq \ pusty zbiór ~ \ Strzałka w prawo ~ H \ podzbiór K ~ \ lub ~ K \ podzbiór H}$

Pierwszy warunek określa, że ​​zestaw B , który zawiera wszystkie elementy dowolnego podzbioru, musi należeć do kolekcji zestawów zagnieżdżonych. Niektórzy autorzy twierdzą również, że B nie jest puste lub puste nie jest podzbiorem C .

Drugi warunek stwierdza, że ​​przecięcie każdej pary zestawów w kolekcji zestawów zagnieżdżonych nie jest zestawem pustym tylko wtedy, gdy jeden zestaw jest podzbiorem drugiego.

W szczególności podczas skanowania wszystkich par podzbiorów w drugim warunku jest to prawdziwe dla dowolnej kombinacji z B .

Przykład

Wyrażenie przykładu jako częściowo uporządkowanego zestawu przez jego diagram Hassego .

Używając zestawu pierwiastków atomowych , tak jak zestaw kart do gry pasuje :

B = {♠, ♥, ♦, ♣};     B ₁ = {♠, ♥};   B ₂ = {♦, ♣};   B ₃ = {♣};
C = { B , B ₁ , B ₂ , B ₃ }.

Drugi warunek (definicji formalnej) można sprawdzić łącząc wszystkie pary:

B ₁ ∩ B ₂ = ∅;  B ₁ ∩ B ₃ = ∅;  B ₃ ⊂ B ₂ .

Istnieje hierarchia, którą można wyrazić za pomocą dwóch gałęzi i jej zagnieżdżonego porządku:   B ₃ ⊂ B ₂ ⊂ B ;  B ₁ ⊂ B .

Koncepcje pochodne

Jako zbiory, które są ogólną abstrakcją i podstawą wielu pojęć, zbiór zagnieżdżony jest podstawą „hierarchii zagnieżdżonej”, „hierarchii zawierania” i innych.

Hierarchia zagnieżdżona

Hierarchia zagnieżdżona lub hierarchia włączenia to hierarchiczna kolejność zestawów zagnieżdżonych . Przykładem koncepcji gniazdowania są rosyjskie lalki matrioszki . Każda lalka jest otoczona przez inną lalkę, aż do zewnętrznej lalki. Lalka zewnętrzna zawiera wszystkie lalki wewnętrzne, następna lalka zewnętrzna zawiera wszystkie pozostałe lalki wewnętrzne i tak dalej. Matrioszki reprezentują zagnieżdżoną hierarchię, w której każdy poziom zawiera tylko jeden obiekt, tj. jest tylko jeden z każdego rozmiaru lalki; uogólniona hierarchia zagnieżdżona dopuszcza wiele obiektów na poziomach, ale każdy obiekt ma tylko jednego rodzica na każdym poziomie. Ilustrowanie ogólnej koncepcji:

${\ Displaystyle {\ tekst {kwadrat}} \ podzbiór {\ tekst {czworokąt}} \ podzbiór {\ tekst {wielokąt}} \ podzbiór {\ tekst {kształt}} \,}$

Kwadrat można zawsze nazwać czworobokiem, wielokątem lub kształtem. W ten sposób jest to hierarchia. Rozważ jednak zbiór wielokątów używający tej klasyfikacji. Kwadrat może być tylko czworobokiem; nigdy nie może być trójkątem , sześciokątem itp.

Hierarchie zagnieżdżone to schematy organizacyjne leżące u podstaw taksonomii i klasyfikacji systematycznych. Na przykład, używając oryginalnej taksonomii Linneusza (wersji, którą przedstawił w 10. wydaniu Systema Naturae ), człowieka można sformułować jako:

${\ Displaystyle {\ tekst {H. sapiens}}\subset {\text{Homo}}\subset {\text{Naczelne}}\subset {\text{Mammalia}}\subset {\text{Animalia}}}$

Taksonomie mogą się często zmieniać (jak widać w taksonomii biologicznej ), ale podstawowa koncepcja hierarchii zagnieżdżonych jest zawsze taka sama.

Hierarchia powstrzymywania

Hierarchia zawierania jest bezpośrednią ekstrapolacją koncepcji hierarchii zagnieżdżonej . Wszystkie uporządkowane zestawy są nadal zagnieżdżone, ale każdy zestaw musi być „ ścisły ” — żadne dwa zestawy nie mogą być identyczne. Powyższy przykład kształtów można zmodyfikować, aby to zademonstrować:

${\displaystyle {\text{kwadrat}}\subsetneq {\text{czworokąt}}\subsetneq {\text{wielobok}}\subsetneq {\tekst{kształt}}\,}$

Notacja oznacza, że x jest podzbiorem y, ale nie jest równe  y . ${\displaystyle x\subsetneq y\,}$

Ograniczanie hierarchia jest stosowany w klasie dziedziczenie z programowania obiektowego .

Zobacz też

• Zestaw dziedzicznie policzalny
• Własność dziedziczna
• Hierarchia (matematyka)
• Zagnieżdżony model zbioru do przechowywania informacji hierarchicznych w relacyjnych bazach danych

Bibliografia