Axiom Of Choice

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Toto je soubor v archivech Stanfordské encyklopedie filozofie.

Axiom of Choice

První publikované Út 8. ledna 2008; věcná revize St 9. ledna 2008

Princip teorie množin známý jako Axiom of Choice byl označován za „pravděpodobně nejzajímavější a navzdory jeho pozdnímu vzhledu, nejvíce diskutovaným axiomem matematiky, druhý za Euclidovým axiomem paralel, který byl představen více než dva tisíce před lety “(Fraenkel, Bar-Hillel & Levy 1973, §II.4). Fulsomeness tohoto popisu by mohla vést ty neobeznámené s axiom očekávat, že to bude tak překvapivé jako, řekněme, princip konstantnosti rychlosti světla nebo Heisenbergův princip nejistoty. Ale ve skutečnosti se Axiom of Choice, jak je obvykle uvedeno, zdá být humdrum, dokonce zřejmý. Jde o nic jiného než o tvrzení, že vzhledem k jakékoli sbírce vzájemně nesouvisejících neprázdných sadje možné sestavit novou sadu - transverzální nebo výběrovou - obsahující přesně jeden prvek z každého člena dané kolekce. Nicméně tento zdánlivě neškodný princip má dalekosáhlé matematické důsledky - mnohé z nich jsou nepostradatelné, některé překvapivé - a při diskusích o základech matematiky se objevil významně. To (nebo jeho ekvivalenty) bylo zaměstnáno v nespočetných matematických dokumentech a řada monografií byla věnována výhradně tomuto.a řada monografií se jí věnovala výhradně.a řada monografií se jí věnovala výhradně.

• 1. Původy a chronologie axiomu volby
• 2. Nezávislost a konzistence zvoleného axiomu
• 3. Maximální principy a Zornova lemma
• 4. Matematické aplikace axiomu volby

• 5. Axiom of Choice and Logic

  Doplňkový dokument: Axiom volby a teorie typů

• Bibliografie
• Další internetové zdroje
• Související záznamy

1. Původy a chronologie axiomu volby

V roce 1904 Ernst Zermelo formuloval Axiom of Choice (v tomto článku zkráceně AC), co se týče toho, co nazýval krytím (Zermelo 1904). Začíná libovolnou množinou M a pomocí symbolu M 'označuje libovolnou neprázdnou podmnožinu M, jejíž sbírku označuje M. Pokračuje:

Představte si, že s každou podmnožinou M 'je spojen libovolný prvek m ₁ ', který se vyskytuje v samotném M ' nechť m ₁ 'se nazývá „rozlišovací“prvek M'. Tím se získá „pokrývka“g množiny M určitými prvky množiny M. Počet těchto krytí se rovná součinu součinů všech podmnožin M '] a rozhodně se liší od 0.

Poslední věta této nabídky - která tvrdí, že ve skutečnosti vždy existuje krytí pro shromažďování neprázdných podmnožin jakéhokoli (neprázdného) souboru - je první formulace Zermeloho Axiom of Choice ^[1]. To se nyní obvykle uvádí z hlediska volebních funkcí: zde je výběrovou funkcí v kolekci H neprázdných množin mapa f s doménou H tak, že f (X) ∈ X pro každé X ∈ H.

Jako velmi jednoduchý příklad nechť H je kolekce neprázdných podmnožin {0, 1}, tj. H = {{0}, {1}, {0,1}}. Potom má H dvě odlišné výběrové funkce f ₁ af ₂ dané:

f 1 ({0})	=	0
f 1 ({1})	=	1
f 1 ({0, 1})	=	0

f 2 ({0})	=	0
f 2 ({1})	=	1
f 2 ({0, 1})	=	1

Zajímavější příklad funkce výběru je poskytnut tím, že H je množina (neuspořádaných) párů reálných čísel a funkce, která je přiřazením každého páru jeho nejmenšímu prvku. Funkce jiné volby se získá přiřazením každého páru jeho největšímu prvku. Je zřejmé, že na H lze definovat mnohem více funkcí výběru.

Zermeloova první formulace AC uvádí:

AC1:

Jakákoli kolekce neprázdných sad má funkci výběru.

AC1 lze přeformulovat pomocí indexovaných nebo proměnných sad. Indexovaná kolekce množin A = {A _i  : i ∈ I} může být koncipována jako proměnná množina, jako množina, která se mění v množině indexů I. Každé _Ai je pak „hodnotou“sady proměnných A ve fázi i. Volba funkce na A je mapa f: I → ∪ _{i ∈ I} A _i tak, že f (i) ∈ A _i pro všechny i ∈ I. Výběrová funkce na A je tedy „výběrem“prvku proměnné množiny A v každé fázi; jinými slovy, výběrová funkce na A je variabilní prvek A. AC1 je pak ekvivalentní tvrzení

AC2:

Každá indexovaná kolekce sad má funkci výběru.

Neformálně vzato, AC2 představuje tvrzení, že proměnná sada s prvkem v každé fázi má variabilní prvek.

AC1 lze také přeformulovat z hlediska vztahů, viz.

AC3:

Pro jakýkoli vztah R mezi množinami A, B, ∀ x ∈ A ∃ y ∈ B [R (x, y)] ⇒ ∃ f [f: A → B & ∀ x ∈ A [R (x, fx)].

Jinými slovy, každá relace obsahuje funkci mající stejnou doménu.

Nakonec se AC3 snadno ukazuje jako ekvivalent (v obvyklých teoriích) k: ^[2]

AC4:

Každá pomocná funkce má pravý inverzní tvar.

V 1908 papíru Zermelo představil modifikovanou formu AC. Nazvěme transverzální (nebo výběrovou množinu) pro skupinu množin H libovolná podskupina T ⊆ ∪H, pro kterou má každá průsečík T ∩ X pro X ∈ H přesně jeden prvek. Jako velmi jednoduchý příklad nechť H = {{0}, {1}, {2, 3}}. Potom má H dva transverzály {0, 1, 2} a {0, 1, 3}. Více podstatný příklad je poskytnut tím, že necháme H být soubor všech linií v euklidovské rovině rovnoběžný s x-osou. Pak množina T bodů na y -axi je příčná pro H.

Zermeloovo druhé (1908) formulace AC tedy uvádí, že pokud jde o transverzály, je tvrzení, že každá rodina vzájemně nesouvislých neprázdných množin má transverzální. ^[3]

Zermelo tvrdí, že „čistě objektivní charakter“této zásady „je okamžitě zřejmý“. V tomto tvrzení chtěl Zermelo zdůraznit skutečnost, že v této podobě zásada nevyvolává žádnou možnost volby „volby“. Může se také stát, že Zermelo mělo na mysli následující „kombinatorické“odůvodnění zásady. Vzhledem k tomu, že skupina H vzájemně nesouvislých neprázdných množin, volejte podmnožinu S ⊆ ∪H selektor pro H, pokud S ∩ X ≠ ∅ pro všechny X ∈ H. Jasně existují selektory pro H; ItselfH sám je příkladem. Nyní si můžeme představit, že vybereme selektor S pro H a „zředíme“každou křižovatku S S X pro X ∈ H, dokud nebude obsahovat pouze jeden prvek. Výsledkem je příčný pro H. Tento argument, vhodně upřesněný, dává přesnou derivaci AC v této formulaci z množiny teoretických principů známých jako Zorn 's lemma (viz níže).

Nazvěme Zermeloovu formulaci z roku 1908 kombinační axiom volby:

CAC:

Každá sbírka vzájemně nesouvisejících neprázdných množin má průřez.

Je třeba poznamenat, že AC1 a CAC pro konečné kolekce sad jsou prokazatelné (indukcí) v obvyklých teoriích množin. Ale v případě nekonečné sbírky, i když je každý z jejích členů konečný, je otázka existence výběrové funkce nebo průřezu problematická ^[4]. Například, jak již bylo zmíněno, je snadné přijít s výběrovou funkcí pro sbírku párů reálných čísel (jednoduše zvolit menší prvek z každého páru). V žádném případě však není zřejmé, jak vytvořit výběrovou funkci pro shromažďování dvojic libovolných množin reálných čísel.

Původním záměrem Zermeloho při zavádění AC bylo stanovit ústřední princip Cantorovy teorie množin, konkrétně, že každá sada připouští řádné uspořádání, a tak lze také přiřadit kardinální číslo. Zermeloovo zavedení axiomu z roku 1904, jakož i jeho použití, vyvolalo značnou kritiku ze strany dnešních matematiků. Hlavní vznesená námitka byla proti tomu, co někteří viděli jako svůj vysoce nekonstruktivní, dokonce idealistický charakter: zatímco axiom tvrdí, že je možné provést libovolný počet „snad i nespočetných“libovolných „rozhodnutí“, nedává to žádný náznak o tom, jak se tyto skutečně mají uskutečnit, o tom, jak mají být definovány, jinak řečeno, výběrové funkce. To bylo obzvláště nevhodné pro matematiky „konstruktivního“ohnutí, jako jsou tzv. Francouzští empirici Baire,Borel a Lebesgue, pro které by bylo možné tvrdit, že matematický objekt existuje, pouze pokud jej lze definovat tak, aby byl jedinečně charakterizován. Zermelo odpověď na jeho kritiky přišel ve formě ve dvou dokumentech v roce 1908. V prvním z nich, jak bylo uvedeno výše, přeformuloval, ve kterém přeformuloval AC z hlediska transverzálních; ve druhém (1908a) výslovně uvedl další předpoklady potřebné k tomu, aby prokázal svůj důkaz řádné věty. Tyto předpoklady představovaly první explicitní představení systému axiomů pro teorii množin.on přeformuloval, ve kterém přeformuloval AC z hlediska transverzálů; ve druhém (1908a) výslovně uvedl další předpoklady potřebné k tomu, aby prokázal svůj důkaz řádné věty. Tyto předpoklady představovaly první explicitní představení systému axiomů pro teorii množin.on přeformuloval, ve kterém přeformuloval AC z hlediska transverzálů; ve druhém (1908a) výslovně uvedl další předpoklady potřebné k tomu, aby prokázal svůj důkaz řádné věty. Tyto předpoklady představovaly první explicitní představení systému axiomů pro teorii množin.

Jak debata týkající se Axiom of Choice drnula dál, vyšlo najevo, že důkazy řady významných matematických teorémů ji zásadně využívají, což vede mnoho matematiků k tomu, aby s nimi zacházeli jako s nezbytným nástrojem jejich obchodu. Například Hilbert přišel k AC jako k základnímu principu matematiky ^[5] a použil jej při obraně klasických matematických úvah proti útokům intuicionistů. Opravdu jeho ε-operátoři jsou v podstatě jen výběrové funkce (viz položka na epsilonském počtu).

Ačkoli užitečnost střídavého proudu rychle vyjasnila, zůstaly pochybnosti o jeho správnosti. Tyto pochybnosti byly posíleny skutečností, že to mělo jisté nápadně kontraintuitivní důsledky. Nejpozoruhodnější z nich byly Banachovy a Tarského paradoxní rozklady koule (Banach a Tarski 1924): jakákoli pevná koule může být rozdělena na konečně mnoho kusů, které lze znovu sestavit do dvou pevných koulí stejné velikosti; a jakákoli pevná koule může být rozdělena na konečně mnoho kusů takovým způsobem, aby bylo možné je znovu sestavit do pevné koule libovolné velikosti. (Viz Wagon 1993.)

Teprve v polovině třicátých let minulého století byla otázka spolehlivosti AC konečně položena na důkaz Kurta Gödele o její konzistentnosti s ostatními axiomy teorie množin.

Zde je krátká chronologie AC: ^[6]

1904/1908	Zermelo zavádí axiomy teorie množin, výslovně formuluje AC a používá jej k prokázání řádné věty, čímž vyvolává bouři kontroverze.
1904	Russell uznává AC jako multiplikativní axiom: součin libovolných nenulových kardinálních čísel je nenulový.
1914	Hausdorff odvozuje od AC existenci neměřitelných souborů v „paradoxní“podobě, že ½ koule je shodná s 1/3 (Hausdorff 1914).
1922	Fraenkel zavádí „permutační metodu“k vytvoření nezávislosti AC od systému teorie množin s atomy (Fraenkel 1922).
1924	Na základě práce Hausdorffa, Banacha a Tarského pocházejí z AC jejich paradoxní rozklad sféry.
1926	Hilbert zavádí do své teorie důkazů „transfinit“nebo „epsilon“axiom jako verzi AC. (Hilbert 1926).
1936	Lindenbaum a Mostowski rozšiřují a zdokonalují Fraenkelovu permutační metodu a dokazují nezávislost různých prohlášení teorie množin slabší než AC. (Lindenbaum a Tarski 1938)
1935–38	Gödel stanoví relativní konzistenci AC s axiomy teorie množin (Gödel 1938, 1939, 1940).
Padesátá léta	Mendelson, Shoenfield a Specker, pracující samostatně, používají permutační metodu k vytvoření nezávislosti různých forem AC od systému teorie množin bez atomů, ale také postrádající axiom nadace (Mendelson 1956, 1958, Shoenfield 1955, Specker 1957).
1963	Paul Cohen prokazuje nezávislost AC od standardních axiomů teorie množin (Cohen 1963, 1963a, 1964).

2. Nezávislost a konzistence zvoleného axiomu

Jak bylo uvedeno výše, v roce 1922 Fraenkel prokázala nezávislost AC od systému teorie množin obsahujícího „atomy“. Atomem se zde rozumí čistý jednotlivec, tj. Entita bez členů a přesto odlišná od prázdné sady (takže a fortiori atom nemůže být množina). V systému teorie množin s atomy se předpokládá, že jeden dostane nekonečnou množinu atomů A. Jeden může stavět vesmír V (A) množin přes A tím, že začíná na A, přidává všechny podmnožiny A, sousedí všechny podmnožiny výsledku atd., A iteruje transfinitely. V (A) je pak modelem teorie množin s atomy. Fraenkelova metoda pro prokázání nezávislosti AC je pozorování, že vzhledem k tomu, že atomy nelze stanovit, teoreticky rozlišit,každá permutace množiny A atomů indukuje permutaci struktury - automorfismus - vesmíru V (A) sad vytvořených z A. Tato myšlenka může být použita k vytvoření jiného modelu Sym (V) teorie množin - permutačního nebo symetrického modelu -, ve kterém sada vzájemně nesouvislých párů prvků A nemá žádnou výběrovou funkci.

Nyní předpokládejme, že jsme dostali skupinu G automorfismů A. Řekněme, že automorfismus π z A opravuje prvek x V (A), pokud π (x) = x. Je zřejmé, že pokud π ∈ G opravuje každý prvek A, opravuje také každý prvek V (A). Nyní se může stát, že pro určité prvky x ∈ V (A) postačuje fixace prvků podskupiny A jakoukoli π ∈ G pro opravu x. Proto jsme vedeni k definování podpory pro x, aby byla podskupinou X A tak, že kdykoli π ∈ G opraví každý člen X, také opraví x. Členové V (A), kteří mají konečnou podporu, se nazývají symetrické.

Dále definujeme vesmír Sym (V), který se skládá z dědičně symetrických členů V (A), tj. Těch x ∈ V (A) tak, že x, prvky x, prvky x, atd., jsou všechny symetrické. Sym (V) je také modelem teorie množin se sadou atomů A a π indukuje automorfismus Sym (V).

Nyní předpokládejme, že A bude rozdělena do (nutně nekonečné) vzájemně nesouvislé množiny P párů. Vezměte G jako skupinu permutací A, které fixují všechny páry v P. Pak P ∈ Sym (V); nyní lze ukázat, že Sym (V) neobsahuje na P žádnou funkci výběru. Předpokládejme, že f byly volitelnou funkcí na P a f ∈ Sym (V). Potom má f konečnou podporu, která může mít podobu {a ₁, …, a _n, b ₁, …, b _n } s každou dvojicí {a _i, b _i } ∈ P. Protože P je nekonečný, můžeme vybrat pár {c, d} = U od P odlišný od všech {a _i, b _i }. Nyní definujeme π ∈ G tak, aby π fixovala každého a _i a b_i a výměny c a d. Pak π také opraví f. Protože f mělo být volitelnou funkcí na P a U ∈ P, musíme mít f (U) ∈ U, tj. F (U) = c nebo f (U) = d. Vzhledem k tomu, že výměny c a d znamenají, že π (f (U)) ≠ f (U). Ale protože π je automorfismus, zachovává také funkční aplikaci, takže π (f (U)) = π f (π (U)). Ale π (U) = U a π f = f, odkud π (f (U)) = f (U). Řádně jsme dospěli k rozporu, což ukazuje, že vesmír Sym (V) neobsahuje žádnou volitelnou funkci na P.

Jde o to, že pro symetrickou funkci f definovanou na P existuje konečný seznam L párů z P, přičemž fixace všech prvků, které stačí k fixaci f, a tedy i všech hodnot f. Nyní, pro jakýkoli pár U v P, ale ne v L, lze vždy najít permutaci π, která opravuje všechny prvky párů v L, ale neopravuje členy U. Protože π musí stanovit hodnotu f na U, nemůže tato hodnota ležet v U. Proto f nemůže „vybrat“prvek U, takže a fortiori f nemůže být volitelnou funkcí na P.

Tento argument ukazuje, že kolekce sad atomů nemusí mít nutně výběrové funkce, ale nedokáže prokázat stejný fakt pro „obvyklé“sady matematiky, například pro množinu reálných čísel. To muselo počkat až do roku 1963, kdy Paul Cohen ukázal, že je v souladu se standardními axiomy teorie množin (které vylučují existenci atomů) předpokládat, že početná sbírka dvojic množin reálných čísel nemá volitelnou funkci. Jádro Cohenovy metody dokazování - slavená metoda násilí - byla mnohem obecnější než jakákoli předchozí technika; nicméně jeho důkaz nezávislosti také nezbytně používal permutaci a symetrii v podstatě ve formě, ve které je Fraenkel původně použil.

Gödelův důkaz relativní konzistence AC s axiomy teorie množin (viz záznam o Kurtu Gödelovi) spočívá na úplně jiné myšlence: na definovatelnosti. Zavedl novou hierarchii množin - konstruktivní hierarchii - analogicky s kumulativní hierarchií typů. Připomínáme, že ten je definován následující rekurzí na ordinálech, kde P (X) je mocnina X, α je ordinál a λ je limit ordinál::

V 0	=	∅
V a + 1	=	P (V α)
V λ	=	∪ α <λ V α

Konstruktivní hierarchie je definována podobnou rekurzí na ordinálech, kde Def (X) je množina všech podmnožin X, které jsou ve struktuře definovány v prvním řádu (X, ∈, (x) _{x ∈ X}): ^[7]

L 0	=	∅
L a + 1	=	Def (L α)
L λ	=	∪ α <λ L α

_{Konstruovatelný} vesmír je třída L = ∪ _α∪Ord L _α; členy L jsou konstruktivní sady. Gödel ukázal, že (za předpokladu axiomů Zermelo-Fraenkelovy teorie množin ZF) je struktura (L, ∈) modelem ZF a také AC, jakož i zobecněné hypotézy kontinua). Následuje relativní konzistence AC s ZF.

Gödel (1964) (a nezávisle Myhill a Scott 1971, Takeuti 1963 a Post 1951) také poznamenal, že jednodušší důkaz relativní konzistence AC lze formulovat z hlediska ordinální definovatelnosti. Pokud píšeme D (X) pro množinu všech podmnožin X, které jsou ve struktuře (X, ∈) definovatelné v prvním řádu, pak je třída OD ordinálně definovatelných množin definována jako unie ∪ _α∈Ord D (V _a). Třída HOD dědičně pořadových definovatelných množin sestává ze všech sad, pro které a, členové a, členové členů a, … atd., Jsou všichni ordinální definovatelní. Pak lze ukázat, že struktura (HOD, ∈) je modelem ZF + AC, ze kterého opět vychází relativní konzistence AC s ZF.^[8]

3. Maximální principy a Zornova lemma

Axiom of Choice je úzce spojen se skupinou matematických propozic, souhrnně známých jako maximální principy. Obecně řečeno, tato tvrzení tvrdí, že určité podmínky jsou dostatečné k tomu, aby zajistily, že částečně uspořádaná množina obsahuje alespoň jeden maximální prvek, tj. Prvek takový, že vzhledem k danému částečnému uspořádání jej žádný prvek přísně nepřekročí.

Abychom viděli souvislost mezi myšlenkou maximálního prvku a AC, vraťme se k jeho formulaci AC2 z hlediska indexovaných množin. Předpokládejme tedy, že jsme dostali indexovanou rodinu neprázdných množin A = {A _i  : i ∈ I}. Definujme funkci potenciální volby na A jako funkci f, jejíž doména je podmnožinou I tak, že f (i) ∈ A _ipro všechny i ∈ J. (Zde je využití potenciálu kvalifikátoru naznačeno skutečností, že doména je podmnožinou I; vzpomeňte si, že výběrová funkce f na A má stejné vlastnosti jako to, co nyní nazýváme potenciální výběrové funkce, kromě toho, že doména f je požadováno, aby to bylo všechno I, ne jen podmnožina.) Sada P potenciálních volebních funkcí na A může být částečně uspořádána zahrnutím: souhlasíme s tím, že pro potenciální výběrové funkce f, g ∈ P je vztah f ≤ g zadán že doména f je zahrnuta v doméně g a hodnota f v prvku její domény se shoduje s hodnotou g. Nyní je snadno vidět, že maximální prvky P s ohledem na částečné uspořádání ≤ jsou přesně výběrové funkce na A.

Zornova Lemma je nejznámějším principem zajišťujícím existenci takových maximálních prvků. Abychom to řekli, potřebujeme několik definic. Vzhledem k částečně uspořádané sadě (P, ≤) je horní mez pro podmnožinu X P prvkem a ∈ P, pro který x ≤ a pro každé x ∈ X; maximální prvek P pak může být definován jako prvek a, pro který se sada horních mezí {a} shoduje s {a}, což v podstatě znamená, že žádný prvek P není přísně větší než a. Řetězec v (P, ≤) je podmnožinou C P tak, že pro libovolné x, y ∈ P buď x ≤ y nebo y ≤ x. P je považován za induktivní, pokud má každý řetězec v P horní hranici. Nyní Zorn's Lemma tvrdí:

Zorn's Lemma (ZL):

Každá neprázdná induktivní částečně uspořádaná sada má maximální prvek.

Proč je Zornova Lemma věrohodná? Zde je neformální argument. Vzhledem k neprázdné induktivní částečně uspořádané sadě (P, ≤) vyberte libovolný prvek p ₀ z P. Pokud je p ₀ maximální, zastavte se. Jinak vyberte prvek p ₁ > p ₀; pokud je p ₁ maximální, zastavte se. Jinak vyberte prvek p ₂ > p ₁ a postup opakujte. Pokud žádný z prvků, p ₀ <p ₁ <p ₂ <… <p _n <… je maximální, p _i tvoří řetězec, který, protože P je induktivní, má horní mez q ₀. Pokud q ₀je maximální, zastavte se. Jinak lze postup opakovat s q ₀ <q ₁,… a poté iterovat. Tento proces musí nakonec skončit, protože v opačném případě by spojení takto vytvořených řetězců představovalo správnou třídu, což by samo o sobě znamenalo, že by P byla sama o sobě v rozporu s předpokladem. Bod, ve kterém se proces ukončí, poskytne maximální prvek P.

Tento argument, vhodně rigorized, poskytuje důkaz, ^[9], ve ZL z AC1 v teorie množin Zermelo-Fraenkelův: v tomto důkazu AC1 se používá pro „pick“prvky uvedené v neformální argumentu.

Další verzi Zornovy Lemmy lze uvést ve sbírkách sad. Když vezmeme v úvahu sbírku H sad, nazvěme hnízdo v H jakoukoli podskupinu N H tak, že pro každou dvojici členů N je jedna zahrnuta v druhé. ^[10] Volejte H silně induktivní, pokud je spojení jakéhokoli hnízda v H členem H. Lemmy Lemmy H. Zornova, pak lze ekvivalentně přepracovat jako tvrzení, že jakákoli neprázdná silně induktivní sbírka H má maximální člen, tj. Člen správně zahrnut do žádného člena H. To může být zase formulováno ve dvojí formě. Říkejte rodině sad silně reduktivní, pokud je uzavřena pod křižovatkami hnízd. Pak každá neprázdná silně reduktivní rodina sad má minimální prvek, to znamená, že člen řádně neobsahuje žádný člen rodiny.

AC2 je nyní v této alternativní formě snadno odvozeno od Zornovy Lemmy. Pro množinu P potenciálních volebních funkcí na indexované rodině množin A je zjevně neprázdná a snadno se ukazuje, že je silně induktivní; takže Zornovo lemma dává na A. existenci výběrové funkce.

CAC lze odvodit od ZL způsobem, který odráží výše uvedené „kombinatorické“odůvodnění CAC. Předpokládejme tedy, že jsme dostali rodinu H vzájemně nesouvislých neprázdných množin; zavolej podmnožinu S ⊆ ∪H vzorkování pro H, pokud pro kterékoli X ∈ H je buď X ⊆ S nebo S ∩ X neprázdné a konečné. Minimální vzorkování jsou přesně příčné pro H; ^[11] a odběr vzorků T je zjevně neprázdný, protože obsahuje ∪H. Takže jestliže to může být ukázáno, že T je silně reduktivní, ^[12] Zornova lemma dá minimální prvek T a tak příčný pro H. Silnou reduktivitu T můžeme vidět takto: předpokládejme, že {S _i  : i ∈ I} je hnízdo vzorků; nechť S = ∩ _{i ∈ I} S_i. Musíme ukázat, že S je sama o sobě vzorkem; za tímto účelem nechť X ∈ H a předpokládejme ¬ (X ⊆ S). Pak existuje i ∈ I, pro které ¬ (X ⊆ S _i); protože S _i je vzorkování, S _i ∩ X je konečný (JAA: navrhované přidání: "a") neprázdné, řekněme S _i ∩ X = {x ₁, …, x _n }. Je zřejmé, že S ∩ X je pak konečný; předpokládejme kvůli rozporu, že S ∩ X = ∅. Pak pro každé k = 1,…, n existuje i _k ∈ I, pro které ¬ (x _k ∈ S _{i k). Z toho vyplývá, že ¬ (S i ⊆ S i k) pro k = 1,…, n. Takže od S itvoří řetězec, každý s i k je podmnožinou S i. Nechť Sj je nejméně S i 1,…, S i k; pak S j ⊆ S i. Ale protože ¬ (x k ∈ S j), pro k = 1,…, n, nyní vyplývá, že S j ∩ X = ∅, což je v rozporu se skutečností, že Sj je vzorkování. Proto S ∩ X ≠ ∅; a S je vzorek, jak je nárokováno.}

Všimli jsme si, že zatímco Zornovo lemma a Axiom of Choice jsou teoreticky rovnocenné, je mnohem obtížnější odvodit bývalého z druhého než naopak.

Zde je stručná chronologie maximálních principů.

1909	Hausdorff představuje první explicitní formulaci maximálního principu a vychází z AC (Hausdorff 1909) (
1914	Hausdorffova Grundzüge der Mengenlehre (jedna z prvních knih o teorii množin a obecné topologii) obsahuje několik maximálních principů.
1922	Kuratowski formuluje a používá několik maximálních principů, jak se vyhnout použití transfinitálních ordinálů (Kuratowski 1922).
1926–28	Bochner a další nezávisle zavádějí maximální principy (Bochner 1928, Moore 1932).
1935	Max Zorn, zjevně neznalý s předchozími formulacemi maximálních principů, publikuje (Zorn 1935) jeho definitivní verzi později, aby se stal oslavovaným jako jeho lemma (ZL). ZL byl poprvé vytvořen v Hamburku v roce 1933, kde jej Chevalley a Artin rychle „přijali“. Zdá se, že to byl Artin, který nejprve uznal, že ZL by přineslo AC, takže tyto dva jsou rovnocenné (nad zbývajícími axiomy teorie množin). Zorn považoval jeho princip méně za teorém než za axiom - doufal, že nahradí těžkopádné aplikace v algebře indukce a řádného uspořádání transfinitů, které algebraisté ve škole Noether přišli považovat za „transcendentální“zařízení.
1939–40	Teichmüller, Bourbaki a Tukey nezávisle přeformulují ZL z hlediska „vlastností konečného charakteru“(Bourbaki 1939, Teichmuller 1939, Tukey 1940).

4. Matematické aplikace axiomu volby

Axiom of Choice má řadu aplikací v matematice, z nichž řada se k nim formálně shoduje ^[13]. Historicky nejdůležitější aplikace byla první, a to:

Věta o řádném objednávání (Zermelo 1904, 1908). Každá sada může být dobře objednána

Po Zermelo publikoval jeho 1904 důkaz o dobře-objednávat teorém od AC, to bylo rychle vidět, že tito dva jsou ekvivalentní.

Další časný ekvivalent AC je

Multiplikativní axiom (Russell 1906). Produkt jakékoli sady nenulových kardinálních čísel je nenulový

Mezi první aplikace AC patří:

• Každá nekonečná množina má počítatelnou podmnožinu. Tento princip, opět slabší než AC, nemůže být dokázán bez něj v kontextu zbývajících axiomů teorie množin.
• Každé nekonečné kardinální číslo se rovná jeho čtverci. Toto bylo prokázané ekvivalentní k AC v Tarski 1924.
• Každý vektorový prostor má základ (iniciovaný Hamelem 1905). To se ukázalo jako ekvivalent AC v Blass 1984.
• Každé pole má algebraický uzávěr (Steinitz 1910). Toto tvrzení je slabší než AC, ve skutečnosti je důsledkem (slabší) věty o kompaktnosti pro logiku prvního řádu (viz níže).
• Existuje Lebesgueův neměřitelný soubor reálných čísel (Vitali 1905). Ukázalo se to mnohem později jako důsledek BPI (viz níže), a proto slabší než AC. Solovay (1970) založil nezávislost na zbývajících axiomech teorie množin.

Významným „folklórním“ekvivalentem AC je

• Set-teoretický distribuční zákon. Pro libovolnou dvojitě indexovanou rodinu množin {M _{i, j}  : i ∈ I, j ∈ J}, a kde J ^I je sada všech funkcí s doménou I, které nabývají hodnot v J:

  ∩ _{i ∈ I}  ∪ _{j ∈ J}   M _{i, j} = ∪ _{f ∈ J ^I}  ∩ _{i ∈ I}   M _{i, f (i)}

Hodně studovaným zvláštním případem AC je

Princip závislých voleb (Bernays 1942, Tarski 1948). Pro jakýkoli neprázdný vztah R na množině A, pro kterou je rozsah (R) ⊆ doména (R), existuje funkce f: ω → A taková, že pro všechny n ∈ω, R (f (n), f (n +) 1)). Tento princip, i když (mnohem) slabší než AC, nemůže být dokázán bez něj v kontextu zbývajících axiomů teorie množin

Matematické ekvivalenty AC zahrnují:

• Tychonovova věta (1930): produkt kompaktních topologických prostorů je kompaktní. Toto bylo dokázané ekvivalentní k AC v Kelley 1950. Ale pro kompaktní Hausdorff prostory to je ekvivalentní k BPI (vidět dolů), a proto slabší než AC
• Löwenheim-Skolem-Tarski věta (Löwenheim 1915, Skolem 1920, Tarski a Vaught 1957): věta prvního řádu mající model kardinality κ má také model jakékoli nekonečné kardinality μ tak, že μ ≤ κ. Tarski to dokázal jako ekvivalent AC.
• Kerin-Milmanova věta: jednotková koule B duálu skutečného normovaného lineárního prostoru má extrémní bod, tj. Ten, který není vnitřním bodem žádného úseku v B. Toto bylo dokázané ekvivalentní k AC v Bell a Fremlin 1972a. Tam je ukázáno, že vzhledem k jakékoli indexované rodině A neprázdných množin existuje přirozený bijekt mezi výběrovými funkcemi na A a krajními body jednotkové koule dvojice určitého skutečného normovaného lineárního prostoru konstruovaného z A.
• Každá distribuční mříž má maximální ideál. To se ukázalo jako rovnocenné s AC v Klimovském 1958 a pro mříže sad v Bell a Fremlin 1972.
• Každý komutativní prsten s identitou má maximální ideál. Hodges 1979 to dokázal jako AC.

Existuje několik matematických důsledků AC, o kterých je známo, že jsou slabší ^[14], než zejména:

• Boolean Prime Ideální věta (BPI): každá booleovská algebra má maximální (nebo prvotřídní) ideál. Ukázalo se, že to bylo slabší než AC v Halpern a Levy 1971.
• The Stone Reprezentation Theorem for Booleean algebras (Stone 1936): každá booleovská algebra je izomorfní pro pole množin. To je ekvivalent BPI, a tedy slabší než AC
• Kompaktní věta pro logiku prvního řádu (Gödel 1930, Malcev 1937, další): pokud má každá konečná podmnožina souboru vět vět prvního řádu model, pak sada má model. Ukázalo se, že v Henkin 1954 byl ekvivalent BPI, a proto slabší než AC.
• Věta o úplnosti pro logiku prvního řádu (Gödel 1930, Henkin 1954): každá konzistentní množina vět prvního řádu má model. Henkin to v roce 1954 prokázal jako ekvivalent BPI, a proto slabší než AC. Je-li mohutnost modelu stanovena správným způsobem, tvrzení se stává ekvivalentem AC.

Konečně, existuje

Sikorského rozšíření věty pro booleovské algebry (Sikorski 1949): každá úplná booleovská algebra je injektivní, tj. Pro jakoukoli booleovskou algebru A a jakoukoli úplnou booleovskou algebru B lze jakýkoli homomorfismus podalgebry A až B rozšířit na celý A

Otázka rovnocennosti tohoto s AC je jednou z mála zbývajících zajímavých otevřených otázek v této oblasti; zatímco to jasně implikuje BPI, to bylo dokázané nezávislé na BPI v Bell 1983.

Mnoho z těchto vět je diskutováno v Bell and Machover (1977).

5. Axiom of Choice and Logic

Počáteční spojení mezi AC a logikou se objevuje návratem k jeho formulaci AC3, pokud jde o vztahy, konkrétně: jakákoli binární relace obsahuje funkci se stejnou doménou. Tato verze AC je přirozeně vyjádřitelná v jazyce L druhého řádu s jednotlivými proměnnými x, y, z,… a funkčními proměnnými f, g, h,…. V L jsou binární vztahy reprezentovány vzorci φ (x, y) se dvěma volnými jednotlivými proměnnými x, y. Protějšek v L tvrzení AC3 je tedy

ACL:

∀ x ∃ y φ (x, y) → ∃ f ∀ x φ (x, fx).

Toto schéma vět je standardní logickou formou AC.

Zermeloho původní podoba Axiom of Choice, AC1, lze vyjádřit jako schéma vět v rámci vhodně posílené verze L. Proto nyní předpokládáme, že L obsahuje navíc predikátové proměnné X, Y, Z, … a funkční proměnné F, G, H,… druhého řádu. Zde může být funkční proměnná F druhého řádu použita na predikátovou proměnnou X, čímž se získá individuální termín FX. Schéma vět

AC1L:

∀ X [Φ (X) → ∃ x X (x)] → ∃ F ∀ X [Φ (X) → X (FX)]

je přímým protějškem AC1 v tomto posíleném jazyce druhého řádu. Slovy AC1L tvrdí, že pokud má každý predikát, který má určitou vlastnost Φ, instance, pak existuje funkce F na predikátech, takže pro jakýkoli predikát X vyhovující Φ je FX instancí X. Zde predikáty hrají roli sad.

Až dosud jsme mlčky předpokládali, že naše logika pozadí je obvyklou klasickou logikou. Skutečná hloubka spojení mezi střídavým proudem a logikou se však objevuje pouze tehdy, je-li na obrázek přenesena intuicionální nebo konstruktivní logika. Je pozoruhodné, že za předpokladu pouze rámce intuicionistické logiky spolu s určitými mírnými dalšími předpoklady může Axiom of Choice ukázat, že zahrnuje kardinální pravidlo klasické logiky, zákon vyloučeného středu - tvrzení, že A ∨ ¬ A pro jakoukoli nabídku A. Abychom byli přesní, pomocí pravidel intuicionistické logiky v našem rozšířeném jazyce L odvodíme ^[16] zákon vyloučeného středu z AC1L spojeného s následujícími dalšími principy:

Predikativní porozumění:

∃ X ∀ x [X (x) ↔ φ (x)], kde φ neobsahuje žádnou vázanou funkci nebo predikátové proměnné.

Rozšiřitelnost funkcí:

∀ X ∀ Y ∀ F [X ≈ Y → FX = FY], kde X ≈ Y je zkratka pro ∀ x [X (x) ↔ Y (x)], tj. X a Y jsou extenzivně ekvivalent.

Dva výrazní jednotlivci:

0 ≠ 1, kde 0 a 1 jsou individuální konstanty.

Nyní ať A je daný návrh. Pomocí prediktivního porozumění můžeme zavést predikátové konstanty U, V spolu s tvrzeními

(1)	∀ x [U (x) ↔ (A ∨ x = 0)]
	∀ x [V (x) ↔ (A ∨ x = 1)]

Nechť Φ (X) je vzorec X ≈ U ∨ X ≈ V. Potom můžeme jednoznačně tvrdit ∀ X [Φ (X) → ∃ x X (x)], takže AC1L lze vyvolat pro tvrzení ∃ F ∀ X [Φ (X) → X (FX)]. Nyní můžeme zavést funkční konstantu K spolu s tvrzením

(2)	∀ X [Φ (X) → X (KX)].

Protože evidentně můžeme tvrdit Φ (U) a Φ (V), vyplývá z (2), že můžeme uplatňovat U (KU) a V (KV), odtud také pomocí (1),

[A ∨ KU = 0] ∧ [A ∨ KV = 1].

Z distribučního zákona (který má intuiciistickou logiku) vyplývá, že můžeme tvrdit

A ∨ [KU = 0 ∧ KV = 1].

Z předpokladu, že 0 ≠ 1, vyplývá, že

(3)	A ∨ KU ≠ KV

je tvrditelný. Z bodu (1) však vyplývá, že můžeme uplatnit A → U ≈ V, a tedy také pomocí rozšíření funkcí, A → KU = KV. To vede k prosaditelnosti KU ≠ KV → ¬ A, což spolu s (3) zase dává prosaditelnost

A ∨ ¬ A,

to je zákon vyloučeného středa.

Skutečnost, že Axiom of Choice naznačuje Vyloučený střed, se na první pohled zdá být v rozporu se skutečností, že ten první je často považován za platný princip v systémech konstruktivní matematiky řízené intuicionální logikou, např. Bishopova konstruktivní analýza ^[17] a Martin -Löfova teorie konstruktivního typu ^[18], ve které není vyloučen vyloučený střed. Podle Bishopových slov: „V konstruktivní matematice existuje výběrová funkce, protože volba je implikována samotným smyslem existence.“Tak například předchůdce ∀ x ∃ y φ (x, y) ACL, vzhledem k konstruktivní konstrukci, jen znamená, že máme postup, který, aplikovaný na každé x, dává ay, pro které φ (x, y). Ale to je přesně to, co je vyjádřeno výsledným ∃ f ∀ x φ (x, fx) ACL.

K vyřešení těchto obtíží je třeba poznamenat, že při odvozování vyloučeného středa z ACL1 byly zásadně využívány zásady prediktivního porozumění a rozšiřitelnosti funkcí ^[19]. Z toho vyplývá, že v systémech konstruktivní matematiky potvrzující AC(ale nikoli vyloučený střed), musí selhat princip prediktivního porozumění nebo princip rozšiřitelnosti funkcí. I když princip prediktivního porozumění může být dán konstruktivním zdůvodněním, žádné takové zdůvodnění nemůže být poskytnuto pro princip prodloužení funkcí. Funkce na predikátech jsou dány intenzivně a splňují pouze odpovídající princip intencionality ∀ X ∀ Y ∀ F [X = Y → FX = FY]. Princip rozšiřitelnosti lze snadno učinit selháním, když vezmeme v úvahu například predikáty P: racionální bez peří a Q: lidskou bytost a funkci K na predikátech, která každému predikátu přiřadí počet slov v jeho popisu. Pak se můžeme dohodnout, že P ≈ Q, ale KP = 3 a KQ = 2.

V intuicionistické teorii množin (tj. Teorii množin založených na intuicionistickém oproti protikladu k klasické logice - to zkrátíme jako IST) a v teorii toposů platí principy prediktivního porozumění a rozšiřitelnosti funkcí (oba jsou vhodně konstruovány), takže AC implikuje Vyloučeno uprostřed. ^[20], ^[21]

Odvození vyloučeného středu z AC bylo poprvé dáno Diaconescuem (1975) v kategorii teoretických nastavení. Jeho důkaz používal v zásadě odlišné myšlenky od výše uvedeného důkazu; zejména nevyužívá principů rozšiřitelnosti, ale místo toho využívá myšlenku kvocientu objektu (nebo množiny) pomocí vztahu ekvivalence. Je poučné formulovat Diaconescu argument v IST. Za tímto účelem zavoláme podmnožinu U sady A, kterou lze oddělit, pokud existuje podmnožina V, pro kterou U ∩ V = ∅ a U ∪ V = A. Argument Diaconescu se rovná odvození z AC4 (viz výše) tvrzení, že každá podmnožina množiny je oddělitelná, ze které snadno vyplývá vyloučená středa. Tady to je.

Nejprve, u U ⊆ A, indikátor pro U (v A) je mapa g: A × 2 → 2 vyhovující

U = {x ∈ A: g (x, 0) = g (x, 1)}

Je pak snadné ukázat, že podmnožina je odpojitelná, a to pouze tehdy, má-li indikátor.

Nyní ukážeme, že pokud AC4 drží, pak každá podmnožina sady má indikátor, a proto je odpojitelná.

Pro U ⊆ A nechť R je binární vztah na A + A = A × {0} ∪ A × {1} daný

R = {((x, 0), (x, 0): x ∈ A} ∪ {((x, 1), (x, 1)): x ∈ A} ∪

{((x, 0), (x, 1): x ∈ A} ∪ {((x, 1), (x, 0): x ∈ A

Lze zkontrolovat, že R je ekvivalenční vztah. Napište r pro přirozenou mapu od A + A do kvocientu ^[22] Q (A + A) od R, který nese každý člen A + A do jeho R-ekvivalenční třídy.

Nyní použijte AC4 k získání mapy f: Q → A + A vyhovující f (X) ∈ X pro všechna X ∈ Q. Není těžké ukázat, že při psaní π ₁ pro projekci na první souřadnici,

(*)	pro n = 0, 1 a x ∈ A, π 1 (f (r (x, n)) = x;

a

(**)	x ∈ U ↔ f (r (x, 0)) = f (r (x, 1)).

Nyní definujte g: A × 2 → 2 pomocí g = π ₂

f

r, kde π ₂ je projekce na druhou souřadnici. Pak g je indikátor pro U, jak ukazují následující ekvivalence:

x ∈ U	↔	f (r (x, 0)) = f (r (x, 1)) … podle (**)
	↔	π 1 (f (r (x, 0))) = π 1 (f (r (x, 1))) ∧ π 2 (f (r (x, 0))) = π 2 (f (r (x, 1)))
	↔	π 2 (f (r (x, 0))) = π 2 (f (f (x, 1))) … pomocí (*)
	↔	g (x, 0) = g (x, 1).

Důkaz je kompletní.

Lze ukázat (Bell 2006), že každý z řady intuicionálně neplatných logických principů, včetně zákona vyloučeného středu, je ekvivalentní (v teorii intuicionální množiny) s vhodně oslabenou verzí axiomu výběru. V souladu s tím lze tyto logické zásady považovat za principy výběru.

Zde jsou sporné logické zásady:

SLEM	α ∨ ¬ α (α jakákoli věta)
Lin	(α → β) ∨ (β → α) (α, β jakékoli věty)
Kámen	¬ α ∨ ¬¬ α (α jakákoli věta)
Př	∃ x [∃ x α (x) → α (x)] (α (x) libovolná formule s maximálně x volnou)
Un	∃ x [α (x) → ∀ x α (x)] (α (x) libovolná formule s maximálně x volnou)
Dis	∀ x [α ∨ β (x)] → α ∨ ∀ x β (x) (α jakákoli věta, β (x) libovolná formule s maximálně x volnou)

Přes intuiciální logiku jsou Lin, Stone a Ex důsledky SLEM; a Un znamená Dis. Všechny tyto režimy samozřejmě vycházejí z úplného zákona vyloučeného středu, tj. SLEM pro libovolné vzorce.

V následujícím textu je prázdná množina označena 0, {0} 1 a {0, 1} 2.

Formulujeme následující principy výběru - zde X je libovolná množina, Fun (X) třída funkcí s doménou X a φ (x, y) libovolná formule jazyka teorie množin s maximálně volnými proměnnými x, y:

AC X	∀ x ∈ x ∃ y φ (x, y) → ∃ f ∈ zábava (X) ∀ x ∈ X φ (x, fx)
AC * X	∃ f ∈ Zábava (X) [∀ x ∈ X ∃ y φ (x, y) → ∀ x ∈ X φ (x, fx)]
DAC X	∀ f ∈ Zábava (X) ∃ x ∈ X φ (x, fx) → ∃ x ∈ X ∀ y φ (x, y)
DAC * X	∃ f ∈ Zábava (X) [∃ x ∈ X φ (x, fx) → ∃ x ∈ X ∀ y φ (x, y)]

První dvě z nich jsou formy AC pro X; zatímco klasicky ekvivalentní, v IST AC ^* _X znamená AC _X, ale ne naopak. Principy DAC _X a DAC ^* _X jsou dvojí formy axiomu volby pro X: klasicky jsou oba ekvivalenty AC _X a AC ^* _X, ale intuitivně DAC ^* _X implikuje DAC _X, a ne naopak.

Rovněž formulujeme slabý princip extenzivního výběru, ve kterém α (x) a β (x) jsou všechny vzorce s nejvýše proměnnou x free:

WESP:

∃ x ∈ 2 α (x) ∧ ∃ x ∈ 2 β (x) →

∃ x ∈ 2 ∃ y ∈ 2 [α (x) ∧ β (y) ∧ [∀ x ∈ 2 [α (x) ↔ β (x)] → x = y].

Tento princip, přímý důsledek zvolené axiomy, tvrdí, že pro každou dvojici instančních vlastností členů 2 mohou být instancím přiřazeny vlastnosti způsobem, který závisí pouze na jejich rozšířeních.

Každý z výše uvedených logických principů je ekvivalentní (v IST) principu volby. Ve skutečnosti:

• WesP a SLEM jsou ekvivalentní nad IST.
• AC ^* ₁ a Ex jsou ekvivalentní oproti IST.

Dále, zatímco DAC ₁ je snadno vidět jako prokazatelný v IST, máme

DAC ^* ₁ a Un jsou ekvivalentní k IST

Dále, zatímco AC ₂ je snadno dokázatelné v IST, naopak máme

• DAC ₂ a Dis jsou ekvivalentní k IST.
• V průběhu IST je DAC ^* ₂ ekvivalentem Un, a tedy také DAC ^* ₁.

Abychom poskytli výběrová schémata ekvivalentní s Linem a Stoneem, představujeme

ac ^* _X:

∃ f ∈ 2 ^X [∀ x ∈ X ∃ y ∈ 2 φ (x, y) → ∃ x ∈ X φ (x, fx)]

wac ^* _X:

∃ f ∈ 2 ^X [∀ x ∈ X ∃ y ∈ 2 φ (x, y) → ∀ x ∈ X φ (x, fx)] za předpokladu, že je v IST prokázáno, že ∀ x [φ (x, 0) → ¬φ (x, 1)]

Je zřejmé, že ac ^* _X je ekvivalentní

∃ f ∈ 2 ^X [∀ x ∈ X [φ (x, 0) ∨ φ (x, 1)] → ∀ x ∈ X φ (x, fx)]

a podobně pro DAC ^* _X.

Poté, přes IST, ac ^* ₁ a dac ^* ₁ jsou ekvivalentní k Lin a Stone.

Tyto výsledky ukazují, jak hluboce vybrané principy interagují s logikou, když se předpokládá, že logika na pozadí je intuicionální. V klasickém prostředí, kde se předpokládá zákon vyloučeného středa, jsou tato spojení odstraněna.

Čtenáři, kteří se zajímají o téma axiomu výběru a teorie typů, mohou nahlédnout do následujícího doplňkového dokumentu:

Axiom volby a teorie typů

Bibliografie

• Aczel, P., 1978. „Typově-teoretická interpretace teorie konstruktivních množin,“v A. ManIntyre, L. Pacholski a J. Paris (eds.), Logic Colloquium 77, Amsterdam: North-Holland, s. 55 -66.
• –––, 1982. „Typově-teoretická interpretace konstruktivní teorie množin: principy výběru“, v AS Troelstra a D. van Dalen (eds.), LEJ Brouwer Centenary Symposium, Amsterdam: North-Holland, pp. 1- 40.
• Aczel, P. a N. Gambino, 2002. "Zásady sběru v teorii závislých typů", v P. Callaghan, Z. Luo, J. McKinna a R. Pollack (eds.), Druhy důkazů a programů (Poznámky k přednášce o Computer Science, svazek 2277), Berlín: Springer, str. 1-23.
• –––, 2005. „Zobecněná typově-teoretická interpretace teorie konstruktivních množin,“Journal of Symbolic Logic, 71/1: 67-103. [Předtisk je k dispozici online v komprimovaném Postscriptu]
• Aczel, P. a M. Rathjen, 2001. Poznámky k konstruktivní teorii množin. Technická zpráva 40, Mittag-Lefflerův institut, Švédská královská akademie věd. [Předtisk je k dispozici online]
• Banach, S. a Tarski, A., 1924. „Sur la décomposition des ensembleles de points en strany, úcty, congruentes,“Fundamenta Mathematicae, 6: 244-277.
• Bell, JL, 1983. „O síle Sikorského věta o rozšíření pro booleovské algebry,“Journal of Symbolic Logic, 48: 841-846.
• –––, 1988. Topózy a teorie místních souprav: Úvod, Oxford: Clarendon Press, 1988.
• –––, 1997. „Zornovo lemma a kompletní booleovské algebry v teoriích intuicionistického typu,“Journal of Symbolic Logic, 62: 1265-1279.
• –––, 2003. „Některé nové intuicionistické ekvivalenty Zornovy Lemmy,“Archiv pro matematickou logiku, 42: 811-814.
• –––, 2005. Teorie množin: Booleovské modely a důkazy nezávislosti, Oxford: Clarendon Press.
• –––, 2006. „Principy výběru v intuicionistické teorii množin,“v Logický přístup k filozofii, Devidi, D. a Kenyon, T. (ed.), Berlín: Springer: 36-44.
• –––, 2008. „Axioma výběru a zákon vyloučeného středu ve slabých teoriích,“nastává matematická logika čtvrtletně.
• Bell, JL a Fremlin, D., 1972. „Maximální ideální věta pro mřížky sad,“Bulletin London Mathematical Society, 4: 1-2.
• –––, 1972a. "Geometrická forma axiomu volby," Fundamenta Mathematicae, 77: 167-170.
• Bell, JL a Machover, M., 1977. Kurz matematické logiky. Amsterdam: Severní Holandsko.
• Bernays, P., 1942. „Systém teorie axiomatických množin, část III,“Journal of Symbolic Logic, 7: 65-89.
• Bishop, E. a Bridges, D., 1985. Konstruktivní analýza, Berlín: Springer.
• Blass, A., 1984. „Existence bází zahrnuje axiom volby,“v Axiomatic Theory Theory, Baumgartner, Martin a Shelah (eds.) (Contemporary Mathematics Series, Svazek 31), American Mathematical Society, pp. 31-33.
• Bochner, S., 1928. "Fortsetzung Riemannscher Flachen," Mathematische Annalen, 98: 406-421.
• Bourbaki, N., 1939. Elements de Mathematique, Livre I: Theorie des Ensembles, Paris: Hermann.
• –––, 1950. „Sur le theoreme de Zorn,“Archiv dem Mathematik, 2: 434-437.
• Cohen, PJ, 1963. „Nezávislost hypotézy kontinua I,“Sborník z Národní akademie věd USA, 50: 1143-48.
• –––, 1964. „Nezávislost hypotézy kontinua II“, Sborník americké národní akademie věd, 51: 105-110.
• –––, 1966. Teorie množin a hypotéza Continuum, New York: Benjamin.
• Curry, HB a R. Feys, 1958. Combinatory Logic, Amsterdam: Severní Holandsko.
• Devidi, D., 2004. "Principy volby a konstruktivní logika," Philosophia Mathematica, 12/3: 222-243.
• Diaconescu, R., 1975. „Axiom výběru a doplňování“, Sborník americké matematické společnosti, 51: 176–8.
• Fraenkel, A., 1922. "Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre", Mathematische Annalen, 86: 230-237.
• Fraenkel, A., 1922a. Klasse, 253-257. Přeloženo z Van Heijenoort, Z Frege do Gödel: Zdrojová kniha v matematické logice 1879-1931, Harvard University Press, 1967, s. 284-289.
• Fraenkel, A., Y. Bar-Hillel a A. Levy, 1973. Základy teorie teorií, Amsterdam: North-Holland, ^2. vydání.
• Gödel, K., 1938. „Konzistentnost axiomu výběru a zobecněné hypotézy kontinua,“Sborník americké národní akademie věd, 24: 556-7.
• Gödel, K., 1938. „Důkaz konzistence pro zobecněnou hypotézu kontinua“, Sborník americké národní akademie Sciemces, 25: 220-4.
• Gödel, K., 1940. Soulad axiomu volby a zobecněné hypotézy kontinua s axiomy teorií množin, anály matematických studií, č. 3, Princeton: Princeton University Press.
• Gödel, K., 1964. "Poznámky před Princetonskou dvouleté konferenci" v The Undecidable, Martin Davis (ed.), CITY: Raven Press, s. 84-88.
• Goodman, N. a Myhill, J., 1978. „Výběr znamená vyloučený střed,“Zeitschrift kožešina Mathematische Logik und Grundlagen der Mathematik, 24/5: 461.
• Grayson, RJ, 1975. „Snopový přístup k modelům teorie množin,“M. S.c. diplomová práce, Katedra matematiky, Oxfordská univerzita.
• Halpern,, JD a Levy, A., 1971. „Booleovský primární ideální teorém neimplikuje axiom volby,“Axiomatická teorie množin, Sborníky ze sympozií v Pure Mathematics, sv. XIII, část I. American Mathematical Society, str. 83-134.
• Hamel, G., 1905. "Eine Basis aller Zahlen und die unstetigen Lösungen der Funktionalgleichung: f (x + y) = f (x) + f (y)," Mathematische Annalen, 60: 459-62.
• Hausdorff, F., 1909. "Die Graduierung nach dem Endverlauf," Königlich Sächsichsen Gesellschaft der Wissenschaften zu Leipzig, Math. - Fyzicky. Klasse, Sitzungberichte, 61: 297-334.
• –––, 1914. Grundzüge der Mengenlehre, Lipsko: de Gruyter. Přetištěno, New York: Chelsea, 1965.
• –––, 1914a. „Bemerkung über den Inhalt von Punktmengen,“Mathematische Annalen, 75: 428-433.
• Hilbert D., 1926. „Über das Unendliche,“Mathematische Annalen, 95. Přeloženo v J. van Heijenoort (ed.) Z Frege do Gödel: Zdrojová kniha v matematické logice, 1879–1931, Cambridge, MA: Harvard University Press, 1967, str. 367-392.
• Hodges, W., 1979. „Krull naznačuje Zorn,“Journal of London Mathematical Society, 19: 285-7.
• Howard, P. a Rubin, JE, 1998. Důsledky axiomu volby, průzkumy a monografie americké matematické společnosti, sv. 59.
• Howard, WA, 1980. „Pojem konstrukce podle vzorců,“v JR Hindley a JP Seldin (eds.), HB Curry: Eseje o kombinatorické logice. Lambda Calculus and Formalism, New York and London: Academic Press, pp. 479-490.
• Jacobs, B., 1999. Kategorická logika a teorie typů, Amsterdam: Elsevier.
• Jech, T., 1973. Axiom of Choice, Amsterdam: Severní Holandsko.
• Kelley, JL, 1950. „Věta o produktu Tychonoff zahrnuje axiom volby,“Fundamenta Mathematicae, 37: 75-76.
• Klimovsky, G., 1958. "El teorema de Zorn y la existencia de filtros a ideales maximales en los reticulados distributivos," Revista de la Union Matematica Argentina, 18: 160-64.
• Kuratowski, K., 1922. „Une méthode d'élimination des nombres transfinis des raissonements mathématiques,“Fundamenta Mathematicae, 3: 76-108.
• Lawvere, FW a Rosebrugh, R., 2003. Sady pro matematiku, Cambridge: Cambridge University Press.
• Lindenbaum, A., a Mostowski, A., 1938. “„ Über die Unabhängigkeit des Auswahlsaxioms a einiger seiner Folgerungen, “Comptes Rendus des Séances de la Société des Sciences a des Lettres de Varsovie, 31: 27-32.
• Maietti, ME, 2005. „Modulární korespondence mezi závislými typy teorií a kategorií, včetně pretopoi a topoi,“Mathematical Structures in Computer Science, 15/6: 1089-1145.
• Martin-Löf, P., 1975. „Intuitionistická teorie typů; predikativní část,“v HE Rose a JC Shepherdson (eds.), Logic Colloquium 73, Amsterdam: North-Holland, str. 73-118.
• –––, 1982. „Konstruktivní matematika a počítačové programování“, v LC Cohen, J. Los, H. Pfeiffer a KP Podewski (eds.), Logika, metodologie a filozofie vědy VI, Amsterdam: North-Holland, pp 153-179.
• –––, 1984. Intuitionistická teorie teorií, Neapol: Bibliopolis.
• –––, 2006. „100 let Zermeloho axiomu výběru: jaký byl problém s tím?“„The Computer Journal, 49/3: 345-350.
• Mendelson, E., 1956. „Nezávislost slabé axiomy výběru,“Journal of Symbolic Logic, 21: 350-366.
• –––, 1958. „Axiom fundierungu a axiom výběru,“Arkiv fur Mathematische Logik und Grundlagenforschung, 4: 67-70.
• –––, 1987. Úvod do matematické logiky, CITY: Wadsworth & Brooks, 3. vydání.
• Moore, GH, 1982. Zermelo's Axiom of Choice, Berlin: Springer-Verlag.
• Moore, RL, 1932. Základy teorie množin bodů, Anerican Mathematical Society Colloquium Publications, sv. 13.
• Myhill, J. a Scott, DS, 1971. "Ordinální definovatelnost", Axiomatická teorie množin. Proceedings of Symposia in Pure Mathematics, roč. XIII, část I. American Mathematical Society, pp. 271-8.
• Post, EL, 1953. "Nutná podmínka pro definovatelnost pro transfinit von Neumann-Gödel množiny teorií, s aplikací na problém existence definovatelného řádového uspořádání kontinua." Předběžná zpráva, Bulletin americké matematické společnosti, 59: 246.
• Ramsey, FP, 1926. „Základy matematiky,“Sborník z London Mathematical Society, 25: 338-84. Přetištěno v základech matematiky a dalších esejích, DH Mellor, ed. London: Routledge, 2001.
• Rubin, H. a Rubin, JE, 1985. Ekvivalenty axiomu volby II, Amsterdam: Severní Holandsko.
• Rubin, H. a Scott, DS, 1954. „Některé topologické věty, které jsou ekvivalentní teorému prvotního ideálu,“Bulletin of American Mathematical Society, 60: 389.
• Russell, B., 1906. „O některých potížích v teorii transfinitních čísel a typů řádů,“Sborník z London Mathematical Society, 4/2: 29-53.
• Shoenfield, JR, 1955. „Nezávislost axiomu volby,“Journal of Symbolic Logic, 20: 202.
• Sikorski, R., 1948. „Věta o rozšíření homomorfismů,“Annales de la Societé Polonaise de Mathématiques, 21: 332-35.
• Solovay, R., 1970. „Model teorie množin, ve kterém je každá sada realů měřitelná Lebesgueem,“Annals of Mathematics, 92: 1-56.
• Specker, E., 1957. "Zur Axiomatik der Mengenlehre (Fundierungs- und Auswahlaxiom)," Zeit. Matematika. Logik und Grund., 3: 173-210.
• Steinitz, E., 1910. "Algebraische Theorie der Körper," Journal für die Reine und angewandte Mathematik (Crelle), 137: 167-309.
• Stone, MH, 1936. „Teorie reprezentací pro booleovské algebry,“Transactions of American Mathematical Society, 40: 37-111.
• Tait, WW, 1994. „Zákon vyloučeného středu a axiom volby,“v Mathematics and Mind, A. George (ed.), New York: Oxford University Press, s. 45-70.
• Takeuti, G., 1961. "Poznámky k Cantor's Absolute", Journal of the Mathematical Society of Japan, 13: 197-206.
• Tarski, A., 1948. "Axiomatické a algebraické aspekty dvou vět o součtech kardinálů," Fundamenta Mathematicae, 35: 79-104.
• Teichmuller, O., 1939. "Brauch der Algebraiker byl Auswahlaxiom?" Deutsches Mathematik 4: 567-577.
• Vitali, G., 1905. Sul problema della misura dei gruppi di punti di una retta, Bologna: Tip. Gamberini e Parmeggiani.
• Wagon, S., 1993. The Banach-Tarski Paradox, Cambridge University Press.
• Zermelo, E., 1904. „Neuer Beweis, dass jede Menge Wohlordnung werden kann (Aus einem an Herrn Hilbert gerichteten Briefe)“, Mathematische Annalen, 59: 514-16. Přeloženo v J. van Heijenoort (ed.), Z Frege do Gödel: Source Book in Mathematical Logic, 1879-1931, Cambridge, MA: Harvard University Press, 1967, str. 139-141.
• –––, 1908. Neuer Beweis für die Möglichkeit einer Wohlordnung, Mathematische Annalen, 65: 107-128. Přeloženo v J. van Heijenoort (ed.), Z Frege do Gödel: Source Book in Mathematical Logic, 1879-1931, Cambridge, MA: Harvard University Press, 1967, s. 183-198.
• –––, 1908a. „Untersuchungen uber die Grundlagen der Mengenlehre,“Mathematische Annalen, 65: 107-128. Přeloženo v J. van Heijenoort (ed.), Z Frege do Gödel: Source Book in Mathematical Logic, 1879-1931, Cambridge, MA: Harvard University Press, 1967, str. 199-215.
• Zorn, M., 1935. Poznámka k metodě v transfinitové algebře, Bulletin of American Mathematical Society, 41: 667-70.

Další internetové zdroje