Volná mříž - Free lattice

V matematiky , v oblasti teorii objednávky , je volný mřížka je volný objekt odpovídající mřížky . Jako volné objekty mají univerzální vlastnost .

Formální definice

Jakékoli set X může být použita k vytvoření volného semilattice FX . Volný semilattice je definována jako sestávající ze všech konečných podskupin z X , s semilattice operace dané běžného set unie . Volná semilattice má univerzální vlastnost . Univerzální morfismus je ( FX , η) , kde η je mapa jednotka η: X → FX , který má x ∈ X k ojedinělým množiny { x }. Univerzální vlastnost je pak následující: vzhledem k libovolné mapě f : X → L od X do libovolné semilattické L , existuje jedinečný semilattický homomorfismus takový . Mapa může být výslovně zapsána; je to dáno ${\ displaystyle {\ tilde {f}}: FX \ na L}$${\ displaystyle f = {\ tilde {f}} \ circ \ eta}$${\ displaystyle {\ tilde {f}}}$

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

kde označuje operaci semilattice v L . Tuto konstrukci lze povýšit ze semilattices na mřížky ; konstrukcí bude mít mapa stejné vlastnosti jako mříž. ${\ displaystyle \ bigvee}$${\ displaystyle {\ tilde {f}}}$

Konstrukce X ↦ FX je potom funktorem z kategorie množin do kategorie svazů. Funktor F je ponechán adjungovaný na zapomnětlivý funktor od mřížek po jejich základní množiny. Volná mřížka je volný objekt .

Slovní úloha

Příklad výpočtu x ∧ z ~ x ∧ z ∧ ( x ∨ y )

x ∧ z ∧ ( x ∨ y ) ≤ ~ x ∧ z o 5. od té doby x ∧ z ≤ ~ x ∧ z o 1. od té doby x ∧ z = x ∧ z

x ∧ z ≤ ~ x ∧ z ∧ ( x ∨ y ) do 7. od té doby x ∧ z ≤ ~ x ∧ z a x ∧ z ≤ ~ x ∨ y o 1. od té doby x ∧ z = x ∧ z do 6. od té doby x ∧ z ≤ ~ X o 5. od té doby X ≤ ~ X o 1. od té doby X = X

Slovní úloha zdarma svazů má některé zajímavé aspekty. Uvažujme případ omezených svazů , tj. Algebraických struktur se dvěma binárními operacemi ∨ a ∧ a dvěma konstantami ( operace s nullou ) 0 a 1. Sada všech dobře tvarovaných výrazů, které lze pomocí těchto operací formulovat na prvky z daného sada generátorů X se bude jmenovat W ( X ). Tato sada slov obsahuje mnoho výrazů, které v každé mřížce označují stejné hodnoty. Pokud je například a nějaký prvek X , pak a  ∨ 1 = 1 a a  ∧ 1 = a . Slovní úloha pro volné ohraničených mřížek je problém určení, která z těchto prvků W ( x ) označuje to samé, prvek na volném ohraničené mřížky FX , a tudíž v každém ohraničené mřížky.

Slovní úlohu lze vyřešit následovně. Vztah ≤ _~ na W ( X ) lze definovat indukčně nastavením w ≤ _~ v právě tehdy, když platí jedna z následujících možností:

1.   w = v (to může být omezeno na případ, kdy w a v jsou prvky X ),
2.   w = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ a obě w ₁ ≤ _~ v a w ₂ ≤ _~ v drží,
5.   w = w ₁ ∧ w ₂ a buď w ₁ ≤ _~ v nebo w ₂ ≤ _~ v platí,
6.   v = v ₁ ∨ v ₂ a buď w ≤ _~ v ₁ nebo w ≤ _~ v ₂ platí,
7.   v = v ₁ ∧ v ₂ a obě w ≤ _~ v ₁ a w ≤ _~ v ₂ platí.

Toto definuje předobjednávku ≤ _~ na W ( X ), takže vztah ekvivalence lze definovat pomocí w ~ v, když w ≤ _~ v a v ≤ _~ w . Jeden pak může ukázat, že částečně uspořádaný kvocientový prostor W ( X ) / ~ je volně ohraničená mřížka FX . Tyto třídy ekvivalence z W ( X ) / ~ jsou množiny všech slov w a proti s w ≤ _~ v a v ≤ _~ w . Dvě dobře tvarovaná slova v a w ve W ( X ) označují stejnou hodnotu v každé ohraničené mřížce právě tehdy, když w ≤ _~ v a v ≤ _~ w ; tyto podmínky lze účinně rozhodnout pomocí výše uvedené indukční definice. Tabulka ukazuje příklad výpočtu, který ukazuje, že slova x ∧ z a x ∧ z ∧ ( x ∨ y ) označují stejnou hodnotu v každé ohraničené mřížce. S případy mřížek, které nejsou ohraničené, se zachází podobně, s vynecháním pravidel 2. a 3. ve výše uvedené konstrukci.

Řešení slovní úlohy na volných mřížkách má několik zajímavých důsledků. Jedním z nich je, že volná mřížka tříprvkové sady generátorů je nekonečná. Ve skutečnosti lze dokonce ukázat, že každá volná mřížka na třech generátorech obsahuje sublattice, která je volná pro sadu čtyř generátorů. Tím, indukce , to nakonec získá sublattice zdarma na countably mnoha generátorů. Tato vlastnost připomíná univerzálnost SQ ve skupinách .

Důkaz, že volná mřížka ve třech generátorech je nekonečná, probíhá indukčním definováním

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

kde x , y , a z jsou tři generátory, a p ₀ = x . Jeden pak pomocí indukčních vztahů slovní úlohy ukazuje, že p _{n +1} je striktně větší než p _n , a proto všech nekonečně mnoho slov p _n vyhodnotí na různé hodnoty ve volné mřížce FX .

Úplná volná mříž

Dalším důsledkem je, že úplná volná mřížka (na třech nebo více generátorech) „neexistuje“ v tom smyslu, že se jedná o správnou třídu . Důkaz toho vyplývá i ze slovní úlohy. Chcete-li definovat úplný svaz , pokud jde o vztahy, nestačí používat finitary vztahy k setkat a spojit ; člověk musí mít také nekonečné vztahy definující setkávání a spojování nekonečných podmnožin. Například nekonečný vztah odpovídající „spojení“ lze definovat jako

${\ displaystyle \ operatorname {sup} _ {N} :( f: N \ to FX)}$

Zde je f mapa z prvků kardinálu N do FX ; operátor označuje supremum v tom, že pořizuje obraz f k jeho spojení. To je samozřejmě totožné s „spojením“, když N je konečné číslo; smyslem této definice je definovat spojení jako vztah, i když N je nekonečný kardinál. ${\ displaystyle \ operatorname {sup} _ {N}}$

Axiomy předobjednávky slovní úlohy mohou být spojeny dvěma nekonečnými operátory odpovídajícími splnění a připojení. Poté to rozšíří definici na ordinálně indexovanou danou ${\ displaystyle p_ {n}}$${\ displaystyle p _ {\ alpha}}$

${\ displaystyle p _ {\ alpha} = \ operatorname {sup} \ {p _ {\ beta} \ mid \ beta <\ alpha \}}$

kdy je limit pořadové číslo . Pak, stejně jako dříve, lze ukázat, že je přísně větší než . V úplné volné mřížce tedy existuje alespoň tolik prvků, kolik je řadových čísel, a tedy úplná volná mříž nemůže existovat jako množina, a proto musí být vlastní třídou. ${\ displaystyle \ alpha}$${\ displaystyle p _ {\ alpha +1}}$${\ displaystyle p _ {\ alpha}}$

Reference

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