Ordliste - Glossary of order theory

Dette er en ordliste over noen termer som brukes i forskjellige matematikkgrener som er relatert til feltene orden , gitter og domeneteori . Vær oppmerksom på at det også er en strukturert liste over bestillingsemner . Andre nyttige ressurser kan være følgende oversiktsartikler:

I det følgende vil delvis ordrer vanligvis bare bli angitt med transportørsettene. Så lenge den tiltenkte betydningen er tydelig fra konteksten, vil det være tilstrekkelig å betegne det korresponderende relasjonelle symbolet, selv uten forutgående introduksjon. Videre vil <angi den strenge rekkefølgen indusert av

EN

  • Acyklisk . En binær relasjon er asyklisk dersom den inneholder ingen "sykluser": ekvivalent, det transitive nedleggelse er antisymmetrisk .
  • Tilstøtende . Se Galois -tilkobling .
  • Alexandrov topologi . For et preordered sett P , en hvilken som helst øvre sett O er Alexandrov-åpen . Omvendt er en topologi Alexandrov hvis et skjæringspunkt mellom åpne sett er åpent.
  • Algebraisk poset . En poset er algebraisk hvis den har en base av kompakte elementer.
  • Antichain . En antikjede er en poset der ingen to elementer er sammenlignbare, det vil si at det ikke er to forskjellige elementer x og y slik at x y . Med andre ord er ordensforholdet til et antikjede bare identitetsforholdet.
  • Tilnærmer forholdet . Se forholdet under .
  • Antisymmetrisk forhold . En homogen forhold R på et sett X er antisymmetrisk , hvis x R y og y R x innebærer x = y , for alle elementer x , y i X .
  • Antiton . En antitone funksjon f mellom Posets P og Q er en funksjon som, for alle elementer x , y av P , xy (i P ) impliserer f ( y ) ≤ f ( x ) (i Q ). Et annet navn på denne eiendommen er ordre-reversering . I analyse , i nærvær av totale ordrer , kalles slike funksjoner ofte monotont synkende , men dette er ikke en veldig praktisk beskrivelse når det gjelder ikke-totale ordrer. Den doble oppfatningen kalles monoton eller ordenbevarende .
  • Asymmetrisk sammenheng . En homogen forhold R på et sett X er asymmetrisk, hvis x R y innebærer ikke y R x , for alle elementer x , y i X .
  • Atom . Et atom i en poset P med minst element 0, er et element som er minimalt blant alle elementene som er ulik til 0.
  • Atomisk . En atom poset P med minst elementet 0 er en der, for hver ikke-null element x av P , er det et atom en av P med enx .

B

  • Base . Se kontinuerlig poset .
  • Binært forhold . En binær relasjon over to setter en delmengde av deres kartesiske produkt
  • Boolsk algebra . En boolsk algebra er et distributivt gitter med minst element 0 og største element 1, der hvert element x har et komplement ¬ x , slik at x ∧ ¬ x = 0 og x ∨ ¬ x = 1.
  • Avgrenset poset . En avgrenset poset er en som har det minste elementet og det største elementet.
  • Avgrenset fullført . En poset er avgrenset fullstendig hvis alle delmengdene med noen øvre grense også har en minst slik øvre grense. Den doble oppfatningen er ikke vanlig.

C

  • Kjede . En kjede er et helt bestilt sett eller et helt bestilt delsett av en poset. Se også totalbestilling .
  • Kjeden komplett . Et delvis bestilt sett der hver kjede har minst øvre grense .
  • Lukkingsoperatør . Et lukke operatøren på poset P er en funksjon C  : P P som er monoton, idempotent , og tilfredsstiller C ( x ) ≥ x for alle x i P .
  • Kompakt . Et element x i en poset er kompakt hvis det er langt under seg selv, dvs. x << x . Man sier også at et slikt x er begrenset .
  • Sammenlignbar . To elementer x og y i en posisjon P er sammenlignbare hvis enten x y eller y x .
  • Sammenlignbarhetsgraf . Sammenlikningsgrafen til en poset ( P , ≤) er grafen med toppunktet P der kantene er de parene med forskjellige elementer av P som er sammenlignbare under ≤ (og spesielt under dens refleksive reduksjon <).
  • Komplett boolsk algebra . En boolsk algebra som er et komplett gitter.
  • Fullfør Heyting -algebra . En Heyting -algebra som er et komplett gitter kalles en komplett Heyting -algebra. Denne oppfatningen sammenfaller med begrepene ramme og språk .
  • Komplett gitter . Et komplett gitter er en poset der vilkårlige (muligens uendelige) slutter seg til (suprema) og møter (infima).
  • Fullstendig delordre . En komplett delordre, eller cpo , er en rettet fullstendig delordre (qv) med minst element.
  • Fullstendig forhold . Synonym for Connected relation .
  • Komplett semilattice . Forestillingen om en komplett semilattice er definert på forskjellige måter. Som forklart i artikkelen om fullstendighet (ordensteori) , er enhver poset som enten alt suprema eller alle infima eksisterer for allerede et komplett gitter. Derfor er ideen om en komplett semilatt noen ganger brukt til å falle sammen med ideen om et komplett gitter. I andre tilfeller er komplette (møte-) semilattices definert for å være avgrensede komplette cpos , som uten tvil er den mest komplette klassen av poseter som ikke allerede er komplette gitter.
  • Helt distribuerende gitter . Et komplett gitter er fullstendig distribuerende hvis vilkårlige sammenføyninger fordeles over vilkårlige møter.
  • Fullføring . En ferdigstillelse av en poset er en ordreinnbygging av posetten i et komplett gitter.
  • Fullføring ved kutt . Synonym for ferdigstillelse av Dedekind - MacNeille .
  • Tilkoblet forhold . En total eller fullstendig relasjon R på et sett X har egenskapen som for alle elementene x , y av X , minst én av x R y eller y R x holder.
  • Kontinuerlig poset . En poset er kontinuerlig hvis den har en base , dvs. en undersett B av P slik at hvert element x av P er overordnet til et rettet sett som finnes i { y i B | y << x }.
  • Kontinuerlig funksjon . Se Scott-kontinuerlig .
  • Converse . Det motsatte <° av en ordre <er det der x <° y når y <x.
  • Deksel . Et element y i en poset P sies å dekke et element x i P (og kalles et deksel på x ) hvis x < y og det ikke er noe element z av P slik at x < z < y .
  • CPO . Se fullstendig delbestilling .

D

  • dcpo . Se fullstendig delordre .
  • Dedekind - MacNeille ferdigstillelse . Dedekind - MacNeille -ferdigstillelsen av et delvis bestilt sett er det minste komplette gitteret som inneholder det.
  • Tett rekkefølge . En tett poset P er en der, for alle elementene x og y i P med x < y , er det et element z i P , slik at x < z < y . Et delsett Q av P er tett i P hvis det for et element x < y i P er et element z i Q slik at x < z < y .
  • Regissert sett . Et ikke-tomt undersett X av en poset P kalles rettet, hvis det for alle elementene x og y i X er et element z av X slik at x z og y z . Den doble oppfatningen kalles filtrert .
  • Fullstendig delvis ordre rettet . En poset D sies å være en rettet komplett poset, eller dcpo , hvis hver rettet delmengde av D har et overordnet.
  • Distribuerende . Et gitter L kalles distributivt hvis vi for alle x , y og z i L finner at x ∧ ( y z ) = ( x y ) ∨ ( x z ). Denne tilstanden er kjent for å være ekvivalent med dens orden dual. Et møte- semilattice er fordelende hvis for alle elementene a , b og x , a b x innebærer eksistensen av elementene a ' a og b' b slik at a ' b' = x . Se også fullstendig distribuerende .
  • Domene . Domene er et generelt begrep for objekter som de som studeres i domeneteori . Hvis det brukes, krever det ytterligere definisjon.
  • Ned-sett . Se nedre sett .
  • Dobbel . For en poset ( P , ≤) er dobbel rekkefølge P d = ( P , ≥) definert ved å sette x ≥ y hvis og bare hvis y ≤ x . Den doble rekkefølgen av P er noen ganger betegnet med P op , og kalles også motsatt eller omvendt rekkefølge. Enhver ordensteoretisk forestilling induserer en dobbel forestilling, definert ved å bruke den originale setningen på rekkefølgen dual av et gitt sett. Dette utveksler ≤ og ≥, møtes og blir med, null og enhet.

E

  • Forlengelse . For delordrer ≤ og ≤ ′ på et sett X , er ≤ ′ en forlengelse av ≤ forutsatt at for alle elementene x og y av X , betyr xy at x ≤ ′ y .

F

  • Filtrer . Et undersett X av en poset P kalles et filter hvis det er et filtrert øvre sett. Den doble oppfatningen kalles ideell .
  • Filtrert . Et ikke-tomt undersett X av en poset P kalles filtrert, hvis det for alle elementene x og y i X er et element z av X slik at zx og zy . Den doble oppfatningen kalles regissert .
  • Endelig element . Se kompakt .
  • Ramme . En ramme F er et komplett gitter, der for hver x i F og hver delsett Y av F , den uendelige fordelingsloven x Y ={ x y | y i Y } holder. Rammer er også kjent som lokaliteter og som komplette Heyting -algebraer .

G

  • Galois -forbindelse . Gitt to posisjoner P og Q ,kalleset par monotone funksjoner F : P Q og G : Q P en Galois -forbindelse, hvis F ( x ) ≤ y tilsvarer x G ( y ), for alle x i P og y i Q . F er kalt den nedre adjungerte av G og G er kalt den øvre adjungerte av F .
  • Det største elementet . For en delmengde X av en poset P , et element en av X blir kalt den største del av X , hvis x en for hvert element x i X . Den doble oppfatningen kalles minst element .
  • Bakken sett . Grunnsettet til en poset ( X , ≤) er settet X som delvis rekkefølge ≤ er definert på.

H

  • Heyting algebra . En Heyting algebra H er et avgrenset gitter, hvor funksjonen f et : H H , gitt ved f en ( x ) = et x er den nedre adjungerte av et Galois-forbindelse , for hvert element en av H . Den øvre adjointen til f a er deretter betegnet med g a , med g a ( x ) = a ⇒; x . Hver boolsk algebra er en Heyting -algebra.
  • Hasse diagram . Et Hasse -diagram er en type matematisk diagram som brukes til å representere et endelig delvis ordnet sett, i form av en tegning av dets transitive reduksjon .
  • Homogent forhold . En homogen relasjon på et setter en delmengde avSaid annerledes, det er en binær relasjon overseg selv.

Jeg

  • Ideell . Et ideal er en undersett X av en poset P som er et rettet lavere sett. Den doble oppfatningen kalles filter .
  • Forekomstalgebra . Den forekomsten algebra av en poset er det assosiative algebra av alle skalar-verdi funksjoner på intervaller, med addisjon og skalar multiplikasjon definert punktvis, og multiplikasjon definert som en viss konvolusjon; se forekomstalgebra for detaljer.
  • Infimum . For en poset P og en delmengde X av P , den største element i settet av nedre grenser for X (hvis det finnes, som det kan ikke) kalles infimum , møtes , eller største nedre grensen av X . Den er merket med inf X eller X . Det minste to elementer kan skrives som inf { x , y } eller x y . Hvis mengden X er endelig, snakker man om et begrenset minimum . Den doble oppfatningen kalles supremum .
  • Intervall . For to elementer a , b i et delvis ordnet sett P , er intervallet [ a , b ] delsettet { x i P | en x b } av P . Hvis a b ikke holder intervallet vil være tomt.
  • Endelig intervallposisjon . Et delvis ordnet sett P er begrenset intervall hvis hvert intervall i skjemaet {x i P | x ≤ a} er et begrenset sett.
  • Omvendt . Se Converse .
  • Irrefleksiv . En relasjon R på et sett X er irrefleksiv, hvis det ikke er noe element x i X slik at x R x .
  • Isoton . Se monoton .

J

  • Bli med . Se overlegenhet .

L

  • Gitter . Et gitter er en poset der alle ikke-tomme endelige sammenføyninger (suprema) og møter (infima) eksisterer.
  • Minste element . For en delmengde X av en poset P , et element en av X kalles minste element av X , hvis en x for hvert element x i X . Den doble oppfatningen kalles det største elementet .
  • Den lengde av en kjetting er antallet av elementer mindre en. En kjede med 1 element har lengde 0, ett med 2 elementer har lengde 1 osv.
  • Lineær . Se totalbestilling .
  • Lineær forlengelse . En lineær forlengelse av en delrekkefølge er en utvidelse som er en lineær orden, eller total rekkefølge.
  • Lokalitet . En lokalitet er en komplett Heyting -algebra . Lokaliteter kalles også rammer og vises i steinalitet og meningsløs topologi .
  • Lokalt endelig poset . Et delvis ordnet sett P er lokalt endelig hvis hvert intervall [ a , b ] = { x i P | a x b } er et begrenset sett.
  • Nedre grense . En nedre grense av et delsett X av en poset P er et element b i P , slik at f x , for alle x i X . Den doble oppfatningen kalles øvre grense .
  • Nedre sett . En undergruppe X av et poset P kalles et lavere sett hvis, for alle elementer x i X og p i P , p x innebærer at p er inneholdt i X . Den doble oppfatningen kalles øvre sett .

M

  • Maksimal kjede . En kjede i en poset som ingen elementer kan legges til uten å miste eiendommen til å bli fullstendig bestilt. Dette er sterkere enn å være en mettet kjede, da det også utelukker eksistensen av elementer enten mindre enn alle elementene i kjeden eller større enn alle dens elementer. En endelig mettet kjede er maksimal hvis og bare hvis den inneholder både et minimalt og et maksimalt element i stillingen.
  • Maksimalt element . En maksimal element i en undergruppe X av en poset P er et element m av X , slik at m x innebærer m = x , for alle x i X . Den doble oppfatningen kalles minimal element .
  • Maksimalt element . Synonym for største element. For en delmengde X av en poset P , et element en av X kalles høyeste element av X når x en for hvert element x i X . Et maxim um element er nødvendigvis maxim al , men det motsatte trenger ikke holde.
  • Møt . Se infimum .
  • Minimal element . En minimal element i en undergruppe X av en poset P er et element m av X , slik at x m innebærer m = x , for alle x i X . Den doble oppfatningen kalles maksimalt element .
  • Minimum element . Synonym for minste element. For en delmengde X av en poset P , et element en av X kalles minimumselementet av X når x en for hvert element x i X . Et minim um element er nødvendigvis minim al , men det motsatte trenger ikke holde.
  • Monoton . En funksjon f mellom posisjonene P og Q er monoton hvis, for alle elementene x , y av P , x y (i P ) innebærer f ( x ) ≤ f ( y ) (i Q ). Andre navn på denne eiendommen er isoton og bevarer ordre . I analyse , i nærvær av totale ordrer , kalles slike funksjoner ofte monotont økende , men dette er ikke en veldig praktisk beskrivelse når det gjelder ikke-totale ordrer. Den doble oppfatningen kalles antitone eller ordre reversering .

O

  • Order-dual . Ordredualen til et delvis ordnet sett er det samme settet med delordensforholdet erstattet av det motsatte.
  • Ordreinnbygging . En funksjon f mellom Posets P og Q er en ordre-innebygging hvis, for alle elementer x , y av P , x y (i P ) er ekvivalent med f ( x ) ≤ f ( y ) (i Q ).
  • Bestill isomorfisme . En kartlegging f : P Q mellom to posisjoner P og Q kalles en ordensisomorfisme, hvis den er bijektiv og både f og f −1 er monotone funksjoner . Tilsvarende er en ordensisomorfisme en subjektiv rekkefølge som innebygd .
  • Ordrebevaring . Se monoton .
  • Ordre-reversering . Se antitone .

P

  • Delvis ordre . En delvis ordre er en binær relasjon som er refleksiv , antisymmetrisk og transitiv . I et lite misbruk av terminologi brukes begrepet noen ganger også for å ikke referere til et slikt forhold, men til det tilhørende delvis ordnede settet.
  • Delvis bestilt sett . Et delvis bestilt setteller poset for kort, er et settsammen med en delvis ordrepå
  • Poset . Et delvis bestilt sett.
  • Forhåndsbestill . En forhåndsbestilling er en binær relasjon som er refleksiv og transitiv . Slike bestillinger kan også kalles quasiorders eller ikke-strenge forhåndsbestillinger . Begrepet forhåndsbestilling brukes også for å betegne et asyklisk binært forhold (også kalt en asyklisk digraph ).
  • Forhåndsbestilt sett . Et forhåndsbestilt setter et settsammen med en forhåndsbestiltpå
  • Bevarer . En funksjon f mellom posisjonene P og Q sies å bevare suprema (sammenføyninger), hvis vi for alle undersett X av P som har en supremum sup X i P finner at sup { f ( x ): x i X } eksisterer og er lik f (sup X ). En slik funksjon kalles også join-preserving . Analogt sier man at f bevarer endelige, ikke-tomme, dirigerte eller vilkårlige sammenføyninger (eller møter). Den omvendte egenskapen kalles join-reflecting .
  • Prime . En ideell I i et gitter L sies å være primtall, dersom, for alle elementer x og y i L , x y i I betyr X i I eller y i I . Den doble oppfatningen kalles et primfilter . Tilsvarende er et sett et førsteklasses filter hvis og bare hvis komplementet er et hovedideal.
  • Rektor . Et filter kalles hovedfilter hvis det har minst element. Tosidig er et hovedideal et ideal med det største elementet. De minst eller største elementene kan også kalles hovedelementer i disse situasjonene.
  • Projeksjon (operatør) . Et selvkart på et delvis ordnet sett som er monotont og ideelt under funksjonskomposisjon . Prognoser spiller en viktig rolle i domeneteorien .
  • Pseudokomplement . I en Heyting -algebra er elementet x ⇒; 0 kalles pseudokomplementet til x . Det er også gitt med sup { y  : yx = 0}, dvs. som den minste øvre grensen for alle elementene y med yx = 0.

Sp

  • Quasiorder . Se forhåndsbestilling .
  • Kvasitransitiv . En relasjon er kvasitransitiv hvis relasjonen til forskjellige elementer er transitive. Transitive innebærer quasitransitive og quasitransitive innebærer acyklisk.

R

  • Reflekterer . En funksjon f mellom posisjonene P og Q sies å gjenspeile suprema (slutter seg til), hvis for alle undersettene X av P som overordnet sup { f ( x ): x i X } eksisterer og har formen f ( s ) for noen s i P , så finner vi at sup X eksisterer og at sup X = s . Analogt sier man at f gjenspeiler endelige, ikke-tomme, dirigerte eller vilkårlige sammenføyninger (eller møter). Den omvendte egenskapen kalles join-preserving .
  • Refleksiv . En binær relasjon R på et sett X er refleksiv, hvis x R x har for hvert element x i X .
  • Rester . Et dobbeltkart festet til en gjenværende kartlegging .
  • Residuated kartlegging . Et monotont kart som forhåndsbildet til et prinsipielt ned-sett igjen er hoved. Tilsvarende en komponent i en Galois -forbindelse.

S

  • Mettet kjede . En kjede slik at ingen elementer kan legges til mellom to av elementene uten å miste eiendommen til å bli fullstendig bestilt. Hvis kjeden er begrenset, betyr dette at i hvert par påfølgende elementer dekker den større den mindre. Se også maksimal kjede.
  • Spredt . En total ordre er spredt hvis den ikke har et tett bestilt delsett.
  • Scott-kontinuerlig . En monoton funksjon f  : P Q mellom posisjonene P og Q er Scott-kontinuerlig hvissettet { fx |for hvert regissert sett D som har en supremum sup D i P x i D } har supremum f (sup D ) i Q . Uttalt annerledes, en Scott-kontinuerlig funksjon er en som bevarer alt rettet suprema. Dette tilsvarer faktisk å være kontinuerlig med hensyn til Scott -topologien på de respektive posettene.
  • Scott -domene . Et Scott -domene er et delvis ordnet sett som er et begrenset komplett algebraisk CPO .
  • Scott åpnet . Se Scott topologi .
  • Scott topologi . For en poset P , et delsett O er Scott-åpen dersom det er et øvre sett og alle rettet settene D som har en supremum i O har ikke-tom skjæringspunktet med O . Settet med alle Scott-åpne sett danner en topologi , Scott-topologien .
  • Semilattice . En semilattice er en poset der enten alle endelige ikke-tomme sammenføyninger (suprema) eller alle endelige ikke-tomme møter (infima) eksisterer. Følgelig snakker man om en join-semilattice eller meet-semilattice .
  • Minste element . Se minst element .
  • Sperner -eiendom av et delvis bestilt sett
  • Sperner poset
  • Strengt Sperner poset
  • Sterkt Sperner poset
  • Streng rekkefølge . Se streng delordre .
  • Strenge delordre . En streng delordre er en homogen binær relasjon som er transitive , irrefleksive og antisymmetriske .
  • Streng forhåndsbestilling . Se streng delordre .
  • Supremum . For en poset P og en delmengde X av P , det minste element i settet av øvre grensene av X (hvis det finnes, som det kan ikke) kalles supremum , delta , eller i det minste øvre grense for X . Den er merket med sup X eller X . Overdelen av to elementer kan skrives som sup { x , y } eller x y . Hvis mengden X er endelig, snakker man om et begrenset overordnet . Den doble oppfatningen kalles infimum .
  • Suzumura -konsistens . En binær relasjon R er Suzumura konsistent hvis x R y innebærer at x R y eller ikke y R x .
  • Symmetrisk relasjon . En homogen forhold R på et sett X er symmetrisk, hvis x R y innebærer y R x , for alle elementer x , y i X .

T

  • Topp . Se enhet .
  • Total bestilling . En total rekkefølge T er en delvis rekkefølge der vi for x og y i T har x y eller y x . Totale ordrer kalles også lineære ordrer eller kjeder .
  • Totalt forhold . Synonym for Connected relation .
  • Transitivt forhold . Et forhold R på et sett X er transitive, hvis x R y og y R z antyde x R z , for alle elementer x , y , z i x .
  • Transitiv lukking . Den transitive lukning R * av en forbindelse R består av alle parene x , y som det cists en begrenset kjetting x R en , en R b , ..., z R y .

U

  • Enhet . Det største elementet i en poset P kan kalles enhet eller bare 1 (hvis den eksisterer). Et annet vanlig begrep for dette elementet er topp . Det er den infimum av den tomme settet og den supremum av P . Den doble oppfatningen kalles null .
  • Oppsatt . Se øvre sett .
  • Øvre grense . En øvre grense for et delsett X av en poset P er et element b i P , slik at x b , for alt x i X . Den doble oppfatningen kalles nedre grense .
  • Øvre sett . En undergruppe X av et poset P kalles et øvre sett hvis, for alle elementer x i X og p i P , x p innebærer at p er inneholdt i X . Den doble oppfatningen kalles lavere sett .

V

  • Verdivurdering . Gitt et gitter er en verdsettelse streng (det vil si ), monoton, modulær (det vil si ) og positiv. Kontinuerlige verdivurderinger er en generalisering av tiltak.

W

  • Langt under forhold . I en poset P , noe element x er langt under y , som er skrevet x << y , hvis for alle rettet delmengder D av P , som har en supremum, y sup D antyder x d for noen d i D . En sier også at x tilnærmet y . Se også domeneteori .
  • Svak rekkefølge . En delvis rekkefølge ≤ på et sett X er en svak rekkefølge forutsatt at poset (X, ≤) er isomorf til en tallbar samling sett bestilt ved sammenligning av kardinalitet .

Z

  • Null . Det minste elementet i en poset P kan kalles null eller bare 0 (hvis det eksisterer). Et annet vanlig begrep for dette elementet er bunn . Null er den supremum av den tomme settet og den infimum av P . Den doble oppfatningen kalles enhet .

Merknader

Referanser

Definisjonene gitt her er i samsvar med de som finnes i følgende standardoppslagsbøker:

  • BA Davey og HA Priestley, Introduction to Lattices and Order , 2. utgave, Cambridge University Press, 2002.
  • G. Gierz, KH Hofmann, K. Keimel, JD Lawson, M. Mislove og DS Scott, Continuous Lattices and Domains , In Encyclopedia of Mathematics and its Applications , Vol. 93, Cambridge University Press, 2003.

Spesifikke definisjoner:

  • Deng, Bangming (2008), Endelige dimensjonale algebraer og kvantegrupper , Matematiske undersøkelser og monografier, 150 , American Mathematical Society, ISBN 978-0-8218-4186-0