temata:16-mnoziny-relace-zobrazeni:main [SZZ]

Množina

Definice

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

Y = { x | x

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)
=
=

Relace

Binární relace

Definice

(a, b) … uspořádaná relace, uspořádaná dvojice

(a ,b) = {{a}, {a,b}}

Definice

Jsou-li X,Y množiny, pak karté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
Jednoznačnost zobrazení je důležitá a znamená, že každý prvek vzoru se zobrazí na právě jeden prvek v obrazu.
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í)

se zobrazenim souvisy vyrazy „vzor“ a „obraz“
množina všech vzorů je definičním oborem, množina všech obrazů je oborem hodnot

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 zobrazením, 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

Ukazka

Mějme množinu celých čísel Z, sestrojme zbytkové třídy po dělení 4 (modulo 4).

Dělením čísla $a \in Z$ dostaneme tyto zbytky:

$\lbrace 0, 1, 2, 3 \rbrace$

Čísla 1, 5, 9, 14, …, 5 + k.4 dávají zbytek po dělení 4 číslo 1, dostáváme tedy třídu $[1] = \lbrace..., -7, -3, 1, 5, 9, ...\rbrace$

Analogicky pro 2, 6, 10, … dostaneme $[2] = \lbrace..., -6, -2, 2, 6, 10, ...\rbrace$

Celkově dostaneme třídu zbytků [0], [1], [2], [3].

Pro operace se zbytky potom plati nasledujici:

[0] + [2] = [1]

[2] + [1] = [3]

[3] + [3] = [2]

[0] * [2] = [0]

[2] * [3] = [2]

pokud odstraníme závorky, dostaneme zajímavé výsledky, pokud se neuvědomíme, že se jedná o operace se zbytkovými třídami:

0 + 1 = 1

2 + 1 = 3

3 + 3 = 2

0 * 2 = 0

2 * 3 = 2

Přikládám návod, co jsem jednou psal spolubydlícímu před půlsemestrálkou — Jirka Hynek 2011/03/16 20:51

Relace na mnozine

vezmeme JEDNU množinu a na ni aplikujeme relaci
- tzn. máme nějakou množinu - třeba X, která obsahuje určité prvky - třeba {1,2,3,4}
provedeme kartézský součin (X x X) = {1,2,3,4} x {1,2,3,4}
- budeme vytvářet všechny možné dvojice: (prvek z mnoziny vlevo, prvek z mnoziny vpravo) → { (1,1), (1,2), … , (4,4) }
  - bude jich fakt hodne, jak je videt → to je kartezsky soucin, ze musi byt vsechny moznosti
nyní můžeme vytvářet relace
- pokud vezmeme RELACI, vezmeme PODMNOŽINU kartézského součinu
- např. { (1,2), (3,4) } je relace na množině X, protože je podmnožinou kartézského součinu → všech dvojic
teď si můžeme popsat jednotlivé relace:
1. REFLEXIVNÍ - aby relace byla reflexivní, musí obsahovat prvky (x,x) ⇒ tzn. všechny dvojice se stejnými prvky:
  - → { (1,1), (2,2), (3,3), (4,4) } → MUSÍ TAM BYT ALE VSECHNY PRVKY - u nás: 1, 2, 3 a 4
2. SYMETRICKÁ - pokud máme v relaci nějakou dvojici - např. (1,2), musí k ní být vždy „zrcadlový obraz“ - tedy (2,1)
3. ANTISYMETRICKÁ - to je opak předchozí relace
  - ⇒ tzn. pokud tam mám (1,2) nemůžu už mít (2,1) … ale neplatí to pro (x,x), kde první i druhý prvek je stejný (ty můžou být obsaženy v ansymetrické relaci) ⇒ tzn. tyto dvojice nás nezajímají, jenom ty kde prvni a druhy prvek je jiny
4. TRANZITIVNÍ - pokud mám v relaci (1,2) a třeba (2,3), kde druhý prvek jedné dvojice se rovná prvnímu prvku jiné, musím spojit sousedy těchto prvků ⇒ tzn (1,3) tam musí také být, aby to bylo tranzitivní
5. EKVIVALENCE ⇒ platí A, B a D
6. ČÁSTEČNÉ USPOŘÁDÁNÍ ⇒ platí A, C a D
7. TOLERANCE → platí A a B
8. KVAZIUSPOŘÁDÁNÍ ⇒ platí A a D

vagabund, IDA, mnozina, relace, zobrazeni

Potvrzení

16
Celé jméno	OK	!!!
Jirka Hynek
	1

Diskuze

george, 2011/03/16 20:49

Vytvořil jsem tomuto tématu nový jmenný prostor a přesunul to sem z původního umístění. Hodilo by se to trochu formátovat, ať se v tom člověk vyzná.

george, 2011/03/16 21:25

Přidal jsem příklad, co jsem posílal spolubydlícímu před půlsemestrálkou. Osekal jsem to o zbytečnosti, tak se to snad hodí…

george, 2011/04/17 10:54

Je potřeba tady dodělat informace o zobrazení a přidat obrázky.

Obsah

16 - Množiny, relace a zobrazení

Množina

Operace s množinami

Relace

Binární relace

Relace na množině

Potvrzení

Diskuze