Přechodný vztah - Transitive relation

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Přechodný vztah“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Říjen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, a homogenní vztah R přes soubor X je tranzitivní pokud pro všechny prvky A, b, C v Xkdykoli R se týká A na b a b na C, pak R také souvisí A na C. Každý částečná objednávka stejně jako každý vztah ekvivalence musí být tranzitivní.

Definice

Homogenní vztah R na scéně X je tranzitivní vztah li,^[1]

pro všechny A, b, C ∈ X, pokud a R b a b R c, pak a R c.

Nebo z hlediska logika prvního řádu:

${ displaystyle forall a, b, c v X: (aRb klín bRc) Rightarrow aRc,}$

kde a R b je infixová notace pro (A, b) ∈ R.

Příklady

Jako nematematický příklad je vztah „je předkem“ tranzitivní. Například pokud je Amy předkem Becky a Becky je předkem Carrie, pak je Amy také předkem Carrie.

Na druhou stranu, „je rodným rodičem“ není přechodný vztah, protože pokud je Alice rodícím rodičem Brendy a Brenda je rodícím rodičem Claire, pak Alice není rodícím rodičem Claire. A co víc, to je antitransitivní: Alice může nikdy být rodičem Claire.

„Is greater than“, „is at least as great as“, and „is equal to“ (rovnost ) jsou tranzitivní vztahy na různých množinách, například množině reálných čísel nebo množině přirozených čísel:

kdykoli X > y a y > z, pak také X > z

kdykoli X ≥ y a y ≥ z, pak také X ≥ z

kdykoli X = y a y = z, pak také X = z.

Další příklady tranzitivních vztahů:

• "je podmnožina z „(zařazení souboru, vztah k souborům)
• „rozdělí“ (dělitelnost, vztah k přirozeným číslům)
• „implikuje“ (implikace, symbolizovaný „⇒“, relace zapnuta propozice )

Příklady netranzitivních vztahů:

• "je nástupce z „(vztah k přirozeným číslům)
• „je členem množiny“ (symbolizováno jako „∈“)^[2]
• "je kolmý (vztah na řádcích v Euklidovská geometrie )

The prázdný vztah na libovolné sadě ${ displaystyle X}$ je tranzitivní^[3][4] protože tam nejsou žádné prvky ${ displaystyle a, b, c v X}$ takhle ${ displaystyle aRb}$ a ${ displaystyle bRc}$, a proto je podmínka přechodnosti prázdně pravda. Vztah R obsahující pouze jeden objednaný pár je také tranzitivní: pokud je objednaný pár ve tvaru ${ displaystyle (x, x)}$ pro některé ${ displaystyle x v X}$ jediné takové prvky ${ displaystyle a, b, c v X}$ jsou ${ displaystyle a = b = c = x}$, a skutečně v tomto případě ${ displaystyle aRc}$, zatímco pokud objednaný pár nemá formu ${ displaystyle (x, x)}$ pak takové prvky neexistují ${ displaystyle a, b, c v X}$ a tudíž ${ displaystyle R}$ je vakuově tranzitivní.

Vlastnosti

Vlastnosti uzavření

• The inverzní (konverzace) přechodného vztahu je vždy přechodný. Například vědět, že „je podmnožina „je tranzitivní a“ je nadmnožina „je jeho inverzní, lze usoudit, že i druhý je tranzitivní.
• Průsečík dvou přechodných vztahů je vždy přechodný. Například když víme, že „narodil se dříve“ a „má stejné křestní jméno jako“, jsou tranzitivní, lze usoudit, že „také se narodil dříve a má stejné křestní jméno jako“ je také tranzitivní.
• Spojení dvou tranzitivních vztahů nemusí být tranzitivní. Například „narodil se dříve nebo má stejné křestní jméno jako“ není přechodný vztah, protože např. Herbert Hoover je spojen s Franklin D. Roosevelt, což zase souvisí s Franklin Pierce, zatímco Hoover nesouvisí s Franklinem Piercem.
• Doplněk přechodného vztahu nemusí být přechodný. Například zatímco „rovná se“ je přechodná, „nerovná se“ je pouze přechodná na množinách s nejvýše jedním prvkem.

Další vlastnosti

Přechodný vztah je asymetrický právě když je nereagující.^[5]

Přechodný vztah nemusí být reflexní. Pokud ano, nazývá se to a předobjednávka. Například na place X = {1,2,3}:

• R = {(1,1), (2,2), (3,3), (1,3), (3,2)} je reflexivní, ale nikoli tranzitivní, protože dvojice (1,2) chybí,
• R = {(1,1), (2,2), (3,3), (1,3)} je reflexivní i tranzitivní, takže se jedná o předobjednávku,
• R = {(1,1), (2,2), (3,3)} je reflexivní i tranzitivní, další předobjednávka.

Přechodná rozšíření a přechodné uzavření

Nechat R být binární relací na place X. The přechodné rozšíření z R, označeno R₁, je nejmenší binární relace na X takhle R₁ obsahuje R, a pokud (A, b) ∈ R a (b, C) ∈ R pak (A, C) ∈ R₁.^[6] Předpokládejme například X je soubor měst, z nichž některá jsou spojena silnicemi. Nechat R být vztahem k městům, kde (A, B) ∈ R pokud existuje silnice přímo spojující město A a město B. Tento vztah nemusí být tranzitivní. Přechodné rozšíření tohoto vztahu lze definovat pomocí (A, C) ∈ R₁ pokud můžete cestovat mezi městy A a C pomocí maximálně dvou silnic.

Pokud je vztah tranzitivní, pak je jeho přechodné rozšíření samo o sobě, tj. Pokud R je tedy přechodný vztah R₁ = R.

Přechodné rozšíření R₁ by byl označen R₂a tímto způsobem obecně pokračovat v přechodném rozšíření R_i bylo by R_{i + 1}. The přechodné uzavření z R, označeno R* nebo R^∞ je množinová unie R, R₁, R₂, ... .^[7]

Tranzitivní uzavření relace je tranzitivní relace.^[7]

Vztah „je rodičem narození“ na množině lidí není přechodný vztah. V biologii však často vyvstává potřeba uvažovat o rodném rodičovství po libovolný počet generací: vztah „je předkem narození“ je přechodný vztah a je to přechodné uzavření vztahu „je rodným rodičem“.

Pro příklad měst a silnic výše (A, C) ∈ R* za předpokladu, že můžete cestovat mezi městy A a C pomocí libovolného počtu silnic.

Relační vlastnosti, které vyžadují tranzitivitu

• Předobjednávka - a reflexní tranzitivní vztah
• Částečná objednávka - an antisymetrický předobjednávka
• Celková předobjednávka - a celkový předobjednávka
• Vztah ekvivalence - a symetrický předobjednávka
• Přísné slabé objednávání - přísné částečné pořadí, ve kterém je nesrovnatelnost vztahem rovnocennosti
• Celkové objednání - a celkový, antisymetrický tranzitivní vztah

Počítání tranzitivních vztahů

Žádný obecný vzorec, který počítá počet tranzitivních vztahů na konečné množině (sekvence A006905 v OEIS ) je známo.^[8] Existuje však vzorec pro hledání počtu vztahů, které jsou současně reflexivní, symetrické a tranzitivní - jinými slovy ekvivalenční vztahy - (sekvence A000110 v OEIS ), ty, které jsou symetrické a přechodné, ty, které jsou symetrické, přechodné a antisymetrické, a ty, které jsou úplné, přechodné a antisymetrické. Pfeiffer^[9] dosáhl v tomto směru určitého pokroku, když vyjádřil vztahy s kombinacemi těchto vlastností, pokud jde o sebe navzájem, ale přesto je výpočet kterékoli z nich obtížný. Viz také.^[10]

Související vlastnosti

The Kámen, nůžky, papír hra je založena na nepřechodném a antitransitivním vztahu "X bije y".

Vztah R je nazýván intranzitivní pokud to není tranzitivní, tedy pokud xRy a yRz, ale ne xRz, pro některé X, y, zNaproti tomu vztah R je nazýván antitransitivní -li xRy a yRz to vždy znamená xRz Například vztah definovaný pomocí xRy -li xy je sudé číslo je nepřechodná,^[11] ale ne antitransitivní.^[12] Vztah definovaný xRy -li X je sudé a y je zvláštní je tranzitivní i antitransitivní.^[13] Vztah definovaný xRy -li X je nástupce počet y je nepřechodná^[14] a antitransitivní.^[15] Neočekávané příklady nepřechodnosti vznikají v situacích, jako jsou politické otázky nebo skupinové preference.^[16]

Zobecněno na stochastické verze (stochastická tranzitivita ), studie tranzitivity najde aplikace v teorie rozhodování, psychometrie a užitné vzory.^[17]

A kvazitranzitivní vztah je další zobecnění; je nutné, aby byl tranzitivní pouze na jeho nesymetrické části. Takové vztahy se používají v teorie sociální volby nebo mikroekonomie.^[18]

Viz také

• Přechodná redukce
• Nepřenosné kostky
• Teorie racionální volby
• Hypotetický úsudek - přechodnost materiálu podmíněná

Poznámky

Reference

• Grimaldi, Ralph P. (1994), Diskrétní a kombinatorická matematika (3. vyd.), Addison-Wesley, ISBN  0-201-19912-2
• Liu, C.L. (1985), Základy diskrétní matematikyMcGraw-Hill, ISBN  0-07-038133-X
• Gunther Schmidt, 2010. Relační matematika. Cambridge University Press, ISBN  978-0-521-76268-7.
• Smith, Douglas; Eggen, Maurice; St.Andre, Richard (2006), Přechod k pokročilé matematice (6. vydání), Brooks / Cole, ISBN  978-0-534-39900-9

externí odkazy

• "Přechodnost", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Transitivita v akci na cut-the-uzel