4. előadás

Részbenrendezés: antiszimmetrikus + transizív + reflexív.

Jele: \(\leq\)

Rendezések

Részbenrendezett halmaz

DEF: Ha A egy halmaz, R pedig egy részbenrendezés, akkor az A-t és az R-t együtt részbenrendezett halmaznak nevezzük \((A, R)\) DEF: Ha \((A, \leq)\) egy részbenrendezett halmaz, akkor

• \(x \in A\) MINIMÁLIS, ha \(\not\exists y \in A, y \ne x, y \leq x\)
• \(x \in A\) LEGKISEBB, ha \(\forall y \in A: x \leq y\)

(Maximális, legnagyobb): ugyan az, csak a relációs jel fordítva

MIN: "Nincs alatta semmi"

Legkisebb: "Minden fölötte van"

Teljes rendezés

DEF: Egy A halmazon egy (\(\leq\)) részbenrendezés TELJES rendezés, ha DICHOTOM (\(\forall x, y: x \leq y \lor y \leq x\))

Szigorú rendezés

Minden \(\leq\)-hoz létezik \(<\): szigorú párja a relációnak

\(< := \leq \text{, és} \ne\)

Fordítva: \(\leq := < \land =\) (gyenge pár)

Tulajdonságok:

Első három a szigorú részbenrendezésnél érvényes

Az utolsó akkor lép érvénybe, ha szogorú rendezés is.

Dichotom: Van egy olyan párja, amiből csak az egyik valósulhat meg (vagy \(\le\), vagy \(\ge\))

Trichotom: Van két olyan kiegészítője, amiből csak az egyik lehetséges (két szám nem lehet egyszerre \(<\), \(>\), és \(=\))

Fontos rendezés: LEXIKOGRAFIKUS

\((x, y) \in \mathbb{R}^2, (x', y') \in \mathbb{R}^2\) esetén

\((x, y) \leq (x', y') \iff x < x' \text{ vagy } (x = x' \land y \leq y')\)

Függvények

"csak úgy függvény" \(\leftrightarrow\) \(A \to B\) függvény

DEF: Egy \(f\) reláció függvény, ha \(\forall x, y, y': ((x, y) \in f \land (x, y') \in f) \Rightarrow y = y'\)

Azaz, minden \(x\) csak egy \(y\)-nal állhat relációban

(Mindenhonnan max 1 nyíl megy kifelé)

Jelölés:

• \(x \in dmn(f)\) (ilyenkor pontosan 1 \(y\) van)
• arra, az \(y\)-ra, amire \((x, y) \in f\) azt értük, hogy \(y = f(x)\)
• VAGY \(x \mapsto y\) vagy \(x \substack{f \\ \mapsto} y\)

DEF: \(A\) és \(B\) halmazok, akkor az \(f: A \to B\) jelölés azt jelenti, hogy

1. \(f\) függvény
2. \(dmn(f) = A\)
3. \(rng(f) \subseteq B\)

Azaz pontosan az \(A\) elemeinek van képe, és azok \(B\)-beliek

Pl: \(f: \N \to \N \quad f(x) = x^2\)

Def: \(f \in A \to B\) (\(f\) parciális függvény \(A\)-ból \(B\)-be)

1. \(f\) függvény
2. \(dmn(f) \subseteq A\)
3. \(rng(f) \subseteq B\) Def: Egy \(f\) függvény INJEKTÍV (kölcsönösen egyértelmű), ha \(\forall x, x': f(x)=f(x') \Rightarrow x = x'\)

Megjegyzés: \(f\) injektív \(\iff\) \(f^{-1}\) függvény Def: Egy \(f: A \to B\) függvény SZÜRJEKTÍV, ha \(\forall y \in B: \exists x: f(x) = y\)

Azaz \(rng(f) = B\), tehát egyértelműen megadjuk az értékkészletet Def: \(f: A \to B\) BIJEKTÍV, ha injektív ÉS szürjektív

Megj.: ilyenkor \(f^{-1}: B \to A\)

Bijektív függvény példa

Négyzetre emelés (\(x \mapsto x^2\)), HA \(f: \R^+ \to \R^+\)

De, ha \(f: \R \to \R\), akkor nem injektív, nem szürjektív, tehát nem lehet bijektív se

De, ha \(f: \R \to \R^+\), akkor szürjektív, de még mindig nem injektív

\(\R \to \R\):

• Injektív, ha minden vízszintes egyenes \(\leq 1\) pontban metszi
• Szürjektív, ha minden vízszintes egyenes \(\geq 1\) pontban metszi

Megjegyzés: \(f: A \to B\)

• \(f\) az \(A\)-ból \(B\)-be képez
• Helytelenül mondják:
  • \(f\) az \(A\)-ból \(B\)-re képez
  • Ez magával hordozza azt is, hogy \(f\) szürjektív

Függvények kompozíciója

Ha \(f\) és \(g\) függvény, akkor \(f \circ g\) is függvény \(\quad\) és \(\forall x \in dmn(f \circ g): (f \circ g)(x) = f(g(x))\)

Állítás:

• \(f\) injetív, y injektív \(\Rightarrow\) \(f \circ g\) injektív
• \(f: B \to C\) szürjektív és \(y: A \to B\) szürjektív \(\Rarr\) \(f \circ g: A \to C\) szürjektív
• \(f: B \to C\) bijektív és \(g: A \to B\) bijektív \(\Rarr\) \(f \circ g: A \to C\) bijektív

Bizonyítás:

• Injektivitás: \(f(g(x)) = f(g(x')) \substack{\Rarr \\ f \ injektív} g(x) = g(x') \substack{\Rarr \\ g \ injektív} x = x'\)
• Szürjektív: \(z \in C \substack{f \ szürjektív \\ \Rarr} \exists y \in B: f(y) = z \substack{g \ szürjektív \\ \Rarr} \exists x \in A: g(x)=y \Rarr f(g(x)) = z\)
• Injektív + szürjektív \(\Rarr\) bijektív

Megjegyzés: bijekció \(\Rarr\) ugyanannyi elem

Műveletek

Speciális függvény

\(f: A \times A \to A\)

Pl.: \(+\) az \(\N\)-on: \(+: \N \times \N \to \N\)

\(f: A \times A \to A\)

\(f((a, b))\) helyett gyakran infix jelölést használunk