Przeskocz do treści

Delta mi!

Loading

Indukcja pozaskończona

Piotr Zakrzewski

o artykule ...

  • Publikacja w Delcie: kwiecień 2017
  • Publikacja elektroniczna: 30 marca 2017
  • Autor: Piotr Zakrzewski
    Afiliacja: Instytut Matematyki, Uniwersytet Warszawski

Indukcja pozaskończona wykorzystywana jest w dowodach istnienia różnych obiektów matematycznych. Główną częścią tego typu dowodu jest definicja indukcyjna (inaczej: rekurencyjna) funkcji.

Definicje funkcji przez indukcję pozaskończoną są uogólnieniem rekurencyjnych definicji ciągów. Rekurencyjna definicja ciągu |(an) składa się z określenia wyrazu a0 (lub kilku początkowych wyrazów) tego ciągu, a następnie pokazania, w jaki sposób każdy kolejny wyraz |a (n > 0) n zależy od wyrazów wcześniejszych ai,i < n. Taką strukturę ma następująca definicja indukcyjna ciągu Fibonacciego: a0 = a1 = 1,an = an−1 + an−2 dla n > 1. Jest intuicyjnie oczywiste, że powyższa definicja w jednoznaczny sposób definiuje ciąg: 1,1,2,3,5,8,13,21,...

W następnym przykładzie definicja indukcyjna pewnego ciągu posłuży nam do dowodu istnienia funkcji  f ze zbioru liczb wymiernych w liczby wymierne (oznaczane przez |Q ), która liczby wymierne każdego przedziału |(s,t), gdzie |s,t ∈Q i s < t, przekształca na cały zbiór Q. Zatem funkcja | f ma mieć tę własność, że dla każdej trójki liczb wymiernych |(s,t,q), gdzie |s < t (oznaczmy zbiór wszystkich takich trójek przez T), istnieje taka liczba p ∈(s,t)∩ Q, że | f(p) = q.

Skorzystamy z tego, że T jest zbiorem przeliczalnym, czyli takim, którego elementy można ponumerować liczbami naturalnymi. Innymi słowy, istnieje ciąg trójek (sn,tn,qn), gdzie n ∈N, którego zbiorem wyrazów jest T . Za jego pomocą indukcyjnie zdefiniujemy ciąg |(pn) taki, że p ∈ (s,t ) ∩Q n n n oraz p ≠ p n m dla wszystkich n, | m o ile |n≠ m. Mianowicie, określamy najpierw p0 | jako dowolną liczbę wymierną z przedziału (s0,| t0) (np.  t+s p0 = 020- ). Następnie, jeśli n > 0 i dane są już wyrazy |pi dla i < n, to definiujemy |pn jako jedną z tych liczb wymiernych przedziału |(s,t ), n n które są różne od każdego p i dla |i < n. Wybór |pn jest możliwy, ponieważ w każdym niepustym przedziale otwartym jest nieskończenie wiele liczb wymiernych.

Mając dany ciąg |(pn), określamy funkcję | f na wszystkich jego wyrazach jako  f(pn) = qn dla |n ∈N. To gwarantuje, że funkcja  f ma żądaną własność: każda trójka (s,t,q) ∈T jest postaci |(sn,tn,qn) dla pewnego |n∈ N i wówczas p = p n jest tą liczbą wymierną z przedziału (s,t), dla której  f (p) = q (na pozostałych liczbach wymiernych, jeśli takie istnieją, można określić wartości funkcji  f jakkolwiek).

Zmodyfikujemy teraz powyższe rozumowanie tak, by uzyskać funkcję g ze zbioru liczb rzeczywistych w liczby rzeczywiste (oznaczane przez |R ), która każdy przedział (a, b), gdzie a,b ∈ R i a < b, przekształca na cały zbiór |R. Znanych jest wiele dowodów istnienia takiej funkcji. Przedstawimy tu argument oparty na indukcji pozaskończonej.

Niech |W będzie zbiorem wszystkich takich trójek liczb rzeczywistych |(a,b,y), że a < b. Jest on nieprzeliczalny, nie możemy więc jego elementów ponumerować liczbami naturalnymi. Skorzystamy jednak z tego, że istnieje (czego nie będziemy tu dowodzić) wygodny z punktu widzenia naszej sytuacji odpowiednik zbioru liczb naturalnych, mianowicie zbiór, który oznaczymy przez |𝔠, wraz z relacją ⪯, ustalającą pewien liniowy porządek jego elementów, o następujących własnościach:

1.
Wszystkie elementy zbioru W można poindeksować za pomocą elementów zbioru |𝔠, czyli ustawić w ciąg pozaskończony trójek |(a ,b ,y ), α α α gdzie |α ∈𝔠.
2.
Jeśli |α jest dowolnym elementem zbioru 𝔠 oraz |{xβ β≺ α} jest dowolnym zbiorem złożonym z liczb rzeczywistych, poindeksowanych elementami zbioru 𝔠, mniejszymi w sensie porządku ⪯ od α, to w każdym przedziale (a,b), gdzie |a < b, znajdzie się liczba różna od wszystkich liczb xβ dla |β ≺α .
3.
W każdym niepustym podzbiorze zbioru |𝔠 istnieje element najmniejszy w sensie porządku ⪯ .

Z pomocą ciągu pozaskończonego (aα,bα,yα) (zob. warunek 1) przez indukcję pozaskończoną zdefiniujemy taki ciąg pozaskończony (xα), że |x ∈ (a ,b ) α α α oraz x ≠x β α dla wszystkich |α,β ∈𝔠, o ile β ≠ α. Postępujemy zgodnie ze schematem wcześniejszej konstrukcji ciągu |(pn). Mianowicie, jeśli 0 oznacza najmniejszy w sensie porządku ⪯ element zbioru |𝔠 (taki element istnieje na mocy warunku 3), to określamy najpierw |x = b0+a0. 0 2 Następnie, jeśli 0 ≺ α i dane są już wyrazy x β dla |β ≺α , to definiujemy xα jako jedną z tych liczb z przedziału (aα,bα), które są różne od każdego |xβ dla β ≺ α. Wybór xα jest możliwy na mocy warunku 2.

Wymaga jeszcze uzasadnienia, dlaczego opisana powyżej definicja indukcyjna prowadzi do jednoznacznego przypisania wartości xα wszystkim α ∈𝔠. Nieco upraszczając, gdyby zbiór tych |α ∈𝔠, którym powyższa definicja indukcyjna nie przypisała wartości, był niepusty, to na mocy warunku 3. istniałby w nim najmniejszy element, powiedzmy α 0. Wówczas 0 ≺α 0, gdyż wyraz |x0 został zdefiniowany. Ponadto, na mocy definicji |α0 zdefiniowane byłyby wszystkie wyrazy x β dla |β ≺α . 0 To jednak - jak widzieliśmy powyżej - umożliwiałoby zdefiniowanie wyrazu xα0, co prowadziłoby do sprzeczności z definicją elementu α0.

Na koniec, mając dany ciąg pozaskończony (xα), określamy funkcję g na wszystkich jego wyrazach jako g(xα) = yα dla każdego |α ∈𝔠 (por. warunek 1). Podobnie jak w przypadku funkcji  f to już wystarczy, by funkcja g miała żądaną własność, co kończy dowód.