Halmazok

Relációk és azok tulajdonságai

Kulcsszavak: reláció, refelxiv, tranzitív, szimetrikus, aszimetrikus, ekvivalencia, részbenrendezés, dichotóm, rendezés

Definíció

A2=A×A=a,b:aA, bA
ρA2

Rendezett párok halmazát, amelyet az AxA Descartes-négyzet részhalmazaként kapunk ρ relációknak nevezzük.

Példa:

A=1,3,6
AxA=1,1,1,3,1,6,3,1,3,3,3,6,6,1,6,3,6,6
ρ={1,1,1,3,1,6,3,3,3,6,6,6} | ρA2,

.
A ρ ebben az esetben a kissebb vagy egyenlő relációnak felel meg: (1≤1), (1≤3), (1≤6), (3≤3), (3≤6), (6≤6).

Relációk tulajdonságai

Reflexív

(aA): aρa

IRÁNYÍTOTT GRÁFKÉNT ÁBRÁZOLVA:  a gráf minden pontjában van hurokél.

Példa:ρ reflexív, mert az A halmaz minden tagjára érvényes hogy 11,33,66

Szimetrikus

(a, bA): aρbbρa

IRÁNYÍTOTT GRÁFKÉNT ÁBRÁZOLVA: ha a gráf minden éle kétirányú.

Példa:ρ nem szimetrikus, mert  például abból hogy 3 ≤ 6 [azaz (3, 6) ∈ ρ], nem következik, hogy 6 ≤ 3 [azaz (6, 3) ∈ ρ].

Tranzitív

(a, b,cA): aρbbρcaρc

IRÁNYÍTOTT GRÁFKÉNT ÁBRÁZOLVA: ha létezik út két pont között, akkor létezik 1 hosszú út is közöttükl.

Példa:ρ  tranzitív, mert például  ha 1 ≤ 3  és 3 ≤ 6 akkor ebből az következik hogy 1 ≤ 6.

Antiszimetrikus

(a, bA): aρbbρa

IRÁNYÍTOTT GRÁFKÉNT ÁBRÁZOLVA: ha bármely két különböző pont között 0 vagy 1 irányban megy él.

Példa:ρ antiszimetrikus, mert minden szám csak önmagánál kisebb vagy egyenlő.

Relációk tipusai

  • Ekvivalenciareláció: reflexív, szimetrikus és tranzitív
  • Részbenrendezés: reflexív, antiszimetrikus és tranzitív
  • Dichotóm: ha bármely a, b ∈ A-ra teljesül, hogy (a, b) ∈ ρ vagy (b, a) ∈ ρ
    IRÁNYÍTOTT GRÁFKÉNT ÁBRÁZOLVA:a gráf bármely két pontja között megy él.
  • Rendezés:, részbenrendezés és dichotóm