Transitivt forhold - Transitive relation

I matematikk , et forhold R på et sett X er transitive hvis, for alle elementer en , b , c i X , når R vedrører en til b og b til c , så kan R også angår en til c . Hver delordre og hver ekvivalensrelasjon må være transitive.

Definisjon

Transitive  binære forhold
Symmetrisk Antisymmetrisk Tilkoblet Velbegrunnet Har joins Har møter Refleksiv Irrefleksiv Asymmetrisk Også kjent som: Totalt, Semiconnex Antirefleksiv Ekvivalensforhold ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Forhåndsbestilling (kvasiorder) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Delvis rekkefølge ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Total forhåndsbestilling ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Total bestilling ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Forhåndsbestilling ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Vel-kvasi-bestilling ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ Velordnet ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Gitter ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ Bli med-semilattice ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ Meet-semilattice ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ Strenge delordre ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Streng svak orden ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Streng total orden ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✓ Symmetrisk Antisymmetrisk Tilkoblet Velbegrunnet Har joins Har møter Refleksiv Irrefleksiv Asymmetrisk Definisjoner: ${\ displaystyle \ scriptstyle {{\ text {For all}} \, a, b \, {\ text {and}} \, S \ neq \ varnothing:}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$ ${\ displaystyle \ scriptstyle {aRb \, {\ text {and}} \, bRa \ Rightarrow a = b}}$ ${\ displaystyle \ scriptstyle {a \ neq b \ Høyre pil aRb \, {\ tekst {eller}} \, bRa}}$ ${\ displaystyle \ scriptstyle {\ min S \, {\ text {exist}}}}$ ${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {finnes}}}}$ ${\ displaystyle \ scriptstyle {a \ kile b \, {\ tekst {finnes}}}}$ ${\ displaystyle \ scriptstyle {aRa}}$ ${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$
Alle definisjoner stilltiende krever at den homogene relasjonen er transitiv : En " ✓ " indikerer at kolonneegenskapen er nødvendig i raddefinisjonen. For eksempel krever definisjonen av et ekvivalensforhold at det er symmetrisk. Oppført her er flere egenskaper som en homogen forhold kan tilfredsstille. ${\ displaystyle R}$${\ displaystyle \ scriptstyle {{\ text {For all}} \, a, b, c, {\ text {if}} aRb {\ text {og}} bRc {\ text {deretter}} aRc}.}$

En homogen relasjon R på settet X er en transitiv relasjon hvis,

for alle a , b , c ∈ X , hvis a R b og b R c , så a R c .

Eller når det gjelder førsteordens logikk :

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

hvor en R b er den infiks notasjon for ( en , b ) ∈ R .

Eksempler

Som et ikke -matematisk eksempel er forholdet "er en stamfar til" transitive. For eksempel, hvis Amy er en stamfar til Becky, og Becky er en stamfar til Carrie, så er Amy også en stamfar til Carrie.

På den annen side er "er fødselsforeldre til" ikke et transitive forhold, for hvis Alice er fødselsforelderen til Brenda, og Brenda er fødselsforelderen til Claire, så er ikke Alice fødselsforelderen til Claire. Dessuten er det antitransitivt : Alice kan aldri være Claires fødselsforelder.

"Er større enn", "er minst like stor som", og "er lik" ( likhet ) er transitive relasjoner på forskjellige sett, for eksempel settet med reelle tall eller settet med naturlige tall:

når x > y og y > z , så også x > z

når x ≥ y og y ≥ z , så også x ≥ z

når x = y og y = z , så også x = z .

Flere eksempler på transitive relasjoner:

• "er en delmengde av" (inkludering av sett, en relasjon til sett)
• "deler" ( delbarhet , et forhold til naturlige tall)
• "impliserer" ( implikasjon , symbolisert med "⇒", en relasjon til proposisjoner )

Eksempler på ikke-transitive relasjoner:

• "er etterfølgeren til" (en relasjon til naturlige tall)
• "er medlem av settet" (symbolisert som "∈")
• "er vinkelrett på" (en relasjon på linjer i euklidisk geometri )

Den tomme forhold på ethvert sett er transitive fordi det ikke er noen elementer slik at og , og dermed transitivity tilstand er vacuously sann . En forbindelse R som inneholder bare ett ordnet par er også transitive: hvis ordnet par er av formen for noen bare slike elementer er , og faktisk i dette tilfelle , mens dersom ordnet par er ikke på formen så er det ingen slike elementer og er derfor 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

Lukkingsegenskaper

• Det omvendte (inverse) av et transitive forhold er alltid transitive. For eksempel, å vite at "er en undergruppe av" er transitive og "er et supersett av" er dens motsatte, kan man konkludere med at sistnevnte også er transitive.
• Skjæringspunktet mellom to transitive forhold er alltid transitive. For eksempel, å vite at "ble født før" og "har samme fornavn som" er transitive, kan man konkludere med at "ble født før og også har det samme fornavnet som", er også transitive.
• Foreningen av to transitive relasjoner trenger ikke være transitive. For eksempel er "født før eller har samme fornavn som" ikke et transitive forhold, siden f.eks. Herbert Hoover er i slekt med Franklin D. Roosevelt , som igjen er i slekt med Franklin Pierce , mens Hoover ikke er i slekt med Franklin Pierce .
• Komplementet til en transitive relasjon trenger ikke å være transitive. For eksempel, mens "lik med" er transitive, er "ikke lik" bare transitive på sett med høyst ett element.

Andre eiendommer

Et transitive forhold er asymmetrisk hvis og bare hvis det er irrefleksivt .

En transitiv relasjon trenger ikke å være refleksiv . Når det er det, kalles det en forhåndsbestilling . For eksempel på sett X = {1,2,3}:

• R = {(1,1), (2,2), (3,3), (1,3), (3,2)} er refleksiv, men ikke transitiv, ettersom paret (1,2) er fraværende ,
• R = {(1,1), (2,2), (3,3), (1,3)} er refleksiv så vel som transitiv, så det er en forhåndsbestilling,
• R = {(1,1), (2,2), (3,3)} er refleksiv så vel som transitiv, en annen forhåndsbestilling.

Transitive forlengelser og transitive lukking

La R være en binær relasjon på settet X . Den transitive forlengelse av R , betegnet R ₁ , er den minste binære forhold på X slik at R ₁ inneholder R , og hvis ( en , b ) ∈ R og ( b , c ) ∈ R deretter ( en , c ) ∈ R ₁ . Anta for eksempel at X er et sett med byer, hvorav noen er forbundet med veier. La R være relasjonen på byer der ( A , B ) ∈ R hvis det er en vei direkte knytte byen A og byen B . Denne relasjonen trenger ikke være transitiv. Den transitive forlengelsen av denne relasjonen kan defineres med ( A , C ) ∈ R ₁ hvis du kan reise mellom byene A og C ved å bruke maksimalt to veier.

Dersom en forbindelse er transitive da dens transitive forlengelse er i seg selv, det vil si, hvis R er en transitive forhold deretter R ₁ = R .

Den transitive forlengelse av R ₁ vil bli betegnet med R ₂ , og fortsetter på denne måte, generelt, den transitive forlengelse av R _jeg ville være R _{i + 1} . Den transitive lukning av R , betegnet med R * eller R ^∞ er settet foreningen av R , R ₁ , R ₂ , ....

Den transitive lukkingen av en relasjon er en transitiv relasjon.

Forholdet "er fødselsforeldre til" på et sett med mennesker er ikke et transitive forhold. I biologien oppstår det imidlertid ofte behov for å vurdere fødselsforeldre over et vilkårlig antall generasjoner: forholdet "er en fødselsforfader til" er en transitiv relasjon, og det er den transitive nedleggelsen av forholdet "er fødselsforeldren til".

For eksempel på byer og veier ovenfor, ( A , C ) ∈ R * forutsatt at du kan reise mellom byene A og C ved å bruke et hvilket som helst antall veier.

Relasjonsegenskaper som krever transitt

• Forhåndsbestilling - en refleksiv og transitiv relasjon
• Delordre - en antisymmetrisk forhåndsbestilling
• Total forhåndsbestilling - en tilkoblet (tidligere kalt total) forhåndsbestilling
• Ekvivalensforhold - en symmetrisk forhåndsbestilling
• Streng svak orden - en streng delvis rekkefølge der uforlikelighet er et ekvivalensforhold
• Total bestilling - en tilkoblet (total), antisymmetrisk og transitiv relasjon

Teller transitive relasjoner

Ingen generell formel som teller antall transitive relasjoner på et begrenset sett (sekvens A006905 i OEIS ) er kjent. Imidlertid er det en formel for å finne antall relasjoner som samtidig er refleksive, symmetriske og transitive - med andre ord ekvivalensforhold - (sekvens A000110 i OEIS ), de som er symmetriske og transitive, de som er symmetriske, transitive , og antisymmetrisk, og de som er totale, transitive og antisymmetriske. Pfeiffer har gjort noen fremskritt i denne retningen, og uttrykt forhold til kombinasjoner av disse egenskapene når det gjelder hverandre, men det er fortsatt vanskelig å beregne noen. Se også.

Antall n -element binære relasjoner av forskjellige typer

Elementer	Noen	Transitive	Refleksiv	Forhåndsbestille	Delvis rekkefølge	Total forhåndsbestilling	Total bestilling	Ekvivalensforhold
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	1. 3	4	4	3	3	2	2
3	512	171	64	29	19	1. 3	6	5
4	65 536	3.994	4.096	355	219	75	24	15
n	2 n 2		2 n 2 - n			${\ textstyle \ sum _ {k = 0}^{n} k!}$S ( n , k )	n !	${\ textstyle \ sum _ {k = 0}^{n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Relaterte eiendommer

Den Stein, Saks, Papir spillet er basert på en intransitive og antitransitive forhold " x slår y ".

En relasjon R kalles intransitiv hvis den ikke er transitiv, det vil si hvis xRy og yRz , men ikke xRz , for noen x , y , z . I kontrast kalles en relasjon R antitransitiv hvis xRy og yRz alltid innebærer at xRz ikke holder. For eksempel er forholdet definert av xRy hvis xy er et partall intransitivt, men ikke antitransitivt. Forholdet er definert av XRY hvis x er partall og y er oddetall er både transitive og antitransitive. Forholdet definert av xRy hvis x er etterfølgernummeret til y er både intransitivt og antitransitivt. Uventede eksempler på intransitivitet oppstår i situasjoner som politiske spørsmål eller gruppepreferanser.

Generalisert til stokastiske versjoner ( stokastisk transitivitet ), finner studiet av transitivitet anvendelser i beslutningsteori , psykometrikk og bruksmodeller .

Et kvasitransitivt forhold er en annen generalisering; det kreves bare å være transitive på den ikke-symmetriske delen. Slike relasjoner brukes i sosial valgteori eller mikroøkonomi .

Se også

• Transitiv reduksjon
• Intransitive terninger
• Rasjonell valgteori
• Hypotetisk syllogisme - materialets transitivitet betinget

Merknader

Referanser

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

Eksterne linker

• "Transitivity" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Transitivitet i aksjon på knivsnute