3. előadás - Relációk

Asszociativitás Kompozíciókra

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

Megjegyzés

Ha \(R, S, T\): "gyereke"

Gyerek unokája = unoka gyereke

Bizonyítás

\((x, w) \in (R \circ S) \circ T \iff (x, w) \in R \circ (S \circ T)\)

Bal oldal: \(\exists y: (x, y) \in T \land (y, w) \in R \circ S\)

Jobb Oldal: \(\exists z: (x, y) \in S \circ T \land (Z, W) \in R\)

Bal oldal: \(\exists y: (x, y) \in T \land (y, w) \exists z:(y, z) \in S \land (z, w) \in R\)

Jobb Oldal: \(\exists z: \exists y: (x, y)\in T \land (y, z) \in S \land (Z, W) \in R\)

Ez a két állítás ekvivalens

Def: Reláció megszorítása egy halmazra

R rel, A halmaz: \(R|_a := \{x, y \in R | x \in A\}\)

Def: R szerinti kép/inverz kép

\(R(A) := \left\{y \space |\space \exist x \in A: (x,y) \in R \right\}\)

\(R^{-1}(A) := \left\{x \space |\space \exists y \in B: (x, y) \in R\right\}\)

Alternatív jelölés

\(\mathbb{P}\): Prímszámok, \(R\): hatványok(Reláció)

\(R(\mathbb{P})\): Prímek hatványai

Egy \(R\) reláció

Tranzitív

\(\forall x, y, z: (x, y) \in R \land (y, z) \in R \Rightarrow (x, z) \in R\)

Ha \(x \rightarrow y \rightarrow z \Rightarrow x \rightarrow z\)

Hármas reláció, amit az első kettőből ki lehet következtetni

Szimmetrikus

\(\forall x, y: (x, y) \in R \iff (y, x) \in R\)

Antiszimmetrikus

\(((x, y) \in R \land (y, x) \in R) \Rightarrow x = y\)

Másképp:

\(\forall x, y: x \ne y\)

\((x, y) \in R \Rightarrow (y, x) \not\in R\)

Irreflexív

\(\forall x: (x, x) \not\in R\)

Szigorúan antiszimmetrikus

\(\forall (x, y): (x, y) \in R \Rightarrow (y, x) \not\in R\)

Def: Egy R reláció az A halmazon

Reflexív

\(\forall x \in A: (x, x) \in R\)

Dichotom

\(\forall (x, y) \in A: (x, y) \in R \lor (y, x) \in R\)

Trichotom

\(\forall (x, y) \in A:\)

• a: \(x = y\)
• b: \((x, y) \in R\)
• c: \((y, x) \in R\)

közül pontosan EGY teljesül

Egy R reláció

Értelmezési tartománya

\(dmn(R) = {x | \exists y:(x, y) \in R}\)

Értékkészlete

\(rng(R) = {y | \exists x:(x, y) \in R}\)

Példa

Párhuzamosság (\(||\)): szimmetrikus, tranzitív, reflexív (sík egyenesei)

Ekvivalenciareláció

egy R reláció az A halmazon ekvivalenciaosztály, ha

• tranzitív
• szimmetrikus
• A-n reflexív

Ekvivalenciaosztály

Egy A halmaz (ekvivalencia)osztályozása (\(X\)):

Felbontása olyan halmazokra, melyek:

• Páronkínt diszjunktak (\(\forall G, H \in X: G \ne H \Rightarrow G \cap H = \emptyset\))
• Úniójuk az \(A\) (\(\cup X = A\))
• Nem üresek (\(\forall H \in X: H \ne \emptyset\))

Tétel 1

Minden ekvivalenciareláció meghatároz egy osztályozást és viszont

1. tétel bizonyítása

R ekvivalencia reláció

\(x \in A \ alaphalmaz\)

\([x]\) (x osztálya)

\([x] := \left\{y | (x, y) \in R\right\}\)

Állítás: ezok az osztályok "jók", osztályozását adják A-nak

• Nem üres: REFL \(\Rightarrow \forall x: x \in \left[x\right]\) + \(\cup \left[x\right] = A\)
• Diszjunktság: \(\left[x\right] \cap \left[y\right] \Rightarrow \left[x\right] = \left[y\right]\)

Legyen \(z \in \left[x\right] \cap \left[y\right]: (x, y) \in R \land (y, z) \in R\)

és legyen: \(w \in \left[x\right].\)

KELL: \(w \in \left[y\right]\)

Alkalmazás

pl. Maradékosztályok

\((x, y) \in R \iff x-y \ \text{osztható 10-zel}\)