Transfiniittinen induktio

Transfiniittinen induktio on todistusmenetelmä, joka yleistää matemaattisen induktion tapaukseen , jossa on lukematon määrä parametriarvoja.

Kuvaus

Transfiniittinen induktio perustuu seuraavaan lauseeseen:

Olkoon hyvin perusteltu joukko (eli osittain järjestetty joukko , jossa jokaisessa ei-tyhjässä osajoukossa on minimialkio), ja olkoon jokin lause. Jos mikä tahansa on totta kaikille , siitä seuraa, että se on totta . Sitten väite on totta kaikille . $M$ $P(x)$ $x\in M$ $x\in M$ $P(y)$ $y<x$ $P(x)$ $P(x)$ $x$

Suhde matemaattiseen induktioon

Matemaattinen induktio on transfiniittisen induktion erikoistapaus. Todellakin, olkoon luonnollisten lukujen joukko ( erityistapaus hyvin järjestetystä joukosta). Sitten transfiniittisen induktion väite muuttuu seuraavaksi: jos jollekin luonnolliselle lauseiden , , samanaikainen totuus merkitsee lauseen totuutta , niin kaikki väitteet ovat tosia . Tässä tapauksessa induktiokanta, eli , osoittautuu triviaaliksi erikoistapaukseksi . $M$ $n$ $P(1)$ $P(2)$ $\ldots$ $P(n-1)$ $P(n)$ $P(n)$ $P(1)$ $n = 1$

Käyttöesimerkkejä

Monissa tapauksissa transfiniittistä induktiota käytetään yhdessä Zermelon lauseen kanssa , jonka mukaan mikä tahansa joukko voidaan järjestää hyvin. Zermelon lause vastaa valinnan aksioomaa , joten todistus on ei-konstruktiivinen .

Osoitetaan esimerkkinä, että on mahdollista piirtää tietty joukko ympyröitä siten, että tasan jokaisen pisteen läpi kulkee tasan 2 ympyrää. (Tässä tapauksessa voidaan myös antaa eksplisiittinen konstruktio, mutta kolmen ympyrän tapauksessa alla oleva todistus muuttuu vain hieman, eikä eksplisiittinen konstruktio ole vielä tiedossa).

Järjestämme tason pisteet täysin siten, että pienempien pisteiden joukon kardinaliteetti on pienempi kuin jatkumo (voidaan osoittaa, että mikä tahansa joukko voidaan järjestää kokonaan siten, että sen minkä tahansa alkion osalta pienempien joukossa on vähemmän kardinaalisuus). Otetaan esimerkkinä seuraava väite : on mahdollista piirtää vähemmän kuin jatkuva joukko erilaisia ympyröitä siten, että jokainen pienempi tai yhtä suuri piste peittyy tasan 2 ympyrällä ja loput pisteet enintään kahdella ympyrällä , ja mille tahansa pisteelle tämä joukko voidaan valita siten, että se sisältää pisteen ympyräjoukon . Jos on minimipiste, otamme mitkä tahansa 2 erilaista ympyrää, jotka kulkevat tämän pisteen läpi. Väite minimiin on todistettu. Olkoon nyt mikä tahansa kohta ja tiedetään, että väite on totta mille tahansa . Otetaan kaikkien pisteiden ympyräjoukkojen liitto . Induktiohypoteesilla voidaan olettaa, että suurten pisteiden ympyräjoukot sisältävät pienempien pisteiden ympyräjoukot, joten tuloksena oleva joukko kattaa tason pisteet enintään kahdesti. Koska alkioiden joukko pienempi kuin , on pienempi kuin jatkumo ja jokainen yhdistetty joukko on pienempi kuin jatkumo, niin tuloksena olevan joukon kardinaliteetti on myös jatkumoa pienempi. Muodostettu ympyräjoukko kattaa jo kaikki pisteet alle 2 kertaa . $x$ $P(x)$ $x$ $y<x$ $y$ $x$ $P(x)$ $x$ $x$ $y<x$ $y<x$ $x$ $x$

Näytämme nyt kuinka peittää . Ei -leikkautuvien ympyröiden jatkumo kulkee läpi. Huomaa, että mikä tahansa ympyräpari leikkaa enintään kahdessa pisteessä, mikä tarkoittaa, että 2 kertaa katetun tason pistejoukon kardinaliteetti on pienempi kuin jatkumo (tässä käytetään lausetta, joka vastaa jos on ääretön joukko ). Tämä tarkoittaa, että on jatkumo ympyröitä, joilla ei ole kahdesti katettuja pisteitä. Otetaan niistä yksi tai kaksi, riippuen pisteen läpi jo kulkevien ympyröiden määrästä . Induktioväite on todistettu. $x$ $x$ $A\ kertaa A$ $A$ $A$ $x$

Katso myös

Kirjallisuus

Kuratovsky K., Mostovsky A. Joukkoteoria . - M . : Mir, 1970. - 416 s.