3. előadás tételei

Relációk kompozíciójának asszociativitása

Állítás

$\forall R,T,S$ Relációra:

\[ (R\circ S)\circ T = R\circ(S\circ T) \]

Bizonyítás

\[ (x,w)\in (R\circ S)\circ T \underset{?}{\Longleftrightarrow} (x,w) \in R\circ(S\circ T) \]

Bal oldal

\[ (x,w)\in (R\circ S)\circ T\\ \Updownarrow \\ \exists y : (x,y) \in T \land (y,w) \in R \circ S\\ \Updownarrow \\ \exists y \exists z : (x,y) \in T \land (y,z) \in S \land (z,w) \in R \]

Jobb oldal

\[ (x,w) \in R\circ(S\circ T) \\ \Updownarrow \\ \exists z : (x,z) \in S \circ T \land (z,w) \in R \\ \Updownarrow \\ \exists y \exists z : (x,y) \in T \land (y,z) \in S \land (z,w) \in R \]

Magyarázat

Lényegében bonts szét mindent, és látszani fog, hogy ugyanazon köztes elemek kellenek a kompozíció teljesítéséhez, így ez azt magyarázza, hogy a kompozíció valóban asszociatív...

Ekvivalenciarelációk és osztályzások közötti kapcsolatról szóló tétel

Állítás

Minden ekvivalenciareláció meghatároz egy osztályzást és viszont. (És visszakapjuk az eredetit)

Bizonyítás

R Ekvivalencia reláció (Reflexív, Szimetrikus, Tranzitív) $$ \rightarrow \text{Osztály?} $$ $$ x \in A \text{ alaphalmaz} $$ $$ \text{x osztálya:} $$

Dimat Art

\[ [x] \text{:=} \{y | (x,y) \in \mathbb{R}\} \]

Állítás: Ezek az osztályok ("jó") osztályozását adják az A-nak.

nem üres:
- $\text{Reflexív} \Rightarrow \forall x: x \in [x]$
és - $U [x] = A$ - Diszjunktság: - $[x] \cap [y] \Rightarrow [x] = [y] \text{ elég.}$ - $\text{ ahol } [x] \cup [y] \text{ nem üres }$

\

\[ \text{Legyen } z \in [x] \cap [y] : (x,z) \in \mathbb{R} \land (y,z) \in \mathbb{R} \]

\[ \text{És legyen } w \in [x] \text{ Kell: } w \in [y] \]

Tudjuk: $$ (x,z) \in \mathbb{R} \xRightarrow{\text{Szimetrikus}} (z,x) \in \mathbb{R} \xRightarrow{\text{Tranzitív}} (y,x) \in \mathbb{R} $$

\[ (y,z) \xRightarrow{\text{Szimetrikus}} (z,y) \in \mathbb{R} \]

\[ (z,w) \in \mathbb{R} \xRightarrow{\text{Szimetrikus}} (w,x) \in \mathbb{R} \]

Mivel: $$ (y,x) \in \mathbb{R} \land (x,w) \in \mathbb{R} \xRightarrow{\text{Tranzitív és Szimetrikus}} (y,w) \in \mathbb{R} $$

Másik irány: $$ R \text{:=} {(x,y) | \text{x és y ugyanabban az osztályban szerepel.}} $$

Itt van valami HF, hogy R+S+T, de elég hosszú a bizonyítás magában is.