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 ≤

Denicja

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 <

Denicja

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

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.

◦

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

◦

Deniowanie 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 deniowania przez indukcj¦

Deniujemy 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, deniujemy 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, deniujemy 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 deniowa¢ 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).

◦

Deniowanie 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 preksowy

Denicja:

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

◦