Transitiv relation - Transitive relation

I matematik , en relation $R$ på en uppsättning $X$ är transitiv om, för alla element $a$ , $b$ , $c$ i $X$ , närhelst $R$ avser $en$ till $b$ och $b$ till $c$ , då $R$ avser också $en$ till $c$ . Varje delordning såväl som varje ekvivalensrelation måste vara transitiv.

Definition

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	✓	✗	✗	✗	✗	✗	✓	✗	✗
Förbeställning (kvasiorder)	✗	✗	✗	✗	✗	✗	✓	✗	✗
Delvis beställning	✗	✓	✗	✗	✗	✗	✓	✗	✗
Total förbeställning	✗	✗	✓	✗	✗	✗	✓	✗	✗
Total order	✗	✓	✓	✗	✗	✗	✓	✗	✗
Förbeställning	✗	✗	✓	✓	✗	✗	✓	✗	✗
Väl kvasi-ordning	✗	✗	✗	✓	✗	✗	✓	✗	✗
Välordnat	✗	✓	✓	✓	✗	✗	✓	✗	✗
Gitter	✗	✓	✗	✗	✓	✓	✓	✗	✗
Join-semilattice	✗	✓	✗	✗	✓	✗	✓	✗	✗
Meet-semilattice	✗	✓	✗	✗	✗	✓	✓	✗	✗


Strikt delordning	✗	✗	✗	✗	✗	✗	✗	✓	✓
Strikt svag ordning	✗	✗	✗	✗	✗	✗	✗	✓	✓
Strikt total order	✗	✗	✓	✗	✗	✗	✗	✓	✓
	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 kolumnegenskapen krävs i raddefinitionen. 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}.}

En homogen relation $R$ på uppsättningen $X$ är en transitiv relation om,

för alla

a, b, c \in X

, om

a R b

och

b R c

, då

a R c

.

Eller när det gäller första ordningens logik :

{\ displaystyle \ forall a, b, c \ in X: (aRb \ wedge bRc) \ Rightarrow aRc,}

där $R ''$ är infix notation för $(a, b) \in R$ .

Exempel

Som ett icke -matematiskt exempel är förhållandet "är en förfader till" transitivt. Till exempel, om Amy är en förfader till Becky, och Becky är en förfader till Carrie, är Amy också en förfader till Carrie.

Å andra sidan är "är föräldern till" inte en transitiv relation, för om Alice är Brendas förälder och Brenda är Claires födelseförälder, så är Alice inte Claires födelseförälder. Dessutom är det antitransitivt : Alice kan aldrig vara förälder till Claire.

"Är större än", "är minst lika stor som", och "är lika med" ( jämlikhet ) är transitiva relationer på olika uppsättningar, till exempel uppsättningen av reella tal eller uppsättningen naturliga tal:

när x > y och y > z , då också x > z

när x ≥ y och y ≥ z , då också x ≥ z

när x = y och y = z , då också x = z .

Fler exempel på transitiva relationer:

"är en delmängd av" (uppsättning inkludering, en relation till uppsättningar)
"delar" ( delbarhet , en relation till naturliga tal)
"implicerar" ( implikation , symboliserad med "⇒", en relation till propositioner )

Exempel på icke-transitiva relationer:

"är efterträdaren till" (en relation till naturliga tal)
"är medlem i uppsättningen" (symboliseras som "∈")
"är vinkelrätt mot" (en relation på linjer i euklidisk geometri )

Den tomma relation på en uppsättning är transitiv eftersom det inte finns några element så att och och därmed transitivity villkoret är vacuously sant . En relation $R$ innehåller endast en ordnat par är också transitiv: om ordnat par är av formen för en del de enda sådana element är , och även i detta fall , medan om ordnat par är inte av formen då finns det inga sådana element och är därför vakuumtransitiv. ${\ displaystyle X}$ ${\ displaystyle a, b, c \ i X}$ ${\ displaystyle aRb}$ ${\ displaystyle bRc}$ ${\ displaystyle (x, x)}$ ${\ displaystyle x \ i X}$ ${\ displaystyle a, b, c \ i X}$ ${\ displaystyle a = b = c = x}$ ${\ displaystyle aRc}$ ${\ displaystyle (x, x)}$ ${\ displaystyle a, b, c \ i X}$ ${\ displaystyle R}$

Egenskaper

Stängningsegenskaper

Det omvända (omvända) av en transitiv relation är alltid transitiv. Till exempel, att veta att "är en delmängd av" är transitivt och "är en superset av" är dess motsats, man kan dra slutsatsen att den senare också är transitiv.
Skärningspunkten mellan två transitiva relationer är alltid transitiv. Till exempel, att veta att "föddes före" och "har samma förnamn som" är transitiva, kan man dra slutsatsen att "föddes före och också har samma förnamn som" också är transitivt.
Föreningen mellan två transitiva relationer behöver inte vara transitiv. Till exempel, "föddes före eller har samma förnamn som" är inte en transitiv relation, eftersom t.ex. Herbert Hoover är släkt med Franklin D. Roosevelt , som i sin tur är relaterad till Franklin Pierce , medan Hoover inte är släkt med Franklin Pierce .
Komplementet till en transitiv relation behöver inte vara transitiv. Till exempel, medan "lika med" är transitivt, är "inte lika med" endast transitivt på uppsättningar med högst ett element.

Övriga fastigheter

En transitiv relation är asymmetrisk om och bara om den är irreflexiv .

En transitiv relation behöver inte vara reflexiv . När det är det kallas det en förbeställning . Till exempel på uppsättning X = {1,2,3}:

R = {(1,1), (2,2), (3,3), (1,3), (3,2)} är reflexivt, men inte transitivt, eftersom paret (1,2) är frånvarande ,
R = {(1,1), (2,2), (3,3), (1,3)} är såväl reflexiv som transitiv, så det är en förbeställning,
R = {(1,1), (2,2), (3,3)} är reflexiv såväl som transitiv, en annan förbeställning.

Transitiva förlängningar och transitiva stängningar

Låt $R$ vara en binär relation på inspelningsplatsen $X$ . Den transitiva förlängning av $R$ , betecknad $R 1$ , är den minsta binära förhållande på $X$ sådan att $R 1$ innehåller $R$ , och om $(a, b) \in R$ och $(b, c) \in R$ sedan $(a, c) \in R 1$ . Anta till exempel att $X$ är en uppsättning städer, varav några är anslutna med vägar. Låt $R$ vara relationen på städer där $(A, B) \in R$ , om det finns en väg direkt länka stad $A$ och stad $B$ . Denna relation behöver inte vara transitiv. Den transitiva förlängningen av denna relation kan definieras med $(A, C) \in R 1$ om du kan resa mellan städerna $A$ och $C$ med högst två vägar.

Om en relation är transitiv alltså dess transitiva förlängning är i sig, det vill säga, om $R$ är en transitiv relation sedan $R 1 = R$ .

Den transitiva förlängning av $R 1$ skulle betecknas med $R 2$ , och fortsatt på detta sätt, i allmänhet, den transitiva förlängning av $R i$ skulle vara $R i + 1$ . Den transitiva stängningen av $R$ , betecknad med $R *$ eller $R \infty$ är uppsättningen union av $R$ , $R 1$ , $R 2$ , ....

Den transitiva stängningen av en relation är en transitiv relation.

Relationen "är förälder för födseln" på en uppsättning människor är inte en transitiv relation. Men inom biologin uppstår ofta behovet av att överväga födelseföräldraskap över ett godtyckligt antal generationer: förhållandet "är en födelsefader till" är en transitiv relation och det är den transitiva stängningen av relationen "är födelseföräldern till".

För exemplet med städer och vägar ovan, $(A, C) \in R *$ förutsatt att du kan resa mellan städer $A$ och $C$ med valfritt antal vägar.

Relationsegenskaper som kräver transitivitet

Förbeställning - en reflexiv och transitiv relation
Delvis ordning - en antisymmetrisk förbeställning
Total förbeställning - en ansluten (tidigare kallad total) förbeställning
Ekvivalensrelation - en symmetrisk förbeställning
Strikt svag ordning - en strikt partiell ordning där ojämförlighet är ett ekvivalensförhållande
Total beställning - en ansluten (total), antisymmetrisk och transitiv relation

Räknar transitiva relationer

Ingen allmän formel som räknar antalet transitiva relationer på en ändlig uppsättning (sekvens A006905 i OEIS ) är känd. Det finns dock en formel för att hitta antalet relationer som samtidigt är reflexiva, symmetriska och transitiva - med andra ord ekvivalensrelationer - (sekvens A000110 i OEIS ), de som är symmetriska och transitiva, de som är symmetriska, transitiva och antisymmetriska och de som är totala, transitiva och antisymmetriska. Pfeiffer har gjort vissa framsteg i denna riktning och uttryckt relationer med kombinationer av dessa egenskaper i termer av varandra, men det är fortfarande svårt att beräkna någon. Se även.

Antal n -element binära relationer av olika typer
Element	Några	Transitiv	Reflexiv	Förboka	Delvis beställning	Total förbeställning	Total order	Ekvivalensrelation
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3 994	4 096	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ² - n}			${\ textstil \ sum _ {k = 0}^{n} k!}$	n !	${\ textstil \ sum _ {k = 0}^{n}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Relaterade fastigheter

Den Sten, sax, påse spel är baserat på en intransitiv och antitransitive relation " x slår y ".

En relation R kallas intransitiv om den inte är transitiv, det vill säga om xRy och yRz , men inte xRz , för vissa x , y , z . Däremot kallas en relation R antitransitiv om xRy och yRz alltid innebär att xRz inte håller. Till exempel är den relation som definieras av xRy om xy är ett jämnt tal intransitiv, men inte antitransitiv. Förhållandet som definieras av xRy om x är jämnt och y är udda är både transitivt och antitransitivt. Förhållandet som definieras av xRy om x är efterföljarens antal y är både intransitivt och antitransitivt. Oväntade exempel på intransitivitet uppstår i situationer som politiska frågor eller grupppreferenser.

Generaliserat till stokastiska versioner ( stokastisk transitivitet ) hittar studien av transitivitet tillämpningar av beslutsteori , psykometrik och användningsmodeller .

En kvasitransitiv relation är en annan generalisering; det krävs endast att vara transitiv på sin icke-symmetriska del. Sådana relationer används i sociala valteori eller mikroekonomi .

Se även

Transitiv minskning
Intransitiva tärningar
Rationell valteori
Hypotetisk syllogism - materialets transitivitet villkorligt

Anteckningar

Referenser

Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics (3rd ed.), Addison-Wesley, ISBN 0-201-19912-2
Liu, CL (1985), Elements of Discrete Mathematics , McGraw-Hill, ISBN 0-07-038133-X
Gunther Schmidt , 2010. Relationsmatematik . Cambridge University Press, ISBN 978-0-521-76268-7 .
Smith, Douglas; Eggen, Maurice; St.Andre, Richard (2006), A Transition to Advanced Mathematics (6: e upplagan), Brooks/Cole, ISBN 978-0-534-39900-9

externa länkar

"Transitivity" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
Transitivity in Action vid knivhugg

Languages

In other projects