Beställ inbäddning

I ordningsteori , en gren av matematik , är en orderinbäddning en speciell sorts monoton funktion , som ger ett sätt att inkludera en delvis ordnad uppsättning i en annan. Liksom Galois-kopplingar utgör ordningsinbäddningar en föreställning som är strikt svagare än begreppet ordningsisomorfism . Båda dessa försvagningar kan förstås i termer av kategoriteori .

Formell definition

Formellt, givet två delvis ordnade uppsättningar (posets) $(S,\leq )$ och $(T,\preceq )$ , en funktion ${ \displaystyle f:S\to T}$ är en orderinbäddning om $f$ är både orderbevarande och orderreflekterande , dvs för alla $x$ och $y$ i ${\ displaystyle S}$ , har man

$x\leq y{\text{ if and only if }}f(x)\preceq f(y).$

En sådan funktion är nödvändigtvis injektiv eftersom $f(x)=f(y)$ innebär $x\leq y$ och $y \leq x$ . Om det finns en beställningsinbäddning mellan två posetter $S$ och $T$ , säger man att $S$ kan bäddas in i $T$ .

Egenskaper

Ömsesidig ordningsinbäddning av $(0,1)$ och $[0,1]$ , med $f (x)=(94x+3)/100$ i båda riktningarna.

Mängden $S$ av divisorer på 6, delvis ordnade efter x delar y . Inbäddningen $id:\{1,2,3\}\to S$ kan inte vara en korrigering.

En ordningsisomorfism kan karakteriseras som en surjektiv ordningsinbäddning. Som en konsekvens begränsar varje ordning som bäddar in f till en isomorfism mellan dess domän S och dess bild f ( S ), vilket motiverar termen "inbäddning". Å andra sidan kan det mycket väl vara så att två (nödvändigtvis oändliga) poser är ömsesidigt ordningsinbäddade i varandra utan att vara ordningsisomorfa.

Ett exempel är det öppna intervallet $\displaystyle (0,1)}$ för reella tal och motsvarande slutna intervall ${\displaystyle [0,1]$ } Funktionen $f(x)=(94x+3)/100$ mappar den förra till delmängden $(0.03,0.97)$ av den senare och den senare till delmängden $[0.03,0.97]$ av den förra, se bild. Att beställa båda uppsättningarna på det naturliga sättet, $f$ är både ordningsbevarande och ordningsreflekterande (eftersom det är en affin funktion ). Ändå kan ingen isomorfism mellan de två poseterna existera, eftersom t.ex. $[0,1]$ har ett minsta element medan $(0,1)$ inte har det. För ett liknande exempel med användning av arctan för att ordna-inbädda de reella talen i ett intervall, och identitetskartan för den omvända riktningen, se t.ex. Just och Weese (1996).

En retract är ett par $(f,g)$ av ordningsbevarande kartor vars sammansättning $g\circ f$ är identiteten. I det här fallet kallas ${\displaystyle f} en coretraction och måste vara en orderinbäddning.$ Men inte varje orderinbäddning är en korrigering. Som ett trivialt exempel har den unika ordningsinbäddningen $f:\emptyset \to \{1\}$ från den tomma satsen till en icke-tom sats ingen tillbakadragning, eftersom det inte finns någon ordningsbevarande map $g:\{1\}\to \emptyset$ . Betrakta mer illustrativt mängden $S$ av divisorer på 6, delvis ordnade efter x dividerar y , se bild. Betrakta den inbäddade underposten $\{1,2,3\}$ . En indragning av inbäddnings- $\displaystyle id:\{1,2,3\}\to S}$ skulle behöva skicka $6$ till någonstans i $\{1,2,3\}$ ovanför både $2$ och $3$ , men det finns ingen sådan plats.

Ytterligare perspektiv

Poster kan enkelt ses från många perspektiv, och beställningsinbäddningar är tillräckligt grundläggande för att de tenderar att vara synliga överallt. Till exempel:

• ( Modell teoretiskt ) En poset är en uppsättning utrustad med en (reflexiv, antisymmetrisk och transitiv) binär relation . En ordning som bäddar in A → B är en isomorfism från A till en elementär understruktur av B .
• ( Graf teoretiskt ) En poset är en (transitiv, acyklisk, riktad, reflexiv) graf . En ordning som bäddar in A → B är en grafisomorfism från A till en inducerad subgraf av B .
• ( Kategori teoretiskt ) En poset är en (liten, tunn och skelett) kategori så att varje hemset har högst ett element. En order som bäddar in A → B är en fullständig och trogen funktion från A till B som är injektiv på objekt, eller motsvarande en isomorfism från A till en fullständig underkategori av B .

Se även

• Dushnik-Millers teorem
• Lavers teorem