Connexió de Galois

En matemàtica, especialment en la teoria de l'ordre, una connexió de Galois és una correspondència particular entre dos conjunts parcialment ordenats (abreujat "Poset" en anglès). Les connexions de Galois generalitzen la correspondència entre subgrups i subcossos investigada en la teoria de Galois. Tenen aplicació en diverses teories matemàtiques.

Una connexió de Galois és bastant més feble que un isomorfisme entre els Posets implicats, però cada connexió de Galois dona lloc a un isomorfisme de certs sub-Posets, com explicarem més endavant.

Igual que la teoria de Galois, les connexions deuen el seu nom al matemàtic francès Évariste Galois.

Definició

Suposeu dos conjunts parcialment ordenats ( A , ≤) i ( B , ≤). Una connexió de Galois entre aquests Posets consisteix en dues funcions monòtones: F : A → B i G : B → A , com que per a tot a a A i b a B , tenim

F(a)\leq b\leftrightarrow a\leq G(b)

En aquesta sitaución es diu a F adjunt inferior de G ja G , adjunt superior de F . Aquesta terminologia relaciona les connexions a la teoria de categories que es comenta després. Tal com es detallarà, cada part d'una connexió de Galois determina unívocament l'altra correspondència. En veure dues funcions que formen una connexió de Galois com dues especificacions d'aquest objecte, és convenient assenyalar un parell d'adjunts inferior i superior corresponents com f^* i f_*, respectivament. Noteu que l'asterisc es posa sobre el símbol de la funció per assenyalar l'adjunt inferior .

Definició alternativa

La definició anterior és comú a moltes aplicacions actualment, i prominent en les teories de reticles i de dominis. No obstant això, originalment es va derivar una noció lleugerament diferent en la teoria de Galois. En aquesta definició alternativa, una connexió de Galois és un parell de funcions antítones (que inverteixen l'ordre), F : A → B i G : B → A entre els Posets A i B , de manera que

B\leq F(a)\leftrightarrow a\leq G(b)

Ambdues nocions d'una connexió de Galois segueixen presents en la literatura. En Wikipedia el terme connexió (monòtona) de Galois es referirà sempre a una connexió de Galois en el primer sentit. Si s'aplica la definició alternativa, es faran servir els termes connexió de Galois antítona o connexió de Galois inversora .

En realitat, les implicacions d'ambdues definicions són bastant similars, ja que les connexions antítonas de Galois entre A i B són simplement connexions monòtones de Galois entre A i l'ordre dual B ^op de B . Totes les afirmacions següents sobre les connexions de Galois es poden convertir fàcilment, per tant, en afirmacions sobre les connexions antítonas.

Noteu però, que no té sentit parlar d'adjunts inferior i superior d'una connexió antítona de Galois: la situació és completament simètrica.

Exemples

L'exemple motivador ve de la teoria de Galois: Suposem una extensió de cossos L / K . Sigui A el conjunt de tots els subcossos de L que contenen K , ordenats per inclusió $\subseteq$ . Si E és un d'aquests subcossos, s'escriu Gal ( L / E ) el grup d'automorfismes de cossos de L que mantenen fix E . Sigui B el conjunt de subgrups de Gal ( L / K ), ordenats per inclusió $\subseteq$ . Per a un d'aquests subgrups G , es defineix Fix ( G ) com el cos que consisteix en tots els elements de L que es mantenen fixos per tots els elements de G . Llavors les funcions I $\mapsto$ Gal ( L / E ) i G $\mapsto$ Fix ( G ) formen una connexió antítona de Galois.

Per veure un exemple de teoria d'ordre, sigui U un conjunt, i siguin A i B els conjunts potència de U , ordenats per inclusió. Preneu-vos un subconjunt fix L de U . Llavors les funcions F i G , on F ( M ) és la intersecció de L i M , i G ( N ) és la unió de N i ( U \ L ), formen una connexió monòtona de Galois, sent F l'adjunt inferior. Es pot trobar en qualsevol àlgebra de Heyting una connexió de Galois similar l'adjunt inferior ve donat per l'operació ínfim. En particular, és present en tota àlgebra booleana, on es poden descriure dues funcions com F ( x ) = ( a $\wedge$ x ) i G ( i ) = ( i $\vee$ $\neg$ a ) = ( a $\rightarrow$ i ). En termes lògics: "implicació" és l'adjunt superior de "conjunció".

En l'article sobre propietats de completesa hi ha més exemples interessants de connexions de Galois. Resulta que les familiars funcions $\vee$ i $\wedge$ són adjunts en dues connexions de Galois possibles. Passa el mateix amb les funcions del conjunt d'un element que assenyala els elements ínfim i suprem d'un ordre parcial. Anant més enllà, fins i tot es pot caracteritzar els reticles complets mitjançant l'existència d'adjunts adequats. Aquestes consideracions donen una impressió de la ubiqüitat de les connexions de Galois en la teoria de l'ordre.

En geometria algebraica, la relació entre conjunts de polinomis i els seus conjunts de zeros és una connexió antítona de Galois: fixi un nombre natural n i un cos K i sigui A el conjunt de tots els subconjunts de l'anell polinòmic K[X₁,..., X_n] ordenat per inclusió $\subseteq$ , i sigui B el conjunt de tots els subconjunts de Kⁿ ordenats per inclusió $\subseteq$ . Si S és un conjunt de polinomis, definim F(S) ={x $\in$ Kⁿ: f(x) = 0, $\forall$ f $\in$ S}, com el conjunt de zeros comuns dels polinomis de S. Si T és un subconjunt de Kⁿ, definim G(T) ={f $\in$ K[X₁,..., X_n]: f (x) = 0, $\forall$ x $\in$ T}. Llavors F i G formen una connexió antítona de Galois.

Si f : X → I és una funció, llavors per a tot subconjunt M de X podem formar la imatge F ( M ) = f ( M ) ={ f ( m ): m $\in$ M }i per a qualsevol subconjunt N de I podem formar la imatge inversa G ( N ) = f ^-1 ( N ) ={ x $\in$ X : f ( x ) $\in$ N }. Llavors F i G formen una connexió monòtona de Galois entre els conjunts potència X i I , ordenats tots dos per inclusió $\subseteq$ . Hi ha un altre parell d'adjunts més en aquesta situació: per a un subconjunt M de X , definim H ( M ) ={ i $\in$ I : f ^-1 ({ i }) $\subseteq$ M }. Llavors G i H formen una connexió monòtona de Galois entre els conjunts potència I i X . En la primera connexió de Galois, G és l'adjunt superior, mentre que en la segona serveix com a adjunt inferior.

Prengui un objecte matemàtic X que tingui un conjunt subjacents, per exemple un grup, anell, espai vectorial, etc. Per a qualsevol subconjunt S de X , sigui F ( S ) el subobjectes de X més petit que contingui S , és a dir, el subgrup, subanell o subespai generat per S . Per a qualsevol subobjectes U de X , sigui G ( U ) el subconjunt subjacents a U (fins i tot podem prendre un espai topològic com X , sigui F ( S ) la clausura de S , i feu els subconjunts tancats de X com "subobjectes de X "). Ara, F i G formen una connexió monòtona de Galois si els conjunts i subobjectes estan ordenats per inclusió. F és l'adjunt inferior.

Un comentari molt general de Martin Hyland és que sintaxi i semàntica són adjuntes: prengui A , el conjunt de totes les teories lògiques (axiomatitzar), i B el conjunt potència del conjunt de totes les estructures matemàtiques. Per a una teoria T $\in$ A , sigui F ( T ) el conjunt de totes les estructures que satisfan els axiomes T ; per a un conjunt d'estructures matemàtiques S , sigui G ( S ) l'axiomatización mínima de S . Podem dir llavors que F ( T ) és un subconjunt de S si i només si T implica lògicament G ( S ): el "funtor semàntic" F i el "funtor de sintaxi " G formen una connexió monòtona de Galois, i la semàntica l'adjunt inferior.

Finalment, Suposeu X i I dos conjunts arbitraris i una relació binària R donada sobre X i I . Per a qualsevol subconjunt M de X , definim F ( M ) ={ i $\in$ I : MRY $\forall$ m $\in$ M }. De manera similar, per a qualsevol subconjunt N de I , definim G ( N ) ={ x $\in$ X : xRn $\forall$ n $\in$ N }. Llavors F i G constitueixen una connexió antítona de Galois entre els conjunts potència de X i I , ordenats tots dos per inclusió $\subseteq$ .

Propietats

D'ara endavant, suposarem una connexió (monòtona) de Galois f = ( f ^*, f _*), on f ^*: A → B és l'adjunt inferior tal com s'ha presentat anteriorment. Es poden obtenir immediatament algunes propietats bàsiques útils i instructives. Segons la propietat per definició de les connexions de Galois, f ^* ( x ) ≤ f ^* ( x ) és equivalent a x ≤ f _* ( f ^* ( x )), per a tot x de A . Amb un raonament similar (o aplicant sense més el principi de dualitat de la teoria de l'ordre), trobem que f ^* (f_*(i)) ≤ i, per a tot i de B. Aquestes propietats poden descriure dient que la composició f^* $\circ$ f_* és deflacionària , mentre que f_* $\circ$ f^* és inflacionària (o extensiva).

Si ara considerem qualssevol elements x i i de A tals que x ≤ i , llavors podem usar clarament això per obtenir x ≤ f_* (f^* ( i )). Aplicant la propietat bàsica de les connexions de Galois, podem concloure que f^* (x) ≤ f^* ( i ). Però això únicament mostra que f^* conserva l'ordre de qualssevol dos elements, és a dir, és monòtona. De nou, un raonament semblant li assigna monotonicitat a f_*. Per tant la monotonicitat no té per què incloure explícitament en la definició. No obstant això, esmentar ajuda a evitar confusions sobre això de les dues nocions alternatives de les connexions de Galois.

Una altra propietat bàsica de les connexions de Galois és el fet que f_* (f^* (f_*(x))) = f_*(x), per a tot x de B. Veiem clarament que

f_*(f^*(f_*(x))) ≥ f_*(x)

perquè f_* $\circ$ f^* és inflacionista com hem vist abans. De manera similar, ja que f^* $\circ$ f_* és deflacionària, trobem que

f^* f_* f^* f_*(x) ≤ f^* f_* (x) ≤ x,

que és equivalent a

f_*(f^*(f_*(x))) ≤ f_*(x).

Això mostra la igualtat desitjada. Encara més, podem utilitzar aquesta propietat per concloure que

f^*(f_*(f^*(f_*(x)))) = f^*(f_*(x)),

és a dir, f^* $\circ$ f_* és idemponent.

Operadors de cloenda i connexions de Galois

Allò que s'ha exposat anteriorment es pot resumir de la manera següent: per a una connexió de Galois, la composició f _* $\circ$ f ^* és monòtona (sent la composició de funcions monòtones), inflacionària i idempotent. Això estableix que f _* $\circ$ f ^* és de fet un operador de cloenda sobre A . Dualment, f ^* $\circ$ f _* és monòtona, deflacionària i idempotent. Aquestes funcions s'anomenen de vegades operadors de nucli .

Al revés, qualsevol operador de clausura c sobre un Poset A dona origen a la connexió de Galois amb adjunt inferior f ^* que no és més que la correstricción de c a la imatge de c (és a dir, una funció sobreyectiva del sistema de cloenda c ( A )). Llavors l'adjunt superior f _* el dona la inclusió de c ( A ) en A , que fa correspondre cada element tancat sobre si mateix, considerat com un element de A . D'aquesta manera, es veuen estretament relacionats els operadors de clausura i les connexions de Galois, especificant cadascun una instància de l'altre. S'arriba a conclusions similars per als operadors de nucli.

Les consideracions anteriors mostren també que els elements tancats de A (elements x amb f _* ( f ^* ( x )) = x ) es corresponen amb elements dins del rang de l'operador de nucli f ^* $\circ$ f _*, i viceversa.

Existència i unicitat de les connexions de Galois

Una altra propietat important de les connexions de Galois és que els adjunts inferiors conserven tots els suprems que hi ha dins del seu domini. Dualment, els adjunts superiors conserven tots els ínfims. D'aquestes propietats un pot concloure immediatament també la monotonicitat dels adjunts. El teorema del funtor adjunt de la teoria d'ordre estableix que la implicació inversa és vàlida també en certs casos: especialment, qualsevol funció entre reticles complets que conservi tots els suprems és l'adjunt inferior d'una connexió de Galois.

En aquesta situació, una característica important de les connexions de Galois és que un adjunt determina unívocament l'altre. Per tant podem endurir l'afirmació anterior per garantir que qualsevol funció que conservi el suprem entre reticles complets és l'adjunt inferior d'una connexió de Galois única. La propietat principal per derivar aquesta unicitat és la següent: per cada x de A , f ^* ( x ) és el menor element i de B tal que x ≤ f _* ( i ). Dualment, per a cada i de B , f _* ( i ) és el major x de A tal que f ^* ( x ) ≤ i . L'existència d'una certa connexió de Galois implica ara l'existència dels respectius elements suprem i ínfim, independentment de si els Posets corresponents satisfan alguna propietat de completesa. Per tant, quan es dona un adjunt d'una connexió de Galois, podem definir l'altre mitjançant aquesta propietat. D'altra banda, una funció f és un adjunt inferior si i només si cada conjunt de la forma{ x de A | f ( x ) ≤ b }, b de B , conté un element suprem. De nou, això es pot dualitzar per l'adjunt superior.

Connexions de Galois com morfismes

Les connexions de Galois proporcionen també una classe interessant de funcions entre Posets que poden usar-se per obtenir categories de Posets. En particular, és possible compondre connexions de Galois: donades les connexions de Galois ( f ^*, f _*) entre els Posets A i B i ( g ^*, g _*) entre B i C , la composició ( g ^* $\circ$ f ^*, f _* $\circ$ g _*) també és una connexió de Galois. Quan considerem categories de reticles complets, això es pot simplificar per considerar només funcions que conservin tots els suprems (o ínfims). Fent correspondre reticles complets als seus duals, aquestes categories mostren acte dualitat, que són bastant fonamentals per obtenir altres teoremes de dualitat. Un tipus més especial de morfismes que indueixen funcions adjuntes en l'altra direcció són els morfismes considerats normalment per marcs (o locals).

Connexió amb la teoria de categories

Cada conjunt parcialment ordinador pot veure com una categoria de manera natural: hi ha un morfisme únic de x a i si i només si x ≤ i . Llavors una connexió de Galois no és sinó un parell de funtor adjunts entre dues categories que sorgeixen de conjunts parcialment ordenats. En aquest context, l'adjunt superior és l'adjunt dret mentre que l'adjunt inferior és l' adjunt esquerre . No obstant això, s'evita aquesta terminologia per a connexions de Galois, ja que hi va haver un temps en què els Posets es transformaven en categories de manera dual, és a dir, amb fletxes apuntant en la direcció oposada. Això va portar a una notació complementària fa a adjunts esquerres i drets, que actualment és ambigua.

Aplicacions en la teoria de la programació

Les connexions de Galois es poden usar per descriure moltes formes d'abstracció en la teoria d'interpretació abstracta de llenguatges de programació.

Referències

Una introducció a les connexions de Galois disponible gratuïtament, que presenta molts exemples i resultats. També inclou notes sobre les diferents notacions i definicions que sorgeixen en aquesta àrea:

M. Erne, J. Koslowski, A. Melton, G. E. Strecker, A primer on Galois connections , en: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, Vol 704, 1993, pp. 103-125. Disponible en línia en diversos formats: PS.GZ Arxivat 2006-01-08 a Wayback Machine. ksu.edu/# Strecker/primer.ps PS Arxivat 2013-07-20 a Wayback Machine.

Els següents llibres estàndard de referència inclouen també connexions de Galois usant notació i definicions modernes:

B. A. Davey and H. A. Priestley: Introduction to lattices and Order , Cambridge University Press, 2002.
G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: Continuous Lattice and Domains , Cambridge University Press, 2003.

Finalment, algunes publicacions que fan servir la definició original (antítona):

Garrett Birkhoff: Lattice Theory , Amer. Math. Soc Coll. Pub, Vol 25, 1940
Øystein Ore: Galois Connexions , Transactions of the American Mathematical Society 55 (1944), pp. 493-513

Nota