У математици, аксиома избора, или АИ, је аксиома теорије скупова. Неформално речено, аксиома тврди да је за било коју дату групу посуда, од којих се у свакој налази најмање по један предмет, могуће изабрати по тачно један предмет из сваке посуде, чак и ако постоји бесконачно много посуда и нема правила које говори који предмет да се узме из сваке. Аксиома избора није неопходна ако је број посуда коначан, или ако је задато такво правило.
Аксиому избора је 1904. године формулисао Ернст Зермело. Иако је у почетку била контроверзна, данас је већина математичара користи без резерви.van Heijenoort, 1967. pp. 183. Jech, 1977. pp. 348ff. Један од разлога што је прихваћена јесте велики број важних математичких резултата, као што је теорема Тихонова, захтевају аксиому избора у својим доказима. Савремени теоретичари скупова такође проучавају аксиоме које нису компатибилне са аксиомом избора, као што је аксиома одређености. За разлику од аксиоме избора, ове алтернативе обично нису исказане као аксиоме математике, већ само као принципи у теорији скупова, са интересантним последицама.
Исказ Функција избора је функција -{f}-, дефинисана на колекцији -{X}- непразних скупова, таква да за сваки скуп -{s}- из -{X}-, -{f(s)}- је елемент из -{s}-. Помоћу овог концепта, аксиома може да се искаже на следећи начин: За сваки скуп непразних скупова, -{X}-, постоји функција избора -{f}-, дефинисана на -{X}-.
Стога, негација аксиоме гласи да постоји скуп непразних подскупова који нема функцију избора.
Свака функција избора над колекцијом -{X}- непразних скупова се може посматрати као (или идентификовати са) елементом Декартовог производа скупова из -{X}-. Ово доводи до исказа који је еквивалентан аксиоми избора: Произвољан Декартов производ непразних скупова је непразан.
Варијанте Постоје многе варијанте других еквивалентних исказа аксиоме избора. Они су еквивалентни у смислу да, у присуству осталих основних аксиома теорије скупова, они имплицирају аксиому избора, и аксиома избора имплицира њих.
Једна варијанта избегава коришћење функције избора, заменивши сваку функцију избора својим опсегом. Ако је дат било који скуп -{X}-, у пару дисјунктних непразних скупова, постоји најмање један скуп -{C}- који садржи тачно по један заједнички елемент са са сваким од скупова из -{X}-.
Још једна еквивалентна аксиома посматра само колекције -{X}- које су у бити партитивни скупови других скупова: За сваки скуп -{A}-, партитивни скуп од -{A}- (минус празан скуп) има функцију избора.
Неки аутори који користе ову формулацију често говоре о функцији избора над -{A}-, али треба имати у виду да је ово мало другачији појам од појма функције избора. Њен домен је партитивни скуп од -{A}- (минус празан скуп), па стога има смисла за сваки скуп -{A}-, док код дефиниција у остатку овог чланка, домен функције избора над колекцијом скупова је та колекција, па зато има смисла само за скупове скупова. Са овим алтернативним појмом функције избора, аксиома избора се може краће записати као Сваки скуп има функцију избора.. Dover, 1972. што је еквивалентно са За сваки скуп -{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}-) показује како да се изведе конструктивно неприхватљиви принцип искључења трећег, или његову ограничену форму, у конструктивној теорији скупова из претпоставке аксиоме избора.
Још један аргумент против аксиоме избора је тај што она имплицира постојање контраинтуитивних објеката. Један пример овога је парадокс Банаха-Тарског, који тврди да је могуће декомпоновати ("раставити, исећи") тродимензиону једноделну лопту у коначно много делова, и коришћењем само ротација и транслација, преуредити ове делове тако да дају две једноделне лопте од којих је свака запремине једнаке почетној од које су настале. Делови у овој декомпозицији, конструисани коришћењем аксиоме избора, су екстремно компликовани.
Упркос овим аргументима, већина математичара прихвата аксиому избора као валидан принцип за доказивање нових резултата у математици.
Многе теореме је могуће доказати без коришћења било аксиоме избора, било њене негације; ово је уобичајено у конструктивној математици. Такви искази ће бити истинити у сваком моделу Зермело-Френкел теорије скупова (ЗФ), независно од истинитости или неистинитоси аксиоме избора у том појединачном моделу. Ограничење на ЗФ чини сваку тврдњу која се ослања било на аксиому избора било на њену негацију, недоказивом. На пример, парадокс Банаха-Тарског није могуће ни доказати, нити оповргнути коришћењем саме ЗФ: немогуће је да се конструише тражена декомпозиција лопте у ЗФ, али је такође немогуће да се покаже да таква декомпозиција не постоји. Слично, сви доле излистани искази који у свом доказу захтевају аксиому избора, или неку њену слабију верзију, су недоказиви у ЗФ, али како је сваки од њих доказив у ЗФ плус аксиома избора, постоје модели ЗФ у којима је сваки исказ тачан. Искази као што је парадокс Банаха-Тарског могу да се преформулишу у условне исказе, на пример Ако аксиома избора важи, декомпозиција из парадокса Банаха-Тарског постоји. Такви условни искази су доказиви у ЗФ када су почетни искази доказиви у ЗФ плус аксиома избора.
Независност По раду Курта Гедела и Пола Коена, аксиома избора је логички независна од осталих аксиома Зермело-Френкел теорије скупова (ЗФ). Ово значи да ни она, нити њена негација не могу да буду доказане унутар ЗФ, ако је ЗФ конзистентна. Последично, ако је ЗФ конзистентна, онда је и ЗФ плус аксиома избора конзистентна, као и ЗФ плус негација аксиоме избора. Значи одлука да ли је или није прикладно да се у доказима користи аксиома избора не може да буде донета позивањем на остале аксиоме теорије скупова. Ова одлука се мора донети на некој другој основи.
Један аргумент у прилог коришћења аксиоме избора јесте то што је она згодна: њено коришћење не може да шкоди (не може да доведе до контрадикције), а омогућава да се докажу неке ствари кое иначе не би било могуће доказати. Теореме као што су: сваки идеал у прстену је садржан у максималном идеалу, сваки векторски простор има базу и сваки производ компактних простора је компактан, можда не би важиле за математичке објекте велике кардиналности.
Резултат доказа независности такође показује да широка класа математичких исказа, укључујући све исказе који се могу изрећи језиком Пеанове аритметике, су доказиви у ЗФ ако и само ако су доказиви у ЗФ са аксиомом избора. Искази у овој класи укључују исказ да П = НП, Риманову хипотезу, и многе друге нерешене математичке проблеме. Када се покуша решавање проблема из ове класе, нема разлике да ли се претпоставља ЗФ или ЗФИ (Зермело-Френкел са аксиомом избора), ако је поставља само питање постојања доказа. Међутим, могуће је да постоји краћи доказ који следи из ЗФИ него из ЗФ.