Lukning operatør - Closure operator

I matematik , en lukning operatør på et sæt S er en funktion af strømmen sæt af S til selv at opfylder følgende betingelser for alle sæt ${\ displaystyle \ operatorname {cl}: {\ mathcal {P}} (S) \ rightarrow {\ mathcal {P}} (S)}$ ${\ displaystyle X, Y \ subseteq S}$

${\ displaystyle X \ subseteq \ operatorname {cl} (X)}$	(cl er omfattende ),
${\ displaystyle X \ subseteq Y \ Rightarrow \ operatorname {cl} (X) \ subseteq \ operatorname {cl} (Y)}$	(cl er monoton ),
${\ displaystyle \ operatorname {cl} (\ operatorname {cl} (X)) = \ operatorname {cl} (X)}$	(cl er idempotent ).

Lukning operatører bestemmes ved deres lukkede mængder , dvs. ved sættene af formen cl ( X ), idet lukningen cl ( X ) af et sæt X er den mindste lukkede sæt indeholdende X . Sådanne familier med "lukkede sæt" kaldes undertiden lukningssystemer eller " Moore -familier " til ære for EH Moore, der studerede lukkeoperatører i sin introduktion til en form for generel analyse fra 1910 , hvorimod begrebet lukning af en delmængde stammer fra arbejde fra Frigyes Riesz i forbindelse med topologiske rum. Selvom ideen om lukning ikke var formaliseret på det tidspunkt, opstod i slutningen af 1800 -tallet med bemærkelsesværdige bidrag fra Ernst Schröder , Richard Dedekind og Georg Cantor .

Lukning operatører kaldes også " skrog operatører ", hvilket forhindrer forvirring med de "lukning operatører" studeret i topologi . Et sæt sammen med en lukkeoperatør på det kaldes undertiden et lukningsrum .

Ansøgninger

Lukning operatører har mange applikationer:

I topologi er lukkeoperatørerne topologiske lukkeoperatører , hvilket skal tilfredsstille

{\ displaystyle \ operatorname {cl} (X_ {1} \ cup \ dots \ cup X_ {n}) = \ operatorname {cl} (X_ {1}) \ cup \ dots \ cup \ operatorname {cl} (X_ { n})}

for alle (Bemærk, at for dette giver ). ${\ displaystyle n \ in \ mathbb {N}}$ ${\ displaystyle n = 0}$ ${\ displaystyle \ operatorname {cl} (\ varnothing) = \ varnothing}$

I algebra og logik er mange lukkeoperatører endelige lukningsoperatorer , dvs. de tilfredsstiller

{\ displaystyle \ operatorname {cl} (X) = \ bigcup \ left \ {\ operatorname {cl} (Y): Y \ subseteq X {\ text {og}} Y {\ text {finite}} \ right \} .}

I teorien om delvist ordnede sæt , som er vigtige i teoretisk datalogi , har lukningsoperatører en mere generel definition, der erstatter med . (Se § Lukningsoperatører på delvist bestilte sæt .) ${\ displaystyle \ subseteq}$ ${\ displaystyle \ leq}$

Lukning operatører i topologi

Den topologiske lukning af en delmængde X af et topologisk rum består af alle punkter y af rummet, således at hver kvarter af y indeholder et punkt i X . Funktionen, der forbinder hver delmængde X dens lukning, er en topologisk lukningsoperator. Omvendt giver hver topologisk lukkeoperatør på et sæt anledning til et topologisk rum, hvis lukkede sæt nøjagtigt er de lukkede sæt i forhold til lukkeoperatøren.

Lukning operatører i algebra

Finitære lukningsoperatører spiller en relativt fremtrædende rolle i universel algebra , og i denne sammenhæng kaldes de traditionelt algebraiske lukningsoperatorer . Hver delmængde af en algebra genererer en subalgebra : den mindste subalgebra, der indeholder sættet. Dette giver anledning til en endelig lukkeoperatør.

Måske er det mest kendte eksempel på dette den funktion, der forbinder hvert delsæt af et givet vektorrum dets lineære spændvidde . Tilsvarende funktionen, der forbinder hver undergruppe af en given gruppe den undergruppe, der genereres af den, og på samme måde for felter og alle andre typer algebraiske strukturer .

Det lineære spænd i et vektorrum og den lignende algebraiske lukning i et felt tilfredsstiller begge udvekslingsegenskaben: Hvis x er i lukningen af foreningen af A og { y }, men ikke i lukningen af A , så er y i lukningen af foreningen af A og { x }. En endelig lukkeoperatør med denne egenskab kaldes en matroid . Den dimension af et vektorrum, eller transcendensgrad af et felt (over dens primære felt ) er præcis rang af den tilsvarende matroid.

Funktionen, der tilknytter alle delmængder af et givet felt til dets algebraiske lukning, er også en finitær lukningsoperator, og generelt er den forskellig fra den før nævnte operatør. Finitære lukningsoperatorer, der generaliserer disse to operatører, studeres i modelteori som dcl (til definerbar lukning ) og acl (til algebraisk lukning ).

Det konvekse skrog i n -dimensionalt euklidisk rum er et andet eksempel på en finitær lukkeoperatør. Det opfylder anti-exchange-egenskaben: Hvis x er i lukningen af foreningen af { y } og A , men ikke i foreningen af { y } og lukning af A , så er y ikke i lukningen af foreningen af { x } og A . Finitære lukningsoperatører med denne egenskab giver anledning til antimatroider .

Som et andet eksempel på et lukke operatør anvendes i algebra, hvis nogle algebra har univers A og X er et sæt af par af A , så operatøren tildele X den mindste kongruens indeholdende X er en finitary lukning operatør på A x A .

Lukning operatører i logik

Antag, at du har en logisk formalisme, der indeholder visse regler, der giver dig mulighed for at udlede nye formler fra givne. Overvej sættet F for alle mulige formler, og lad P være effektsættet for F , sorteret efter ⊆. For et sæt X af formler, lad cl ( X ) være mængden af alle formler, der kan udledes af X . Så cl er en lukning operatør på P . Mere præcist kan vi opnå cl som følger. Kald "kontinuerlig" en operatør J, således at for hver rettet klasse T ,

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

Denne kontinuitet betingelse er på grundlag af et fast punkt sætning for J . Overvej et-trins-operatoren J for en monoton logik. Dette er operatør associere ethvert sæt X af formler med sættet J ( X ) med formlerne, der enten logiske aksiomer eller der opnås ved en følgeslutning regel fra formler i X eller er i X . Derefter en sådan operatør er kontinuert og vi kan definere cl ( X ) som det mindst faste punkt for J større eller lig med X . I overensstemmelse med et sådant synspunkt foreslog Tarski, Brown, Suszko og andre forfattere en generel tilgang til logik baseret på teori om lukning af operatører. En sådan idé foreslås også i programmeringslogik (se Lloyd 1987) og i fuzzy logik (se Gerla 2000).

Konsekvensoperatører

Omkring 1930 udviklede Alfred Tarski en abstrakt teori om logiske fradrag, der modellerer nogle egenskaber ved logiske beregninger. Matematisk hvad han beskrev er bare en finitary lukning operatør på et sæt (det sæt af sætninger ). I abstrakt algebraisk logik studeres endelige lukkeoperatører stadig under navnet konsekvensoperator , som blev opfundet af Tarski. Sættet S repræsenterer et sæt sætninger, et undersæt T af S en teori, og cl ( T ) er sættet af alle sætninger, der følger af teorien. I dag kan udtrykket referere til lukningsoperatører, der ikke behøver at være endelige; endelige lukningsoperatører kaldes så undertiden endelige konsekvensoperatorer .

Lukkede og pseudo-lukkede sæt

De lukkede sæt med hensyn til en lukkeoperator på S danner en undersætning C af effektsættet P ( S ). Enhver skæringspunktet mellem sæt i C er igen i C . Med andre ord er C et komplet meet-subsemilatice af P ( S ). Omvendt, hvis C ⊆ P ( S ) er lukket under vilkårlige kryds, så er funktionen, der associerer hvert undersæt X af S det mindste sæt Y ∈ C, således at X ⊆ Y er en lukkeoperator.

Der er en enkel og hurtig algoritme til at generere alle lukkede sæt af en given lukkeoperator.

En lukkeoperatør på et sæt er topologisk, hvis og kun hvis sættet med lukkede sæt er lukket under begrænsede fagforeninger, dvs. C er en fuldstændig undergitter af P ( S ). Selv for ikke-topologiske lukkeoperatører kan C ses at have strukturen af et gitter. (Sammenføjningen af to sæt X , Y ⊆ P ( S ) er cl ( X Y ).) Men så er C ikke et undergitter af gitteret P ( S ). ${\ displaystyle \ cup}$

I betragtning af en finitær lukkeoperatør på et sæt, er lukningerne af endelige sæt nøjagtigt de kompakte elementer i sættet C for lukkede sæt. Det følger heraf, at C er en algebraisk poset . Da C også er et gitter, omtales det ofte som et algebraisk gitter i denne sammenhæng. Omvendt, hvis C er en algebraisk poset, er lukkeoperatoren endelig.

Hver lukkeoperator på et begrænset sæt S bestemmes entydigt af sine billeder af sine pseudo-lukkede sæt. Disse er rekursivt definerede: Et sæt er pseudolukket, hvis det ikke er lukket og indeholder lukningen af hver af dets pseudo-lukkede korrekte undersæt. Formelt: P ⊆ S er pseudolukket, hvis og kun hvis

P ≠ cl ( P ) og
hvis Q ⊂ P er pseudo-lukket, så cl ( Q ) ⊆ P .

Lukning operatører på delvist bestilte sæt

Et delvist ordnet sæt (poset) er et sæt sammen med en delvis rækkefølge ≤, dvs. en binær relation, der er refleksiv ( a ≤ a ), transitiv ( a ≤ b ≤ c indebærer a ≤ c ) og antisymmetrisk ( a ≤ b ≤ a indebærer a = b ). Hvert effektsæt P ( S ) sammen med inklusion ⊆ er et delvist ordnet sæt.

En funktion cl: P → P fra en delvis ordre P til sig selv kaldes et lukke operatør, hvis det opfylder følgende aksiomer for alle elementer x , y i P .

x ≤ cl ( x )	(cl er omfattende )
x ≤ y betyder cl ( x ) ≤ cl ( y )	(cl stiger )
cl (cl ( x )) = cl ( x )	(cl er idempotent )

Flere kortfattede alternativer er tilgængelige: definitionen ovenfor svarer til det enkelte aksiom

x ≤ cl ( y ) hvis og kun hvis cl ( x ) ≤ cl ( y )

for alle x , y i P .

Ved at bruge den punktvise rækkefølge på funktioner mellem posetter kan man alternativt skrive extensiveness -egenskaben som id _P ≤ cl, hvor id er identitetsfunktionen . Et selvkort k, der er stigende og idempotent, men tilfredsstiller det dobbelte af extensiveness-egenskaben, dvs. k ≤ id _P kaldes en kerneoperator , interiøroperatør eller dobbelt lukning . Som eksempler, hvis A er en delmængde af et sæt B , er selvkortet på powersættet af B givet af μ _A ( X ) = A ∪ X en lukkeoperator, hvorimod λ _A ( X ) = A ∩ X er en kerneoperatør. Det loft funktionen fra reelle tal til de reelle tal, som tillægger hver real x den mindste heltal ikke mindre end x , er et andet eksempel på en lukning operatør.

Et fixpunkt for funktionen cl, dvs. et element c i P, der opfylder cl ( c ) = c , kaldes et lukket element . En lukkeoperatør på et delvist bestilt sæt bestemmes af dets lukkede elementer. Hvis c er et lukket element, er x ≤ c og cl ( x ) ≤ c ækvivalente betingelser.

Hver Galois -forbindelse (eller resterende kortlægning ) giver anledning til en lukningsoperatør (som forklaret i denne artikel). Faktisk opstår hver lukkeoperatør på denne måde fra en passende Galois -forbindelse. Galois -forbindelsen bestemmes ikke entydigt af lukkeoperatøren. Én Galois -forbindelse, der giver anledning til lukkeoperatøren cl, kan beskrives som følger: hvis A er sættet af lukkede elementer i forhold til cl, så er cl: P → A den nedre tilslutning til en Galois -forbindelse mellem P og A , med den øvre adjoint være indlejring af A i P . Endvidere er hver nedre tilslutning til en indlejring af et eller andet undersæt i P en lukkeoperator. "Lukningsoperatører er lavere ved siden af indlejringer." Bemærk dog, at ikke hver indlejring har en lavere adjoint.

Ethvert delvist ordnet sæt P kan ses som en kategori med en enkelt morfisme fra x til y, hvis og kun hvis x ≤ y . De lukning operatører på delvist ordnet sæt P er så intet, men de monader på kategori P . Tilsvarende kan en lukningsoperatør ses som en endofunktionær i kategorien delvist bestilte sæt, der har de ekstra idempotente og omfattende egenskaber.

Hvis P er et komplet gitter , så er en delmængde A af P sættet af lukkede elementer for en eller anden lukkeoperator på P, hvis og kun hvis A er en Moore -familie på P , dvs. det største element af P er i A , og det minimale (mødes) enhver ikke-tom delmængde af A er igen i A . Ethvert sådant sæt A er i sig selv et komplet gitter med den rækkefølge, der er arvet fra P (men supremum (join) -operationen kan afvige fra P ). Når P er den Powerset boolsk algebra af et sæt X , så en Moore familie på P kaldes et lukkesystem på X .

Lukkeoperatørerne på P danner selv et komplet gitter; bekendtgørelse om lukning operatører er defineret ved cl ₁ ≤ cl ₂ IFF cl ₁ ( x ) ≤ cl ₂ ( x ) for alle x i P .

Se også

Noter

Referencer

Garrett Birkhoff . 1967 (1940). Gitterteori, 3. udgave . American Mathematical Society.
Burris, Stanley N. og HP Sankappanavar (1981) A Course in Universal Algebra Springer-Verlag. ISBN 3-540-90578-2 Gratis online udgave .
Brown, DJ og Suszko, R. (1973) "Abstract Logics", Dissertationes Mathematicae 102- 9-42.
Castellini, G. (2003) Kategoriske lukningsoperatører . Boston MA: Birkhaeuser.
Edelman, Paul H. (1980) Meet-distributive gitter og anti-exchange lukning, Algebra Universalis 10: 290-299.
Ganter, Bernhard og Obiedkov, Sergei (2016) Konceptuel udforskning . Springer, ISBN 978-3-662-49290-1 .
Gerla, G. (2000) Fuzzy Logic: Mathematical Tools for Approximate Reasoning . Kluwer Academic Publishers .
Lloyd, JW (1987) Foundations of Logic Programming . Springer-Verlag .
Tarski, Alfred (1983) "Grundlæggende begreber i metoderne for deduktive videnskaber" i logik, semantik, metamatematik . Hackett (1956 udgave, Oxford University Press ).
Alfred Tarski (1956) Logik, semantik og metamatematik . Oxford University Press .
Ward, Morgan (1942) "Lukningsoperatørerne af et gitter", 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, Lattices and Ordered Algebraic Structures , Springer, 2005, ISBN 1-85233-905-5 .
M. Erné, J. Koslowski, A. Melton, GE Strecker, En primer om Galois -forbindelser , i: Proceedings of the Summer Summer Conference on General Topology and Applications in Honour of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, bind. 704, 1993, s. 103–125. Tilgængelig online i forskellige filformater: PS.GZ PS

eksterne links

Stanford Encyclopedia of Philosophy : " Algebraic Propositional Logic " - af Ramon Jansana.

Languages

In other projects