Tranzitív reláció

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 ${\displaystyle A}$ halmazon értelmezett ${\displaystyle \sim }$ reláció tranzitív, ha bármely ${\displaystyle a,b,c\in A}$ esetén valahányszor ${\displaystyle a\sim b}$ és ${\displaystyle b\sim c}$ egyszerre teljesül, mindannyiszor ${\displaystyle 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 ${\displaystyle (\rho \rho \subseteq \rho )}$.

Példák

• az egyenesek párhuzamossága (mert ha az ${\displaystyle e}$ egyenes párhuzamos az ${\displaystyle f}$ egyenessel, az ${\displaystyle f}$ egyenes pedig párhuzamos a ${\displaystyle g}$ egyenessel, akkor az ${\displaystyle e}$ egyenes szükségszerűen párhuzamos a ${\displaystyle g}$ egyenessel is),
• a pozitív egész számok között az oszthatóság (mert ha az ${\displaystyle a}$ osztható ${\displaystyle b}$-vel és ${\displaystyle b}$ osztható ${\displaystyle c}$-vel, akkor ${\displaystyle a}$ szükségszerűen osztható ${\displaystyle c}$-vel is),
• a halmazok között a tartalmazási reláció (mert ha az ${\displaystyle A}$ halmaz tartalmazza a ${\displaystyle B}$ halmazt, a ${\displaystyle B}$ halmaz pedig tartalmazza a ${\displaystyle C}$ halmazt, akkor az ${\displaystyle A}$ halmaz mindenképpen tartalmazza a ${\displaystyle C}$ halmazt is),
• 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ó.
• 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 ${\displaystyle e}$ egyenes merőleges az ${\displaystyle f}$ egyenesre, az ${\displaystyle f}$ egyenes pedig merőleges a ${\displaystyle g}$ egyenesre, az ${\displaystyle e}$ egyenes nem lesz merőleges a ${\displaystyle g}$ egyenesre),
• a pozitív egész számok között a relatív prímek reláció (mert ha ${\displaystyle a}$ és ${\displaystyle b}$ relatív prímek és ${\displaystyle b}$ és ${\displaystyle c}$ is relatív prímek, attól ${\displaystyle a}$ és ${\displaystyle c}$ még nem feltétlenül relatív prímek egymással, például ${\displaystyle a=6,b=5,c=4}$ esetén sem)
• a halmazok között a diszjunktság reláció (mert attól, hogy az ${\displaystyle A}$ és a ${\displaystyle B}$ halmaznak nincs közös eleme, valamint a ${\displaystyle B}$ és a ${\displaystyle C}$ halmaznak sincs közös eleme még nem biztos, hogy ${\displaystyle A}$ és ${\displaystyle 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 információk

• Alice és Bob - 12. rész: Alice és Bob rendet tesz
• Alice és Bob - 13. rész: Alice és Bob eladósodik