Rodzina zestawów - Family of sets
W teorii mnogości i pokrewnych dziedzin matematyki , zbiór F z podzbiorów danego ustawionej S nazywamy rodzinę podzbiorów z S , lub rodziny zbiorów ponad S . Bardziej ogólnie, zbiór dowolnych zbiorów nazywany jest rodziną zbiorów lub zbiorem-rodziną lub zbiorem-systemem .
Termin „zbiór” jest tutaj używany, ponieważ w niektórych kontekstach rodzina zestawów może zawierać powtarzające się kopie danego elementu, aw innych kontekstach może tworzyć odpowiednią klasę, a nie zestaw.
Skończona rodzina podzbiorów zbioru skończonego S nazywana jest również hipergrafem .
Przykłady
- Zestaw mocy P ( S ) to rodzina zestawów ponad S .
- K -subsets S ( k ) o zadanej S (czyli podzbiór S z liczbą elementów podzestawu danych, co K ) tworzą rodzinę zestawy.
- Niech S = {a,b,c,1,2}, przykład rodziny zbiorów nad S (w sensie wielozbiorowym ) jest dany przez F = {A 1 , A 2 , A 3 , A 4 } gdzie A 1 = {a,b,c}, A 2 = {1,2}, A 3 = {1,2} i A 4 = {a,b,1}.
- Klasa Ord wszystkich liczb porządkowych to duża rodzina zbiorów; oznacza to, że sam w sobie nie jest zbiorem, lecz właściwą klasą .
Nieruchomości
- Każda rodzina podzbiorów S sama jest podzbiorem zbioru potęgowego P ( S ), jeśli nie ma powtarzających się elementów.
- Każda rodzina zbiorów bez powtórzeń jest podklasą właściwej klasy V wszystkich zbiorów ( wszechświata ).
- Twierdzenie Halla o małżeństwie , za sprawą Philipa Halla , daje konieczne i wystarczające warunki, aby skończona rodzina niepustych zbiorów (dozwolone powtórzenia) miała system odrębnych przedstawicieli .
Pojęcia pokrewne
Pewne typy obiektów z innych dziedzin matematyki są równoważne rodzinom zbiorów, ponieważ można je opisać wyłącznie jako zbiór zbiorów obiektów pewnego typu:
- Hipergraf , zwany również zestaw system jest utworzony przez zbiór wierzchołków wraz z innym zestawem hyperedges , z których każdy może być dowolny zestaw. Hipergrafy hipergrafu tworzą rodzinę zbiorów, a każdą rodzinę zbiorów można interpretować jako hipergraf, którego wierzchołkami jest suma zbiorów.
- Streszczenie symplicjalnego kompleks jest kombinatoryczne abstrakcja pojęcie kompleksu symplicjalnego , kształtu utworzonego przez związki odcinków, trójkątów, czworościanów i wyższych wymiarów simplices dołączył twarzą w twarz. W abstrakcyjnym kompleksie symplicjalnym każdy sympleks jest reprezentowany po prostu jako zbiór jego wierzchołków. Każda rodzina zbiorów skończonych bez powtórzeń, w której podzbiory dowolnego zbioru w rodzinie również należą do rodziny, tworzy abstrakcyjny kompleks symplicjalny.
- Struktura częstość składa się ze zbioru punktów , zestaw linii , i (arbitralne) związku binarnego , zwany stosunek występowania , określający, które punkty należą do której linii. Strukturę incydencyjną można określić za pomocą rodziny zbiorów (nawet jeśli dwie różne proste zawierają ten sam zbiór punktów), zbiory punktów należących do każdej prostej iw ten sposób można interpretować dowolną rodzinę zbiorów jako strukturę incydencyjną.
- Binarny kod blokowy składa się z zestawu słów kodowych, z których każde jest ciągiem zer i jedynek o tej samej długości. Gdy każda para słów kodowych ma dużą odległość Hamminga , może być używana jako kod korygujący błędy . Kod blokowy można również opisać jako rodzinę zestawów, opisując każde słowo kodowe jako zestaw pozycji, w których zawiera 1.
- Topologiczna miejsca składa się z dwóch, τ (X), gdzie X jest zestaw (zwane punkty ) i τ to seria zestawów (zwane otwarte zestawy ) nad X τ muszą zawierać zarówno zbiór pusty i sam X i jest zamknięta pod zbiorem zbioru i przecięciem zbioru skończonego.
Specjalne typy rodzin zestawów
Rodzina Spernera to rodzina zestawów, w której żaden z zestawów nie zawiera żadnego z pozostałych. Twierdzenie Spernera ogranicza maksymalny rozmiar rodziny Spernera.
Rodzina Helly to rodzina zbiorowa , w której każda minimalna podrodzina z pustym przecięciem ma ograniczony rozmiar. Twierdzenie Helly mówi, że zbiory wypukłe w przestrzeniach euklidesowych o ograniczonym wymiarze tworzą rodziny Helly.
Streszczenie symplicjalnego kompleks to zestaw mieszkaniami F , która jest w dół zamknięte , czyli każdy podzbiór zbioru w F jest także w F . Matroid jest abstrakcyjną symplicjalnego kompleks z dodatkową właściwość zwaną własność powiększania .
Rodziny zestawów ponad | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Koniecznie zamknięte pod : |
FIP |
Wyreżyserowane przez |
|||||||||||
Klasa monotoniczna | |||||||||||||
π -system | |||||||||||||
-system ( system Dynkin) | |||||||||||||
Pierścień (teoria porządku) | |||||||||||||
Pierścień (teoria miary) | |||||||||||||
δ-Pierścień | |||||||||||||
𝜎-Pierścień | |||||||||||||
Algebra (pole) | |||||||||||||
𝜎-Algebra (𝜎-Pole) | |||||||||||||
Podwójny ideał | |||||||||||||
Filtr | |||||||||||||
Filtr wstępny (Podstawa filtra) | |||||||||||||
Filtr podrzędny | |||||||||||||
Koniecznie zamknięte pod : |
skończone skrzyżowania |
policzalne malejące przecięcia |
policzalne skrzyżowania |
Właściwość przecięcia skończonego |
Skierowany w dół |
skończone związki |
policzalne rozłączne związki |
policzalne rosnące związki |
policzalne związki |
komplementy |
względne dopełnienia |
zawiera | zawiera |
Zakłada się, że wszystkie rodziny nie są puste. są dowolnymi elementami z oznacza unię parami rozłącznych zbiorów (zwaną unią rozłączną ).
Dodatkowo semialgebra lub semiring jest π -system gdzie każdy uzupełnieniem jest równe skończonej suma rozłączna zbiorów w |
Zobacz też
- Algebra zbiorów
- Klasa (teoria mnogości)
- Projekt kombinatoryczny
- δ-pierścień
- Pole zestawów
- Zindeksowana rodzina
- System λ (system Dynkina)
- π-system
- Pierścień zestawów
- Paradoks Russella (lub Zbiór zestawów, które nie zawierają samych siebie )
- σ-algebra
- σ-pierścień
Uwagi
Bibliografia
- Biggs, Norman L. (1985), Matematyka dyskretna , Oxford: Clarendon Press, ISBN 0-19-853252-0
- Brualdi, Richard A. (2010), wprowadzające kombinatoryka (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-602040-2
- Roberts, Fred S.; Tesman, Barry (2009), kombinatoryka stosowana (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
Zewnętrzne linki
- Multimedia związane z rodzinami Setów w Wikimedia Commons