Аксиома избора

Из Википедије, слободне енциклопедије

У математици, аксиома избора, или АИ, је аксиома теорије скупова. Неформално речено, аксиома тврди да је за било коју дату групу посуда, од којих се у свакој налази најмање по један предмет, могуће изабрати по тачно један предмет из сваке посуде, чак и ако постоји бесконачно много посуда и нема правила које говори који предмет да се узме из сваке. Аксиома избора није неопходна ако је број посуда коначан, или ако је задато такво правило.

Аксиому избора је 1904. године формулисао Ернст Зермело.[1] Иако је у почетку била контроверзна, данас је већина математичара користи без резерви.[2] Један од разлога што је прихваћена јесте велики број важних математичких резултата, као што је теорема Тихонова, захтевају аксиому избора у својим доказима. Савремени теоретичари скупова такође проучавају аксиоме које нису компатибилне са аксиомом избора, као што је аксиома одређености. За разлику од аксиоме избора, ове алтернативе обично нису исказане као аксиоме математике, већ само као принципи у теорији скупова, са интересантним последицама.

Исказ[уреди]

Функција избора је функција f, дефинисана на колекцији X непразних скупова, таква да за сваки скуп s из X, f(s) је елемент из s. Помоћу овог концепта, аксиома може да се искаже на следећи начин:

За сваки скуп непразних скупова, X, постоји функција избора f, дефинисана на X.

Стога, негација аксиоме гласи да постоји скуп непразних подскупова који нема функцију избора.

Свака функција избора над колекцијом X непразних скупова се може посматрати као (или идентификовати са) елементом Декартовог производа скупова из X. Ово доводи до исказа који је еквивалентан аксиоми избора:

Произвољан Декартов производ непразних скупова је непразан.

Варијанте[уреди]

Постоје многе варијанте других еквивалентних исказа аксиоме избора. Они су еквивалентни у смислу да, у присуству осталих основних аксиома теорије скупова, они имплицирају аксиому избора, и аксиома избора имплицира њих.

Једна варијанта избегава коришћење функције избора, заменивши сваку функцију избора својим опсегом.

Ако је дат било који скуп X, у пару дисјунктних непразних скупова, постоји најмање један скуп C који садржи тачно по један заједнички елемент са са сваким од скупова из X.

Још једна еквивалентна аксиома посматра само колекције X које су у бити партитивни скупови других скупова:

За сваки скуп A, партитивни скуп од A (минус празан скуп) има функцију избора.

Неки аутори који користе ову формулацију често говоре о функцији избора над A, али треба имати у виду да је ово мало другачији појам од појма функције избора. Њен домен је партитивни скуп од A (минус празан скуп), па стога има смисла за сваки скуп A, док код дефиниција у остатку овог чланка, домен функције избора над колекцијом скупова је та колекција, па зато има смисла само за скупове скупова. Са овим алтернативним појмом функције избора, аксиома избора се може краће записати као

Сваки скуп има функцију избора.[3]

што је еквивалентно са

За сваки скуп A, постоји функција f, таква да се за сваки непразан подскуп B од A, f(B) налази у B.

Негација аксиоме се стога може изразити као:

Постоји скуп A, такав да за све функције f (на скупу непразних подскупова од A), постоји B, такво да се f(B) не налази у B.

Употреба[уреди]

До касног 19. века, аксиома избора је често коришћена имплицитно, мада још није била формално изречена. На пример, након што би установио да скуп X садржи само непразне скупове, математичар би могао да каже „нека је F(s) један од чланова s за свако s из X“. У општем случају, није могуће да се докаже да F постоји без аксиоме избора, али изгледа да ово до Зермела нико није уочио.

Не захтева свака ситуација аксиому избора. За коначне скупове X, аксиома избора следи из других аксиома теорије скупова. У том случају је еквивалентно рећи да ако постоји неколико (коначан број) посуда, од којих свака садржи најмање по један предмет, онда може да буде изабран по тачно један предмет из сваке посуде. Јасно, ово је могуће спровести: крене се од прве посуде из које се изабере један предмет; продужи се до посуде кутије из које се изабере један предмет; и тако даље. Број посуда је коначан, тако да ће се у једном тренутку процедура избора завршити. Резултат је експлицитна функција избора: функција која пресликава прву кутију у први изабрани елемент, другу кутију у други изабрани елемент, и тако даље. (Формални доказ за све коначне скупове би користио принцип математичке индукције.)

И код одређених бесконачних скупова X је могуће избећи аксиому избора. На пример, ако се претпостави да су елементи од X скупови природних бројева. Сваки непразан скуп природних бројева има најмањи елемент, па се функција избора може дефинисати просто тако што пресликава сваки скуп у најмањи елемент тог скупа. Ово даје избор елемента за сваки скуп, и може да се запише експлицитан израз који говори коју вредност функција узима. Сваки пут када је могуће начинити такав експлицитан избор, аксиома избора није неопходна.

Тешкоће се појављују када не постоји природан избор елемената из сваког скупа. Ако није могуће начинити експлицитне изборе, како се да се зна да ти скупови постоје? На пример, под претпоставком да је X скуп свих непразних подскупова реалних бројева. Први покушај решења би могао да буде исти као и у случају коначног броја скупова. Ако се бира елемент из сваког скупа редом, пошто је X бесконачан скуп, процедура избора се никад неће окончати, и стога на овај начин није могуће произвести функцију избора за X. Значи, такав приступ не ради. Следећа могућност би била да се одреди најмањи елемент сваког скупа. Међутим, неки подскупови реалних бројева немају најмањи елемент. На пример, отворени интервал (0, 1) нема најмањи елемент: Ако је x унутар (0, 1), онда је и x/2 у том интервалу, а x/2 је увек строго мање од x. Дакле, ни узимање најмањег елемента није решење.

Разлог зашто је могуће узети најмање елементе из подскупова природних бројева лежи у чињеници да природни бројеви имају своју добру уређеност: сваки подскуп скупа природних бројева има јединствени најмањи елемент у односу на природно уређење. Могло би да се примети да: Иако уобичајено уређење реалних бројева не ради, можда је могуће да се нађе другачије уређење реалних бројева које добро уређује скуп. Тада би функција избора могла да изабере најмањи елемент из сваког скупа у односу на ово ново уређење. Проблем налажења функције избора тада прелази у провлем конструисања доброг уређења, а испоставља се да је аксиома избора неопходна за његово постојање; сваки скуп може да буде добро уређен ако и само ако аксиома избора важи.

Неконструктивни аспекти[уреди]

Доказ који захтева аксиому избора је, у једном значењу речи, неконструктиван: чак иако доказ потврђује постојање објекта, може да буде немогуће да се тај објекат дефинише у језику теорије скупова. На пример, иако аксиома избора имплицира да постоји добро уређење реалних бројева, постоје модели теорије скупова са аксиомом избора у којима се не може дефинисати ни једно добро уређење реалних бројева. Још један пример је подскуп реалних бројева који није Лебег мерљив, за који се може доказати да постоји коришћењем аксиоме избора, али је конзистентно да се такав скуп не може дефинисати.

Неки математичари не воле аксиому избора јер она производи овакве објекте који не могу да се конструишу. Како нема канонског доброг уређења било ког скупа, конструкција која се ослања на добро уређење може да не произведе канонски резултат, чак и када се он тражи (као што је често случај у теорији категорија). Мала заједница математичара конструктивиста тврди да би сви докази постојања морали да буду потпуно експлицитни; морало би да буде могуће да се конструише, на експлицитан и канонски начин, све за шта је доказано да постоји. Они одбацују пуну аксиому избора јер она утврђује постојање објекта, без да јединствено одреди његову структуру. Штавише, теорема Ђаконеску-Гудман-Мајхил (Diaconescu–Goodman–Myhill) показује како да се изведе конструктивно неприхватљиви принцип искључења трећег, или његову ограничену форму, у конструктивној теорији скупова из претпоставке аксиоме избора.

Још један аргумент против аксиоме избора је тај што она имплицира постојање контраинтуитивних објеката. Један пример овога је парадокс Банаха-Тарског, који тврди да је могуће декомпоновати ("раставити, исећи") тродимензиону једноделну лопту у коначно много делова, и коришћењем само ротација и транслација, преуредити ове делове тако да дају две једноделне лопте од којих је свака запремине једнаке почетној од које су настале. Делови у овој декомпозицији, конструисани коришћењем аксиоме избора, су екстремно компликовани.

Упркос овим аргументима, већина математичара прихвата аксиому избора као валидан принцип за доказивање нових резултата у математици.

Многе теореме је могуће доказати без коришћења било аксиоме избора, било њене негације; ово је уобичајено у конструктивној математици. Такви искази ће бити истинити у сваком моделу Зермело-Френкел теорије скупова (ЗФ), независно од истинитости или неистинитоси аксиоме избора у том појединачном моделу. Ограничење на ЗФ чини сваку тврдњу која се ослања било на аксиому избора било на њену негацију, недоказивом. На пример, парадокс Банаха-Тарског није могуће ни доказати, нити оповргнути коришћењем саме ЗФ: немогуће је да се конструише тражена декомпозиција лопте у ЗФ, али је такође немогуће да се покаже да таква декомпозиција не постоји. Слично, сви доле излистани искази који у свом доказу захтевају аксиому избора, или неку њену слабију верзију, су недоказиви у ЗФ, али како је сваки од њих доказив у ЗФ плус аксиома избора, постоје модели ЗФ у којима је сваки исказ тачан. Искази као што је парадокс Банаха-Тарског могу да се преформулишу у условне исказе, на пример Ако аксиома избора важи, декомпозиција из парадокса Банаха-Тарског постоји. Такви условни искази су доказиви у ЗФ када су почетни искази доказиви у ЗФ плус аксиома избора.

Независност[уреди]

По раду Курта Гедела и Пола Коена, аксиома избора је логички независна од осталих аксиома Зермело-Френкел теорије скупова (ЗФ). Ово значи да ни она, нити њена негација не могу да буду доказане унутар ЗФ, ако је ЗФ конзистентна. Последично, ако је ЗФ конзистентна, онда је и ЗФ плус аксиома избора конзистентна, као и ЗФ плус негација аксиоме избора. Значи одлука да ли је или није прикладно да се у доказима користи аксиома избора не може да буде донета позивањем на остале аксиоме теорије скупова. Ова одлука се мора донети на некој другој основи.

Један аргумент у прилог коришћења аксиоме избора јесте то што је она згодна: њено коришћење не може да шкоди (не може да доведе до контрадикције), а омогућава да се докажу неке ствари кое иначе не би било могуће доказати. Теореме као што су: сваки идеал у прстену је садржан у максималном идеалу, сваки векторски простор има базу и сваки производ компактних простора је компактан, можда не би важиле за математичке објекте велике кардиналности.

Резултат доказа независности такође показује да широка класа математичких исказа, укључујући све исказе који се могу изрећи језиком Пеанове аритметике, су доказиви у ЗФ ако и само ако су доказиви у ЗФ са аксиомом избора. Искази у овој класи укључују исказ да П = НП, Риманову хипотезу, и многе друге нерешене математичке проблеме. Када се покуша решавање проблема из ове класе, нема разлике да ли се претпоставља ЗФ или ЗФИ (Зермело-Френкел са аксиомом избора), ако је поставља само питање постојања доказа. Међутим, могуће је да постоји краћи доказ који следи из ЗФИ него из ЗФ.

Аксиома избора није једини значајан исказ који је независан од ЗФ. На пример, уопштена хипотеза континуума није само независна у односу на ЗФ, већ је независна и у односу на ЗФИ. Међутим, ЗФ плус уопштена хипотеза континуума имплицирају аксиому избора, што чини уопштену хипотезу континуума строго јачим тврђењем од аксиоме избора, невезано за чињеницу да су оба независна у односу на ЗФ.

Јаче аксиоме[уреди]

Аксиома конструктабилности и уопштена хипотеза континуума обе имплицирају аксиому избора, али су строго јаче од ње.

У класи теорија као што су Фон Нојман-Бернејз-Геделова теорија скупова и Морзе-Келеј теорија скупова, постоји могућа аксиома која се зове аксиома глобалног избора која је јача од аксиоме избора за скупове јер такође важи и за праве класе. И аксиома глобалног избора следи из аксиоме ограничења величине.

Еквиваленти[уреди]

Постоји јако велики број важних исказа који су под претпоставком аксиома ЗФ али не и аксиоме избора нити њене негације, еквивалентни са аксиомом избора. Најважнији међу њима су Зорнова лема и теорема добре уређености. У ствари, Зермело је испрва и увео аксиому избора како би формализовао свој доказ принципа добре уређености.

Теорија категорија[уреди]

Неколико резултата теорије категорија користе аксиому избора у својим доказима. Ови резултати могу да буду слабији, еквивалентни или јачи од аксиоме избора, у зависности од снаге техничких основа. На пример, ако се категорије дефинишу у појмовима скупова, то јест као скупове објеката и морфизме (што се обично назива мала категорија), или чак локално мале категорије, чији објекти су скупови, онда не постоји категорија свих скупова, па је тешко да се формулација теорије категорија примени на све скупове. Са друге стране, други описи основа теорије категорија су знатно снажнији, па идентичнан исказ избора теорије категорија може да буде јачи од стандардне формулације описане раније.

Међу примерима исказа теорије категорија који захтевају избор су:

Слабији облици[уреди]

Постоји неколико слабијих исказа који нису еквивалентни са аксиомом избора, али су у блиској вези с њом. Један пример је аксиома пребројивог избора, која каже да функција избора постоји за сваки пребројиви скуп X, и јача аксиома зависног избора. Ове аксиоме су довољне за многе доказе у области елементарне математичкој анализи, и конзистентне су са неким принципима, као што је Лебег мерљивост свих скупова реалних бројева, који се могу оповргнути из аксиоме избора.

Међу осталим аксиомама слабијим од аксиоме избора су Буловска теорема о простом идеалу и аксиома униформизације.

Резултати који захтевају АИ (или њене слабије облике) а слабији су од ње[уреди]

Један од интересантних момената у вези аксиоме избора јесте велики број места у математици где се она појављује. Следе примери исказа који захтевају аксиому избора у смислу да нису доказиви из Зермело-Френкел теорије скупова, али су доказиви из ЗФ ако јој се дода аксиома избора. Еквивалентно, ови искази су тачни у свим моделима ЗФ плус АИ, али су нетачни у неким моделима ЗФ.

Јачи облици ¬АИ[уреди]

Размотримо јаче облике негације аксиоме избора. На пример, ако ознаком БС означимо тврдњу да сваки скуп реалних бројева има Берово својство, онда је БС јаче од ¬АИ (негација аксиоме избора), која тврди непостојање било какве функције избора на можда само једном скупу непразних скупова. Ваља уочити да ојачане негације могу да буду сазласне са слабијим облицима аксиоме избора. На пример, ЗФ + ЗИ[5] + БС је конзистентно ако је ЗФ конзистентно.

Са ЗФ + ЗИ је такође конзистентно са тврђењем да је сваки скуп реалних бројева Лебег мерљив; међутим ова конзистентност, по Роберту М. Соловеју, не може да се докаже из саме ЗФ плус аксиома избора, већ захтева благу претпоставку великог кардинала (постојање недоступног кардинала). Много јача аксиома одређености, или АО, имплицира да је сваки скуп реалних бројева Лебег мерљив, има Берово својство, и својство савршеног скупа (сва три тврђења су резултат одбацивања аксиоме избора). ЗФ + ЗИ + АО је конзистентно ако је довољно јака аксиома великог кардинала конзистентна (постојање бесконачно много Вудинових кардинала).

Резултати који захтвају ¬АИ[уреди]

Постоје модели Зермело-Френкел теорије скупова у којима је аксиома избора нетачна. Ознака ЗФ¬И се користи као скраћеница за Зермело-Френкел теорија скупова са негацијом аксиоме избора'. За неке моделе ЗФ¬И је могуће доказати негацију неких стандардних чињеница. Ваља имати у виду да је сваки модел за ЗФ¬И такође и модел за ЗФ, па за сваки од следећих исказа постоји модел ЗФ у коме је исказ тачан.

  • Постоји модел ЗФ¬И у коме постоји функција f из скупа реалних бројева у скуп реалних бројева, таква да f није непрекидна на a, али за сваки низ {xn} који конвергира ка a, limn f(xn)=f(a).
  • Постоји модел ЗФ¬И у коме су реални бројеви пребројива унија пребројивих скупова.[тражи се извор од 06. 2011.]
  • Постоји модел ЗФ¬И у коме постоји поље које нема алгебарско затворење.
  • У свим моделима ЗФ¬И постоји векторски простор без базе.
  • Постоји модел ЗФ¬И у коме постоји векторски простор са две базе различите кардиналности.

За доказе, видети књигу Томаса Јеха, The Axiom of Choice, American Elsevier Pub. Co., New York, 1973.

Цитати[уреди]

"Аксиома избора је очигледно тачна, теорема добре уређености очигледно није тачна, а за Зорнову лему, ко зна?" — Џери Бона

Ово је шала: иако су ова три исказа математички еквивалентна, већина математичара сматра аксиому избора интуитивном, принцип добре уређености контраинтуитивним, а Зорнову лему сувише комплексном за било какву интуицију.

"Аксиома избора је неопходна да би се изабрао скуп из бесконачног броја чарапа, али не и за бесконачан број ципела." — Бертран Расел

Ово је запажање да може да се дефинише функција избора из бесконачног броја пари ципела тако што се на пример каже да се увек бира лева ципела. Међутим, без аксиоме избора, не може се тврдити да таква функција постоји за чарапе, јер се лева и десна чарапа (по претпоставци) међусобно не разликују.

Извори[уреди]

  1. ^ Zermelo, Ernst (1904). „Beweis, dass jede Menge wohlgeordnet werden kann“ (reprint). Mathematische Annalen 59: 514-16. DOI:10.1007/BF01445300. 
  2. ^ van Heijenoort, 1967, pp. 183. Jech, 1977, pp. 348ff.
  3. ^ Patrick Suppes, "Axiomatic Set Theory", Dover, 1972 (1960). ISBN 978-0-486-61630-8. pp. 240
  4. ^ „[FOM] Are (C,+) and (R,+) isomorphic“. www.cs.nyu.edu. 
  5. ^ аксиома зависног избора

Литература[уреди]

  • Herrlich, Horst, Axiom of Choice, Springer Lecture Notes in Mathematics 1876, Springer Verlag Berlin Heidelberg (2006). ISBN 978-3-540-30989-5.
  • Paul Howard and Jean Rubin, "Consequences of the Axiom of Choice". Mathematical Surveys and Monographs 59; American Mathematical Society; 1998.
  • Thomas Jech, "About the Axiom of Choice." Handbook of Mathematical Logic, John Barwise, ed., 1977.
  • Gregory H Moore, "Zermelo's axiom of choice, Its origins, development and influence", Springer; 1982. ISBN 978-0-387-90670-6.
  • Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: (1908). pp. 261-81. PDF download via digizeitschriften.de
Превод на енглески: Jean van Heijenoort, 2002. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. New edition. Harvard Univ. Press. ISBN 978-0-674-32449-7.
  • 1904. "Proof that every set can be well-ordered," 139-41.
  • 1908. "Investigations in the foundations of set theory I," 199-215.

Спољашње везе[уреди]