Linjär förlängning

I ordningsteori , en gren av matematik , är en linjär förlängning av en partiell ordning en total ordning (eller linjär ordning) som är kompatibel med den partiella ordningen. Som ett klassiskt exempel är den lexikografiska ordningen för helt ordnade set en linjär förlängning av deras produktordning .

Definitioner

Linjär förlängning av en delordning

En partiell ordning är en reflexiv , transitiv och antisymmetrisk relation. Givet eventuella delordningar $\,\leq \,$ och $\,\leq ^{*}\,$ på en uppsättning $X,$$\, \leq ^{*}\,$ är en linjär förlängning av $\,\leq \,$ exakt när

1. $\,\leq ^{*}\,$ är en total order , och
2. För varje $x,y\in X,$ om $x\leq y,$ så $x\leq ^{*}y.$

Det är den andra egenskapen som får matematiker att beskriva $\,\leq ^{*}\,$ som sträckande $\,\leq .$

Alternativt kan en linjär förlängning ses som en ordningsbevarande bijektion från en delvis ordnad uppsättning $P$ till en kedja $C$ på samma markuppsättning.

Linjär förlängning av en förbeställning

En förbeställning är en reflexiv och transitiv relation. Skillnaden mellan en förbeställning och en partiell beställning är att en förbeställning tillåter att två olika objekt betraktas som "likvärdiga", det vill säga både $x\precsim y$ och $y\precsim x$ håll, medan en partiell ordning tillåter detta endast när $x=y$ . En relation $\precsim ^{*}$ kallas en linjär förlängning av en förorder $\precsim$ om:

1. $\precsim ^{*}$ är en total förbeställning , och
2. För varje $x,y\in X,$ om $x\precsim y$ då $x\precsim ^{*}y$ , och
3. För varje $x,y\in X,$ om $x\prec y$ så $x\prec ^{*}y$ . Här betyder ${\displaystyle x\prec y} "$$x\precsim y$ och inte $y\precsim x$ ".

Skillnaden mellan dessa definitioner finns endast i villkor 3. När förlängningen är en delordning behöver inte villkor 3 anges explicit, eftersom det följer av villkor 2. Bevis : anta att x ≾ $displaystyle x\precsim y}$ och inte $y\precsim x$ . Enligt villkor 2, $x\precsim ^{*}y$ . Med reflexivitet innebär "inte $y\precsim x$ " att $y\neq x$ . Eftersom $\precsim ^{*}$ är en delordning, betyder $x\precsim ^{*}y$ och $y\neq x$ "inte $y\precsim ^{*}x$ ". Därför $x\prec ^{*}y$ .

Men för allmänna förbeställningar behövs villkor 3 för att utesluta triviala förlängningar. Utan detta villkor skulle förordningen med vilken alla element är ekvivalenta ( $y\precsim x$ och $x\precsim y$ för alla par x , y ) vara en förlängning av varje förboka.

Orderförlängningsprincip

Ytterligare information: Szpilrajns förlängningssats

Påståendet att varje delorder kan utökas till en total order kallas orderförlängningsprincipen . Ett bevis med valets axiom publicerades först av Edward Marczewski (Szpilrajin) 1930. Marczewski skriver att satsen tidigare hade bevisats av Stefan Banach , Kazimierz Kuratowski och Alfred Tarski , återigen med hjälp av valets axiom, men att bevisen inte hade publicerats.

Det finns ett analogt uttalande för förbeställningar: varje förbeställning kan utökas till en total förbeställning. Detta påstående bevisades av Hansson.

I modern axiomatisk mängdteori tas ordningsförlängningsprincipen i sig själv som ett axiom, med ontologisk status jämförbar med valets axiom. Ordningsförlängningsprincipen antyds av den booleska primidealsatsen eller motsvarande kompaktitetssats , men den omvända implikationen håller inte.

Att tillämpa ordningsförlängningsprincipen på en partiell ordning där vartannat element är ojämförligt visar att (under denna princip) varje uppsättning kan ordnas linjärt. Detta påstående att varje uppsättning kan ordnas linjärt är känd som ordningsprincipen , OP, och är en försvagning av välordningssatsen . Det finns dock modeller för mängdteori där ordningsprincipen håller medan ordningsförlängningsprincipen inte gör det.

Relaterade resultat

Ordningsförlängningsprincipen är konstruktivt bevisbar för ändliga mängder med topologiska sorteringsalgoritmer , där den partiella ordningen representeras av en riktad acyklisk graf med mängdens element som dess hörn . Flera algoritmer kan hitta en förlängning i linjär tid . Trots att det är lätt att hitta en enda linjär förlängning är problemet med att räkna alla linjära förlängningar av en ändlig partiell ordning #P-komplett ; det kan dock uppskattas av ett randomiserat tillnärmningsschema helt polynom-tid . Bland alla partiella ordrar med ett fast antal element och ett fast antal jämförbara par är de partiella ordrar som har det största antalet linjära förlängningar halvordningar .

Ordningsdimensionen för en partiell ordning är den minsta kardinaliteten för en uppsättning linjära förlängningar vars skärningspunkt är den givna partiella ordningen ; på motsvarande sätt är det det minsta antalet linjära förlängningar som behövs för att säkerställa att varje kritiskt par av den partiella ordningen är omvänd i åtminstone en av förlängningarna.

Antimatroider kan ses som generaliserande partiella beställningar; i denna uppfattning är de strukturer som motsvarar de linjära förlängningarna av en partiell ordning de grundläggande orden för antimatroiden.

Detta område inkluderar också ett av ordningsteorins mest kända öppna problem, 1/3–2/3 gissningen , som säger att i varje finit partiellt ordnad uppsättning $P$ som inte är helt ordnad finns det ett par $(x,y)$ av element i $P$ för vilka de linjära förlängningarna av $P$ där $x<y$ tal mellan 1/3 och 2/3 av det totala antalet linjära förlängningar av $P.$ Ett ekvivalent sätt att ange gissningen är att, om man väljer en linjär förlängning av $P$ likformigt slumpmässigt, så finns det ett par $(x,y)$ som har en sannolikhet mellan 1/3 och 2/3 att beställas som $x<y.$ Men för vissa oändliga partiellt ordnade mängder, med en kanonisk sannolikhet definierad på dess linjära förlängningar som en gräns för sannolikheterna för finita partiella ordningar som täcker den oändliga partiella ordningen, 1/3–2/ 3 gissningar håller inte.

Algebraisk kombinatorik

Att räkna antalet linjära förlängningar av en finit poset är ett vanligt problem inom algebraisk kombinatorik . Detta tal ges av den ledande koefficienten för ordningspolynomet multiplicerat med $|P|!.$

Ung tablå kan betraktas som linjära förlängningar av ett finit ordningsideal i den oändliga poseten $\mathbb {N} \times \mathbb {N} ,$ och de räknas av kroklängdsformeln .