Indukcja pozaskończona

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.