Fullständighet (ordningsteori)

Inom det matematiska området för ordningsteori hävdar fullständighetsegenskaper förekomsten av vissa infima eller suprema av en given delvis ordnad uppsättning (poset) . Det mest välbekanta exemplet är fullständigheten av de reella talen . En speciell användning av termen hänvisar till fullständiga partiella beställningar eller kompletta galler . Det finns dock många andra intressanta föreställningar om fullständighet.

Motivationen för att överväga fullständighetsegenskaper härrör från den stora betydelsen av suprema (minsta övre gränser, joins , " $\vee$ ") och infima (största nedre gränser, möter , " $\wedge$ ") för att teorin om delordningar. Att hitta ett supremum innebär att peka ut ett distingerat minsta element från uppsättningen av övre gränser. Å ena sidan förkroppsligar dessa specialelement ofta vissa konkreta egenskaper som är intressanta för den givna tillämpningen (som att vara den minsta gemensamma multipeln av en uppsättning tal eller föreningen av en samling av mängder). Å andra sidan, vetskapen om att vissa typer av delmängder garanterat har suprema eller infima gör det möjligt för oss att betrakta beräkningen av dessa element som totala operationer på en delvis beställd uppsättning. Av denna anledning posetter med vissa fullständighetsegenskaper ofta beskrivas som algebraiska strukturer av ett visst slag. Att studera egenskaperna hos de nyvunna verksamheterna ger dessutom ytterligare intressanta ämnen.

Typer av fullständighetsegenskaper

Alla fullständighetsegenskaper beskrivs längs ett liknande schema: ett beskriver en viss klass av delmängder av en delvis ordnad uppsättning som krävs för att ha ett supremum eller som krävs för att ha ett infimum. Därför har varje fullständighetsegenskap sin dubbla , erhållen genom att invertera de ordningsberoende definitionerna i det givna uttalandet. Vissa av begreppen är vanligtvis inte dualiserade medan andra kan vara självduala (dvs. likvärdiga med deras dubbla uttalanden).

Minsta och största elementen

Det enklaste exemplet på en supremum är den tomma, dvs. supremum för den tomma uppsättningen . Per definition är detta det minsta elementet bland alla element som är större än varje medlem i den tomma uppsättningen. Men detta är bara det minsta elementet i hela poset, om det har en, eftersom den tomma delmängden av en poset P konventionellt anses vara både avgränsad ovanifrån och underifrån, där varje element i P är både en övre och nedre gräns av den tomma delmängden. Andra vanliga namn för det minsta elementet är botten och noll (0). Den dubbla föreställningen, den tomma nedre gränsen, är det största elementet , toppen eller enheten (1).

Posets som har en botten kallas ibland spetsiga, medan posets med en topp kallas enhetliga eller toppade. En ordning som har både ett minsta och ett största element är avgränsad. Detta bör dock inte förväxlas med begreppet begränsad fullständighet som ges nedan.

Ändlig fullständighet

Ytterligare enkla fullständighetsvillkor uppstår från beaktande av alla icke-tomma ändliga mängder . En ordning där alla icke-tomma ändliga mängder har både ett supremum och ett infimum kallas ett gitter . Det räcker att kräva att alla suprema och infima av två element existerar för att erhålla alla icke-tomma ändliga; ett okomplicerat induktionsargument visar att varje finit icke-tom supremum/infimum kan dekomponeras till ett ändligt antal binära suprema/infima. De centrala operationerna av gitter är alltså binär suprema $\vee$ och infima $\wedge$ . Det är i detta sammanhang som termerna möts för $\wedge$ och join för $\vee$ är vanligast.

En poset där endast icke-tom finita suprema är känd för att existera kallas därför en join-semilattice . Den dubbla föreställningen är möte-semilattice .

Ytterligare fullständighetsvillkor

Den starkaste formen av fullständighet är existensen av all suprema och all infima. Poseterna med denna egenskap är de kompletta gallren . Men med hjälp av den givna ordningen kan man begränsa till ytterligare klasser av (möjligen oändliga) delmängder, som inte ger denna starka fullständighet på en gång.

Om alla riktade delmängder av en poset har ett supremum, är ordern en riktad-komplett partiell order (dcpo). Dessa är särskilt viktiga inom domänteorin . Den sällan övervägda dubbla begreppet till en dcpo är den filtrerade kompletta poset. Dcpos med minsta element ("pointed dcpos") är en av de möjliga betydelserna av frasen fullständig partiell ordning (cpo).

Om varje delmängd som har någon övre gräns också har en minsta övre gräns, kallas respektive poset bounded complete . Termen används flitigt med denna definition som fokuserar på suprema och det finns inget gemensamt namn för den dubbla egenskapen. Begränsad fullständighet kan dock uttryckas i termer av andra fullständighetsvillkor som lätt kan dualiseras (se nedan). Även om begrepp med namnen "fullständig" och "avgränsad" redan var definierade, är det osannolikt att förvirring uppstår eftersom man sällan skulle tala om en "avgränsad fullständig poset" när man menar en "avgränsad cpo" (som bara är en "cpo med största elementet "). Likaså är "begränsat komplett gitter" nästan entydigt, eftersom man inte skulle ange begränsningsegenskapen för kompletta gitter, där det ändå antyds. Observera också att den tomma uppsättningen vanligtvis har övre gränser (om poset är icke-tom) och därför har en bounded-complete poset ett minsta element.

Man kan också överväga delmängderna av en poset som är helt ordnade , dvs kedjorna . Om alla kedjor har en högsta nivå kallas ordern för kedja komplett . Återigen, detta koncept behövs sällan i den dubbla formen.

Samband mellan fullständighetsegenskaper

Det har redan observerats att binära möten/joins ger alla icke-tomma ändliga möten/joins. Likaså är många andra (kombinationer) av ovanstående villkor likvärdiga.

• Det mest kända exemplet är existensen av all suprema, som i själva verket är likvärdig med existensen av all infima. För varje delmängd X av en poset kan man faktiskt överväga dess uppsättning av nedre gränser B . B är då lika med infimum av X : eftersom varje element i X är en övre gräns för B , är sup B mindre än alla element i X , dvs sup B är i B. Det är det största elementet i B och därav infimumet av X . På ett dubbelt sätt innebär existensen av all infima existensen av all suprema.
• Begränsad fullständighet kan också karakteriseras olika. Genom ett argument som liknar ovanstående finner man att det högsta av en mängd med övre gränser är infimum för mängden av övre gränser. Följaktligen är begränsad fullständighet likvärdig med existensen av alla icke-tomma infima.
• En poset är ett komplett gitter om och bara om det är en cpo och en join-semilattice. I själva verket, för varje delmängd X , är mängden av alla finita suprema (fogar) av X riktad och supremumet för denna mängd (som existerar genom riktad fullständighet) är lika med supremumet av X . Således har varje uppsättning ett överlägsenhet och genom ovanstående observation har vi ett komplett gitter. Den andra riktningen av beviset är trivialt.
• Om man antar valets axiom är en poset kedjan komplett om och bara om den är en dcpo.

Fullständighet i termer av universell algebra

Som förklarats ovan tillåter närvaron av vissa fullständighetsvillkor att betrakta bildandet av vissa suprema och infima som totala operationer av en delvis beställd uppsättning. Det visar sig att det i många fall är möjligt att karakterisera fullständighet enbart genom att beakta lämpliga algebraiska strukturer i betydelsen universell algebra , som är utrustade med operationer som $\vee$ eller $\wedge$ . Genom att införa ytterligare villkor (i form av lämpliga identiteter ) för dessa operationer, kan man verkligen härleda den underliggande partiella ordningen uteslutande från sådana algebraiska strukturer. Detaljer om denna karakterisering kan hittas i artiklarna om de "gitterliknande" strukturer för vilka detta vanligtvis anses vara: se semilattic , gitter , Heyting algebra och boolesk algebra . Observera att de två sistnämnda strukturerna utvidgar tillämpningen av dessa principer utöver enbart fullständighetskrav genom att introducera en ytterligare negationsoperation .

Fullständighet i fråga om tillägg

Ett annat intressant sätt att karakterisera fullständighetsegenskaper tillhandahålls genom begreppet (monotona) Galois-kopplingar , dvs adjunktioner mellan partiella ordningar. I själva verket ger detta tillvägagångssätt ytterligare insikter både i naturen hos många fullständighetsegenskaper och i betydelsen av Galois-kopplingar för ordningsteori. Den allmänna observation som denna omformulering av fullständighet bygger på är att konstruktionen av vissa suprema eller infima ger vänster eller höger angränsande delar av lämpliga Galois-förbindelser.

Betrakta en delvis ordnad uppsättning ( X , ≤). Som ett första enkelt exempel, låt 1 = {*} vara en specificerad ettelementuppsättning med den enda möjliga partiella ordningen. Det finns en uppenbar mappning j : X → 1 med j ( x ) = * för alla x i X . X har ett minsta element om och endast om funktionen j har en lägre adjoint j ^* : 1 → X . Definitionen för Galois-anslutningar ger faktiskt att i detta fall j ^* (*) ≤ x om och endast om * ≤ j ( x ), där den högra sidan uppenbarligen gäller för alla x . Dubbelt är förekomsten av en övre adjoint för j ekvivalent med att X har ett största element.

En annan enkel mappning är funktionen q : X → X × X ges av q ( x ) = ( x , x ). Naturligtvis är den avsedda beställningsrelationen för X × X bara den vanliga produktordern . q har en lägre adjoint q ^* om och endast om alla binära kopplingar i X finns. Omvänt kan joinoperationen $\vee$ : X × X → X alltid tillhandahålla den (nödvändigtvis unika) nedre adjointen för q . Dubbelt tillåter q en övre adjoint om och endast om X har alla binära möten. Således är mötesoperationen $\wedge$ , om den finns, alltid en övre adjoint. Om både $\vee$ och $\wedge$ existerar och dessutom ${\displaystyle \wedge } också är en lägre adjoint, då$ är poset X en Heyting-algebra — en annan viktig specialklass av delbeställningar.

Ytterligare fullständighetsförklaringar kan erhållas genom att använda lämpliga kompletteringsförfaranden . Till exempel är det välkänt att insamlingen av alla lägre uppsättningar av en poset X , ordnade efter delmängdsinkludering , ger ett komplett gitter D ( X ) (nedsatt gitter). Dessutom finns det en uppenbar inbäddning e : X → D ( X ) som mappar varje element x i X till dess huvudideal { y i X | y ≤ x }. En liten reflektion visar nu att e har en lägre adjoint om och bara om X är ett komplett gitter. I själva verket kommer denna nedre adjoint att mappa alla lägre uppsättningar av X till dess högsta i X . Genom att komponera denna nedre adjoint med funktionen som mappar vilken delmängd som helst av X till dess nedre stängning (återigen ett tillägg för att inkludera lägre uppsättningar i powersetet ), erhåller man den vanliga supremummappen från powerset 2 ^X till X . Som tidigare uppstår en annan viktig situation när denna överordnade karta också är en övre adjoint: i detta fall är det kompletta gittret X konstruktivt fullständigt distributivt . Se även artiklarna om fullständig distributivitet och distributivitet (orderteori) .

Övervägandena i detta avsnitt föreslår en omformulering av (delar av) ordningsteorin i termer av kategoriteori , där egenskaper vanligtvis uttrycks genom att referera till relationerna ( morfismer , mer specifikt: adjunktioner) mellan objekt, istället för att beakta deras inre struktur. För mer detaljerade överväganden om detta förhållande, se artikeln om den kategoriska formuleringen av ordningsteori.

Se även

• Fullständigt fördelande galler
• Gränsbevarande funktion på bevarande av befintlig suprema/infima.
• Total order – Order vars element alla är jämförbara

Anteckningar

• G. Markowsky och BK Rosen. Baser för kedjekompletta poster IBM Journal of Research and Development. mars 1976.
• Stephen Bloom. Variationer av beställda algebror Journal of Computer and System Sciences. oktober 1976.
• Michael Smyth. Maktdomäner Journal of Computer and System Sciences. 1978.
• Daniel Lehmann. Om ordningens algebra Journal of Computer and System Sciences. augusti 1980.