Förhandsbeställning

Transitiva binära relationer
Symmetrisk Antisymmetrisk Ansluten Välgrundad Har anslutit sig Har möter Reflexiv Irreflexiv Asymmetrisk Totalt, Semiconnex Antireflexiv _ Ekvivalensförhållande Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Förbeställning (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Delordning ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total förbeställning ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total beställning ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Förhandsbeställning ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Väl kvasiordning ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Välbeställt ✗ Y Y Y ✗ ✗ Y ✗ ✗ Gitter ✗ Y ✗ ✗ Y Y Y ✗ ✗ Sammanfoga-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Möt-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strikt delordning ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strikt svag ordning ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strikt total beställning ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetrisk Antisymmetrisk Ansluten Välgrundad Har anslutit sig Har möter Reflexiv Irreflexiv Asymmetrisk Definitioner, för alla $a,b$ och $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ eller }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{finns}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{inte }}bRa\end{aligned}}$
Y indikerar att kolumnens egenskap alltid är sann för radens term (till vänster), medan ✗ indikerar att egenskapen inte är garanterad i allmänhet (den kanske, eller kanske inte, håller). Till exempel, att varje ekvivalensrelation är symmetrisk, men inte nödvändigtvis antisymmetrisk, indikeras med Y i kolumnen "Symmetrisk" respektive ✗ i kolumnen "Antisymmetrisk". Alla definitioner kräver tyst att den homogena relationen $R$ ska vara transitiv : för alla $a,b,c,$ om $aRb$ och $}$${\displaystyle$$aRc.$ sedan En terms definition kan kräva ytterligare egenskaper som inte är listade i den här tabellen.

I mängdteorin är en förordning på en mängd $X$ en förordning $\leq$ på $X$ (en transitiv och reflexiv relation på ${\displaystyle X})$ som är starkt sammankopplad (vilket betyder att två godtyckliga punkter är jämförbara) och välgrundad i den meningen att den inducerade relationen $x<y$ definierad av $x\leq y{\text{ och }}y\nleq x$ är en välgrundad relation .

Förbeställning på en uppsättning

En förordning på en uppsättning $X$ är en homogen binär relation $\,\leq \,$ på $X$ som uppfyller följande villkor:

1. Reflexivitet : $x\leq x$ för alla $x\in X.$
2. Transitivitet : om $x<y$ och $y<z$ så är $x<z$ för alla $x,y,z\in X.$
3. Totalt/starkt anslutet : $x\leq y$ eller $y\leq x$ för alla $x,y\in X.$
4. för varje icke-tom delmängd $S\subseteq X,$ finns det några $m\in S$ så att $m\leq s$ för alla $s\in S.$
   • Detta villkor är ekvivalent med den inducerade strikta förordningen $x<y$ definierad av $x\leq y$ och $y\ nleq x$ är en välgrundad relation .

En homogen binär relation $\,\leq \,$ på $X$ är en förordning om och endast om det finns en surjection $\pi :X\to Y$ till en välordnad uppsättning $(Y,\lesssim )$ så att för alla $x,y\in X,$${\textstyle x\leq y}$ om och endast om $\pi (x)\lesssim \pi (y).$

Exempel

Hassediagram över förbrunnsbeställningen $\lfloor x/4\rfloor \leq \lfloor y/5\rfloor$ på de icke-negativa heltal, som visas upp till 29. Cykler är indikeras i rött och $\lfloor \cdot \rfloor$ anger golvfunktionen .

Hassediagram över förbeställningen $\lfloor x/4\rfloor \leq \lfloor y/4\rfloor$ på de icke-negativa heltal, som visas upp till 18. Den tillhörande ekvivalensrelationen är $\lfloor x/4\rfloor =\lfloor y/4\rfloor ;$ den identifierar siffrorna i varje ljusröd fyrkant.

Givet en mängd $A,$ den binära relationen på mängden $X:=\operatorname {Finite} (A)$ av alla finita delmängder av $A$ definieras av $S\leq T$ om och endast om $|S|\leq |T|$ (där $|\cdot |$ anger uppsättningens kardinalitet ) är en förordning.

Egenskaper

Om $\leq$ är en förordning på $X,$ så är relationen $\sim$ definierad av

$$x\sim y{\text{ if and only if }}x\leq y\land y\leq x$$

är en ekvivalensrelation på $X,$ och $\leq$ inducerar en välordning på kvoten $X/{\sim }.$ Ordningstypen för denna inducerade brunnsordning är en ordningsföljd , kallad längden på förbeställningen .

En norm på en uppsättning $X$ är en karta från $X$ till ordinalerna. Varje norm framkallar en förordnande; om $\phi :X\to Ord$ är en norm, ges den tillhörande förbeställningen av

$$x\leq y{\text{ if and only if }}\phi (x)\leq \phi (y)$$

Omvänt induceras varje förordning av en unik regelbunden norm (en norm $\phi :X\to Ord$ är regelbunden om, för någon $x\in X$ och någon $\alpha <\phi (x),$ det finns $y\in X$ så att $\phi (y) =\alpha$ ).

Förhandsbeställningsfastighet

Om ${\boldsymbol {\Gamma }}$ är en punktklass av delmängder av någon samling ${\mathcal {F}}$ av polska mellanslag , ${\mathcal {F}}$ stängd under kartesisk produkt , och om $\leq$ är en förordning av någon delmängd $P$ av något element $X$ av ${\mathcal {F}},$ då sägs ${\displaystyle \leq } vara en$${\boldsymbol {\Gamma }}$ - förordning av $P$ om relationerna $<^{*}$ och $\leq ^{*}$ är element av ${\boldsymbol {\Gamma }},$ där för $x,y\in X,$

1. $x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))$
2. $x\leq ^{*}y{\text{ if and only if }}x\in P\land (y \notin P\lor x\leq y)$

${\boldsymbol {\Gamma }}$ sägs ha prewellorder-egenskapen om varje uppsättning i ${\boldsymbol {\Gamma }}$ medger en ${\boldsymbol {\Gamma } }$ -förbeställning.

Förbeställningsegenskapen är relaterad till egenskapen i starkare skala ; i praktiken har många punktklasser som har egenskapen förbeställande också skalegenskapen, vilket gör det möjligt att dra starkare slutsatser.

Exempel

${\boldsymbol {\Pi }}_{1}^{1}$ och ${\boldsymbol {\Sigma }}_{2}^{1}$ har båda förhandsbeställning av egendom; detta kan bevisas enbart i ZFC . Om man antar tillräckligt stora kardinaler , för varje $n\in \omega ,$${\boldsymbol {\Pi }}_{2n+1}^{1}$ och ${\boldsymbol {\Sigma }}_{2n+2}^{1}$ har prewellording-egenskapen.

Konsekvenser

Minskning

Om ${\boldsymbol {\Gamma }}$ är en adekvat punktklass med egenskapen prewellordering, så har den också reduktionsegenskapen : För vilket mellanslag som helst $X\in {\mathcal {F}}$ och alla uppsättningar $A,B\subseteq X,$$A$ och $B$ båda i ${\boldsymbol {\Gamma }},$ föreningen $A\cup B$ kan delas upp i set $A^{*},B^{*},$ båda i ${\ fetsymbol {\Gamma }},$ så att $A^{*}\subseteq A$ och $B^{*}\subseteq B.$

Separation

Om ${\boldsymbol {\Gamma }}$ är en adekvat punktklass vars dubbla punktklass har prewellorder-egenskapen, så har ${\boldsymbol {\Gamma }}$ separationsegenskapen : För valfritt mellanslag $X\in {\mathcal {F}}$ och alla uppsättningar $A,B\subseteq X,$$A$ och $B$ disjunkta uppsättningar både i ${\boldsymbol {\Gamma }},$ finns en mängd $C\subseteq X$ så att både $C$ och dess komplement $X\setminus C$ är i ${\boldsymbol {\Gamma }},$ med $A\subseteq C$ och $B\cap C=\varnothing .$

Till exempel, ${\boldsymbol {\Pi }}_{1}^{1}$ har prewellording-egenskapen, så ${\boldsymbol {\Sigma }}_{1} ^{1}$ har separationsegenskapen. Detta betyder att om $A$ och $B$ är disjunkta analytiska delmängder av något polskt utrymme $X,$ så finns det en Borel -delmängd $C$ av $X$ så att $C$ inkluderar $A$ och är disjunkt från $B.$

Se även

• Beskrivande mängdlära – Delfält av matematisk logik
• Graderad poset – delvis ordnad uppsättning utrustad med en rangfunktion, ibland kallad en rangordnad poset Sidor som visar wikidata-beskrivningar som en reserv – en graderad poset är analog med en förordning med en norm, som ersätter en karta till ordningstalen med en karta till de naturliga talen
• Skalegenskap – typ av objekt i beskrivande mängdteori Sidor som visar wikidatabeskrivningar som en reserv

•    Moschovakis, Yiannis N. (1980). Beskrivande mängdteori . Amsterdam: Norra Holland. ISBN 978-0-08-096319-8 . OCLC 499778252 .
•    Moschovakis, Yiannis N. (2006). Anteckningar om mängdlära . New York: Springer. ISBN 978-0-387-31609-3 . OCLC 209913560 .