vztahy mezi dvojicemi objektů
např. rovnost přirozených čísel
"krabička" se dvěma vstupy (na pořadí záleží) → vrátí nám ano nebo ne
můžeme vyjmenovat všechny dvojice, pro které nám krabička vrátí ano
kartézský součin X×Y:={(x,y)∣x∈X,y∈Y}
Df: Relace mezi množinami X, Y je libovolná podmnožina X × Y.
Relace na množině X ... mezi X, X.
příklad – pro X = {1, 2, 3, 4, 5}
- (x,y)∈R zkrátíme na xRy
- rovnost
- R = {(1,1), (2,2), (3,3), (4,4), (5,5)}
- diagonální relace – ΔX:={(x,x)∣x∈X}
- dělitelnost x \ y
- x+y≤5
- ∅ prázdná relace
- X × Y univerzální relace
Df: pro relace R⊆X×Y definujeme inverzní relaci R−1⊆Y×X
- ∀x∈X,∀∈Y:yR−1x≡xRy
Df: pro relace R⊆X×Y a S⊆Y×Z definujeme jejich složení R∘S⊆X×Z:
- ∀x∈X,∀z∈Z:x(R∘S)z≡(∃y∈Y:xRy∧ySz)
příklad
- R⊆X×Y,ΔY
- R∘ΔY=R
funkce jsou relace, které ke každému vstupu přiřazují pouze jeden výstup
Df: Funkce (zobrazení) z X do Y je relace f mezi X, Y taková, že ∀x∈X ∃!y∈Y:xfy
Značení: f:X→Y
- pro x∈X:f(x)=y≡xfy
- pro A⊆X:f[A]:={f(a)∣a∈A}
příklady
- x↦x identita ΔX
- sin:R→[−1,1]
- lze zapsat větší množinu než definiční obor?
- sgn:R→{−1,0,+1}
- x↦−1 pro x<0
- x↦0 pro x=0
- x↦+1 pro x>0
- mohutnost množiny
- ∣_∣:2N→N∪{∞}
- f(a,b)=a+b
- f:R×R→R
skládání funkcí
- f∘g
- dva způsoby značení
- (f∘g)(x)=g(f(x))
Df: Funkce f:x→y je
- prostá (injektivní) ≡∀x1,x2∈X:X=x2⇒f(x1)=f(x2)
- na Y (surjektivní, francouzská výslovnost) ∀y∈Y:∃x∈X:f(x)=y
- vzájemně jednoznačná (1–1, bijektivní) ≡∀y∈Y:∃!x∈X:f(x)=y
pro funkci f je f−1 funkce ⟺f je bijektivní
pro f prostou: f−1 je funkce z Y' do X
- přičemž Y' je množina všech obrazů, tedy všech f[X]
Df: relace R na X je
- reflexivní ≡∀x∈X:xRx
- ΔX⊆R
- symetrická ≡∀x,y∈X:xRy⟺yRx
- antisymetrická ≡∀x,y∈X,x=y:(xRy⇒¬yRx)
- pokud x a y jsou různé prvky a x je v relaci s y, tak není pravda, že y je v relaci s x
- tranzitivní ≡∀x,y,z∈X:xRy∧yRz⇒xRz
- R∘R⊆R
- Df: Relace R je ekvivalence ≡ R je reflexivní & symetrická & tranzitivní
- příklady
- rovnost na reálných číslech
- mod K na Z
- x≡y⟺K\x−y
- geometrická shodnost
- geometrická podobnost
- pro R ekvivalenci na X
- Df: ekvivalenční třída prvku x∈X: R[x]:={y∈X∣xRy}
Df: (částečné) Uspořádání na množině X je relace R na X, která je reflexivní, antisymetrická a tranzitivní
- např. porovnávání reálných čísel
- Df: (částečně) Uspořádaná množina (X,R): X je množina, R uspořádání na X
- Značení ≤ (nebo různé varianty tohoto znaku)
- Df: x,y∈X jsou porovnatelné ≡xRy∨yRx
- Df: Uspořádání je lineární (úplné) ≡ každé 2 prvky jsou porovnatelné
- částečné uspořádání – může (ale nemusí) mít neporovnatelné prvky
- ostré uspořádání – každému uspořádání ≤ na X přiřadíme relaci < na X: a<b≡a≤b∧a=b
- pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)
- vlastnosti ostrého uspořádání – ireflexivní, antisymetrické, tranzitivní
- příklady
- (N,≤) lineární
- (Q,≤) lineární
- ΔX
- (N+,\)
- (2X,⊆) inkluze
- lexikografické
- abeceda: (X,≤)
- Df: (X2,≤lex)
- (a1,a2)≤lex(b1,b2)≡a1<b1∨(a1=b1∧a2≤b2)
- (Xk,≤lex)
- (X∗,≤lex)
- X* – konečné posloupnosti prvků z X
- pokud je slovo krátké, doplníme ho mezerami ze začátku abecedy
Df: relace bezprostředního předchůdce
- a◃b≡a<b∧∄c:a<c∧c<b
- Hasseův diagram – pro konečné ČUM (částečně uspořádané množiny) – viz sešit
Df: pro ČUM (X,≤) je x∈X:
- minimální ≡∄y∈X:y<x
- nejmenší ≡∀y∈X:x≤y
- maximální
- největší
Větička: Každá konečná neprázdná částečně uspořádaná množina (X,≤) má minimální prvek.
Dk: zvolíme x1∈X libovolně
- Buď x1 je minimální,
- nebo ∃x2<x1, s ním pokračuji
- x1>x2>x3>⋯>xt
- Pokud t > |x|, pak ∃i,j;i=j:xi=xj
- to lze pomocí tranzitivity dovést ke sporu
Df: A⊆X pro ČUM (X,≤) je
- řetězec ≡(A,≤) je lineární UM
- antiřetězec ≡∀(a,b)∈A,a=b jsou neporovnatelné