Stängningsoperatör

Stängningsoperatören är en generalisering av det intuitiva begreppet stängning. Nämligen: om är en delvis beställd uppsättning , kommer operatören att kallas en stängningsoperatör om tre villkor är uppfyllda: $\langle P,\leqslant \rangle$ $C:P\till P$

$x\leqslant C(x)$ ( omfattning ),
$x\leqslant y\Högerpil C(x)\leqslant C(y)$ ( monotoni )
$C(C(x))=C(x)$ ( idempotens )

Uppsättningen är ofta Boolean av någon annan uppsättning ; exempel på detta kan hittas i topologi, algebra och logik. $P$ $S$

Elementen i vyn kallas slutna , de bildar en delmängd i den ursprungliga delvis ordnade uppsättningen . Stängningsoperatören är helt definierad av uppsättningen slutna element; nämligen, stängningen av ett element är det minsta slutna elementet större än eller lika med det givna: $C(x)$ $C(P)$ $P$ $x\in P$

C(x)=\inf \lbrace c\in C(P):c\geq x\rbrace

Uppsättningen av alla slutna element kallas ibland Moore-familjen [1] efter den amerikanske matematikern Eliakim Moore , som studerade nedläggningar 1910 [2] . Vissa speciella fall av stängning kallas skal (till exempel konvext skal eller linjärt skal ) - detta undviker förväxling med begreppet en sluten uppsättning .

Exempel på stängningsoperatörer kan hittas inom en mängd olika områden inom matematiken:

Inom topologi studeras förslutningen av en mängd . Den topologiska stängningen "respekterar" den ändliga föreningen av mängder:

C(X_{1}\cup \dots \cup X_{n})=C(X_{1})\cup \dots \cup C(X_{n})

för någon .

n\in \mathbb {N}

I synnerhet för denna formel blir . $n=0$ $C(\varnothing )=\varnothing$

Inom algebra och logik anses stängningsoperatorer som har finitaritetsegenskapen :

C(X)=\bigcup _{Y\in {\mathcal {F))(X)}C(Y)

, där är mängden av alla finita delmängder av mängden .

{\mathcal {F}}(X)

X

I universell logik , är ett exempel på en stängning konsekvensoperatorn .

Teoretisk datavetenskap tillämpar också i mycket stor utsträckning all utveckling av teorin om order inom området för stängningsoperatörer, inklusive definitionen av godtyckliga, delvis ordnade uppsättningar.

Stängningsoperatör i topologi

Stängningen av en uppsättning i ett givet topologiskt utrymme består av de punkter i utrymmet, vars område har minst en gemensam punkt med . Funktionen som tilldelar varje delmängd av ett givet utrymme dess stängning är en topologisk stängningsoperator (i den mening som definierats ovan). Omvänt definierar vilken operator som helst för topologisk stängning en topologi på uppsättningen , där uppsättningen är stängd om och endast om den är ett element av boolesk , stängd med avseende på operatorn . $X$ $X$ $C:2^{S}\to 2^{S}$ $S$ $X\subseteq S$ $2^{S}$ $C$

Faktum är att Kuratowskis axiomtiska är ett system av allmänna topologiaxiom som utnyttjar denna idé. Den bygger en topologisk struktur , utgående från definitionen av en topologisk stängningsoperatör som en omfattande idempotent operatör med egenskapen . $C$ $C(X\cup Y)=C(X)\cup C(Y)$

Monotonicitetsaxiomet för den topologiska stängningsoperatorn är redundant, eftersom det härleds från resten av axiomen.

Stängningsoperatorn i algebra

Den finitära förslutningen spelar en viktig roll i universell algebra , där den traditionellt kallas för en algebraisk förslutning . Vilken delmängd som helst av en algebra definierar någon delalgebra: den minsta av alla delalgebra som innehåller den givna mängden. Detta introducerar den booleska stängningsoperatorn . $X$ $A$ $2^A$

Det kanske mest kända exemplet på en sådan operator är en funktion som tilldelar en uppsättning vektorer i något linjärt utrymme dess linjära spännvidd , delrummet som bildas av dessa vektorer. Ett annat exempel: en funktion som mappar till någon delmängd av gruppelement den undergrupp som genereras av dem . Liknande exempel kan konstrueras för fält , gitter och andra typer av algebraiska strukturer .

Stängningsoperatorerna "linjärt span" och "det minsta underfältet som innehåller en given uppsättning" har den sk. utbytesegenskap : om den tillhör förslutningen , men inte tillhör uppsättningens förslutning , så tillhör den förslutningen . En finitär stängning som har denna egenskap kallas en matroid . Dimensionen av vektorutrymmet och graden av transcendens av fältet (över dess primfält ) är exakt samma rang som motsvarande matroid. $a$ $X\cup \{b\}$ $X$ $b$ $X\cup \{a\}$

En funktion som mappar en delmängd av ett fält till dess algebraiska stängning är också en finitär stängningsoperator, men skiljer sig i sina egenskaper från operatorerna ovan. Dessa två typer av stängningar studeras i modellteori , där de betecknas (från engelskan definable closure ) och (från den engelska algebraic closure ). $\operatörsnamn {dcl}$ $\operatörsnamn {acl}$

Det konvexa skrovet i det euklidiska rymden är ett annat exempel på en finitär förslutning. Den här operatören har anti-utbytesegenskapen : om den inte tillhör uppsättningen men tillhör dess stängning, så tillhör den inte avslutningen . Finitära stängningar med denna egenskap leder till föreställningen om en antimatroid . $a$ $X\cup \{b\}$ $b$ $X\cup \{a\}$

Stängningsoperatorn i logik

Tänk på en viss logisk formalism , som gör det möjligt att, enligt vissa regler, härleda nya formler från befintliga. Låt beteckna mängden av alla möjliga formler, och beteckna Boolean för denna mängd, sorterad efter inkludering. För en godtycklig uppsättning formler betecknar vi uppsättningen formler som härrör från . Sedan är stängningsoperatören definierad på . $F$ $P=2^{F}$ $X$ $C(X)$ $X$ $C$ $P$

Det kan definieras mer strikt enligt följande. Låt vara en deduktiv stegoperator i monoton logik; med andra ord, är en uppsättning formler, som var och en är antingen ett axiom, eller tillhör eller erhålls genom en enda tillämpning av någon härledningsregel på formler från . Observera att för alla riktade klasser är likheten sann , därför är operatorn kontinuerlig och fixpunktssatsen kan appliceras på den . Då definieras som den minsta fixpunkten större än eller lika med . I enlighet med denna synvinkel föreslog Tarski [3] , Brown och Sushko [4] , liksom andra författare, en generell metod för matematisk logik baserad på teorin om stängningsoperatörer. Samma idé har funnits i logisk programmering [5] och fuzzy logic [6] . $C$ $J:P\to P$ $J(X)$ $X$ $X$ $T$ $J(\lim T)=\lim J(T)$ $J$ $C(X)$ $J$ $X$

Följdoperator

Runt 1930 utvecklade Alfred Tarski en abstrakt teori om deduktion som modellerar några av egenskaperna hos logiska kalkyler. Ur en matematisk synvinkel beskrev han den finitära stängningen på uppsättningen av propositioner . I universell logik , får denna stängning ett namn myntat av Tarski : konsekvensoperatör . Så, låt vara mängden av alla möjliga propositioner, dess undergrupp är en teori; då är uppsättningen av påståenden som är den logiska konsekvensen av teorin . Nuförtiden kan termen "corollary operator" appliceras på mer än bara finitära operatorer; i detta fall, om operatorn fortfarande uppfyller finitaritetsvillkoret, kallas den för en finit konsekvensoperator . $S$ $T$ $C(T)$ $T$

Slutna uppsättningar

Låt stängningsoperatören agera på Boolean . Familjen av slutna delmängder bildar en delmängd i . Varje skärningspunkt av mängder från igen ligger i , Det vill säga är en fullständig lägre subgitter i . Följaktligen, om någon uppsättning är stängd med avseende på godtyckliga (möjligen oändliga) skärningspunkter, är funktionen som tilldelar varje delmängd den minsta uppsättningen som innehåller en stängningsoperator. $C$ $P=2^{S}$ $C(P)$ $P$ $C(P)$ $C(P)$ $C(P)$ $P$ $K\subseteq 2^{S}$ $X\subseteq S$ $Y\in K$ $X$

Stängningsoperatorn kallas topologisk om familjen av slutna uppsättningar är slutna med avseende på ändliga föreningar, det vill säga om den bildar ett subgitter som är komplett med avseende på föreningsoperationen. Även om operatorn inte är topologisk, har uppsättningen fortfarande en gitterstruktur (med operationer och definierade som: , ); men i det här fallet är det inte ett subgitter av , eftersom operationerna på dem är inkonsekventa. $C(P)$ $C$ $C(P)$ $\kil$ $\vee$ $X\wedge Y=X\cap Y$ $X\vee Y=C(X\cup Y)$ $C(P)$ $P$

Om stängningsoperatorn är finitär , då är stängningarna av finita uppsättningar de kompakta elementen av uppsättningen . Därför är en algebraisk mängd (eller "algebraisk gitter", om vi tar hänsyn till att det verkligen finns en gitterstruktur på). Omvänt, om en familj av slutna uppsättningar är en algebraisk partiellt ordnad uppsättning, då är motsvarande stängningsoperator finitär. $C(P)$ $C(P)$ $C(P)$

Allmänt fall: stängning på delvis beställda set

Stängningar kan övervägas inte bara på Boolean, utan även på alla partiellt beställda set . Utöver ovanstående definition av förslutningsoperatören som en omfattande monoton idempotent funktion, finns det även ett antal alternativa definitioner. Till exempel kan dessa tre axiom ersättas med ett:

x\leq C(y)\Leftrightarrow C(x)\leq C(y)

för någon .

x,y\in P

Om vi antar att en punktvis jämförelse definieras mellan mappningar , kan en operators extensivhetsegenskap kortfattat skrivas på följande sätt: $C:P\to P$

C\geq \operatörsnamn {id}

, där betecknar den identiska funktionen .

\operatörsnamn {id}

En monoton idempotent mappning med en dubbel egenskap kallas en kärnoperator ( eng. kärnoperator [7] ), inre operator ( eng. inre operator [8] ) eller dual closure ( eng. dubbel stängning [9] ). Ett exempel på en sådan funktion är operationen att erhålla det inre av en mängd i en topologi. Ett annat exempel ges av avrundningsfunktionen , betraktad som en operator på reella tal med en naturlig ordning: avrundning nedåt ( eng. floor , ) är den inre operatorn, och avrundning uppåt ( eng. ceil , ) är stängningsoperatorn. Ett annat exempel: om är någon uppsättning, och en godtycklig delmängd är fixerad i den , är den inre operatorn på Boolean och är stängningsoperatorn. $I:P\to P$ $I\leq \operatörsnamn {id}$ $\lgolv x\rgolv$ $\lceil x\rceil$ $S$ $T$ $\mu _{T}(X)=T\cap X$ $P=2^{S}$ $\lambda _{T}(X)=T\kopp X$

En fast punkt på displayen , det vill säga ett element som har egenskapen , kallas sluten . Stängningsoperatören på en delvis beställd uppsättning bestäms helt av uppsättningen slutna element. Om elementet är stängt är påståendet ekvivalent med . $C$ $c\in P$ $C(c)=c$ $c$ $x\leq c$ $C(x)\leq c$

Som förklaras i Galois-korrespondensartikeln genererar all sådan korrespondens en stängningsoperatör. Dessutom kan alla stängningsoperatörer erhållas från viss korrespondens från Galois [10] . En lämplig Galois-korrespondens kan konstrueras på mer än ett sätt; det allmänna sättet är som följer. Låt beteckna uppsättningen av slutna element. Då kan det betraktas som en kartläggning ; detta kommer att vara den nedre angränsande Galois-korrespondensfunktionen. Låt oss ta inbäddningen som den övre adjoint-funktionen . Faktum är att varje funktion som är lägre angränsande till en inbäddning av någon delmängd i är en stängning: "Stängningsoperatörerna är lägre anslutningar till inbäddningar." Dock har inte varje inbäddning en lägre adjoint funktion! $K$ $C$ $P\to K$ $K\to P$ $P$

Varje poset kan betraktas som en kategori där en pil finns (och är unik) om och endast om . I denna tolkning motsvarar stängningsoperatörer monader $P$ $x\to y$ $x\leq y$

Om är ett komplett gitter , då för att en delmängd ska vara en uppsättning slutna element av någon operatör , är det nödvändigt och tillräckligt [11] att det bildar en Moore-familj på , d.v.s. en uppsättning som innehåller den övre och minsta nedre gränsen av någon delmängd av uppsättningen . Varje sådan är i sig ett komplett gitter, och ordningsrelationen och den nedre operationen (infimum) ärvs från , medan den övre operationen (supremum) kan skilja sig åt. När gittret introduceras som en boolesk algebra av delmängder av någon uppsättning , kallas Moore-familjen uppsättningens slutsystem [ 12 ] . $P$ $K\subseteq P$ $C$ $K$ $P$ $P$ $K$ $K$ $P$ $P$ $S$ $S$

Stängningsoperatorerna på det kompletta gittret bildar själva ett komplett gitter, på vilket ordningsrelationen introduceras punktvis: om och endast om . ${\displaystyle C_{1}\leq C_{2))$ $\forall x\in P\;C_{1}(x)\leq C_{2}(x)$

Historik

Begreppet stängning introducerades av E. G. Moore i 1910 års monografi Introduktion till en form av allmän analys . Konceptet med ett system av slutna delmängder beskrevs först i F. Ries verk i relation till topologiska utrymmen [2] .

Ser även

Anteckningar

↑ Birkhoff, 1984 , sid. 148.
↑ 12 Blyth , 2005 , sid. elva.
↑ Tarski, 1956 .
↑ Brown & Suszko, 1973 .
↑ Lloyd, 1987 .
↑ Gerla, 2001 .
↑ Gierz et al., 2003 , Definition O-3.8(iii), sid. 26.
↑ Erné et al., 1993 , Definition 2 (1), s. 104–105: "En stängning (respektive interiör ) operation ."
↑ Blyth, 2005 , sid. tio.
↑ Blyth, 2005 , Teorem 1.7, sid. tio.
↑ Birkhoff, 1984 , Theorem 1, sid. 148.
↑ Birkhoff, 1984 , not 1 ), sid. 149.

Litteratur

Birkhoff, G. Gitterteori. — 3:e uppl. - Providence, RI: American Mathematical Society, 1973. - vi, 418 sid. — (American Mathematical Society Colloquium Publications; vol. XXV). - ISBN 0-8218-1025-1 . — .
[Rysk översättning: Birkhoff, G. Lattice Theory. - M . : Vetenskap. Huvudupplagan av fysisk och matematisk litteratur, 1984. - 568 sid. - 9400 exemplar. ]
Blyth, T. S. Gitter och ordnade algebraiska strukturer. - London: Springer-Verlag, 2005. - ix, 303 sid. — (Universitetstext). — ISBN 1-85233-905-5 . - doi : 10.1007/B139095 . — .
Brown, DJ Abstrakt logik / DJ Brown, R. Suszko // Dissertationes Mathematicae. - 1973. - Vol. II. — S. 9–41. — ISSN 0012-3862 .
Burris, S. En kurs i universell algebra / S. Burris, HP Sankappanavar. - New York, NY: Springer-Verlag, 1981. - xvi, 276 sid. - (Examinerade texter i matematik; vol. 78). — ISBN 0-387-90578-2 . — .
[Gratis onlineupplaga: Burris, S. A Course in Universal Algebra / S. Burris, HP Sankappanavar. — The Millennium Edition, 2012 uppdatering. - 2012. -xiv, 276 sid. : 36 illus. - ISBN 978-0-9880552-0-9 . ]
Castellini, G. Kategoriska stängningsoperatörer: [ arch. 30 december 2015 ]. - Boston, MA : Birkhäuser, 2003. - xii, 300 sid. - (Matematik: Teori & tillämpningar). - ISBN 978-1-4612-6504-7 . - doi : 10.1007/978-0-8176-8234-7 .
Edelman, PH Meet-distributive Lattices and the Anti-exchange Closure // Algebra Universalis. - 1980. - Vol. 10, nr. 1. - S. 290-299. — ISSN 0002-5240 . - doi : 10.1007/BF02482912 .
Erné, M. En primer om Galois-anslutningar / M. Erné, J. Koslowski, A. Melton … [ et al. ] // Annals of the New York Academy of Sciences. - 1993. - Vol. 704: Uppsatser om allmän topologi och tillämpningar. - S. 103-125. — ISSN 0077-8923 . - doi : 10.1111/j.1749-6632.1993.tb52513.x .
[Elektroniska förtryck:
- Erne, M., et al. En primer på Galois-anslutningar : [PS.GZ] / prep. av J. Koslowski // Jürgen Koslowskis hemsida . — 1991/92.
- Erne, M., et al. En primer på Galois-anslutningar: icke-RPN-version : [PS.GZ] / prep. av J. Koslowski // Jürgen Koslowskis hemsida . — 1991/92.
- Erne, M., et al. En primer på Galois-anslutningar : [PS] / prep. av GE Strecker // George E. Strecker (Hemsida) . ]
Gerla, G. Fuzzy Logic: Matematiska verktyg för ungefärligt resonemang. - Dordrecht : Kluwer Academic Publishers, 2001. - xii, 269 s. - (Trends in Logic; vol. 11). — ISBN 0-7923-6941-6 . - doi : 10.1007/978-94-015-9660-2 .
Gierz, G. Continuous Lattices and Domains / G. Gierz, KH Hoffman, K. Keimel … [ et al. ] . - New York, NY: Cambridge University Press, 2003. - xxxvi, 591 s. - (Encyclopedia of Mathematics and its Applications; vol. 93). - ISBN 0-521-80338-1 .
Lloyd, JW Grunderna för logisk programmering. — 2:a utv. ed. - Berlin: Springer-Verlag, 1987. - xii, 212 sid. - (Artificiell intelligens. Ser. Symbolic Computation). — ISBN 3-540-18199-7 . - ISBN 978-3-642-83191-1 . - doi : 10.1007/978-3-642-83189-8 .
Tarski, A. Fundamental Concepts of the Methodology of Deductive Sciences = Fundamentale Begriffe der Methodologie der deduktiven Wissenschaften : [orig. 1930] // Logik, semantik, metamatematik. Uppsatser från 1923 till 1938 av Alfred Tarski / övers. av JH Woodger . - Oxford: Clarendon Press, 1956. - S. 60-109. — .
Ward, M. The Closure Operators of a Lattice // Annals of Mathematics. - 1942. - Vol. 43, nr. 2. - S. 191-196. — ISSN 0003-486X . - doi : 10.2307/1968865 . — .

Länkar

Jansara, Ramon. Algebraisk propositionell logik / Edward N. Zalta (red.) // Stanford Encyclopedia of Philosophy . - Metaphysics Research Lab, Stanford University, 2016. - 12 december.