16 - Množiny, relace a zobrazení

Soubor objektů, chápaný jako celek. Objekty se nazývají prvky množiny. Charakterizující vlastnost množiny je, že je jednoznačně určena svými prvky (ale nevšímá si jejich pořadí ani žádné další struktury). Množina, neobsahující žádné prvky se nazývá prázdná množina.

Prázdná množina … varnothing

Operace s množinami

X union Y = { x | x X vert x Y}

X inter Y = { x | x X wedge x Y}

X - Y = { x | x X wedge x notin Y}

X xor Y = { x | (X - Y) union (Y - X)}

platí:

A B = B A
A B = B A
(A B) C = A (B C)
(A B) C = A (B C)
(A B) C = (A B) (A C)
(A B) C = (A B) (A C)
=
=

Binární relace

(a, b) … uspořádaná relace (a ,b) = {{a}, {a,b}}

definice: jsou-li X,Y množiny, pak kertézským součinem množin X,Y rozumíme množin X x Y = {(x,y) | x X, y Y}

definice: binární relací z X do Y pak rozumíme libovolnou podmnožinu kartézského součinu, tj. (a, b) subset X x Y

definice: buď R subset X x Y, potom Dom R = {x | exists y Y: (x,y) R} … definiční obor Im R = {y | exists x X: (x,y) R} … obor hodnot

definice: buď f subset X x Y relace z X do Y: forall x Dom f subset X exists ! y Y: (x, y) f

(x, y) f, y = f(x), f: X right Y

zobrazeni nazýváme:

prosté neboli injektivní: , X: f() = f() = (každý prvek v Y má nejvýše jeden vzor)
surjektní neboli na: y Y x X: f(x) = y (každý prvek v Y má nějaký vzor)
bijektní neboli vzájemně jednoznačné (surjektivní a injektivní)

definice: Nechť R subset X x Y, potom inverzní relaci značíme $R^{-1}$ a platí $R^{-1}$ Y x X. Je li inverzní relace zobrazíme, potom mluvíme o inverzním zobrazení

definice: Nechť máme relace S,R, potom S circ R navýváme složenou relací, čteme S po R, analogicky pro fce

Relace na množině

´ definice: Nechť R subset X x X,

a) reflexivní, jestli (x,x) R pro x X,
b) symetrická, jestli (x,y) R (y,x) R,
c) antisymetrická, jestli [(x,y) R (y,x) R] x = y,
d) tranzitivní, jestli [xRy yRz] xRz

ekvivalence … platí a,b,d

částečné uspořádání … a,c,d

tolerance … a,b

kvaziuspořádání … a,d

definice: Nechť X množina a S soubor podmnožin množiny X. Jestli je union S = X a množiny z S po dvou disjuktní, zavýváme S rozkladem na množině X.

Nechť R relace definovaná na X a platí že S je rozklad, potom je R ekvivalence

definice: [a] = {x | x X, xRa}, potom S = {[a] | a X} je rozklad na X