Podstawy matematyki dla informatyków
Cz¦±¢ IV. Indukcja
Zima 2013-14
www.mimuw.edu.pl/~urzy/Pmat/04indukcja.pdf
Giuseppe Peano, 1889-91:
1. Zero
jest liczb¡ naturaln¡.
2.
Ka»da liczba naturalna ma
nast¦pnik
, który jest liczb¡
naturaln¡.
3.
Liczby o tych samych nast¦pnikach s¡ równe.
4.
Zero nie jest nast¦pnikiem »adnej liczby naturalnej.
5.
Je±li zero ma pewn¡ wªasno±¢ W , oraz
I
z tego »e jaka± liczba naturalna ma wªasno±¢ W
wynika, »e jej nast¦pnik te» ma wªasno±¢ W ,
to ka»da liczba naturalna ma wªasno±¢ W .
◦
Typ N liczb naturalnych
I
Zakªadamy, »e 0 : N oraz, »e je±li n : N to tak»e s(n) : N.
Przy tym s(n) nie jest zerem.
I
Funkcja s : N → N jest ró»nowarto±ciowa.
I
Je±li W (0) oraz ∀n:N(W (n) → W (s(n))) to ∀n:N. W (n).
◦
Wnioskowanie przez indukcj¦:
Cel: ∀n:N W (n)
...
Zatem W (0).
(Krok bazowy wykonany)
Niech n ∈ N
(
Cel 1: W (n) → W (s(n)))
Zaªó»my, »e W (n).
(
Cel 2: W (s(n))
...
Zatem W (s(n)).
(Cel 2 osi¡gni¦ty)
Zatem W (n) → W (s(n)).
(Cel 1 osi¡gni¦ty)
Zatem ∀n:N (W (n) → W (s(n)).
(Krok indukcyjny wykonany)
Zatem ∀n:N W (n)
◦
Przykªad
Niech s oznacza relacj¦ nast¦pnika (n s m ⇔ m = s(n)).
Symbol s
+
oznacza domkni¦cie przechodnie relacji s.
Symbol s
∗
oznacza domkni¦cie przechodnio-zwrotne relacji s.
Fakt
Dla ka»dej liczby naturalnej zachodzi ¬(n s
+
n).
W szczególno±ci zawsze mamy s(n) 6= n.
Dowód
:
Gdyby
0 s
+
0
to
0 s
∗
y s 0
, czyli
0 = s(y)
dla
pewnego
y
, sprzeczno±¢.
Zaªó»my wi¦c, »e
¬(
n s
+
n)
i przypu±¢my, »e
s(n) s
+
s(n)
.
Wtedy
s(n) s
∗
y s s(n)
dla pewnego
y
, sk¡d
s(y) = s(n)
,
wi¦c
y = n
. A zatem
n s s(n) s
∗
y = n
, czyli
h
n, ni ∈ s · s
∗
=
s
+
, sprzeczno±¢.
◦
Zaªó»my, »e 0 s
+
0.
(Cel 1: sprzeczno±¢)
...
Sprzeczno±¢.
(Cel 1 osi¡gni¦ty)
Zatem ¬ 0 s
+
0.
(Krok bazowy wykonany)
Niech n ∈ N
(
Cel 2: ¬(n s
+
n) → ¬(s(n) s
+
s(n))
Zaªó»my, »e ¬(n s
+
n).
(
Cel 3: ¬(s(n) s
+
s(n))
...
Zatem ¬ s(n) s
+
s(n).
(Cel 3 osi¡gni¦ty)
Zatem ¬ (n s
+
n) → ¬ (s(n) s
+
s(n))
(Cel 2 osi¡gni¦ty)
Zatem ∀n:N (¬(n s
+
n) → ¬(s(n) s
+
s(n)))
(Krok ind. wykonany)
Zatem ∀n:N ¬(n s
+
n)
◦
Relacja ≤
De nicja
I
m ≤ n
wtedy i tylko wtedy, gdy m s
∗
n.
I
m < n
wtedy i tylko wtedy, gdy m ≤ n, ale m 6= n.
Fakt
Relacje s
+
i < pokrywaj¡ si¦.
Dowód
:
(1) Niech m s
+
n. Wtedy m s
∗
n, wi¦c m ≤ n.
Ale m 6= n, bo n s
+
n jest niemo»liwe.
(2) Je±li m < n, to m s
∗
n. Wiemy, »e s
∗
=
s
+
∪
1
N
.
Poniewa» m 6= n, wi¦c hm, ni 6∈ 1
N
. Zatem m s
+
n.
◦
Relacja <
De nicja
I
m ≤ n
wtedy i tylko wtedy, gdy m s
∗
n.
I
m < n
wtedy i tylko wtedy, gdy m ≤ n, ale m 6= n.
Fakt
m < n wtedy i tylko wtedy, gdy s(m) ≤ n.
Dowód
:
(1) Niech m < n, czyli m s
+
n.
Wiemy, »e s
+
=
s · s
∗
. Zatem m sy s
∗
n. Ale wtedy y = s(m).
(2) Niech s(m) ≤ n. Wtedy m ss(m) s
∗
n, wi¦c m s
+
n.
◦
Fakt
Relacja ≤ jest relacj¡ liniowego porz¡dku w N,
tj. jest zwrotna, przechodnia, antysymetryczna i spójna.
Zero jest elementem najmniejszym, tj. ∀m. 0 ≤ m.
Dowód
:
Zwrotno±¢ i przechodnio±¢ wprost z de nicji.
Antysymetria: Przypu±¢my, »e n ≤ m ≤ n, gdzie m 6= n.
Wtedy n < m < n, sk¡d n < n (tj. n s
+
n), co jest niemo»liwe.
Zero jest najmniejsze: Dowodzimy, »e ∀m. 0 ≤ m:
1.
Oczywi±cie 0 ≤ 0.
2.
Je±li 0 ≤ m, to z m ≤ s(m) wynika 0 ≤ s(m).
◦
Relacja ≤ jest liniowym porz¡dkiem
Spójno±¢: Dowodzimy, »e ∀nm ∈ N(m ≤ n ∨ n ≤ m) przez
indukcj¦ ze wzgl¦du na n, tj. dowodzimy, »e
ka»de n ∈ N ma wªasno±¢
∀
m ∈ N(m ≤ n ∨ n ≤ m).
1.
Dla n = 0 mamy zawsze n ≤ m.
2.
Zaªó»my, »e ∀m ∈ N(m ≤ n ∨ n ≤ m).
Dowodzimy, »e ∀m ∈ N(m ≤ s(n) ∨ s(n) ≤ m):
Niech m ∈ N. Je±li m ≤ n, to tym bardziej m ≤ s(n).
W przeciwnym razie n ≤ m, tak naprawd¦ n < m.
Poniewa» s
+
=
s · s
∗
, wi¦c n s s(n) ≤ m.
◦
Zasada minimum
Ka»dy niepusty podzbiór A ⊆ N ma element najmniejszy,
tj. taki element a ∈ A, »e ∀b (b ∈ A → a ≤ b).
Dowód
:
Przypu±¢my przeciwnie. Przez indukcj¦ ze wzgl¦du
na n dowodzimy, »e
∀
n∀k(k ∈ A → n < k).
St¡d A = ∅.
Najpierw zauwa»my, »e 0 6∈ A. W przeciwnym razie 0 byªoby
najmniejszym elementem. A wi¦c
∀
k(k ∈ A → 0 < k)
.
Je±li
∀
k(k ∈ A → n < k)
to ∀k(k ∈ A → s(n) ≤ k),
bo n < k to to samo co s(n) ≤ k.
Gdyby wi¦c s(n) ∈ A to s(n) byªoby najmniejsze w A.
No to s(n) 6∈ A i mamy
∀
k(k ∈ A → s(n) < k)
.
◦
Zasada minimum
Ka»dy niepusty podzbiór A ⊆ N ma element najmniejszy,
tj. taki element a ∈ A, »e ∀b (b ∈ A → a ≤ b).
Oznaczenie:
a = min A
◦
Troch¦ inna zasada indukcji
Wniosek
Je±li ∀n:N(∀m:N(m < n → W (m)) → W (n)),
to ∀n:N. W (n).
Dowód
:
Niech A = {n : N | ¬W (n)}. Je±li teza nie
zachodzi, to zbiór A jest niepusty, ma wi¦c element
najmniejszy n. Wtedy ∀m:N(m < n → W (m)) ale nie jest
speªniony warunek W (n), co jest sprzeczne z zaªo»eniem.
Moraª:
Aby udowodni¢, »e ka»da liczba naturalna ma
wªasno±¢ W , wystarczy dla ka»dego n pokaza¢, »e:
je±li wszystkie liczby mniejsze od n maj¡ wªasno±¢ W ,
to tak»e n ma wªasno±¢ W
◦
Przykªad
Graf spójny, w którym nie ma cykli nazywamy
drzewem
.
Fakt:
Drzewo o n ≥ 1 wierzchoªkach ma n − 1 kraw¦dzi.
Dowód:
Indukcja ze wzgl¦du na liczb¦ wierzchoªków.
Je±li drzewo nie ma kraw¦dzi, to ma tylko 1 wierzchoªek.
Warunek jest wtedy speªniony.
Mo»na zaªo»y¢, »e drzewo ma jakie± kraw¦dzie.
Usuwaj¡c jedn¡ z nich dostajemy dwa drzewa.
Jedno ma n
1
wierzchoªków, drugie n
2
wierzchoªków.
Razem jest n
1
+
n
2
=
n wierzchoªków.
Z zaªo»enia indukcyjnego, pierwsze drzewo ma n
1
−
1
kraw¦dzi, a drugie n
2
−
1. Razem z t¡ usuniet¡ mamy
dokªadnie n
1
−
1 + n
2
−
1 + 1 = n − 1 kraw¦dzi.
◦
Zªy przykªad
Niefakt:
W dowolnym sko«czonym zbiorze koni
wszystkie konie s¡ tego samego koloru.
Niedowód:
Je±li w zbiorze jest tylko jeden ko«, to warunek
jest speªniony. Je±li jest wi¦cej koni, to wybierzmy jednego
konia k a reszt¦ podzielmy na dwie mniejsze cz¦±ci A i B.
Zbiory A ∪ {k} i B ∪ {k} s¡ mniejsze, wi¦c konie w zbiorze
A ∪ {k} s¡ tego samego koloru i w zbiorze B ∪ {k} te».
No to wszystkie konie s¡ tego samego koloru.
Gdzie jest bª¡d?
To nie dziaªa dla 2 koni.
◦
De niowanie przez indukcj¦
Dodawanie:
0 + n = n;
s(m) + n = s(m + n).
Mno»enie
0 · n = 0;
s(m) · n = m · n + n
Schemat rekursji prostej:
f (0, n
1
, . . . ,
n
k
) =
g(n
1
, . . . ,
n
k
);
f (s(m), n
1
, . . . ,
n
k
) =
h(m, n
1
, . . . ,
n
k
,
f (m, n
1
, . . . ,
n
k
)).
◦
Dwa razy dwa
2 · 2 = 1 · 2 + 2 = (0 · 2 + 2) + 2 =
(
0 + 2) + 2 = 2 + 2 = s(1 + 2) =
s(s(0 + 2)) = s(s(2)) = s(s(s(s(0)))) = 4.
◦
Dowodzenie przez indukcj¦
Fakt
Dodawanie jest ª¡czne: dla dowolnych liczb m, k, l ∈ N
zachodzi równo±¢ m + (k + l) = (m + k) + l.
Dowód
:
Indukcja ze wzgl¦du na m.
Udowodnimy, ze ka»da liczba m : N ma wªasno±¢
∀
k, l : N. m + (k + l) = (m + k) + l
.
Po pierwsze, 0 + (k + l) = (k + l) = (0 + k) + l.
Po drugie z warunku m + (k + l) = (m + k) + l wynika
s(m) + (k + l) = s(m + (k + l)) = s((m + k) + l) =
s(m + k) + l = (s(m) + k) + l, i dobrze.
◦
Dowodzenie przez indukcj¦
W podobny sposób dowodzimy wielu innych wªasno±ci liczb
naturalnych. Na przykªad
I
»e dodawanie jest przemienne;
I
»e mno»enie jest ª¡czne i przemienne, itp.
Z przemienno±ci dodawania wynika m.in., »e
s(n) = s(0 + n) = s(0) + n = n + s(0).
A wi¦c s(n) = n + 1.
◦
Jeszcze jedno zadanie
Fakt:
Dla dowolnych m, n:
m ≤ n
wtedy i tylko wtedy, gdy ∃k(k + m = n).
Dowód:
Niech
r = {hm, ni | ∃k(k + m = n)}
.
Mamy udowodni¢, »e
s
∗
=
r
.
Inkluzja ⊆ wynika st¡d, »e s ⊆ r i r jest przechodnia.
Istotnie, je±li
k + m = n
oraz
l + n = p
, to
(
l + k) + m = p
.
W przeciwn¡ stron¦, przez indukcj¦ ze wzgl¦du na k
dowodzimy, »e
m s
∗
(
k + m)
.
Oczywi±cie m s
∗
(
0 + m), bo 0 + m = m.
Przypu±¢my, »e m s
∗
(
k + m).
Poniewa» (k + m) s s(k + m) = s(k) + m, wi¦c m s
∗
(
s(k)+m).
◦
De niowanie przez indukcj¦
Schemat rekursji prostej:
f (0, n
1
, . . . ,
n
k
) =
g(n
1
, . . . ,
n
k
);
f (m + 1, n
1
, . . . ,
n
k
) =
h(m, n
1
, . . . ,
n
k
,
f (m, n
1
, . . . ,
n
k
)).
Funkcja Ackermanna
(To nie jest rekursja prosta)
A(0, x) = s(x);
A(n + 1, 0) = A(n, 1);
A(n + 1, x + 1) = A(n, A(n + 1, x)).
wiczenie:
Policzy¢ A(m, n) dla kilku maªych liczb m, n.
◦
Ogólny schemat de niowania przez indukcj¦
De niujemy funkcj¦ f : N × D → E
f (0, d) = g(d);
(1)
f (m + 1, d) = h(m, d, f (m, d)).
(2)
◦
Przykªad: domkni¦cie przechodnie
Dla ustalonej relacji r w zbiorze A, de niujemy ci¡g relacji r
n
:
I
r
0
=
r;
I
r
n+1
=
r
n
∪ (
r
n
·
r
n
)
.
Wreszcie niech r
ω
=
S
n∈N
r
n
.
atwy lemat:
Je±li m ≤ n, to r
m
⊆
r
n
.
Fakt:
r
ω
=
r
+
Dowód:
Zacznijmy od tego, »e relacja r
ω
jest przechodnia.
Bo tak: je±li hx, yi, hy, zi ∈ r
ω
, to istniej¡ takie m, n, »e
h
x, yi ∈ r
m
i hy, zi ∈ r
n
. Wtedy obie pary nale»¡ do r
max{m,n}
,
sk¡d hx, zi ∈ r
max{m,n}+1
⊆
r
ω
.
Poniewa» r = r
0
⊆
r
ω
i r
ω
jest przechodnia, wi¦c r
+
⊆
r
ω
.
◦
Przykªad: domkni¦cie przechodnie
Dla ustalonej relacji r w zbiorze A, de niujemy ci¡g relacji r
n
:
I
r
0
=
r;
I
r
n+1
=
r
n
∪ (
r
n
·
r
n
)
.
Wreszcie niech r
ω
=
S
n∈N
r
n
.
Fakt:
r
ω
=
r
+
Dowód:
Teraz trzeba pokaza¢, »e r
ω
⊆
r
+
. W tym celu przez
indukcj¦ dowodzimy, »e r
n
⊆
r
+
dla wszystkich n ∈ N.
Po pierwsze, r ⊆ r
+
.
Po drugie, je±li r
n
⊆
r
+
, to
r
n+1
=
r
n
∪ (
r
n
·
r
n
) ⊆
r
+
∪ (
r
+
·
r
+
) ⊆
r
+
∪
r
+
=
r
+
.
◦
Liczby caªkowite
Chcemy odejmowa¢ liczby naturalne, tj. mie¢ dziaªanie
odwrotne do dodawania: chcemy, »eby (3 − 5) + 5 = 3.
Inaczej: chcemy rozwi¡za¢ równanie x + 5 = 3.
Pomysª: implementowa¢ 3 − 5 jako par¦ h3, 5i.
Ale wtedy (3 − 5) + 4 + 1 = 2 + 1, sk¡d (3 − 5) + 4 = 2.
Zatem 3 − 5 = 2 − 4. Tak jest dlatego, »e 3 + 4 = 2 + 5.
A wi¦c niektóre ró»nice musz¡ by¢ równe:
h
m, ni ∼ hm
0
,
n
0
i
⇔
m + n
0
=
m
0
+
n
To jest relacja równowa»no±ci w N × N. Liczby caªkowite to
jej abstrakty (pary liczb naturalnych z dokªadno±ci¡ do ∼).
Moraª:
Mo»na de niowa¢ Z jako N × N/
∼
.
◦
Liczby wymierne
Liczby wymierne to pary liczb caªkowitych z dokªadno±ci¡ do
(cz¦±ciowej) relacji równowa»no±ci
h
x, yi ≈ hu, vi ⇔ (y, v 6= 0 ∧ x · v = u · y)
Oczywi±cie zamiast [hx, yi]
≈
piszemy
x
y
.
◦
Liczby rzeczywiste
Ci¡g Cauchy'ego to taki ci¡g f liczb (wymiernych), »e
∀ε:Q (ε > 0 → ∃n:N ∀k:N(k ≥ n → (f (n)−ε < f (k) < f (n)+ε)))
Liczby rzeczywiste
to ci¡gi Cauchy'ego liczb wymiernych
z dokªadno±ci¡ do (cz¦±ciowej) relacji równowa»no±ci:
f ≡ g, wtedy i tylko wtedy, gdy
∀ε:Q (ε > 0 → ∃n ∀k (k ≥ n → (f (k) − ε < g(k) < f (k) + ε))).
◦
Typ indukcyjny: sªowa nad {a, b}
Na±laduj¡c Giuseppe Peana:
I
Sªowo puste jest sªowem.
I
Ka»de sªowo w mo»na przedªu»y¢, dopisuj¡c na ko«cu
liter¦ a lub b (oznaczenie wa, wb).
I
Je±li wa = va lub wb = vb to w = v;
I
Sªowa wa i vb s¡ ró»ne i niepuste;
I
Zasada indukcji?
◦
Zasada indukcji dla sªów
Je±li
I
sªowo puste ma wªasno±¢ X ,
I
z tego, »e sªowo w ma wªasno±¢ X wynika, »e
sªowa wa i wb te» maj¡ wªasno±¢ X ,
to
I
ka»de sªowo ma wªasno±¢ X .
X (ε) ∧ (∀w:{a, b}
∗
(
X (w) → X (wa) ∧ X (wb))) →
→ ∀
w:{a, b}
∗
.
X (w).
◦
De niowanie przez indukcj¦
Dªugo±¢ sªowa:
I
|ε| =
0;
I
|
wa| = |w| + 1;
I
|
wb| = |w| + 1.
Skªadanie (konkatenacja) sªów:
I
w · ε = w;
I
w · va = (w · v)a;
I
w · vb = (w · v)b.
Konkatenacja jest ª¡czna:
ein · (und · zwanzig) = (ein · und) · zwanzig = einundzwanzig
.
◦
Dowodzenie przez indukcj¦
Fakt
Dla dowolnych sªów w i v zachodzi |w · v| = |w| + |v|.
Dowód
:
Udowodnimy, »e ka»de sªowo v ma wªasno±¢
∀
w:{a, b}
∗
.|
w · v| = |w| + |v|.
Krok bazowy:
Poniewa» w · ε = w, wi¦c |w · ε| = |w|.
Krok indukcyjny:
Niech |w · v| = |w| + |v| dla wszystkich w.
|
w · va| = |(w · v)a| = |w · v| + 1 = |w| + |v| + 1 = |w| + |va|,
Drugi przypadek jest analogiczny.
wiczenie:
Udowodni¢, »e
∀
w (ε · w = w).
◦
Porz¡dek pre ksowy
De nicja:
w ⊆ v ⇔ ∃u (v = w · u).
wiczenie:
Niech s oznacza relacj¦ nast¦pnika dla sªów:
w s v wtedy i tylko wtedy, gdy v = wa lub v = wb.
Udowodni¢, »e ⊆ to to samo co s
∗
.
Fakt
Relacja ⊆ jest cz¦±ciowym porz¡dkiem.
Dowód
:
Zwrotno±¢ i przechodnio±¢ s¡ oczywiste.
Antysymetria: je±li w = vx i v = wy to w = wyx.
Ale |w| = |wyx| = |w| + |y| + |x|, wi¦c x = y = ε.
◦
Typy indukcyjne
Obiekty typu indukcyjnego tworzone s¡ przez
konstruktory
.
Ka»dy element mo»na otrzyma¢ tylko w jeden sposób, przez
odpowiednie zªo»enie konstruktorów.
Z typem indukcyjnym zwi¡zane s¡
I
swoista zasada indukcji;
I
swoisty schemat de niowania przez indukcj¦.
◦
Listy
Listy liczb naturalnych tworz¡ typ indukcyjny list generowany
przez dwa konstruktory:
nil : list
,
oraz
cons : N × list → list
.
Zamiast cons(n, `) cz¦sto piszemy n :: `.
Zasada indukcji:
W (nil) ∧ ∀`:list(W (`) → ∀n:N. W (n :: `)) → ∀`:list. W (`).
Schemat de niowania przez indukcj¦:
f (nil, d) = g(d);
f (n :: `, d) = h(`, n, d, f (`, d)).
◦
Inne typy indukcyjne
Drzewa binarne:
leaf : tree
node : tree × tree → tree
Omega-drzewa:
leaf : ω-tree
node : (N → ω-tree) → ω-tree.
◦