Bestel relatie

Een bestelling betrekking op een set is een binaire relatie in deze set die de elementen vergelijkt samen consequent. Een set met een order relatie is een geordende set. Er wordt ook gezegd dat de relatie gedefinieerd op deze set een bestelling structuur of gewoon een bestelling.

Definities en voorbeelden

Bestel relatie

Een bestelling relatie is een binaire relatie reflexief, transitief en antisymmetrische: E is een set en een binaire relatie op de set als "≤" deze relatie is een order relatie als voor alle x, y en z elementen van E :

  • x ≤ x
  • ⇒ x = y
  • ⇒ x ≤ z

Door de vorm van deze axioma worden ze gecontroleerd door de binaire verhouding ≥, die bepaald wordt door

Bij een bestelling relatie wordt geassocieerd wederkerige bestelling op dezelfde set. Wordt ook geassocieerd met een bestelling relatie ≤, een strikte volgorde relatie aangeduid zogenaamde & lt; dat is de beperking van de orde met betrekking tot paren verschillende elementen:

Een orderelatie in de zin van de bovenstaande definitie wordt soms aangeduid als breed order.

Voor sommige verhoudingen van orde twee elementen van E altijd vergelijkbaar, dat wil zeggen dat voor alle x, y E:

De order relatie die we toen gezegd dat is totaal en dat de ingestelde E is volledig in opdracht van deze relatie. Een bestelling relatie op E wordt gezegd gedeeltelijk te zijn als het niet totaal, en E wordt vervolgens gedeeltelijk besteld. Merk op dat in het Engels, voor de gedeeltelijke orde wijst elke bestelling, die in totaal kunnen zijn. Deze terminologie wordt soms ook gebruikt in het Frans.

Een geordende

Een geordende set is een set met een order relatie. Als een geordende set eindig, kan grafisch worden weergegeven in de vorm van een diagram Hasse, vergelijkbaar met de gebruikelijke weergave van een grafiek papier, die gemakkelijker kunnen veroorloven te werken. Als het oneindig is, kan het een deel van haar Hasse diagram tekenen.

Voorbeelden en tegen-voorbeelden

  • De relatie "kleiner dan of gelijk aan" is een totale bestelling relatie op de set van getallen, de set van rationele of alle van de werkelijke.
  • De relatie is "strikt minder dan", bijvoorbeeld op de set van natuurlijke getallen is geen orde relatie omdat het niet reflexief.
  • De relatie integratie "is een ondergroep van" of "wordt in 'is een gedeeltelijke volgorde van alle delen van een geheel. Als de gegeven set voorbij is, een hele partij is voorbij. Onderstaande figuur toont de Hasse schema van een set 3 items.
  • De deelbaarheid relatie is een gedeeltelijke volgorde op de natuurlijke getallen, maar dit is geen orderelatie op integers omdat het niet antisymmetrische: -1 -1 en 1 verdeelt verdeelt 1. Onderstaande figuur toont het diagram van Hasse deelbaarheid relatie tussen de getallen 0-9.
  • Alle functies in ℝ ℝ, begiftigd met de bestelling relatie f ≤ g als voor elke echte x, f ≤ g, is een gedeeltelijk geordende verzameling oneindigheid. Intuïtief functie is kleiner dan de andere wanneer de curve nog steeds onder de andere curve. We kunnen dit voorbeeld om de functies van een set X generaliseren in een geordende set P.
  • De groep segmenten van een gegeven set gedeeltelijk bestellen met het orderelatie door de verfijning van scores: per definitie een scheidingswand dunner dan de andere wanneer splitst de andere delen van kleinere delen.
  • Gegeven twee bestelde sets E en F, zijn er ten minste twee natuurlijke manieren om een ​​ordening definieert op E × F.
    • De volgorde product: ≤ als en slechts als x ≤ x en y ≤ y '.
    • De lexicografische orde ≤ IFF] .Als het initiële bestellingen totaal, de lexicografische volgorde is totaal. Bijv. ≤ relatie gedefinieerd op alle Parx complexe ≤ y als en slechts als Re & lt; Re of Re = Re en Im ≤ IMEST een totale bestelling relatie. Het is echter niet verenigbaar met de carrosserie van het gehele complex.
  • Kan worden verstrekt ℝ alle n variabelen van de veeltermen van een gedeeltelijke orde relatie. We beginnen met het vergelijken van de eenheid monomen in n variabelen via de lexicografische orde veroorzaakte. Twee polynomen P en Q worden vergeleken zeggen dat P strikt kleiner dan Q indien nul monomial P strikt kleiner dan nul monomial van Q. Dit orderelatie op polynomen is gedeeltelijk.
  • Naar tevredenheid kunnen we niet een te bestellen op de cirkel te definiëren zou betekenen "wordt geplaatst vóór". Bijvoorbeeld, op alle punten van de cirkel-eenheid, de relatie tussen twee punten M en N gedefinieerd door "de belangrijkste maatregel van de hoek, [ON))" is positief of nul is niet een order relatie want het is niet transitief.
  • De relatie is "de vader" van een groep mensen is niet een order relatie omdat het niet transitief.

Verwante begrippen

Toenemende toepassingen

Wanneer en twee bestelde sets, wordt een F E F in genoemde verhogen als het behoud van de order, bij afnemende inverse daarvan, dat wil zeggen:

Toen ze houdt strikte volgorde is strikt toe: voor alle x en y van E x & lt; E y ⇒ f & lt; F f,

en strikt afneemt wanneer het tegenovergestelde: voor alle x en y van E x & lt; E y ⇒ f & gt; F f.

Merk op dat een groeiend één mapping noodzakelijkerwijs strikt toe.

Morfismen van orders groeien toepassingen.

Een monotone of monotone brede toepassing is het verhogen of verlagen toepassing.

Grootste element en maximaal element

In een geordende set E, is het niet per se aanwezig grootste element. Als E is voltooid, zal het een maximale element bevatten. Wanneer E een oneindige inductief samenstel, Zorn lemma garandeert nog dat er een maximaal element.

Strikte volgorde relatie

We hebben gezien dat een order relatie "≤" op een gegeven set, we natuurlijk verbonden relatie "& lt; "Zogenaamde strikte volgorde bepaald op dezelfde set, en verkregen door het beperken van het aan koppels van verschillende elementen. Het is mogelijk om direct axiomatiseren het begrip strikte volgorde. Dit kan zelfs natuurlijker in sommige gevallen.

Een strikte volgorde relatie is een reflexieve binaire relatie en transitief: een set en E is een binaire relatie op de set aangeduid & lt;, deze relatie is een strikte volgorde relatie als en slechts als voor alle x, y en z E elementen:

  • niet
  • ⇒ x & lt; z

Onmiddellijk af te leiden we uit deze twee eigenschappen als een strikte volgorde relatie is antisymmetrisch. In feite strikt orderelatie is antisymmetrische in een sterkere zin dat een groot orderelatie, dat wil zeggen dat voor alle x en y van de ondersteuningsassemblage E:

  • x & lt; ⇒ er niet

Maar voor een reflexieve relatie, zoals strikte orders, deze eigenschap is gelijk aan de antisymmetrie pand set voor grote orders. Dus er is geen kwaad in het praten antisymmetrie in beide gevallen.

Evenals een order relatie gecombineerd we een strikte volgorde relatie, een strikte volgorde relatie of "& lt; "Een natuurlijk associeert een grote order relatie of" ≤ ", gedefinieerd door:

Kies een of de andere van axiomatizations niet uit zichzelf. In beide gevallen hebben we een grote order en een strikte volgorde geassocieerd gedefinieerd. Inderdaad is het gemakkelijk om, via dezelfde eigenschappen als:

  • De strikte volgorde relatie geassocieerd met een brede orde relatie doet voldoen aan de strikte volgorde axioma's.
  • De brede orde relatie in verband met een strikte volgorde relatie goed controleert de brede orde axioma's.
  • Er zijn veel symmetrie: krijgen een strikte volgorde relatie "& lt; "En een grote order relatie" ≤ "," & lt; "Is betrokken bij" ≤ "als en slechts als" ≤ "wordt geassocieerd met" & lt; ".

Voor een strikte volgorde, allemaal op deze manier:

en zei toen dat het een totale strikte volgorde relatie. Er is geen verwarring met de gehele voorgaande zin relatie, omdat een streng orderelatie die reflexieve, kan niet volledig in de zin dat een grote orde.

Voor een totaal strikte volgorde, de drie mogelijkheden x & lt; y, x = y en y & lt; x zijn exclusief, en soms spreken we, na Cantor van driedeling pand.

Ontkenning van een order relatie

De ontkenning van een binaire relatie gedefinieerd op een set is de grafiek van de relatie complementair is aan die van de in. Opmerking Op. Met andere woorden, twee leden verbonden door als en alleen als ze niet in.

Om te zeggen dat er een bestelling is totaal, dat zijn ontkenning is het omgekeerde strikte volgorde. Dat wil zeggen dat er gelijkwaardigheid voor een bestelling naar:

  • is totaal;

Door nadelen als er twee afzonderlijke elementen niet vergelijkbaar met een order, kan de negatie geen order, omdat het niet antisymmetrische. De ontkenning van een niet-lineaire volgorde is nooit een bevel.

Bijvoorbeeld, de negatie van de opneming ⊄ op alle delen van een set van ten minste twee elementen geen order, want als a ≠ b, we altijd {a} {b} ≠ maar met {a} en {b} ⊄ {b} {a} ⊄.

Dual orde

De dubbele van een geordende set P = is de geordende set P = als ≤ is een order relatie op E, dan is de relatie ≥ gedefinieerd op E

is een goed.

Preorder

Een preorder is een reflexieve en transitieve binaire relatie.

Het kan worden beschouwd als een orderelatie waarin zou niet triviaal cycli toe. Voeg de toestand antisymmetrie onmogelijk maakt de aanwezigheid van deze niet-triviale cycli.

Elke quotiënt van een preorder door de equivalentie relatie die het genereert is een bevel.

Extra Eigenschappen

Verenigbaarheid

Een bestelling van een set met een interne samenstelling wet verenigbaar is met de wet als en slechts als, want alles was

  • De gebruikelijke volgorde op de set van echte ondersteunt de toevoeging, maar niet vermenigvuldigen. Dit is eigenlijk de vermenigvuldiging met een negatieve reële die onverenigbaar is met de bestelling.
  • De gebruikelijke volgorde relatie op de set van positieve reële is compatibel met optellen en vermenigvuldigen.
  • De set van complexe getallen is niet sorteerbaar opdracht relatie verenigbaar is met het optellen en vermenigvuldigen operaties.

Een groep voorzien van een ordening in overeenstemming met haar interne wetgeving wordt een geordende groep.

Is een totaal bestelde commutatieve groep neutraal. Een positief element is als. Wordt gezegd Archimedische zijn indien voor elk paar positieve elementen, is er een integer zodat.

Goed geordende

Een geordende set wordt gezegd goed geordende als elke niet-lege deelverzameling van deze set heeft een minimaal element.

Traliewerk

Een reeks heet rooster indien besteld en dat elk paar elementen heeft een bovengrens en een ondergrens. Een bovengrens wordt meer element dat elk paar elementen elk ander element van dezelfde eigenschap groter is dan de terminal. Met andere woorden, een aansluiting de kleinste Enhancer. Als het rooster is een gerichte graaf, betekent dit dat elk paar knooppunten een gemeenschappelijke voorouder en nakomeling.

Toepassingen

Om topologie

Een geordende set kan worden voorzien van meerdere topologie van de volgorde: de orde topologie, topologie wordt onmiddellijk de topologie van de order gelaten.

Links naar complexen simpliciale

Een belangrijke klasse van simpliciale complexen is van eindige besteld sets. Het definieert een eindige geordende set P complexe orde van D is alle kanalen van orde P. Het complex is triviaal een simpliciale complex.

De studie van de geordende set zelf geeft informatie over de orde complex en derhalve interessant om simplicial complex te bestuderen zoals een seriële complex geordende set.