Tranzitív reláció

A szaggatott nyíl behúzása szükséges a tranzitivitás eléréséhez

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 „magasabbnak 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.

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 $(\rho \rho \subseteq \rho )$.

Példák

• 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).

Ellenpéldák

• 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).

További példák tranzitív relációkra

• valós számokon a kisebb-egyenlő, a nagyobb-egyenlő, a kisebb, a nagyobb, az egyenlőség
• minden ekvivalenciareláció, úgymint:
  • 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.:
  • pozitív egész számokon az oszthatóság
  • halmazokon a tartalmazási reláció.