Mříž (objednávka) - Lattice (order)

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Květen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A mříž je abstraktní struktura studovaná v matematický subdisciplíny teorie objednávek a abstraktní algebra. Skládá se z a částečně objednaná sada ve kterém každé dva prvky mají jedinečný supremum (také se nazývá nejmenší horní mez nebo připojit se ) a jedinečný infimum (nazývané také největší dolní mez nebo setkat ). Příkladem je přirozená čísla, částečně seřazeno podle dělitelnost, pro které je jedinečným supremem nejmenší společný násobek a jedinečným infimem je největší společný dělitel.

Mříže lze také charakterizovat jako algebraické struktury uspokojující jisté axiomatický identity. Jelikož jsou obě definice ekvivalentní, teorie mřížky čerpá z obou teorie objednávek a univerzální algebra. Semilattices zahrnují mřížky, které zase zahrnují Hej a Booleovy algebry. Všechny tyto „mřížovité“ struktury připouštějí teoretický řád stejně jako algebraické popisy.

Mříže jako částečně uspořádané sady

Li (L, ≤) je částečně objednaná sada (poset) a S ⊆ L je libovolná podmnožina, pak prvek u ∈ L se říká, že je horní hranice z S -li s ≤ u pro každého s ∈ S. Sada může mít mnoho horních hranic nebo vůbec žádnou. Horní mez u z S se říká, že je jeho nejmenší horní meznebo připojit senebo supremum, pokud u ≤ X pro každou horní hranici X z S. Sada nemusí mít alespoň horní mez, ale nemůže mít více než jednu. Duálně, l ∈ L se říká, že je dolní mez z S -li l ≤ s pro každého s ∈ S. Dolní mez l z S se říká, že je jeho největší dolní meznebo setkatnebo infimum, pokud X ≤ l pro každou dolní mez X z S. Sada může mít mnoho dolních mezí nebo vůbec žádné, ale může mít nanejvýš jednu největší dolní mez.

Částečně objednaná sada (L, ≤) se nazývá a spojit-semilattice pokud každá podskupina dvou prvků {A, b} ⊆ L má spojení (tj. nejmenší horní mez) a nazývá se a setkat-semilattice pokud má každá dvouprvková podmnožina splnění (tj. největší dolní mez), označeno A ∨ b a A ∧ b resp. (L, ≤) se nazývá a mříž pokud je to spojovací a setkávací semilattice. Tato definice činí ∨ a ∧ binární operace. Obě operace jsou monotónní vzhledem k danému pořadí: A₁ ≤ A₂ a b₁ ≤ b₂ to naznačuje A₁ ∨ b₁ ≤ A₂ ∨ b₂ a A₁ ∧ b₁ ≤ A₂ ∧ b₂.

Z toho vyplývá, že indukce argument, že každá neprázdná konečná podmnožina mřížky má nejméně horní a největší dolní mez. S dalšími předpoklady mohou být možné další závěry; vidět Úplnost (teorie objednávek) pro další diskusi o tomto tématu. Tento článek také pojednává o tom, jak lze výše uvedenou definici přeformulovat z hlediska existence vhodného Galoisova spojení mezi souvisejícími částečně uspořádanými soubory - přístup zvláštního zájmu pro teoretická kategorie přístup k mřížím a pro formální koncepční analýza.

A ohraničená mříž je mříž, která má navíc a největší prvek (také nazývaný maximumnebo horní prvek a označeno 1 nebo ${ displaystyle top}$) a a nejméně prvek (také nazývaný minimálnínebo dno, označeno 0 nebo ${ displaystyle bot}$), které uspokojují

0 ≤ X ≤ 1 za každou X v L.

Každá mřížka může být vložena do ohraničené mřížky přidáním umělého největšího a nejmenšího prvku a každá neprázdná konečná mřížka je ohraničena spojením (respektive splněním) všech prvků, označených ${ displaystyle bigvee L = a_ {1} lor cdots lor a_ {n}}$ (příslušně) ${ displaystyle bigwedge L = a_ {1} land cdots land a_ {n}}$) kde ${ displaystyle L = {a_ {1}, ldots, a_ {n} }}$.

Částečně uspořádaná množina je ohraničená mřížka právě tehdy, když má každá konečná množina prvků (včetně prázdné množiny) spojení a splnění. Pro každý prvek X posetu je to triviálně pravdivé (je to a prázdná pravda ) že ${ displaystyle forall a in varnothing: x leq a}$ a${ displaystyle forall a in varnothing: a leq x}$, a proto je každý prvek posetu horní i dolní mez prázdné množiny. To znamená, že spojení prázdné sady je nejméně elementem ${ displaystyle bigvee varnothing = 0}$, a setkání prázdné sady je největším prvkem ${ displaystyle bigwedge varnothing = 1}$. To je v souladu s asociativitou a komutativitou setkání a spojení: spojení unie konečných množin se rovná spojení spojení množin a duálně se setkání unie konečných množin rovná splnění sety množin, tj. pro konečné podmnožiny A a B poset L,

${ displaystyle bigvee left (A cup B right) = left ( bigvee A right) vee left ( bigvee B right)}$

a

${ displaystyle bigwedge left (A cup B right) = left ( bigwedge A right) wedge left ( bigwedge B right)}$

držet. Brát B být prázdná množina,

${ displaystyle bigvee left (A cup emptyset right) = left ( bigvee A right) vee left ( bigvee emptyset right) = left ( bigvee A right) vee 0 = bigvee A}$

a

${ displaystyle bigwedge left (A cup emptyset right) = left ( bigwedge A right) wedge left ( bigwedge emptyset right) = left ( bigwedge A right) klín 1 = bigwedge A}$

což odpovídá skutečnosti, že ${ displaystyle A cup emptyset = A}$.

Mřížový prvek y říká se Pokrýt jiný prvek X, pokud y > X, ale neexistuje a z takhle y > z > X.Tady, y > X prostředek X ≤ y a X ≠ y.

Mříž (L, ≤) je nazýván odstupňované, někdy zařadil (ale viz Hodnocená poseta pro alternativní význam), pokud může být vybaven a hodnostní funkce r z L do ℕ, někdy do ℤ, kompatibilní s objednávkou (tzv r(X) < r(y) kdykoli X < y) takové, že kdykoli y kryty X, pak r(y) = r(X) + 1. Hodnota hodnostní funkce pro mřížový prvek se nazývá jeho hodnost.

Vzhledem k podmnožině mřížky H ⊆ L, setkat se a připojit se omezit na dílčí funkce - nejsou definovány, pokud jejich hodnota není v podmnožině H. Výsledná struktura na H se nazývá a částečná mříž. Kromě této vnější definice jako podmnožiny nějaké jiné algebraické struktury (mřížka) lze částečnou mřížku také definovat jako soubor se dvěma částečnými binárními operacemi splňujícími určité axiomy.^[1]

Mřížky jako algebraické struktury

Obecná mříž

An algebraická struktura ${ displaystyle (L, curlyvee, curlywedge)}$, skládající se ze sady ${ displaystyle L}$ a dvě binární, komutativní a asociativní operace ${ displaystyle curlyvee}$, a ${ displaystyle curlywedge}$, na ${ displaystyle L}$ je mříž pokud následující axiomatická identita platí pro všechny prvky ${ displaystyle a, b, c v L}$, někdy nazývané absorpční zákony.

${ displaystyle a curlyvee (a curlywedge b) = a}$

${ displaystyle a curlywedge (a curlyvee b) = a}$

Následující dvě identity jsou také obvykle považovány za axiomy, i když vyplývají ze dvou absorpčních zákonů dohromady.^{[poznámka 1]}. Tito se nazývají idempotentní zákony.

${ displaystyle a curlyvee a = a}$

${ displaystyle a curlywedge a = a}$

Tyto axiomy tvrdí, že obojí ${ displaystyle (L, curlyvee)}$ a ${ displaystyle (L, curlywedge)}$ jsou pololattice. Absorpční zákony, jediné výše uvedené axiomy, ve kterých se oba setkávají a spojují, rozlišují mřížku od libovolného páru semilattických struktur a zajišťují, aby tyto dvě semilattice vhodně interagovaly. Zejména každá semilattice je dvojí toho druhého.

Ohraničená mříž

A ohraničená mříž je algebraická struktura formuláře ${ displaystyle (L, curlyvee, curlywedge, 0,1)}$ takhle ${ displaystyle (L, curlyvee, curlywedge)}$ je mříž, ${ displaystyle 0}$ (spodní část mřížky) je prvek identity pro operaci spojení ${ displaystyle curlyvee}$, a ${ displaystyle 1}$ (vrchol mřížky) je prvek identity pro operaci setkání ${ displaystyle curlywedge}$.

${ displaystyle a curlyvee 0 = a}$

${ displaystyle a curlywedge 1 = a}$

Vidět semilattice pro další detaily.

Napojení na jiné algebraické struktury

Mříže mají nějaká spojení s rodinou skupinové algebraické struktury. Vzhledem k tomu, že se setkáváte a připojujete k dojíždění i přidružování, mřížku lze považovat za sestávající ze dvou komutativních poloskupiny se stejnou doménou. Pro ohraničenou mřížku jsou tyto poloskupiny ve skutečnosti komutativní monoidy. The absorpční zákon je jedinou definující identitou, která je vlastní teorii mřížky.

Komutativitou, asociativitou a idempotencí lze uvažovat o spojení a setkávání jako o operacích na neprázdných konečných množinách, spíše než na dvojicích prvků. V ohraničené mřížce lze také definovat spojení a splnění prázdné množiny (jako ${ displaystyle 0}$ a ${ displaystyle 1}$). Díky tomu jsou ohraničené mřížky poněkud přirozenější než obecné mřížky a mnoho autorů vyžaduje ohraničení všech mřížek.

Algebraická interpretace svazů hraje zásadní roli v univerzální algebra.

Spojení mezi těmito dvěma definicemi

Řádově-teoretická mřížka vede ke dvěma binárním operacím ∨ a ∧. Protože komutativní, asociativní a absorpční zákony lze pro tyto operace snadno ověřit, vytvářejí je (L, ∨, ∧) do mřížky v algebraickém smyslu.

Opak je také pravdivý. Vzhledem k algebraicky definované mřížce (L, ∨, ∧), lze definovat dílčí pořadí ≤ zapnuto L nastavením

A ≤ b -li A = A ∧ bnebo

A ≤ b -li b = A ∨ b,

pro všechny prvky A a b z L. Zákony absorpce zajišťují rovnocennost obou definic:

A = A ∧ b naznačuje b = b ∨ (b ∧ A) = (A ∧ b) ∨ b = A ∨ b

a duálně pro druhý směr.

Nyní lze zkontrolovat, že takto zavedený vztah definuje částečné uspořádání, ve kterém se binární setkává a spojuje prostřednictvím původních operací ∨ a ∧.

Vzhledem k tomu, že dvě definice mřížky jsou ekvivalentní, lze volně vyvolat aspekty kterékoli z definic jakýmkoli způsobem, který vyhovuje danému účelu.

Příklady

• 

  Obr. 1: Podmnožiny {x, y, z}, pod nastavit zařazení. Název "mříž" je navržen ve formě Hasseův diagram zobrazující to.

• 

  Obr. 2: Mřížka celočíselných dělitelů 60, seřazená podle "rozděluje".

• 

  Obr. 3: Mřížka z oddíly z {1, 2, 3, 4}, objednáno někým "zušlechťuje".

• 

  Obr. 4: Mřížka kladných celých čísel, seřazená podle ≤.

• 

  Obr. 5: Mřížka nezáporných celočíselných párů, seřazená po částech.

• Pro jakoukoli sadu A, kolekce všech podskupin A (volal napájecí sada z A) lze objednat prostřednictvím zahrnutí podmnožiny získat mřížku ohraničenou A sám a prázdná sada. Soubor průsečík a unie interpretovat meet a join (viz obr. 1).
• Pro jakoukoli sadu A, sbírka všech konečných podskupin A, nařízeno začleněním, je také mřížkou a bude omezeno tehdy a jen tehdy A je konečný.
• Pro jakoukoli sadu A, sbírka všech oddíly z A, objednáno někým upřesnění, je mřížka (viz obr. 3).
• The kladná celá čísla v jejich obvyklém pořadí tvoří mřížku pod operacemi „min“ a „max“. 1 je dole; není tam žádný top (viz obr. 4).
• The Kartézské náměstí přirozených čísel, seřazeno tak (A, b) ≤ (C, d) -li A ≤ C a b ≤ d. Dvojice (0, 0) je spodní prvek; není tam žádný top (viz obr. 5).
• Přirozená čísla také tvoří mřížku pod operacemi přijímání největší společný dělitel a nejmenší společný násobek, s dělitelnost jako vztah objednávky: A ≤ b -li A rozděluje b. 1 je dole; 0 je nahoře. Obr. 2 ukazuje konečnou sublattice.
• Každý úplná mříž (viz také níže ) je (spíše specifická) ohraničená mříž. Tato třída dává vzniknout široké škále praktických příklady.
• Sada kompaktní prvky z aritmetický úplná mříž je mřížka s nejmenším prvkem, kde mřížkové operace jsou dány omezením příslušných operací aritmetické mřížky. Toto je specifická vlastnost, která odlišuje aritmetické mřížky od algebraické mřížky, pro které kompakty tvoří pouze a spojit-semilattice. Obě tyto třídy úplných svazů jsou studovány v teorie domény.

Další příklady svazů jsou uvedeny pro každou z dalších vlastností popsaných níže.

Příklady jiných než svazů

Obr. 8: Non-mřížka poset: A a b mají společné dolní hranice 0, d, G, h, a i, ale žádný z nich není největší dolní mez.

Obr. 7: Non-mřížka poset: b a C mají společné horní hranice d, E, a F, ale žádný z nich není nejmenší horní mez.

Obr. 6: Non-mřížka poset: C a d nemají společnou horní mez.

Většina částečně uspořádaných sad není mříž, včetně následujících.

• Diskrétní poset, což znamená takový poset X ≤ y naznačuje X = y, je mřížka právě tehdy, má-li nejvýše jeden prvek. Zejména dvouprvkový diskrétní poset není mříž.
• Ačkoli sada {1, 2, 3, 6} částečně uspořádaná dělitelností je mříž, množina {1, 2, 3} takto objednané není mřížka, protože dvojici 2, 3 chybí spojení; podobně 2, 3 postrádá setkání {2, 3, 6}.
• Sada {1, 2, 3, 12, 18, 36} částečně seřazené podle dělitelnosti není mříž. Každá dvojice prvků má horní a dolní hranici, ale dvojice 2, 3 má tři horní hranice, jmenovitě 12, 18 a 36, ​​z nichž žádný není nejmenší z těchto tří dělitelných (12 a 18 nerozdělují navzájem). Stejně tak dvojice 12, 18 má tři spodní hranice, a to 1, 2 a 3, z nichž žádná není největší z těchto tří dělitelnosti (2 a 3 se nerozdělují).

Morfismy mřížek

Obr. 9: Monotónní mapa F mezi mřížemi, které nezachovávají ani se nespojují, ani se nesetkají F(u) ∨ F(proti) = u′ ∨ u′ = u′ ≠ 1′ = F(1) = F(u ∨ proti) a F(u) ∧ F(proti) = u′ ∧ u′ = u′ ≠ 0′ = F(0) = F(u ∧ proti).

Vhodný pojem a morfismus mezi dvěma mřížemi snadno proudí z výše algebraická definice. Vzhledem k tomu, dvě mřížky (L, ∨_L, ∧_L) a (M, ∨_M, ∧_M), a mřížkový homomorfismus z L na M je funkce F : L → M takové, že pro všechny A, b ∈ L:

F(A ∨_L b) = F(A) ∨_M F(b), a

F(A ∧_L b) = F(A) ∧_M F(b).

Tím pádem F je homomorfismus ze dvou podkladových pololattice. Když se uvažuje o mřížích s větší strukturou, morfismy by také měly „respektovat“ zvláštní strukturu. Zejména a homomorfismus s omezenou mřížkou (obvykle se nazývá jen „mřížkový homomorfismus“) F mezi dvěma ohraničenými mřížemi L a M by měl mít také následující vlastnost:

F(0_L) = 0_M , a

F(1_L) = 1_M .

V teoreticko-řádové formulaci tyto podmínky pouze uvádějí, že homomorfismus mřížek je funkcí zachování binární setkání a připojení. U ohraničených svazů je zachování nejmenších a největších prvků pouze zachováním spojení a splnění prázdné množiny.

Jakýkoli homomorfismus mřížek je nutně monotónní s ohledem na související objednávkový vztah; vidět Funkce zachování limitu. Opak není pravdivý: monotónnost v žádném případě neznamená požadovanou ochranu setkání a spojení (viz obr. 9), ačkoli zachování objednávek bijekce je homomorfismus, pokud je inverzní je také zachování objednávek.

Vzhledem ke standardní definici izomorfismy jako invertibilní morfismy, a mřížkový izomorfismus je jen a bijektivní mřížkový homomorfismus. Podobně, a příhradový endomorfismus je mřížkový homomorfismus od mřížky k sobě samému a mřížkový automorfismus je bijektivní mřížkový endomorfismus. Mřížky a jejich homomorfismy tvoří a kategorie.

Sublattices

A sublattice mříže L je podmnožinou L to je mříž se stejnými operacemi setkání a spojování jako L. To je, pokud L je mřížka a M je podmnožinou L tak, že pro každou dvojici prvků A, b v M oba A ∧ b a A ∨ b jsou v M, pak M je sublattice z L.^[2]

Sublattice M mříže L je konvexní sublattice z L, pokud X ≤ z ≤ y a X, y v M to naznačuje z patří M, pro všechny prvky X, y, z v L.

Vlastnosti svazů

Nyní představujeme řadu důležitých vlastností, které vedou k zajímavým speciálním třídám mřížek. Jedna, omezenost, již byla diskutována.

Úplnost

Poset se nazývá a úplná mříž -li Všechno její podmnožiny mají spojení i setkání. Zejména každá úplná mříž je ohraničenou mřížkou. Zatímco omezené mřížkové homomorfismy obecně zachovávají pouze konečná spojení a splnění, pro zachování libovolných spojení a splnění jsou vyžadovány úplné mřížkové homomorfismy.

Každá poseta, která je úplnou semilattice, je také úplnou mřížkou. S tímto výsledkem souvisí zajímavý fenomén, že pro tuto třídu posetů existují různé konkurenční představy o homomorfismu, v závislosti na tom, zda jsou považovány za úplné svazy, úplné spojovací poloplátky, úplné spojovací poloplátky nebo za spojovací úplné nebo splňující kompletní mříže.

Všimněte si, že „částečná mřížka“ není opakem „úplné mřížky“ - spíše „částečná mřížka“, „mřížka“ a „úplná mřížka“ jsou stále více omezující definice.

Podmíněná úplnost

A podmíněně úplná mříž je mříž, ve které každý neprázdný podmnožina který má horní hranici má spojení (tj. nejméně horní mez). Takové mřížky poskytují nejpřímější zobecnění axiom úplnosti z reálná čísla. Podmíněně úplná mřížka je buď úplná mřížka, nebo úplná mřížka bez maximálního prvku 1, minimálního prvku 0 nebo obou.

Distribuce

Obr. 11: Nejmenší nemodulární (a tedy nedistribuční) mřížka N5. Označené prvky porušují rovnici distributivity C ∧ (A ∨ b) = (C ∧ A) ∨ (C ∧ b), ale uspokojit jeho dvojí C ∨ (A ∧ b) = (C ∨ A) ∧ (C ∨ b).

Obr. 10: Nejmenší nedistribuční (ale modulární) mříž M3.

Vzhledem k tomu, že mřížky přicházejí se dvěma binárními operacemi, je přirozené se zeptat, zda je jedna z nich distribuuje přes druhý, tj. zda jeden nebo druhý z následujících dvojí zákony platí pro každé tři prvky A, b, C z L:

Distribuce ∨ nad ∧

A ∨ (b ∧ C) = (A ∨ b) ∧ (A ∨ C).

Distribuce ∧ nad ∨

A ∧ (b ∨ C) = (A ∧ b) ∨ (A ∧ C).

Mříž, která splňuje první nebo ekvivalentně (jak se ukázalo), druhý axiom, se nazývá a distribuční mřížJediné nedistribuční mřížky s méně než 6 prvky se nazývají M.₃ a N₅;^[3] jsou zobrazeny na obrázcích 10 a 11. Mříž je distribuční právě tehdy, když nemá a sublattice izomorfní s M.₃ nebo N₅.^[4] Každá distribuční mřížka je izomorfní s mřížkou množin (se sjednocením a průnikem jako spojením a splněním).^[5]

Pro přehled silnějších pojmů distributivity, které jsou vhodné pro úplné mřížky a které se používají k definování více speciálních tříd mřížek, jako jsou rámy a zcela distribuční mřížky viz distributivita v teorii řádu.

Modularita

Pro některé aplikace je podmínka distribuce příliš silná a často je užitečná následující slabší vlastnost. Mříž (L, ∨, ∧) je modulární pokud pro všechny prvky A, b, C z L, drží následující identita.

Modulární identita

(A ∧ C) ∨ (b ∧ C) = ((A ∧ C) ∨ b) ∧ C.

Tato podmínka je ekvivalentní následujícímu axiomu.

Modulární zákon

A ≤ C naznačuje A ∨ (b ∧ C) = (A ∨ b) ∧ C.

Mříž je modulární právě tehdy, když nemá a sublattice isomorfní k N₅ (zobrazeno na obr. 11).^[4] Kromě distribučních mřížek jsou příklady modulárních mřížek mřížka oboustranné ideály a prsten, mřížka podmodulů a modul a mřížka normální podskupiny a skupina. The sada termínů prvního řádu s objednávkou "je konkrétnější než"je nemodulární mřížka používaná v automatické uvažování.

Semimodularita

Konečná mřížka je modulární právě tehdy, když je jak horní, tak dolní semimodulární. Pro odstupňovanou mřížku je (horní) semimodularita ekvivalentní následující podmínce na hodnostní funkci r:

r(X) + r(y) ≥ r(X ∧ y) + r(X ∨ y).

Další ekvivalentní podmínkou (pro odstupňované mřížky) je Birkhoff stav:

pro každého X a y v L, pokud X a y oba kryjí X ∧ y, pak X ∨ y pokrývá obojí X a y.

Mřížka se nazývá nižší semimodulární, pokud její duální je semimodulární. Pro konečné mřížky to znamená, že předchozí podmínky platí při výměně ∨ a,, „kryty“ vyměněné s „je pokryto“ a nerovnosti jsou obráceny.^[6]

Spojitost a algebraicita

v teorie domény, je přirozené usilovat o aproximaci prvků v částečném pořadí pomocí „mnohem jednodušších“ prvků. To vede ke třídě spojité posety, skládající se z posetů, kde lze každý prvek získat jako supremum a řízená sada prvků, které jsou dole prvek. Pokud je lze dodatečně omezit na kompaktní prvky posetu pro získání těchto řízených množin, pak je poset sudý algebraický. Oba koncepty lze aplikovat na mřížky následovně:

• A spojitá mříž je úplná mříž, která je spojitá jako poset.
• An algebraická mřížka je úplná mřížka, která je algebraická jako poset.

Obě tyto třídy mají zajímavé vlastnosti. Například spojité mřížky lze charakterizovat jako algebraické struktury (s nekonečnými operacemi), které splňují určité identity. I když taková charakterizace není známa pro algebraické mřížky, lze je popsat „syntakticky“ pomocí Scott informační systémy.

Doplňky a pseudoplňky

Nechat L být ohraničená mřížka s největším prvkem 1 a nejmenším prvkem 0. Dva prvky X a y z L jsou doplňuje navzájem tehdy a jen tehdy, když:

X ∨ y = 1 a X ∧ y = 0.

Obecně platí, že některé prvky ohraničené mřížky nemusí mít doplněk a jiné mohou mít více než jeden doplněk. Například množina {0, ½, 1} s obvyklým uspořádáním je ohraničená mřížka a ½ nemá doplněk. V ohraničené mřížce N₅prvek A má dva doplňky, viz. b a C (viz obr. 11). Ohraničená mříž, pro kterou má každý prvek komplement, se nazývá a doplněná mříž.

Doplněná mříž, která je také distribuční, je Booleova algebra. Pro distribuční mřížku doplněk X, pokud existuje, je jedinečný.

V případě, že je doplněk jedinečný, píšeme ¬X = y a ekvivalentně ¬y = X. Odpovídající unární úkon přes L, nazývané komplementace, zavádí analogický logický negace do teorie mřížky.

Ahoj algebry jsou příkladem distribučních svazů, kde některým členům mohou chybět doplňky. Každý prvek X Heytingovy algebry má na druhé straně a pseudokomplement, také označeno ¬X. Pseudokomplement je největší prvek y takhle X ∧ y = 0. Pokud je pseudoplněk každého prvku Heytingovy algebry ve skutečnosti doplňkem, pak je Heytingova algebra ve skutečnosti booleovská algebra.

Stav řetězce Jordan – Dedekind

A řetěz z X₀ na X_n je sada ${ displaystyle {x_ {0}, x_ {1}, ldots, x_ {n} }}$, kde ${ displaystyle x_ {0}$.v délka tohoto řetězce je nnebo o jeden menší než jeho počet prvků. Řetěz je maximální -li X_i kryty X_i−1 pro všechny 1 ≤ i ≤ n.

Pokud pro jakýkoli pár, X a y, kde X < y, všechny maximální řetězce z X na y mít stejnou délku, pak se říká, že mřížka splňuje Stav řetězce Jordan – Dedekind.

Zdarma mříže

Jakákoli sada X lze použít ke generování zdarma semilattice FX. Volná semilattice je definována tak, že se skládá ze všech konečných podmnožin X, přičemž semilattická operace je dána obyčejností nastavit unii. Volná semilattice má univerzální vlastnictví. Pro volná mříž přes sadu X, Whitman dal konstrukci založenou na polynomech X's členy.^[7][8]

Důležité mřížově-teoretické pojmy

Nyní definujeme několik teoreticko-teoretických představ o důležitosti teorie mřížky. V následujícím textu pojďme X být prvkem nějaké mřížky L. Li L má spodní prvek 0, X ≠ 0 je někdy vyžadováno. X je nazýván:

• Připojte se ireducibilní -li X = A ∨ b naznačuje X = A nebo X = b pro všechny A, b v L. Když je první podmínka zobecněna na libovolné spojení ${ displaystyle bigvee _ {i in I} a_ {i}}$, X je nazýván úplně se připojte k nesnížitelnosti (nebo ∨-neredukovatelné). Dvojí představa je splnit neredukovatelnost (∧-ireducibilní). Například na obr. 2 jsou prvky 2, 3, 4 a 5 spojeny jako neredukovatelné, zatímco 12, 15, 20 a 30 jsou neredukovatelné. V příhradě reálná čísla s obvyklým řádem je každý prvek spojen s neredukovatelným, ale žádný není zcela spojen s neredukovatelným.
• Připojte se k prime -li X ≤ A ∨ b naznačuje X ≤ A nebo X ≤ b. I to lze zobecnit, abychom získali představu zcela se připojit k hlavnímu. Dvojí představa je setkat se s hlavním. Každý prvek join-prime je také neredukovatelný a každý prvek meet-prime je také neredukovatelný. Konverzace platí, pokud L je distribuční.

Nechat L mít spodní prvek 0. Prvek X z L je atom -li 0 < X a neexistuje žádný prvek y z L takhle 0 < y < X. Pak L je nazýván:

• Atomový pokud pro každý nenulový prvek X z L, existuje atom A z L takhle A ≤ X;
• Atomistický pokud každý prvek L je supremum atomů.

Pojmy ideály a dvojí představa filtry odkazují na konkrétní druhy podmnožiny částečně uspořádané množiny, a jsou proto důležité pro teorii mřížky. Podrobnosti naleznete v příslušných položkách.

Viz také

• Připojte se a setkejte se
• Mapa svazů
• Orthocomplemented mříž
• Celková objednávka
• Ideál a filtr (duální pojmy)
• Šikmá mříž (zobecnění na nekomutativní spojení a setkání)
• Eulerova mříž
• Postova mříž
• Tamari mříž
• Young – Fibonacciho mříž
• 0,1-jednoduchá mříž

Aplikace, které používají teorii mřížky

tento článek je v seznam formát, ale může číst lépe jako próza. Můžete pomoci převod tohoto článku, Pokud je to vhodné. Nápověda k úpravám je k dispozici. (Březen 2017)

Všimněte si, že v mnoha aplikacích jsou sady pouze částečnými mřížemi: ​​ne každý pár prvků má schůzku nebo spojení.

• Zbytečná topologie
• Mřížka podskupin
• Spektrální prostor
• Invariantní podprostor
• Operátor uzavření
• Abstraktní interpretace
• Subskripční mřížka
• Fuzzy množina teorie

Poznámky

Reference

Monografie dostupné zdarma online:

• Burris, Stanley N. a Sankappanavar, H. P., 1981. Kurz univerzální algebry. Springer-Verlag. ISBN  3-540-90578-2.
• Jipsen, Peter a Henry Rose, Odrůdy mřížek, Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN  0-387-56314-8.
• Nation, J. B., Poznámky k teorii mřížky. Kapitoly 1-6. Kapitoly 7–12; Dodatky 1–3.

Základní texty doporučené pro ty s omezeným obsahem matematická zralost:

• Donnellan, Thomas, 1968. Teorie mřížky. Pergamon.
• Grätzer, Georgi, 1971. Teorie mřížky: První koncepty a distribuční mřížky. W. H. Freeman.

Standardní současný úvodní text, poněkud těžší než výše uvedený:

• Davey, B. A .; Priestley, H. A. (2002), Úvod do mřížek a řádu, Cambridge University Press, ISBN  978-0-521-78451-1

Pokročilé monografie:

• Garrett Birkhoff, 1967. Teorie mřížky, 3. vyd. Sv. 25 publikací AMS Colloquium Publications. Americká matematická společnost.
• Robert P. Dilworth a Crawley, Peter, 1973. Algebraická teorie svazů. Prentice-Hall. ISBN  978-0-13-022269-5.
• Grätzer, George (1996) [1978]. Obecná teorie mřížky (Druhé vydání.). Basilej: Birkhäuser. ISBN  978-3-7643-6996-5.

Na volných mřížích:

• R. Freese, J. Jezek a J. B. Nation, 1985. „Free Lattices“. Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America.
• Johnstone, P. T., 1982. Kamenné prostory. Cambridge studia pokročilé matematiky 3. Cambridge University Press.

K historii teorie mřížky:

• Štĕpánka Bilová (2001). Eduard Fuchs (ed.). Mřížová teorie - její vznik a život (PDF). Prometheus. 250–257.

O aplikacích teorie mřížky:

• Garrett Birkhoff (1967). James C. Abbot (ed.). Co pro vás mohou Lattices udělat?. Van Nostrand. Obsah

externí odkazy

• „Lattice-ordered group“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Weisstein, Eric W. "Mříž". MathWorld.
• J.B.Nation, Poznámky k teorii mřížky, nepublikované poznámky k kurzu dostupné jako dva soubory PDF.
• Ralph Freese, „Domovská stránka teorie mřížky“.
• OEIS sekvence A006966 (Počet neoznačených mřížek s n elementy)