skripta od Horáka

š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) ∧ (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 A1,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ů A1,A2, ... ,An takto:
řekneme, že výroky A1,A2, ... ,An jsou ekvivalentní, jestliže platí Ai ⇔Aj pro každé
i,j = 1,...,n.
6
Větu tohoto tvaru většinou nedokazujeme ověřováním všech ekvivalencí Ai ⇔ Aj pro
každé inegationslash=j (kterých je celkem n·(n−1)), ale obvykle postupujeme tak, že dokážeme
platnost pouze n implikací tvaru:
A1 ⇒A2 , A2 ⇒A3 , ... , An−1 ⇒An , An ⇒A1.
Je jednoduché ukázat, že odsud již plyne ekvivalentnost všech výroků A1,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 ⇒ Aj (i negationslash= j), v nichž se
každý z výroků A1,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≥n0, kde n0 je nějaké pevně dané celé číslo. Nejčastěji je n0 = 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ů
α) dokážeme platnost výroku V(n0)
β) předpokládáme, že výrok V(n) platí pro n = n0,n0 + 1, ..., k a za tohoto před-
pokladu 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 mate-
matickou 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 ∈ A.
Skutečnost, že objekt x není prvkem množiny A (tzn. x nepatří do A) pak budeme
zapisovat: xnegationslash∈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 vlast-
nost množin se nazývá extenzionalita. Můžeme tedy psát:
A = B ⇔ (∀x)(x∈A ⇔ x∈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 ∅.
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 a a1,a2,...,an jsou všechny její prvky, pak píšeme
A = {a1,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ů a1,a2,...,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ázd-
nou 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)},
čímž myslíme, že pro libovolné x platí: x∈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. Po-
znamenejme, ž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∈ Z ∧ x2 −1 = 0}
je dvouprvková množina sestávající z čísel 1 a -1, tzn. X = {1,−1}, zatímco množina
X = {x | x∈ Z ∧ x2 + 1 = 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 negationslash∈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 ∈ M či nikoliv. Jestliže však M ∈M, pak podle definice je Mnegationslash∈ M, což je spor.
Jestliže by bylo Mnegationslash∈M, pak podle definice dostáváme M∈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žinaAje podmnožina množinyB a píšemeA⊆B, jestliže libovolný
prvek množiny A je zároveň prvkem množiny B. Vztah ⊆ se nazývá množinová inkluze.
Jestliže A⊆B a Anegationslash= B, pak říkáme, že A je vlastní podmnožina množiny B a píšeme
A⊂B.
Máme-li dokázat, že A ⊆ B pak postupujeme tak, že vezmeme libovolný prvek
x ∈ A a dokážeme, že x ∈ B. Jestliže množina A není podmnožinou množiny B, pak
budeme psát A negationslash⊆ B. Chceme-li dokázat, že A negationslash⊆ B, pak (podle předchozích úvah
o negacích kvantifikovaných výroků) dokazujeme, že existuje prvek x takový, že x ∈ A
a zároveň xnegationslash∈B, a to nejlépe tak, že tento prvek konkrétně nalezneme.
Pro libovolné množiny A,B,C zřejmě platí:
A⊆A, ∅ ⊆A, (A⊆B ∧ B ⊆C) ⇒ A⊆C, A = B ⇔ (A⊆B ∧ B ⊆A).
Důležitý je zejména poslední z výše uvedených vztahů, pomocí kterého obvykle do-
kazujeme rovnost dvou množin A,B. Důkaz vedeme tak, že dokážeme nejdříve inkluzi
A⊆B a potom inkluzi B ⊆A.
Jsou-li A,B množiny, pak můžeme utvořit další množiny
A ∪B = {x | x∈A ∨ x∈B}
A ∩B = {x | x∈A ∧ x ∈B}
A − B = {x | x∈A ∧ x negationslash∈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 ne-
jenom 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 negationslash∈ A ∪B právě když xnegationslash∈A ∧ xnegationslash∈B
x negationslash∈ A ∩B právě když xnegationslash∈A ∨ xnegationslash∈B
xnegationslash∈A −B právě když xnegationslash∈A ∨ x∈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.
Nechť A,B,C jsou libovolné množiny. Pak platí:
1. A∪B = B∪A 2. A∩B = B∩A
3. (A∪B)∪C = A∪(B∪C) 4. (A∩B)∩C = A∩(B∩C)
5. A∩(B∪C) = (A∩B)∪(A∩C) 6. A∪(B∩C) = (A∪B)∩(A∪C)
7. A−(B∪C) = (A−B)∩(A−C) 8. A−(B∩C) = (A−B)∪(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:
”⊆”: x∈A−(B∩C) ⇒ x∈A ∧ xnegationslash∈ (B∩C) ⇒ x∈A ∧ (xnegationslash∈B ∨ xnegationslash∈C) ⇒
⇒ (x∈A ∧ xnegationslash∈B) ∨ (x∈A ∧ xnegationslash∈C) ⇒ x∈ (A−B) ∨ x∈ (A−C) ⇒
⇒ x∈ (A−B) ∪ (A−C).
”⊇”: x∈ (A−B) ∪ (A−C) ⇒ x∈ (A−B) ∨ x∈ (A−C) ⇒
⇒ (x∈A ∧ xnegationslash∈B) ∨ (x∈A ∧ xnegationslash∈C) ⇒ x∈A ∧ (xnegationslash∈B ∨ xnegationslash∈C) ⇒
⇒ x∈A ∧ xnegationslash∈ (B∩C) ⇒ x∈A−(B∩C). squaresolid
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 napoprve 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 I negationslash= ∅ libovolná
(tzv. indexová) množina a Ai je množina pro každé i∈I, pak
sjednocení množin Ai je množina uniontext
i∈I
Ai = {x | ∃i0 ∈I : x∈Ai0}
průnik množin Ai je množina intersectiontext
i∈I
Ai = {x | ∀ i∈I : x∈Ai}.
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ě I.
V případě, že I je konečná množina, například I = {1,2,...n}, píšeme též
A1 ∪A2 ∪···∪An , resp. A1 ∩A2 ∩···∩An .
V případě, že je I = N, píšeme též
∞uniontext
i=1
Ai, resp.
∞intersectiontext
i=1
Ai. Přitom je nutné zdůraznit, že
poslední dva zápisy samozřejmě není možné použít univerzálně pro jakoukoliv nekoneč-
nou indexovou množinu I.
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 sym-
bolem 2A. Konkrétně, například pro A = {x,y,z} je
2A = {∅,{x},{y},{z},{x,y},{x,z},{y,z},{x,y,z}}.
Podobně například pro A = ∅ je 2∅ = {∅}, 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 (a1,a2,...an). Přitom klademe
(a1,a2, ...,an) = (b1,b2, ...,bn) právě když a1 = b1 ∧ a2 = b2 ∧ ... ∧ 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
A×B = {(x,y) | x∈A, y ∈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×B a B×A jsou obecně různé. Je-li napříkladA = {a} a B = {x,y},
pak je:
A×B = {(a,x),(a,y)} a B×A = {(x,a),(y,a)},
a tedy A×B negationslash= B×A.
Dále je zřejmé, že je-li některá z množin A,B prázdná, tzn. A = ∅ nebo B = ∅,
pak i jejich kartézský součin je prázdná množina, tzn. A×B = ∅.
Analogickým způsobem zavádíme pro libovolné n ≥ 2 kartézský součin množin
A1,A2, ... , An , jako množinu
A1 ×A2 × ... ×An = {(a1,a2, ...,an) | ai ∈Ai, i = 1,2,...,n}.
11
Je-li A1 = 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,y,z∈ R 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. A×(B∪C) = (A×B)∪(A×C) 2. (A∪B)×C = (A×C)∪(B×C)
3. A×(B∩C) = (A×B)∩(A×C) 4. (A∩B)×C = (A×C)∩(B×C)
5. A×(B−C) = (A×B)−(A×C) 6. (A−B)×C = (A×C)−(B×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:
”⊆”: (x,y) ∈A×(B−C) ⇒ x∈A ∧ y ∈ (B−C) ⇒ x∈A ∧ (y ∈B ∧ y negationslash∈C) ⇒
⇒ (x,y) ∈ (A×B) ∧ (x,y) negationslash∈ (A×C) ⇒ (x,y) ∈ (A×B)−(A×C).
”⊇”: (x,y) ∈ (A×B)−(A×C) ⇒ (x,y) ∈ (A×B) ∧ (x,y) negationslash∈ (A×C) ⇒
⇒ (x∈A ∧ y ∈B) ∧ (xnegationslash∈A ∨ y negationslash∈C) ⇒ (x∈A ∧ y ∈B ∧ xnegationslash∈A) ∨
∨ (x∈A ∧ y ∈B ∧ y negationslash∈C) ⇒ x∈A ∧ (y ∈B ∧ y negationslash∈C) ⇒
⇒ x∈A ∧ y ∈ (B−C) ⇒ (x,y) ∈A×(B−C). squaresolid
Poznamenejme, že v některých množinových rovnostech uvedených ve větách 2.1.
a