Forudbestilling

Charles Lebert September 9, 2016 F 0 0
FONT SIZE:
fontsize_dec
fontsize_inc

I matematik, specielt med henblik på teorien, en forudbestilling eller quasiorder er en binær relation, der er refleksiv og transitiv. Alle delvise ordrer og ækvivalens relationer er preorders, men preorders er mere generelt.

Navnet "preorder" kommer fra tanken om, at preorders er "næsten ordrer, men ikke helt; de er hverken nødvendigvis anti-symmetrisk eller symmetrisk. Fordi en forudbestilling er en binær relation, kan symbolet ≤ anvendes som notationssystem indretning til relationen. Men fordi de ikke nødvendigvis anti-symmetrisk, nogle af den almindelige intuition knyttet til symbolet ≤ gælder måske ikke. På den anden side kan en forudbestilling anvendes på en ligefrem måde, at definere en delvis orden og en ækvivalens relation. At gøre dette, er imidlertid ikke altid nyttigt eller umagen værd, afhængigt af problemområdet ved at blive undersøgt.

I ord, når en ≤ b, kan man sige, at B omfatter en eller at en forud b, eller at b formindsket til en. Lejlighedsvis, notationen ← eller anvendes i stedet for ≤.

Til hver preorder, der svarer en orienteret graf, med elementer i sættet svarer til toppunkter, og ordren forholdet mellem par af elementer svarende til den rettede kanter mellem knuder. Det modsatte er ikke tilfældet: mest rettet grafer hverken refleksiv eller transitive. Bemærk, at i almindelighed kan de tilsvarende grafer være cykliske grafer: preorders kan have cyklusser i dem. En preorder der er antisymmetrisk ikke længere har cykler; det er en delvis orden, og svarer til en rettet acyklisk graf. En preorder, der er symmetrisk er en ækvivalensrelation; Det kan opfattes som at have mistet pejlemærkerne på kanterne af grafen. I almindelighed kan en forudbestilling have mange usammenhængende komponenter.

Formel definition

Overveje nogle sæt P og en binær relation ≤ på P. Så ≤ er en preorder, eller quasiorder, hvis det er refleksiv og transitiv, dvs for alle a, b og c i P, har vi, at:

Et træk, der er udstyret med en forudbestilling kaldes en preordered sæt.

Hvis en forudbestilling er også antisymmetric, dvs. et ≤ b og b ≤ a indebærer a = b, så er det en delvis orden.

På den anden side, hvis det er symmetrisk, det vil sige, hvis en ≤ b ≤ b indebærer en, så er det en ækvivalens relation.

Et preorder som er bevaret i alle sammenhænge kaldes en precongruence. En precongruence som også er symmetrisk er en kongruens forhold.

Ækvivalent, kan en forudbestilt sæt P defineres som en kategori med objekter elementer af P, og hver hom-sæt, der har de fleste et element.

Alternativt kan en forudbestilt sæt forstås som en beriget kategori, beriget over kategori 2 =.

En preordered klasse er en klasse udstyret med en forudbestilling. Hvert sæt er en klasse og så hver forudbestilt sæt er en preordered klasse. Preordered klasser kan defineres som tynde kategorier, dvs. som kategorier med højst en morphism fra et objekt til et andet.

Eksempler

  • Den sikre adgang forhold i nogen orienteret graf giver anledning til en forudbestilling, hvor x ≤ y i preorder hvis og kun hvis der er en sti fra X til Y i orienteret graf. Omvendt hver forudbestilling er sikre adgang kobling i en orienteret graf med x ≤ y). Dog kan mange forskellige grafer har samme sikre adgang preorder som hinanden. På samme måde til at sikre adgang for dirigerede acykliske grafer, instrueret grafer uden cykler, giver anledning til delvist bestilt sæt.
  • Enhver endelig topologisk rum giver anledning til en forudbestilling på dens punkter, hvor x ≤ y hvis og kun hvis x tilhører hvert kvarter af y, og hver finite preorder kan være udformet som specialiseringen preorder af et topologisk rum på denne måde. Det vil sige, der er en 1-til-1 overensstemmelse mellem finite topologier og finite preorders. Men forholdet mellem uendelige topologiske rum og deres specialisering preorders er ikke 1-til-1.
  • Et net er en rettet preorder, det vil sige, hvert par elementer har en øvre grænse. Definitionen af ​​konvergens via net er vigtig i topologi, hvor preorders kan ikke erstattes af delvist bestilt sæt uden at miste vigtige funktioner.
  • Relationen defineret ved hvis det, hvor f er en funktion i nogle forudbestilling.
  • Relationen er defineret ved, hvis der findes en indsprøjtning fra x til y. Injektion kan erstattes af surjection eller enhver type struktur-bevarelse funktion, såsom ring homomorfi eller permutation.
  • Den indlejring relation til tællelige samlede orderings.
  • Grafen-mol forhold i grafteori.
  • En kategori med højst én morphism fra ethvert objekt til et andet objekt er en preorder. Disse kategorier kaldes tynd. I denne forstand kategorierne "generalisere" preorders ved at tillade mere end én relation mellem objekter: hver morphism er et særskilt preorder forhold.

I datalogi, kan man finde eksempler på de følgende preorders.

  • Mange-en og Turing reduktioner preorders på kompleksitet klasser.
  • De subtypning relationer er normalt preorders.
  • Simulation preorders er preorders.
  • Reduktion relationer i abstrakte omskrive systemer.
  • Den encompassment preorder på sættet af termer, defineret ved s≤t hvis en subterm af t er en udskiftning forekomst af s.

Eksempel på en total preorder:

  • Præference, i henhold til fælles modeller.

Anvendelser

Preorders spiller en central rolle i flere situationer:

  • Hver preorder kan gives en topologi, at Alexandrov topologi; og faktisk er alle preorder på et sæt er i en-til-en korrespondance med en Alexandrov topologi på sættet.
  • Preorders kan anvendes til at definere indvendige algebraer.
  • Preorders give Kripke semantik for visse typer af modal logik.

Konstruktioner

Hver binær relation R på et sæt S kan udvides til en preorder på S ved at tage transitive lukning og refleksiv lukning, R. transitive lukning angiver sti-forbindelse i R: x Ry hvis og kun hvis der er en R-sti fra x til y.

Givet en preorder på S kan man definere en ækvivalensrelation ~ på S, således at en ~ b hvis og kun hvis b og b a.

Ved anvendelse af denne relation, er det muligt at konstruere en delvis orden på kvotienten sæt af ækvivalens, S / ~, sættet af alle ækvivalensklasser af ~. Bemærk, at hvis forudbestilling er R, S / ~ er det sæt af R-cyklus ækvivalensklasser: x ∈ hvis og kun hvis x = y eller x er i en R-cyklus med y. Under alle omstændigheder, på S / ~ vi kan definere ≤ hvis og kun hvis x y. Ved konstruktionen af ​​~, denne definition er uafhængig af de valgte repræsentanter og den tilsvarende forhold er faktisk veldefineret. Det er let bekræftet, at dette giver en delvist ordnet sæt.

Omvendt fra en partiel orden på en partition af et sæt S man kan konstruere en preorder på S. Der er en 1-til-1 korrespondance mellem preorders og par.

For en preorder "", en relation "& lt;" kan defineres som en & lt; b hvis og kun hvis, eller ækvivalent, ved hjælp af ligningen forhold indført ovennævnte ,. Det er en streng partiel orden; hver streng delvis ordre kan være resultatet af en sådan konstruktion. Hvis preorder er anti-symmetrisk, dermed en delvis orden "≤", ligestilling er lighed, så relationen "& lt;" kan også defineres som en & lt; b hvis og kun hvis.

. Resultatet er refleksiv reduktion af forudbestilling. Men hvis forudbestilling ikke er anti-symmetrisk resultatet ikke transitive, og hvis det er, som vi har set, er det samme som før.)

Omvendt har vi en b hvis og kun hvis en & lt; b eller en ~ b. Dette er årsagen til, at notationen ""; "≤" kan være forvirrende for en forudbestilling, som ikke er anti-symmetrisk, kan det foreslå, at en ≤ b indebærer, at en & lt; b eller a = b.

Bemærk, at med denne konstruktion flere preorders "" kan give det samme forhold "& lt;", så uden yderligere oplysninger, så som ækvivalens forhold, "" kan ikke rekonstrueres fra "& lt;". Mulige preorders omfatter følgende:

  • Definer en ≤ b som en & lt; b eller a = b. Dette giver den delvise orden i forbindelse med den strenge delvise orden "& lt;" gennem refleksiv lukning; i dette tilfælde ækvivalens er lighed, så vi har ikke brug for notater og ~.
  • Definer ab som "ikke b & lt; a", hvilket svarer til at definere en ~ b som "hverken & lt; b eller b & lt; a"; disse relationer og ~ generelt ikke transitiv; men hvis de er, ~ er en ækvivalens; i dette tilfælde "& lt;" er en streng svag orden. Den resulterende preorder er total, det vil sige en total forudbestilling.

Antal preorders

Som forklaret ovenfor, er der en 1-til-1 korrespondance mellem preorders og par. Antallet af preorders er således summen af ​​antallet af delvise ordrer på hver partition. For eksempel:

  • for n = 3:
    • 1 partition på 3, hvilket giver 1 preorder
    • 3 partitioner af 2 + 1, hvilket giver 3 × 3 = 9 preorders
    • 1 partition på 1 + 1 + 1, hvilket giver 19 preorders
  • for n = 4:
    • 1 partition på 4, hvilket giver 1 preorder
    • 7 partitioner med to klasser, hvilket giver 7 × 3 = 21 preorders
    • 6 partitioner af 2 + 1 + 1, hvilket giver 6 x 19 = 114 preorders
    • 1 partition på 1 + 1 + 1 + 1, hvilket giver 219 preorders

Interval

For ab, intervallet er det sæt af punkter x opfylder økse og XB, også skrevet økse b. Den indeholder i det mindste punkter a og b. Man kan vælge at udvide definitionen for alle par. De ekstra intervaller er alle tomme.

Ved hjælp af den tilsvarende nøje sammenhæng "& lt;", kan man også definere interval som det sæt af punkter x tilfredsstille en & lt; x og x & lt; b, også skrevet en & lt; x & lt; b. Et åbent interval kan være tom, selv om en & lt; b.

Der kan også defineres på samme måde.

  Like 0   Dislike 0
Forrige artikel Paul Rabaut
Kommentarer (0)
Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha