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 1).

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 2).

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.

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.

1) Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 46
2) Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 47-48

Diskuze

, 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

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

, 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.

, 2008/05/27 12:27

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

, 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.

, 2008/06/04 10:44

MOzna bych jeste pridal pojem identicke zobrazeni a prazdne zobrazeni.

, 2008/06/04 12:33

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

, 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 :)

, 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…

, 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?

, 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š.

, 2008/06/06 12:48

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

, 2008/06/06 10:13

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

, 2008/06/06 11:18

A ony tam nejsou?? :)

, 2008/06/15 05:34

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

, 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 RN)
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:

  1. může být parciální funkce prostá? (spíš bych řekl, že ne)
  2. může být parciální funkce surjektivní? (řekl bych že ano)
, 2008/06/15 15:10

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

, 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.

, 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.

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

, 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.

, 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.

, 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

, 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?

, 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


, 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.

, 2008/06/17 23:03

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

, 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…

, 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.

, 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“).

, 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“


, 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: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0