Transfinit induktion

Transfinit induktion  är en bevismetod som generaliserar matematisk induktion till fallet med ett oräkneligt antal parametervärden.

Beskrivning

Transfinit induktion är baserad på följande uttalande:

Låt vara  en välgrundad uppsättning (det vill säga en delvis ordnad uppsättning där varje icke-tom delmängd har ett minimalt element), och låt vara  ett påstående. Låt för allt som är sant för alla , det följer att det är sant . Då är påståendet sant för alla .

Samband med matematisk induktion

Matematisk induktion är ett specialfall av transfinit induktion. Låt oss faktiskt vara  uppsättningen av naturliga tal (ett specialfall av en välordnad uppsättning). Sedan förvandlas påståendet om transfinit induktion till följande: om för något naturligt påståendenas samtidiga sanning , , , antyder påståendets sanning så är alla påståenden sanna . I det här fallet visar sig induktionsbasen, d.v.s. , vara ett trivialt specialfall för .

Användningsexempel

I många fall används transfinit induktion tillsammans med Zermelos teorem , som säger att vilken mängd som helst kan vara välordnad. Zermelos teorem motsvarar valets axiom , så beviset är icke-konstruktivt .

Som ett exempel, låt oss bevisa att det är möjligt att rita en viss uppsättning cirklar så att exakt 2 cirklar passerar genom varje punkt i planet. (I detta fall kan en explicit konstruktion också ges, men för tre cirklar ändras beviset nedan endast något, och den explicita konstruktionen är ännu inte känd).

Vi ordnar punkterna i planet helt så att kardinaliteten för uppsättningen av punkter är mindre än är mindre än kontinuumet (det kan visas att vilken uppsättning som helst kan ordnas helt så att för något av dess element har uppsättningen av mindre mindre kardinalitet). Låt oss ta följande påstående som ett exempel: det är möjligt att rita mindre än en kontinuerlig uppsättning olika cirklar så att varje punkt mindre än eller lika med täcks av exakt 2 cirklar, och de återstående punkterna täcks av högst två cirklar , och för vilken punkt som helst kan denna uppsättning väljas så att den innehåller uppsättningen cirklar för punkten . Om  är minimipunkten, så tar vi 2 olika cirklar som passerar genom denna punkt. Påståendet om minimum är bevisat. Låt nu  vara någon punkt och det är känt att påståendet är sant för alla . Ta föreningen av uppsättningar cirklar för alla punkter . Genom induktionshypotesen kan vi anta att uppsättningarna av cirklar för stora punkter inkluderar uppsättningarna av cirklar för mindre punkter, så den resulterande uppsättningen kommer att täcka planets punkter högst två gånger. Eftersom uppsättningen av element mindre än , är mindre än kontinuumet, och varje förenad uppsättning är mindre än kontinuumet, kommer den resulterande uppsättningen också att ha en kardinalitet som är mindre än kontinuumet. Den konstruerade uppsättningen cirklar täcker redan alla punkter mindre än 2 gånger .

Vi kommer nu att visa hur man täcker . Ett kontinuum av icke-korsande cirklar passerar igenom. Observera att vilket par cirklar som helst skär varandra vid högst två punkter, vilket betyder att kardinaliteten för uppsättningen av punkter i planet som täcks 2 gånger är mindre än kontinuumet (här använder vi påståendet som är ekvivalent med if  är en oändlig mängd ). Det betyder att det finns ett kontinuum av cirklar där det inte finns några punkter täckta två gånger. Låt oss ta en eller två av dem, beroende på antalet cirklar som redan passerar genom punkten . Induktionspåståendet är bevisat.

Se även

Litteratur