1.3.4. Tranzitivitás

Tranzitív reláció: Egy H halmazon értelmezett ρ binér relációt akkor mondunk tranzitívnak, ha bármely a,b,c H-ra a ρ b és b ρ c-ből következik, hogy a ρ c.

Példák tranzitív relációkra:

  • A pozitív természetes számok halmazán: a kisebb b-nél.
  • A pozitív természetes számok halmazán: a osztója b-nek.
  • A sík valamennyi háromszögének a halmazán: a hasonló b-hez.
  • A sík valamennyi egyenesének a halmazán: a párhuzamos b-vel.
  • Az A részhalmaza B-nek (AB).

Megjegyzés.

A tranzitív reláció gráfreprezentációjában az egymással tranzitív relációban lévő elemekhez tartozó irányított utak hossza legalább 2.