Prednáška 2.
Def: Funkcia(zobrazenie) z A do B je relácia z A do B, ktorá je všade definovaná a jednoznačná.
{z každého vrchola množiny A vychádza práve jedna šípka}
Pr1.
A={1,2,3}, B={w,x,y,z}
R1={(1,w)(2,x)(3,x)}- funkcia
R2={(1,w)(2,x)}- nie je funkcia, pretože nie je všade definovaná
R3={(1,w)(2,w)(2,x)}- nie je funkcia, lebo nie je jednoznačná a nie je všade definovaná
Označenie: f,g,h,... alebo malé grécke písmená φ
f(x)- obraz bodu x vo funkcii f.
f: A -> B {A - definičný obor funkcie, B – koobor, obor hodnôt}
Pr2.

f(x)=3x2+x-1

∀ x∈ℝ

∃ y ∈ℝ

Veta: Nech R je relácia z množiny A do množiny B, potom R je funkcia, práve vtedy

ak I A≤R° R ∧ I B≥ R° R .
Pozn.:

R

° R : A A

R

° R : B  B

Príklady špeciálnych funkcii( zobrazení )

1. Konštantná funkcia: f : A

 B , ∃b∈B ∀ x∈ A f  x=b

2. Identické zobrazenie: I A : A  A , I A x= x

3. Postupnosť: a0,a1,a2,... prvkov z A je funkcia f :

ℕ A ,

f

i=ai

4. Usporiadaná n-tica: a0,...an n prvkov z A je funkcia f :{1,.. , n} A ,

f

i=a

i

1

≤i≤n

5. Charakteristická funkcia množiny A <=M

A: M {0,1}



A  x  = x∉ A  0 ∨ x∈ A  1

6. Najväčšia celá dolná čast (floor function):

f :

ℝ ℤ

f

 x=[ x]

7. Najmenšia celá horná čast(celling function):

f :

ℝ  ℤ

f

 x=najmenšie celé číslo≥ x

8. Funkcia trunc:

f :

ℝ  ℤ

zabúda desatinnú čast čísla

Vlastnosti funkcii(zobrazení)
Def: Zobrazenie f : A

 B sa nazýva injektívne(prosté) x1, x2∈A , x1 ≠ x2, f  x1 ≠ f  x2

Def: Zobrazenie f : A

 B sa nazýva surjektívne ∀ y∈B ∃ x∈ A f  x = y

Pozn: f je injektívna, ak f je jednoznačna relacia
f je surjektívna, ak opačná relácia f je všade definovaná
Def: Zobrazenie f : A

 B sa nazýva bijektívne(jedno-jednoznačne) ak je injektívne a aj surjektívne.

Pr1.

f :

ℝ ℝ

f

 x = 3x  7

je bijekcia

Pr2.

g :

ℝ ℝ

g

 x= x

4 − x

nie je bijekcia g(0)=04 – 0 = 0, g(0)=14 – 1 = 0

Pr3.
A={1,2,3}, B={1,2,3,4,5}

ℝ : A B ,

f

= {1,1 , 2,3 ,3,4}− funkcia je injektívna , ale nie je surjektívna

kolko rôznych f : A

 B vieme nájsť? 5 3 .

Def: Ak f : A

 B je funkcia a A1⊆ A f /a1 A B je zúženie

funkcia f na množine A1, ak platí f /a1 x = f  x  , ∀ x ∈A1
Pr4.

f :

ℝ ℝ

f

 x =sin  x

A

1=[ o ,  ]

f

/

[o ,] [ o ,  ]  ℝ

Def: Nech A1⊆ A , f : A1 B funkcia ak g : A B je taká , že g  x= f  x ∀ x A1 tak g sa nazýva
rozšírenie funkcie f.

Prednáška 3

Relácie na množine:

R

⊆ A× A

A

=ℤ , k , l ∈R

Pr1.
A = {a,b,c}, R = {(a,a),(a,b),(b,c),(b,a)}

Orientovaný diagram

A

B

C

Def: Nech R

⊆ A× A R sa nazýva

1. reflexívna

∀ a∈ A; a , a ∈R

2. antireflexívna

∀ a∈ A; a , a ∉R

3. symetrická

∀ a ,b∈A ; a , b∈R b , a∈R

4. antisymetrická

∀ a ,b∈A ; [a , b∈R∧b , a∈R ] a=b

5. asymetrická

∀ a ,b∈A ; a , b∈R b , a∉R

6. tranzitívna

∀ a ,b , c∈A ; [a ,b∈R∧b , c∈R]  a , c ∈R

7. trichotomická

∀ a , b∈A ; a=b ∨ a ,b∈R ∨ b , a ∈R

Pr2.
A – množina ľudí

č1 , č2∈R

č1 je súrodenenec č2

1. nie
2. áno
3. áno

4. nie
5. nie
6. áno
7. nie

Pozn: Všimnite si, že:

1. R je reflexívna,<=> R⊇ Ia

2. R je antireflexívna <=> R∩ Ia={ }
3. R je symetrická <=> R

= R

4. R je antisymetrická <=> R∩ R⊆I a
5. R je asymetrická <=> R

∩ R={ }

6. R je tranzitívna<=> R

⊇ R° R

Def: Binárna relácia R na množine A sa nazýva ekvivalencia ak je(naraz): reflexívna, symetrická,
tranzitívna.

Pr3. A

=ℤ ; m , n∈R 4 / m−n

1. Reflexívna

k , k ∈R

2. Symetrická m , n∈R 4 / m−n  4/ n−m  m , n∈R

3. Tranzitívna

k ,l ∈R∧l , n∈R  k , n∈R

4

/

k

−l

∧ 4 /

l

−n

 4 /

k

−n

Notácia: E – (ekvivalencia)

 x , y ∈R ;  x , y∈E

x R y; x E y; x~y; x ~E y
Def: Nech E je relácia ekvivalencie na množine A
Potom množina

{x∈ A ∣ a , x ∈E } sa nazýva trieda ekvivalencie prvku a.

Pr4.

A

=ℤ k , l∈R 4/ k ,l

[3]R={7,11,15,−1,.......}⊆ℤ

[1]

R ={5,1,9,− 3,....... }⊆ℤ

[7]R≠[1]R=[5]R

Lema: nech E je relácia ekvivalencie na A
Potom platí:

1.

∀ a∈ A a∈[a ]

E

2.

a E b

≡[a]

E =[b ]E

3. pre každé z triedy ekvivalencie platí [a]E=[b]E∨[a ]E∩[b]E={ }

Prednáška 4
Nech E je relácia ekvivalencie na A
Trieda ekvivalencie prvku a

∈A

[a]

E ={x∨a , x ∈ E }⊆ A

Veta: Nech E relácia ekvivalencie na A a nech x , y

∈A

Potom

1. x ∈[ x ]E
2.

x E y

≡[ x]=[ y]

3.

[ x ]=[ y]∨[ x ]∩[ y ]=∅

Dôkaz:

1. vyplýva z reflexívnosti E

2. => Predp., že x E y, nech nejaké z ∈[ X ]E  z E x∧ x E y , teda z E y  z∈[ y ]E

<= Predp., že

[ x ]

E =[ y ]E

vieme , že x

∈[ x ]

E podľa a.  [ x ]E =[ y ]E  x ∈[ y ]E 

x E y

3. Sporom:

Predp., že

[[x]E≠[ y ]E∧[ x ]∩[ y ]≠∅]

∃ z∈[ x ]

E∩[ y ]E 

z

∈[ x ]

E ∧ z ∈[ y ]E 

z E x

∧z E y  x E y  [ x]

E =[ y ]E− spor !

def:
systém S množín Si sa nazýva rozklad množiny A, ak

1.

∀ i Si≠∅

2. množiny Si sú po dvojiciach disjunktné

3.

U

s

i ∈S =

A

Ozn.: Nech E je ekvivalencia na A

Systém tried ekvivalencie označujeme

A /

E = {[ x]E ∨ x ∈ A }

Veta: Nech E je ekvivalencia na A

Potom

A /

E

- systém tried ekvivalencie na A je rozklad množiny A

Dôkaz: Treba overiť vlastnosti rozkladu

1. neprázdnosť: ∀ x∈ A [ X ]E obsahuje aspoň x
2. disjunktívnosť: triedy sú po dvojiciach disjunktné(predchádzajúca veta)

3.

U

x

∈ A [ x]E= A

U

[ x ]

E ⊆ A  ∀ x ∈ A ∃ [ x]E

Pr1.
A= {1,2,3,...10} A1 ={1,2,..5} A2 = {6,7,..10}

Def: Nech S je nejaký rozklad možiny A
Relácia ES na A (ekvivalencia indukovaná rozkladom)

E

S ={ x , y∈ A× A∨∃C v rozklade S tak , že x∈C ∧ y ∈C }

Veta: Relácia ES z predchádzajúcej definície je ekvivalencia na A
Dôkaz:

1. reflexívna

∀ a∈ A∃C ∈S z vlastnosti

2. symetria
3. tranzitívnosť

 x , y ∈E

S ∧ y , z ∈ E S ∃ C ∈S ; x , y ∈C ∧∃ D∈ S ; y , z ∈ D  y∈C ∩ D  C = D

x , y , z

∈C  x , z∈E

S

č.b.t.d.

Vieme

E



A /

E

S

 E

S

Veta: Nech E je ekvivalencia na A

Potom

A /

E

je rozklad indukovaný E,

E A/E =E

Nech S je rozklad množiny A

Es – ekvivalencia indukovaná rozkladom S. Potom

A /

E

S

=S

ekvivalencia na A = rozklad množiny A

Def: Binárna relácia R na množine A sa nazýva čiastočné usporiadanie množiny A, ak je

a) reflexívna
b) antisymetrická
c) tranzitívna

d) Pr2.:

≤ na množine ℤ ℤ , ≤ 

≤ na množineℝ

A

=serZ

 R= / l ,k∈R l /

k

ℤ

 , / 

Pr3.: A

≠∅  P  A , ⊆  je to čiastočné usporiadanie?

Prednáška 5
Pr1.:
A{1,2,3,4}
R{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,4)}

=> a R b ak a | b

Zjednodušený diagram čiastočného diagramu – Hasseho diagram
Ostré usporiadanie
Def: bin relácia R, definovaná na A sa nazýva ostré usporiadanie ak je

1. asymetrická
2. tranzitívna

Veta: (vzťah ostrého a čiastočného usporiadania)

a) Nech R je čiast. usp. množiny A, potom relácia S, ktorú definujeme takto: a S b práve vtedy

a R b a

≠b je osté usporiadanie

b) Nech S je ostré usp. množiny A, potom relácia R, ktorú definujeme a R b práve vtedy a S b

alebo a = b je čiastočné usp.

Def: Nech a ,b

∈ A sú prvky množiny A

Nech R je relácia čiastočného usporiadania(ostrého) na A
Prvky a,b nazývame porovnateľné v usp. R
ak a R b alebo b R a - nie sú porovnateľné
Def: Usporiadanie R sa nazýva lineárne(úplné) usporiadanie ak každé dva prvky z A sú porovnateľné
v usp. R
(A,R) sa nazýva lineárne (úplné) usporiadaná množina
Def: Nech A je čiast. (ostro) usporiadaná množina
Podmnožina B

⊆A sa nazýva reťazec v A, ak každé dva prvky z B sú porovnateľné.

Def: Nech R je čiast. usporiadanie na A.
nech B

⊆A

a) Prvok b

∈B je najmenším prvkom v Bvzhľadom na usp. R, ak ∀ x∈B b R x.

b) Prvok b

∈B sa nazýva minimálny prvok B vzhľadom na usp. R, ak ¬∃ x ∈B také,

že x R b

Veta: Nech A je čiast. usp. množina
nech B

⊆A

a) B má nanajvýš jeden najmenší prvok
b) Najmenší prvok (ak existuje) je zároveň aj minimálny
c) Ak B je reťazec, tak minimálny je najmenší.

Veta: podobne pre najväčší a maximálny prvok
Dôkaz:
Sporom predpokl., že máme 2 rôzne najmenšie prvky

b

1,b2 ∈ B

b

1 je najmenšie  b1≤b 2

∧ b

2 je najmenšie  b1 ≥b2

b

1 =b2  SPOR

Def: Nech A je čiastočne usp. množina A s usp. R nech B

⊆A .

a

∈A sa nazýva dolné ohraničenie množiny B, ak a R x ∀ x∈B