Gratis galler

Inom matematiken , inom ordningsteorin , är ett fritt gitter det fria objektet som motsvarar ett gitter . Som fria föremål har de den universella egenskapen .

Formell definition

Vilken som helst uppsättning X kan användas för att generera den fria halvgittret FX . Det fria halvgittret definieras till att bestå av alla de finita delmängderna av X , med halvgittrets operation ges av ordinär mängdunion . Det fria halvgittret har den universella egenskapen . Den universella morfismen är ( FX , η ) , där η är enhetskartan η: X → FX som tar x ∈ X till singeluppsättningen { x }. Den universella egenskapen är då som följer: givet valfri karta f : X → L från X till något godtyckligt semigitter L , existerar det en unik semigitterhomomorfism ${\tilde {f}}:FX\ till L$ så att $f={\tilde {f}}\circ \eta$ . Kartan ${\tilde {f}}$ kan vara explicit nedskriven; den ges av

S\in FX\mapsto \bigvee \left\{f(s)\mid s\in S\right\}

där $\bigvee$ anger halvgitteroperationen i L . Denna konstruktion kan främjas från semigitter till galler ^{[ förtydligande behövs ]} ; genom konstruktion kommer kartan ${\tilde {f}}$ att ha samma egenskaper som gittret.

Konstruktionen X ↦ FX är då en funktion från kategorin mängder till kategorin gitter. Funktionen F lämnas intill den glömska funktorn från gitter till deras underliggande uppsättningar. Det fria gittret är ett fritt objekt .

Ordproblem

Ordet problem för fria gitter och fritt avgränsade gitter kan avgöras med hjälp av en induktiv relation. Lösningen har flera intressanta följder. En är att det fria gittret för en treelementsuppsättning generatorer är oändlig. I själva verket kan man till och med visa att varje fritt gitter på tre generatorer innehåller ett subgitter som är fritt för en uppsättning av fyra generatorer. Genom induktion ger detta så småningom ett subgitter fritt på oräkneligt många generatorer. Den här egenskapen påminner om SQ-universalitet i grupper .

Beviset på att det fria gittret i tre generatorer är oändligt sker genom att induktivt definiera

p _{n +1} = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p _n ))))))

₀ där x , y och z är de tre generatorerna och p = x . Man visar sedan, med hjälp av ordproblemets induktiva relationer, att p _{n +1} är strikt större än p _n , och därför evalueras alla oändligt många ord p _n till olika värden i det fria gittret FX .

Det kompletta fria gallret

En annan följd är att det fullständiga fria gittret (på tre eller flera generatorer) "inte existerar", i den meningen att det är en riktig klass . Beviset för detta följer också av ordet problem. För att definiera ett komplett gitter i termer av relationer räcker det inte att använda de finitära relationerna möta och gå med ; man måste också ha oändliga relationer som definierar mötet och sammanfogningen av oändliga delmängder. Till exempel kan den oändliga relationen som motsvarar "join" definieras som

\operatörsnamn {sup} _{N}:(f:N\to FX)

Här är f en karta från elementen i en kardinal N till FX ; operatorn $\operatorname {sup} _{N}$ betecknar supremum, genom att den tar bilden av f till dess sammanfogning. Detta är naturligtvis identiskt med "join" när N är ett ändligt tal; poängen med denna definition är att definiera join som en relation, även när N är en oändlig kardinal.

Axiomen för förbeställningen av ordproblemet kan angränsas av de två infinitära operatorerna som motsvarar möte och sammanfogning. Efter att ha gjort det utökar man sedan definitionen av $p_{n}$ till en ordinärt indexerad $p_{\alpha }$ som ges av

p_{\alpha }=\operatörsnamn {sup} \{p_{\beta}\mid \beta <\alpha \}

när $\alpha$ är en limitordinal . Sedan, som tidigare, kan man visa att $p_{\alpha +1}$ är strikt större än $p_{\alpha }$ . Det finns alltså minst lika många element i det kompletta fria gittret som det finns ordinaler, och därför kan det fullständiga fria gittret inte existera som en mängd, och måste därför vara en riktig klass.

Peter T. Johnstone, Stone Spaces , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ( ISBN 0-521-23893-5 ) (Se kapitel 1)