Asymmetrisk relation - Asymmetric relation

Transitiva  binära relationer
Symmetrisk Antisymmetrisk Ansluten Välgrundad Har fogar Har träffar Reflexiv Irreflexiv Asymmetrisk Också känd som: Totalt, Semiconnex Antireflexiv Ekvivalensrelation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Förbeställning (kvasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Delvis beställning ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total förbeställning ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Förbeställning ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Väl kvasi-ordning ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Välordnat ✗ Y Y Y ✗ ✗ Y ✗ ✗ Gitter ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strikt delordning ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Strikt svag ordning ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Strikt total order ✗ ✗ Y ✗ ✗ ✗ ✗ Y Y Symmetrisk Antisymmetrisk Ansluten Välgrundad Har fogar Har träffar Reflexiv Irreflexiv Asymmetrisk Definitioner: ${\ displaystyle \ scriptstyle {{\ text {För alla}} \, a, b \, {\ text {och}} \, S \ neq \ varnothing:}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$ ${\ displaystyle \ scriptstyle {aRb \, {\ text {och}} \, bRa \ Rightarrow a = b}}$ ${\ displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {eller}} \, bRa}}$ ${\ displaystyle \ scriptstyle {\ min S \, {\ text {finns}}}}}$ ${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {existerar}}}}$ ${\ displaystyle \ scriptstyle {a \ kil b \, {\ text {existerar}}}}$ ${\ displaystyle \ scriptstyle {aRa}}$ ${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$
Alla definitioner kräver tyst att den homogena relationen är transitiv : A " " indikerar att kolumnens egenskap krävs av definitionen av radens term (längst till vänster). Till exempel kräver definitionen av en ekvivalensrelation att den är symmetrisk. Noterade här är ytterligare egenskaper som en homogen relation kan uppfylla. ${\ displaystyle R}$${\ displaystyle \ scriptstyle {{\ text {För alla}} \, a, b, c, {\ text {if}} aRb {\ text {och}} bRc {\ text {då}} aRc}.}$ Y

I matematik , en asymmetrisk relation är en binär relation på en uppsättning där för alla om är relaterat till dess är inte relaterad till${\ displaystyle R}$ ${\ displaystyle X}$${\ displaystyle a, b \ i X,}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle a.}$

Formell definition

En binär relation på är någon delmängd av Givet skriva om och bara om vilket betyder att det är stenografi för Uttrycket läses som " är relaterat till av " Den binära relationen kallas asymmetrisk om för alla om är sant då är falskt; det vill säga om då Detta kan skrivas i notationen av första ordningens logik som ${\ displaystyle X}$${\ displaystyle R}$${\ displaystyle X \ times X.}$${\ displaystyle a, b \ i X,}$${\ displaystyle aRb}$${\ displaystyle (a, b) \ i R,}$${\ displaystyle aRb}$${\ displaystyle (a, b) \ i R.}$${\ displaystyle aRb}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle R.}$${\ displaystyle R}$${\ displaystyle a, b \ i X,}$${\ displaystyle aRb}$${\ displaystyle bRa}$${\ displaystyle (a, b) \ i R}$${\ displaystyle (b, a) \ not \ in R.}$

$${\ displaystyle \ forall a, b \ i X: aRb \ innebär \ lnot (bRa).}$$

En logiskt ekvivalent definition är:

för alla minst en av och är falsk ,${\ displaystyle a, b \ i X,}$${\ displaystyle aRb}$${\ displaystyle bRa}$

som i första ordningens logik kan skrivas som:

$${\ displaystyle \ forall a, b \ i X: \ lnot (aRb \ wedge bRa).}$$

Ett exempel på en asymmetrisk relation är " mindre än " -förhållandet mellan reella tal : om då nödvändigtvis inte är mindre än "mindre än eller lika" -relationen å andra sidan, är inte asymmetrisk, eftersom backning till exempel producerar och båda är Sann. Asymmetri är inte samma sak som "inte symmetrisk ": relationen mindre än eller lika är ett exempel på en relation som varken är symmetrisk eller asymmetrisk. Den tomma relationen är den enda relation som är ( vakuum ) både symmetrisk och asymmetrisk. ${\ displaystyle \, <\,}$${\ displaystyle x <y}$${\ displaystyle y}$${\ displaystyle x.}$${\ displaystyle \, \ leq,}$${\ displaystyle x \ leq x}$${\ displaystyle x \ leq x}$

Egenskaper

• En relation är asymmetrisk om och bara om den är både antisymmetrisk och irreflexiv .
• Begränsningar och konversationer av asymmetriska relationer är också asymmetriska. Till exempel är begränsningen av från realen till heltal fortfarande asymmetrisk, och inversen av är också asymmetrisk.${\ displaystyle \, <\,}$${\ displaystyle \,> \,}$${\ displaystyle \, <\,}$
• En transitiv relation är asymmetrisk om och bara om den är irreflexiv: if och transitivitet ger motsägelsefull irreflexivitet.${\ displaystyle aRb}$${\ displaystyle bRa,}$${\ displaystyle aRa,}$
• Som en konsekvens är en relation transitiv och asymmetrisk om och bara om det är en strikt partiell ordning .
• Alla asymmetriska relationer är inte strikta partiella ordningar. Ett exempel på en asymmetrisk icke-transitiv, till och med antitransitiv relation är rockpappersaxens relation: om beats sedan inte slår och om beats och beats sedan inte slår${\ displaystyle X}$${\ displaystyle Y,}$${\ displaystyle Y}$${\ displaystyle X;}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Z,}$${\ displaystyle X}$${\ displaystyle Z.}$
• En asymmetrisk relation behöver inte ha kopplingsegenskapen . Till exempel strikt delmängd relation är asymmetrisk, och ingen av uppsättningarna och är en strikt delmängd av den andra. En relation är kopplad om och endast om dess komplement är asymmetriskt.${\ displaystyle \, \ subsetneq \,}$${\ displaystyle \ {1,2 \}}$${\ displaystyle \ {3,4 \}}$

Se även

• Tarskis axiomatisering av realerna - en del av detta är kravet att över de reella talen ska vara asymmetrisk.${\ displaystyle \, <\,}$

Referenser