Inducția transfinită

Inducția transfinită este o metodă de demonstrare care generalizează inducția matematică în cazul unui număr nenumărat de valori ale parametrilor.

Descriere

Inducția transfinită se bazează pe următoarea afirmație:

Fie o mulțime bine întemeiată (adică o mulțime parțial ordonată în care fiecare submulțime nevidă are un element minim) și fie o declarație. Să fie pentru orice din ceea ce este adevărat pentru toți , rezultă că este adevărat . Atunci afirmația este adevărată pentru orice . $M$ $P(x)$ $x\în M$ $x\în M$ $P(y)$ $y<x$ $P(x)$ $P(x)$ $X$

Relația cu inducția matematică

Inducția matematică este un caz special de inducție transfinită. Într-adevăr, să fie mulțimea numerelor naturale (un caz special al unei mulțimi bine ordonate). Apoi afirmația inducției transfinite se transformă în următoarea: dacă pentru orice natural adevărul simultan al enunțurilor , , , implică adevărul enunțului , atunci toate enunțurile sunt adevărate . În acest caz, baza de inducție, adică , se dovedește a fi un caz special banal pentru . $M$ $n$ $P(1)$ $P(2)$ $\ldots$ $P(n-1)$ $P(n)$ $P(n)$ $P(1)$ $n=1$

Exemple de utilizare

În multe cazuri, inducția transfinită este utilizată împreună cu teorema lui Zermelo , care afirmă că orice mulțime poate fi bine ordonată. Teorema lui Zermelo este echivalentă cu axioma de alegere , deci demonstrația este neconstructivă .

De exemplu, să demonstrăm că este posibil să se deseneze un anumit set de cercuri astfel încât exact 2 cercuri să treacă prin fiecare punct al planului. (În acest caz, poate fi dată și o construcție explicită, dar pentru cazul a trei cercuri, demonstrația de mai jos se modifică doar puțin, iar construcția explicită nu este încă cunoscută).

Ordonăm complet punctele planului astfel încât cardinalitatea mulțimii de puncte mai mică decât este mai mică decât continuumul (se poate demonstra că orice mulțime poate fi ordonată complet astfel încât pentru oricare dintre elementele sale mulțimea celor mai mici are mai puțin cardinalitate). Să luăm următoarea afirmație ca exemplu: este posibil să desenăm mai puțin decât o mulțime continuă de cercuri diferite, astfel încât fiecare punct mai mic sau egal cu este acoperit de exact 2 cercuri, iar punctele rămase sunt acoperite de cel mult două cercuri , iar pentru orice punct această mulțime poate fi aleasă astfel încât să conțină setul de cercuri pentru punctul . Dacă este punctul minim, atunci luăm oricare 2 cercuri diferite care trec prin acest punct. Afirmația pentru minim este dovedită. Fie acum orice punct și se știe că afirmația este adevărată pentru orice . Luați uniunea de seturi de cercuri pentru toate punctele . Prin ipoteza de inducție, putem presupune că seturile de cercuri pentru punctele mari includ seturile de cercuri pentru punctele mai mici, astfel încât mulțimea rezultată va acoperi punctele planului de cel mult două ori. Deoarece mulțimea elementelor mai mică decât , este mai mică decât continuumul și fiecare mulțime unită este mai mică decât continuumul, atunci mulțimea rezultată va avea și o cardinalitate mai mică decât continuumul. Setul construit de cercuri acoperă deja toate punctele de mai puțin de 2 ori . $X$ $P(x)$ $X$ $y<x$ $y$ $X$ $P(x)$ $X$ $X$ $y<x$ $y<x$ $X$ $X$

Vom arăta acum cum să acoperim . Un continuum de cercuri care nu se intersectează trece. Rețineți că orice pereche de cercuri se intersectează în cel mult două puncte, ceea ce înseamnă că cardinalitatea mulțimii de puncte ale planului acoperit de 2 ori este mai mică decât continuumul (aici folosim afirmația care este echivalentă cu if este o mulțime infinită ). Aceasta înseamnă că există un continuum de cercuri pe care nu există puncte acoperite de două ori. Să luăm unul sau două dintre ele, în funcție de numărul de cercuri care trec deja prin punctul . Afirmația de inducție este dovedită. $X$ $X$ $A\ori A$ $A$ $A$ $X$

Vezi și

Literatură

Kuratovsky K., Mostovsky A. Teoria mulțimilor. - M . : Mir, 1970. - 416 p.