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:
- fullstendighetsegenskaper for delordrer
- distributivity lover av orden teori
- bevaringsegenskaper for funksjoner mellom posetter.
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 , x ≤ y (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 en ≤ x .
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 x ≤ y 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 z ≤ x og z ≤ y . 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 : y ∧ x = 0}, dvs. som den minste øvre grensen for alle elementene y med y ∧ x = 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