Obsah

AP1, IN1 Množiny a relace
Diskuze

AP1, IN1 Množiny a relace

Zadání

(zobrazení, funkce, rozklady a ekvivalence)

Vypracování

Naivní pohled: Množina je soubor prvků a je svými prvky plně určena. Naivní pohled uvažuje jen konečné množiny.

Množiny ale mohou být i prvky jiných množin. Množiny mohou pochopitelně mít i nekonečně mnoho prvků.

Příklady

$M=\{a, b\} = \{b, a\} = \{a, b, a\};\ N=\{\{a\}\, ,\,\{b,c,d,e\} \}$

$a \in M;\ a \notin N;\ \{ a\} \notin M;\ \{ a\} \in N$

$\emptyset \in \{\emptyset\};\ \emptyset \notin \emptyset$

V této souvislosti je dobré uvést také Russelův paradox

Fakt: Není pravda, že každý soubor prvků lze považovat za množinu.

$X=\{ M | M$ je množina taková, že $M \not\in M\}$ . Platí $X \in X$ ?

Ano. Tj. $X \in X$ . Pak ale X splňuje $X \not\in X$ .
Ne. Pak X splňuje vlastnost $X \not\in X$ , tedy X je prvkem X, tj. $X \in X$ .

Obě možné odpovědi vedou ke sporu. $X$ tedy nelze prohlásit za množinu.

Právě tento a další paradoxy vedly na začátku 20. století ke vzniku axiomatické teorie množin (později ke vzniku více axiomatických teorií).
V takových axiomatizovaných teoriích množin obvykle nesmí množina obsahovat jiné prvky než zase jenom množiny a nic jiného.

Základní pojmy a definice

Podmnožina: $A \subseteq B\ \Leftrightarrow\ \forall x\in A:\, x \in A \Rightarrow x \in B$ Vlastní podmnožina: $A \subset B\ \Leftrightarrow\ A \subseteq B\, \wedge\, A \neq B$ Sjednocení: $A \cup B = \{ x\,\mid\, x \in A\,\vee\, x \in B \}$ Průnik: $A \cap B = \{ x\, \mid\, x \in A\, \wedge\, x \in B \}$ Rozdíl: $A \setminus B = \{ x\, \mid\, x \in A\,\wedge\, x \notin B \}$ Doplněk: Nechť $A\subseteq M\$ . Doplněk A vzhledem k M je množina $B = M \setminus A$ Součin: $A \times B = \{(a,b)\,\mid\, a \in A \wedge b \in B\}$ Potenční množina: Jedná se vlastně o množinu všech podmnožin. $2^{A}=\{ B\, \mid\, B \subseteq A\}$

Příklady

$A=\{1,2,3\},\ B=\{3,4,5\},\ C=\{a,b\},\ D=\{1,2\} D \subset A;\ D \subseteq A$

$A \cup B\,=\,\{1,2,3,4,5\}$

$A \cap B\,=\,\{3\}$

$A \setminus B\,=\,\{1,2\}$

$A \times C \,=\,\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}$

$2^{C}\,=\,\{\emptyset,\{a\},\{b\},\{a,b\} \};\ 2^{\emptyset}\,=\,\{\emptyset\}$

Relace

k-ární relace mezi $A_1, A_2,\ldots,A_k$ je podmnožina součinu $A_1 \times A_2\times \ldots \times A_k$ . $2^{A_1 \times A_2 \times \ldots \times A_k}$ je množina všech relací mezi $A_1,A_2,\ldots, A_k$ . Pokud je $k=2$ jedná se o binární relaci, pokud je $k=3$ , jde o relaci ternární.

Složení relací: Má smysl pouze u binárních relací a definováno následovně:

$R\subseteq A\times B,\ S \subseteq B \times C:$

$S\circ R\, =\, \{(a,c)\,\mid\, \exists b \in B.\, (a,b)\in R\, \wedge\, (b,c)\in S\}$

Příklady

$A=\{1,2,3\};\ B=\{a,b,c\};\ C=\{x,y,z\}$

$R=\{(1,a),(1,b),(2,c),(3,a)\}\subseteq A\times B;\ S=\{(a,z),(b,x)\}\subseteq B\times C$

$R^{-1}=\{(a,1),(b,1),(c,2),(a,3)\}$

$S\circ R = \{(1,x),(1,z),(3,z)\}$

Funkce a zobrazení

(Totální) funkce z $A$ do $B$ je relace $f \subseteq A\times B$ kde pro každé $x\in A$ existuje právě jedno $y\in B$ takové, že $(x,y)\in f$ .

$(x,y)\in f$ je ekvivalentní zápisu $f(x)=y$ . $A$ je definiční obor, $B$ je obor hodnot.

Parciální funkce z množiny $A$ do množiny $B$ je relace $f \subseteq A\times B$ kde pro každé $x\in A$ existuje nejvýše jedno $y\in B$ takové, že $(x,y)\in f$ .

Funkce $f$ je injektivní (prostá) právě tehdy, když $\forall x,y\in A, x\neq y\ \Rightarrow \ f(x)\neq f(y)$ .
Funkce $f$ je surjektivní (na) právě tehdy, když $\forall y\in B. \exists x\in A.\, f(x)=y$ .
Funkce $f$ je bijektivní, jestliže je injektivní a surjektivní.

Tyto vlastnosti funkcí lze využít pro porovnávání velikostí jednotlivých množin a to i nekonečných:

$|A| \leq |B|$ pokud existuje injekce $A \rightarrow B$ .
$|A|=|B|$ pokud existuje bijekce $A \rightarrow B$ . - např. N, Q a Z jsou „stejně velké“ (tzv. spočetně nekonečné)
$|A|<|B|$ pokud existuje injekce $A \rightarrow B$ ale neexistuje bijekce $A \rightarrow B$ . - např. R je striktně větší než libovolná spočetná množina

Vlastnosti binárních relací

Pro následující definice budeme uvažovat $R \subseteq M \times M$ .

Relace $R$ je reflexivní právě tehdy, když $\forall a\in M:\, (a,a)\in R$ .
Relace $R$ je symetrická, pokud platí: $(a,b)\in R\, \Rightarrow\, (b,a)\in R$ .
Relace $R$ je antisymetrická, pokud platí: $(a,b)\in R\, \wedge\, (b,a)\in R \,\Rightarrow\, a=b$ .
Relace $R$ je tranzitivní, pokud platí: $(a,b)\in R\,\wedge\, (b,c)\in R\, \Rightarrow\, (a,c)\in R$ .
Relace $R$ je ekvivalence, pokud je reflexivní, symetrická a tranzitivní.
Relace $R$ je uspořádání, pokud je reflexivní, antisymetrická a tranzitivní.

Příklady

Buď $M$ množina studentů FI. Uvažujme relace $R\subseteq M\times M$ definované takto:

$(x,y) \in R$ právě když $x$ má stejnou výšku jako $y$

relace je reflexivní, symetrická a tranzitivní: jde o relaci ekvivalence.

$(x,y) \in R$ právě když $x$ má alespoň takovou výšku jako $y$

tato relace je reflexivní a tranzitivní.

$(x,y) \in R$ právě když $x$ a $y$ mají stejné rodné číslo

tato relace je reflexivní, symetrická, antisymetrická a tranzitivní (je to tedy ekvivalence i uspořádání).

$(x,y) \in R$ právě když $x$ má jinou výšku než $y$

tato relace je symetrická.

Rozklady a ekvivalence

Buď $M$ množina. Rozklad na $M$ je množina $N \subseteq 2^{M}$ taková, že platí:

$\emptyset \notin N$
$A,B \in N \Rightarrow A \cap B = \emptyset\ \vee\ A=B$
$\bigcup_{A\in N}A = M$

Pokud chceme ověřit, že daná množina je rozklad na nějaké množině, musíme ověřit platnost výše uvedených tří podmínek.

Příklad

$M=\{1,2,3,4,5,6,7,8,9\}$

$N=\{\{1,4\},\{2,7,8,9\},\{3\},\{5,6\} \};\ O=\{\{1,4\},\{2,7,8,9\},\{3,4\},\{5,6\} \}$

$N$ je rozklad na $M$ , ale $O$ rozklad na $M$ není (nemůže být rozkladem ani na žádné jiné množině – viz 2. podmínka pro rozklad).

Každý rozklad $N$ určuje jistou ekvivalenci $R_N$ na množině $M$ a to následovně:

$(x,y)\in R_N\ \Leftrightarrow\ \exists A\in N.\, x,y \in A$

Takto definovaná relace $R_N$ splňuje všechny požadavky na relaci ekvivalence. Je tedy reflexivní, symetrická a tranzitivní. Toto je možné ověřit důkazem ¹⁾.

Příklad

$M=\{1,2,3,4\};\ N=\{\{1,3,4\},\{2\}\}$

$R_N=\{(1,1),(1,3),(1,4),(3,3),(3,1),(3,4),(4,4),(4,1),(4,3),(2,2)\}$

Každá ekvivalence $R$ určuje jistý rozklad $M/R$ na $M$ :

$[x] = \{y\in M\, \mid\, (x,y)\in R \}$
$M/R = \{ [x]\, \mid\, x \in M\}$

Takto definovaný rozklad splňuje všechny požadavky na rozklad (viz výše). Toto je opět možné dokázat ²⁾.

Příklad

$M=\{1,2,3,4\};\$

Buď $R=\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ ekvivalence na $M$ . Potom:
$M/R=\{\{1,2\},\{3\},\{4\} \}$

Co byste ještě měli znát?

Měli byste také znát, kde se využívá ekvivalence.

Předměty

FI:IB000 Úvod do informatiky (podzim 2005), prof. RNDr. Antonín Kučera, Ph.D.

Použitá literatura

prof. RNDr. Antonín Kučera, Ph.D., slidy z přednášek předmětu IB000 Úvod do informatiky. Tyto slidy nejsou v současné době již dostupné na osobním webu prof. Kučery. Jako alternativa se nabízejí materiály doc. RNDr. Petra Hliněného, Ph.D. dostupné zde.

Úvod do informatiky, doc. RNDr. Petr Hliněný – v kapitole 11 jsou hezky popsány Nekonečné množiny a zastavení algoritmu

Vypracoval

Honza Palas, UČO: 172760
Z mé strany na 99% hotovo, pokud vás napadne něco doplnit, samozřejmě můžete.

Otázku si přečetl pan RNDr. Jan Bouda a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen rámcová, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

¹⁾

Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 46

²⁾

Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 47-48

Diskuze

Karel Barot, 2008/05/27 01:38

Mel bych pripominku k casti „Funkce vs. zobrazení“. Nevim, odkud Honza cerpal, ale ja chapu tyto pojmy zcela odlisne. To, co Honza nazyva zobrazenim, ja chapu jako funkci. Funkce je (podle meho nazoru) „předpis, jak jednoznačně přiřazovat prvkům jedné množiny prvky obecně jiné množiny“. A nezalezi na tom, jestli je obor hodnot mnozina obsahujici cisla nebo jine prvky. U zobrazeni pouze netrvame na „jednoznacnosti“.
U uvedenych prikladu Honza tvrdi, ze f je zobrazeni (a tedy neni funkce). Podle me f i g jsou (totalni) funkce. Funkci by nebylo napriklad zobrazeni h = {(1,a), (1,b), (2,b), (3,c)} prave proto, ze pro prvek 1 z mnoziny A existuji dva obrazy „a“ a „b“ z mnoziny B. (To, ze se prvek 1 i 2 zobrazi na prvek „b“ definici funkce neodporuje.)

kb

Marek Babák, 2008/05/27 09:12

Ja si myslím, že je to správně, zobrazení je relace A a B, přičemž jedinou podmínkou je jednoznačnost.
Kdežto funkce(v matematice) je zobrazení nějaké množiny(většinou čísel) do množiny čísel.
Tvůj příklad není ani zobrazení, protože nesplňuje podmínku jednoznačnosti.

Nicméně by nebylo od věci sem dát přesnou definici zobrazení a funkce. (optimálně takové, ve kterých se vyskytuje slovo relace)

Jan Palas, 2008/05/27 10:45

Ahoj, to co jsem napsal, je opravdu správně :) To, co uvádí Karel jako zobrazení h není zobrazení! Jedná se pouze o obecnou relaci. U funkce i zobrazení je požadavek jednoznačnosti.

Jinak definice funkcí (i se slovem relace :) se v článku vyskytuje, dokonce i v příslušné sekci :) Doplnil jsem tam ještě poznámku a věřím, že to takhle bude už jasnější. Pokud ne, pište a já doplním nebo doplňte sami.

Karel Barot, 2008/05/27 12:27

Diky za vyvedeni z omylu. Mylne jsem se domnival, ze zobrazeni je synonymum k relaci :).

Marek Babák, 2008/05/27 11:48

Jasne ale není tam definice zobrazení ;) edit: sory, koukam zes uz to tam dal, akorat jsem se uplne nezorientoval, protoze je to soucast dalsiho textu.

Michal bednář, 2008/06/04 10:44

MOzna bych jeste pridal pojem identicke zobrazeni a prazdne zobrazeni.

Winsik, 2008/06/04 12:33

Opravil jsem priklad na rozklad - R nebyla ekvivalence, nebyla reflexivni, pridan prvek 4,4

Dusan Katona, 2008/06/05 17:24

Mam pripomienku k casti „Funkce vs. zobrazení“, podla mojho nazoru je dost matuca…ja zobrazenie chapem ako totalnu funkciu, navyse definicia zobrazenia nie je „ku kazdemu x existuje _najvyse jedno_ y“, ale _prave jedno_ y (v tom note paragrafe je teda chyba).
Tiez nechapem, preco pri definicii funkce A→B musi byt B mnozina cisel (v skriptach som to nikde nenasiel). Taktiez veta „Tedy každá funkce je i zobrazení.“ je chybna, parcialna funkcia zobrazenie nie je.
Poprosim teda autora, nech tu cast „Funkce vs. zobrazení“ prehodnoti :)

Jan Palas, 2008/06/05 22:36

Děkuju za upozornění. Já jsem pochopil to „jednoznačné přiřazení“, o kterém píšu u zobrazení, tak, že to nemusí být totální. Nicméně jsem si to teď různě ověřoval a máš pravdu. Zobrazení musí být totální, takže definici jsem upravil a inkriminovanou větu pozměnil na „Každá totální funkce je i zobrazení,“ což už myslím je správně. Nicméně musím podotknout, že zrovna názvosloví v této oblasti (tj. funkce, zobrazení) není zrovna z nejustálenějších. V materiálech napříč českými VŠ je možné najít různé odlišnosti…

Dusan Katona, 2008/06/05 23:14

Ja som cerpal len zo skript Zakladov matematiky a tam to je uvedene takto…Inak mozes mi prosim este objasnit, preco pri funkcii musi byt obor hodnot mnozina cisel?

Jan Palas, 2008/06/06 10:10

Skripta Základů matematiky nemám, neboť jsem ten předmět neměl. A proč musí být obor hodnot množina čísel? Protože jsem to tak našel zadefinované v několika materiálech (např. MFF UK). Ano, je pravda, že v materiálech z FI se tato podmínka nikde neobjevuje, ale to souvisí asi s tím, jak jsem psal výše, že názvosloví v této oblasti není zrovna sjednocené…

No a ještě jsem to konzultoval se spolubydlící co studuje matiku na PřF a ta zase chápe tyto dva pojmy jako naprosto ekvivalentní, včetně toho, že zobrazení nemusí být totální. Shodli jsme se akorát na tom, že v názvosloví panuje chaos…

Pokud to chceš opravit v souladu toho, jak jsou tyto pojmy chápány v rámci předmětu Základy matematiky, určitě můžeš.

Dusan Katona, 2008/06/06 12:48

Diki za objasnenie :) opravovat to uz ale nebudem, necham to tak…

Petr Lorenc, 2008/06/06 10:13

Myslím, že by se k této otázce měly zmínit i injekce, surjekce a bijekce

Jan Palas, 2008/06/06 11:18

A ony tam nejsou?? :)

Adam Libuša, 2008/06/15 05:34

Nechýba medzi zoznamom operátorov symetrický rozdiel? [ A ÷ B = (A - B) \zjednotenie (B-A) ]

Marek Babák, 2008/06/15 10:45

Při učení mě napadly 3 věci:
1. by tu mohlo být úplně na začátku jakým způsobem množiny zadáváme (výčet prvků, definice, ještě nějak?)
2. N mi nepřipadá jako optimální označení nějaké obecné množiny, když se používá pro přirozená čísla, občas to v mate i když v kontextu je to správně (třeba R_N)
3. mě napadlo několik otázek k parciální funkci, takže je sem dávám jestli mi to někdo nepotvrdíte:

může být parciální funkce prostá? (spíš bych řekl, že ne)
může být parciální funkce surjektivní? (řekl bych že ano)

Andrej Podhradsky, 2008/06/15 15:10

Kazda totalna funkcia je zaroven aj parcialna funkcia ⇒ moze byt teda aj prosta aj surjektivna

Michal Lasak, 2008/06/17 13:44

Podla mna nemas pravdu
A = { 1, 2, 3}
B = { x, y}
f: A → B
1 → x
3 → y
==
f je parcialna a f nie je prosta, vies mi povedat, aku hodnotu ma f(2)?
Rovnako keby bola prosta, tak by platilo, ze |A| < = |B|, co takisto neplati.

Preto parcialna funkcia, ktora nie je totalna, urcite nie je prosta.
Parcialna funkcia, ktora je sucasne totalna, moze byt prosta.

Ondrej Bozek, 2008/06/20 11:45

Ja si myslim ze ta funkce je prosta. Neporusuje definici. Pro vsechy x!=y plati f(x)!=f(y). Rozhodne f(1)!=f(2)!=f(3). Nemuzu rict jakou hodnotu ma f(2) protoze neni def., ale rozhodne nema hodnotu f(1) ani f(3). Myslim si ze pokud f(2) je nedef. potom 2 logicky neni v definicnim oboru funkce(stejne jako 4,5,6…) a tedy to druhe tvrzeni |A|⇐|B| plati.

Petr Lorenc, 2008/06/22 09:46

A = { 1, 2, 3}
B = { x, y}
f: A → B
1 → x
3 → y
==
toto přece není funkce. Funkce totiž přiřazuje hodnoty KAŽDÉMU prvku z def. oboru (tedy z A)

Martin Vytrhlík, 2008/06/22 10:05

z definice parcialni fce vyplyva ze je to funce, protoze parcialni fce prirazuje hodnoty kazdemu prvku z def. oboru NEJVYSE JEDEN(takze klidne nula prvku)prvek z oboru hodnot.

Martin Minář, 2008/06/22 17:45

No podle me, by injektivni byt mela, v rozporu s definici to nijak neni. Ohanite se tu porovnanim |A|⇐|B|, ale to jaksi nikde u definice injektivni funkce nevidim. Intuitivne to sice plati, ale treba jen pro totalni funkce.

Mira Hlaváček, 2012/05/30 09:21

je (dle clanku na wikipedii: A partial function is said to be injective or surjective when the total function given by the restriction of the partial function to its domain of definition is.), prvky A, ktere nemaji definovany obraz se neuvazuji

Zly pes, 2008/06/17 22:00

preco teda tato funkcia je prosta
q = prazdna mnozina
priklad zo skript z UDI: q: q → {a,b}

a Tebou definovana f prosta nie je?
1 =/ 2 ⇒ f(1) sa nerovna comu ked f(2) def. nie je? jaku log. hodnotu ma toto tvrdenie?

Michal Lasak, 2008/06/17 22:58

No q je prosta, pretoze vyhovuje definicii. Pre kazde x,y patri q plati, ze ak x!=y tak sa nerovnaju ani obrazy. Kedze je q prazdna, tak to definiciu nema ako porusovat. Takisto ti plati |q| < = 2, pretoze |q|=0. Mnou definovana funkcia nie je prosta, pretoze neplati 3 < = 2. To je jednoznacny argument. A takisto si myslim, ze kedze f(2) nie je definovana, tak nevies porovnat obrazy 1 a 2, ale toto ti uz neviem dokazat :D

Ondrej Bozek, 2008/06/20 11:49

Funkce f cos napsal je prosta protoze definicni obor te funkce je {1,3} f(2) neni def. a tedy 2 neni v definicnim oboru funkce :). A potom 2 = 2.

Zly pes, 2008/06/17 23:03

tak to si mi teda vela toho nepovedal :-) )…bo to ma zaujimalo :-) )

Marek Blahuš, 2008/06/22 15:44

Jak je to tedy s tím zobrazením? Vidím, že v názvosloví panují neshody, ale zase mi přijde docela hloupé ho u zkoušky vůbec nezmínit. A přitom ve stávajícím stavu, po provedeném mazání nejistých částí, se teď v celém textu vyskytuje slovo „zobrazení“ jen jednou (a to jen v nadpise sekce ;-) ), ačkoliv pokud bychom to měli brát striktně podle definice této otázky, mělo by zaujímat až čtvrtinu textu, no a nebo by mělo být přeci jen alespoň zmíněno…

Jitka Pospíšilová, 2008/06/22 18:45

oddelala jsem ten odstavecek Funkce vs. zobrazeni na podnet pana Boudy… napisu mu mail, jestli bude mit cas, tak at mi napise, jak to tedy presne je s oznacenim funkce a zobrazeni… treba jeste dnes odpovi.

Marek Blahuš, 2008/06/22 18:54

Díky (a kdyby to nestihl dnes, určitě se dá odpovědět i zítra, i když to už se to pak bude hodit jen některým z nás). Myslím si, že je dost významené aspoň mít jasno v tom, co jim tam tedy o tom pojmu zobrazení mám říct (klidně i pokud by odpověď měla znít „vůbec nic“).

Jitka Pospíšilová, 2008/06/22 21:42

tak odpověď zní: „obvykle se to pouziva jako synonymum slova funkce, nekdy se to bere take jako totalni funkce. Dokonce i kdyz se podivate do nekterych hodne renomovanych encyklopedii matematiky tak uz jsem nasel jednu, kde to nedopatrenim definovali dvakrat jinak na ruznych mistech - pouzili dva vyse zminene vyznamy“

Jitka Pospíšilová, 2008/06/22 22:31

a jeste si dovoluji sem dat i dalsi dodatek pro ty, kteri by to chteli rozebirat:
„Zrejme se jedna o klasicky problem nezavisleho vyvoje terminologie v ruznych oborech matematiky. kdyz o tom tak premyslim, tak algebra (zejmena linearni) pouziva temer zasadne slovo zobrazeni (linearni zobrazeni vektorovych prostoru, ..) a prakticky nepouziva slovo funkce. Naopak matematicka analyza zase trva na pojmu funkce - uz jste nekdy derivovala zobrazeni ;-) ?

obcasna definice ze zobrazeni je proste muze pochazet prave z linearni algebry, kde se v drtive vetsine pripadu uvazuji jen totalni zobrazeni.

To jen kdyby se u statnic chtel nekdo rozhovorit“

Pan Bouda ale doporucuje se na toto tema spise zeptat doc. Fuchse, ktery se asi zabyval i historii matematiky, ten by vedel vice.

You could leave a comment if you were logged in.

home/inf/ap1.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru