Tranzitív reláció

A Wikipédiából, a szabad lexikonból.

Egy homogén kétváltozós relációt akkor nevezünk tranzitívnak, ha az elempárok azon tulajdonsága, hogy egymással relációban állnak, "láncszerűen" tovább adódik, mint például a testmagasság esetében a "magasabbank lenni" relációnál: ha én magasabb vagyok az apámnál, az apám pedig magasabb az anyámnál, akkor én magasabb vagyok az anyámnál.

[szerkesztés] Néhány példa és ellenpélda

  • az egyenesek párhuzamossága (mert ha az e egyenes párhuzamos az f egyenessel, az f egyenes pedig párhuzamos a g egyenessel, akkor az e egyenes szükségszerűen párhuzamos a g egyenessel is),
  • a pozitív egész számok között az oszthatóság (mert ha az a osztható b-vel és b osztható c-vel, akkor a szükségszerűen osztható c-vel is),
  • a halmazok között a tartalmazási reláció (mert ha az A halmaz tartalmazza a B halmazt, a B halmaz pedig tartalmazza a C halmazt, akkor az A halmaz mindenképpen tartalmazza a C halmazt is),
  • az emberek között a "fölmenő rokona" reláció (mert ha egy személy fölmenő rokona egy másiknak, ez a másik pedig fölmenő rokona egy harmadiknak, akkor az első szükségszerűen fölmenő rokona a harmadiknak is).

Nem ilyen

  • az egyenesek merőlegessége (mert attól, hogy az e egyenes merőleges az f egyenesre, az f egyenes pedig merőleges a g egyenesre, az e egyenes nem lesz merőleges a g egyenesre),
  • a pozitív egész számok között a relatív prímek reláció (mert ha a és b relatív prímek és b és c is relatív prímek, attól a és c még nem feltétlenül relatív prímek egymással, például a = 6,b = 5,c = 4 esetén sem)
  • a halmazok között a diszjunktság reláció (mert attól, hogy az A és a B halmaznak nincs közös eleme, valamint a B és a C halmaznak sincs közös eleme még nem biztos, hogy A és C halmaznak sincs közös eleme),
  • az emberek között az "ismerik egymást" reláció (mert ha egy ember ismer egy másikat, s ez a másik ismer egy harmadikat, attól az első még nem fogja szükségképpen ismerni a harmadikat).

[szerkesztés] A precíz matematikai definíció:

Az A halmazon értelmezett \sim reláció tranzitív, ha bármely a, b, c\in A esetén valahányszor a\sim b és b\sim c egyszerre teljesül, mindannyiszor a\sim c is teljesül.

Halmazelméletileg ez azt jelenti, hogy a reláció négyzete (önmagával való szorzata, kompozíciója) része önmagának (ρoρ⊆ρ).

[szerkesztés] További példák

Tranzitív relációk

  • valós számokon a kisebb-egyenlő, a nagyobb-egyenlő, a kisebb, a nagyobb, az egyenlőség
  • minden ekvivalenciareláció, úgysmint:
    • halmazokon az ekvivalencia, azaz számosságazonosság;
    • egész számokon az azonos paritás, vagy általánosabban az azonos maradékosztályba tartozás,
    • egy sík vagy a tér egyenesein a párhuzamosság
    • a tér síkjain a párhuzamosság
    • logikai formulák halmazán az logikai ekvivalencia
  • Minden (elő)rendezési és rendezési reláció, pl.: