Relációk és azok tulajdonságai

Definíció

A^{2} = A \times A = \{(a, b) : a \in A, b \in A\}

ρ \subseteq A^{2}

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\}

A x A = \{(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)} | ρ \subseteq A^{2},

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

(\forall a \in A) : 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 $(1 \leq 1), (3 \leq 3), (6 \leq 6)$

(\forall a, b \in A) : a ρ b \Rightarrow b ρ 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) ∈ ρ].

(\forall a, b, c \in A) : a ρ b \land b ρ c \Rightarrow a ρ 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.

(\forall a, b \in A) : (a ρ b \land b ρ a) \Rightarrow a = b

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ő.

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

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