Operator zamknięcia - Closure operator

W matematyce , A operator konsekwencji na zestaw S jest funkcja z zestawu mocy od S do siebie, który spełnia następujące warunki dla wszystkich zestawów $\operatorname {cl}:{\mathcal {P}}(S)\rightarrow {\mathcal {P}}(S)$ $X,Y\subseteq S$

${\ Displaystyle X \ subseteq \ operatorname {cl} (X)}$	(cl jest obszerne ),
${\ Displaystyle X \ podseteq Y \ Rightarrow \ operatorname {cl} (X) \ podseteq \ operatorname {cl} (Y)}$	(cl jest monotonnym ),
${\ Displaystyle \ nazwa operatora {cl} (\ nazwa operatora {cl} (X)) = \ nazwa operatora {cl} (X)}$	(cl jest idempotentnym ).

Operatory domknięcia są określane przez ich zbiory domknięte , tj. przez zbiory postaci cl( X ), ponieważ domknięcie cl( X ) zbioru X jest najmniejszym zbiorem domkniętym zawierającym X . Takie rodziny „zbiorów domkniętych” są czasami nazywane systemami domknięcia lub „ rodzinami Moore'a ”, na cześć EH Moore'a, który studiował operatory domknięcia w 1910 Wprowadzenie do formy analizy ogólnej , podczas gdy koncepcja domknięcia podzbioru powstała w praca Frigyesa Riesza w związku z przestrzeniami topologicznymi. Idea zamknięcia, choć nie sformalizowana w tamtym czasie, zrodziła się pod koniec XIX wieku dzięki znaczącym wkładom Ernsta Schrödera , Richarda Dedekinda i Georga Cantora .

Operatory zamknięcia są również nazywane „ operatorami kadłuba ”, co zapobiega pomyleniu z „operatorami zamknięcia” badanymi w topologii . Zbiór wraz ze znajdującym się na nim operatorem domknięcia jest czasami nazywany przestrzenią domknięcia .

Aplikacje

Operatorzy zamknięć mają wiele zastosowań:

W topologii operatorami domknięcia są topologiczne operatory domknięcia , które muszą spełniać

{\ Displaystyle \ operatorname {cl} (X_ {1} \ filiżanka \ kropki \ filiżanka X_ {n}) = \ operatorname {cl} (X_ {1}) \ filiżanka \ kropki \ filiżanka \ operatorname {cl} (X_ { n})}

dla wszystkich (Zauważ, że za to daje ). ${\ Displaystyle n \ w \ mathbb {N}}$ $n=0$ $\operatorname {cl} (\varnothing)=\varnothing$

W algebrze i logice wiele operatorów domknięcia jest skończonymi operatorami domknięcia , tj. spełniają one

{\ Displaystyle \ operatorname {cl} (X) = \ bigcup \ lewo \ {\ operatorname {cl} (Y): Y \ subseteq X {\ tekst {i }} Y {\ tekst { skończony}} \ prawo \} .}

W teorii częściowy porządek , które są ważne w teoretycznej informatyki , operator konsekwencji mają bardziej ogólną definicję, która zastępuje się . (Patrz § Operatory zamknięcia w częściowo zamówionych zestawach .) $\subseteq$ $\leq$

Operatory zamknięcia w topologii

Topologiczna zamknięcie podzbioru X o topologii powierzchni składa się z punktów y przestrzeni, tak że każdy sąsiedztwa z y zawiera punkt X . Funkcja, która łączy z każdym podzbiorem X jego zamknięcie, jest topologicznym operatorem zamknięcia. I odwrotnie, każdy operator domknięcia topologicznego na zbiorze powoduje powstanie przestrzeni topologicznej, której zbiory domknięte są dokładnie zbiorami domkniętymi względem operatora domknięcia.

Operatory zamknięcia w algebrze

Operatory domknięcia skończonego odgrywają stosunkowo ważną rolę w algebrze uniwersalnej iw tym kontekście tradycyjnie nazywa się je operatorami domknięcia algebraicznego . Każdy podzbiór o Algebra wytwarza się podalgebrą : najmniejsze podalgebrą zawierający zestaw. Daje to początek operatorowi zamknięcia skończonego.

Być może najbardziej znanym tego przykładem jest funkcja, która przyporządkowuje każdemu podzbiorowi danej przestrzeni wektorowej jego rozpiętość liniową . Podobnie, funkcja Associates każdego podzbioru danej grupy podgrupa wytwarzane przez niego, i podobnie w dziedzinie i wszystkie inne rodzaje struktur algebraicznych .

Rozpiętość liniowa w przestrzeni wektorowej i podobne domknięcie algebraiczne w polu spełniają własność wymiany: Jeśli x jest w domknięciu sumy A i { y } , ale nie w domknięciu A , to y jest w domknięciu połączenia A i { x }. Operator zamknięcia skończonego z tą właściwością nazywa się matroid . Wymiar z przestrzeni wektorowej, lub stopień transcendencji pola (ponad jej głównego pola ) jest dokładnie taki stopień odpowiedniego matroid.

Funkcja odwzorowująca każdy podzbiór danego pola na jego domknięcie algebraiczne jest również operatorem domknięcia skończonego i generalnie różni się od operatora wspomnianego wcześniej. Operatory domknięcia skończonego, które uogólniają te dwa operatory, są badane w teorii modeli jako dcl (dla domknięcia definiowalnego ) i acl (dla domknięcia algebraicznego ).

Kadłuba wypukła w n -wymiarowej przestrzeni euklidesowej jest kolejnym przykładem finitary operatora zamknięcia. Spełnia ona własność antywymiany: Jeśli x jest w domknięciu unii { y } i A , ale nie w unii { y } i domknięciu A , to y nie jest w domknięciu unii { x } i A . Operatory zamknięcia skończonego z tą właściwością dają początek antymatroidom .

Jako kolejny przykład operatora domknięcia używanego w algebrze, jeśli jakaś algebra ma wszechświat A i X jest zbiorem par A , to operator przypisujący X najmniejszą kongruencję zawierającą X jest skończonym operatorem domknięcia na A x A .

Operatory zamknięcia w logice

Załóżmy, że masz jakiś logiczny formalizm, który zawiera pewne reguły pozwalające wyprowadzić nowe formuły z podanych. Rozważmy zbiór F wszystkich możliwych wzorów, i niech P będzie zestaw zasilający z F , uporządkowane według ⊆. Dla zbioru X formuł, niech cl( X ) będzie zbiorem wszystkich formuł, które można wyprowadzić z X . Wtedy cl jest operatorem zamknięcia na P . Dokładniej, możemy otrzymać cl w następujący sposób. Zadzwoń "ciągły" operator J taki, że dla każdej skierowanej klasy T ,

J ( lim T ) = lim J ( T ).

Ten warunek ciągłości jest oparty na twierdzeniu o punkcie stałym dla J . Rozważmy jednoetapowy operator J logiki monotonicznej. Jest to operator dołączania jakichkolwiek zestaw X o wzorach na ustawionej J ( X ) o wzorach które są albo aksjomaty logiczne lub są otrzymywane przez regułę interferencję z wzorami w X, lub są w X . Wtedy taki operator jest ciągły i możemy zdefiniować cl( X ) jako najmniej ustalony punkt dla J większego lub równego X . Zgodnie z takim punktem widzenia Tarski, Brown, Suszko i inni autorzy zaproponowali ogólne podejście do logiki oparte na teorii operatorów domknięcia. Również taka idea jest proponowana w logice programowania (por. Lloyd 1987) i logice rozmytej (por. Gerla 2000).

Operatory konsekwencji

Około 1930 roku Alfred Tarski opracował abstrakcyjną teorię dedukcji logicznych, która modeluje niektóre właściwości rachunków logicznych. Matematycznie to, co opisał, jest po prostu skończonym operatorem domknięcia na zbiorze (zbiorze zdań ). W abstrakcyjnej logice algebraicznej , operatory domknięcia skończonego są nadal badane pod nazwą operator konsekwencji , który został ukuty przez Tarskiego. Zbiór S reprezentuje zbiór zdań, podzbiór T z S teorię, a cl( T ) jest zbiorem wszystkich zdań wynikających z teorii. Obecnie termin ten może odnosić się do operatorów zamknięcia, które nie muszą być skończone; Operatory domknięcia skończonego są wówczas czasami nazywane operatorami konsekwencji skończonych .

Zbiory zamknięte i pseudo-zamknięte

Zbiory domknięte w odniesieniu do operatora domknięcia na S tworzą podzbiór C zbioru potęgowego P ( S ). Każde przecięcie zbiorów w C jest znowu w C . Innymi słowy, C jest zupełną subsemilacją spotkania P ( S ). Odwrotnie, jeśli C ⊆ P ( S ) jest domknięty pod dowolnymi przecięciami, to funkcja, która łączy z każdym podzbiorem X z S najmniejszy zbiór Y ∈ C taki, że X ⊆ Y jest operatorem domknięcia.

Istnieje prosty i szybki algorytm generowania wszystkich zbiorów domkniętych danego operatora domknięcia.

Operator domknięcia na zbiorze jest topologiczny wtedy i tylko wtedy, gdy zbiór domkniętych zbiorów jest domknięty pod skończonymi sumami , tj. C jest podsiecią spełniającą zupełną P ( S ). Nawet dla nietopologicznych operatorów zamknięcia, C może być postrzegane jako posiadające strukturę kratową. (Złączenie dwóch zbiorów X , Y ⊆ P ( S ) to cl( X Y ).) Ale wtedy C nie jest podsiecią sieci P ( S ). ${\ Displaystyle \ filiżanka}$

Mając operator domknięcia skończonego na zbiorze, domknięcia zbiorów skończonych są dokładnie zwartymi elementami zbioru C zbiorów domkniętych. Wynika z tego, że C jest posetem algebraicznym . Ponieważ C jest również kratą, często określa się ją w tym kontekście jako krata algebraiczna. I odwrotnie, jeśli C jest posetem algebraicznym, to operator domknięcia jest skończony.

Każdy operator domknięcia na zbiorze skończonym S jest jednoznacznie określony przez jego obrazy jego zbiorów pseudodomkniętych . Są one definiowane rekurencyjnie: Zbiór jest pseudo-zamknięty, jeśli nie jest zamknięty i zawiera domknięcie każdego z jego pseudo-zamkniętych właściwych podzbiorów. Formalnie: P ⊆ S jest pseudodomknięte wtedy i tylko wtedy, gdy

P ≠ cl( P ) i
jeśli Q ⊂ P jest pseudodomknięte, to cl( Q ) ⊆ P .

Operatory zamykania na częściowo zamówionych zestawach

Zbiór częściowo uporządkowany (poset) to zbiór wraz z porządkiem częściowym ≤, tj. relacja binarna, która jest zwrotna ( a ≤ a ), przechodnia ( a ≤ b ≤ c oznacza a ≤ c ) i antysymetryczna ( a ≤ b ≤ a implikuje a = b ). Każdy zbiór potęgowy P ( S ) wraz z włączeniem ⊆ jest zbiorem częściowo uporządkowanym.

Funkcja cl: P → P z porządku częściowego P do samej siebie nazywana jest operatorem domknięcia, jeśli spełnia następujące aksjomaty dla wszystkich elementów x , y w P .

x ≤ cl( x )	(cl jest obszerne )
x ≤ y implikuje cl( x ) ≤ cl( y )	(cl rośnie )
cl(cl( x )) = cl( x )	(cl jest idempotentny )

Dostępnych jest więcej zwięzłych alternatyw: powyższa definicja jest równoważna pojedynczemu aksjomatowi

x ≤ cl( y ) wtedy i tylko wtedy, gdy cl( x ) ≤ cl( y )

dla wszystkich x , y w P .

Używając porządku punktowego na funkcjach między zestawami, można alternatywnie zapisać własność ekstensywności jako id _P ≤ cl, gdzie id jest funkcją tożsamości . Self-map k , że rośnie i idempotent, ale spełniają podwójną nieruchomości rozległości, czyli k ≤ id _P nazywamy operator jądro , operator wewnętrzny lub podwójnego zamknięcia . Na przykład, jeśli A jest podzbiorem zbioru B , to samoodwzorowanie na zbiorze B dane przez μ _A ( X ) = A ∪ X jest operatorem domknięcia, podczas gdy λ _A ( X ) = A ∩ X jest operator jądra. Funkcję sufitu z liczb rzeczywistych do liczb rzeczywistych, które przydziela się do każdej rzeczywistym X najmniejszą liczbę całkowitą nie mniejszą niż x , to kolejny przykład operatora zamknięcia.

Punkt stały funkcji cl, tj. element c z P, który spełnia cl( c ) = c , nazywamy elementem zamkniętym . Operator zamknięcia na częściowo uporządkowanym zbiorze jest określony przez jego elementy zamknięte. Jeśli c jest elementem zamkniętym, to x ≤ c i cl( x ) ≤ c są warunkami równoważnymi.

Każde połączenie Galois (lub mapowanie rezydualne ) powoduje powstanie operatora zamknięcia (jak wyjaśniono w tym artykule). W rzeczywistości każdy operator zamknięcia powstaje w ten sposób z odpowiedniego połączenia Galois. Połączenie Galois nie jest jednoznacznie określone przez operatora zamknięcia. Jedno połączenie Galois, które daje początek operatorowi domknięcia cl, można opisać następująco: jeśli A jest zbiorem elementów domkniętych względem cl, to cl: P → A jest dolnym sprzężeniem połączenia Galois między P i A , z górne sprzężenie jest osadzeniem A w P . Co więcej, każde dolne sprzężenie osadzenia pewnego podzbioru w P jest operatorem domknięcia. „Operatory zamknięcia są niższymi elementami osadzenia”. Należy jednak pamiętać, że nie każde osadzanie ma niższe przyleganie.

Każdy częściowo uporządkowany zbiór P może być postrzegany jako kategoria , z pojedynczym morfizmem od x do y wtedy i tylko wtedy , gdy x ≤ y . Operatory domknięcia na częściowo uporządkowanym zbiorze P są więc niczym innym jak monadami na kategorii P . Równoważnie operator domknięcia może być postrzegany jako końcowy element kategorii zbiorów częściowo uporządkowanych, który ma dodatkowe właściwości idempotentne i rozległe .

Jeśli p jest pełna kraty , to podzbiór z P jest zbiór zamkniętych elementów do pewnego operatora zamknięcia na P , wtedy i tylko wtedy, gdy jest rodzina Moore na P , to znaczy do wielkości elementu P w A i infimum (spotkać) dowolnego niepustego podzbioru A jest ponownie w A . Każdy taki zbiór A jest sam w sobie kompletną kratą z porządkiem dziedziczonym z P (ale operacja supremum (łączenia) może różnić się od operacji P ). Gdy P jest potęgową algebrą Boole'a zbioru X , wtedy rodzina Moore'a na P nazywana jest systemem domknięć na X .

Operatory zamknięcia na P tworzą same kompletną siatkę; kolejność operatorów zamknięcia definiuje Cl ₁ ≤ Cl ₂ IFF cl ₁ ( x ) ≤ Cl ₂ ( x ) dla wszystkich x w P .

Zobacz też

Uwagi

Bibliografia

Garrett Birkhoff . 1967 (1940). Teoria kraty, wyd . Amerykańskie Towarzystwo Matematyczne.
Burris, Stanley N. i HP Sankappanavar (1981) Kurs uniwersalnej algebry Springer-Verlag. ISBN 3-540-90578-2 Bezpłatna wersja online .
Brown, DJ i Suszko, R. (1973) „Abstract Logics”, Dissertationes Mathematicae 102-9-42.
Castellini, G. (2003) Operatory domknięcia kategorycznego . Boston MA: Birkhaeuser.
Edelman, Paul H. (1980) Meet-distributive lattices and the anti-exchange closure, Algebra Universalis 10: 290-299.
Ganter, Bernhard i Obiedkov, Siergiej (2016) Eksploracja koncepcyjna . Springera, ISBN 978-3-662-49290-1 .
Gerla, G. (2000) Logika rozmyta: narzędzia matematyczne do wnioskowania przybliżonego . Wydawnictwa Akademickie Kluwer .
Lloyd, JW (1987) Podstawy programowania logicznego . Springer-Verlag .
Tarski, Alfred (1983) „Podstawowe koncepcje metodologii nauk dedukcyjnych” w Logic, Semantics, Metamatematics . Hackett (wyd. 1956, Oxford University Press ).
Alfred Tarski (1956) Logika, semantyka i metamatematyka . Wydawnictwo Uniwersytetu Oksfordzkiego .
Ward, Morgan (1942) „Operatory zamknięcia kraty”, Annals of Mathematics 43: 191-96.
G. Gierz, KH Hofmann, K. Keimel, JD Lawson, M. Mislove, DS Scott: Continuous Lattices and Domains , Cambridge University Press, 2003
TS Blyth, Kraty i uporządkowane struktury algebraiczne , Springer, 2005, ISBN 1-85233-905-5 .
M. Erné, J. Koslowski, A. Melton, GE Strecker, Elementarz o połączeniach Galois , w: Proceedings of the Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy Nauk, tom. 704, 1993, s. 103-125. Dostępne online w różnych formatach plików: PS.GZ PS

Zewnętrzne linki

Stanford Encyclopedia of Philosophy : „ Algebraiczna logika zdań” — autorstwa Ramona Jansany.

Languages

In other projects