Trellis (objednaná sada)

V matematice je mřížka (v angličtině : mřížka ) jednou z algebraických struktur používaných v obecné algebře . Jedná se o částečně uspořádanou množinu, ve které má každá dvojice prvků horní a dolní hranici . Mřížkový může být viděn jako Galoisova mřížka s binární relace .

Ve skutečnosti existují dvě ekvivalentní definice mřížky, jedna se týká vztahu výše uvedeného řádu, druhá algebraická.

Předběžné příklady a protiklady

Jakákoli sada poskytovaná se vztahem k celkovému řádu je mřížka. Například libovolná sada reálných čísel poskytovaná v obvyklém pořadí.

Mezi množinami opatřenými vztahem částečného řádu jsou jednoduché příklady svazů výsledkem vztahů řádu „je zahrnuto v“ a „dělí“.

Sada dílů sady opatřený začlenění tvoří mříž, kde je horní hranice je sjednocení a dolní mez křižovatku.
Pokud je část mřížky stabilní horní a dolní mezí, tvoří mříž (pro omezené pořadí). Takto sada otvorů topologického prostoru (vždy poskytovaná se zahrnutím) a filtr na sadě tvoří mřížky.
Tato podmínka stability není nutná:
- množina uzavřených intervalů ℝ (včetně prázdné množiny) je mřížka, jejíž dolní mez je křižovatkou a jejíž horní hranice není vždy sjednocení: tedy horní hranice intervalů [1, 3] a [4, 5] je interval [1, 5];
- množinou vztahů ekvivalence na dané množině je mřížka (seřazená podle plynulosti binárních vztahů ), jejíž dolní mez je průsečík (na grafech), ale horní hranice je vztah ekvivalence generovaný l 'unií.
Sada přirozených čísel s relací „rozdělit“ tvoří mřížku, kde horní hranice je PPCM a dolní hranice je GCD .
Pro jakékoli celé číslo n ≥ 3 není množina celých čísel od 1 do n , obdařená relačním řádem „divide“, mřížkou, protože dvojice { n , n - 1} nemá žádnou větší ani horní hranici (protože jakoukoli násobek n a n - 1 je násobkem n ( n - 1), která je> n ).
Nestačí, aby každý pár měl horní a dolní mez, aby získal mřížku. V relaci popsané opačným Hasseho diagramem tedy dvojice {b, c} připouští tři horní limity d, e a f, ale žádná horní mez, protože {d, e, f} nemá menší prvek.

Algebraická definice

Mřížka je množina E opatřená dvěma vnitřními zákony, které se obvykle zaznamenávají noted a ⋀ ověřující:

dva zákony jsou komutativní a asociativní ;
pro všechny $A$ a $B$ z E : ( absorpce zákon ). $a \ klín (a \ vee b) = a = a \ vee (a \ klín b)$

Zákon absorpce s sebou nese idempotence jakéhokoli prvku A z E na obou zákonů:

{\ displaystyle a \ vee a = a \ qquad {\ text {a}} \ qquad a \ klín a = a}

Z takové struktury lze definovat na E je vztah pořadí , poznamenat ≤, následujícím způsobem:

{\ displaystyle a \ leq b \ šipka doleva a \ vee b = b}

Můžeme ukázat, že tento vztah je skutečně řádový (možná částečný). Vlastnost asociativity zajišťuje tranzitivitu . Vlastnost idempotence zajišťuje reflexivitu . Komutativita zajišťuje antisymetrii . Díky dvěma absorpčním vlastnostem to také můžeme ukázat

{\ displaystyle a \ leq b \ Šipka vlevo a \ klín b = a}

Poté to můžeme ověřit

{\ displaystyle \ sup (a, b) = a \ vee b \ qquad {\ text {et}} \ qquad \ inf (a, b) = a \ klín b}

což zajišťuje, že se skutečně jedná o mříž ve smyslu objednávek. ${\ displaystyle (E, \ leq)}$

Definice vztahem objednávky

Mřížka je množina E opatřená vztahem objednávky ověřujícím:

pro všechny prvky a a b z E existuje horní a dolní mez množiny { a , b }.

Abychom E poskytli algebraickou mřížkovou strukturu, všimli jsme si, že horní a dolní mez pak definují dva vnitřní zákony:

${\ displaystyle a \ vee b = \ sup (a, b)}$ ;
$a \ klín b = \ inf (a, b)$ .

Vlastnosti algebraické mřížky pro tyto dva zákony vyplývají zcela přímo z definice.

Mřížky jsou proto definovány buď algebraicky, nebo vztahem objednávky.

Příhradový glosář

Uspořádaná množina, ve které má každá dvojice prvků horní mez (nebo dolní mez), je poloviční mřížka .

Poloviny mřížky morfismus od ( L , ∨ L ) až ( M , ∨ M ) je mapa f : L → M tak, že pro všechny , b ∈ L , f ( ∨ L b ) = f ( a ) ∨ M f ( b ). Říkáme, že je to vložení (poloviční mřížky), pokud je f také injektivní . Definice morfismu a vložení mřížky jsou potom samozřejmé.Příklad: mříž z oddílů z řady $X$ - isomorphic do mřížky ekvivalence na $X$ - je ponořen do mřížky podskupin ze symetrického skupiny $S ( X )$ , spojením na každý oddíl $n$ podskupině $Π A \in π S ( A )$ .Jakýkoli morfismus (resp. Jakékoli vložení) mřížky (nebo dokonce poloviční mřížky) je morfismus (resp. Vložení) uspořádaných množin, ale převrácené hodnoty jsou nepravdivé a dokonce: jakákoli mřížka je ponořena do mřížky vztahů ekvivalence na určité množině, kterou lze navíc zvolit konečnou, pokud je mřížka.

O mřížce se říká, že je distributivní (en), pokud je právo ⋁ distribuční vzhledem k zákonu ⋀, nebo znovu (což je v mřížce ekvivalentní), pokud je právo ⋀ distribuční vzhledem k zákonu ⋁.

Mřížka se říká, že je ohraničená, pokud má maximum a minimum. Sada přirozených celých čísel obdarovaných vztahem řádu ≤ tedy není omezena, ale stejná sada obdarená vztahem řádu „rozdělí“ je omezená mřížka, jejíž minimum je 1 a maximum 0.

O ohraničené mřížce se říká, že se doplňuje, pokud má každý její prvek x komplement y splňující x ⋀ y = 0 a x ⋁ y = 1, kde 0 označuje minimální prvek mřížky a 1 maximální prvek.

Ohraničená a doplňovaná distribuční mřížka se také nazývá booleovská algebra .

Mřížka E je považována za úplnou, pokud má kterákoli část E horní hranici, nebo znovu (což je ekvivalentní, viz níže ), pokud má kterákoli část E dolní hranici.

V příhradové E , který má minimální označenou 0, atomy jsou minimální prvky v E \ {0}. Například v mřížce množiny částí množiny jsou atomy singletony. Některé mřížky s minimem nemusí mít atomy. To je například případ ℝ + , stejně jako množiny pravidelných otvorů (stejných otvorů uvnitř jejich adheze ) topologického prostoru opatřeného inkluzí.

Ideální mřížka E je neprázdná I , který je při provozu ⋁ a která je taková, že pokud x ∈ E a y ∈ I , pak x ⋀ y ∈ I .

Vzhledem k tomu, podmnožina z množiny X , sada dílů A je ideální mřížka všech částí X .

Kompletní mřížoví

V mřížce má jakákoli konečná část E horní a dolní hranici, ale ne vždy to platí pro nekonečné části, i když je omezená: množina racionálních čísel mezi 0 a 2 je omezená mřížka, ale není kompletní, protože sada racionálních čísel této sady, jejíž čtverec je menší než 2, nemá horní hranici.

Garrett Birkhoff představil následující význam epiteta „úplný“: o uspořádané množině se říká, že je úplná, pokud má kterákoli část horní mez (včetně prázdné množiny, která vyžaduje, aby E měla minimum). Toto je ekvivalentní jakékoli části, která má dolní mez (včetně prázdné množiny, která stanoví, že E má maximum).

Také říkáme, že E je zcela síťovaný prostor . V teoretické informatice má zkratka English CPO , i když její doslovný překlad „úplný částečný řád“, jiný význam. Aby nedocházelo k záměně s jiným pojmem úplného prostoru , tedy ve smyslu metrických prostorů nebo obecněji jednotných prostorů , navrhl Bourbaki termín dokončený , který nebyl uložen. Tedy ℝ (což je pro obvyklou vzdálenost úplné) není tedy dokončeno, ale ℝ = ℝ ⋃ ${-\infty, + \infty} ano$ , proto je dokončen název jeho skutečné linky . ℝ je ve skutečnosti vyplněný (in) (ve smyslu Dedekind - MacNeille (in) ) ℝ, to znamená nejmenší úplná mřížka obsahující ℝ.

Další příklady.

Každý segment je úplná mříž.
Sada částí sady je úplná mřížka pro zahrnutí.
Pro jakékoliv části G úplné mřížky, dílčí mřížky horní hranici pro G je kompletní (a stejný pro to dolní mez).
V teorii integrace, jestliže f a g jsou dvě borelianské funkce na ℝ, integrovatelné ve smyslu Lebesgue a ověřující f <g , je množina borelianských funkcí h zahrnutá mezi f a g neúplnou mřížkou, která se stane úplnou, pokud identifikujeme dvě stejné funkce téměř všude (všimněte si! horní hranice rodiny borelianských funkcí může být neměřitelná; když kvocient modulo rovnosti téměř všude, podíváme se na to, co se nazývá horní základní hranice , která, když se vrátíme k funkcím, téměř všude zvětší každý prvek z rodiny).

Knaster-Tarskiho věta : jakákoli rostoucí mapa úplné mřížky má sama o sobě pevný bod.

Dualita

Pokud je mřížka, pak její duální mřížka je . ${\ displaystyle (E, \ vee, \ klín, \ leq)}$ ${\ displaystyle (E, \ klín, \ vee, \ geq)}$

Dualita věta : Pokud je věta T platí pro všechny mříží pak dvojí teorém T, získané nahrazením všechny výskyty podle (a naopak) a všechny výskyty podle (a naopak) je věta platí pro všechny mřížoví. $\ vee$ $\ klín$ $\ leq$ $\ geq$

Poznámky a odkazy

N. Bourbaki , Základy matematiky : Teorie množin [ detail vydání ], str. ER.28 , viděný v Knihách Google , hovoří o „ síťovaném celku nebo objednané síti (nebo mřížce )“ .
Skutečně, a také obrácením obou zákonů. $a \ lor a = a \ lor (a \ land (a \ lor a)) = a$
(in) Philip Whitman (in) , „ Mřížky, vztahy ekvivalence a podskupiny “ , Bull. Hořký. Matematika. Soc. , sv. 52,1946, str. 507-522 ( číst online ).
(in) Pavel Pudlak Jiří Tůma, „ Každá konečná mříž může být vložena do přepážky konečné mřížky “ , Algebra Universalis , sv. 10,1980, str. 74-95 ( číst online ).
Opravdu, pokud je například ⋁ distribuční ve srovnání s ⋀, pak ${\ Displaystyle (a \ land c) \ lor (b \ land c) = [a \ lor (b \ land c)] \ land [c \ lor (b \ land c)] = (a \ lor b) \ land (a \ lor c) \ land c = (a \ lor b) \ land c}$ proto je distribut distribuční vzhledem k ⋁.
Viz například toto opravené cvičení na Wikiversity .
Viz také stránky disambiguation Complétude a Complet .

Podívejte se také

Související články

Bibliografie

Zdroje dostupné online:
- Garrett Birkhoff , „ Teorie a aplikace mřížek “, Annals of IHP , sv. 11, n o 5,1949, str. 227-240 ( číst online )
- (en) Stanley N. Burris a HP Sankappanavar, Kurz univerzální algebry , Springer Verlag , 1981 ( ISBN 978-3-540-90578-3 )
- (en) Peter Jipsen a Henry Rose, Odrůdy mřížek , Springerova přednáška z matematiky 1533 , 1992 ( ISBN 978-0-387-56314-5 )
Příručky:
- (en) Thomas Donnellan, Lattice Theory , Pergamon Press , 1968
- (en) G. Grätzer, Lattice Theory: First concepts and distributive lattices , WH Freeman, 1971
- (en) BA Davey a HA Priestley, Introduction to Lattices and Order , Cambridge University Press , 2002
- (en) Garrett Birkhoff, Lattice Theory , AMS Colloquium Publications, sv. 25, 3 e ed., 1967