Transfinia indukto

En matematiko, transfinia indukto estas vastigaĵo de matematika indukto al bonordaj aroj, ekzemple al aro de ordaj numeroj aŭ kardinaloj.

Transfinia indukto

Estu P(α) esti propraĵo difinita por ĉiuj ordaj numeroj α. Supozu ke se P(β) estas vera por ĉiuj β<α, tiam P(α) estas ankaŭ vera. Tiam transfinia indukto statas ke P estas vera por ĉiuj ordaj numeroj.

Tio estas, se P(α) estas vera se P(β) estas vera por ĉiuj β<α, tiam P(α) estas vera por ĉiuj α. Aŭ, pli praktike: por ke pruvi propraĵon P por ĉiuj ordaj numeroj α, oni povas alpreni ke ĝi estas jam konata por ĉiuj pli malgrandaj β<α.

Kutime la pruvo estas disfendata en tri okazojn:

• Nula okazo: Pruvi ke P(0) estas vera.
• Postanta okazo: Pruvi ke por ĉiu postanta orda numero β+1, P(β+1) sekvas el P(β) (kaj, se necesas, P(α) por ĉiuj α < β).
• Limiga okazo: Pruvi ke por ĉiu limiga orda numero λ, P(λ) sekvas el P(α) por ĉiuj α<λ.

Rimarku ke la dua kaj tria okazo estas identaj krom la speco de orda numero konsiderata. Ili formale ne bezonatas al esti pruvataj aparte, sed en praktiko la pruvoj estas tipe malsamaj pro bezono apartigi prezentojn.

Transfinia rikuro

Transfinia rikuro estas maniero de konstruado aŭ difinado de io kaj estas proksime rilatanta al la koncepto de transfinia indukto. Kiel ekzemplo, vico de aroj A_α estas difinita por ĉiu orda numero α, per precizigo kiel al difini A_α surbaze de la vico de A_β por β<α.

Pli formale, oni povas statigi la transfinian rikuran teoremon kiel sekvas. Por donita klasa funkcio G: V → V, tie ekzistas unika transfinia vico F: Ord → V (kie Ord estas la klaso de ĉiuj ordaj numeroj) tia ke F(α) = G(F $\upharpoonright$ α) por ĉiuj ordaj numeroj α.

Kiel ĉe indukto, oni povas trakti malsamajn specojn de ordaj numeroj aparte: alia formulaĵo de transfinia rikuro estas ke por donita aro g₁, kaj klasaj funkcioj G₂, G₃, ekzistas unika funkcio F: Ord → V tia ke

• F(0) = g₁,
• F(α + 1) = G₂(F(α)), por ĉiuj α en Ord,
• F(λ) = G₃(F $\upharpoonright$ λ), por ĉiu limiga λ≠0.

Noto ke postulatas ke la domajnoj de G₂, G₃ estas larĝaj sufiĉe por fari la pli suprajn propraĵojn signifajn. La unikeco de la vico kontentiganta ĉi tiujn propraĵojn povas esti pruvita uzante transfinian indukton.

Pli ĝenerale, oni povas difini objektojn per transfinia rikuro sur ĉiu bone-fundamentita rilato R. R ne bezonas eĉ esti aro; ĝi povas esti propra klaso, se ĝi estas aro-simila duargumenta rilato; tio estas, por ĉiu x, la kolekto de ĉiuj y tiaj ke y R x devas esti aro.

Interrilato al la aksiomo de elekto

Pruvoj aŭ konstruoj uzantaj la indukton kaj rikuron ofte uzas la aksiomon de elekto por produkti bonordigitan rilaton kiu povas esti traktata per transfinia indukto. Tamen, se la rilato koncernata estas jam bonordigita, oni povas ofte uzi transfinian indukton sen alvoko de la aksiomo de elekto. Fakte, la domajno de la rilato ne bezonas eĉ esti aro; ĝi povas esti propra klaso, se ĝi estas aro-simila duargumenta rilato; tio estas, por ĉiu x, la kolekto de ĉiuj y tiaj ke y R x devas esti aro. Ekzemple, multaj rezultoj pri borelaj aroj estas pruvitaj per transfinia indukto sur la orda numera rango de la aro; ĉi tiuj rangoj estas jam bonordigitaj, do la aksiomo de elekto estas ne bezonata por bonordigi ilin.

Jena konstruado de la aro de Vitali montras ke la aksiomo de elekto povas esti uzata en pruvo per transfinia indukto:

Unue, bonordigu la reelaj nombroj, donante vicon $\langle r_{\alpha }|\alpha <c\rangle$, kie c estas la kardinalo de kontinuumo. Estu v₀ egala r₀. Tiam estu v₁ egala r_α1, kie α₁ estas plej malgranda tia ke r_α1 − v₀ estas ne racionala nombro. Daŭrigu; je ĉiu paŝo elektu la plej malgrandan reelon de la vico r kiu ne havas racionalan diferencon kun ĉiu ero de tiel jam konstruita la vico v. Daŭrigu ĝis kiam ĉiuj reelaj nombroj en la vico r estas trapasitaj. La fina vico v estos numerigo de la aro de Vitali.

La pli supra argumento uzas la aksiomon de elekto en esenca maniero je la komenco, por ke bonordigi la reelajn nombrojn. Post ĉi tio, la aksiomo de elekto ne estas uzata denove.

Aliaj uzoj de la aksiomo de elekto estas pli subtila. Ekzemple, konstruado per transfinia rikuro ofte ne precizigas unikan valoron por A_α+1 laŭ donita vico supren ĝis α, sed precizigas nur kondiĉon kiun A_α+1 devas kontentigi, kaj argumenton ke ekzistas almenaŭ unu aro kontentiganta ĉi tiun kondiĉon. Se ne eblas difini unikan ekzemplon de ĉi tia aro je ĉiu paŝo, tiam povas esti necese alvoki (iun formon de) la aksiomo de elekto por elekti unu ĉi tian aron je ĉiu paŝo. Por induktoj kaj rikuroj de kalkulebla longo, la pli malforta aksiomo de dependa elekto estas sufiĉa. Ĉar estas modeloj de aroteorio de Zermelo-Franekel, interesaj por aroteoriistoj, kiuj kontentigas la aksiomon de dependa elekto sed ne la plenan aksiomon de elekto, la scio ke aparta pruvo nur postulas dependan elekton povas esti utila.

Uzoj

Difinoj de:

• Aro de Bernstein
• Spaco de Novak
• Hierarkio de borelaj aroj en polaj spacoj
• Buleaj termoj
• Alef-nombroj
• Beth-nombroj
• Orda numera aritmetiko - adicio, multipliko, potencigo
• Klaso de Baire (por funkcio inter polaj spacoj)
• Konstruebla universo
• Larĝo de Cantor-Bendixson de distribuita spaco

Vidu ankaŭ

• Matematika indukto
• Epsilono-indukto
• Plena indukto
• Orda numero
• Bona ordo