Aksiomo de elekto

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

En matematiko, la aksiomo de elekto, aŭ AC, estas aksiomo de aroteorio. Neformale, la aksiomo de elekto statas ke por ĉiu donita kolekto de ujoj, ĉiu enhavanta po almenaŭ unu objekto, eblas fari elekton de akurate unu objekto el ĉiu ujo, eĉ se estas malfinie multaj ujoj kaj ne estas regulo por tio kiun objekton preni el ĉiu ujo. La aksiomo de elekto estas ne postulita se la kvanto de ujoj estas finia aŭ se aparta regulo por la elektado estas havebla.

La aksiomo de elekto estas uzata kune kun la aksiomoj de aroteorio de Zermelo-Fraenkel (ZF). Estu ZFC mallongigo de "aksiomoj de Zermelo-Fraenkel plus la aksiomo de elekto".

La aksiomo de elekto estis formulita en 1904 de Ernst Zermelo. Kvankam originale kontraŭa, ĝi estas nun uzata sen rezervo per plejparto de matematikistoj. Unu motivado por ĉi tiu uzo estas ke multaj gravaj matematikaj rezultoj, kiel teoremo de Tychonoff, postulas la aksiomon de elekto por iliaj pruvoj. Modernaj araj teoriistoj ankaŭ studas aksiomojn kiuj estas ne kongruaj kun la aksiomo de elekto, kiel la aksiomo de determineco. Malsimile al la aksiomo de elekto, ĉi tiuj alternativoj estas kutime ne proponataj kiel aksiomoj por matematiko, sed nur kiel principoj en aroteorio kun interesaj konsekvencoj.

Frazo[redakti | redakti fonton]

Elekta funkcio estas funkcio f, difinita sur aro X de nemalplenaj aroj, tia ke por ĉiu aro s en X, f(s) estas ero de s. Kun ĉi tiu koncepto, la aksiomo povas esti skribita kiel:

Por ĉiu aro X de nemalplenaj aroj, tie ekzistas elekta funkcio f difinita sur X.

Tial la nego de la aksiomo de elekto statas ke ekzistas aro de nemalplenaj aroj kiu ne havas elektan funkcion.

Ĉiu elekta funkcio sur kolekto X de nemalplenaj aroj povas esti konsiderata kiel (aŭ identigita kun) ero de la kartezia produto de la aroj en X. Ĉi tio kondukas al ekvivalenta frazo de la aksiomo de elekto:

Por ĉiu donita kolekto de nemalplenaj aroj, ilia kartezia produto estas nemalplena aro.

Variantoj[redakti | redakti fonton]

Estas multaj aliaj ekvivalentaj frazoj de la aksiomo de elekto. Ili estas ekvivalentoj en la senco ke, en ĉeesto de la aliaj bazaj aksiomoj de aroteorio, ĉiu el ili implicas la aksiomon de elekto kaj estas implicita de ĝi.

Unu variaĵo evitas la senperan uzon de elektaj funkcioj:

Por ĉiu donita aro X de duope disaj ne-malplenaj aroj, tie ekzistas almenaŭ unu aro C kiu enhavas akurate po unu eron komunan kun ĉiu el la aroj en X.

Alia ekvivalenta aksiomo nur konsideras arojn X kiuj estas esence potencaroj de aliaj aroj:

Por ĉiu aro A, la aro de ĉiuj subaroj de A, kun la malplena aro forprenita, havas elektan funkcion.

Aŭtoroj kiu uzas ĉi tiun formulaĵon ofte parolas pri la elekta funkcio sur A, sed uzas malsaman komprenon de elekta funkcio. Ĝia fonto-aro estas la potencaro de A kun la malplena aro forprenita, kaj tiel la nocio havas sencon por ĉiu aro A, sed en la difino uzita aliloke en ĉi tiu artikolo, la fonto-aro de elekta funkcio sur kolekto de aroj estas ĉi tiu kolekto, kaj tiel ĝi nur havas sencon por aroj de aroj. Kun ĉi tiu alia komprenaĵo de elekta funkcio, la aksiomo de elekto povas esti kompakte skribita kiel

Ĉiu aro havas elektan funkcion.

kio estas ekvivalento al

Por ĉiu aro A estas funkcio f tia ke por ĉiu ne-malplena subaro B de A, f(B) estas en B.

La nego de la aksiomo povas tial esti esprimita kiel:

Ekzistas aro A tia ke por ĉiuj funkcioj f sur la aro de ne-malplenaj subaroj de A, estas B tia ke f(B) ne estas en B.

Limigo al finiaj aroj[redakti | redakti fonton]

La kutima frazo de AC ne specifigas malfiniecon de la aro, kaj do ĝi statas ke ankaŭ ĉiu finia aro de nemalplenaj aroj havas (finian) elektan funkcion. Tamen, la finia okazo estas teoremo de aroteorio de Zermelo-Fraenkel (ZF), kaj estas facile pruvata per matematika indukto.

La intuicieco de AC povas esti pro ĝeneraligo de ĉi tiu finia okazo.

Uzado[redakti | redakti fonton]

Ĝis fino de la 19-a jarcento, la aksiomo de elekto estis ofte uzata implice, kvankam ĝi ankoraŭ ne estis formale skribita. Ekzemple, post trovo ke la aro X enhavas nur ne-malplenajn arojn, matematikisto povus diri "estu F(s) unu el la membroj de s por ĉiuj s en X.". Ĝenerale, neeblas pruvi ke F ekzistas sen la aksiomo de elekto, sed ĉi tio aspektas al esti nenotita ĝis Zermelo.

Ne ĉiu situacio postulas la aksiomon de elekto. Por finiaj aroj X, la aksiomo de elekto sekvas el la aliaj aksiomoj de aroteorio. En ĉi tiu okazo ĝi estas ekvivalenta al diro ke se oni havas finian kvanton da skatolojn, ĉiu enhavanta almenaŭ unu aĵon, tiam oni povas elekti akurate po unu aĵon el ĉiu skatolo. Klare oni povas fari ĉi tion: oni startu je la unua skatolo, elektu aĵon; iru al la dua skatolo, elektu aĵon; kaj tiel plu. La kvanto de skatoloj estas finia, do iam la elekta proceduro venas al fino. La rezulto estas eksplicita elekta funkcio: funkcio kiu prenas la unuan skatolon kiel la ardumento kaj redonas la unuan eron kiun oni elektis, prenas la duan skatolon kaj redonas la duan eron kiun oni elektis, kaj tiel plu. Formala pruvo por ĉiuj finiaj aroj devus uzi la principon de matematika indukto.

Por certaj malfiniaj aroj X, estas ankaŭ eble eviti la aksiomon de elekto. Ekzemple, supozu ke la eroj de X estas aroj de naturaj nombroj. Ĉiu nemalplena aro de naturaj nombroj havas la plej malgrandan eron, do por precizigi la elektan funkcion oni povas simple diri ke ĝi bildigas ĉiun aron al la plej malgranda ero de la aro. Ĉi tio donas difinitan elekton de ero el ĉiu aro kaj tiel aperas eksplicita esprimo kiu diras kiun valoron la elekta funkcio redonas. Se eblas precizigi ĉi tian eksplicitan elekton, do la aksiomo de elekto estas senbezona.

La malfacilaĵo aperas se ne estas natura elekto de eroj de ĉiu aro. Se oni ne povas fari eksplicitajn elektojn, kiel oni scias ke la aro ekzistas? Ekzemple, supozu ke X estas aro de ĉiuj ne-malplenaj subaroj de la reelaj nombroj. Unue oni povus provi procedi kvazaŭ X estis finia. Se oni provas elekti eron de ĉiu aro, tiam, ĉar X estas malfinia, la elekta proceduro neniam finiĝos, kaj sekve, oni neniam kapablas produkti elektan funkcion por ĉiuj eroj de X. Alie, oni povus provi precizigi la elekton, uzante la plej malgrandan eron de ĉiu aro. Sed iuj subaroj de la reelaj nombroj ne havas plej malgrandan eron. Ekzemple, la malfermita intervalo (0, 1) ne havas plej malgrandan eron: se x estas en (0, 1), do ankaŭ estas x/2 en (0, 1), kaj x/2 estas ĉiam severe pli malgranda ol x. Do preno de la plej malgranda ero ne laboras.

La kaŭzo ke oni povas elekti plej malgrandajn erojn de subaroj de la naturaj nombroj estas tio ke la naturaj nombroj estas antaŭ-ekipitaj kun bona ordo: ĉiu nemalplena subaro de la naturaj nombroj havas unikan plej malgrandan eron sub la natura ordigo. Eble oni povus diri, ke eĉ kvankam la kutima ordigo de la reelaj nombroj ne laboras, eble eblas trovi la alian ordigon de la reelaj nombroj kiu estas bona ordo. Tiam la elekta funkcio povus elekti la plej malgrandan eron de ĉiu aro sub la nova ordigo. La problemo tiam iĝas je konstruado de la bona ordo, kiu, kiel okazas, denove postulas la aksiomon de elekto por sia ekzisto; ĉiu aro povas esti bone ordigita se kaj nur se la aksiomo de elekto estas vera.

Nekonstruaj aspektoj[redakti | redakti fonton]

Pruvo postulanta la aksiomon de elekto estas, en unu signifo de la vorto, nekonstruanta: eĉ kvankam la pruvo establas la ekziston de objekto, povas esti neeble difini la objekton en la lingvo de aroteorio. Ekzemple, dum la aksiomo de elekto implicas ke ekzistas bona ordo de la reelaj nombroj, estas modeloj de aroteorio kun la aksiomo de elekto en kiu neniu bona ordo de la reelaj nombroj estas difinebla. Kiel la alia ekzemplo, subaro de la reelaj nombroj kiu estas ne lebege mezurebla povas esti pruvita al ekzisti uzante la aksiomon de elekto, sed estas konsekvence ke neniu ĉi tia aro estas difinebla.

La aksiomo de elekto produktas ĉi tiujn objektojn kiuj estas pruvitaj al ekzisti per nekonstruanta pruvo, sed ne povas esti eksplicite konstruitaj, kio povas konflikti kun iuj filozofiaj principoj. Ĉar ne estas kanona bona ordo de ĉiuj aroj, konstruado kiu fidas sur bona ordo povas ne produkti kanonan rezulton, eĉ se kanona rezulto estas dezirata (kiel estas ofte la okazo en teorio de kategorioj). En konstruismo, ĉiuj ekzistaj pruvoj estas postulataj al esti tutece eksplicitaj. Tio estas, oni devas kapabli konstrui, en eksplicita kaj kanona maniero, iun tion kiu estas pruvata al ekzisti. Ĉi tiu ismo malakceptas la plenan aksiomon de elekto ĉar ĝi asertas la ekziston de objekto sen unika difino de ĝia strukturo. Fakte la teoremo de Diaconescu-Goodman-Myhill montras kiel derivi la konstrue neakcepteblan leĝon de malinkluzivata mezo, aŭ limigitan formon de ĝi, en konstrua aroteorio de la supozo de la aksiomo de elekto.

Alia argumento kontraŭ la aksiomo de elekto estas ke ĝi implicas ekziston de kontraŭintuiciaj objektoj. Unu ekzemplo de ĉi tiu estas la paradokso de Banaĥo-Tarski kiu diras ke eblas malkomponi la 3-dimensian solidan unuoblan pilkon en finie multajn pecojn kaj, uzante nur turnadojn kaj movojn, rekunigi la pecojn en du solidajn pilkojn ĉiu kun la sama volumeno kiel la originala. La pecoj en ĉi tiu malkomponaĵo, konstruitaj uzante la aksiomon de elekto, estas ege komplikaj.

La plejparto de matematikistoj akceptas la aksiomon de elekto kiel valida principo por pruvado de novaj rezultoj en matematiko. Estas sufiĉe interese, tamen, noti ĉu iu teoremo en ZFC estas logike ekvivalenta (kun la ZF aksiomoj) al la aksiomo de elekto, kaj matematikistoj serĉas rezultojn kiuj postulas ke la aksiomo de elekto estu malvera, kvankam ĉi tiu speco de konkludoj estas malpli komuna ol la speco kiu postulas la aksiomo de elekto al esti vera.

Eblas pruvi multajn teoremojn uzante nek la aksiomo de elekto nek ĝian negon; ĉi tio estas komuna en konstruiva matematiko. Ĉi tiaj frazoj estas veraj en ĉiu modelo de ZF, sendistinge de la vereco aŭ malvereco de la aksiomo de elekto en ĉi aparta modelo. En la limigo al ZF, ĉiu pretendo, kiu fidas sur la aksiomo de elekto aŭ ĝia nego, estas nepruvebla. Ekzemple, la paradokso de Banaĥo-Tarski estas nek demonstrebla nek malpruvebla de ZF sola: neeblas konstrui la postulatan malkomponaĵon de la unuobla pilko en ZF, sed ankaŭ neeblas pruvi ke ne ekzistas ĉi tiu malkomponaĵo. Simile, ĉiu frazoj listigitaj pli sube kiuj postulas la aksiomon de elekto aŭ iu pli malfortan version por pruvo estas nepruveblaj en ZF, sed pro tio ke ĉiu el ili estas demonstrebla en ZF plus la aksiomo de elekto, estas modeloj de ZF en kiuj ĉiu el la frazoj estas vera. Frazoj kiel la paradokso de Banaĥo-Tarski povas esti refrazigitaj kiel kondiĉaj frazoj, ekzemple, "se AC veras, do ekzistas la malkomponaĵo de la paradokso de Banaĥo-Tarski". Ĉi tiaj kondiĉaj frazoj estas demonstreblaj en ZF se la originalaj frazoj estas demonstreblaj en ZFC.

Sendependeco[redakti | redakti fonton]

Estu ZF¬C mallongigo de "aroteorio de Zermelo-Fraenkel plus la nego de la aksiomo de elekto". La aksiomo de elekto estas logike sendependa de la aliaj aksiomoj de ZF. Ĉi tio signifas ke nek ĝi nek ĝia nego povas esti pruvita al esti vera en ZF, se ZF estas konsekvenca. Sekve, se ZF estas konsekvenca, do ZFC estas konsekvenca kaj ankaŭ ZF¬C estas konsekvenca. Do la decido ĉu estas konvene uzi la aksiomon de elekto en pruvo ne povas esti farita per alvoko de la aliaj aksiomoj de aroteorio. La decido devas esti farita sur la aliaj bazoj. La sendependeco estas montrita en laboro de Kurt Gödel kaj Paul Cohen.

Unu argumento donita en komplezo de uzado de la aksiomo de elekto estas ke ĝi estas oportuna: uzo de ĝi ne povas rezulti en kontraŭdiro kaj ebligan pruvi iujn frazojn kiuj alie ne povas esti pruvitaj. Multaj teoremoj kiuj estas demonstreblaj uzante la aksiomon de elekto estas de eleganta ĝenerala karaktero: ĉiu idealo en ringo estas enhavata en maksimuma idealo, ĉiu vektora spaco havas bazon, kaj ĉiu produto de kompaktaj spacoj estas kompakta. Sen la aksiomo de elekto, ĉi tiuj teoremoj povas esti ne veraj por matematikaj objektoj de grandaj kardinaloj.

La pruvo de la sendependeca rezulto ankaŭ montras ke larĝa klaso de matematikaj frazoj, inkluzivante ĉiujn propoziciojn kiuj povas esti frazitaj en la lingvo de aritmetiko de Peano, estas demonstreblaj en ZF se kaj nur se ili estas demonstreblaj en ZFC. Ĉi tio estas ĉar aritmetikaj frazoj estas absolutaj al la konstruebla universo L. Absoluteca teoremo de Shoenfield donas pli ĝeneralan rezulton. Frazoj en ĉi tiu klaso inkluzivas la frazojn kiel P = NP, la rimana hipotezo, kaj multaj aliaj nesolvitaj matematikaj problemoj. Kiam oni provas solvi problemojn en ĉi tiu klaso, ne estas diferenco ĉu ZF aŭ ZFC estas uzata se la nura demando estas la ekzisto de pruvo. Eblas, tamen, ke estas pli mallonga pruvo de teoremo en ZFC ol en ZF.

La aksiomo de elekto estas ne la nura grava frazo kiu estas sendependa de ZF. Ekzemple, la ĝeneraligita kontinuaĵa hipotezo (GCH) estas ne nur sendependa de ZF, sed ankaŭ sendependa de ZFC. Tamen, ZF plus GCH implicas AC, tiel GCH estas severe pli forta pretendo ol AC, eĉ kvankam ili ambaŭ estas sendependaj de ZF.

Pli fortaj aksiomoj[redakti | redakti fonton]

La aksiomo de konstruebleco kaj la ĝeneraligita kontinuaĵa hipotezo ambaŭ enhavas la aksiomon de elekto, sed estas severe pli fortaj ol ĝi.

En klasaj teorioj kiel aroteorio de Von Neumann-Bernays-Gödel kaj aroteorio de Morse-Kelley, estas ebla aksiomo nomata kiel la aksiomo de malloka elekto kiu estas pli forta ol la aksiomo de elekto por aroj ĉar ĝi aplikas ankaŭ al propraj klasoj. Kaj la aksiomo de malloka elekto sekvas el la aksiomo de limigo de amplekso.

Ekvivalentoj[redakti | redakti fonton]

Estas multaj gravaj frazoj kiuj, alprenante la aksiomojn de ZF sed nek AC nek ¬AC, estas ekvivalentaj al la aksiomo de elekto. La plej gravaj inter ilin estas lemo de Zorn kaj la bona orda teoremo. Fakte, Zermelo komence prezentis la aksiomon de elekto por formaligi sian pruvon de la bona orda teoremo.

Teorio de kategorioj[redakti | redakti fonton]

Estas kelkaj rezultoj en teorio de kategorioj kiuj bezonas la aksiomon de elekto por sia pruvo. Ĉi tiuj rezultoj povus esti pli malfortaj ol, ekvivalentaj al, aŭ pli fortaj ol la aksiomo de elekto, dependante de la forteco de la teknikaj fundamentoj. Ekzemple, se oni difinas kategoriojn per aroteoriaj terminoj, do kiel arojn de objektoj kaj strukturkonservantajn transformojn (kutime nomataj malgrandaj kategorioj), aŭ eĉ loke malgrandaj kategorioj, kies objektoj estas aroj, tiam ne ekzistas kategorio de ĉiuj aroj, kaj do estas malfacile por kategorio-teoria formulaĵo turni sin al ĉiuj aroj. Aliflanke, aliaj fundamentaj priskriboj de teorio de kategorioj estas konsiderinde pli fortaj, kaj identa kategorio-teoria frazo de elekto povas esti pli forta ol la norma formulaĵo, kiel en la klasa teorio, menciita pli supre.

Ekzemploj de kategorio-teoriaj frazoj kiuj postulas elekton:

Pli malfortaj formoj[redakti | redakti fonton]

Estas kelkaj pli malfortaj frazoj kiuj estas ne ekvivalentoj al la aksiomo de elekto, sed estas proksime rilatantaj. Unu ekzemplo estas la aksiomo de dependa elekto (DC). Ankoraŭ pli malforta ekzemplo estas la aksiomo de kalkulebla elekto (ACω aŭ CC), kiu statas ke elekta funkcio ekzistas por ĉiu kalkulebla aro de nemalplenaj aroj. Ĉi tiuj aksiomoj estas sufiĉaj por multaj pruvoj en rudimenta analitiko, kaj estas konsekvencaj kun iuj principoj, kiel la lebega mezurebleco de ĉiu subaro de reelaj nombroj, kiu estas malpruvebla de la aksiomo de elekto.

Aliaj elektaj aksiomoj pli malfortaj ol aksiomo de elekto estas la bulea prima ideala teoremo kaj la aksiomo de samformigo.

Rezultoj postulantaj aksiomon de elekto aŭ pli malfortajn formojn, sed pli malfortaj ol ĝi[redakti | redakti fonton]

Unu el la plej interesaj aspektoj de la aksiomo de elekto estas la granda kvanto de lokoj en matematiko kie ĝi montriĝas. Jen iuj frazoj kiuj postulas la aksiomon de elekto en la senco ke ili estas ne demonstreblaj de ZF sed estas demonstrebla de ZFC. Ekvivalente, ĉi tiuj frazoj estas veraj en ĉiuj modeloj de ZFC sed malveraj en iuj modeloj de ZF.

Pli fortaj formoj de la nego de AC[redakti | redakti fonton]

Ekzemple, se oni mallongigas per BP la pretendon ke ĉiu aro de reelaj nombroj havas la propraĵon de Baire, tiam BP estas pli forta ol ¬AC, kiu asertas la neekziston de iu elekta funkcio sur eble nur sola aro de nemalplenaj aroj. Fortigita nego de AC povas esti kongrua kun malfortigita formoj de AC. Ekzemple, ZF + DC (aksiomo de dependa elekto) + BP estas konsekvenca, se ZF estas konsekvenca.

Estas ankaŭ konsekvence kun ZF + DC ke ĉiu aro de reelaj nombroj estas lebege mezurebla; tamen, ĉi tiu konsekvenca rezulto, pro Robert M. Solovay, ne povas esti pruvita en ZFC mem, sed postulas mildan grandan kardinalan supozon (la ekziston de nealirebla kardinalo). La multe pli forta aksiomo de determineco AD, implicas ke ĉiu aro de reelaj nombroj estas lebege mezurebla, havas la propraĵon de Baire, kaj havas la perfektan aran propraĵon (ĉiuj tri el ĉi tiuj rezultoj estas refutita per AC mem). ZF + DC + AD estas konsekvenca se sufiĉe forta granda kardinala aksiomo estas konsekvenca (la ekzisto de malfinie multaj kardinaloj de Woodin).

Frazoj konsekvencaj kun la nego de AC[redakti | redakti fonton]

Estas modeloj de ZF en kiuj la aksiomo de elekto estas malvera. Por certaj modeloj de ZF¬C, eblas pruvi negon de iuj normaj faktoj.

Ĉiu modelo de ZF¬C estas ankaŭ modelo de ZF, do por ĉiu el jenaj frazoj, ekzistas modelo) de ZF en kiu la frazo estas vera.

  • Ekzistas modelo de ZF¬C en kiu ekzistas funkcio f de la reelaj nombroj al la reelaj nombroj tia ke f estas ne kontinua je a, sed f estas vice kontinua je a, kio estas, por ĉiu vico {xn} konverĝanta al a,  \lim_{n\to\infty} f(x_n)=f(a).
  • Ekzistas modelo de ZF¬C kiu havas malfinian aron de reelaj nombroj sen kalkuleble malfinia subaro.
  • Ekzistas modelo de ZF¬C en kiu reelaj nombroj estas kalkulebla unio de kalkuleblaj aroj.
  • Ekzistas modelo de ZF¬C en kiu ekzistas kampo sen tegaĵo.
  • En ĉiuj modeloj de ZF¬C ekzistas vektora spaco sen bazo.
  • Ekzistas modelo de ZF¬C en kiu ekzistas vektora spaco kun du bazoj de malsamaj kardinaloj.
  • Ekzistas modelo de ZF¬C en kiu ekzistas libera plena bulea algebro sur kalkuleble multaj generiloj.
  • Ekzistas modelo de ZF¬C en kiu ĉiu aro en Rn estas mezurebla aro. Tial eblas malinkluzivi kontraŭintuiciajn rezultojn similajn al la paradokso de Banaĥo-Tarski kiu estas demonstrebla en ZFC. Plu, ĉi tio estas ebla dum alpreno de la aksiomo de dependa elekto, kiu estas pli malforta ol AC sed sufiĉa por ellabori la plejparton de reela analizo.
  • En ĉiuj modeloj de ZF¬C, la ĝeneraligita kontinuaĵa hipotezo ne veras.

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]