Transfinia indukto

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En matematiko, transfinia indukto estas vastigaĵo de matematika indukto al bonordaj aroj, ekzemple al aro de ordaj numerojkardinaloj.

Transfinia indukto[redakti | redakti fonton]

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[redakti | redakti fonton]

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 g1, kaj klasaj funkcioj G2, G3, ekzistas unika funkcio F: Ord → V tia ke

  • F(0) = g1,
  • F(α + 1) = G2(F(α)), por ĉiuj α en Ord,
  • F(λ) = G3(F \upharpoonright λ), por ĉiu limiga λ≠0.

Noto ke postulatas ke la domajnoj de G2, G3 estas larĝaj sufiĉe por fari la pli suprajn propraĵojn signfajn. 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[redakti | redakti fonton]

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 la kontinuaĵo. Estu v0 egala r0. Tiam estu v1 egala rα1, kie α1 estas plej malgranda tia ke rα1 − v0 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[redakti | redakti fonton]

Difinoj de:

Vidu ankaŭ[redakti | redakti fonton]