Pavel Horák ZÁKLADY MATEMATIKY UČEBNÍ TEXT 2005 ÚVOD Tento učební text je určen pro předmět Ml 125 Základy matematiky, který je povinným předmětem v bakalářském studijním programu Matematika, studijních oborech Matematika se zaměřením na vzdělávání a Matematika pro víceoborové studium na přírodovědecké fakultě Masarykovy Univerzity v Brně. Může být použit také v předmětu M1120 Základy matematiky, který je povinným předmětem ve studijních oborech Obecná matematika a Profesní matematika bakalářského studijního programu Matematika a ve všech studijních oborech studijnho programu Aplikovaná matematika, včetně distanční formy studia na přírodovědecké fakultě Masarykovy Univerzity v Brně. Jedná se o úvodní jednosemestrální kurz, který je doporučen absolvovat v 1. semestru studia. Předmět Základy matematiky je ve výše uvedených studijních oborech úvodním matematickým kurzem, jehož cílem je zopakovat a rozšířit středoškolskou látku z matematiky a následně probrat některá další témata, zejména algebraického charakteru. Dalším cílem kurzu je pokud možno "srovnat" matematické znalosti studentů, kteří přicházejí z různých středních škol, mnohdy s různou úrovní a intenzitou výuky matematiky. Z tohoto důvodu je výklad orientován spíše na studenty s chatrnějšími matematickými znalostmi. Ovšem i u těchto studentů se předpokládá, že vlastní pílí svoje případné nedostatky ve středoškolských znalostech matematiky zacelí. Přehled středoškolského učiva z matematiky je možno nalézt například v publikaci "Odmaturuj z matematiky", autorů P. Čermáka a P. Červinkové, kterou vydalo nakladatelství Di-daktis (druhé, opravené vydání v roce 2003). Tuto nebo podobnou knížku by si měli pořídit všichni studenti, kteří cítí, že v jejich středoškolských matematických znalostech jsou mezery. Učební text předpokládá pouze elementární znalosti základních matematických pojmů a jejich vlastností, vyučovaných na každé střední škole. V textu je užívána běžná symbolika známá ze střední školy. Nově zaváděná označení jsou v textu vždy řádně vysvětlena. Vzhledem k tomu, že pro mnohé čtenáře může být tento text prvním matematickým textem, kterým se budou opravdu vážně zabývat, je výklad veden co možná nejpodrobnější a nejelementárnější formou. Téměř všechna tvrzení jsou podrobně dokazována s cílem, aby si čtenář dobře osvojil základní matematické postupy a dovednosti, které bude následně během dalšího studia mnohokrát používat. Konec důkazu je v textu opticky označen symbolem ■ , umístěným na konci řádku. Pro označování základních číselných množin jsou v textu použity následující standardní symboly: N ... množina všech přirozených čísel Z ... množina všech celých čísel Q ... množina všech racionálních čísel R ... množina všech reálných čísel C ... množina všech komplexních čísel. 1 I. OPAKOVÁNÍ A DOPLNĚNÍ STŘEDOŠKOLSKÉ LÁTKY 1. Základní logické pojmy. V matematice se zabýváme studiem vlastností různých objektů a vztahů mezi nimi. K označování matematických objektů užíváme různých symbolů. Některé z nich mají pevný význam a nazýváme je konstanty (například symboly 1, 7r, y/2, atd.). Jiné symboly takový přesně stanovený význam nemají, ale můžeme za ně konstanty vhodným způsobem dosazovat a nazýváme je proměnné. U proměnných musí být vždy vymezeny ty objekty, které je možno za proměnné dosazovat (například "přirozené číslo x", "přímka p", atd.). Výrok je sdělení, o němž má smysl říci, že je pravdivé nebo nepravdivé. Hovoříme pak o pravdivém výroku nebo nepravdivém výroku. Například sdělení "Praha má více než tisíc obyvatel" je pravdivým výrokem, zatímco sdělení "Číslo sedm je sudé" je nepravdivým výrokem. Může se také stát, že dané sdělení je výrokem, o němž však momentálně neumíme rozhodnout, zdali pravdivým či nepravdivým. Takovým je například výrok "Mimo naši sluneční soustavu žijí myslící bytosti". Každému výroku V se přiřazuje jeho pravdivostní hodnota p (V) takto: je - li výrok V pravdivý, klademe p (V) = 1 a je- li výrok V nepravdivý, klademe p (V) = 0 Logické spojky nám umožňují z jednotlivých výroků tvořit další výroky. Nejběžněji se používají následující logické spojky, které mají své ustálené názvy i označení, jak je uvedeno v následující tabulce (kde A, B značí libovolné výroky). Název logické spojky Označení Slovní vyjádření negace -^A není pravda, že A konjunkce AAB A a (současně) B disjunkce Aw B A nebo B implikace A^B jestliže A, pak B ekvivalence A^B A právě když B. Každou z uvedených logických spojek popíšeme nyní tak, že uvedeme, jaké pravdivostní hodnoty přiřazujeme výroku, utvořenému s její pomocí (v závislosti na pravdivostních hodnotách výchozích výroků A, B). Vznikne tak tzv. tabulka pravdivostních hodnot, která má pro negaci dva řádky a pro ostatní uvedené logické spojky čtyři řádky. P (A) p(B) p (A AB) p (A V B) p(A=>B) p(A^B) 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 2 p (A) p(^A) 1 0 0 1 Rozeberme si nyní podrobněji jednotlivé logické spojky. Negace libovolného výroku A se dá bez problémů správně vytvořit obratem "není pravda, že A". Tato formulace bývá však často jazykově poněkud kostrbatá, a proto se snažíme i v matematice tvořit negace bez užití tohoto obratu. Například místo "není pravda, že číslo 7 je dělitelné třemi" řekneme raději "číslo 7 není dělitelné třemi". Konjunkce výroků působí obvykle nejméně potíží. Z tabulky vidíme, že výrok Af\B je pravdivý jedině v případě, že oba výroky A, B jsou pravdivé. Disjunkce A V B je pravdivá, je-li pravdivý alespoň jeden z výroků A, B (to jest jeden, druhý nebo oba dva). Zde tedy při použití spojky "nebo" dochází někdy k odchylce od běžné hovorové řeči, v níž se spojka "nebo" velmi často používá ve smyslu vylučovacím ("Budu doma nebo ve škole"). Implikace A =>• B je nepravdivá pouze v případě, když výrok A je pravdivý a výrok B je nepravdivý. Ve všech ostatních případech je implikace pravdivá. Je nutné si zejména dobře uvědomit, že implikace A =>• B je vždy pravdivá v případě, když výrok A je nepravdivý (a to bez ohledu na pravdivostní hodnotu výroku B). Je-li implikace A =>• B pravdivá, pak říkáme též, že A je dostatečná podmínka pro B a dále říkáme, že B je nutná podmínka pro A. Ekvivalence A -<=> B je pravdivá právě v případě, že oba výroky A, B mají stejnou pravdivostní hodnotu, tzn. jsou oba současně pravdivé nebo současně nepravdivé. Výroky A, B se pak též nazývají ekvivalentní výroky. * * * V matematických úvahách můžeme tedy daný výrok nahradit jiným výrokem, který je s ním ekvivalentní. Velmi často se jedná o negaci konjunkce dvou výroků a negaci disjunkce dvou výroků, pro které platí: ( -. (A A B)) je ekvivalentní s ((->A) V (-.5)) ( -. (A V B)) je ekvivalentní s ((-.^4) A (->B)). O tom, že dané výroky jsou skutečně ekvivalentní, se můžeme přesvědčit pomocí tabulky pravdivostních hodnot těchto výroků. Utvořme takovou tabulku pro první z uvedených vztahů. P (A) p(B) p (A AB) P HA A B)) P h A) p H*)) p(^A V -iB) 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 Pro druhý vztah se odpovídající tabulka pravdivostních hodnot vytvoří analogicky (udělejte si sami!). 3 Podobným způsobem lze ukázat, že ekvivalenci dvou výroků je možno vyjádřit pomocí konjunkce obou implikací těchto výroků, tzn. (A o B) je ekvivalentní s ((A => B) A (B =>• A)) což je možno opět ověřit pomocí příslušné tabulky pravdivostních hodnot. Další důležitý vztah, který budeme v dalším velmi často využívat se týká implikací. Platí totiž: (A =>• B) je ekvivalentní s ((->B) =>• (ni)) tzn. implikace A =>• B je z logického hlediska totéž co implikace —>B =>• -*A. Pravdivost tohoto tvrzení okamžitě vyplývá z níže uvedené tabulky. Poznamenejme ještě, že implikaci —>B =>• —>A se říká obměna implikace A =>• B . p (A) p (B) p (A => B) P H?) PN) p (-,£ => -ni) 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 Podobným způsobem se dá odvodit ekvivalentnost celé řady výroků složených ze tří výroků A, B, C. Pro ilustraci uveďme dvě dvojice ekvivalentních výroků, s nimiž se při logických úvahách poměrně často setkáváme. Platí: ((A A (BvC))) je ekvivalentní s ((A A B) V (A AC))) ((A V (BAC))) je ekvivalentní s ((A V B) A (Av C))) Ekvivalentnost uvedených dvojic výroků se dokáže stejným způsobem, jako dříve, tzn. pomocí tabulky pravdivostních hodnot, která v tomto případě bude mít osm řádků. Sestavíme tuto tabulku tentokrát pro druhou dvojici výroků. Pro první dvojici se sestaví analogicky (proveďte si sami!). p(A) p(B) p(C) p(BAC) p(Av(BAC)) p(AvB) p(AvC) P({AVB)A{AVC)) 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 * * * Všimněme si, že sdělení obsahující nějakou proměnnou, například "celé číslo x je větší než 5", není výrokem. Z tohoto sdělení se stane výrok (ať už pravdivý, či nepravdivý) teprve tehdy, až za proměnnou x dosadíme nějakou konstantu z příslušné 4 množiny, z níž můžeme konstanty volit, v našem případě tedy nějaké konkrétní celé číslo. Přitom je zřejmé, že takovéto sdělení může obsahovat případně i více proměnných, například: "reálné číslo x je menší než reálné číslo y" obsahuje dvě proměnné x, y. Sdělení obsahující proměnné, z něhož se stane výrok teprve po dosazení (přípustných) konstant za příslušné proměnné, se nazývá výroková funkce. Z výrokové funkce můžeme tedy utvořit výrok tím, že za všechny proměnné dosadíme (přípustné) konstanty. Další možností, jak z výrokové funkce utvoříme výrok je tzv. kvantifikace proměnných. Ta spočívá v tom, že nějakým způsobem udáme počet objektů, pro něž z výrokové funkce obdržíme výrok. Ta část výroku, v níž je tento počet udáván, se nazývá kvantifikátor. Příkladem kvantifikátorů jsou obraty: "každý", "nejvýše jeden", "alespoň jeden", "právě jeden", "právě čtyři", "nekonečně mnoho", "konečně mnoho", atd. Konkrétně, z výše uvedené výrokové funkce "celé číslo x je větší než 5" je možno například utvořit následující kvantifikované výroky: "alespoň jedno celé číslo je větší než 5" (pravdivý výrok) "nejvýše jedno celé číslo je větší než 5" (nepravdivý výrok) "každé celé číslo je větší než 5" (nepravdivý výrok). Poznamenejme ještě, že některé kvantifikátory můžeme vyjádřit několika různými slovními obraty se stejným významem. Například místo "alespoň jeden" můžeme stejně dobře říci "existuje" či "jeden nebo více". Podobně místo "nejvýše jeden" můžeme říci "žádný nebo jeden". V každém případě si při použití jakéhokoliv kvantifikátoru musíme vždy velmi dobře rozmyslet přesný význam toho, co říkáme. Nejčastěji používané kvantifikátory mají svá označení. Kvantifikátor "každý" se též nazývá obecný kvantifikátor a označuje symbolem V. Podobně, kvantifikátor "existuje" se nazývá existenční kvantifikátor a označuje symbolem 3. V matematických úvahách je třeba velmi často provádět negace kvantifikovaných výroků. Obvykle nepoužíváme matematicky "bezpečného", ale gramaticky nepěkného obratu "není pravda, že ...". Ukažme si nyní schematicky princip tvoření negací výroků s obecnými a existenčními kvantifikátory, což jsou případy, s nimiž se v praxi nejčastěji setkáváme: výrok s obecným kvantifikátorem: "pro každý prvek z oboru U platí V" negace tohoto výroku: "existuje prvek z oboru U, pro který neplatí V" výrok s existenčním kvantifikátorem: "existuje prvek z oboru U, pro který platí V" negace tohoto výroku: "pro každý prvek z oboru U neplatí V" přičemž v posledním případě je samozřejmě vhodné slovo "každý" nahradit gramaticky správnějším slovem "žádný". K tomu ještě poznamenejme, že při tvoření kvantifikovaných výroků a jejich negací můžeme samozřejmě užít i jiných gramatických obratů, které však musí zachovávat daný smysl. Ukažme si to na následujícím příkladu. Kvantifikovaný výrok: "každé nové auto je červené" můžeme přeformulovat například do tvaru "všechna nová auta jsou červená". Negací tohoto kvantifikovaného 5 výroku pak bude výrok "existuje nové auto, které není červené", který můžeme případně přeformulovat do tvaru "alespoň jedno nové auto není červené". * * * Na závěr této kapitoly si ještě stručně všimneme struktury matematických tvrzení a jejich důkazů. Této problematice je nutné důkladně porozumět a při dalším studiu tohoto textu se k ní stále vracet. Matematická tvrzení, kterým se také říká "věty", mají nejčastěji tvar implikace výroků nebo ekvivalence výroků. Rozeberme si oba případy a ukažme, jak se taková tvrzení obvykle dokazují. Matematická věta tvaru implikace má tvar P =>• T, přičemž výrok P se nazývá předpokladem této věty a výrok T se nazývá tvrzením věty. K důkazu matematických vět tvaru implikace P =>• T je možno použít různých důkazových metod. Nejčastější jsou: a) důkaz přímý, který spočívá v tom, že z platnosti výroku P (předpokladu) řadou platných implikací odvodíme platnost výroku T (tvrzení). Jinak řečeno, hledáme výroky Ai,A2, ... , An tak, že platí: P =>. A1 A A1 =>- A2 A ... A An_x =>• An A An =>• T. b) důkaz nepřímý spočívá v přímém důkazu tvrzení —T =>• -P . Zde tedy využíváme již dokázaného faktu, že implikace P =>• T a její obměna —T =>• -P jsou ekvivalentní výroky. Při důkazu touto metodou tedy předpokládáme, že je pravdivý výrok -iT a řadou platných implikací dokážeme platnost výroku -P. Jinak řečeno, z negace tvrzení dokážeme (řadou platných implikací) negaci předpokladu. Určitou modifikací nepřímého důkazu je tzv. důkaz sporem, kdy předpokládáme, že platí předpoklad P a neplatí tvrzení T. Následně potom řadou platných implikací odvodíme spor. Přitom sporem rozumíme situaci, kdy nějaký výrok a jeho negace mají být současně pravdivé - je zřejmé, že tato situace nemůže nastat. Matematická věta tvaru ekvivalence má tvar A -<=> B a dokazuje se většinou tak, že dokážeme jednak platnost implikace A =>• B a dále pak platnost implikace B =>• A, a to metodami popsanými výše. Uvědomme si, že správnost této úvahy vyplývá z dříve dokázaného faktu, že ekvivalence A <&■ B je logicky ekvivalentní s konjunkcí implikací (A=>B) A (B^A). Poměrně často se můžeme setkat s tvrzeními, která je možno považovat za jisté zobecnění matematických vět typu ekvivalence. Jedná se o věty tvaru "Jestliže platí výrok P, potom výroky Ai,A2, ... , An jsou ekvivalentní". K tomu nejprve poznamenejme, že pojem ekvivalentních výroků, který jsme zavedli pro dva výroky, můžeme rozšířit na libovolný konečný počet výroků Ai,A2, ... , An takto: řekneme, že výroky A\, A2, ... , An jsou ekvivalentní, jestliže platí Ai <ŕ4> Aj pro každé i,j = l,...,n. 6 Větu tohoto tvaru většinou nedokazujeme ověřováním všech ekvivalencí Ai A j pro každé i^j (kterých je celkem n-(n—1)), ale obvykle postupujeme tak, že dokážeme platnost pouze n implikací tvaru: AX^A2} A2^A3, ... , An_x^Ani An^Ax. Je jednoduché ukázat, že odsud již plyne ekvivalentnost všech výroků Ai,A2, ... , An. Poznamenejme ještě, že zvolené pořadí výroků v uvedených implikacích není závazné. Bylo by také možné dokazovat libovolných n implikací Ai =>• A j (i ^ j), v nichž se každý z výroků A\,A2, ... ,An objeví právě jednou jako předpoklad a právě jednou jako tvrzení a to tak, že je-li daný výrok v jedné implikaci tvrzením, pak je v následující implikaci předpokladem. Nepřesně, ale názorně řečeno je pouze nutné, aby se nám "kruh implikací uzavřel". Zvláštním typem důkazu matematické věty je důkaz matematickou indukcí. Touto metodou není možné dokazovat jakoukoliv matematickou větu, nýbrž jenom ty věty, které tvrdí, že za daných předpokladů platí výrok V(n), a to pro všechna celá čísla n > no, kde no je nějaké pevně dané celé číslo. Nejčastěji je no = 1. Důkaz takové věty matematickou indukcí pak probíhá ve dvou krocích, následujícím způsobem: za daných předpokladů a) dokážeme platnost výroku V (no) ß) předpokládáme, že výrok V(n) platí pro n = no, no + 1, ... , k a za tohoto předpokladu dokážeme platnost výroku V(k + 1). Věta je pak dokázána. Přepoklad vyslovený v ß) se nazývá indukční předpoklad. Poznamenejme, že ve většině důkazů matematickou indukcí se z indukčního předpokladu využije pouze to, že platí V(k) a z platnosti V(k) se pak již odvodí požadovaná platnost V(k + 1). Mohlo by se tedy zdát, že stačí indukční předpoklad "redukovat" na předpoklad platnosti V(k). V dalším se však setkáme s matematickými větami, které se budou dokazovat matematickou indukcí, přičemž taková "redukce" indukčního předpokladu nebude možná. 7 2. Základní množinové pojmy. Pojem množiny je základním pojmem celé matematiky. Přitom pod pojmem množina budeme rozumět libovolně, jednoznačně vymezený souhrn nějakých objektů, které budeme nazývat prvky množiny. Pro názornost budeme množiny obvykle označovat velkými latinskými písmeny a prvky množin pak malými latinskými písmeny. Základní a přitom vlastně jedinou vlastností množin je, že mají prvky. Skutečnost, že objekt x je prvkem množiny A (tzn. x patří do A) budeme zapisovat: x G A. Skutečnost, že objekt x není prvkem množiny A (tzn. x nepatří do A) pak budeme zapisovat: x ^ A. Množina je jednoznačně určená svými prvky. Proto dvě množiny, nezávisle na způsobu jejich zadání, považujeme za stejné, právě když mají stejné prvky. Tato vlastnost množin se nazývá extenzionalita. Můžeme tedy psát: A = B o (Vx) (x e A o x e B). Existuje množina, která se vyznačuje tím, že nemá žádné prvky. Nazývá se prázdná množina a označuje se symbolem 0. Množina se nazývá konečná, jestliže je možné ji zadat vyjmenováním všech jejích prvků. Je-li A konečná množina aai,02,...,a„ jsou všechny její prvky, pak píšeme A = {ai,a2, ... ,an}. Z extenzionality vyplývá, že nezáleží na pořadí v jakém vyjmenováváme, resp. zapisujeme prvky množiny A. Mohlo by se však stát, že uvedená množina A má méně než n prvků; v takovém případě se některé z prvků 0,1,0,2, ■ ■ ■ ,an opakují. Obvykle pak v zápise množiny A opakující se prvky až na jeden vynecháváme. Například tedy: {x, y} = {y, x} a pokud je x = y, potom {x, y} = {x} = {y}. Kromě konečných množin se v matematice můžeme velmi často setkat i s neprázdnou množinou, kterou není možné zadat vyjmenováním všech jejích jednotlivých prvků. Taková množina se nazývá nekonečná. Nekonečné množiny obvykle zadáváme nějakou jejich charakteristickou vlastností. Jestliže P(x) je nějaká vlastnost, pak píšeme X = {x \ P(x)}, čími, myslíme, že pro libovolné x platí: x E X právě tehdy, když x splňuje P(x). Například vlastností "x je sudé celé číslo" je určena množina všech celých sudých čísel. Poznamenejme, že z rovnosti X = {x | P(x) } nemusí automaticky vyplývat, že množina X je nekonečná - stejně dobře může být konečná nebo dokonce prázdná. Například množina X = {x | x eZ A x2-l = 0} je dvouprvková množina sestávající z čísel 1 a -1, tzn. X = {1, — 1}, zatímco množina X = {x | x eZ A x2 + l = 0} je prázdnou množinou. 8 Na tomto místě je nutné upozornit na to, že výše uvedené vymezení pojmu množiny není vlastně přesnou definicí a vede k rozporům, protože jsou "souhrny", které za množiny považovat nemůžeme. Nejjednoduší příklad takové "zakázané množiny" byl nalezen zhruba před sto lety. Je to souhrn M = { X | X G" X } všech množin X, které neobsahují sebe jako prvek. Pokud by M byla množina, pak si můžeme položit otázku, zda M G M či nikoliv. Jestliže však MgM, pak podle definice je M^ M, což je spor. Jestliže by bylo M G" M, pak podle definice dostáváme M E M, což je opět spor. Řešení problémů spojených s definicí pojmu množiny podává speciální matematická disciplína, axiomatická teorie množin, kterou se však v tomto textu nebudeme zabývat. Budeme pracovat v tzv. naivní teorii množin, která je vybudována na základě výše uvedeného nepřesného vymezení pojmu množiny, přičemž však naše úvahy budou z hlediska teorie množin legální. Říkáme, že množina A je podmnožina množiny B a píšeme AC5, jestliže libovolný prvek množiny A je zároveň prvkem množiny B. Vztah C se nazývá množinová inkluze. Jestliže A C\ B a A yí B, pak říkáme, že A je vlastní podmnožina množiny B a píšeme Ac B. Máme-li dokázat, že A C B pak postupujeme tak, že vezmeme libovolný prvek x E A a dokážeme, že x E B. Jestliže množina A není podmnožinou množiny B, pak budeme psát A % B. Chceme-li dokázat, že A % B, pak (podle předchozích úvah o negacích kvantifikovaných výroků) dokazujeme, že existuje prvek x takový, že x E A a zároveň x G" B, a to nejlépe tak, že tento prvek konkrétně nalezneme. Pro libovolné množiny A, B, C zřejmě platí: AC A, |Ci, (A C B A B C C) => AC C, A = B <& (ACBaBCA). Důležitý je zejména poslední z výše uvedených vztahů, pomocí kterého obvykle dokazujeme rovnost dvou množin A, B. Důkaz vedeme tak, že dokážeme nejdříve inkluzi A C B a, potom inkluzi B C A. Jsou-li A, B množiny, pak můžeme utvořit další množiny AuB = {x\xeAVxeB} A n B = {x \ x E A A x E B} A-B = {x\xeA A x g B} které postupně nazýváme sjednocení, průnik a rozdíl množin A a B. Poznamenejme ještě, že při různých množinových úvahách je třeba vyjádřit nejenom skutečnost, daný prvek ve sjednocení, průniku nebo rozdílu množin leží, ale často také skutečnost, že v nich neleží. V takových případech zřejmě platí: x ^ A U B právě když x G" A A x ^ B x E1 A DB právě když x G" A V x ^ B x G" A — B právě když x G" A V x E B . Pro sjednocení, průnik a rozdíl množin platí celá řada tvrzení, z nichž si některé uvedeme v následující větě. 9 Věta 2.1. Necht A, B, C jsou libovolné množiny. Pak platí: 1. AuB = BuA 2. AnB = BnA 3. (AuB)uC = Au(BuC) 4. (AnB)nC = An(BnC) 5. An(BuC) = (AnB)u(AnC) 6. Au(5n(ľ) = (Au B) n (Au C) 7. A-(B U C) = (A-B) n (A-C) 8. A-(B n C) = (A - B) U (A - C) Důkaz. Důkaz všech uvedených tvrzení se provádí stejným způsobem, a to dokazováním příslušných množinových inkluzí. Pro ilustraci dokážeme například vztah 8: nC": x eA-(BnC) => xeAAx^(BhC) => xeA A (x^B V x^C) => => (x E A A x £" B) V (x E A A x £ C) =>• x e (A- B) y x e (A-C) =>• => x G (A - B) U (A - C). nD": x E (A-B) U (A-C) => xE(A-B) V xE(A-C) => =>- (x E A A x (£ B) V (x E A A x (£ C) =>• xG^A(x^JBVx^C)^> 4 lÉÍAi^(BnC) 4 iGÍ-(BílC). ■ Pokud si pozorně prohlédneme předchozí důkaz, zjistíme, že jeho druhá část je pouze "obrácením" části první. Bylo by tedy možné provést důkaz "najednou" tak, že bychom napsali pouze jeho první část a všechny symboly =>• pro implikace bychom nahradili symboly <^ pro ekvivalence. Tento postup však nelze aplikovat vždycky, a proto zejména začátečník by měl množinovou rovnost napoprvé vždy dokazovat pomocí důkazu dvou množinových inkluzí. Pojem sjednocení a průniku dvou množin je možné zobecnit. Je-li 7^0 libovolná (tzv. indexová) množina a Ai je množina pro každé i E I, pak sjednocení množin Ai je množina |J Ai = {x \ 3Íq E I : x E Ai0} i€l průnik množin Ai je množina P| Aj = { a: | M i E I : x E Ai}. iei Uvědomme si, že předchozí definice zahrnují sjednocení a průnik jak dvou množin, tak libovolného konečného počtu množin a případně i nekonečného počtu množin. To, který z těchto případů nastane, záleží zřejmě na indexové množině 7. V případě, že 7 je konečná množina, například 7 = {1, 2,.. .n}, píšeme též A1 U A2 U ■ ■ ■ U An , resp. Ax n A2 n • • • n Ar oo oo V případě, že je 7 = N, píšeme též [J Ai, resp. f] Ai. Přitom je nutné zdůraznit, že í=i i=i poslední dva zápisy samozřejmě není možné použít univerzálně pro jakoukoliv nekonečnou indexovou množinu 7. 10 V matematice se poměrně často setkáváme s množinami, jejichž prvky jsou zase množiny. Pro takovou množinu budeme používat názvu systém množin. Příklad 2.1. Nechť A je libovolná množina. Pak všechny podmnožiny množiny A tvoří systém množin, který budeme nazývat systém všech podmnožin množiny A a označovat symbolem 2A. Konkrétně, například pro A = {x, y1 z} je 2A = {Q ,{x} ,{y} ,{z} ,{x,y} ,{x,z} ,{y,z} ,{x,y,z}}. Podobně například pro A = 0 je 2® = {0}, tzn. 2® je jednoprvkovou množinou, jejímž jediným prvkem je prázdná množina. Obecněji, je-li množina A konečná, o n prvcích, potom množina 2A je jistě také konečná a lze ukázat, že má 2n prvků. Tento fakt do jisté míry zdůvodňuje použité označení 2A pro systém všech podmnožin množiny A. Na druhé straně, je-li množina A nekonečná, pak je množina 2A samozřejmě také nekonečná. Na závěr tohoto paragrafu si ještě zavedeme pojem kartézského součinu dvou množin. K tomu budeme potřebovat pojem uspořádaná dvojice prvků. Pro naše účely postačí intuitivní představa, že ke každým dvěma prvkům x,y lze přiřadit nový prvek (x, y), nazývaný uspořádanou dvojicí tak, že dvě uspořádané dvojice (x, y) a (r, s) jsou si rovny, právě když x = r a y = s. V uspořádané dvojici (x, y) tedy záleží na pořadí prvků x, y, přičemž prvek x se nazývá první složka a prvek y se nazývá druhá složka uspořádané dvojice (x,y). Analogickým způsobem lze pro libovolné n > 2 zavést pojem uspořádaná n-tice prvků, kterou označujeme symbolem (ai, a2,... an). Přitom klademe (ai, a2, • • • , an) = (5i, b2, ... , bn) právě když ai = bľ A a2 = b2 A ... A an = bn , tzn. dvě uspořádané n-tice prvků se rovnají právě když se rovnají jejich odpovídající si složky. Jestliže A, B jsou libovolné množiny, pak množina Ax B = {(x, y) I x G A, y e B} se nazývá kartézský součin množin A, B (v tomto pořadí). Z předchozí definice je zřejmé, že v kartézském součinu záleží na pořadí množin, tzn. množiny A x B a B x A jsou obecně různé. Je-li například A = {a} a B = {x, y} , pak je: Ax B = {(a,x),(a,y)} a B x A = {(x, a), (y, a)}, a tedy Ax B ^ B x A. Dále je zřejmé, že je-li některá z množin A, B prázdná, tzn. A = 0 nebo 5 = 0, pak i jejich kartézský součin je prázdná množina, tzn. A x B = 0. Analogickým způsobem zavádíme pro libovolné n > 2 kartézský součin množin Ai,A2, ... , An , jako množinu Ax x A2 x ... x An = { (ai, a2, ... , an) \ a,i e A{, i = 1, 2, ... , n } . 11 Je-li Ai = A2 = ... = An = A, pak příslušný kartézský součin označujeme symbolem An a nazýváme jej n-tá kartézská mocnina množiny A. Například tedy kartézská mocnina R3 = {(x,y,z) | x, |/, z G M libovolné } je množinou všech uspořádaných trojic reálných čísel. Pro sjednocení, průnik, rozdíl a kartézský součin množin opět platí celá řada tvrzení. Některé z nich uvedeme v následující větě. Věta 2.2. Nechť A, B, C jsou libovolné množiny. Pak platí: 1. Ax(BuC) = (AxB)u(AxC) 2. (A U B) x C = (A x C) U (B x C) 3. A x (B n C) = (A x B) n (A x C) 4. (A n B) x C = (A x C) n (B x C) 5. A x (B-C) = (A x B)-(A x C) 6. (A - B) x C = (A x C) - (B x C) Důkaz. Důkaz všech uvedených tvrzení se opět provede technickým rozepsáním příslušných množinových inkluzí. Pro ilustraci dokažme například vztah 5 : "C": (x,y) G Ax (B-C) => x e A A y e (B-C) => x e A A {y e B A y ^ C) => => (x, y) G (A x B) A (x, y) £ (A x C) => (x, y) e {A x B) - {A x C). "D": (x, y) e (A x B)-(A x C) => (x, y) e (A x B) A (x, y) & (A x C) => =>- (xeAAyeB)A(x^Ayy^C) =>• (xeAAyeBAx^A)V V (x e A A y e B A y £ C) ^ x e A A (y e B A y £ C) => => x e A A y e (B-C) => (x, y) eAx (B - C). M Poznamenejme, že v některých množinových rovnostech uvedených ve větách 2.1. a 2.2. je možné sjednocení a průnik dvou množin nahradit "obecným" sjednocením a průnikem množin, jak je vidět z následující věty. Věta 2.3. Nechť I je neprázdná indexová množina a nechť A, B i jsou množiny, pro každé i G /. Pak platí: 2. AU C\Bi = C\(AuBi) i£l i£l 4. A - p Bi = U (A - BA iei i£i 6. A x H Bi = p (A x Bt). i£l i£l Důkaz. Důkaz všech uvedených tvrzení se, stejně jako v předchozích větách, provede technickým rozepsáním příslušných množinových inkluzí. Pro ilustraci tentokrát dokažme například vztah 1: i. A n U Bi = i£l i£l 3. A - J Bi : i£l = f](A-Bi i£l 5. A x J Bi --i£l = \J(AxB< i£l 12 nc": x e A n {J Bi =>• x e A a x e {J Bi =>• x e A a 3i0 e I ■. x e Bio =>• => 3i0 E I : x E AnBio => xG|J(-4n^)- i£l VD": x e \J(AnBi) =>• 3i0 e I : x e AnBio =>• x e A A 3i0 e I : x e Bio =>• =^ x e A a x e \J Bi ^ x e An \J Bi. ■ Závěrem našich úvodních úvah o množinách je nutné varovat před představou, že všechny jednoduché množinové vztahy, které "pěkně vypadají" musí vždy také platit. Například rovnost: A — (B — C) = (A — B) — C obecně neplatí. To, že uvedená rovnost neplatí, dokazujeme tak, že uvedeme jeden konkrétní příklad množin A, B, C, které tuto rovnost nesplňují. V našem případě je to celkem jednoduché: stačí vzít například dva různé prvky a, b a utvořit množiny A = {a} , B = {b} , C = {a}. Při této volbě je pak A — (B — C) = {a}, zatímco (^4 — B) — C = 0, což dokazuje, že uvedená rovnost skutečně neplatí. To, že neplatí rovnost daných množin samozřejmě nemusí nutně znamenat, že neplatí ani jedna z obou inkluzi. Uvědomme si, že A = B <=> (AC B A B C A) což tedy znamená, že A i- B <& (A%B V B%A). Například v přechozí úvaze jsme uvedením konkrétního protipříkladu dokázali, že neplatí množinová inkluze A — (B — C) C (A — B)—C, a tedy neplatí příslušná množinová rovnost. Pokud jde o opačnou inkluzi, tj. A — (B — C) D (A — B) — C, tak ta v uvedeném případě platí (dokažte si sami rozepsáním). 13 3. Základní číselné obory. Pojem čísla je základním matematickým pojmem, s nímž se setkáváme již od předškolního věku. Na základní a střední škole se čísla a operace s nimi zavádějí víceméně intuitivně a žáci postupně poznávají jejich důležité vlastnosti. V této kapitole zavedeme označení, resp. popis základních číselných oborů a podrobněji se zmíníme pouze o vlastnostech komplexních čísel. Čísla přirozená označujeme symbolem N, přičemž N = {1,2,3, ... }. Poznamenejme, že někdy se mezi přirozená čísla zahrnuje i číslo nula. Jde o věc dohody, my v tomto textu nulu do přirozených čísel zahrnovat nebudeme. Čísla celá označujeme symbolem Z, přičemž Z = { ... — 3, —2, —1, 0,1, 2, 3, ... } . Základními vlastnostmi celých čísel se budeme podrobněji zabývat v následující kapitole. Čísla racionální označujeme symbolem Q. Jedná se o čísla, která lze vyjádřit ve tvaru zlomku, kde čitatel i jmenovatel jsou celá čísla, přičemž jmenovatel je různý od nuly. Připomeňme, že každé racionální číslo má nekonečně mnoho možných vyjádření uvedeného tvaru, např. 2-24-46-6 3 ' ^3 ' 6 ' ^6 ' 9 ' ^9 ' '" Použijeme-li pro racionální číslo zápis, kde se ve jmenovateli vyskytuje nejmenší kladné číslo, pak říkáme, že jsme dané číslo vyjádřili v základním tvaru. Takové vyjádření je pro každé racionální číslo zřejmě jediné. V předchozím příkladu je to zápis |. Čísla reálná označujeme symbolem EL Množina R reálných čísel se skládá ze dvou disjunktních podmnožin, z nichž jedna je tvořena čísly racionálními a druhá čísly iracionálními. Přitom iracionální čísla nelze vyjádřit jako podíl celých čísel, jsou to například čísla \Í2 , y/b , 7T , log 6 , sin ^tt , atd. Množina R má jednu důležitou vlastnost: existuje vzájemně jednoznačné přiřazení všech reálných čísel a všech bodů libovolné přímky. Jinak řečeno, každému reálnému číslu lze přiřadit jediný bod zvolené přímky a také obráceně, každému bodu této přímky odpovídá jediné reálné číslo. Podrobným studiem vlastností reálných čísel se zabývá základní kurz matematické analýzy. Jak již bylo řečeno, uvedené číselné obory jsme popsali pouze intuitivně. K jejich přesné konstrukcí a přesnému odvozením základních vlastností je potřeba matematických znalostí, které přesahují rámec středoškolské matematiky. Touto problematikou se bude později zabývat kurz teoretické aritmetiky. Nicméně, všechny základní vlastnosti čísel uváděné na střední škole samozřejmě platí a my je budeme i nadále používat. 14 Víme tedy, že ve všech uvedených číselných oborech je možno čísla sčítat a násobit, přičemž jak sčítání tak násobení jsou komutativní, asociativní a platí distributivní zákon. Navíc v Z, Q a R ke každému číslu existuje číslo opačné, zatímco v oboru přirozených čísel N tomu tak není. Dále, v oborech Q a R ke každému nenulovému číslu existuje číslo převrácené, zatímco v N a v Z tomu tak není. Konečně, čísla všech uvedených číselných množin je možno uspořádat "podle velikosti" (tzn. zavést symboly pro nerovnosti < , < , atd.). Pro počítání s nerovnostmi pak platí celá řada známých početních pravidel. Čísla komplexní označujeme symbolem C Na rozdíl od předchozích číselných oborů nejsou komplexní čísla mírou žádné reálné veličiny a nelze je tedy získat jako výsledek fyzikálních či jiných měření. Komplexní čísla vznikla postupným zobecňováním pojmu čísla v souvislosti s potřebou řešit úlohy, jejichž řešení v předchozích číselných oborech neexistuje. Příkladem takové úlohy je třeba hledání řešení jednoduché kvadratické rovnice x2 + 1 = 0. V žádném z předchozích číselných oborů řešení této rovnice evidentně neexistuje, protože tam pro každé číslo x platí, že x2 > 0, což znamená, že je vždy x2 + 1 ^ 0. V oboru komplexních čísel však existuje řešení nejenom této kvadratické rovnice, ale dá se ukázat, že existuje řešení jakékoliv kvadratické rovnice a dokonce, že existuje řešení všech podobných rovnic libovolných stupňů. Definice. Komplexní čísla C zavádíme jako množinu všech uspořádaných dvojic reálných čísel, tzn. C = R x R. Sčítání a násobení komplexních čísel definujeme takto: pro libovolné (a, 5), (c, d) G C položíme (a, b) + (c, d) = (a + c , b + d) (a, b) ■ (c, d) = (ac — bd , ad + bc). Úmluva. Všimněme si, že pro komplexní čísla tvaru (t, 0) platí: (a,0) + (c,0) = (a + c,0) a (a, 0) • (c, 0) = (ac , 0), což znamená, že komplexní čísla tohoto tvaru se sčítají a násobí stejným způsobem jako čísla reálná. Můžeme tedy každé komplexní číslo tvaru (t, 0) ztotožnit s reálným číslem t. Označíme- li navíc komplexní číslo (0,1) symbolem i, je pak možné každé komplexní číslo z = (a, b) zapsat ve tvaru: z = (a, b) = (a, 0) + (0, b) = (a, 0) + (0, b) ■ (0,1) = a + bi Definice. Vyjádření komplexního čísla z = (a, b) ve tvaru z = a + bi se nazývá algebraický tvar komplexního čísla z. Přitom reálné číslo a se nazývá reálná část komplexního čísla z, reálné číslo b se nazývá imaginární část komplexního čísla z a číslo i = (0,1) se nazývá imaginární jednotka. 15 Z předchozích definic bezprostředně vyplývá několik důležitých poznatků: 1. pro imaginární jednotku i platí: i2 = (0,1) -(0,1) = (-1,0) = -1. Vidíme tedy, že výše zmiňovaná kvadratická rovnice tvaru x2 + 1 = 0 má v oboru komplexních čísel řešení a tímto řešením je například komplexní číslo i. Pro úplnost jenom poznamenejme, že tato rovnice má celkem dvě řešení, tím druhým je komplexní číslo —i = (0, —1). 2. dvě komplexní čísla v algebraickém tvaru se rovnají právě když se rovnají jejich reálné části a jejich imaginární části. 3. sčítání a násobení dvou komplexních čísel v algebraickém tvaru se provádí stejným způsobem, jako sčítání a násobení dvojčlenů (s využitím toho, že i2 = —1). Nemusíme si tedy nazpaměť pamatovat definice pro sčítání a násobení komplexních čísel uvedené v předchozí definici. 4. komplexní čísla je možno graficky znázorňovat, a sice jako body v tzv. Gaussově rovině. Jedná se o rovinu s kartézským souřadnicovým systémem s osami x ("reálná osa") a y ("imaginární osa"), v níž je každé komplexní číslo z = (a, b) = a + bi znázorněno jako bod o souřadnicích [a, b\. Přitom zde platí podobný vztah jako platil mezi reálnými čísly a body na přímce. V tomto případě je tedy každému komplexnímu číslu uvedeným způsobem přiřazen právě jeden bod Gaussovy roviny a naopak, každému bodu Gausssovy roviny odpovídá jediné komplexní číslo. Jednoduchými technickými výpočty se lehce ověří, že sčítání a násobení komplexních čísel splňuje stejná základní pravidla, které platí pro racionální čísla a reálná čísla. Konkrétně - sčítání a násobení komplexních čísel je komutativní, asociativní a platí distributivní zákon. Roli nuly hraje komplexní číslo (0,0), které ztotožňujeme s reálným číslem 0 a roli jedničky hraje komplexní číslo (1,0), které zotožňujeme s reálným číslem 1. Dále, ke komplexnímu číslu z = (a,b) = a + bi existuje číslo opačné, kterým je komplexní číslo —z = (—a, —b) = —a — bi a konečně platí, že k nenulovému komplexnímu číslu z existuje číslo převrácené -. Můžeme tedy provádět dělení čísla a + bi nenulovým číslem c + di. Přitom se používá standardní "trik", kdy čitatele i jmenovatele rozšíříme číslem c — di, jak je vidět z následujícího příkladu. Příklad 3.1. 4 + i Napište v algebraickém tvaru komplexní číslo 2 — 3« Řešení : 4 + i _ A + i 2 + 3i _ 8 + 12i + 2i + 3i2 _ 5 + Ui _ _5_ 14 . 2-3i ~ 2 — 3i ' 2 + 3i ~ 22 - (3i)2 ~ 13 ~ 13 + 13 * ' Poznámka. Na rozdíl od od čísel reálných nelze komplexní čísla uspořádat "podle velikosti". Pro komplexní čísla nelze zavést vztah nerovnosti tak, aby splňoval všechny základní vlastnosti a početní pravidla, které má v případě čísel reálných. Komplexní čísla tedy 16 například nelze rozlišit na "kladná" a "záporná" (tj. větší nebo menší než nula) a do množiny komplexních čísel nelze přenést žádné partie z oboru čísel reálných, v nichž se vyskytují pojmy "větší" nebo "menší" (tzn. například partii o nerovnicích). Je-li dáno komplexní číslo z = a + bi, pak komplexní číslo a — bi se nazývá číslo komplexně sdružené k číslu z a označuje se symbolem ~ž. Přitom platí, že součin komplexních čísel z a ~ž je číslo reálné, které je dokonce nezáporné. Skutečně: z ■ ž = (a + bi) ■ (a - bi) = a2 + b2 > 0 . Podobným způsobem se rozepsáním dokáže, že pro libovolná komplexní čísla u, v platí: «\ u u + v = u + v u-v = u-v ' .v ) v Pro ilustraci dokažme například druhý z uvedených vztahů, ostatní se dokáží podobně. Je-li tedy u = a + bi, v = c + di, potom je u-v = (a + bi) ■ (c + di) = (ac — bd) + (ad + bc)i = (ac — bd) — (ad + bc)i ü -v = (a — bi) ■ (c — di) = (ac — bd) + (—ad — bc)i = (ac — bd) — (ad + bc)i což znamená, že dokazovaný vztah platí. Další pojem, který známe z předchozích číselných oborů a který lze zavést pro komplexní čísla je pojem absolutní hodnoty. Je-li tedy z = (a, b) = a + bi libovolné komplexní číslo, pak absolutní hodnota komplexního čísla z se označuje | z \ a definuje se takto: \z\ = Va2 + b2 . Z této definice ihned vidíme, že geometrický význam absolutní hodnoty z komplexního čísla je stejný, jako je tomu u reálných čísel. V obou případech totiž absolutní hodnota udává vzdálenost obrazu daného čísla od počátku soustavy souřadnic. Pro počítání s absolutními hodnotami z komplexních čísel platí podobná základní pravidla jako u čísel reálných, tzn. pro libovolná komplexní čísla u, v je: u-u| = |w|-|u| a je-li w/0, pak u v I Oba vztahy můžeme dokázat bezprostředním rozepsáním podle definice absolutní hodnoty. Je-li tedy u = a + bi, v = c + di, potom je u ■ v = (ac — bd) + (ad + bc)i, odkud dostáváme \u-v\ = ^(ac - bd)2 + (ad + bc)2 = Va2c2 + b2d2 + a2d2 + b2c2 \u\.\v\ = ^J(a2 + b2) ■ ^(c2 + d2) = Va2c2 + a2d? + b2c2 + b2d2 odkud plyne první z obou vztahů. Druhý vztah se dokáže analogicky. Komplexní čísla jsme doposud zapisovali pouze v algebraickém tvaru. Nyní si ukážeme jiný způsob jejich zápisu. Jeho princip spočívá v tom, že bod Z/Ov Gaussově 17 rovině můžeme jednoznačně určit pomocí jeho vzdálenosti r od počátku souřadné soustavy O a velikosti orientovaného úhlu íp jehož počáteční rameno je kladná poloosa x a koncové rameno je polopřímka O Z (viz obrázek). Je zřejmé, že v případě Z = O , tzn. pro komplexní číslo z = 0, uvedené vyjádření není možné. , y Z b r\ 2). Dokážeme nyní dané tvrzení pro n. Použijeme-li postupně definici mocniny, indukční předpoklad a součtové vzorce pro kosinus a sinus, dostáváme: zn = z ■ zn~x = \z\ (cos f + i sin 1 je přirozené číslo. Řešit takovou rovnici znamená najít všechna komplexní čísla, která jí vyhovují. Tato komplexní čísla budeme také nazývat (komplexní) n - té odmocniny z komplexního čísla a. Při řešení binomických rovnic budeme vždy předpokládat, že a/0, protože pro a = 0, má tato rovnice zřejmě jediné řešení, a to x = 0. Tento předpoklad nám 19 také umožní vyjádřit číslo a, v goniometrickém tvaru. Řešení binomických rovnic jsou popsána v následujícím tvrzení. Věta 3.2. Binomická rovnice xn — a = 0, kde a = \a\ (cos a + i sin a), má v oboru komplexních čísel právě n různých řešení, a to /r—r ( a + 2k-K . . a + 2kir \ n _, n xk = v N ( cos----------- + l sm----------- > Pro k = 0,1, 2, ... , n—1. V n n y Důkaz. K tomu, abychom tuto větu dokázali, je třeba ukázat tři věci, a to, že: 1. číslo Xk dané rovnici vyhovuje - to však ihned dostaneme dosazením čísla Xk do dané rovnice a umocněním podle věty 3.1. 2. čísla xq,xi, ... ,xn_i jsou navzájem různá - to bezprostředně vyplývá z vyjádření komplexního čísla v goniometrickém tvaru a z vlastností funkcí kosinus a sinus. 3. žádná další řešení dané binomické rovnice neexistují. Je-li tedy z = \ z \ (cos

/3-i|10 _ / 2-210 \ \l + tVšf-\ -1 + tf ~ V28-(^)6 20 aľg z = i (arg(2z) + 10arg(v/3-i) - [8arg(l+ň/Š) + 6arg(-l+z) ] + fe-2yr) = = l (f + 10-^7T - 8-f - 6 - f vr + k-27t) = |vr + A; • f vr . Hledanými pátými odmocninami z c je pak následujících pět komplexních čísel (místo argumentu ^ir můžeme vzít hodnotu ^ir — 2% = ^ z intervalu (0, 2%)) : Zk = cos( ^ + k • |-7r) + i sin( ^ + k ■ |7r) pro k = 0,1, 2, 3, 4. Velmi důležitým zvláštním případem binomické rovnice je rovnice Řešení této rovnice budeme nazývat n-té odmocniny z jedné. Vzhledem k tomu, že číslo 1 (chápané jako komplexní číslo) má argument a = 0 a jeho absolutní hodnota je rovna jedné, dostáváme dosazením do vzorce pro řešení binomické rovnice, že pro n-té odmocniny z jedné platí: 2kw . . 2kw n ., n Xk = cos------ + i sin------ , k = 0,1, 2, ... , n—1. n n Vidíme tedy, že n-tých odmocnin z jedné (v oboru komplexních čísel) je právě n a jejich obrazy, nakreslené v Gaussově rovině, leží ve vrcholech pravidelného n-úhelníku vepsaného do jednotkové kružnice se středem v počátku, přičemž jeden z vrcholů leží v bodě 1 na reálné ose. Nakreslete si sami obrázek znázorňující například všech osm osmých odmocnin z jedné. Na závěr našich úvah o binomických rovnicích uveďme dvě důležité vlastnosti n-tých odmocnin z jedné, které budeme později využívat. Věta 3.3. Pro n -té odmocniny z jedné platí: 1. součin dvou n-tých odmocnin z jedné je opět n-tá odmocnina z jedné 2. převrácená hodnota n-té odmocniny z jedné je opět n-tá odmocnina z jedné. Důkaz. Nechť xr,xs jsou libovolné n-té odmocniny z jedné. Potom je : x™ = 1 a x™ = 1. Nyní vezměme číslo xr-xs a číslo — a umocněme je na n-tou. Dostaneme: /1\" ln | 71 . /y* | '" ----- sy*'" . ty*'" ----- T PÍ I ____ I ----- _____ ----- 1 v ' r s \xr) x™ odkud plyne, že čísla xr-xs a — jsou řešeními binomické rovnice xn — 1 = 0. Jinak řečeno, obě čísla jsou n-tými odmocninami z jedné. ■ 21 4. Základní vlastnosti celých čísel. Na střední škole byla odvozena nebo jenom uvedena řada vlastností celých čísel a pravidel pro počítání s nimi. V této kapitole zopakujeme a doplníme zejména základní vlastnosti celých čísel, které souvisejí s dělitelností. Definice. Nechť a, b jsou celá čísla. Říkáme, že a dělí b a píšeme a \ b, jestliže existuje celé číslo z tak, že platí b = a ■ z . V opačném případě říkáme, že a nedělí b a píšeme a \ b . Je nutné vždy přesně vědět, co znamená výše uvedený slovní obrat "v opačném případě". Jinak řečeno, je nutné správně utvořit negaci výroku s existenčním kvantifikátorem. Tedy a nedělí 5, znamená, že pro každé celé číslo z platí, že b ^ a ■ z. Dále je nutné si uvědomit, že zvláštní roli při dělitelnosti celých čísel hraje číslo nula. Přímo z definice dělitelnosti v oboru celých čísel totiž plyne, že a | 0 pro každé a G Z tzn. každé celé číslo dělí nulu 0 | b právě když 5 = 0 tzn. nula dělí pouze nulu. Všimněme si dále, že každé celé číslo b je vždy dělitelné čísly 1, —1, b, —b. Tato čísla se nazývají nevlastní dělitelé čísla b. Všichni ostatní dělitelé čísla b (pokud existují) se nazývají vlastní dělitelé čísla b. S vlastními a nevlastními děliteli přirozených čísel souvisí následující dva pojmy. Definice. Celé číslo p se nazývá prvočíslo, jestliže p > 1 a p má pouze nevlastní dělitele. Podobně, celé číslo s se nazývá složené číslo jestliže s > 1 a s má i vlastní dělitele. Některé základní vlastnosti celých čísel, které se týkají dělitelnosti, popisuje následující věta. Věta 4.1. Nechť a, b, c jsou libovolná celá čísla. Pak platí: 1. a | a 2. a | b A b \ c =>• a \ c 3. a \ b A a \ c =>• a \ (b ■ x + c ■ y) pro každé x, y E Z 4. a\b A b\ a O b = ±a. Důkaz. 1. tvrzení je zřejmé, neboť lze napsat a = a ■ 1, což znamená, že a \ a. 2. nechť a \ b A b \ c. Pak existují celá čísla zi, z^ tak, že: b = a ■ z\ A c = b ■ zi- Po dosazení dostáváme c = a ■ (z± ■ z•". Nechť a\b A b \ a. Potom existují zi,Z2 G Z tak, že b = z\ a A a = z^ b. Po dosazení dostáváme b = zi Z2 b . Nyní, pokud je b = 0 , pak musí být a = 0 (proč ?) a tvrzení platí. Nechť tedy b ^ 0 . Potom můžeme číslem b vykrátit a dostáváme 1 = z\ ■ z^ ■ Tato rovnice je však v oboru celých čísel splněna pouze pro z\ = zi = \ nebo pro z\ = zi = — 1. Platí tedy, že b = ± a . Důkaz implikace "<^= ". b = ±a => b = a ■ (±1) A a = b ■ (±1) =>• a | b A 6 | a. ■ Jedním ze základních algoritmů, který se učí žáci již na základní škole, je algoritmus pro dělení dvou přirozených čísel. Uvědomme si, že výsledkem výpočtu je vlastně nalezení dalších dvou čísel, tzv. částečného podílu a zbytku. Celou situaci lze zformulovat v oboru celých čísel pomocí následující věty. Věta 4.2. (Věta o dělení se zbytkem celých čísel) Nechť a, b jsou celá čísla, taková, zeb ^ 0. Potom existují celá čísla q, r, splňující vztah: (1) a = b- q + r A 0 < r < |ft| , přičemž toto vyjádření je jednoznačné. Důkaz. Důkaz věty provedeme ve dvou krocích. V prvním kroku dokážeme, že uvedené vyjádření existuje a ve druhém kroku pak ukážeme, že čísla g, r splňující vztah (1) jsou určena jednoznačně. 1. Důkaz existence vyjádření (1) . Uvažme množinu celých čísel M = {x -\b\ | x G Z A x -\b\ < a}. Množina M je zřejmě neprázdná a existuje v ní největší prvek, který si označíme Xq ■ | b | (rozmyslete si podrobně, že tomu tak skutečně je). Potom platí: (2) a = xq ■ \ b \ + r kde r > 0 a dále zřejmě je (xo + 1) • | b \ > a, neboli xo-|6| + |6| > a, odkud po úpravě dostáváme, že a — xo ■ \b\ < \ b \ a po dosazení za a ze (2) vychází (3) r < \b\ Nyní už jenom stačí pouze provést označení f xo , je-li b > 0 Q = i { —xo , je-li b < 0 a při tomto označení dostáváme ze (2) a (3) okamžitě hledaný vztah (1). 23 2. Důkaz jednoznačnosti vyjádření (1) . Budeme předpokládat, že existují dvě dvojice celých čísel, splňující vztah (1) a dokážeme, že se odpovídající si čísla rovnají. Nechť tedy q, q', r, r' jsou celá čísla, splňující vztah (1), tzn.: a = b ■ q + r , 0 < r < | 6 | A a = b ■ q' + r', 0 < r' < | 6 |. Pak odečtením obou rovnic obdržíme b-(q-q') = r'—r, odkud přechodem k absolutním hodnotám dostáváme: \ b ■ (q — q') \ = \ b \ ■ \ q — q' \ = \ r' — r \ . Dále, z předpokladů o číslech rar' plyne, že musí být \r' — r \ < \b\. Nyní - pokud by bylo q ^ q', dostáváme \r' — r\ = \b\ ■ \ q — q' \>\ b \ , což je spor. Musí tedy být q = q', odkud pak ihned plyne, že r = r'. To však znamená, že vyjádření (1) je jednoznačné. ■ Číslo q z vyjádření (1) se nazývá (neúplný) podíl po dělení čísla a číslem b. Číslo r z vyjádření (1) se nazývá zbytek po dělení čísla a číslem b. Mimo jiné tedy vidíme, že zbytek r po dělení čísla a číslem 5 je definován jednoznačně a nabývá vždy právě jedné z hodnot 0 , 1, ... , |b| — 1. Nyní zavedeme v oboru celých čísel Z pojem největšího společného dělitele dvou celých čísel a popíšeme jeho základní vlastnosti. Definice. Nechť a, b jsou celá čísla. Celé číslo d se nazývá největší společný dělitel čísel a, b, jestliže platí: 1. d | a A d\b 2. jestliže k \ a A k \ b pro nějaké k G Z, potom také k\d. Věta 4.3. Nechť a, b jsou libovolná celá čísla. Pak platí : 1. existuje největší společný dělitel čísel a, b 2. jestliže d je největším společným dělitelem čísel a, b, pak {d, — d} je množinou všech největších společných dělitelů čísel a, b 3. jestliže d je největším společným dělitelem čísel a, b, pak existují celá čísla u, v tak, že platí a ■ u + b ■ v = d . Důkaz. 1. pro a = 0, 6 = 0 existuje největší společný dělitel, a sice číslo 0 (ověřte si sami, že tomu tak skutečně je). Nechť tedy a/0 nebo b ^ 0. Uvažme množinu čísel M = {a ■ x + b ■ y \ x,y G Z libovolné} 24 a označme d = a ■ xq + b ■ i/o nejmenší kladné číslo patřící do M (rozmyslete si, že takové číslo určitě existuje). Nyní ukážeme, že d je hledaným největším společným dělitelem čísel a, b (ověřením obou částí definice). Tedy: 1. podle věty o dělení celých čísel existují q,r G Z tak, že a = d ■ q + r kde 0 < r < d (zde I d I = d protože d je podle předpokladu kladné). Pak r = a — d ■ q = a — (a ■ xo + b ■ i/o) • q = a, ■ (1 — xq ■ q) + b ■ (—i/o • q) G M. Poněvadž však 0 < r < d a d je nejmenším kladným číslem patřícím do M, musí být r = 0. To ale znamená, že a = d ■ q, a tedy d \ a. Podobným způsobem se ukáže, že také d \ b. 2. jestliže k \ a , k \ b, pak podle věty 4.1. 3. platí, že k \ (a ■ xq + b ■ i/o) = d . Dokázali jsme tak, že d je největším společným dělitelem čísel a, b . 2. nechť d je daný největší společný dělitel čísel a, b a nechť / je libovolný největší společný dělitel a, b. Potom: f \ a A f | b, odkud plyne (protože d je největší společný dělitel a, 5), že / | d, d I a A d I b, odkud plyne (protože / je největší společný dělitel a, 5), že d \ f. Tedy f \ d A d \ f , tzn. podle věty 4.1. 4 dostáváme, že / = ± d. 3. z důkazu 1. části věty plyne, že existují xo, i/o G Z tak, že a- xo + b-ijo je největším společným dělitelem čísel a, b. Vzhledem k 2. části věty však libovolného největšího společného dělitele čísel a, b můžeme vyjádřit ve tvaru a ■ (±xo) + b ■ (±|/o), odkud po vhodném označení dostáváme žádané tvrzení. ■ Z předchozí věty plyne, že pro a = b = 0 existuje jediný jejich největší společný dělitel, a sice číslo 0. V všech ostatních případech (tzn. pro a / 0 V ři / 0) existují vždy dva největší společní dělitelé čísel a, 6, lišící se znaménkem. Dále poznamenejme, že třetí část věty pouze zaručuje existenci celých čísel u, v, splňujících uvedený vztah. Dá se ukázat, že takových dvojic čísel u, v existuje nekonečně mnoho. Poznámka - dělitelnost v oboru přirozených čísel. Na střední škole se pojem dělitelnosti obvykle probírá v oboru přirozených čísel. Samotný pojem dělitelnosti lze bez problémů přeformulovat pro přirozená čísla zřejmým způsobem: pro přirozená čísla a, b řekneme, že a dělí b, jestliže existuje přirozené číslo u tak, že b = a ■ u. Základní vlastnosti dělitelnosti, které jsme uvedli ve větě 3.1. platí i pro dělitelnost v oboru přirozených čísel. Rovněž pojem největšího společného dělitele je možné zavést pro přirozená čísla stejným způsobem, jako jsme to učinili pro čísla celá. Poznamenejme, že v tomto případě je možno druhou podmínku v definici největšího společného dělitele dvou přirozených čísel, tzn. podmínku " jestliže k \ a, k \ b pro nějaké k EN, potom také k \ d " nahradit ekvivalentní podmínkou " d je největší ze všech přirozených čísel k splňujících: k \ a, k \ b ". Největší společný dělitel čísel a, b v oboru přirozených čísel existuje jediný. 25 Definice. Řekneme, že dvě celá čísla a, b jsou nesoudělná, jestliže číslo 1 je jejich největším společným dělitelem. Následující věta ukáže některé jednoduché vlastnosti nesoudělných čísel. Všimněte si, že se při jejich důkazu podstatným způsobem využívá 3. část předchozí věty. Věta 4.4. Nechť a,b,c,a\,... ,an jsou celá čísla. Pak platí : 1. a , b jsou nesoudělná A a , c jsou nesoudělná =>• a ,b • c jsou nesoudělná 2. a | b ■ c A a , b jsou nesoudělná =>• a \ c 3. p je prvočíslo A p \ a\ ■ ... ■ an =>• p | aj pro nějaké i = 1, 2, ... , n . Důkaz. 1. Nechť a,b jsou nesoudělná a a,c jsou nesoudělná. Podle věty 4.3.3 existují celá čísla u, v, x, y tak, že platí: a ■ u + b ■ v = 1 A a ■ x + c ■ y = 1. Vynásobením obou rovností dostáváme : (4) a ■ (uax + ucy + bvx) + bc ■ (vy) = 1 Nyní dokážeme, že 1 je největším společným dělitelem čísel a , b ■ c. 1. zřejmě platí, že 1 | a A 1 \ bc 2. jestliže k \ a A k \bc, potom ze (4), užitím věty 4.1.3 dostáváme, že k | [ a ■ (uax + ucy + bvx) + bc ■ (vy) ] =>• k \ 1. Dokázali jsme tak, že čísla a ,b • c jsou nesoudělná. 2. Nechť a \ b ■ c A a ,b jsou nesoudělná. Pak podle věty 4.3.3 existují celá čísla u, v tak, že a ■ u + b ■ v = l.Po vynásobení této rovnice číslem c dostáváme: acu + bcv = c, odkud podle věty 4.1.3 (poněvadž a \ a A a\bc) plyne, že a\c. 3. Tvrzení budeme dokazovat matematickou indukcí vzhledem k n . a) pro n = 1 tvrzení evidentně platí ß) předpokláme, že tvrzení platí pro 1, ... , n—1 (n > 2). Nechť nyní p je prvočíslo A p | ai • ... • an , tzn. p\ (aľ- ... -an_i) • an . Jestliže p | an , pak dostáváme požadované tvrzení. Nechť tedy p nedělí an . Potom jsou čísla p, an nesoudělná (proč ?) a podle 2. části této věty platí, že p | (ai• ... • an_i). Podle indukčního předpokladu pak p \ a j pro nějaké i = 1,2, ... ,n—1. ■ 26 Věta 4.5. Každé celé číslo a > 1 lze rozložit na součin prvočísel, a to jednoznačné, až na jejich pořadí Důkaz. Nejprve budeme dokazovat existenci požadovaného rozkladu a pak jeho jednoznačnost. 1. Důkaz existence rozkladu. Důkaz povedeme sporem. Předpokládejme, že existují celá čísla větší než jedna, která nelze rozložit na součin prvočísel a nejmenší z těchto čísel označme u. Pak ale u není prvočíslo, tzn. u musí mít vlastního dělitele b, a tedy: u = b ■ c, kde 1 < b < u, 1 < c < u. Ale čísla 6, c lze rozložit na součin prvočísel (jinak spor s definicí čísla u), a tedy u = b ■ c lze pak také rozložit na součin prvočísel, což je spor. 2. Důkaz jednoznačnosti rozkladu (až na pořadí činitelů). Nechť (5) a = pí- ... -pn = qi- ... -qk jsou dva rozklady čísla a > 1 na součin prvočísel. Požadovanou jednoznačnost vyjádření (až na pořadí činitelů) nyní dokážeme matematickou indukcí vzhledem k n. a) pro n = 1 je a prvočíslem, tzn. musí být také k = 1 a následně pak p\ = q\. ß) předpokládejme, že pro všechna celá čísla větší než jedna, mající rozklad na součin méně než n prvočísel, je tento rozklad jednoznačný (až na pořadí činitelů). Vezměme celé číslo a > 1, pro které platí (5). Potom pn \ a = qi ■ ... ■ q^ . Ale pn je prvočíslo, tzn. musí platit pn \ qi pro nějaké i = 1, ... , k . Poněvadž pn i qi jsou prvočísla, musí být pn = qi, takže po zkrácení číslem pn = qi ve (4) a následném užití indukčního předpokladu dostáváme žádanou jednoznačnost. ■ Věta 4.6. Prvočísel je nekonečně mnoho. Důkaz. Budeme postupovat sporem. Předpokládejme, že existuje pouze konečně mnoho prvočísel a označme je například pi,P2, • • • , Pn- Nyní utvořme číslo a = P\ -P2 ■ ••• -Pn + 1- Číslo a lze podle předchozí věty rozložit na součin jistého počtu prvočísel, tzn. jinak řečeno, číslo a je určitě dělitelné alespoň jedním prvočíslem. Existuje tedy prvočíslo pi (kde i = 1,2, ... , n) tak, že Pí | a. Kromě toho také Pí | p\ ■ p• 2" . Nechť platí 1 a nechť a = m ■ q± + r\, resp. b = m ■ q2 + r2 , přičemž 0 < ri, r2 < rn . Odečtením obou rovnic dostaneme : r2 - r\ = (b- a) + m- (qi - q2) ■ Podle 1 je m | {b — a) a triviálně platí rn | rn , a tedy podle V. 4.1. 3. je pak rn | (r2 — r\), což znamená, že existuje celé číslo z, tak že (5) r2 — r\ = m ■ z . Zřejmě však je — m < (r2 — ri) < m (proč ?), a tedy jediná hodnota z, která splňuje vztah (5) je číslo nula. Je tedy r2 — r\ = rn ■ 0 = 0, neboli r2 = r\ . Platí tedy 2. Důkaz implikace " 2 =í> 3" . Nechť platí 2, tzn. čísla a, 5 dávají po dělení číslem rn stejný zbytek. Můžeme tedy psát a = m ■ q\ + r , b = m ■ g2 + r (přičemž 0 < r < m). Po odečtení obou rovnic dostáváme 6 — a = m ■ (g2 — qi), což znamená, že 5 = a + m ■ (q2 - qi), kde (q2 - qi) G Z . Tedy čísla a, 5 se liší o celočíselný násobek čísla m, čímž jsme dokázali 3. Důkaz implikace "3 =/-1" . Nechť platí 3, tzn. existuje celé číslo z tak, že b = a + z • rn . Pak ale b — a = z • rn , neboli m | (5 — a). Podle definice je tedy a = b (mod m), což znamená, že jsme dokázali platnost 1. ■ Kongruence mají celou řadu zajímavých vlastností a pro počítání s nimi platí celá řada pravidel. Některé ze základních vlastností kongruencí nyní uvedeme. 28 Věta 4.8. Necht 'in je pevné přirozené číslo a necht a, o, c jsou celá čísla. Pak platí: 1. a = a (mod m) 2. a = b (mod m) =>• b = a (mod m) 3. a = b (mod m) A b = c (mod m) =>• a = c (mod m) Vztahy 1. a 2. okamžitě plynou například z 2. části předchozí věty. Důkaz vztahu 3. Nechť a = b (mod m) A o = c (mod m). Pak m | (b — a) A m | (c — b) odkud užitím věty 4.1.3 dostáváme, že m | (1 • (c — b) + 1 • (b — a)) =>- m | (c — a), což znamená, že a = c (mod m). Platí tedy vztah 3. ■ Věta 4.9. Necht a = b (mod m), c = d (mod m) . Pak platí : 1. a + c = 5 + d (mod m) 2. a — c = b — d (mod m) 3. a ■ c = b ■ d (mod m) 4. an = 6n (mod m); pro libovolné přirozené n . Důkaz. Dokážeme například vztah 3. Podle předpokladů a podle věty 4.7 (část 3), existují celá čísla zi, z^ tak, že a = b+zim , c = d + Z2in . Dosazením a výpočtem dostáváme : a-c = (b + zim) ■ (d + Z2'in) = (5 • d) + (bz2 + z\d + z\Z2'rn) ■ m odkud vidíme (opět užitím věty 4.7, část 3), že platí vztah 3. Vztahy 1. a 2. se dokáží analogicky a vztah 4. se dokáže ze vztahu 3. užitím matematické indukce (proveďte si sami). ■ Z předchozí věty mimo jiné vyplývá, že se kongruence chovají vzhledem ke sčítání, odčítání a násobení kongruencí (podle stejného modulu rn) podobně jako rovnice. Navíc pro kongruence platí další pravidla, která používáme u rovnic. Například, k oběma stranám kongruence je možno přičíst nebo odečíst libovolné celé číslo, resp. obě strany kongruence můžeme vynásobit libovolným celým číslem (to vyplývá ihned z předchozí věty a z faktu, že každé celé číslo je vždy kongruentní samo se sebou). Pozor - v kongruencích nelze obecně provádět "krácení"! Například je : 3-6 = 7-6 (mod 8), ale přitom neplatí, že 3 = 7 (mod 8). Následující věta však ukáže, že v kongruencích je možné provádět "krácení" číslem, které je nesoudělné s modulem. 29 Věta 4.10. Necht m je pevné přirozené číslo a necht a, 6, c jsou celá čísla. Pak platí: a ■ c = b ■ c (mod m) A c, m jsou nesoudělná ==>• a = b (mod m) . Důkaz. a ■ c = b ■ c (mod m) ^=^ m \ {bc — ac) =^ m \ {b — a) ■ c. Ale protože m, c jsou nesoudělná, musí (podle věty 4.4.2) platit, že ra | {b — a), což tedy znamená, že a = b (mod m). ■ 30 5. Zobrazení. Pojem zobrazení patří k základním pojmům celé matematiky. S tímto pojmem je možné se setkat již na střední škole. Definice. Nechť A, B jsou libovolné množiny. Předpis /, který každému prvku množiny A přiřazuje právě jeden prvek množiny B, se nazývá zobrazení množiny A do množiny B. Píšeme pak / : A —y B. Uvedená definice je sice názorná a pro naše účely dostačující, ale z hlediska teorie množin není zcela přesná, protože obsahuje nedefinovaný pojem "předpis". Přesnou definici zobrazení uvedeme později, v kapitole o relacích. Jestliže / : A —y B je zobrazení, pak množina A se nazývá definiční obor a množina B se nazývá obor hodnot tohoto zobrazení. Skutečnost, že prvku a G A je přiřazen prvek b E B, budeme vyjadřovat zápisem: f(a) = b. Jestliže je f (a) = b , pak budeme říkat, že prvek b je obraz prvku a, resp. budeme říkat, že prvek a je vzor prvku b. Dvě zobrazení / : A —y B , g : C —y D se rovnají (což budeme stručně vyjadřovat zápisem / = g), jestliže: A = C A B = D A f (x) = g{x) pro každé x G A tzn. jestliže se rovnají jejich definiční obory, obory hodnot a příslušné předpisy. V opačném případě (tzn. není-li splněna alespoň jedna z předchozích tří podmínek) se obě zobrazení nerovnají, což budeme stručně zapisovat ve tvaru f ^ g. Vidíme, že k zadání zobrazení je nutno zadat definiční obor, obor hodnot a příslušný předpis. Na příkladech nyní ukážeme, jak je při tom možno postupovat. Příklad 5.1. Definujme zobrazení / : A —y B takto: 1. A = {a, b,c,d}, B = {r, s, t, u, v} a položíme: f(a) = u, f(b) = r, f(c) = v, f(d) = t. 2. A = Z, B = N a, položíme : f 2x + 1 pro x > 0 f(x) = \ [ —2x pro x < 0 3. A = R, B = R a položíme: f (x) = siná: pro každé iGl 4. A = R, B = (—1,1) a položíme : f (x) = sin x pro každé x G M . Všimněte si toho, že poslední dvě zobrazení mají stejný předpis (a sice f (x) = siná;), ale přesto se nerovnají!! Mají totiž různé obory hodnot - jednou je oborem hodnot množina B = R a podruhé je oborem hodnot množina B = (—1,1). 31 Poznámka. 1. Definice zobrazení nevylučuje situaci, že některá z množin A, B je prázdnou množinou. Rozeberme si tento případ podrobněji. Je-li A prázdná množina a B je libovolná množina, pak existuje jediné zobrazení 0 —> B, které se nazývá prázdne zobrazení (rozmyslete si, jak je v tomto případě splněna definice zobrazení!). Je-li A neprázdná množina a, B je prázdná množina, potom neexistuje žádné zobrazení A —> 0 . 2. Je-li A libovolná neprázdná množina, pak zobrazení id a '■ A —> A definované předpisem: í<1a(x) = x, pro každé x G A se nazývá identické zobrazení (nebo též identita) na množině A . 3. Je-li iCRjSCR, pak zobrazení / : A —> B se obvykle nazývá (reálná) funkce (jedné reálné proměnné). Tato zobrazení se podrobně studují v matematické analýze. 4. Zobrazení mohou také vystupovat v roli prvků množin. Důležitým příkladem je množina všech zobrazení A —> B, kterou označujeme symbolem BA . Ilustrujme si tento pojem na příkladu množin A = {a,b,c} a B = {x, y}. Lehce zjistíme, že existuje právě 8 různých zobrazení A —> B (nakreslete si sami příslušné obrázky!). Množina BA má tedy 8 (tzn. 23) prvků. Obecně lze pro konečné množiny ukázat, že má-li množina A n prvků a množina B má s prvků, potom existuje právě sn různých zobrazení A —> B , neboli množina BA má sn prvků. Tato úvaha do jisté míry vysvětluje, proč je pro označení množiny všech zobrazení A —> B použit symbol BA (a nikoliv třeba symbol AB). Zobrazení mohou mít různé další vlastnosti. Nejzákladnější a zároveň nejdůležitější vlastnosti zobrazení jsou popsány v následující definici. Definice. Zobrazení / : A —> B se nazývá - injektivní zobrazení (nebo též prosté zobrazení), jestliže každý prvek z množiny B má při zobrazení / nejvýše jeden vzor. - surjektivní zobrazení (nebo též zobrazení na), jestliže každý prvek z množiny B má při zobrazení / alespoň jeden vzor. - bijektivní zobrazení, jestliže každý prvek z množiny B má při zobrazení / právě jeden vzor. O každém z výše definovaných pojmů je nutno mít zcela jasnou a názornou představu. Vyjádříme-li předchozí definici pouze jinými slovy (rozmyslete si podrobně sami, že obsahově jde skutečně o totéž), pak můžeme také říci, že: - zobrazení / : A —> B je injektivní právě když se každé dva různé prvky množiny A zobrazí vždy na dva různé prvky množiny B - zobrazení / : A —> B je surjektivní, právě když se na každý prvek množiny B vždy zobrazí nějaký prvek množiny A . - zobrazení / : A —> B je bijektivní právě když je současně injektivní a surjektivní. 32 V praxi je velmi často potřeba technicky dokázat, že zadané zobrazení má, případně nemá některou z výše uvedených vlastností. Obvykle postupujeme následujícím způsobem: dokazujeme-li, že zobrazení / : A —y B - je injektivní, pak předpokládáme, že pro prvky x,y E A platí f(x) = f(y) a následně dokážeme, že x = y. Můžeme také dokazovat implikaci: x ^ y => f(x) ^ f(y) (rozmyslete si, proč jsou oba postupy ekvivalentní). Technicky jednodušší bývá obvykle způsob první. - není injektivní, pak nalezneme dva konkrétní různé prvky z množiny A, které se zobrazí na stejný prvek v množině B. - je surjektivní, pak vezmeme libovolný (obecný) prvek b E B a, najdeme k němu vzor, tzn. najdeme prvek a E A, pro který platí: f (a) = b. - není surjektivní, pak nalezneme v množině B takový konkrétní prvek, který nemá při zobrazení / žádný vzor. Budeme-li u jednotlivých zobrazení z příkladu 5.1. zjišťovat, zda jsou injektivní, resp. surjektivní, resp. bijektivní, pak celkem jednoduše zjistíme (proveďte si ověření podrobně sami!), že - zobrazení z příkladu 5.1.1. je injektivní a není surjektivní, - zobrazení zobrazení z příkladu 5.1.2. je injektivní i surjektivní, tzn. je bijektivní, - zobrazení zobrazení z příkladu 5.1.3. není injektivní a není surjektivní - zobrazení zobrazení z příkladu 5.1.4. není injektivní a je surjektivní. Definice. Nechť / : A —y B je bijektivní zobrazení. Definujme zobrazení f~l : B —y A takto: pro každé b E B položíme f-\b) = a , kde a je ten prvek z množiny A, který je vzorem prvku b při původním zobrazení / (tzn. je f (a) = b). Zobrazení f~l se potom nazývá inverzní zobrazení k zobrazení / . Je třeba si uvědomit, že f~x je skutečně zobrazením, což vyplývá z toho, že původní zobrazení / je bijektivní (tento předpoklad nelze z definice vypustit!!), a tedy v definici uvedený prvek a existuje, a to jediný. Jestliže je zobrazení / : A —y B bijektivním zobrazením, pak přímo z definice inverzního zobrazení ihned plyne, že f~ľ : B —y A je také bijektivním zobrazením, a navíc zřejmě platí, že : (Z"1)"1 = /• Příklad 5.2. Zobrazení / : Z —y N z příkladu 5.1. 2 je, jak vime, bijektivní. Existuje tedy k němu zobrazení inverzní f~ľ : N —y Z. Lehce se zjistí, že: pro každé liché x G N pro každé sudé xGl. 33 f-\x) Definice. Nechť / : A —y B , g : B —y C jsou zobrazení. Potom zobrazení (g o f) : A —y C definované předpisem (d ° f)(x) = 9 ( f(x)) Pro každé x E A se nazývá složené zobrazení (ze zobrazení f a g, y tomto pořadí). Z definice je vidět, že složené zobrazení je možno definovat pouze v případě, že obor hodnot prvního zobrazení je roven definičnímu oboru druhého zobrazení. Poznamenejme ještě, že symbol g o f čteme buď "g kolečko /" nebo ng po /". U zápisu složeného zobrazení go f si ještě všimněme toho, že i když se nejprve provádí zobrazení / a potom zobrazení g, je zaveden zápis "v obráceném pořadí". Nutí nás k tomu vžitá konvence, podle které se argument x píše napravo od symbolu zobrazení /. Poznamenejme, že někteří autoři dávají při označování složeného zobrazení přednost "skutečnému pořadí" obou zobrazení a místo go f píší fog. Kvůli tomu pak opouštějí zmiňovanou konvenci a místo f(x) píší (x)f, popřípadě xf. Jestliže / : A —y B je zobrazení, pak přímo z definice složeného zobrazení ihned plyne, že foidA = f A idBo f = f . Je-li zobrazení / : A —y B navíc bijektivní, pak (jak víme) existuje inverzní zobrazení f~l:B —y A a zřejmě platí f-1of = idA A fof-1 = idB. Další základní vlastnosti složených zobrazení shrneme v následujících větách. Věta 5.1. Nechť f : A —y B, g : B —y C, h : C —y D jsou zobrazení. Pak platí: h o (g o f) = (h o g) o f . Důkaz. Zřejmě je h o (g o /) : A —y D, (h o g) o f : A —y D, a tedy definiční obory a obory hodnot obou zobrazení jsou si rovny. K dokázání věty zbývá dokázat rovnost příslušných předpisů. Nechť tedy je x G A libovolný. Pak je: (ho (go f))(x) = h((g o f)(x)) = h(g(f(x))) ((h o g) o f)(X) = (h o g)(f(x)) = h(g(f(x))) tedy oba předpisy jsou stejné a věta platí. ■ Věta 5. 2. Necht f : A —y B a g : B —y C jsou zobrazení. Pak platí: 1. /, g jsou injektivní zobrazení =>• go f je injektivní zobrazení 2. /, g jsou surjektivní zobrazení =>• go f je surjektivní zobrazení 3- g o f je injektivní zobrazení =>• / je injektivní zobrazení 4- g o f je surjektivní zobrazení =>• g je surjektivní zobrazení. 34 Důkaz. Jednotlivá tvrzení dokážeme tak, jak bylo popsáno v komentáři k definici injektivního a surjektivního zobrazení. 1. předpokládáme, že /, g jsou injektivní zobrazení a dokazujeme, že (go f) je injektivní zobrazení. Nechť tedy pro prvky a, b E A platí: (gof)(a) = (gof)(b). Užitím definice složeného zobrazení dostáváme g(f(a)) = g(f(b)). Protože však g je injektivní, dostáváme f (a) = f(b), odkud (protože / je injektivní) dostáváme, že a = b. Dokázali jsme tak, že zobrazení (g o /) je injektivní. 2. Předpokládáme, že /, g jsou surjektivní zobrazení a dokazujeme, že go f je surjektivní zobrazení. Nechť tedy z E C je libovolný prvek. Protože g je surjektivní, existuje prvek y E B tak, že g (y) = z. Ale také / je surjektivní, tzn. k prvku y E B existuje prvek x E A tak, že f(x) = y. Dohromady pak: z = g(y) = 9{f{x)) = (go f)(x), což znamená, že prvek x je vzorem prvku z při zobrazení (g o f). Dokázali jsme tak, že zobrazení g o / je surjektivní. 3. Předpokládáme, že (g o /) je injektivní zobrazení a dokazujeme, že / je injektivní zobrazení. Nechť tedy pro prvky a, b G A platí: /(«) = /(&)■ Potom je jistě také g (f (a)) = g(f(b)), neboli (g o f) (a) = (gof)(b). Protože však je (g o /) injektivní, dostáváme odtud, že a = b. Dokázali jsme tak, že zobrazení / je injektivní. 4. Přepokládáme, že (g o f) je surjektivní zobrazení a dokazujeme, že g je surjektivní zobrazení. Nechť tedy z G C je libovolný prvek. Protože (g o /) je surjektivní, musí existovat prvek x G A takový, že (g of)(x) = z, neboli g (f (x)) = z. To však znamená, že prvek f (x) je hledaným vzorem prvku z při zobrazení g. Dokázali jsme tak, že zobrazení g je surjektivní. ■ Věta 5.3. Necht f : A —> B , g : B —> A jsou zobrazení. Pak platí: g o f = id a A / o g = íoIb <$■ f,g jsou bijektivní A g = f~x . Důkaz. Implikace "<^=" zřejmě platí. Dokážeme tedy pouze implikaci opačnou. Důkaz implikace " =>". Vzhledem k tomu, že identické zobrazení je bijektivní, tzn. je injektivní i surjektivní, tak z předchozí věty (část 3 a 4) ihned plyne, že f i g jsou bijektivní zobrazení. Dále, zřejmě je g : B —> A, f~ľ : B —> A. Zbývá tedy dokázat rovnost příslušných předpisů. Nechť tedy y E B libovolný. Ale /je bijektivní, tzn. existuje jediný prvek 35 iris vlastností f(x) = y. Pak ale /-%) = x = idA{x) = (gof)(x) = g(f(x)) = g(y). Dokázali jsme tedy, že g = f~x. ■ Poznamenejme, že v předchozí větě k tomu, aby g = f~x nestačí platnost pouze jedné z uvedených rovností g o f = id a nebo / o g = idß , jak by se snad na první pohled mohlo zdát. Ukažme si to na následujícím příkladu. Příklad 5.3. Nechť / : N —y N, resp. g : N —y N jsou zobrazení, definovaná takto: f 1 pro x = 1 f (x) = x + 1 pro ViéN resp. g (x) = < { x — 1 pro x > 2 (zkuste si nejprve obě zobrazení schematicky nakreslit!). Zřejmě platí: go f = idN protože (g o f) (x) = g(f(x)) = g (x + 1) = (x + 1) — 1 = x . Přitom však zobrazení / není surjektivní (neboť číslo 1 nemá při zobrazení / žádný vzor) a zobrazení g není injektivní (neboť g(l) = g(2)). Vidíme tedy, že k zobrazením f, g inverzní zobrazení vůbec neexistují. Na závěr kapitoly o zobrazeních uvedeme některé základní úvahy týkající se porovnávání množin, zejména nekonečných. Půjde především o to, abychom se oprostili od představy, kterou si nevědomky přinášíme již ze základní školy, a sice, že počet prvků množiny je číslo. Budeme se snažit navzájem porovnávat počty prvků různých množin a provedeme nejjednodušší klasifikaci nekonečných množin, na množiny spočetné a nespočetné. Navíc uvidíme, že není možné všechny vžité (a správné!) představy o konečných množinách přenášet na množiny nekonečné. Definice. Nechť A, B jsou množiny. Jestliže existuje bijektivní zobrazení / : A —> B, pak říkáme, že množiny A, B jsou ekvivalentní nebo též, že mají stejnou mohutnost a píšeme A ~ B . Věta 5.4. Nechť A, B, C jsou libovolné množiny. Pak platí : 1. A~A 2. A~ B =^ B~ A 3. A~B A B - C =*► A ~ C Důkaz. 1. Identické zobrazení id a '■ A —y A je vždy bijektivní, tzn. vždy platí A ~ A. 2. Nechť A ~ B, tzn. existuje bijektivní zobrazení / : A —y B. Potom však existuje inverzní zobrazení f~l : B —y A, které je také bijektivní, a tedy B ~ A. 36 3. Nechť A ~ B A B ~ C, tzn. existují bijektivní zobrazení / : A —y B a g : B —y C. Potom podle věty 5.2 (část 1 a 2) je složené zobrazení (g o f) : A —y C také bijektivní, což znamená, že je A ~ C. Příklad 5.4. 1. Dvě konečné množiny mají stejnou mohutnost, právě když mají stejný počet prvků. 2. Množiny N a Z mají stejnou mohutnost. To lze lehce dokázat tak, že sestrojíme nějaké bijektivní zobrazení mezi těmito dvěma množinami. Například zobrazení z příkladu 5.1.2, tzn. f 2x + 1 pro x > 0 / : Z —y N definované předpisem f(x) = < [ — 2x pro x < 0 je bijektivní. 3. Množiny Z a Q mají stejnou mohutnost. Stručně popíšeme princip, jak se sestrojí bijektivní zobrazení mezi množinami Q a Z. Toto zobrazení budeme konstruovat postupně. Nejprve zobrazíme bijektivně kladná racionální čísla na kladná celá čísla takto: napíšeme kladná racionální čísla, vyjádřená v základním tvaru, do řádků tak, že do 1. řádku napíšeme postupně všechna racionální čísla s čitatelem 1 (a vzrůstajícími jmenovateli), do 2. řádku podobně všechna racionální čísla s čitatelem 2, atd. Vznikne "tabulka" tvaru i I I i 1 2 3 4 2 2 2 2 1 3 5 7 3 3 3 3 1 2 4 5 Vypíšeme-li nyní její prvky po diagonálách, tzn. II21_23JL2 1'2'1'3'3'1'4'5'""" ' seřadíme tím kladná racionální čísla do posloupnosti a dostaneme hledanou bijekci kladných racionálních čísel na kladná celá čísla. Podobným způsobem zobrazíme bijektivně záporná racionální čísla na záporná celá čísla a konečně, nulu zobrazíme na nulu. Dohromady pak dostáváme bijektivní zobrazení množiny Q na množinu Z. 4. Nechť (a, b) je libovolný pevný otevřený interval na reálné ose. Pak platí: (a, b) a (c, d) mají stejnou mohutnost pro jakýkoliv otevřený interval (c, ď); (a, b) a R+ mají stejnou mohutnost (kde R+ značí množinu kladných reálných čísel); (a, 5) a R mají stejnou mohutnost. Tato tvrzení dokážeme uvedením příslušných bijektivních zobrazení. Dokažte si sami, že následující zobrazení jsou skutečně bijektivní. d - c f : (a, b) —y (c, d) kde f (x) = c +-------• (x — a) 37 /:(a,6)—>R+ kde /(x) = |-| Íx — p -------- pro a < x < p 1-1 -------- pro p < x < b b — x přičemž p je libovolné pevné reálné číslo takové, že a < p < b. 5. Nechť (a, b) je libovolný pevný otevřený interval na reálné ose. Pak platí, že intervaly (a, b), (a, b), (a, b), (a, b) mají stejnou mohutnost. Vzhledem k 4. bude zřejmě stačit, když sestrojíme bijekci mezi (0,1) a (0,1). Ale zobrazení: / : (0,1) —► (0,1) definované f(x) = { ^ Pro * = *> i Ü • ■ • [ a; jinak je bijektivní (nakreslete si sami schematický obrázek a dokažte). Zbývající bijekce mezi intervaly (0,1) a (0,1), resp mezi intervaly (0,1} a (0,1) se sestrojí podobným způsobem. 6. Množiny N a R nemají stejnou mohutnost. Vzhledem ke 4. stačí dokázat, že reálný interval (0,1) a množina N nemají stejnou mohutnost. Budeme postupovat sporem. Předpokládáme tedy, že interval (0,1) a množina N mají stejnou mohutnost, tzn. prvky intervalu (0,1) je možné seřadit do posloupnosti. Tedy: (0,1) = {ai,a2,a3, ... ,an, ...}. Každé číslo a^ má přitom dekadický zápis 7 J Ojfc • 10 — 0 , dji (li2 uís ... a-i = fc=i Pokud má číslo a^ dva různé dekadické zápisy, pak vybereme nekonečný zápis, tj. takový, že pro nekonečně mnoho k je a^ ^ 0. V této souvislosti připomeňme, že dekadický zápis reálného čísla je jednoznačný, až na jednu výjimku, a sice nekonečný periodický zápis s periodou obsahující samé devítky představuje totéž racionální číslo, jako konečný dekadický zápis, který dostaneme z předchozího tak, že vynecháme periodu 9 a zvětšíme předchozí cifru o jedničku. Například tedy 0,2499999... a 0,25 jsou dva zápisy téhož (racionálního) čísla. Čísla tti vyjádřená dekadicky zapíšeme do následující tabulky: dl = -- 0 , (Zu di2 Ol3 • • • din a2 = = 0 i a21 «22 «23 • • ■ 0,2n 0 , an\ an2 ans ... ar 38 Nyní sestrojíme číslo 5, mající dekadický zápis b = 0 , b\ &2 &3 • • • bn ... takto: položíme J 1 je-li akk ^ 1 5fc = <> pro fe = 1,2,3, ... . L 2 je-h akk = 1 Potom číslo b patří do intervalu (0,1), což znamená, že je rovno některému z čísel a,i, a,2, «3, • • • , an, ..., například b = as. Musí tedy (mimo jiné) být ass = bs . Ale číslo b bylo sestrojené tak, že pro každé k je bk ^ akk a specielně tedy také bs ^ ass. Dostáváme tak hledaný spor. K předchozímu důkazu provedenému v příkladu 5.4.6. poznamenejme, že jeho základní myšlenku objevil německý matematik Georg Cantor (1845 - 1918) koncem 19. století. Uvedená metoda se proto také nazývá " Cantorova diagonální metoda". Definice. Množina, která má stejnou mohutnost jako množina N všech přirozených čísel, se nazývá spočetná množina. Nekonečná množina, která není spočetná, se nazývá nespočetná množina. Věta 5.5. 1. Množiny N , Z a Q jsou spočetné množiny. 2. Libovolný reálný interval a množiny R+ a R jsou nespočetné množiny. Důkaz. Obě tvrzení ihned vyplývají z úvah, které jsme provedli v předchozím příkladu. ■ Věta 5.6. Množiny A a 2A nikdy nemají stejnou mohutnost. Důkaz. Důkaz provedeme sporem. Předpokládejme tedy, že množiny A a 2A mají stejnou mohutnost, tzn. existuje bijektivní zobrazení / : A —> 2A. Označme pak Y = {aeA\ ačf(a)}. Vidíme, že Y je podmnožina v A, tzn. jinak řečeno, Y G 2A. Protože však / je bijekce, musí existovat (dokonce jediný) prvek u G A tak, že f (u) = Y. Pro prvek u však mohou nastat dvě možnosti: 1. u G Y, odkud plyne, že u G" f (u) = Y, což je spor 2. u G" Y, odkud plyne, že u E f (u) = Y, což je opět spor. Dohromady tedy dostáváme spor, což znamená, že věta platí. ■ Důsledek. Jestliže množina A je spočetná, potom množina 2A je nespočetná. Důkaz. Nechť A je spočetná množina. Pak A je nekonečná množina a 2A je tedy také nekonečná množina. Z věty 5.6 pak ihned plyne, že 2A je nespočetná množina. ■ 39 Poznámka. Podrobnějšími úvahami o mohutnosti množin (a nejen o ní) se bude později zabývat speciální kurz z teorie množin. Jenom pro ilustraci uveďme bez důkazu několik zajímavých tvrzení o konečných, spočetných a nespočetných množinách. Například platí, že: 1. Množina A je konečná, právě když každá její vlastní podmnožina má jinou mohutnost než A. 2. Je-li I konečná nebo spočetná indexová množina a pro každé i G I je Ai konečná nebo spočetná množina, potom (J Ai je konečná nebo spočetná množina. iei 3. Kartézský součin konečného počtu spočetných množin je spočetná množina. 4. Je-li A nespočetná množina a, A " inkluze (r o a) o g C r o (er o g) se dokáže analogickým způsobem. ■ Definice. Nechť g je libovolná relace mezi množinami A, B. Potom relace g~ľ mezi množinami B,A, definovaná vztahem: g~l = {(u,v) e B x A | (v,u) G g} se nazývá inverzní relace k relaci g. Z definice inverzní relace okamžitě vyplývá, že (u,v) G g~x právě tehdy, když je (v,u) G g. Znázorníme-li si relaci g grafem, pak zřejmě graf relace g~l získáme tak, že vezmeme původní graf relace g a v něm pouze změníme orientaci všech šipek. Věta 6. 2. Nechť g je relace mezi množinami A, B a a je relace mezi množinami B, C . Potom platí: 1- (íT1)"1 = Q 2. (a o g)'1 = g'1 o a'1. Důkaz. 1. dokazovaná rovnost okamžitě vyplývá z definice inverzní relace. 2. zřejmě (a o g)~ľ i g~l o a~x jsou relace mezi množinami C,A. Jejich rovnost tedy dokazujeme jako množinovou rovnost. 'C" nechť (u,v) E (a o g)~ľ. Podle definice inverzní relace je pak (v,u) G a o g a dále, podle definice složené relace existuje b E B tak, že (v, b) E g A (5, u) E a. Potom však (b, v) E g~x A (u, b) E a~ľ, odkud pak podle definice složené relace dostáváme (u, v) E g~x o a~x . Dohromady tedy: (a o g)~ľ C g~x o er-1. 43 " D" inkluze q 1 o cr x C (a o g) x se dokáže analogickým způsobem. ■ Na závěr této kapitoly se budeme nyní zabývat speciálním, ale v praxi se často vyskytujícím typem relace mezi množinami A, B, a sice případem, kdy A = B ^ $. Definice. Nechť M je neprázdná množina. Pak libovolná podmnožina q kartézského součinu M x M se nazývá relace na množině M. Množinu M spolu s relací g budeme označovat symbolem (M, g) a budeme říkat, že (M, g) je množina s relací. Pro x,y G M budeme místo (x,y) G g psát obvykle xgy, resp. místo (x,y) G" g budeme psát x~g y . Příklad 6.3. 1. Nechť M = {a, b, c, d] a nechť například g = {(a, 6), (6, a), (b, b), (b, c)}. Potom g je relace na množině M . 2. Nechť M je libovolná neprázdná množina. Pak a) prázdná relace g = 0 je relací na množině M. b) univerzální relace g = M x M je relací na množině M. c) množina {(x, x) | x E M libovolné} je relací na množině M, kterou nazýváme relace rovnosti a označujeme symbolem t (řecké písmeno jota). 3. Nechť M = 2A , kde A je libovolná množina. Potom množina { (X, Y) | X, Y G 2A A X C F } je relací na množině 2^ , kterou nazýváme relace inkluze a obvykle ji označujeme symbolem C . 4. Nechť M = N je množina všech přirozených čísel. Pak množina { (a, 6) | a, 5 G N A a dělí 5} je relací na množině N, kterou nazýváme relace dělitelnosti (na množině přirozených čísel) a obvykle ji označujeme symbolem | . Zdůrazněme, že dělitelnost je v tomto případě chápána jako dělitelnost v oboru přirozených čísel, tzn. obrat "a dělí 5" znamená: "existuje x G N tak, že platí b = a • x" . 5. Nechť M = Z je množina všech celých čísel a nechť m je pevné přirozené číslo. Pak množina { (a, b) | a, b E Z A a = b (mod m) } je relací na množině všech celých čísel Z, kterou nazýváme relace kongruence podle modulu m. Poznámka. Schematické znázorňování relací na množině (zejména, je-li množina konečná) můžeme provést obrázkem, podobně jako u relací mezi množinami. Jestliže je tedy (M, g) množina s relací, pak prvky množiny M znázorníme jako body v rovině a z bodu x 44 nakreslíme orientovanou šipku do bodu y právě tehdy, když xgy . Přitom je samozřejmě možné, že šipka začíná a končí ve stejném bodu. Taková šipka se nazývá smyčka. Vzniklý obrázek budeme nazývat uzlový graf relace g. Výhodné je rovněž vyjadřování relace g na (konečné) množině M pomocí tabulky, kterou sestrojíme následujícím způsobem: do záhlaví řádků a sloupců vypíšeme prvky množiny M, a to ve stejném pořadí. Do průsečíku řádku označeného x a sloupce označeného y pak napíšeme jedničku, je-li xgy , resp. napíšeme nulu, je-li x~gy . Oba způsoby vyjádření relací si ukažme na relaci z příkladu 6. 3.1., tzn. je-li M = {a,b,c,d} a g = {(a, 6), (b, a), (b, b), (b, c)}. a b c d a 0 1 0 0 b 1 1 1 0 c 0 0 0 0 d 0 0 0 0 Později uvidíme, že některé speciální typy relací na množině je výhodné znázorňovat i jiným způsobem. Nyní si však nejprve popíšeme základní vlastnosti relací na množině. Definice. Nechť (M, g) je množina s relací. Řekneme, že relace g je 1. reflexivní, jestliže: x E M libovolný =>- xgx 2. symetrická, jestliže: x, y E M A xgy =>- ygx 3. antisymetrická, jestliže: x, y G M A xgy A ygx =^ x = y 4. tranzitivní, jestliže: x,y,z E M A xgy A ygz =>• xgz 5. úplná, jestliže: x, y E M libovolné =>• xgy V ygx. Poznámka. Předchozí definice bude hrát v úvahách o relacích na množině zásadní roli, a proto je nutné ji dobře pochopit a bezpečně zvládnout. Ukažme si ještě, jak se poznají výše definované vlastnosti relací (kromě tranzitivity, kde je situace složitější) z uzlového grafu (viz a)) a z tabulky relace (viz b)): reflexivnost: a) každý bod je opatřen smyčkou b) v hlavní diagonále tabulky jsou samé jedničky symetrie : a) mezi dvěma různými body jsou buď dvě šipky nebo žádná šipka b) tabulka je symetrická podle hlavní diagonály antisymetrie: a) mezi dvěma různými body je buď jedna nebo žádná šipka b) dvě různá políčka symetrická podle hlavní diagonály obsahují nejvýše jednu jedničku 45 úplnost: a) každý bod je opatřen smyčkou a každé dva různé body jsou spojeny (alespoň jednou) šipkou b) v hlavní diagonále jsou samé jedničky a dvě různá políčka symetrická podle hlavní diagonály obsahují alespoň jednu jedničku Jinou charakterizaci základních typů relací na množině uvádí následující věta. Věta 6.3. Nechť (M, g) je množina s relací. Pak platí: 1. relace g je reflexivní ^ i C g 2. relace g je symetrická ^ g C g~x 3. relace g je antisymetrická -<=> g n g~x C 4. relace g je tranzitivní ^ g o g C g 5. relace g je úplná -<=> g U g~x = M x M Důkaz. 1. tvrzení zřejmě platí. 2. Důkaz implikace v ^v. Nechť g je symetrická relace na M. Dokážeme, že g C g~ľ. Nechť (x, y) G g libovolné, tzn. xgy. Podle předpokladu je ale ygx, neboli (y, x) G g odkud dostáváme (x, y) G g~x. Platí tedy: q C g~x. Důkaz implikace "<=". Předpokládejme, že g C g~x. Nechť xgy, tzn. (x, y) G £. Podle předpokladu je ale (x, y) G g~x, neboli (í/, x) G £>. Tedy ygx a, relace q je symetrická. 3. Důkaz implikace v ^v. Nechť g je antisymetrická relace na M a nechť (x, y) E g íl g~x libovolné, tzn. platí xgy A ygx. Ale g je antisymetrická, a tedy x = y, neboli (x, y) G i. Dostáváme tak, že g n £>-1 C t. Důkaz implikace "<=". Nechť g n g~l Ct a nechť je xgy A ygx. To ale znamená, že (x, y) E g D g~ľ, a podle předpokladu je tedy (x, y) G t, neboli x = y. Dokázali jsme tedy, že relace g je antisymetrická. 4. Důkaz implikace " =>". Nechť relace £ je tranzitivní a nechť (x, y) E go g libovolné. Pak podle definice složené relace existuje prvek u E M tak, že xgu A ugy. Z tranzitivnosti relace q pak plyne, že xgy, neboli (x, y) E g. Dokázali jsme tak, že go g C g. Důkaz implikace "<=". Nechť go g C g a nechť xgy A ygz, což znamená, že (x, y) E g A (y, z) E g. Potom podle definice složené relace je (x, z) E g o g C g, tzn. xgz. Tedy relace q je tranzitivní. (kde t značí relaci rovnosti na M ) i 46 5. Důkaz implikace " =>". Nechť g je úplná relace. Vzhledem k tomu, že jistě platí: g U g~x C M x M, stačí dokázat pouze opačnou inkluzi. Nechť tedy (x, y) E M x M. Z toho, že relace g je úplná vyplývá, že x g y V ygx, tzn. (x, y) E g \/ (y, x) E g. Je tedy (x, y) E g V (x, y) E g-1, což znamená, že (x, y) E g U g~x. Dokázali jsme tedy, že g u g'1 = M x M. Důkaz implikace "<=". Nechť g U g~ľ = M x M. Nechť x, y E M jsou libovolné prvky. Potom zřejmě (x, y) E M x M = g U g-1, odkud plyne, že (x, y) E g V (x, y) E g-1, a tedy xgy V ygx . Tím jsme dokázali, že relace g je úplná. ■ K uvedeným vlastnostem relací na množině ještě poznamenejme, že symetričnost a antisymetričnost se navzájem nevylučují (například relace rovnosti na M je zároveň symetrická i antisymetrická). Dále je ještě dobré si uvědomit, že úplná relace musí být vždy reflexivní. Následující tabulka nám přehledně uvádí, které z výše zavedených vlastností mají či nemají relace z příkladu 6. 3. Je velmi užitečné si každou jednotlivou odpověď podrobně samostatně ověřit. Číslování relací je stejné jako v příkladu 6. 3. 1 2a 2b 2c 3 4 5 reflexivní ne ne ano ano ano ano ano symetrická ne ano ano ano (**) ne ano antisymetrická ne ano (*) ano ano ano ne tranzitivní ne ano ano ano ano ano ano úplná ne ne ano (*) (***) ne ne V některých případech závisí uvedené vlastnosti relací na počtu prvků množiny M: (*) ano, je-li M jednoprvková množina, jinak ne (**) ano, je-li A prázdná množina, jinak ne (***) ano, je-li A prázdná nebo jednoprvková množina, jinak ne. Relace na množině M, tak jak byla v této kapitole definována, se také někdy nazývá "binární relace". Tento pojem je možno zřejmým způsobem zobecnit na pojem tzv. "n-ární relace na množině M", která je pak definována jako libovolná podmnožina kartézského součinu Mn = M x M x ... x M (n-krát), pro libovolné pevné přirozené číslo n. Ve speciálních případech dostáváme: pro n = 1 tzv. unární relaci (což je vlastně libovolná podmnožina množiny M), pro n = 2 tzv. binární relaci, s níž jsme pracovali výše, pro n = 3 tzv. ternární relaci, což je libovolná podmnožina M x M x M, atd. 47 7. Uspořádané množiny. V této a v následující kapitole budeme podrobněji studovat relace na množině, které splňují současně několik z dříve definovaných vlastností relací. Definice. Nechť (M, g) je množina s relací, přičemž relace g je reflexivní, antisymetrická a tranzitivní. Pak relace g se nazývá uspořádání a (M, g) se nazývá uspořádaná množina. Je-li navíc relace g úplná, pak se g nazývá lineární uspořádání a (M, g) se nazývá lineárně uspořádaná množina nebo krátce řetězec. Příklad 7.1. 1. Relace inkluze C na množině 2 (tzn. na množině všech podmnožin množiny ^4) je relací uspořádání. Přitom (2A, C) je lineárně uspořádaná množina, právě když množina A je prázdná nebo jednoprvková (tzn. právě když množina 2A má jeden nebo dva prvky). 2. Relace dělitelnosti | na množině všech přirozených čísel N je relací uspořádání. Při tom (N, |) není lineárně uspořádaná množina. V této souvislosti poznamenejme, že relace dělitelnosti na množině všech celých čísel Z není relací uspořádání, a to proto, že není antisymetrická. 3. Relace uspořádání čísel podle velikosti < na množině N je relací lineárního uspořádání, a tedy (N, <) je lineárně uspořádaná množina. Přitom relací "uspořádání čísel podle velikosti" rozumíme relaci < definovanou způsobem známým ze střední školy, tzn. x < y právě když y — x je nezáporné číslo. Podobně, relace uspořádání čísel podle velikosti < je relací lineárního uspořádání na množině všech celých čísel Z, racionálních čísel Q a reálných čísel EL Dostáváme tak lineárně uspořádané množiny (Z, <), (Q, <) a (R, <). Úmluva. Libovolnou relaci uspořádání budeme v dalším při obecných úvahách označovat symbolem < ("menší nebo rovno") místo symbolu g nebo jiných řeckých písmen. Jedná se o vžitou konvenci vzniklou z toho, že klasickým příkladem relace uspořádání je uspořádání čísel podle velikosti, označované standardně symbolem < . V této souvislosti je však nutno zdůraznit, že v obecné rovině nebude mít symbol < nic společného s uspořádáním čísel podle velikosti. Je-li < libovolná relace uspořádání, pak zavedeme další úmluvu, a sice: místo konjunkce x < y A x ^ y budeme stručně psát x < y a číst "x je menší než y". Modelem pro toto označení je opět stejný symbol používaný na střední škole pro porovnávání čísel podle velikosti, přičemž v našem případě nebude mít zavedený symbol < s čísly opět obecně nic společného. Výhodou tohoto označení je především to, že jediným symbolem označuje konjunkci dvou podmínek. 48 Poznámka. Uspořádanou množinu (M, <) můžeme (zejména, je-li množina M konečná) znázorňovat graficky. Postupujeme přitom následujícím způsobem: 1. prvky množiny M znázorníme jako body v rovině 2. je-li x < y pak bod x nakreslíme niže než bod y 3. dva body x, y spojíme úsečkou právě tehdy, když x < y a neexistuje žádný bod "mezi nimi", tzn. neexistuje k E M tak, že x < k A k < y. Výsledný graf se pak nazývá hasseovský diagram uspořádané množiny (M, <). Je ihned vidět, že se vlastně jedná o zjednodušený uzlový graf relace < (jsou vynechány smyčky, které by měly být u každého bodu, dále je vynechána orientace šipek, která je nahrazena umístěním bodu "níže" či "výše" a konečně jsou vynechány "zbytečné" šipky, jejichž existence plyne z tranzitivnosti relace < ) . Pro úplnost poznamenejme, že uvedená konstrukce nedefinuje jednoznačně "tvar" has-seovského diagramu. Jednu a tutéž uspořádanou množinu je často možné znázornit hasseovskými diagramy různých tvarů tak, že na první pohled nemusí být vůbec zřejmé, že jde o diagramy téže uspořádané množiny. Na druhé straně, známe-li hasseovský diagram uspořádané množiny, pak z něj lze relaci < jednoznačně zpětně zrekonstruovat. Vidíme tedy, že je možné zadávat uspořádanou množinu pomocí jejího hasseovského diagramu. Příklad 7. 2. Nechť A = {a, b, c} ; potom je 2A = { 0, {a}, {b}, {c}, {a, &}, {a, c}, {b, c}, {a, 5, c}} a hasseovský diagram uspořádané množiny (2A, C) je znázorněn na obrázku a). Část hasseovského diagramu uspořádané množiny (N, |) z příkladu 7.1. 2 je znázorněna na obrázku b). Zde si uvědomme, že obrázek vlastně nezachycuje správně celou situaci, protože z každého čísla x ve skutečnosti vychází nekonečně mnoho úseček, vedoucích do čísel x -p, kde p je libovolné prvočíslo, přičemž prvočísel je, jak víme, nekonečně mnoho. Část hasseovského diagramu uspořádané množiny (N, < ) z příkladu 7.1. 3 (tzn. symbol < v tomto případě značí uspořádání přirozených čísel podle velikosti) je znázorněna na obrázku c). 1. {a,b,c} {a,b} {b,c} 5 6 4 T 3 T 2 i 1 c) 49 Je jasné, že u nekonečných uspořádaných množin nelze jejich hasseovský diagram nikdy nakreslit celý. Vzniklý obrázek je pak jen více či méně názornou orientační pomůckou a někdy ani nemá smysl se snažit jej nakreslit, jako třeba u uspořádané množiny (2K,C). V uspořádaných množinách se mohou vyskytovat jisté "význačné" prvky, které si nyní popíšeme v následující definici. Definice. Nechť (M, <) je uspořádaná množina. Prvek a G M se nazývá nejmenší, jestliže pro každé x E M platí: a < x největší, jestliže pro každé x E M platí: x < a minimální, jestliže neexistuje prvek x E M s vlastností: x < a maximální, jestliže neexistuje prvek x E M s vlastností: a < x. Dále, dva prvky u, v E M se nazývají srovnatelné, jestliže platí, že u < v nebo v < u. V opačném případě se prvky u, v nazývají nesrovnatelné. Příklad 7.3. 1. Nechť uspořádaná množina (M, <) je zadána následujícím hasseovským diagramem: Potom: nejmenším prvkem této uspořádané množiny je prvek a, největší prvek zde neexistuje, minimálním prvkem je prvek a a maximálními prvky jsou prvky b, e. Dále, nesrovnatelnými prvky jsou dvojice prvků 6,c, resp. b, d, resp. b, e , resp. c, d. Všechny ostatní dvojice prvků jsou srovnatelné prvky. 2. U uspořádaných množin z příkladu 7. 2. platí: 1. nejmenším a zároveň jediným minimálním prvkem je 0. Největším a zároveň jediným maximálním prvkem je {a,b,c}. 2. nejmenším a zároveň jediným minimálním prvkem je číslo 1, největší ani maximální prvek zde neexistuje - rozmyslete si podrobně, proč tomu tak je. Zároveň si zkuste rozmyslet, jak by se situace změnila v případě, že bychom k množině N přidali číslo nula a relací by byla relace dělitelnosti na této množině všech nezáporných celých čísel. 3. nejmenším a zároveň jediným minimálním prvkem je číslo 1, největší ani maximální prvek zde neexistuje. Poznámka. Ověřujeme-li o nějakém prvku a E M, že je minimálním prvkem uspořádané množiny (M, <), pak je obvykle technicky nejvýhodnější postupovat tak, že dokazujeme implikaci: 50 x E M A x < a =>• x = a. Podobně, ověřujeme-li, že prvek a, je maximálním prvkem uspořádané množiny (M, <), pak obvykle dokazujeme implikaci: x E M A a < x =>• x = a. Z předchozích příkladů je vidět, že nejmenší, největší, minimální a maximální prvek v uspořádané množině existovat může, ale nemusí. Navíc, minimálních nebo maximálních prvků může v uspořádané množině existovat případně i více. Co všechno v této souvislosti platí, ukazuje následující věta. Věta 7.1. Nechť (M, <) je uspořádaná množina. Pak platí: 1. v uspořádané množině (M, <) existuje nejvýše jeden nejmenší prvek a nejvýše jeden největší prvek. 2. je-li a E M nejmenším prvkem, pak je také minimálním prvkem a žádné další minimální prvky v uspořádané množině (M, <) neexistují. Podobně, je-li a E M největším prvkem, pak je také maximálním prvkem a žádné další maximální prvky v uspořádané množině (M, <) neexistují. Důkaz. Tvrzení věty dokážeme vždy pro nejmenší / minimální prvek. Zbytek obou tvrzení pro největší / maximální prvky se dokáže analogicky. 1. dokazujeme, že v (M, <) existuje nejvýše jeden nejmenší prvek. Budeme přitom postupovat tak, že budeme předpokládat existenci dvou nejmenších prvků a dokážeme, že se tyto prvky rovnají. Nechť tedy a, b jsou nejmenší prvky v (M, <). Potom je a < b (protože a je nejmenším prvkem) a zároveň je b < a (protože b je nejmenším prvkem). Z antisymetrie relace < pak ihned dostáváme, že a = b. 2. nechť a G M je nejmenší prvek. Postupem popsaným v předchozí poznámce dokážeme, že a je minimálním prvkem. Nechť tedy x E M A x < a. Ale a je podle předpokladu nejmenší prvek, tzn. musí platit a < x . Z antisymetrie relace < pak dostáváme, že x = a . Tedy a je minimální prvek. Zbývá dokázat, že žádné další minimální prvky různé od a už v (M, <) neexistují. Nechť tedy y E M je libovolný minimální prvek. Prvek a je podle předpokladu nejmenším prvkem, tzn. musí platit, že a < y, odkud již plyne (vzhledem k tomu, že y je minimální prvek), že y = a. ■ Poznámka. Upozorněme ještě jednou na typickou úvahu použitou v 1. části důkazu předchozí věty, kde jsme dokazovali, že nejmenší prvek v uspořádané množině existuje nejvýše jeden. Jestliže v matematice dokazujeme, že něčeho existuje nejvýše jeden exemplář, pak obvykle postupujeme tak, že předpokládáme existenci dvou exemplářů a následně o nich dokážeme, že se sobě rovnají. 51 Věta 7.2. Uspořádaná množina (M, <) je lineárně uspořádaná právě když jsou každé dva prvky množiny M srovnatelné. Důkaz. Tvrzení plyne ihned z definice lineárně uspořádané množiny a z definice srovnatelných prvků. ■ Věta 7.3. Nechť (M, <) je lineárně uspořádaná množina. Potom platí: 1. prvek a E M je minimální, právě když je nejmenší 2. prvek a E M je maximální, právě když je největší. Důkaz. Tvrzení dokážeme pro minimální a nejmenší prvek. Pro maximální a největší prvek se důkaz provede analogicky. Důkaz implikace " =>". Nechť a je minimální prvek a nechť x G M je libovolný prvek. Podle předpokladu je (M, <) lineárně uspořádaná množina, tzn. musí být a < x nebo x < a. Ale z x < a plyne, že x = a (protože prvek a je minimální), neboli a < x. Vždy tedy platí a < x, což znamená, že prvek a je nejmenším prvkem. Důkaz implikace " -<=". Tato implikace ihned plyne z 2. části věty 7.1. ■ Na závěr kapitoly o uspořádaných množinách zavedeme nejprve pro libovolnou uspořádanou množinu pojmy suprema a infima nějaké její podmnožiny a následně pak rozebereme jejich základní vlastnosti. Uvedené pojmy najdou uplatnění v dalších matematických disciplinách. Definice. Nechť (M, <) je uspořádaná množina, nechť A je libovolná podmnožina v M a nechť c G M. Prvek c se nazývá - dolní závora množiny A, jestliže pro libovolné x E A platí c < x - horní závora množiny A, jestliže pro libovolné x E A platí x < c - infimum množiny A (v množině M), jestliže c je největší dolní závora množiny A; píšeme pak c = inf^ A nebo jenom stručně c = inf A - supremum množiny A (v množině M), jestliže c je nejmenší horní závora množiny A; píšeme pak c = supM A nebo jenom stručně c = sup A . Poznámka. Obrat "c je největší dolní závora množiny An, použitý v definici infima, lze přesněji vyjádřit slovním obratem "c je největším prvkem uspořádané množiny všech dolních závor množiny An . Dokazujeme-li tedy, že c = inf A pak musíme dokázat dvě věci: a) c je dolní závora množiny A ß) je-li m dolní závora množiny A, pak je m < c. 52 Samotná definice infima obecně nezaručuje jeho existenci. Může se totiž stát, že množina dolních závor množiny A je prázdná nebo je sice neprázdná, ale nemá největší prvek. V takovém případě pak infimum A neexistuje. Na druhé straně, pokud infimum A existuje, pak musí být jediné (což ihned vyplývá z věty 7.1.1.), přičemž toto infimum může nebo také nemusí být prvkem množiny A. Analogické úvahy platí pro supremum množiny A v uspořádané množině (M, <), tzn. supremum A může anebo nemusí existovat a pokud existuje, pak je jediné, přičemž může anebo nemusí v A ležet. Připomeňme ještě, že definice infima a suprema množiny A nevylučuje situaci, že množina A je prázdná. Potom: - infimum prázdné množiny existuje právě když uspořádaná množina (M, <) má největší prvek c a v takovém případě je inf 0 = c. - podobně, sup 0 je rovno nejmenšímu prvku uspořádané množiny (M, <), pokud tento nejmenší prvek existuje, jinak sup0 neexistuje. Příklad 7.4. 1. Nechť M = {a,b,c,d,e, f,g,h} a uspořádaná množina (M, <) je zadána hasseov-ským diagramem Ukažme si, jak vypadají infima a suprema některých podmnožin množiny M. - je-li A = {a, b, c} , potom inf A = a a sup A = e - j e-li A = {e, f, g}, potom inf A = c a sup A neexistuje (protože množina horních závor A je prázdná) - je-li A = {d, e}, potom inf A neexistuje (protože množina dolních závor A je prázdná) a sup A = h - je-li A = {c, d}, potom inf A neexistuje (protože množina dolních závor A je prázdná) a sup A také neexistuje (protože množina horních závor A , tj. množina {/, g, h} nemá nejmenší prvek). 2. Uvažme uspořádanou množinu (N, |), tzn. množinu všech přirozených čísel s relací dělitelnosti. Potom například platí: - každá dvouprvková podmnožina {a, 5} má infimum, kterým je největší společný dělitel čísel a, b 53 - každá dvouprvková podmnožina {a, b} má supremum, kterým je nejmenší společný násobek čísel a, b - je-li A libovolná nekonečná podmnožina v N pak její supremum neexistuje (množina horních závor A je v tomto případě prázdná). 3. Uvažme uspořádanou množinu (R, <), tzn. množinu všech reálných čísel s relací uspořádání čísel podle velikosti. Potom například pro intervaly (0,1) a (0,1} platí: inf(0,l) = 0, sup(0,l) = l, inf(0,l) = 0, sup (0,1) = 1. 4. Uvažme uspořádanou množinu (2^,C). Nechť 13 je neprázdná podmnožina množiny 2A (tzn. prvky množiny 13 jsou jisté podmnožiny množiny ^4), potom je zřejmě infB= H x , sup'B= U X. xe'B xe'B Vidíme tedy, že v tomto případě je infimem množinový průnik a supremem je množinové sjednocení všech množin patřících do 13. Vzájemný vztah mezi existencí infim a suprem libovolných podmnožin dané uspořádané množiny (M, <) popisuje následující věta. Poznamenejme ještě, že předpoklad "libovolná podmnožina má infimum" vynucuje existenci nejmenšího a největšího prvku v (M, <) (nejmenším prvkem je inf M a největším prvkem je inf 0). Podobně, předpoklad "libovolná podmnožina má supremum" rovněž vynucuje existenci nejmenšího prvku (kterým je sup 0) a největšího prvku (kterým je supM). Věta 7.4. Nechť (M, <) je uspořádaná množina. Pak následující výroky jsou ekvivalentní : 1. libovolná podmnožina množiny M má infimum 2. libovolná podmnožina množiny M má supremum. Důkaz. Důkaz implikace " 1 ==/- 2". Nechť A je libovolná podmnožina v M. Označme H množinu všech horních závor množiny A (v M). Podle předpokladu existuje infimum množiny H, které označíme c. Nyní budeme dokazovat, že c je hledané supremum množiny A. a) nechť a G A je libovolný prvek. Je-li H = 0, pak c je největší prvek M, a tedy a < c. Je-li H ^ 0 a h G H, pak musí být a < h (proč?). To však znamená, že prvek a je dolní závorou množiny H. Ale c je infimem množiny H a proto musí být a < c. Dokázali jsme tedy, že c je horní závora množiny A . ß) nechť y je libovolná horní závora množiny A. Jinými slovy řečeno, y G H. Prvek c je však infimem množiny H, a tedy musí být c < y. Dokázali jsme tak, že c je nejmenší horní závora množiny A. Dohromady platí, že c = sup A, tzn. libovolná podmnožina v M má supremum. Důkaz implikace "2 =^- 1". Provede se analogickým způsobem, jako předchozí část důkazu. ■ 54 Definice. Nechť (M, <) je uspořádaná množina. Jestliže každá dvouprvková podmnožina množiny M má infimum i supremum, pak se (M, <) nazývá svaz. Jestliže každá podmnožina množiny M má infimum i supremum, pak se (M, <) nazývá úplný svaz. Poznámka. Z předchozí definice bezprostředně vyplývá několik skutečností, které je dobré si uvědomit. Například: 1. Je-li (M, <) svaz, potom také každá konečná neprázdná podmnožina v M má infimum a supremum (dokáže se matematickou indukcí). V případě, že množina M je konečná (a neprázdná), tedy pojmy svaz a úplný svaz splývají. 2. Je-li (M, <) úplný svaz, potom je také svaz. Opačná implikace samozřejmě neplatí, jak ukážeme dále na příkladech. 3. Každý úplný svaz (M, <) má nejmenší a největší prvek, kterým je inf M a supM. Příklad 7.5. 1. Každá lineárně uspořádaná množina je svaz. Specielně tedy (N, <), (Z, <), (Q, <), (M, <), kde < značí uspořádání čísel podle velikosti, jsou svazy. Žádný z nich však není úplným svazem. 2. Uspořádaná množina (N, |) je svaz, který není úplným svazem, což vyplývá z příkladu 7.4.2. 3. Nechť A je libovolná množina. Pak uspořádaná množina (2A, C ) je úplný svaz, což vyplývá z příkladu 7.4.4. 4. Následující obrázek udává hasseovske diagramy všech konečných n-prvkových svazů pro n = 1, 2, 3, 4, 5. n = 1 o n = 2 o o n = 3 q n = 4 o o o o n = 5 o o o o o 55 8. Ekvivalence a rozklady. Definice. Nechť (M, g) je množina s relací, přičemž relace g je reflexivní, symetrická a tranzitivní. Pak se relace g nazývá ekvivalence (na množině M). Pro označování relace ekvivalence budeme místo řeckých písmen obvykle používat symbol ~ (čti "vlnovka"). Příklad 8.1. 1. Nechť M je libovolná neprázdná množina. Pak nejjednoduššími příklady relací ekvivalence na množině M jsou a) relace rovnosti t, b) univerzální relace M x M , které jsme zavedli v kapitole o relacích (viz příklad 6. 3. 2 c a 6. 3. 2 b), kde jsme také uvedli, že každá z těchto relací je reflexivní, symetrická a tranzitivní. 2. Relace kongruence podle modulu m je relací ekvivalence na množině Z všech celých čísel. Tuto relaci jsme zavedli v příkladu 6. 3. 5. Věta 4. 8. pak ukazuje, že relace kongruence podle modulu m je reflexivní, symetrická a tranzitivní, tzn. je to skutečně relace ekvivalence na Z . 3. Nechť / : A —> B je zobrazení. Na množině A nyní definujeme relaci ~ takto: pro x, y G A položíme : x ~ y právě když f (x) = f(y). Je ihned vidět, že ~ je relace na A, která je reflexivní, symetrická a tranzitivní (sami si podrobně rozmyslete!). Tedy ~ je relací ekvivalence na množině A. Poznámka. Na dané neprázdné množině M lze zřejmě definovat celou řadu různých relací ekvivalence. Označme si symbolem £(M) množinu všech relací ekvivalence na množině M. Uvědomíme-li si, že relace ekvivalence na M je vlastně jistá podmnožina kartézského součinu M x M a relace množinové inkluze je vždy reflexivní, antisymetrická a tranzitivní, potom je zřejmé, že (£(M), C) je uspořádaná množina. Uvážíme-li dále, že relace rovnosti i a univerzální relace M x M jsou relacemi ekvivalence na množině M (viz příklad 8.1.1.), pak je již jednoduché ukázat, že relace rovnosti je nejmenším prvkem uspořádané množiny (£(M),C) a univerzální relace je největším prvkem uspořádané množiny (£(M), C). Definice. Nechť M je libovolná neprázdná množina. Pak systém "Jí neprázdných podmnožin množiny M , splňujících podmínky: 1. libovolné dvě různé množiny ze systému IR jsou disjunktní 2. sjednocení všech množin ze systému IR je rovno celé množině M, se nazývá rozklad na množině M. Prvky systému IR se nazývají třídy rozkladu IR. 56 Podmínky, které jsme v předchozí definici vyjádřili slovně, lze pomocí matematické symboliky zapsat následovně: i. X,Y e Ji a X^Y => lnľ = | 2. \JX(X E%) = M Rozklad na množině si můžeme ilustrovat náčrtkem podobného tvaru, jaký je uveden na následujícím obrázku. Na něm je znázorněn rozklad IR na množině M, takový, že IR = {U, V, X, Y, Z}. Rozklad IR má tedy v tomto případě 5 tříd rozkladu, kterými jsou množiny U, V, X, Y, Z. Uvedený obrázek je samozřejmě pouze orientační a nepřesný (mělo by například být řečeno, kam patří hranice jednotlivých množin). Je zřejmé, že počet tříd rozkladu nemusí být konečný tak jako na obrázku, ale může být i nekonečný. V každém případě však musí být IR ^ 0 . Poznámka. Dokazujeme-li, že systém množin IR je rozkladem na množině M, pak z definice rozkladu plyne, že je nutné ověřit následující tři podmínky: 1. každá množina z IR je neprázdnou podmnožinou v M . 2. dvě různé množiny z IR jsou disjunktní. Tuto podmínku je obvykle technicky nejvýhodnější dokazovat tak, že: předpokládáme I,ľeIR A Xnľ/0 a dokážeme, že X = Y. 3. sjednocení všech množin z IR je rovno celé množině M. Zde technicky dokazujeme pouze inkluzi M C [J X (X E Ji), protože opačná inkluze je zřejmě vždycky splněna. Příklad 8. 2. 1. Nechť M je libovolná neprázdná množina. Pak nejjednoduššími příklady rozkladů na množině M jsou následující dva rozklady: a) IR = {{x} | pro každé x E M} , což je rozklad, který má tolik tříd, kolik prvků má množina M, přičemž každá jeho třída obsahuje vždy právě jeden prvek b) IR = {M} , což je rozklad, který má jedinou třídu, a to množinu M . 2. Nechť M = Z . Pak například množiny {x E Z | x < —2}, { — 1,0}, {x E Z | xje sudé, kladné}, {x E Z | xje liché, kladné} tvoří rozklad na množině Z všech celých čísel. Tento rozklad má 4 třídy, z nichž tři třídy mají nekonečně mnoho prvků a jedna třída má konečně mnoho prvků. 57 3. Nechť M = R.. Pro libovolné celé číslo k označme symbolem J^ reálný interval (k , k + 1) , tzn.: 4 = {xel|Kx B je zobrazení a nechť ~ je relace ekvivalence na množině A, definovaná v příkladu 8.1.3. (tzn.: x ~ y ^ f(x) = f(y))- Potom rozkladem příslušným této relaci ekvivalence je rozklad na množině A , jehož třídy jsou tvořeny vždy právě těmi prvky z A, které se při zobrazení / zobrazí na stejný prvek množiny B. Je tedy: A/~ = {X\XCA A 3b0eB : xeX o f(x) = b0} . Rozklad A/~ budeme také nazývat rozklad příslušný zobrazení / . Věta 8.3. Nechť JI je rozklad na množině M. Pro prvky a,b E M položme : a ~ji b právě když existuje třída X E Ji tak, že a, b E X . Pak relace ^^ je relací ekvivalence na množině M . Důkaz. Relace ^^ je zřejmě reflexivní a symetrická. Zbývá tedy dokázat, že relace ^^ je tranzitivní. Nechť tedy pro prvky a,b,c E M platí: a ^^ b A b ^^ c. Podle definice relace ^^ existují třídy X, Y rozkladu JI takové, že a,b E X A b,c E Y. Tedy b E X D Y, což znamená, že Iľlľ / I, a podle definice rozkladu musí být X = Y. Potom však a, c E X , a tedy a ^^ c. Dokázali jsme tak, že relace ^^ je tranzitivní. ■ 60 Definice. Nechť IR je rozklad na množině M. Potom relace ^^ se nazývá ekvivalence příslušná rozkladu Ji. Příklad 8.4. Ukažme si, jak vypadají ekvivalence příslušné některým rozkladům, které jsme uvedli dříve. 1. Nechť M je libovolná neprázdná množina a nechť Ji je rozklad na M tvaru: a) IR = { {x} \ x E M} , tzn. jedná se o rozklad množiny M na jednoprvkové třídy. Potom ekvivalence příslušná tomuto rozkladu je zřejmě relace rovnosti t. b) IR = { M } , tzn. jedná se o rozklad na množině M, sestávající z jediné třídy. Pak relací ekvivalence, příslušné tomuto rozkladu je zřejmě univerzální relace. 2. Nechť M = Z a nechť IR je rozklad množiny Z na zbytkové třídy podle modulu m, tzn. IR = Zm = {Co, Ci,..., Cm_i} . Pak relací ekvivalence příslušné tomuto rozkladu je relace kongruence podle modulu m, neboť platí: a ~rg b ^ a,b E Ci pro nějaké i = 0,1,..., m—l -<=> a = b (mod m). Poznámka. Uvědomme si, že rozklad příslušný ekvivalenci ~ je pouze jedním z mnoha rozkladů, které je možno na množině M vytvořit a jeho definice evidentně závisí na dané relaci ~ . Tak například rozklad na množině Z, příslušný relaci kongruence podle modulu m je právě rozklad Zm a žádný jiný. Podobně je tomu s relací ekvivalence příslušné rozkladu IR, která je definována v závislosti na tomto rozkladu. Na závěr této kapitoly ukážeme, že mezi ekvivalencemi na množině M a rozklady na množině M existuje velice úzká souvislost. Přesněji řečeno, vyjdeme-li od jisté ekvivalence na množině M , utvoříme rozklad příslušný této ekvivalenci a následně utvoříme ekvivalenci příslušnou předchozímu rozkladu, pak skončíme u původní ekvivalence, od níž jsme vyšli. Podobně, máme-li nějaký rozklad na množině M, utvoříme ekvivalenci příslušnou tomuto rozkladu a nakonec sestrojíme rozklad příslušný poslední ekvivalenci, tak dostaneme původní rozklad na M. Můžeme tedy říci, že se tímto způsobem ekvivalence a rozklady vzájemně určují. Přesně popisuje tuto situaci následující věta. Věta 8.4. Nechť M je libovolná neprázdná množina. Pak platí: 1. je-li ~ ekvivalence na množině M, potom ^m/~ = ~ 2. je-li Ji rozklad na množině M, potom M/^^ = Ji Důkaz. Dokazovaná tvrzení jsou v obou případech množinové rovnosti a budeme je tedy také jako množinové rovnosti dokazovat. 1. dokazovaná rovnost je rovností dvou relací na množině M, tzn. budeme dokazovat rovnost dvou podmnožin kartézského součinu M x M. 61 " C" : nechť (a, b) E ~ m/~ ; tzn. a ^m/~ & • Pak existuje třída rozkladu M/~, která obsahuje prvky a, b. Nechť tedy a, b E Xu . Potom podle definice třídy Xu je a ~ u A b ~ u, odkud plyne (užitím symetričnosti a tranzitivnosti relace ~), že a ~ b. Dostáváme tak, že (a, b) G ~. " D" : nechť (a, 5) G ~ , tzn. a ~ 5. Pak zřejmě je a G Xa A b E Xa , kde Xa je jedna ze tříd rozkladu M/~. To ale znamená, že je a ~ m/~ &• Dostáváme tak, že (a,b) G ~Af/~- 2. dokazovaná rovnost je rovností dvou rozkladů na množině M, tzn. budeme dokazovat rovnost dvou systémů podmnožin množiny M. "C" : nechť X G M/^^ , tzn. X je třída rozkladu M/^^ . Pak existuje prvek a E M tak, že X = Xa = {x E M \ x ^^ a}. Ale poslední množina je právě jedna ze tříd rozkladu Ji, což znamená, že X G IR. " D" : nechť X G IR, tzn. X je třída rozkladu IR. Nechť dále a je libovolný pevný prvek z X. Pak ale X = {x G M | x ^^ a} = Xa E M/^^. Dokázali jsme tedy, že X G M/~% . ■ 62 II. ZÁKLADNÍ ALGEBRAICKÉ STRUKTURY 1. Algebraické struktury s jednou operací. V této kapitole se budeme zabývat jistými speciálními typy zobrazení, které se nazývají operace. Pojem operace vznikl zobecněním pojmů běžně známých ze střední školy, jako jsou například násobení přirozených čísel nebo sčítání celých čísel, atd. Vidíme, že v těchto případech je vždy libovolné uspořádané dvojici čísel z jisté množiny přiřazeno jediné, přesně určené číslo z téže množiny. Definice. Nechť G je neprázdná množina. Pak libovolné zobrazení GxG —> G se nazývá operace na množině G. Je-li při tomto zobrazení uspořádané dvojici (a, b) G GxG přiřazen prvek c G G, pak budeme obvykle psát a ■ b = c a budeme hovořit o operaci • (čti "tečka"). Množina G spolu s operací • se nazývá grupoid a označuje se symbolem (G, •). Poznámka. 1. Pro označování operace na množině G (což je vlastně jisté zobrazení) se ukazuje jako nepraktické používat písmena a symboliku zavedenou v kapitole o zobrazeních. Vhodnější je používat speciálních symbolů. Nejčastěji to budou: - symbol • (tzv. multiplikativní symbolika), který budeme číst "krát" a budeme hovořit o operaci " násobení". Je-li a ■ b = c, pak prvek c budeme nazývat součinem prvků a, b (v tomto pořadí). - symbol + (tzv. aditivní symbolika), který budme číst "plus" a budeme hovořit o operaci "sčítání". Je-li a + b = c, pak prvek c budeme nazývat součtem prvků a, b (v tomto pořadí). Poznamenejme, že výše zavedené symboly • nebo + samozřejmě nemají nic společného s násobením nebo sčítáním čísel. Dodejme ještě, že pro označování operací na množině budeme podle potřeby používat i jiné symboly, například o , * atd. 2. Z předchozí definice plyne, že grupoid (G, •) je uspořádaná dvojice, sestávající z množiny G (která se též nazývá nosná množina grupoidu) a z operace • na množině G. Rovnost dvou grupoidu znamená tedy rovnost nosných množin a současně rovnost příslušných operací. Pojem operace na množině G tak, jak byl výše definován, je možné ještě dále zobecnit na pojem tzv. "n-ární operace" na množině G, pro libovolné přirozené n, což je libovolné zobrazení G x G x • • • x G (n-krát) —> G. Je to tedy předpis, který každé uspořádané n-tici prvků z G přiřazuje jediný prvek z G. Příkladem n-ární operace na množině reálných čísel R může být třeba operace max(xi,X2,... ,xn), která každé uspořádané n-tici reálných čísel přiřazuje to číslo, které je z nich maximální. Pro n = 1, 63 resp. n = 2, resp. n = 3 se pak užívá názvů unární operace, resp. binární operace, resp. ternární operace. Příklad 1.1. 1. Uvažme množinu Z všech celých čísel. Pak obyčejné násobení čísel • je zřejmě operací na množině Z. Tedy (Z, •) je grupoid. Podobně dostáváme grupoidy (Z, +), resp. (Z, —), kde + , resp. — značí obyčejné sčítání, resp. obyčejné odčítání celých čísel. Je jasné, že se jedná o různé grupoidy, i když nosná množina je ve všech třech případech stejná. 2. Vezmeme-li množinu N všech přirozených čísel, pak obyčejné odčítání čísel není operací na N, protože například pro přirozená čísla 2, 3 je 2 — 3 ^ N, tzn. nejedná se o zobrazení N x N —y N. Dále například obyčejné dělení čísel není operací na množině R všech reálných čísel (rozmyslete si proč). 3. Nechť A je libovolná množina. Pak sjednocení, průnik a rozdíl dvou podmnožin množiny A je opět (jednoznačně určená) podmnožina v A. Tedy sjednocení, průnik a rozdíl množin jsou operace na množině 2A (tj. na systému všech podmnožin množiny A). Dostáváme tak grupoidy ( 2A1 U ), resp. ( 2A1 n ), resp. ( 2A, — ). 4. Nechť A je libovolná neprázdná množina. Symbolem AA, jak víme, označujeme systém všech zobrazení množiny A do množiny A (tzn. roli prvků množiny AA tedy hrají zobrazení A —y A). Pro f,g E A je zřejmě složené zobrazení g o f opět zobrazením A —y A, tzn. jinak řečeno g o f £ AA . Skládání zobrazení je tedy operací na množině AA a (AA, o) je pak grupoid. Operace na množině G je zobrazení G x G —y G, tzn. je to vlastně jistý předpis, který každé uspořádané dvojici prvků z G přiřadí jediný prvek z G. Tento předpis je možno zadávat různými způsoby, jak jsme ukázali v kapitole o zobrazeních. Pokud je však množina G konečná, pak je výhodné zadávat operaci na G pomocí tabulky, sestrojené následujícím způsobem: do svislého i vodorovného záhlaví tabulky napíšeme prvky množiny G, a to ve stejném pořadí. Výsledek operace pro uspořádanou dvojici (a, b) G G pak zapíšeme do toho políčka tabulky, které se nachází v řádku označeném "a" a ve sloupci nadepsaném "6". Použití tabulky při definování operace ukazuje následující příklad. Příklad 1.2. Na množině G = {a,b,c,d} definujeme operaci • tabulkou: a b c d a b a b c b a b c d c b c a c d a d a d Potom (G, •) je grupoid, přičemž například platí: a ■ d = c, d ■ a = a , atd. 64 Definice. Nechť (G, •) je grupoid. Jestliže platí: a ■ (b ■ c) = (a • b) ■ c pro každé a,b,c G G (asociativní zákon) pak operace • se nazývá asociativní operace a grupoid (G, •) se nazývá asociativní grupoid neboli pologrupa. Definice. Nechť (G, •) je grupoid. Jestliže platí: a ■ b = b ■ a pro každé a, 5 G G (komutativní zákon) pak operace • se nazývá komutativní operace a grupoid (G, •) se nazývá komutativní grupoid. Příklad 1.3. Ověřujeme-li u grupoidů z příkladů 1.1 a 1.2 platnost asociativního a komutativního zákona (proveďte si podrobně sami), pak zjistíme, že: a) grupoidy (Z, •), (Z, +), (2A, U), (2A, n) jsou asociativní i komutativní b) grupoid (Z,—) a grupoid (G,-) z příkladu 1.2 není asociativní a není komutativní c) grupoid (2A, —) je asociativní i komutativní v případě, že A = 0 ; je-li množina A neprázdná, pak grupoid (2A1 —) není asociativní a není komutativní d) grupoid (AA, o) je vždy asociativní; komutativní je tento grupoid pouze v případě, že množina A je jednoprvková, jinak komutativní není. Připomeňme ještě jednou, že při důkazu toho, že nějaké tvrzení obecně neplatí obvykle postupujeme tak, že ukážeme jednu konkrétní situaci, v níž toto tvrzení není splněno. Například chceme-li dokázat, že grupoid (G, •) z příkladu 1.2 není asociativní, pak najdeme konkrétní tři prvky, které platnost asociativního zákona porušují. V tomto případě například stačí vzít prvky a, d, c G G a spočítat příslušné součiny, tzn. a ■ {d ■ c) = b a (a • d) ■ c = a . Na hledání výše zmiňovaného protipříkladu neexistuje žádná univerzální "rada". Je třeba pouze postupovat systematicky a všímat si pozorně toho, jak je tabulka vytvořena. V našem případě je třeba zřejmé, že v hledaném protipříkladu se nemůže vyskytovat prvek b (proč?). Z definice pologrupy vyplývá, že v ní součin tří prvků (v daném pořadí) nezáleží na jejich uzávorkování, které u tří prvků lze provést právě uvedenými dvěma způsoby. Následující věta ukáže, že totéž platí v pologrupě i pro libovolný konečný počet n prvků, kde je počet možných uzávorkování samozřejmě mnohem větší. Věta 1.1. Nechť (G, •) je pologrupa a a±, a,2 , ... , an G G . Pak součin prvků a\, a,2 , ... , a,n (v tomto pořadí) nezáleží na jejich uzávorkování. Důkaz. Tvrzení dokážeme matematickou indukcí vzhledem k n. 65 a) pro n = 1 tvrzení zřejmě platí (prvek a\ chápeme jako "jednočlenný součin") ß) předpokládáme, že tvrzení platí pro 1,... ,n — 1 (n > 2), tzn. předpokládáme, že součin libovolných k prvků vybraných z prvků a\ , ... , an (v tomto pořadí), kde 1 < k < n — 1 nezáleží na jejich uzávorkování. Hodnotu tohoto součinu budeme označovat pomocí hranatých závorek. Nyní mějme dán součin prvků a±, ... , an při libovolném uzávorkování. Hodnotu tohoto součinu označme u. Pak (uvážíme-li "poslední" závorky) je u = b ■ c, kde b je součin prvků a-\_,..., ar a c je součin prvků ar+i,..., an (1 < r < n — 1). Potom: - pro r = 1 je u = [aľ] ■ [a2, ...,an] - pro 2 < r < n — 1 je (použijeme-li postupně indukční předpoklad, asociativní zákon a opět indukční předpoklad) : u=[a1,...,ar]- [ar+1, ...,an] = ( [aľ] ■ [a2, ■ ■ ■, ar]) • [ar+1, ...,an] = = [ai] ■ ([a2, ■ ■ ■, ar] ■ [ar+1, ...,an]) = [ai] ■ [a2, ■ ■ ■, an]. Tedy součin prvků a-\_,..., an má při každém uzávorkování stejnou hodnotu. ■ Definice. Nechť (G, •) je grupoid. Prvek e G G se nazývá neutrální prvek grupoidu (G, •), jestliže platí: (1) a ■ e = a A e ■ a = a pro každý prvek a G G. Předchozí definice především nezaručuje existenci neutrálního prvku v grupoidu a v případě, že neutrální prvek v grupoidu existuje, pak neříká nic o případném počtu neutrálních prvků v tomto grupoidu. Odpověď na tyto otázky nám dává následující věta. Věta 1.2. V grupoidu existuje nejvýše jeden neutrální prvek. Důkaz. Budeme předpokládat, že v grupoidu existují dva neutrální prvky a dokážeme, že se rovnají. Nechť tedy (G, •) je grupoid a nechť e,e' G G jsou neutrální prvky tohoto grupoidu. Pak platí: e • e' = e' (protože e je neutrálním prvkem grupoidu) a současně také platí: e • e' = e (protože e' je neutrálním prvkem grupoidu). Dostáváme tedy, že e = e'. ■ Z předchozí věty plyne, že grupoid buďto nemá žádný neutrální prvek nebo má jeden neutrální prvek. Máme-li v daném grupoidu nalézt neutrální prvek, pak v jednoduchých případech postupujeme tak, že neutrální prvek "uhodneme" a ověřením definice (1) následně ukážeme, že se skutečně o neutrální prvek jedná. Ve složitějších případech, musíme neutrální prvek ze vztahů (1) vypočítat. Příklad 1.4. Vyšetřujeme-li existenci neutrálního prvku u grupoidu z příkladu 1.1 a příkladu 1.2 (proveďte si podrobně sami), pak zjistíme, že : 66 a) grupoid (Z, •) má neutrální prvek 1; grupoid (Z, +) má neutrální prvek 0 a grupoid (Z, —) nemá neutrální prvek b) grupoid (2A,U) má neutrální prvek, kterým je 0; grupoid (2^,n) má neutrální prvek, kterým je množina A a grupoid (2A, —) má neutrální prvek 0 v případě, že A = 0, jinak neutrální prvek nemá c) grupoid (AA,o) má neutrální prvek, kterým je identické zobrazení id a d) grupoid (G, •) z příkladu 1.2 má neutrální prvek b. Všimněme si toho, že u grupoidu zadaných tabulkou se neutrální prvek nalezne velmi jednoduše tak, že u tohoto prvku se v příslušném řádku opakuje vodorovné záhlaví tabulky a v příslušném sloupci se opakuje svislé záhlaví tabulky. Úmluva. V dalším textu budeme místo termínu "neutrální prvek grupoidu (G, •)" (tzn. při multiplikativní symbolice) používat častěji termín "jednička grupoidu (G, •)" a tento prvek budeme (stejně jako doposud) označovat symbolem e . Pokud budeme používat aditivní symboliku (tzn. operaci budeme označovat symbolem + ), pak místo termínu "neutrální prvek grupoidu (G, +)" budeme používat termín "nula grupoidu (G, +)" a tento prvek budeme označovat symbolem o. Rozlišování obou pojmů budeme potřebovat později v situaci, kdy na dané množině budou najednou definovány dvě operace. Použitá terminologie je přitom motivována situací, kdy při obyčejném násobení čísel hraje roli neutrálního prvku číslo 1 a při obyčejném sčítání čísel hraje roli neutrálního prvku číslo nula. Definice. Nechť (G, •) je grupoid s jedničkou e a nechť a E G je pevný prvek. Pak prvek x G G, pro který platí: a ■ x = e A x ■ a = e se nazývá inverzní prvek k prvku a . Na tomto místě zdůrazněme zásadní rozdíl mezi oběma právě zavedenými pojmy. Zatímco pojem neutrálního prvku se týká celého grupiodu a je tedy v pořádku říci "e je neutrálním prvkem daného grupoidu", pojem inverzního prvku se vždy váže k nějakému konkrétnímu prvku. Je tedy nutné trvat na formulaci "x je inverzní prvek k prvku a" a není možné používat formulace typu: "x je inverzní prvek" nebo "x je inverzní prvek grupoidu" nebo " grupoid má inverzní prvek", apod. Úmluva. Pokud budeme používat aditivní symboliku (tzn. operaci budeme označovat +), pak místo termínu "inverzní prvek k prvku a" budeme používat termín "opačný prvek k prvku a". Opačným prvkem k prvku a v grupoidu (G, +) s nulou o je tedy takový prvek x E G, pro který platí: a + x = o A x + a = o. Poznamenejme, že z předchozí definice nevyplývá, že v grupoidu s jedničkou k danému prvku a musí existovat prvek inverzní, ani to, že inverzní prvek k prvku a musí 67 existovat jediný. Může se totiž stát, že v grupoidu s jedničkou k danému prvku - neexistuje žádný inverzní prvek (například v grupoidu (Z,-) k číslu 2 neexistuje inverzní prvek) - existuje jediný inverzní prvek (například v grupoidu (Z, •) k číslu —1 existuje jediný inverzní prvek, kterým je zřejmě číslo —1) - existuje více inverzních prvků (například v grupoidu z příkladu 1.2 k prvku a existují dva inverzní prvky, a sice prvky a, c) . Bude-li však daný grupoid pologrupou (tzn. operace bude asociativní), pak poslední možnost nemůže nenastať, což vyplývá z následující věty. Věta 1.3. V polo grupě s jedničkou ke každému prvku existuje nejvýše jeden prvek inverzní. Důkaz. Nechť (G, •) je pologrupa s jedničkou e a nechť a je libovolný prvek z G. Důkaz povedeme tak, že budeme předpokládat existenci dvou inverzních prvků k prvku a a dokážeme o nich, že se rovnají. Nechť tedy x, y jsou inverzní prvky k prvku a , tzn. podle předchozí definice platí: a ■ x = e A x ■ a = e A a ■ y = e A y ■ a = e . Pomocí těchto vztahů, užitím asociativity operace • a definice jedničky, pak dostáváme : x = x ■ e = x ■ (a ■ y) = (x ■ a) ■ y = e ■ y = y ■ Označení. Z předchozí věty plyne, že když v pologrupě k prvku a existuje prvek inverzní, pak je jediný. V takovém případě budeme tento jediný inverzní prvek k prvku a označovat symbolem a-1 (při multiplikativní symbolice) nebo symbolem —a (při aditivní symbolice). Věta 1.4. Nechť (G, •) je pologrupa s jedničkou e . Nechť a,b E G jsou prvky, k nimž v (G, •) existují inverzní prvky a-1, b~l. Pak platí: 1. e"1 = e 2. (a"1)"1 = a 3. (a-5)"1 = b'1 -a'1 . Důkaz. 1. a 2. část věty plynou okamžitě z definice inverzního prvku k prvku e a definice inverzního prvku k prvku a-1 (rozepište si sami příslušné definice). 3. tvrzení říká, že inverzním prvkem k prvku a ■ b má být prvek (5_1 • a-1) . Ověříme tedy pro tento prvek definici inverzního prvku k prvku a ■ b. Tedy: (a ■ b) ■ (5_1 • a-1) = a ■ (b ■ b~x) ■ a-1 = a ■ e ■ a-1 = a • a-1 = e (b'1 ■ a"1) • (a • b) = b'1 ■ (a"1 • a) • b = b'1 ■ e ■ b = b'1 ■ b = e a dostáváme tak, že prvek (6_1 • a-1) je opravdu inverzním prvkem k prvku a ■ b. ■ 68 Zkusíme-li si zamyslet nad známými příklady pologrup, pak zjistíme, že bude zřejmě užitečné požadovat, aby daná pologrupa měla neutrální prvek a navíc, aby v ní ke každému prvku existoval prvek inverzní. Tato úvaha nás pak vede k následující definici. Definice. Nechť (G, •) je pologrupa s jedničkou, ve které ke každému prvku existuje prvek inverzní. Potom se (G, •) nazývá grupa. Je-li operace • navíc komutativní, pak se grupa (G, •) nazývá komutativní grupa (nebo též abelovská grupa). Příklad 1.5. 1. Značí-li + obyčejné sčítání čísel, pak (Z, +), (Q, +), (R, +), (C, +), jsou komutativní grupy. 2. Značí-li • obyčejné násobení čísel, pak (Q-{0}, •), (R-{0}, •), (C-{0}, •), (R+,-) (kde R+ je množina všech kladných reálných čísel) jsou komutativní grupy. 3. Nechť G = {igC | |x| = 1}, tzn. G je množina všech komplexních čísel ležících na jednotkové kružnici a nechť • značí násobení komplexních čísel. Pak (G, ■) je komutativní grupa (která má zřejmě nekonečně mnoho prvků). 4. Nechť n je pevné přirozené číslo a nechť Gn značí množinu všech n-tých odmocnin z jedné v oboru komplexních čísel, tak jak jsme o nich hovořili v kapitole o komplexních číslech. Tedy: Gn = {zeC | zn = 1}. Nechť • značí násobení komplexních čísel. Pak (Gn , •) je komutativní grupa, která má n prvků (tento fakt plyne z vět 3.2. a 3.3. o komplexních číslech z 1. části textu). Vidíme, že uvedeným způsobem je možno sestrojit komutativní grupu, která má libovolný, předem daný konečný počet prvků. 5. Nechť n £ N. Na množině M.n všech uspořádaných n-tic reálných čísel definujeme operaci + takto : pro libovolné (ai,..., an), (&i,..., bn) G W1 položme (ai, a2, • • •, an) + (&i, b2, ■ ■ ■, bn) = (ai + &i, a2 + b2}..., an + bn) kde symboly + na pravé straně značí obyčejné sčítání čísel (stručně též říkáme, že "sčítání je definováno po složkách"). Potom (Rn,+) je komutativní grupa. Rozepsáním se lehce ukáže, že neutrálním prvkem (nulou) této grupy je uspořádaná n-tice (0, 0,..., 0), a dále, že opačným prvkem k prvku (ai, a2,..., an) je uspořádaná n-tice (—ai, — a,2, • • •, —CLn) ■ 6. Nechť A = {a, b, c} a nechť G značí množinu všech bijektivních zobrazení množiny A na množinu A (kterých je celkem 6 - nakreslete si je !). Nechť dále o značí skládání zobrazení. Potom (G, o) je grupa, která není komutativní. To, že (G, o) je grupa, bezprostředně vyplývá ze základních vlastností zobrazení (rozmyslete si podrobně sami - užijte přitom příslušná tvrzení a úvahy z kapitoly 5., z první části tohoto textu). 69 Ukažme, že tato grupa není komutativní. Vezměme například zobrazení /, g G G, definovaná: f (a) = b , f (b) = c, f (c) = a a g (á) = c, g (b) = b , g (c) = a Potom dostáváme : (/ o g) (a) = f (c) = a , a (g o /)(a) = #(&) = 5, odkud již ihned plyne, že fog^gof,a tedy operace o není komutativní. Poslední příklad je důležitým příkladem nekomutativní grupy. Je vidět, že stejným způsobem je možno sestrojit sestrojit další nekomutativní grupy: - vezmeme-li za výchozí množinu libovolnou konečnou množinu G o n prvcích (n > 3), potom je počet bijekcí G na G roven číslu n faktoriál a dostáváme nekomutativní grupu o n! prvcích (roli prvků hrají bijekce G na G, operací je skládání zobrazení). - vezmeme-li za výchozí množinu G nějakou nekonečnou množinu, pak bijekcí G na G je nekonečně mnoho a dostáváme tak nekonečnou nekomutativní grupu, kde opět roli prvků hrají bijekce G na G a, operací je skládání zobrazení. Další důležitý příklad komutativní grupy, která má konečný počet prvků, ukáže následující věta. Předtím si však na množině Zm zbytkových tříd podle modulu m definujeme operaci "sčítání zbytkových tříd". Definice. Nechť Zm = {Co, Ci,..., Cm_i} je množina všech zbytkových tříd podle modulu m. Na množině Zm definujeme operaci sčítání zbytkových tříd podle modulu rn takto: pro Ci,Cj G Zm položíme: (2) Ci + Cj = Cr , kde r je zbytek po dělení čísla (i + j) číslem m . Poznámka. Připomeňme, že symbol + je ve vztahu (2) použit dvakrát, a to vždy v jiném významu; jednou jako symbol pro právě definovanou operaci na množině Zm a podruhé pro obyčejné sčítání čísel. Dále poznamenejme, že definici sčítání zbytkových tříd, která byla ve (2) popsána slovně, je možné přepsat pomocí věty o dělení se zbytkem celých čísel následovně: (3) Ci + C j = Cr , kde i + j = z ■ m + r A 0 < r < m kde z je vhodné celé číslo. Věta 1.5. Nechť Zm = {Co, Ci,..., Cm_i} je množina zbytkových tříd podle modulu m a nechť + je operace sčítání zbytkových tříd podle modulu m . Potom (Zm , +) je komutativní grupa. Důkaz. 1. z definice sčítání zbytkových tříd ihned plyne, že (Zm , +) je grupoid, který je navíc zřejmě komutativní. 2. dokážeme, že operace + je asociativní. Nechť tedy Ci,Cj,Ck G Zm jsou libovolné zbytkové třídy podle modulu m. Označme nejprve: 70 Ly i ~T~ ^ j — Lyr a ( Ly i ~T~ ^ j ) ~T~ ^ fc — ^ s ' Při tomto označení pak (podle (3)) platí: i + j = z\m + r A 0• 2" a implikace " 1 =>• 3" zřejmě platí. Důkaz implikace "2 =>• 1" . Nechť a E G je libovolný prvek. Pak podle 2 existuje prvek x E G tak, že x ■ a = e a následně, opět podle 2, k prvku x existuje prvek z tak, že z ■ x = e . Potom po dosazení a úpravě dostáváme: a ■ x = e ■ (a • x) = [z ■ x) ■ (a • x) = z • (x • a) • x = z ■ e ■ x = z ■ x = e . Tedy prvek x je inverzním prvkem k prvku a, což znamená, že platí 1. Důkaz implikace "3=^1" se provede analogicky. ■ Definice. Nechť (G, •) je grupoid. Potom: 1. řekneme, že v grupoidu (G, •) platí zákony o dělení, jestliže pro každé a, 5 E G platí: 3 x E G tak, že a ■ x = b A 3 y E G tak, že y ■ a = b 2. řekneme, že v grupoidu (G, •) platí zákony o krácení, jestliže pro každé a, b, c E G platí: c • a = c ■ b =>• a = b A a ■ c = b ■ c =>• a = b . Následující věta ukáže, že v definici grupy je možné požadavek existence jedničky a existence inverzního prvku ke každému prvku nahradit požadavkem platnosti zákonů o dělení. Věta 1.7. Nechť (G, •) je pologrupa. Pak platí: (G, •) je grupa ^ v (G, •) platí zákony o dělení. Důkaz. Důkaz implikace "=^" . Nechť (G, •) je grupa a nechť a, 5 E G jsou libovolné prvky. Jestliže položíme : x = a-1- b a y = b ■ ar1 (uvědomme si, že z definice grupy plyne existence prvku ar1), potom dostáváme: a ■ x = a ■ (a-1- b) = b a dále y ■ a = {b ■ a~r) ■ a = b . Dokázali jsme tedy, že v (G, •) platí zákony o dělení. 72 Důkaz implikace "<^=" . Nechť v pologrupě (G, •) platí zákony o dělení. Důkaz toho, že (G, •) je grupou rozdělíme na dvě části. 1. Dokážeme, že v (G, •) existuje jednička. Nechť a, b G G jsou libovolné prvky. Pak z platnosti zákonů o dělení plyne, že existují prvky x, y, e, e' G G takové, že platí: a ■ x = b A y ■ a = b A a ■ e = a A e' ■ a = a Nyní postupným dosazováním z těchto vztahů dostáváme: (6) b ■ e = (y ■ a) ■ e = y ■ (a ■ e) = y ■ a = b (7) e' ■ b = e' ■ (a ■ x) = (e' ■ a) ■ x = a ■ x = b. Ale prvek b byl libovolný, tzn. ze (6) pro b = e' dostáváme e' ■ e = e' a podobně ze (7) pro b = e dostáváme e' ■ e = e. Je tedy e' = e a po dosazení e za e' do (7) pak ze (6) a (7) plyne, že prvek e je jedničkou v (G, •). 2. Dokážeme, že v (G, •) ke každému prvku existuje prvek inverzní. Nechť a G G je libovolný prvek. Z platnosti zákonů o dělení plyne, že existují prvky x, y G G tak, že platí: a ■ x = e A y ■ a = e. Nyní už jenom stačí dokázat, že y = x . Ale : y = y ■ e = y ■ (a • x) = (y ■ a) ■ x = e ■ x = x . Dokázali jsme tedy, že prvek a; je hledaným inverzním prvkem k prvku a . Dohromady potom z 1. a 2. dostáváme, že (G, •) je grupa. ■ Věta 1.8. Nechť (G, •) je grupa. Pak v (G, •) platí zákony o krácení. Důkaz. Nechť (G, •) je grupa a nechť a,b,c E G jsou prvky, pro které platí: c • a = c-b. Vynásobíme-li tuto rovnost zleva prvkem c_1 (který musí existovat, protože (G, •) je grupa), dostáváme: c_1 • (c • a) = c_1 • (c • b), odkud po přezávorkování a výpočtu dostáváme, že a = b . Analogickým způsobem se dokáže implikace a-c = b-c=>a = b. ■ Poznámka. Poznamenejme, že předchozí větu nelze obrátit (v tom smyslu, že z platnosti zákonů o krácení obecně neplyne, že grupoid nebo pologrupa je grupou). Například v pologrupě (N, •) platí zákony o krácení, ale přitom (N, •) není grupou. Na závěr kapitoly nyní zavedeme pojem celočíselné mocniny prvku v grupě a odvodíme pro něj základní početní pravidla. Uvidíme, že pravidla pro počítání s celočíselnými mocninami prvků v grupě jsou analogická podobným pravidlům pro počítání s čísly, známými ze střední školy. 73 Definice. Nechť (G, •) je grupa, jejíž jedničkou je e, nechť a E G a nechť r G Z. Pak celočíselná mocnina prvku a je definována takto : je-li r celé kladné číslo je-li r = 0 je-li r celé záporné číslo ( —r)-krát Věta 1.9. Nechť (G, •) je grupa a nechť r, s jsou libovolná celá čísla. Pak pro libovolný prvek a E G platí: 1. ar ■ as = ar+s 2. (ar)s = ar's . Důkaz. Důkaz obou tvrzení provedeme najednou a rozdělíme jej na tři části, podle možných hodnot r, s . Nechť tedy a G G je libovolný prvek. I. pro r > 0 A s > 0 nebo r = 0 A s libovolné celé nebo s = 0 A r libovolné celé plynou obě tvrzení přímo z předchozí definice celočíselné mocniny prvku a. II. nechť je r < 0 A s < 0. Potom: ar ■ as = (a~l • ... • a-1) • (a~l ■ ... ■ a-1) = a~l • ... • a~l = ar+s ( —r)-krát ( —s)-krát (—r — s)-krát což je první z dokazovaných vztahů. Dokážeme druhý vztah. Z definice celočíselné mocniny prvku a z věty 1.4.3 plyne (užitím matematické indukce), že pro libovolné přirozené k je a~k = (a_1)fc = (afc)_1. Využitím tohoto faktu a věty 1.4.2 pak dostáváme: K)s = ((a-r)-lr = («o-1)-*)-1 = («o-')-1)-1 = («-rrs- Ale —r > 0 A —s > 0, tzn. podle I. je: (a~r)~s = a^~r^~s^ = ar's. Dohromady tak pro tento případ dostáváme, že ( ar) s = ar's . III. případ r<0As>0 a případ r>0As<0 se dokazují analogickými úvahami jako v předchozích částech důkazu. Poznamenejme, že důkaz této části věty je poměrně rozsáhlý a technicky nepříjemný. ■ Poznámka. Používáme-li aditivního zápisu operace, tzn. máme-li grupu (G, +) , jejímž neutrálním prvkem je o, pak místo názvu "celočíselná mocnina prvku a" budeme používat název celočíselný násobek prvku a, který je tedy definován následujícím způsobem: 74 a + a + ■ ■ ■ + a je-li r celé kladné číslo r-krát ra = \ ° Je"n r = ° (—a) + (—a) + • • • + (—a) je-li r celé záporné číslo s-------------------------------v-------------------------------' ( —r)-krát V tomto případě má potom předchozí věta formálně jiný tvar, a sice: Nechť (G, +) je grupa a nechť r,s E Z. Pak pro libovolný prvek a E G platí: 1. (r • a) + (s ■ a) = (r + s) ■ a 2. s ■ (r • a) = (s ■ r) ■ a . Zde je potřeba dávat obzvláštní pozor na použité symboly, přesněji řečeno na to, že jeden symbol může být použit ve dvou významech. Například, ve vztahu 1. znamená symbol + na levé straně operaci v dané grupě, zatímco symbol + na pravé straně znamená obyčejné sčítání celých čísel. Podobně, ve vztahu 2. značí druhá tečka zprava obyčejné násobení celých čísel, zatímco ostatní tři tečky značí celočíselný násobek prvků z G. 75 2. Podstruktury algebraických struktur s jednou operací. Definice. Nechť (G, •) je grupoid a nechť H je neprázdná podmnožina množiny G . Pak řekneme, že podmnožina H je uzavřená vzhledem k operaci • , jestliže platí: a,b G H libovolné =>• a ■ b G H . Poznámka. Je-li dán grupoid (G, •) a podmnožina H C G je uzavřená vzhledem k operaci • , pak můžeme na množině H přirozeným způsobem definovat operaci, označme ji třeba * , takto: pro libovolné x,y G H položíme x *y = x ■ y . Tímto způsobem dostáváme grupoid (H, *). Z praktických důvodů zaveďme úmluvu, že operaci * na množině H budeme všude v dalším vždy značit stejným symbolem jako původní operaci na množině G. Máme tedy grupoid (H, •), pro který zavedeme následující pojmenování. Definice. Nechť (G, •) je grupoid a nechť neprázdná podmnožina H C G je uzavřená vzhledem k operaci •. Pak grupoid (H, •) se nazývá podgrupoid grupoidu (G, •). Věta 2.1. Nechť (H, •) je podgrupoid grupoidu (G, •) . Pak platí: 1. (G, •) je asociativní =>• (H, •) je asociativní 2. (G, •) je komutativní =>• (H, •) je komutativní 3. prvek e je jedničkou v (G, •) A e G H =>• e je jedničkou v (H, •) . Důkaz. Všechna tři tvrzení plynou okamžitě z příslušných definic. ■ Poznamenejme, že žádnou z implikací v předchozí větě nelze obrátit. Například v grupoidu (G, •) z příkladu 1.2. je ({d},-) podgrupoidem, který je asociativní, je komutativní a má jedničku d, zatímco celý grupoid (G, •) není asociativní, není komutativní a prvek d není jeho jedničkou. Definice. Nechť (G, •) je grupa a nechť (H, •) je podgrupoid v (G, •), který je sám grupou. Potom (H, •) se nazývá podgrupa grupy (G, •). Věta 2. 2. Nechť (H, •) je podgrupa grupy (G, •). Pak platí: 1. jednička podgrupy (H, •) je totožná s jedničkou grupy (G, •) 2. je-li a G H, pak inverzní prvek k prvku a v podgrupe (H, •) je totožný s inverzním prvkem k prvku a v grupě (G, •) . 76 Důkaz. 1. nechť en značí jedničku v (ií, •) a eo značí jedničku v (G, •). Pak platí: en ■ gh = čh (protože e#- je jedničkou v (ií, •)) cg • eH = čh (protože eo je jedničkou v (G, •)). Je tedy en • en = eo • en , odkud užitím zákona o krácení (který v grupě platí) dostáváme, že ejj = eo ■ 2. nechť a E H libovolný a nechť x značí inverzní prvek k prvku a v podgrupě (H, •), resp. y značí inverzní prvek k prvku a v grupě (G, •). Potom je : a ■ x = en = eo A a ■ y = eo odkud plyne, že a ■ x = a ■ y a užitím zákonů o krácení dostáváme, že x = y . ■ Poznámka. Vzhledem k 2. části předchozí věty nemusíme rozlišovat inverzní prvek k prvku a E H v podgrupě a v celé grupě. V obou případech budeme proto inverzní prvek k prvku a označovat symbolem ar1. V praxi se budeme často setkávat s úlohou rozhodnout o tom, zda daný podgrupiod je podgrupou dané grupy či nikoliv. Je vidět, že pokud bychom postupovali přesně podle definice podgrupy, dělali bychom řadu zbytečných kroků (například ověřování toho, že v podgrupoidu platí asociativní zákon). Proto nyní uvedeme větu, která tento postup zjednoduší. Věta 2.3. Nechť (G, •) je grupa a nechť H je neprázdná podmnožina v G . Potom následující výroky jsou ekvivalentní : 1. (ií, •) je podgrupa grupy (G, •) 2. pro a,b G H libovolné platí: a-b E H A a-1 G H 3. pro a, b G H libovolné platí: a ■ b~x G H 4. prv a, b G H libovolné platí: a-1 • b E H Důkaz. Tvrzení budeme dokazovat obvyklým způsobem, tzn. dokážeme postupně čtyři implikace. Důkaz implikace "1 =>• 2 " . Platnost této implikace plyne bezprostředně z definice podgrupy. Důkaz implikace "2 =>• 3 " . Nechť platí 2. a nechť a, b E H. Potom (podle 2.) je b~x E H a následně opětovným užitím 2. dostáváme, že a • b~x E H . Dokázali jsme tak platnost 3. Důkaz implikace "3 =>• 4 " . Nechť platí 3. a nechť a, b E H. Podle 3. je: a ■ a-1 = e G H. Tedy e, a, b E H a 77 použitím 3. dostaneme: e • a~l = a'1 E H a e ■ b~l = b~ľ E H . Je tedy a-1, 5_1 G H , odkud opět podle 3. dostáváme: a-1 • (5-1)-1 = a-1 -b E H , což znamená, že platí 4. Důkaz implikace "4 =>• 1" . Nechť platí 4. a nechť a,b E H. Podle 4. je: a-1 ■ a = e E H. Tedy a,e E H a podle 4. je: a-1 • e = a-1 G iř. Je tedy ar1, b E H, odkud opět podle 4. dostáváme: (a"1)"1-5 = a-b EH, čímž jsme dokázali, že (H, •) je podgrupoid v (G, •), který je podle věty 2.1.1 asociativní. Ale výše bylo dokázáno, že e E H a pro libovolné a E H je a~ľ E H. To znamená, že (H, •) je grupa, neboli (H, •) je podgrupa grupy (G, •) a platí 1. ■ Poznámka. Jak bylo řečeno dříve, předchozí větu používáme k praktickému ověřování toho, zda je (H, •) podgrupou grupy (G, •). Obvykle postupujeme tak, že použijeme část 2., tzn. dokazujeme, že: 1. H CG A Hr® 2. a,b E H libovolné =>• a ■ b E H 3. a E H libovolné =>• a-1 G -H". Příklad 2.1. Uvedeme několik užitečných příkladů podgrup v grupách. 1. Každá grupa (G, •) má vždy dvě podgrupy, a sice podgrupu ({e}, •) a podgrupu (G, •). Tyto podgrupy se nazývají nevlastní podgrupy grupy (G, •). Ostatní podgrupy (pokud existují) se potom nazývají vlastní podgrupy grupy (G, •). 2. V grupě (C, +) všech komplexních čísel, s operací obyčejného sčítání čísel jsou podgrupami například (M, +) nebo (Q, +) nebo (Z, +). 3. V grupě (R— {0}, •) všech nenulových reálných čísel, s operací obyčejného násobení čísel jsou podgrupami například (Q — {0}, •) nebo (M+, •), kde R+ značí množinu všech kladných reálných čísel. 4. V grupě (C — {0}, •) všech nenulových komplexních čísel, s operací obyčejného násobení čísel jsou podgrupami například - podgrupa (E. — {0}, •) ; - podgrupa (G, •), kde G = {z E C | | z | = 1} (tzn. G je množina všech komplexních čísel, která leží na jednotkové kružnici) ; - podgrupa (Gn, •), kde n je pevné přirozené číslo a Gn = {z E C \ zn = 1 } (tzn. Gn je množina všech n-tých odmocnin z 1). Z tohoto příkladu vidíme, že v grupě, která má nekonečný počet prvků mohou existovat podgrupy, které mají jak nekonečný, tak i konečný počet prvků. 78 Poznamenejme, že v grupách (C, + ), resp. (R. — {0}, •), resp. (C — {0}, •) existuje mnohem více podgrup, než které jsme v předchozích příkladech uvedli. Jinými slovy řečeno, uvedené příklady zdaleka nevyčerpávají všechny podgrupy v uvedených grupách. Na druhé straně je možné podat poměrně jednoduchý popis všech podgrup v grupě (Z, +), který si dále uvedeme. Nejprve však zavedeme jedno označení. Označení. Nechť k značí libovolné celé nezáporné číslo. Pak symbolem k ■ Z budeme označovat množinu všech celočíselných násobků čísla k , tzn. k • Z = {k ■ z | zeZ libovolné } . Následující věta nyní ukáže, že všechny podgrupy v grupě (Z, +) jsou právě podgrupy {k • Z, +), kde k je libovolné celé nezáporné číslo. Věta 2.4. (H, +) je podgrupou grupy (Z, +) -<=> existuje celé nezáporné číslo k tak, ž e H = k-Z . Důkaz. Dokážeme postupně obě implikace. Důkaz implikace "=>" . Nechť (H, +) je libovolná podgrupa grupy (Z, +). Jestliže množina H neobsahuje žádné přirozené číslo, pak musí být H = {0} (proč ?) , což znamená, že H = 0 • Z a množina .ff" je požadovaného tvaru. Nechť tedy množina H obsahuje alespoň jedno přirozené číslo. Potom nejmenší přirozené číslo, které náleží do množiny H, označme k (rozmyslete si, že toto číslo skutečně existuje !). Nyní dokážeme, že H = k ■ Z. "C" nechť x E H libovolné. Pak podle věty o dělení celých čísel se zbytkem existují čísla q, r E Z tak, že x = q ■ k + r A 0 < r < k . Ale k E H, tzn. potom také —q-keH (pozor - zde je nutno symbol • chápat ve smyslu celočíselného násobku prvku v grupě, tzn. ve smyslu "opakovaného sčítání"). Kromě toho je x G H , odkud dostáváme, že: x + (—q -k) = r G H . Pak ale musí být r = 0 (jinak dostáváme spor s volbou čísla k), a tedy x = q ■ k G k ■ Z. " Z>" nechť x E k -Z libovolné. Pak existuje s G Z tak, že x = k ■ s . Ale k G H , a tedy také s ■ k = x G H. (pozor - zde opět symbol • chápeme ve smyslu celočíselného násobku prvku v grupě, tzn. ve smyslu "opakovaného sčítání"). Důkaz implikace "^=" . Nechť H = k ■ Z, kde k je pevné celé nezáporné číslo. Užitím věty 2.3.2 dokážeme, že (k ■ Z, +) je podgrupou grupy (Z, +). Tedy : 1. zřejmě je k-Z C Z A fe-Z^0 2. a,b E k ■ Z =>• 3 x,y E Z : a = k ■ x , b = k ■ y =>• a + b = k ■ (x + y) E k ■ Z 3. a E k ■ Z =>• 3 x E Z : a = k ■ x =>• —a = k ■ (—x) E k ■ Z . ■ 79 Vidíme tedy, že v grupě (Z, +) existuje nekonečně mnoho podgrup, které musí být výše popsaného tvaru. Specielně, podgrupami grupy (Z, +) jsou například: 0-Z = {0} , 1 • Z = Z, 2 • Z (což je množina všech celých sudých čísel), 3 • Z (což je množina všech celočíselných násobků čísla 3), atd. Podobným způsobem, jako jsme popsali všechny podgrupy v grupě celých čísel (Z,+), se dají charakterizovat všechny podgrupy v grupě zbytkových tříd (Zm,+). Podrobný důkaz nebudeme v tomto případě provádět, ale pouze si všechny podgrupy popíšeme. Přitom platí: 1. podgrup v grupě (Zm, +) je tolik, kolik je přirozených dělitelů čísla m. 2. je-li k přirozeným dělitelem čísla m, potom jemu odpovídající podgrupou je podgrupa ( {Co , Ck , Cik , ■ ■ ■ , Cm-k} , + ) • Všimněme si, jak je podgrupa odpovídající děliteli k zkonstruována. Patří do ní vždy zbytková třída Co a následně další zbytkové třídy, které dostaneme tak, že k indexu předchozí zbytkové třídy přičítáme číslo k, a to provádíme tak dlouho, "dokud to jde". Příklad 2.2. 1. Je-li m prvočíslo, potom má grupa (Zm, +) pouze nevlastní podgrupy, tzn. podgrupy (Zm,+) a ({C0},+), které odpovídají postupně dělitelům lam daného modulu m. 2. Vypišme všechny podgrupy v grupě (Z6, +). Číslo 6 má čtyři přirozené dělitele, a sice 1,2,3,6, a grupa (Zq,+) má tedy právě následující čtyři podgrupy: ( {Co,Ci,C2,C3,C4,Cs} , +) = (Z6,+), ({Co,C2,C4}, +), ({Co,C3},+), ({Co},+). 80 3. Algebraické struktury se dvěma operacemi. V tomto paragrafu se budeme zabývat algebraickými strukturami se dvěma operacemi, tzn. množinami, na kterých jsou definovány dvě operace. Přitom pro jednu operaci budeme používat aditivní symboliku a pro druhou operaci multiplikativní symboliku. Uvidíme, že zaváděné pojmy budou opět do jisté míry zobecňovat vlastnosti běžných algebraických struktur se dvěma operacemi, se kterými se pracuje na střední škole, tj. celých čísel, resp. racionálních čísel nebo reálných čísel s operacemi obyčejného sčítání a násobení čísel. Definice. Nechť R je množina se dvěma operacemi + a • taková, že platí: 1. (R , + ) je komutativní grupa 2. (R , •) je pologrupa 3. platí distributivní zákony, tzn. pro každé a,b,c G R platí: a ■ (b + c) = a ■ b + a ■ c A (a + b) ■ c = a • c + b ■ c Pak množina R s operacemi + a • se nazývá okruh a označuje se (R , + , •). Jestliže navíc - operace • je komutativní, potom se okruh (R, + , •) nazývá komutativní okruh - pologrupa (R, •) má neutrální prvek (jedničku), potom se okruh (iž, + , •) nazývá okruh s jedničkou. Poznámka. 1. Operaci + v okruhu (R, +, •) budeme nazývat sčítání. Neutrální prvek grupy (R, + ) budeme nazývat nula okruhu (R, +, •) a označovat symbolem 0. Opačný prvek k prvku a budeme označovat symbolem —a. Místo zápisu a + (—b) budeme používat stručnější zápis : a — b. 2. Operaci • v okruhu (R, + , •) budeme nazývat násobení. Neutrální prvek pologrupy (R, •) budeme (jak je vidět z definice) nazývat jednička okruhu (R , + , •) a označovat symbolem 1. Tento symbol pochopitelně nemá obecně nic společného s číslem 1. 3. Pokud se v některém výrazu objeví obě operace bez uzávorkování (jako například na pravých stranách distributivních zákonů), pak budeme vždy předpokládat, že násobení "má přednost" před sčítáním, tzn. budeme dodržovat stejnou úmluvu, jaká se na střední škole zavádí pro obyčejné násobení a sčítání čísel. Příklad 3.1. 1. Značí-li +, resp. • obyčejné sčítání, resp. obyčejné násobení čísel, pak (Z, +, •), (Q, + , •), (R, + , •) a (C , + , •) jsou okruhy. Dalšími okruhy jsou pak například : (Z[^2], + ,•), kdeZ[V2] = {a + bV2 \ a,beZ} (Q(v^) , + ,•)> kde Q(v^) = {a + b^2 | a, b G Q} . 81 2. Na množině R x R definujme operace + a • takto: pro libovolné (a, 5), (c, d) G R x R položme (a, b) + (c, d) = (a + c, b + d) a (a, b) ■ (c, d) = (a • c, b ■ d) kde symboly + a • na pravých stranách značí obyčejné sčítání a násobení čísel. Potom (R x R, + , •) je okruh. 3. Je-li R jednoprvková množina, například R = {x}, pak je zřejmě možno definovat na množině R operaci pouze jedním způsobem. Položíme-li nyní: XI ry* ----- ry* r\ ry . ry ----- Of potom [R, + , •) je okruh, který budeme nazývat triviální okruh. Triviální okruh je jakýmsi "nepřirozeným" příkladem okruhu, ve kterém obě operace splývají, a proto jej často budeme z našich úvah vylučovat. 4. Všechny doposud uvedené příklady okruhů byly komutativní okruhy. Jednoduchý příklad nekomutativního okruhu bude uveden v kurzu lineární algebry, v souvislosti se studiem matic. Další důležitý příklad okruhu je možno sestrojit na množině Zm zbytkových tříd podle modulu m. Připomeňme, že na množině Zm — \Co i Ci■> • • • i Cm-1\ jsme již dříve definovali operaci sčítání + takto: pro C/^5 Oj G ^777, jsme položili Ci + C j = Cr , kde r je zbytek po dělení čísla i + j číslem m. Analogickým způsobem nyní definujeme na množině Zm operaci násobení zbytkových tříd. Definice. Na množině Zm všech zbytkových tříd podle modulu m definujeme operaci násobení zbytkových tříd podle modulu m (kterou označíme symbolem •) takto: pro Cj, C j G Zm položíme: Ci ■ Cj = Cs , kde s je zbytek po dělení čísla i ■ j číslem m. Poznamenejme, že definici násobení zbytkových tříd podle modulu m je možné (rozepsáním věty o dělení se zbytkem celých čísel) formálně přepsat do tvaru: Ci ■ C j = C g , kde i ■ j = z ■ m + s A 0 a-byt0 Většinou bývá v tomto případě jednodušší dokazovat obměnu předchozí implikace, tzn. implikaci k E E (ai ■ hj) =ij=i )■ 85 a-b = 0 => (a = 0 V 5 = 0). Technicky bude potom obvykle nejvýhodnější postupovat tak, že budeme dokazovat například implikaci (a-b = 0 A a/0) => 6 = 0. Definice. Okruh (R , + , •), který je netriviální, je komutativní, má jedničku a nemá dělitele nuly se nazývá obor integrity. Příklad 3.3. 1. Klasickým příkladem oboru integrity je okruh celých čísel (Z , + , •). Dalšími příklady oborů integrity jsou pak okruhy (Q , + , •), (R, + , •) , (C , + , •), (Z[y/2], + ,-), (Q(v^), + , •) uvedené v příkladu 3.1.1. 2. Okruh (R x R, + , •) z příkladu 3.1. 2 není oborem integrity, protože má dělitele nuly (jak jsme ukázali v předchozím příkladu). 3. Okruh (Zm , + , •) zbytkových tříd podle modulu m je pro m > 2 vždy netriviálním, komutativním okruhem s jedničkou. Tento okruh tedy je (resp. není) oborem integrity podle toho, zda nemá (resp. má) dělitele nuly. Z předchozího příkladu tedy vyplývá, okruh (Z7 , + , •) je oborem integrity, zatímco okruh (Zß , + , •) oborem integrity není. Z předchozího příkladu vidíme, že některé okruhy zbytkových tříd jsou obory integrity, zatímco jiné naopak obory integrity nejsou. Přesně tuto situaci rozebírá následující věta. Věta 3.4. Okruh (Zm , + , •) zbytkových tříd podle modulu m je oborem integrity <=> modul m je prvočíslo. Důkaz. Připomeňme, že celé číslo je prvočíslem, jestliže je větší než 1 a má pouze nevlastní dělitele. Důkaz implikace " =>" . Nechť okruh (Zm , + , •) je oborem integrity. Pak je netriviálním okruhem a tedy musí být m > 1. Zbývá dokázat, že m má pouze nevlastní dělitele. Budeme postupovat sporem. Předpokládejme, že m má nějakého vlastního dělitele. Potom má také kladného vlastního dělitele (proč?), kterého označíme r. Platí tedy: 1 < r < m a existuje s G Z, tak že : r ■ s = m. Potom však musí být 1 < s < m, a tedy Cr,Cs G Zm, přičemž Cr ^ Cq , Cs 7^ C q a Cr ■ Cs = Cq . To však znamená, že Cr, Cs jsou dělitelé nuly v (Zm , + , •), což je spor s předpokladem, že (Zm , + , •) je obor integrity. Tedy m nemá žádné vlastní dělitele a dokázali jsme tak, že m je prvočíslo. 86 Důkaz implikace " <=" . Nechť m je prvočíslo. Potom m > 1, což znamená, že okruh (Zm, +, •) je netriviální. Dále víme, že okruh zbytkových tříd je vždy komutativní a má jedničku. Zbývá tedy dokázat, že (Zm , + , •) nemá dělitele nuly. Nechť tedy Cr,Cs G Zm jsou zbytkové třídy takové, že Cr ■ Cs = Cq A Cr ^ Cq . Pak z definice násobení zbytkových tříd plyne (rozmyslete si proč), že m\ r■s A m\ r . Protože však m je prvočíslo, pak (podle věty 4.4.3 z kapitoly L) musí m dělit s, což znamená, že Cs = Cq . Dokázali jsme tak, že okruh (Zm , + , •) nemá dělitele nuly. Tedy okruh (Zm , + , •) je oborem integrity. ■ Věta 3.5. Necht (R, + , •) je okruh a nechť a,b, c G R . Pak následující výroky jsou ekvivalentní. 1. okruh (R, + , •) nemá dělitele nuly 2. a ■ b = a ■ c A a ^ 0 =>• b = c 3. b ■ a = c ■ a A a ^ 0 =>• b = c Důkaz Tvrzení dokážeme obvyklým způsobem, tzn. budeme postupně dokazovat tři implikace. Důkaz implikace "1. =>• 2." . Nechť platí výrok 1. a nechť a ■ b = a ■ c A a^O. Potom a ■ b — a ■ c = 0, tzn. a • {b — c) = 0 . Protože a/0 a okruh nemá dělitele nuly, musí být b — c = 0 , a tedy 6 = c. Důkaz implikace "2. =>• 3." . Nechť platí výrok 2. a nechť b ■ a = c ■ a A a ^ 0 . Potom (6 — c) • a = 0. Podle věty 3.2.2 je součin libovolného prvku s nulou okruhu roven nule okruhu, a tedy specielně musí být {b — c) • 0 = 0 . Dostáváme tedy (b-c)-a = 0 = (b - c) ■ 0 . Pokud by bylo (b — c) 7^ 0, pak bychom užitím 2. dostali a = 0, což by byl spor s předpokladem, že a ^ 0. Musí tedy být (6 — c) = 0, odkud již plyne, že b = c. Důkaz implikace "3 =>• 1" . Nechť platí výrok 3. Dále postupujeme sporem, tzn. předpokládáme, že okruh (R , + , •) má dělitele nuly. Potom existují prvky x,y G R takové, žei/0,j/^0a x ■ y = 0. Podle věty 3.2.2 je součin nuly okruhu s libovolným prvkem roven nule, tzn. platí také 0 • y = 0 . Dostáváme tedy x ■ y = 0 = 0 • y odkud užitím 3. plyne, že x = 0, což je spor. Dokázali jsme tak, že okruh (R, +, •) nemá dělitele nuly. ■ Podmínky 2. a 3. z předchozí věty se nazývají omezené zákony o krácení (levý a pravý). Slovo "omezené" naznačuje, že nemůžeme krátit všemi prvky z R (v našem případě nelze krátit nulou okruhu). 87 Na závěr našich úvah o algebraických strukturách se dvěma operacemi se budeme zabývat dalším speciálním případem okruhu, s nímž se budeme často setkávat. Definice. Nechť (R, + , •) je komutativní okruh s vlastností, že množina jeho nenulových prvků s operací násobení je grupa. Pak (R , + , •) se nazývá těleso. Následující větu můžeme s výhodou použít při praktickém ověřování toho, zda konkrétní okruh je či není tělesem. Věta 3.6. Nechť (R , + , •) je netriviální, komutativní okruh s jedničkou. Pak (R, + , •) je těleso právě když ke každému nenulovému prvku z R existuje prvek inverzní. Důkaz. Důkaz implikace " =>" . Platnost této implikace okamžitě vyplývá z definice tělesa. Důkaz implikace " -<=" . Podle předpokladu je okruh (iž, + , •) komutativní. Budeme tedy dokazovat, že množina všech nenulových prvků z i? s operací násobení, tj. (R — {0} , •), je grupou. Nejprve dokažme, že (R — {0} , •) je grupoid, tzn. jinak řečeno, že v okruhu (R, + , •) neexistují dělitelé nuly. Nechť tedy pro prvky x,y G R platí: x ■ y = 0 A x ^ 0. Podle předpokladu však k prvku x existuje prvek inverzní x~x, tzn. po úpravě je x-1 • (x ■ y) = x~x ■ 0 =>• (x-1 • x) ■ y = 0 =>• y = 0. Tedy [R — {0}, •) je grupoid a z ostatních předpokladů již bezprostředně plyne, že (R — {0} , •) je grupa. Dokázali jsme tak, že (R, + , •) je těleso. ■ Příklad 3.4. 1. Okruhy (Q , + , •), (R, + , •), (C , + , •) jsou tělesa. 2. Na množině Q x Q definujme operace + a • takto: (a, b) + (c, d) = (a + c , b + d) , (a, b) ■ (c, d) = (ac — 3bd, ad + bc). Potom (Q x Q, + , •) je těleso (dokažte si sami, rozepsáním definice tělesa). 3. Okruh (Zm , + , •) zbytkových tříd podle modulu rn je tělesem právě když modul rn je prvočíslem (plyne z věty 3.4, a věty 3.8). 4. Okruhy (Z , + , •) a (Z[y/2}, + , ■) (viz příklad 3.1.1) nejsou tělesa. Podobně, okruh (lxl, + , •) z příkladu 3.1. 2 není tělesem a dále též triviální okruh není tělesem. V tomto paragrafu jsme zavedli tři základní algebraické struktury se dvěma operacemi: okruh, obor integrity a těleso. Víme již, že obor integrity je vždy okruhem, ale okruh nemusí vždy být oborem integrity. Nyní si všimneme, jaký je vzájemný vztah mezi obory integrity a tělesy. 88 Věta 3.7. Každé těleso je oborem integrity. Důkaz. Nechť (R , + , •) je těleso. Potom: 1. (R, + , •) je netriviální okruh. V opačném případě by by totiž množina jeho nenulových prvků R — {0} byla prázdná a tedy (R — {0} , •) by nebyla grupou. 2. (R, + , •) je komutativní okruh, což plyne přímo z definice tělesa. 3. (R, + , •) je okruhem s jedničkou. Jedničkou tělesa bude jednička e grupy (R — {0} , •), protože pro každý nenulový prvek y E R pak je y ■ e = e ■ y = y a pro nulu platí 0 • e = e • 0 = 0 (podle věty 3. 2. 2). Dohromady tedy je x ■ e = e ■ x = x pro Vx G R. 4. (R, + , •) nemá dělitele nuly. Množina nenulových prvků tělesa je vzhledem k operaci násobení grupou, tzn. je také grupoidem, a tedy součin dvou nenulových prvků je opět nenulovým prvkem. Dohromady tak dostáváme, že (R, + , •) je oborem integrity. ■ Předchozí větu není možné obrátit, tzn. obor integrity nemusí být obecně tělesem. Například okruh celých čísel (Z, +, •) je oborem integrity, který není tělesem (protože například k číslu 2 zde neexistuje inverzní prvek). Je-li však množina R konečná, potom obrácení předchozí věty možné je, jak vyplývá z následující věty. Znamená to tedy, že pro konečné množiny pojmy obor integrity a těleso splývají. Věta 3.8. Každý konečný obor integrity je tělesem. Důkaz. Nechť (R, + , •) je konečný obor integrity a nechť množina R sestává z n prvků (n > 2). Podle předpokladu je (R , + , •) netriviální, komutativní okruh s jedničkou, tzn. podle věty 3.6 stačí dokázat, že k libovolnému nenulovému prvku z R existuje prvek inverzní. Nechť tedy a G R — {0} . Uvažme množinu M = {a-x\xER— {0} libovolný } , která je podmnožinou množiny R— {0} (protože daný obor integrity nemá dělitele nuly). Množina M je konečná a má stejný počet prvků jako množina R — {0} , protože podle věty 3.5.2 (použijeme obměnu implikace) pro Xi,X2 G R — {0} platí: 11/12 =>• a ■ xi ^ a ■ X2 ■ Musí tedy být M = R — {0}, což ale znamená, že určitě existuje prvek xo G R — {0} takový, že a ■ Xq = 1. Prvek xq je potom hledaným inverzním prvkem k prvku a . ■ S pojmem tělesa se bude pracovat i v jiných matematických disciplínách. Pokud chceme situaci co nejvíce zjednodušit (při zachování většiny podstatných vlastností), omezujeme se často na tělesa, jejichž prvky budou čísla a operacemi budou obyčejné sčítání a násobení čísel. Nyní taková tělesa zavedeme a ukážeme některé jejich příklady a základní vlastnosti. 89 Definice. Nechť (T , +, •) je těleso takové, že T C C a +, resp. • značí obyčejné sčítání, resp. obyčejné násobení čísel. Pak (T , + , •) se nazývá číselné těleso . Praktické ověřování toho, zda je (T, + , •) číselným tělesem provádíme pomocí následující věty. K ní předem poznamenejme, že ve smyslu dříve zavedených úmluv bude a — b znamenat obyčejný rozdíl čísel a, 5 a podobně | bude značit obyčejný podíl čísel a, b (kde 5^0). Věta 3.9. Necht T je alespoň dvouprvková podmnožina množiny C všech komplexních čísel a + , resp. ■ značí obyčejné sčítání, resp. obyčejné násobení čísel. Potom (T, + , •) je číselným tělesem právě když platí : 1. a,beT => a-beT 2. a,beT A b^O => f GT. Důkaz. Tvrzení věty ihned plyne z definice tělesa, z věty 2.3. a ze známých vlastností platných pro počítání s čísly. ■ Příklad 3. 5. 1. (Q , + ,•), (R , + ,•), (C , + , •) jsou zřejmě číselnými tělesy. 2. (Q(v^), + , •) je číselné těleso. Připomeňme, že Q(VŽ) = {a + b ■ \[2 \ a, b G Q} . Pro ilustraci ověřme (s využitím předchozí věty), že se skutečně jedná o číselné těleso. Množina Q(-\/2) je nekonečná, tzn. je tedy alespoň dvouprvková. Nechť a + b\[2 , c + dy/2 G Q(\/2), tzn. a, 5, c, d e Q . Potom: 1. (a + bVŽ) - (c + dVŽ) = (a-c) + (b-d)V2 E Q(^2), 2. nechť navíc c + d\pi ^ 0 . Potom též c — d^/2 ^ 0 (proč ?) a platí: a + b\[2 a + b\pi c — d\[2 ac — 2bd bc — ad r- r- ^Wl = ^Wl'^ďTI = C2 - 2d2 + C2 _ 2d2 • V2 G ^V2)' Tedy podle věty 3. 9 je (^^(v^), + , •) číselným tělesem. 3. Při stejném označení lze podobným způsobem dokázat, že například (Q(v/p), + , •), kde p je libovolné prvočíslo, je číselné těleso. 4. Označme Q(i) = {a + bi \ a, b G Q} . Potom (Q(i), + , •) je číselné těleso, což se ukáže obdobným výpočtem jako ve 2. části tohoto příkladu. Z předchozích příkladů především vidíme, že číselných těles je nekonečně mnoho a dále, že se neomezují pouze na reálnou osu. K příkladům 3.5.3 a 3.5.4 poznamenejme, 90 že se jedná o speciální příklady obecnějšího tvrzení, podle kterého jsou číselnými tělesy všechny množiny tvaru Q(Vď) = {a + b-Vď | a,öGQ} (s operacemi obyčejného sčítání a obyčejného násobení čísel), přičemž d je libovolné celé číslo, takové, že d ^ 0,1 a d není dělitelné druhou mocninou přirozeného čísla většího než 1. Odmocninu přitom chápeme jako libovolnou z obou druhých odmocnin z čísla d v oboru komplexních čísel (tzn. libovolné z obou řešení rovnice x2 = d v C). Rozebereme-li předchozí příklady číselných těles, pak zjistíme, že všechna uvedená číselná tělesa vždy obsahovala všechna racionální čísla. Skutečnost, že tomu tak musí být vždycky, ukazuje následující věta. Věta 3.10. Nechť (T , + , •) je libovolné číselné těleso. Potom množina T obsahuje množinu Q všech racionálních čísel. Důkaz. Z definice tělesa plyne, že musí existovat nenulový prvek a G T. Potom ale platí, že - = 1 G T, tzn. množina T obsahuje číslo 1. Sečteme-li jedničku se sebou samou libovolný konečný počet-krát, pak výsledek opět musí ležet v T, a tedy T obsahuje množinu všech přirozených čísel. Dále: a — a = 0 G T a pro libovolné přirozené číslo x ET musí být i 0 — x = —x G T. Tedy množina T obsahuje nulu a všechna záporná čísla. Dohromady pak TDZ. Konečně, v T leží i podíl libovolných dvou celých čísel (s nenulovým jmenovatelem), tzn. v T leží každé racionálni číslo. Dostáváme tak, že TDQ. ■ 91 4. Homomorfizmy algebraických struktur. V tomto paragrafu se budeme zabývat studiem vzájemných vztahů mezi algebraickými strukturami se stejným počtem operací. K tomu účelu budeme používat zobrazení mezi těmito algebraickými strukturami, která budou "zachovávat operace" a na základě toho potom ve větší či menší míře "přenášet danou strukturu". Úmluva. Při označování algebraických struktur jsme doposud vždy kromě symbolu nosné množiny důsledně vypisovali i symbol operace či operací. Zavedme nyní úmluvu, že z důvodů stručnosti zápisu budeme symboly operací podle potřeby vynechávat, a to zejména tam, kde nebude nebezpečí nedorozumění a z kontextu bude jasné, o jakou operaci, resp. operace se jedná. Budeme tedy místo obratu "grupoid (G, •)" říkat stručně "grupoid Gn nebo místo "těleso (Q, + , •)" budeme říkat "těleso Q" , atd. Při tom budeme mít na paměti, že se nejedná pouze o množiny, ale jedná se o množiny s operacemi. Definice. Nechť {G , •) a (H, *) jsou grupoidy a nechť íp : G —> H je zobrazení takové, že (1) íp (a • b) = H, pak také říkáme, že grupoid (pologrupu, grupu) G lze vnořit do grupoidu (pologrupy, grupy) H. 3. V předchozí definici homomorfizmu je jasné, že operace • a * jsou obecně různé, což plyne již z použitého označení. Pro jednoduchost zápisu budeme v dalším obě operace označovat obvykle stejným symbolem, většinou symbolem •. Při tom nebude moci dojít k nedorozumění, protože ze souvislostí a ze samotného zápisu bude vždy patrné, o kterou z obou operací se jedná. Příklad 4.1. f. Nechť G je libovolný grupoid. Pak identické zobrazení ida '■ G —> G je vždy homomorfizmus, který je navíc vždy izomorfizmem. 2. Nechť G je libovolný grupoid a nechť H je grupoid s neutrálním prvkem e. Potom zobrazení íp : G —> H , definované :

Zm , definované pro každé a G Z vztahem: íp (a) = Cr , kde r je zbytek po dělení čísla a číslem m je homomorfizmus (dokažte si sami rozepsáním, pomocí věty o dělení se zbytkem celých čísel). Tento homomorfizmus není vnoření a není izomorfizmus. 4. Uvažme pologrupu (N, + ) a grupu (Z x Z , + ), kde operací je "sčítání po složkách" , tzn. (a, b) + (c, d) = (a + c, b + d) . Definujme nyní zobrazení íp : N—)>ZxZ vztahem: íp(x) = (x,0), proVxGN. Potom

R vztahem: ip (x) = In x , pro V a; G R+ . Potom íp je bijekce (proč?) a pro každé a, b E R+ platí:

(5). Dohromady tedy dostáváme, že

G vztahem: íp (Cj) = Xi, pro i = 0,1, 2 . Potom íp je izomorfizmus (což je v podstatě ihned vidět z obou tabulek operací). Věta 4.1. Nechť G, H, K jsou grupoidy, nechť íp : C —> H a t/j : H —> K jsou homomorfizmy. Potom platí : 1. složení homomorfizmů xp o íp je opět homomorfizmus 2. je-li íp izomorfizmus, pak inverzní zobrazení íp~l je také izomorfizmus. 93 Důkaz. 1. Zřejmě íp o ip : G —y K . Nechť a, b G G libovolné. Potom: (ipo-1(ií) = a A (^_1(w) = 6. Dostáváme tak: u ■ v =

• p(G) je komutativní 3. G je asociativní =>• <£>((?) je asociativní. Důkaz. Nechť (G, •) a (fí, •) jsou uvažované grupoidy. Nechť u, v G <£>(£?) jsou libovolné prvky. Pak existují prvky a,b E G tak, že

(£?) • 2. Nechť G je komutativní grupoid. Potom u ■ v =

H je homomorfizmus. Pak množinu Ker

H je homomorfizmus. Pak platí: 1. ip(eG) = eH 2. (p{a~x) = (p (a) _1 pro každé a E G 3. jádro Ker

H je grupový homomorfizmus. 1. Pro jedničku eG grupy G a jedničku ejj grupy H platí: (p (eG) ■ (p (eG) = (p(eG-eG) = (p (eG) = p> (eG) ■ eH odkud užitím zákona o krácení (který v grupě platí) dostáváme, že

H je homomorfizmus. Pak platí: zobrazení íp je injektivní ^ Ker íp = {eo} Důkaz. Tvrzení budeme dokazovat obvyklým způsobem, ve dvou krocích. Důkaz implikace " =>" . Nechť íp je injektivní zobrazení. Budeme dokazovat, že Ker íp = {ea} ■ Jedná se o možinovou rovnost, tzn. dokážeme obě množinové inkluze. "C": Nechť x G Keríp. Potom íp (x) = en = f (gg) ■ Ale zobrazení ip je injektivní, tzn. x = ea , neboli x G {ea} ■ " Z>": Tato inkluze zřejmě platí, protože (podle věty 4.3.1) je íp (ea) = &H , což znamená, že ea G Ker íp . Důkaz implikace " -<=" . Předpokládáme, že Keríp = {ea} a dokážeme, že íp je injektivní. Ale íp(x) = íp(y) =>• íp (x) ■ íp (y)'1 = eH => íp (x ■ y'1) = eH =*► x-y'1 e Keríp, což však podle předpokladu znamená, že x ■ y~x = ea , neboli x = y. Dokázali jsme tedy, že zobrazení íp je injektivní. ■ Definice. Řekneme, že grupoidy (resp. pologrupy, resp. grupy) G, H jsou izomorfní, jestliže existuje izomorfizmus íp : G —> H . Píšeme pak G = H. Poznámka. Předchozí definice je zformulována korektně, neboť z věty 4.1. 2 plyne, že je-li G = H , potom je také H = G a můžeme tedy říkat, že G, H (bez ohledu na pořadí) jsou izomorfní. Připomeňme ještě, že zřejmě platí G = G a dále také platí: G 9áH A H 9iK =^ G 9iK (rozmyslete si podrobně proč !). 96 Z našich dosavadních úvah a tvrzení vyplývá, že izomorfní grupoidy (resp. polo-grupy, resp. grupy) se mezi sebou z algebraického hlediska vůbec neliší. Pomineme-li totiž konkrétní smysl prvků a konkrétní smysl operací, pak vidíme, že dvě izomorfní algebraické struktury mají naprosto stejné všechny vlastnosti, které je možno zformulovat pomocí operace na dané množině, tj. například komutativnost, asociativnost, existence neutrálního prvku, atd. Pěkně je to vidět třeba v příkladu 4.1.6, kde obě grupy jsou konečné, mají stejný počet prvků a tabulky operací jsou "stejné". Z algebraického hlediska je potom nepodstatné, že v jednom případě se jedná o zbytkové třídy a jejich sčítání a ve druhém případě se jedná o jistá komplexní čísla a jejich násobení. Z těchto důvodů je v matematice obvyklé v případě potřeby izomorfní algebraické struktury ztotožňovat. To znamená, že každý prvek jedné struktury se potom považuje za totožný s tím prvkem druhé struktury, který je jeho obrazem při daném izomorfizmu a navíc se nečiní rozdíl mezi operacemi v obou strukturách. Do jisté míry podobná situace nastává též u vnoření. Máme-li vnoření (tzn. in-jektivní homomorfizmus)

H, pak zřejmě zobrazení

Z x Z popsaného v příkladu 4.1.4 nám umožňuje považovat polo-grupu (N, +) za podpologrupu grupy (Z x Z , + ) , přičemž ztotožníme prvek x G N s jeho obrazem

S je zobrazení takové, že pro libovolné prvky a,b G R platí:

-R je izomorfizmus okruhu R na sebe. 2. Vezměme okruh celých čísel (Z, + , •) a okruh (Zm , + , •) zbytkových tříd podle modulu m. Pak zobrazení

Zm definované pro každé a G Z vztahem

(a) ■

(b) pro V a, b G Z . Označme : íp (a) = Ci, <£> (5) = Cj . Potom existují celá čísla zi, zi tak, že platí a = zim + i, kde 0 < z < m A b = z^vri + j , kde 0 < j < m . Po vynásobení čísel a, b a následné úpravě dostáváme: a ■ b = [z\'m + i) ■ {z^m + j) = (z\z<2,vri + z\j + iz^) ■ m + i ■ j odkud plyne, že a-b = i-j (mod m), což znamená, že čísla a-b a i-j dávají po dělení číslem m stejný zbytek, který označíme například k. Potom z definice zobrazení ip a z definice násobení zbytkových tříd plyne, že íp(a-b) = Ck = Q ■ C j = íp (a) ■ íp (b) což je požadovaný vztah. Definice. Nechť R, S jsou okruhy a ip : R —> S je homomorfizmus. Potom množina Ker íp = {x E R \ íp (x) = Os} se nazývá jádro homomorflzmu íp . Základní vlastnosti okruhových homomorfizmů budou analogické odpovídajícím základním vlastnostem homomorfizmů algebraických struktur s jednou operací, jak vyplývá z následujících vět. Věta 4. 5. Nechť R, S, T jsou okruhy, nechť íp : R —> S a t/j : S —> T jsou homomorfizmy těchto okruhu. Potom platí : 1. složení homomorfizmů íp o íp je opět homomorfizmus 2. je-li íp izomorfizmus (okruhů), pak inverzní zobrazení íp~x je také izomorfizmus. Důkaz. Důkaz tvrzení se provede analogicky jako důkaz obdobné věty pro grupoidy, tzn. jako důkaz věty 4.1. ■ Věta 4.6. Nechť R, S jsou okruhy a íp : R —> S je homomorfizmus. Pak platí: 1. p(0Ä) = Os 2. íp (—a) = — íp (a) pro každé a E R 3. zobrazení íp je injektivní ^ Ker íp = { Or } . Důkaz. Uvědomíme-li si, že (R, + ) a (S, + ) jsou grupy, pak je zřejmé, že 1. a 2. platí (jedná se vlastně o 1. a 2. část věty 4. 3, přeformulované do aditivní symboliky). 98 Tvrzení 3. okamžitě plyne z věty 4.4., vzhledem k tomu, že okruhový homomornzmus je současně homomorfizmem příslušných aditivních grup, tzn. grup (R, + ) a (S , + ) . ■ Jestliže existuje izomorfizmus

S je vnoření, pak můžeme podle potřeby ztotožnit okruh R s jeho obrazem