Důkaz matematickou indukcí
Příklad.
Dokažte, že pro každé přirozené číslo \(n\) platí
\[
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}. \tag{P(n)}
\]
Řešení.
Pro \(n = 1\) máme
\[
1 = \frac{1(1+1)}{2} \implies P(1) \text{ platí}.
\]
(Obecný krok matematické indukce). Předpokládejme, že platí \(P(n)\) pro
nějaké
pevné \(n \in \mathbb{N}\). Ukažme, že pak platí též \(P(n+1)\). Máme
\begin{align*}
1 + 2 + 3 + \ldots + n + (n+1) &= \frac{n(n+1)}{2} + (n+1) \\
&= \frac{n(n+1) + 2(n+1)}{2} \\
&= \frac{(n+1)(n+2)}{2}.
\end{align*}
Tedy \(P(n+1)\) platí. Podle principu matematické indukce tedy platí
\(P(n)\)
pro všechna \(n \in \mathbb{N}\).
Jak lze zavést přirozená čísla axiomaticky pomocí tzv. Peanových axiómů, se můžete
dočíst
zde.
Další informace o matematické indukci naleznete zde.
Věta (Princip dobrého uspořádání).
Každá neprázdná podmnožina množiny přirozených čísel má nejmenší prvek.
Uveďme pár příkladů, kdy předchozí princip dobrého uspořádání neplatí.
Uvažujme množinu všech celých čísel \(\mathbb{Z}\) a podmnožinu
\[
\emptyset\neq M = \{k\in \mathbb{Z}: k < 0\}.
\]
Potom zřejmě \(M\) nemá nejmenší prvek. Podobně množina
\[
M = \{x \in \mathbb{R}: 0 < x\}
\]
je neprázdná a nemá v \(\mathbb{R}\) nejmenší prvek. Pokud bychom připustili
existenci nejmenšího prvku, řekněme \(x_0 \in M\), pak lze snadno vidět, že
\(0 < x = \frac{x_0}{2} \in M\) a zároveň \(x < x_0\), což je spor.
Cvičení.
S využitím principu dobrého uspořádání dokažte, že je-li \(S \subset
\mathbb{N}\) a \(S\) splňuje podmínky:
- \(1 \in S\),
- pro každé \(k \in \mathbb{N}\) pokud \(k \in S\), pak \(k+1 \in S\),
pak \(S = \mathbb{N}\).
Předpokládejme, že budeme chtít dokázat tvrzení: "\(\forall n \in \mathbb{N}:
n
\geq n_0 \implies P(n)\)". To znamená, že pro jisté \(n_0 \in \mathbb{N}\)
platí
\(P(n)\) pro všechna \(n \geq n_0\). V tomto případě se postupuje obdobně jako
v předchozím příkladu.
Cvičení.
Předpokládejme, že \(n_0\in \mathbb{N}\) a \(P(n)\) je tvrzení o přirozeném
čísle \(n\). Dále předpokládejme, že platí:
- \(P(n_0)\) je pravdivé,
- pro každé \(k \in \mathbb{N}\) pro které je \(k \geq n_0\) \(P(k)\)
implikuje \(P(k+1)\).
Dokažte, že \(P(n)\) platí pro všechna \(n \geq n_0\).
Cvičení.
Dokažte, že pro každé přirozené číslo \(n\) platí
\[
1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}.
\]
Archimédova vlastnost
Věta (Archimedova vlastnost).
Pro všechna \(y \in \mathbb{R}\) a pro každé \(x\in\mathbb{R}, x > 0\)
existuje \(n \in \mathbb{N}\) takové, že \(nx > y\).
Cvičení.
S využitím Archimédovy vlastnosti dokažte, že množina přirozených čísel
neobsahuje největší prvek.
Věta.
Nechť \(x \in \mathbb{R}\), \(x > 0\). Pak pro každé \(y \in \mathbb{R}\)
existuje jediné celé číslo \(m\in \mathbb{Z}\) takové, že
\[
(m-1)x \leq y < mx.
\]
Důkaz.
(i) (Důkaz existence čísla \(m\)). Nechť \(x \in \mathbb{R}\), \(x > 0\) a \(y
\in \mathbb{R}\). Cílem je nyní dokázat existenci čísla \(m\in \mathbb{Z}\)
tak, aby platilo
\[
(m-1)x \leq y < mx.
\]
Nyní definujme množinu
\[
S = \{m \in \mathbb{Z}: mx > y\}.
\]
Množina \(S\) je neprázdná díky Archimédově vlastnosti. Poznamenejme, že
množina \(S\) podmnožina množiny celých čísel \(\mathbb{Z}\), která není
dobře uspořádaná. Tedy pro důkaz existence nejmenšího prvku v \(S\) nelze
"napřímo" použít princip dobrého uspořádání. Abychom tuto překážku obešli,
uvažujme celé číslo \(k\) pro které platí \(k \leq \frac{y}{x}\), tj. \(kx
\leq y\). Nyní pro každé \(m \in S\) je \(n = m - k > 0\) a tedy \(n \in
\mathbb{N}\). Položíme-li nyní
\[
T = \{n \in \mathbb{N}: (n+k)x > y\},
\]
je zřejmé, že \(T\) je neprázdná podmnožina množiny přirozených čísel a pro
každé \(m \in \mathbb{Z}\) \(m\in S\) právě tehdy, když \(n = m - k \in T\).
Označme pak nejmenší prvek množiny \(T\) jako \(n_0\). Potom je zřejmě
číslo \(m_0 = n_0 + k\) nejmenší prvek množiny \(S\). Nyní ukažme, že pro
\(m = m_0\) platí
\[
(m-1)x \leq y < mx.
\]
Protože je celé číslo \(m_0\) nejmenší prvek množiny \(S\), pak \(m - 1
\notin S\). To znamená, že platí
\[
(m-1)x \leq y.
\]
Nerovnost \(y < mx\) je zřejmá, neboť \(m = m_0\in S\). Tím je důkaz existence
hotov.
(ii) (Jednoznačnost čísla \(m\)). Předpokládejme, že existuje jiné celé číslo
\(m'\) takové, že
\[
(m'-1)x \leq y < m'x.
\]
Ukažme, že pak \(m' = m\). Pokud by platilo \(m' < m\), potom
potom by platilo, že \(m' \in S\), což je spor s tím, že \(m\) je nejmenší
prvek množiny \(S\). Pokud by platilo, že \(m' > m\),
potom by platilo
\[
y < mx \leq (m'-1)x \leq y,
\]
což implikuje, že \(y < y\), což je také spor. Tedy \(m' = m\).
\(~~~\square\)
Věta.
Pro každé dvě reálná čísla \(a, b \in \mathbb{R}\), \(a < b\), existuje
racionální číslo \(r \in \mathbb{Q}\) takové, že \(a < r < b\).
Důkaz.
Z předpokladů věty plyne, že \(b - a > 0\). Z Archimédovy vlastnosti
plyne existence \(n_0 \in \mathbb{N}\) pro nějž platí
\[
1 < n_0(b - a).
\]
Tj. \(0 < 1/n_0 < b - a\). Dále existuje jediné celé číslo \(m_0 \in
\mathbb{Z}\) takové, že
\[
(m_0 - 1)\frac{1}{n_0} \leq a < m_0\frac{1}{n_0}.
\]
Nyní položme \(r = m_0/n_0\). Potom zřejmě \(a < r.\) Dále
\[
a \ge (m_0 - 1)\frac{1}{n_0} = r - \frac{1}{n_0} > r - (b - a) = r - b + a,
\]
což implikuje, že \(r < b\). Tedy \(a < r < b\).
\(~~~\square\)
Suprémum a infimum
V následujícím textu se budeme zabývat suprémem a infimem množiny reálných
čísel. Nejprve zavedeme pojem horní a dolní hranice(meze) podmnoužiny
množiny reálných čísel.
Definice.
Uvažujme neprázdnou podmnožinu \(A \subset \mathbb{R}\). Řekneme, že množina
\(A\)
je shora omezenou množinou, pokud existuje \(h \in \mathbb{R}\) takové,
že
pro každé \(a \in A\) platí \(a \leq h\). Číslo \(h\) nazveme horní
mezí
množiny \(A\).
Podobně řekneme, že množina \(A\) je zdola omezenou množinou, pokud
existuje
\(d \in \mathbb{R}\) takové, že pro každé \(a \in A\) platí \(a \geq d\).
Číslo \(d\)
nazveme dolní mezí množiny \(A\).
Definice.
Uvažujme neprázdnou podmnožinu \(A \subset \mathbb{R}\). Číslo \(s \in
\mathbb{R}\)
nazveme
suprémem množiny \(A\), pokud
- je horní mezí množiny \(A\),
- pro každé \(\varepsilon > 0\) existuje \(a \in A\) takové, že
\(s - \varepsilon < a\).
Číslo \(i \in \mathbb{R}\) nazveme
infimem množiny \(A\), pokud
- je dolní mezí množiny \(A\),
- pro každé \(\varepsilon > 0\) existuje \(a \in A\) takové, že
\(s + \varepsilon > a\).
Věta (Axiom o existenci supréma).
Každá neprázdná shora omezená množina reálných čísel má suprémum.