Dokončení Dedekind – MacNeille - Dedekind–MacNeille completion - Wikipedia

„Dedekind dokončení“ přeadresuje tady. Některé další související pojmy viz Dedekindova úplnost.
The Hasseův diagram částečně uspořádané množiny (vlevo) a jejího dokončení Dedekind – MacNeille (vpravo).

v matematika konkrétně teorie objednávek, Dokončení Dedekind – MacNeille a částečně objednaná sada (nazývané také dokončení řezy nebo normální dokončení)[1] je nejmenší úplná mříž který to obsahuje. Je pojmenován po Holbrook Mann MacNeille jehož papír z roku 1937 jej nejprve definoval a zkonstruoval a poté Richard Dedekind protože jeho konstrukce zobecňuje Dedekind škrty použitý Dedekindem ke konstrukci reálná čísla z racionální čísla.

Objednejte vložení a dokončení mřížky

A částečně objednaná sada (poset) se skládá z a soubor prvků společně s a binární relace X ≤ y na dvojicích prvků, které je reflexní (X ≤ X pro každého X), tranzitivní (li X ≤ y a y ≤ z pak X ≤ z), a antisymetrický (pokud obojí X ≤ y a y ≤ X držte se tedy X = y). Obvyklé číselné uspořádání na celá čísla nebo reálná čísla splňují tyto vlastnosti; na rozdíl od uspořádání čísel však může mít částečné pořadí dva prvky, které jsou nesrovnatelný: ani X ≤ y ani y ≤ X drží. Dalším známým příkladem částečného objednání je zařazení objednávání ⊆ na dvojicích sad.

Li S je částečně objednaná sada, a dokončení z S znamená a úplná mříž L s vkládání objednávek z S do L.[2] Představa úplné mřížky znamená, že každá podmnožina prvků L má infimum a supremum; Tím se zobecňují analogické vlastnosti reálná čísla. Pojem vkládání objednávek vynucuje požadavky, které odlišují prvky S musí být mapovány na odlišné prvky La že každá dvojice prvků v S má stejné objednávání v L jak to dělají S. The prodloužená řada reálných čísel (reálná čísla spolu s + ∞ a −∞) je v tomto smyslu doplněním racionálních čísel: množina racionálních čísel {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} nemá racionální nejméně horní mez, ale v reálných číslech má nejnižší horní mez π.

Daná částečně objednaná sada může mít několik různých dokončení. Například jedno dokončení jakékoli částečně objednané sady S je soubor jeho dolů uzavřené podmnožiny objednáno někým zařazení. S je vložen do této (úplné) mřížky mapováním každého prvku X na nižší sadu prvků, které jsou menší nebo rovny X. Výsledkem je a distribuční mříž a používá se v Birkhoffova věta o reprezentaci. Může však mít mnohem více prvků, než je třeba k vytvoření dokončení S.[3] Ze všech možných dokončených mřížek je Dedekind – MacNeille dokončení nejmenší úplnou mřížkou S vložený do něj.[4]

Definice

Pro každou podmnožinu A částečně objednané sady S, nechť Au označuje množinu horních mezí A; tj. prvek X z S patří Au kdykoli X je větší nebo rovno každému prvku v A. Symetricky, pojďme Al označuje množinu dolních mezí A, prvky, které jsou menší nebo stejné jako každý prvek v A. Pak dokončení Dedekind – MacNeille S skládá se ze všech podskupin A pro který

(Au)l = A;

je objednáno zahrnutím: A ≤ B v dokončení právě tehdy A ⊆ B jako sady.

Prvek X z S vloží do dokončení jako jeho hlavní ideál, sada ↓X prvků menších nebo rovných X. Pak (↓X)u je sada prvků větších nebo rovných X, a ((↓X)u)l = ↓X, což ukazuje ↓X je skutečně členem dokončení.[5] Je jednoduché ověřit, že mapování z X na ↓X je vkládání objednávek.

Někdy se používá alternativní definice dokončení Dedekind – MacNeille, která se více podobá definici řezu Dedekind.[6] V částečně objednané sadě S, definujte a střih být pár sad (A,B) pro který Au = B a A = Bl. Li (A,B) je tedy střih A splňuje rovnici (Au)l = A, a naopak pokud (Au)l = A pak (A,Au) je řez. Proto sada výřezů, částečně seřazená podle zařazení na spodní sadu výřezu (nebo naopak na relaci zahrnutí na horní sadu), poskytuje ekvivalentní definici dokončení Dedekind – MacNeille.

S alternativní definicí mají operace spojení i schůzky úplné mřížky symetrické popisy: if (Ai,Bi) jsou řezy v jakékoli rodině řezů, pak je splnění těchto řezů řezem (L,Lu) kde L = ∩iAia spojení je řez (Ul,U) kde U = ∩iBi.

Příklady

Li Q je sada racionální čísla, nahlíženo jako na zcela uspořádanou množinu s obvyklým číselným řádem, pak každý prvek Dedekind – MacNeilleho dokončení Q lze zobrazit jako Dedekind řez a dokončení Dedekind – MacNeille Q je celková objednávka na reálná čísla, společně se dvěma dalšími hodnotami ± ∞.[7] Konstrukce reálných čísel z racionálních čísel je příkladem Dedekindova dokončení a úplně objednaná sada a dokončení Dedekind – MacNeille zobecňuje tento koncept od celkových objednávek k částečným objednávkám.

Li S je antichain (sada prvků, z nichž žádné dva nejsou srovnatelné), pak Dedekind – MacNeilleovo dokončení S skládá se z S sám spolu se dvěma dalšími prvky, spodním prvkem, který je pod každým prvkem v S a horní prvek, který je nad každým prvkem v S.[8]

Li Ó je jakákoli konečná sada objektů a A je jakákoli konečná sada unárních atributů pro objekty v Ó, pak lze vytvořit dílčí řád výšky dva, ve kterém jsou prvky dílčího řádu objekty a atributy a ve kterém X ≤ y když X je objekt, který má atributy. U takto definovaného dílčího řádu je dokončení Dedekind – MacNeille S je znám jako koncept mříž, a hraje ústřední roli v oblasti formální koncepční analýza.

Vlastnosti

Dedekind – MacNeille dokončení částečně objednané sady S je nejmenší úplná mřížka s S vloženo do něj v tom smyslu, že pokud L je jakékoli mřížkové dokončení S, pak dokončení Dedekind – MacNeille je částečně uspořádanou podmnožinou L.[4] Když S je konečný, jeho dokončení je také konečné a má nejmenší počet prvků ze všech konečných úplných mřížek obsahujících S.

Částečně objednaná sada S je hustá spojení a hustá setkání v dokončení Dedekind – MacNeille; to znamená, že každý prvek dokončení je spojením nějaké sady prvků S, a je také setkáním některé sady prvků v S.[9] Dokončení Dedekind – MacNeille je charakterizováno mezi dokončeními S touto vlastností.

Dedekind – MacNeille dokončení a Booleova algebra je kompletní booleovská algebra; tento výsledek je znám jako Glivenkova – kamenná věta, po Valery Ivanovič Glivenko a Marshall Stone.[10] Podobně dokončení Dedekind – MacNeille a zbytková mříž je úplná residuovaná mříž.[11] Dokončení a distribuční mříž nemusí být samo o sobě distribuční a dokončení a modulární mříž nemusí zůstat modulární.[12]

Dokončení Dedekind – MacNeille je samo-duální: dokončení dvojí částečné objednávky je stejná jako duál dokončení.[13]

Dedekind – MacNeille dokončení S má to samé dimenze objednávky stejně jako S sám.[14]

V kategorie částečně uspořádaných množin a monotónních funkcí mezi částečně uspořádanými množinami tvoří úplná mřížka injekční předměty pro vkládání objednávek a dokončení Dedekind – MacNeille S je injekční trup zS.[15]

Algoritmy

Několik vědců zkoumalo algoritmy pro konstrukci Dedekind – MacNeilleho dokončení konečné částečně uspořádané množiny. Protože dokončení Dedekind – MacNeille může být exponenciálně větší než částečné pořadí, ze kterého pochází,[16] je nutné měřit časové hranice těchto algoritmů z hlediska počtu n prvků vstupního dílčího řádu, ale také z hlediska počtu C prvků jeho dokončení a někdy také z hlediska dalších opatření ke složitosti vstupu a výstupu. Formát, ve kterém je výstupní mřížka reprezentována, může také ovlivnit dobu běhu jejích konstrukčních algoritmů; například pokud je reprezentován jako logická matice zadáním výsledku srovnání mezi každou dvojicí mřížových prvků je výstupní velikost Θ (C2) a toto bude dolní hranice času pro konstrukční algoritmus.

Sestavení sady řezů

Ganter & Kuznetsov (1998) popsat přírůstkový algoritmus, ve kterém je vstupní dílčí pořadí vytvořeno přidáním jednoho prvku najednou; v každém kroku se dokončení menší dílčí objednávky rozšíří a vytvoří dokončení větší dílčí objednávky. V jejich metodě je dokončení představováno explicitním seznamem řezů. Každý řez rozšířeného dílčího řádu, s výjimkou toho, jehož dvě sady se protínají v novém prvku, je buď výřezem z předchozího dílčího řádu, nebo je vytvořen přidáním nového prvku na jednu nebo druhou stranu výřezu z předchozího částečné pořadí, takže jejich algoritmus potřebuje pouze testovací páry sad této formy k určení, které z nich jsou řezy. Čas pro použití jejich metody k přidání jednoho prvku k dokončení částečné objednávky je Ó(cnw) kde w je šířka dílčího řádu, tj. velikost jeho největšího antichain. Proto je čas na výpočet dokončení dané dílčí objednávky Ó(cn2w) = O (cn3).

Tak jako Jourdan, Rampon & Jard (1994) pozor, problém výpisu všech řezů v částečně uspořádané množině lze formulovat jako speciální případ jednoduššího problému, výpisu všech maximálních antichains v jiné částečně objednané sadě. Li P je libovolná částečně objednaná sada, ať Q být částečná objednávka, jejíž prvky obsahují dvě kopie P: pro každý prvek X z P, Q obsahuje dva prvky X0 a X1, s Xi < yj kdyby a jen kdyby X < y a i < j. Pak řezy P odpovídat jeden za jednoho s maximálními antichains v Q: prvky v dolní sadě výřezu odpovídají prvkům s dolním indexem 0 v řetězci a prvky v horní sadě výřezu odpovídají prvkům s indexem 1 v řetězci. Jourdan a kol. popsat algoritmus pro nalezení maximálních řetězců, které, když se použijí na problém výpisu všech výřezů P, vyžaduje čas Ó(C(nw + w3)), vylepšení algoritmu Ganter & Kuznetsov (1998) když šířka w je malý. Alternativně maximální antichain v Q je stejný jako a maximální nezávislá množina v srovnávací graf z Qnebo maximální klika v doplňku grafu srovnatelnosti, takže algoritmy pro klika problém nebo lze problém nezávislé množiny použít i na tuto verzi problému dokončení Dedekind – MacNeille.

Sestavení krycího grafu

The přechodná redukce nebo krycí graf dokončení Dedekind – MacNeille stručně popisuje řádový vztah mezi jeho prvky: každý soused řezu musí odstranit prvek původního dílčího řádu buď z horní nebo dolní sady řezu, takže každý vrchol má maximálně n sousedé. Krycí graf tedy má C vrcholy a nanejvýš cn/2 sousedé, počet, který může být mnohem menší než C2 položky v matici, která určuje všechna párová srovnání mezi prvky. Nourine & Raynaud ukázat, jak efektivně vypočítat tento krycí graf; obecněji, pokud B je libovolná rodina množin, ukazují, jak vypočítat krycí graf mřížky svazků podmnožin B. V případě mřížky Dedekind – MacNeille, B lze brát jako rodinu doplňkové sady hlavních ideálů a svazků podmnožin B jsou doplňky spodní sady řezů. Hlavní myšlenkou jejich algoritmu je generování svazků podmnožin B postupně (pro každou sadu v B, tvořící jeho unii se všemi dříve generovanými odbory), představují výslednou rodinu sad v a trie a pomocí reprezentace triů otestujte u určitých kandidátských párů sad sousednost v krycím vztahu; chce to čas Ó(cn2). V pozdější práci stejní autoři ukázali, že algoritmus může být plně inkrementální (schopný přidávat prvky do dílčího pořadí jeden po druhém) se stejným celkovým časovým ohraničením.[17]

Poznámky

  1. ^ Davey & Priestley (2002, str. 166); Siegfried & Schröder (2003, str. 119).
  2. ^ Siegfried & Schröder (2003), definice 5.3.1, s. 119.
  3. ^ Carpineto, Claudio; Romano, Giovanni (2004), Analýza koncepčních dat: teorie a aplikace, John Wiley and Sons, str. 10, ISBN  978-0-470-85055-8.
  4. ^ A b Bishop (1978); Siegfried & Schröder (2003), Věta 5.3.8, str. 121.
  5. ^ MacNeille (1937), Lemma 11,8, s. 444; Davey & Priestley (2002), Lemma 3.9 (i), s. 166.
  6. ^ Toto je definice, kterou původně používal MacNeille (1937), například.
  7. ^ Davey & Priestley (2002), Příklad 7.44 (1), str. 168; Siegfried & Schröder (2003), Příklad 5.3.3 (2), str. 120.
  8. ^ Davey & Priestley (2002), Příklad 7.44 (2), str. 168.
  9. ^ Siegfried & Schröder (2003), Návrh 5.3.7, s. 121.
  10. ^ Birkhoff (1995), Věta 27, s. 130.
  11. ^ Gabbay, Shehtman & Skvortsov (2009).
  12. ^ Cotlar (1944); Funayama (1944).
  13. ^ Birkhoff (1995).
  14. ^ Tento výsledek je často přičítán nepublikované diplomové práci Harvardské univerzity z roku 1961 od K. A. Bakera „Dimenze, nezávislost na spojení a šíře v částečně uspořádaných sadách“. To bylo publikováno Novák (1969).
  15. ^ Banaschewski & Bruns (1967).
  16. ^ Ganter & Kuznetsov (1998).
  17. ^ Nourine & Raynaud (2002).

Reference

externí odkazy