A Választás Axióma

Tartalomjegyzék:

A Választás Axióma
A Választás Axióma
Anonim

Ez egy fájl a Stanford Enciklopédia Filozófia archívumában.

A választás axióma

Első kiadás: 2008. január 8., kedd; érdemi felülvizsgálat 2008. január 9, hétf

A választott axióma néven ismertetett elmélet elvét „valószínűleg a legérdekesebb és a késői megjelenés ellenére a matematika legvitatottabb axiómájaként kezelik, csupán Euclid párhuzamos axiómájához, amelyet több mint kétezer vezettek be. évekkel ezelőtt”(Fraenkel, Bar-Hillel és Levy 1973, II.4. bekezdés). A leírás teljessége miatt az axiómától ismeretlenek arra számíthatnak, hogy ugyanolyan megdöbbentő lesz, mint mondjuk a fénysebesség állandójának állandó elve vagy a Heisenbergi bizonytalanság elve. Valójában azonban a választott axióma, amint azt általában állítják, hummer, még magától értetődőnek is. Mert nem más, mint az állítás, miszerint, tekintettel a kölcsönösen el nem oldódó, nem üres halmazok gyűjteményére,lehetséges egy új készlet - keresztirányú vagy választható készlet - összeszerelése, amely pontosan egy elemet tartalmaz az adott gyűjtemény minden egyes tagjából. Ennek a látszólag ártalmatlan elvnek azonban messzemenő matematikai következményei vannak - sok nélkülözhetetlen, néhány megdöbbentő -, és kiemelkedő szerepet játszik a matematika alapjairól szóló vitákban. Ezt (vagy annak ekvivalenseit) számtalan matematikai cikkben alkalmazták, és számos monográfiát kizárólag ennek szenteltek.és számos monográfiát szentelték erre a célra.és számos monográfiát szentelték erre a célra.

  • 1. A választási axióma eredete és kronológiája
  • 2. A választási axióma függetlensége és következetessége
  • 3. A maximális alapelvek és Zorn lemma
  • 4. A választási axióma matematikai alkalmazása
  • 5. A választás és logika axióma

    Kiegészítő dokumentum: A választás és típus elmélete axióma

  • Bibliográfia
  • Egyéb internetes források
  • Kapcsolódó bejegyzések

1. A választási axióma eredete és kronológiája

1904-ben Ernst Zermelo megfogalmazta az Axiom of Choice-t (amelyet ebben a cikkben rövidített rövidítésként AC-nek nevezünk), az úgynevezett burkolatok alapján (Zermelo 1904). Egy önkényes M sorozattal kezdődik, és az M 'szimbólummal jelöli az M tetszőleges, nem üres részhalmazát, amelynek gyűjteményét M. jelöli. Folytatja:

Képzeljük el, hogy minden M 'részhalmazhoz egy tetszőleges m 1 ' elem van társítva, amely maga az M 'fordul elő; legyen m 1 'az M' megkülönböztetett elemének '. Ez az M halmaz bizonyos elemeivel „fedezi” az M halmazt. Ezen burkolatok száma megegyezik [az összes M 'részhalmazainak szorzatával], és mindenképpen különbözik a 0-tól.

Az idézet utolsó mondata - amely gyakorlatilag azt állítja, hogy a burkolatok mindig léteznek bármilyen (nem példa nélküli) halmaz nélküli részhalmaz gyűjteményéhez - a Zermelo első megfogalmazása az Axiom of Choice [1]. Ezt általában a választási függvényekkel állítják: itt a nem üres halmazok H gyűjteményének választási függvénye egy f térkép, amelynek H tartománya olyan, hogy f (X) ∈ X minden X ∈ H értékre.

Egy nagyon egyszerű példa lehet, hogy H legyen a {0, 1} nem példa nélküli részhalmazai, azaz H = {{0}, {1}, {0,1}}. Akkor H két különálló választási függvényt, f 1 és f 2 ad, amelyek:

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

A választási függvény egy érdekesebb példája az, ha H-t valós számok (rendezetlen) párjának sorozatába állítják, és az a funkció, amely az egyes párok számára a legkevesebb elemet jelöli. Különböző választási függvény érhető el, ha minden párthoz hozzárendeljük a legnagyobb elemét. Nyilvánvalóan még sok más választási funkció meghatározható a H-n.

A választási funkciók szerint Zermelo AC első megfogalmazása így szól:

AC1:

Bármilyen nem üres készlet készlete választási funkcióval rendelkezik.

Az AC1 újrafogalmazható indexált vagy változó halmazok szerint. Az A = {A i  : i ∈ I} halmazok indexált gyűjteményét úgy állíthatjuk elő, mint egy változó halmazt, ésszerűséggel, mint az I index halmaztól függően változó halmazt. Mindegyik A i akkor az A változó halmazának „értéke” az i stádiumban. Az A választási függvénye egy f térkép: I → ∪ i ∈ I A i olyan, hogy f (i) ∈ A i minden i ∈ I számára. Az A választási függvény tehát az A változó halmazának egyik elemének „kiválasztása” minden szakaszban; más szóval, az A választási függvénye az A változó eleme. AC1 ezután egyenértékű az állítással

AC2:

Bármely indexelt halmaznak választási funkciója van.

Informálisan szólva, az AC2 azzal a kijelentéssel jár, hogy egy változókészlet, amelynek minden eleme egy elemmel rendelkezik, változó elemmel rendelkezik.

Az AC1 a kapcsolatok szempontjából is újrafogalmazható, nevezetesen:

AC3:

Bármely R relációra az A, B halmaz, ∀ x ∈ A ∃ y ∈ B [R (x, y)] ⇒ ∃ f [f: A → B & ∀ x ∈ A [R (x, fx)].

Más szavakkal, minden reláció tartalmaz egy azonos tartományú funkciót.

Végül könnyen megmutatható, hogy az AC3 (a szokásos elméletekben) egyenértékű: [2]

AC4:

Bármelyik szelektív funkciónak van egy jobb inverzje.

Egy 1908-as cikkben a Zermelo bevezette az AC módosított formáját. Hívjuk a H halmazok családjának keresztirányú (vagy választható halmazát) bármely olyan T ⊆ ⊆H részhalmazt, amelynél minden T ∩ X metszéspont X X H számára pontosan egy elemmel rendelkezik. Nagyon egyszerű példa: H = {{0}, {1}, {2, 3}}. Akkor H-nek van a két keresztirányú {0, 1, 2} és {0, 1, 3}. Jelentõsebb példát adhatunk, ha H-nak hagyjuk az összes euklideszi síkban az x-axivel párhuzamos vonalakat. Ekkor az y-axisz T pontjainak halmaza keresztirányú H-re.

A keresztirányban kifejezve, tehát Zermelo AC (1908) második megfogalmazása azzal az állítással jár, hogy a kölcsönösen szétválasztott, nem üres halmazok minden családja keresztirányú. [3]

Zermelo azt állítja, hogy ennek az elvnek a tisztán objektív jellege „azonnal nyilvánvaló”. Ezen állítás megfogalmazásakor Zermelo azt a tényt kívánta hangsúlyozni, hogy ebben az alakban az elv nem vonzza a „választások” lehetőségét. Az is előfordulhat, hogy Zermelo a következő „kombinatorikus” indoklást szem előtt tartotta. Ha kölcsönösen el nem különbözõ nem halmaz halmazok H családját kell megadni, hívja az S ⊆ ∪H alhalmazt H választógombra, ha S ∩ X ≠ ∅ minden X ∈ H számára. Nyilvánvaló, hogy léteznek H szelektorok; ∪Ha maga egy példa. Most el lehet képzelni, hogy elvégezzük az S szelektor választását és az S “X metszéspontjainak„ kinyomtatását”X ∈ H számára, amíg csak egyetlen elemet tartalmaz. Az eredmény keresztirányú a H. számára. Ez az érv, megfelelően finomítva, az AC pontos származtatását eredményezi ebben a megfogalmazásban a Zorn néven ismert elméleti alapelvből.s lemma (lásd alább).

Hívjuk Zermelo 1908-as összetételét a választott kombinatorikus axiómának:

CAC:

A kölcsönösen szétválasztott, nem üres halmazok minden gyűjteményének keresztirányúak vannak.

Meg kell jegyezni, hogy az AC1 és a CAC a készletek véges gyűjteményei esetében is bizonyítható (indukcióval) a szokásos halmazelméletekben. De egy végtelen gyűjtemény esetében, még ha minden tagja véges is, problematikus a választási függvény vagy egy keresztirány fennállásának kérdése [4]. Például, amint már említettük, könnyű választási funkcióval állni a valós számpárok összegyűjtésére (egyszerűen válassza ki az egyes párok kisebb elemét). De egyáltalán nem nyilvánvaló, hogyan lehet választási függvényt létrehozni a tetszőleges valós számok halmazának összegyűjtésére.

Zermelo eredeti célja az AC bevezetése a Cantor halmazelméletének központi alapelvének megteremtése volt, nevezetesen az, hogy minden halmaz elismeri a rendes rendezést, és így bíboros számot is hozzárendelhet. Zermelo axiómájának 1904-es bevezetése, valamint az annak felhasználása jelentős kritikát váltott ki a mai matematikusok részéről. A legfőbb kifogás az volt, hogy egyesek úgy tekintik, mint a nagyon nem konstruktív, sőt idealista karakterét: míg az axióma megengedi, hogy tetszőleges - talán még megszámlálhatatlan - számú tetszőleges „választást” tegyen, addig semmi nem utal. az utóbbi tényleges megvalósításának módja, hogyan kell meghatározni a választási funkciókat. Ez különösen kifogásolható egy „konstruktív” hajlékosságú matematikusok számára, mint például az úgynevezett francia empirikusok Baire,Borel és Lebesgue, akiknek feltételezhető, hogy létezik egy matematikai objektum, csak akkor létezik, ha az meghatározható oly módon, hogy egyedileg jellemezze. Zermelo kritikáira adott válasza 1908-ban két dokumentum formájában alakult ki. Az első részben, amint azt a fentiekben megjegyeztük, újrafogalmazta, amelyben átfogalmazta az AC-et a keresztirányú keretek között; a másodikban (1908a) kifejezetten kifejtette azokat a további feltételezéseket, amelyek szükségesek a jól megrendelő tétel bizonyításához. Ezek a feltevések képezték a halmazelmélet axiómarendszerének első explicit bemutatását.újrafogalmazta, amelyben átfogalmazta az AC-et a keresztirányok tekintetében; a másodikban (1908a) kifejezetten kifejtette azokat a további feltételezéseket, amelyek szükségesek a jól megrendelő tétel bizonyításához. Ezek a feltevések képezték a halmazelmélet axiómarendszerének első explicit bemutatását.újrafogalmazta, amelyben átfogalmazta az AC-et a keresztirányok tekintetében; a másodikban (1908a) kifejezetten kifejtette azokat a további feltételezéseket, amelyek szükségesek a jól megrendelő tétel bizonyításához. Ezek a feltevések képezték a halmazelmélet axiómarendszerének első explicit bemutatását.

Ahogyan a választás axiómájáról folytatott vita zajlott, nyilvánvalóvá vált, hogy számos jelentős matematikai tétel bizonyítéka alapvetően hasznosította azt, és ez arra késztette a matematikusokat, hogy a kereskedelem nélkülözhetetlen eszközeként kezeljék. Például Hilbert úgy vélte, hogy az AC a matematika alapvető alapelveként [5], és a klasszikus matematikai érvelés védelmében alkalmazta az intuíciók támadásainak ellen. Valójában az ε-operátorok alapvetően csak választási funkciók (lásd az epsilon kalkulus bejegyzését).

Noha az AC hasznossága gyorsan világossá válik, továbbra is kétségei vannak annak stabilitásáról. Ezeket a kétségeket megerősítette az a tény, hogy ennek bizonyos feltűnő ellentétes hatásai voltak. A leglátványosabb ezek közül Banach és Tarski szférájának paradox helyzetű bomlása (Banach és Tarski 1924): bármilyen szilárd gömb végesen sok darabra bontható, amelyeket össze lehet szerelni, hogy két azonos méretű szilárd gömböt képezzenek; és bármely szilárd gömb elválaszthatatlanul sok darabra osztható úgy, hogy lehetővé tegyék azok összeszerelését, hogy tetszőleges méretű szilárd gömböt képezzenek. (Lásd Wagon 1993.)

Csak az 1930-as évek közepén vette végül az AC stabilitásának kérdését Kurt Gödel bizonyítékával annak következetességére a set elmélet többi axiómájához viszonyítva.

Itt található az AC rövid időrendje: [6]

1904/1908 Zermelo bemutatja a halmazelmélet axiómáit, kifejezetten megfogalmazza az AC-t, és felhasználja a jól megrendelő tétel bizonyítására, ezáltal felvetve a vitát.
1904 Russell az AC-t multiplikatív axiómának ismeri fel: az önkényes nem nulla bíboros szám szorzata nulla.
1914 A Hausdorff az AC-ből arra következtet, hogy nem mérhető halmazok léteznek „paradox” formában, amelyek szerint egy gömb ½-e egyhöz tartozik (Hausdorff 1914).
1922 Fraenkel bevezeti a „permutációs módszert” az AC függetlenségének megállapításához az atomokkal meghatározott elméleti rendszertől (Fraenkel 1922).
1924 Hausdorff munkájára építve, Banach és Tarski az AC-ből a szféra paradox módon történő bomlásából származik.
1926 Hilbert bevezeti bizonyítási elméletében a „transzfinit” vagy az „epsilon” axiómát, mint az AC változatát. (Hilbert 1926).
1936 Lindenbaum és Mostowski kibővíti és finomítja Fraenkel permutációs módszerét, és bizonyítja az AC-nél gyengébb halmazelméleti állítások függetlenségét. (Lindenbaum és Tarski 1938)
1935-1938 Gödel megállapítja az AC relatív konzisztenciáját a meghatározott elmélet axiómáival (Gödel 1938, 1939, 1940).
1950 Mendelson, Shoenfield és Specker, egymástól függetlenül dolgozva, a permutációs módszert használják az AC különféle formáinak függetlenségének megállapításához az atomok nélküli elméleti rendszertől, de az alap axiómájának hiányában is (Mendelson 1956, 1958, Shoenfield 1955, Specker 1957)..
1963 Paul Cohen bizonyítja az AC függetlenségét a set elmélet szokásos axiómáitól (Cohen 1963, 1963a, 1964).

2. A választási axióma függetlensége és következetessége

Mint fentebb említettük, 1922-ben Fraenkel bizonyította az AC függetlenségét az atomokat tartalmazó halmazelmélet rendszerétől. Itt egy atom alatt tiszta egyént értünk, azaz egy entitásnak nincs tagja, és mégis különbözik az üres halmaztól (tehát egy atom nem lehet halmaz). Az atomokkal meghatározott elméleti rendszerben feltételezzük, hogy az atomok végtelen A halmazát kapják. Felépíthetjük a halmazok V (A) univerzumát A fölött, kezdve A-val, összeadva az A összes részhalmazát, az eredmény összes részhalmazát csatlakoztatva stb., És véglegesen iterálva. A V (A) ezután az atomokkal meghatározott halmazelmélet modellje. Az AC függetlenségének bizonyítására szolgáló Fraenkel-módszer lényege az a megfigyelés, hogy mivel az atomokat nem lehet elméletileg megkülönböztetni,az A atomkészlet bármilyen permutációja az A-ból épített halmazok V (A) univerzumának szerkezetmegőrző permutációját - automatizmusát - indukálja. Ez az ötlet felhasználható a készletelmélet egy másik Sym (V) modelljének - egy permutációnak vagy szimmetrikus modellnek - felépítésére, amelyben az A elemei egymással szétválasztott párja nem rendelkezik választási funkcióval.

Tegyük fel, hogy az A automatizmusainak G csoportját kapjuk. Tegyük fel, hogy az A π automorfizmus rögzíti a V (A) x elemét, ha π (x) = x. Nyilvánvaló, hogy ha π ∈ G rögzíti minden A elemét, akkor V (A) minden elemét is rögzíti. Előfordulhat, hogy bizonyos x ∈ V (A) elemeknél az A részhalmazának elemeinek bármilyen π ∈ G-vel történő rögzítése elegendő az x rögzítéséhez. Ezért arra buzdítunk, hogy határozzuk meg az x támogatását az A X részhalmazaként, tehát amikor π ∈ G rögzíti az X minden tagját, akkor az x is rögzíti. Az V (A) tagokat, amelyek véges támogatással rendelkeznek, szimmetrikusnak nevezzük.

Ezután meghatározzuk a Sym (V) univerzumot V (A) örökletesen szimmetrikus tagjaiból, azaz azokból az x ∈ V (A) -ekből, hogy x, x elemei, x elemeinek elemei stb., mind szimmetrikusak. A Sym (V) az A atomhalmaz halmazelméleti modellje is, és π a Sym (V) automatizmusát indukálja.

Tegyük fel, hogy A-t fel kell osztani egy (szükségszerűen végtelen) kölcsönösen elválasztott P-halmazba. G legyen az A permutációinak csoportja, amely rögzíti az összes P értéket. Majd P ∈ Sym (V); Most bebizonyítható, hogy a Sym (V) nem tartalmaz választási funkciót a P gombbal. Tegyük fel, hogy f választott függvény volt P-n és f ∈ Sym (V) -en. Ezután f-nek van egy véges támasza, amely úgy tekinthető, hogy {a 1,…, a n, b 1,…, b n } legyen, mindegyik {a i, b i } ∈ P párral. Mivel P végtelen, akkor a {c, d} = U pár közül P közül választhatunk, amely különbözik az összes {a i, b i } -tól. Most definiáljuk π ∈ G-t, hogy π rögzítse mindegyik a i-t és b-ti, valamint c és d cseréje. Akkor π is f-et rögzít. Mivel fnek P és U ∈ P választási függvénynek kellett lennie, akkor f (U) ∈ U-nak kell lennie, vagyis f (U) = c vagy f (U) = d. Mivel π cserél c és d, ebből következik, hogy π (f (U)) ≠ f (U). Mivel azonban π egy automatizmus, megőrzi a függvény alkalmazását is, így π (f (U)) = π f (π (U)). De π (U) = U és π f = f, honnan π (f (U)) = f (U). Megfelelően eljutottunk egy ellentmondáshoz, megmutatva, hogy a Sym (V) világegyetem nem tartalmaz P választási funkciót.

A lényeg itt az, hogy a P-nél definiált szimmetrikus függvénynél létezik egy P párt tartalmazó L véges lista, amelynek összes elemének rögzítése elegendő az f rögzítéséhez, és így az f összes értéke is. Most, bármilyen P-nél, P-ben, de nem L-ben, mindig megtalálható egy π permutáció, amely rögzíti a párok összes elemét L-ben, de nem rögzíti az U tagjait. Mivel π-nek rögzítenie kell f értékét U-n, ez az érték nem lehet U-ban. Ezért f nem tudja „választani” egy U elemet, tehát az f még nem lehet választási függvény P-en.

Ez az érv azt mutatja, hogy az atomhalmazok gyűjteményének nem kell feltétlenül választási funkcióval rendelkeznie, ám ugyanezt a tényt nem tudja megállapítani a matematika „szokásos” halmazaira, például a valós számok halmazára. Ennek 1963-ig kellett várnia, amikor Paul Cohen megmutatta, hogy összhangban van a halmazelmélet szokásos axiómáival (amelyek kizárják az atomok létezését) azt feltételezni, hogy a valós számhalmaz-halmazok számolható gyűjteményének nincs választási funkciója. Cohen bizonyítási módszerének - az ünnepelt erőszakos módszernek - lényege lényegesen általánosabb volt, mint bármely korábbi technika; függetlenségi bizonyítéka ugyanakkor alapvetően abban a formában is felhasználta a permutációt és a szimmetriát, amelyben Fraenkel ezeket eredetileg alkalmazta.

Gödel bizonyítéka az AC relatív konzisztenciájáról a set elmélet axiómáival (lásd Kurt Gödel bejegyzését) egy teljesen más gondolaton nyugszik: a definiálhatóság gondolatán. A halmazok új hierarchiáját - a szerkeszthető hierarchiát - vezetett be a kumulatív típusú hierarchia analógiájával. Emlékeztetünk arra, hogy az utóbbit a következő reinkuráció határozza meg az ordinálokban, ahol P (X) az X erőkészlete, α egy rend és λ egy határ sorrend:

V 0 =
V α + 1 = P (V α)
V λ = α <λ V α

A konstruktív hierarchiát egy hasonló rekurzió határozza meg a ordinálokban, ahol Def (X) az X összes részhalmaza, amelyek elsőrendűek a struktúrában (X, ∈, (x) x X): [7]

L 0 =
L α + 1 = Def (L α)
L λ = α <λ L α

A konstruktív univerzum az osztály L = ∪ α∈Ord L α; az L tagjai az összehúzódó halmazok. Gödel megmutatta, hogy (feltételezve a Zermelo-Fraenkel halmazelmélet ZF axiómáit) a szerkezet (L, ∈) a ZF, valamint az AC, valamint az általánosított folytonos hipotézis modellje. Az AC és a ZF relatív konzisztenciája következik.

Gödel (1964) (és egymástól függetlenül Myhill és Scott, 1971, Takeuti 1963 és Post 1951) megfigyelte, hogy az AC relatív konzisztenciájának egyszerűbb bizonyítéka megfogalmazható az ordinális definiálhatóság szempontjából. Ha D (X) értéket írunk az X összes olyan részhalmazára, amelyek az első sorrendben definiálhatók a struktúrában (X, ord), akkor az ordinálisan definiálható halmazok OD osztályát úgy határozzuk meg, hogy ∪ α∈Ord D (V α). Az örökletesen ordinálisan definiálható halmazok HOD osztálya minden olyan halmazból áll, amelyekre a, az a tagjai, az a tagjai tagjai, stb. Minden rendrendben meghatározható. Ezután kimutatható, hogy a szerkezet (HOD, ∈) a ZF + AC modellje, amelyből ismét következik az AC és a ZF relatív konzisztenciája.[8]

3. A maximális alapelvek és Zorn lemma

A választás axióma szorosan kapcsolódik a matematikai javaslatok egy csoportjához, amelyet együttesen maximális alapelveknek neveznek. Általánosságban véve, ezek a javaslatok azt állítják, hogy bizonyos feltételek elegendőek annak biztosításához, hogy a részlegesen rendelt halmaz legalább egy maximális elemet tartalmaz, azaz olyan elemet, hogy az adott részleges rendezés szempontjából egyik elem sem szigorúan meghaladja azt.

A maximális elem és az AC közötti kapcsolat megismeréséhez térjünk vissza az utóbbi AC2 megfogalmazásához az indexált halmazok tekintetében. Tehát tegyük fel, hogy kapunk egy nem üres halmaz indexált családját A = {A i  : i ∈ I}. Definiáljunk egy lehetséges választási függvényt A-n, amely olyan f függvény, amelynek tartománya I részhalmaza, úgy, hogy f (i) ∈ A imindenki számára ∈ J. (Itt a minősítő potenciál használatát az a tény sugallja, hogy a tartomány az I részhalmaza; emlékeztessünk arra, hogy az A választható f funkciója ugyanazokkal a tulajdonságokkal rendelkezik, mint amit most potenciális választási függvényeknek hívunk, azzal a különbséggel, hogy f tartománya Az A potenciális választási függvényeinek P halmazát részben megrendelhetjük a beillesztéssel: egyetértünk abban, hogy az f, g ∈ P potenciális választási függvényeknél f ≤ g viszony áll fenn, feltéve, hogy hogy az f domén bele van foglalva a g tartományába, és f értéke egy domain elemében egybeesik g ott megadott értékével. Könnyen belátható, hogy a P maximális elemei a részleges rendezéshez viszonyítva pontosan az A választási függvényei.

A Zorn Lemma a legismertebb elv, amely biztosítja az ilyen maximális elemek meglétét. Ennek megállapításához szükségünk van néhány meghatározásra. Ha egy részlegesen rendezett halmazt (P, ≤) adunk, akkor a P X részhalmazának felső határa a ∈ P elem, amelynek x ≤ a minden x ∈ X-re; egy P maximális elemét akkor definiálhatjuk olyan a elemként, amelynél a {a} felső határainak halmaza egybeesik a {a} -vel, ami lényegében azt jelenti, hogy P egyik eleme sem lehet szigorúan nagyobb, mint a. A (P, ≤) lánc olyan P C részhalmaza, hogy bármely x, y ∈ P esetén x ≤ y vagy y ≤ x. P-nek akkor mondjuk induktívnak, ha a P minden láncában van felső határ. Most Zorn's Lemma állítja:

Zorn-féle lemma (ZL):

Minden nem igényes induktív részlegesen elrendezett halmaznak van egy maximális eleme.

Miért hihető a Zorn Lemma? Itt egy informális érv. Mivel egy nem üres induktív részben rendezett halmaz (P, ≤), választhatunk egy tetszőleges elemét p 0 a P. Ha p 0 maximális, állj meg itt. Egyébként válasszon egy elemet p 1 > p 0; Ha p 1 maximális, állj meg itt. Egyébként válasszon egy p 2 > p 1 elemet, és ismételje meg a folyamatot. Ha a p 0 <p 1 <p 2 <… <p n <… egyik elem sem maximális, a p i egy olyan láncot képez, amelynek - mivel P induktív - felső határa q 0. Ha q 0maximális, állj meg itt. Ellenkező esetben a folyamat megismételhető q 0 <q 1,… értékkel, majd megismételhető. Ennek a folyamatnak végül be kell fejeződnie, mivel egyébként az így létrehozott láncok összekapcsolása megfelelő osztályt képez, és maga a P a feltételezéssel ellentétben megfelelő osztályt képez. A folyamat befejezésének pontja P maximális elemet eredményez.

Ez az érv, alkalmasan rigorized, ad egy igazolást [9] a ZL származó AC1 a Zermelo-Fraenkel halmazelmélet: ebben a bizonyítás AC1 használják „pick” említett elemek az informális érv.

A Zorn Lemma másik változatát a készletgyűjtemények alapján adhatjuk meg. Ha H halmazból áll, nevezjünk fészket H-ban a H N bármely algyűjteményében úgy, hogy az N tagok bármelyike esetén az egyik a másikba tartozik. [10] H hívja fel erősen induktív módon, ha a H fészek bármelyikének egyesülése H. Zorn Lemma tagja lehet, és ezzel egyenértékűen megismételhető azzal az állítással, hogy minden halvány erősen induktív H gyűjteményhez a maximális tag, azaz egy tag megfelelően beépítve a H. egyetlen tagjába sem. Ez kettős formában is megfogalmazható. Hívjon erősen reduktív halmazkészlet-családot, ha fészkek metszéspontjainál zárva van. Ezután minden nem nem erősen reduktív készletcsaládnak minimális eleme van, vagyis egy tagnak megfelelőnek kell lennie, beleértve a család egyetlen tagját sem.

Az AC2 ma már könnyen származtatható Zorn Lemma-ból ezen alternatív formában. Az indexelt indexhalmazok potenciális választási funkcióinak P halmazánál az A egyértelműen nem üres és könnyen kimutatható, hogy erősen induktív; tehát Zorn lemma választási függvény létezését eredményezi az A-n.

A CAC a ZL- ből származtatható oly módon, hogy visszatérjen a fent vázolt CAC „kombinatorikus” indokolására. Tehát feltételezzük, hogy kapunk egy H családot, amelyek egymástól elválaszthatatlan, nem üres halmazai; hívjon egy S ⊆ ∪H alcsoportot H mintavételre, ha bármelyik X ∈ H esetén X ⊆ S vagy S ∩ X nem üres és véges. A minimális mintavétel pontosan keresztirányú a H számára; [11] és a mintavételek T gyűjtése nyilvánvalóan nem üres, mivel ∪H-t tartalmaz. Tehát, ha bebizonyítható, hogy T erősen reduktív, [12] Zorn lemma a T minimális elemét fogja eredményezni, és így keresztirányú a H-ra. A T erős reductivitása a következőképpen látható: tegyük fel, hogy {S i  : i ∈ I} minták fészke; legyen S = ∩ i ∈ I Si. Meg kell mutatnunk, hogy S maga is egy mintavétel; ebből a célból hagyjuk X ∈ H és tegyük fel ¬ (X ⊆ S). Akkor ott van i ∈ I, amelyre ¬ (X ⊆ S i); mivel S i egy mintavétel, S i ∩ X véges (JAA: javasolt kiegészítés: "és") nem üres, mondjuk S i ∩ X = {x 1,…, x n }. Nyilvánvalóan S ∩ X véges; tegyük fel az ellentmondás kedvéért, hogy S ∩ X = ∅. Aztán minden k = 1,…, n esetén van i k ∈ I, amelyre ¬ (x k ∈ S i k). Ebből következik, hogy ¬ (S i ⊆ S i k), ha k = 1,…, n. Tehát, mivel az S iláncot képeznek, mindegyik S i k az S i részhalmaza. Legyen S j a legkisebb S i 1,…, S i k közül; majd S j ⊆ S i. De mivel ¬ (x k ∈ S j), k = 1,…, n esetén, ebből következik, hogy S j ∩ X = ∅, ellentmond annak, hogy S j egy mintavétel. Ezért S ∩ X ≠ ∅; és S jelentése mintavétel.

Megjegyezzük, hogy míg Zorn lemma és a választás axióma-elméletileg azonosak, sokkal nehezebb előbbit az utóbbiból levezetni, mint fordítva.

Itt található a maximális alapelvek rövid időrendje.

1909 Hausdorff bemutatja a maximális elv első explicit megfogalmazását, és az AC-ből származtatja (Hausdorff 1909) (
1914 Hausdorff Grundzüge der Mengenlehre (a készletelmélet és az általános topológia első könyveinek száma) számos maximális alapelvet tartalmaz.
1922 Kuratowski számos maximális alapelvet fogalmaz meg és alkalmaz annak érdekében, hogy elkerülje a transzfinit ordinálok használatát (Kuratowski 1922).
1926-1928 Bochner és mások önállóan vezetik be a maximális alapelveket (Bochner 1928, Moore 1932).
1935 Max Zorn, nyilvánvalóan ismeretlen a maximális alapelvek korábbi megfogalmazásaival kapcsolatban, közzéteszi (Zorn 1935) annak végleges változatát, hogy később lemmá (ZL) nevezzék. A ZL- t először 1933-ban alakították ki Hamburgban, ahol Chevalley és Artin gyorsan „elfogadták”. Úgy tűnik, hogy Artin fedezte fel először, hogy ZL AC-t ad, tehát a kettő ekvivalens (a halmazelmélet fennmaradó axiómáiban). Zorn elvét kevésbé tételként, mint axiómának tekintette - remélte, hogy ez felülírja a nehézkes alkalmazásokat a transzfinit indukció és a rend rend algebrai alkalmazásában, amelyet a Noether iskolában algebristák „transzcendentális” eszközöknek tekintenek.
1939-1940 Teichmüller, Bourbaki és Tukey egymástól függetlenül újrafogalmazzák a ZL- t a „véges karakter tulajdonságai” alapján (Bourbaki 1939, Teichmuller 1939, Tukey 1940).

4. A választási axióma matematikai alkalmazása

Az Axiom of Choice számos alkalmazással rendelkezik a matematikában, amelyek közül számos formálisan egyenértékűnek bizonyult [13]. A történelem szempontjából a legfontosabb alkalmazás az első, nevezetesen:

A jól megrendelő tétel (Zermelo 1904, 1908). Minden készlet jól megrendelhető

Miután Zermelo 1904-ben közzétette az AC rendrendelési tételének bizonyítékát, gyorsan kiderült, hogy a kettő egyenértékű.

Az AC másik korai egyenértékű értéke

A szorzó szorongás (Russell 1906). A nullán kívüli bíboros számok halmazának szorzata nem nulla

Az AC korai alkalmazásai:

  • Minden végtelen halmaznak van egy megbontható részhalmaza. Ez az AC-nél is gyengébb elv nem bizonyítható anélkül, hogy a set elmélet fennmaradó axiómáinak összefüggésében lenne.
  • Minden végtelen bíboros szám egyenlő a négyzetével. Ez bizonyult az AC-nek a Tarski 1924-ben.
  • Minden vektor térnek van alapja (Hamel 1905 kezdeményezi). Ez bizonyult az AC-vel egyenértékűnek a Blass 1984-ben.
  • Minden mezőnek van egy algebrai zárása (Steinitz 1910). Ez az állítás gyengébb, mint az AC, valóban az elsőrendű logika (gyengébb) kompaktság tételének következménye (lásd alább).
  • Létezik egy Lebesgue nem mérhető valós szám halmaza (Vitali 1905). Ez sokkal később kiderült, hogy a BPI következménye (lásd alább), és ennélfogva gyengébb, mint az AC. Solovay (1970) megállapította a meghatározott elmélet fennmaradó axiómáinak függetlenségét.

Az AC jelentős „folklór” megfelelője

  • A set-elméleti eloszlási törvény. A {M i, j  : i ∈ I, j ∈ J} halmazok tetszőlegesen kétszeresen indexált halmazánál, ahol J I az összes I tartományhoz tartozó függvény halmaza, amely J értéket vesz fel:

    i ∈ I  ∪ j ∈ J   M i, j = ∪ f ∈ J I  ∩ i ∈ I   M i, f (i)

Az AC egy nagyon tanulmányozott különleges esete az

A függő választások elve (Bernays 1942, Tarski 1948). Az A halmazon lévő bármely nem-nem R relációhoz, amelynek tartománya (R) ⊆ tartomány (R), van egy f függvény: ω → A olyan, hogy minden n ∈ω esetén R (f (n), f (n + 1)). Ez az elv, bár (sokkal) gyengébb, mint az AC, nem bizonyítható anélkül, hogy a set elmélet fennmaradó axiómáinak összefüggésében lenne

Az AC matematikai ekvivalensei a következők:

  • Tychonov-tétel (1930): a kompakt topológiai terek terméke kompakt. Ezt 1950-ben Kelley-ben igazolták az AC-vel. De a kompakt Hausdorff-tereknél ez egyenértékű a BPI-vel (lásd alább) és ennélfogva gyengébb, mint az AC
  • Löwenheim-Skolem-Tarski tétel (Löwenheim 1915, Skolem 1920, Tarski és Vaught 1957): Az első rendű mondatnak, amely kardinálissági modellt tartalmaz, minden olyan végtelen kardinális kardinalitás modelljével rendelkezik, amely μ olyan, hogy μ ≤ κ. Ezt Tarski az AC-vel egyenértékűnek bizonyította.
  • Kerin-Milman tétel: a valós normált lineáris tér duális B egységgömbének extrém pontja van, vagyis olyan, amelyik a B bármelyik vonalszegmensének belső pontja. Ez bebizonyosodott az AC-ről Bell és Fremlin 1972a-ban. Itt látható, hogy a nem nem halmazok bármely indexált A családja esetén természetes vonás van az A választási függvények és az A-ból épített valós, normált lineáris tér duális egységének gömbjeinek szélső pontjai között.
  • Minden elosztó rácsnak van egy maximális ideálja. Ez 1958-ban Klimovsky-ban bizonyult az AC-hez, 1972-ben pedig Bell és Fremlin készletek rácsaihoz.
  • Minden identitással rendelkező kommutációs gyűrűnek maximális ideálja van. Ezt Hodges 1979 bizonyította, hogy egyenértékű az AC-vel.

Az AC számos matematikai következménye, amelyekről ismert, hogy gyengébbek [14], különösen:

  • A logikai alap ideális tétel (BPI): minden logikai algebra rendelkezik egy maximális (vagy prime) ideállal. Kimutatták, hogy ez gyengébb, mint az AC Halpern és Levy 1971-ben.
  • A Boole-i algebrák kőreprezentációs tétele (Stone 1936): minden Boole-algebra izomorf egy halmazmezőhöz. Ez megegyezik a BPI-vel, és ennélfogva gyengébb, mint az AC
  • Kompaktium tétel az elsőrendű logikához (Gödel 1930, Malcev 1937, mások): ha az elsőrendű mondatok halmazának minden véges részhalmaza rendelkezik modellel, akkor a halmaznak is van modellje. Henkin 1954-ben kimutatták, hogy ez egyenértékű a BPI-vel, és ennélfogva gyengébb, mint az AC.
  • Az elsőrendű logika teljességének tétele (Gödel 1930, Henkin 1954): Az elsőrendű mondatok minden következetes halmazának van egy modellje. Ezt Henkin 1954-ben bizonyította, hogy egyenértékű a BPI-vel, és ennélfogva gyengébb, mint az AC. Ha a modell kardinalitását helyesen határozzuk meg, akkor az állítás egyenértékűvé válik az AC-vel.

Végül van

A Sikorski kiterjesztési tétel a logikai algebrákra (Sikorski 1949): minden komplett logikai algebra injektív, azaz bármely Boole algebra és B teljes Boole algebra esetében az A szubalgebrájának bármilyen homomorfizmusa kiterjeszthető az A egészére.

Az AC-vel való egyenértékűség kérdése a kevés fennmaradó érdekes nyitott kérdés ezen a területen; miközben egyértelműen azt jelenti BPI bebizonyosodott, független BPI Bell 1983.

Ezen tételek közül sokat Bell és Machover (1977) tárgyal.

5. A választás és logika axióma

Az AC és a logika közötti kezdeti kapcsolat akkor fordul elő, ha visszatérünk az AC3 megfogalmazásához a kapcsolatok szempontjából, nevezetesen: bármilyen bináris kapcsolat tartalmaz egy azonos tartományú funkciót. Az AC változata természetesen kifejezhető L másodrendű nyelven, különálló x, y, z,… változókkal és f, g, h,… függvényváltozókkal. L-ben a bináris kapcsolatokat az φ (x, y) képletek képviselik, két szabad egyedi változóval x, y. Az AC3 állítás L párja tehát

ACL:

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

Ez a mondatrendszer az AC szokásos logikai formája.

Zermelo az Axiom of Choice eredeti formája, az AC1, mondatrendszerként fejezhető ki az L megfelelően megerősített változatán belül. Ennek megfelelően feltételezzük, hogy L tartalmaz továbbá X, Y, Z,… predikátumváltozókat és F, G, H,… másodrendű függvényváltozókat. Itt egy F sorozatú függvényváltozót lehet alkalmazni egy X predikátumváltozóra, hogy egyedi FX kifejezést kapjunk. A mondatok rendszere

AC1L:

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

az AC1 közvetlen párja ebben a megerősített másodrendű nyelvben. Szóval, az AC1L azt állítja, hogy ha mindegyik predikátumnak van egy property tulajdonsága, akkor vannak predikátumokban olyan F függvény, hogy minden X predikátum számára, amely megfelel Φ, FX X példány. Itt a predikátumok a halmazok szerepét játsszák.

Mostanáig hallgatólagosan feltételeztük, hogy háttér-logikánk a szokásos klasszikus logika. Az AC és a logika közötti kapcsolat valódi mélysége azonban csak akkor válik nyilvánosságra, amikor az intuitív vagy konstruktív logika kerül a képbe. Figyelemre méltó tény, hogy ha csak az intuitív logika keretét és bizonyos enyhe további előfeltevéseket feltételezzük, akkor a Choice Axióma bebizonyíthatja, hogy magában foglalja a klasszikus logika kardinális szabályát, a kirekesztett középső törvényét - azt az állítást, hogy A ∨ ¬ A bármilyen ajánlat esetén. Pontosabban, az L kibővített nyelvünkben az intuitív logika szabályait felhasználva az [1] kirekesztett középső törvényt az AC1L- ből származtatjuk, amely a következő kiegészítő elvekkel társul:

Prediktív megértés:

∃ X ∀ x [X (x) ↔ φ (x)], ahol φ nem tartalmaz kötött függvényt vagy predikatív változókat.

A függvények kiterjesztése:

∀ X ∀ Y ∀ F [X ≈ Y → FX = FY], ahol X ≈ Y a ∀ x [X (x) ↔ Y (x)] rövidítése, vagyis X és Y kiterjesztése egyenértékű.

Két különálló személy:

0 ≠ 1, ahol 0 és 1 egyedi állandók.

Legyen A egy adott javaslat. A prediktív megértés révén bevezethetjük az U, V predátumállandókat az állításokkal együtt

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

Legyen Φ (X) X ≈ U ≈ X ≈ V képlet. Ezután egyértelműen állíthatjuk, hogy ∀ X [Φ (X) → ∃ x X (x)], így az AC1L kihívható ∃ F ∀ X [Φ (X) → X (FX)] érvényesítésére. Most bevezethetjük a K függési konstansot az állítással együtt

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

Mivel nyilvánvalóan ert (U) és Φ (V) állíthatunk, (2) pontból következik, hogy az U (KU) és V (KV) állításokat is végezhetjük, az (1) használatával,

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

A disztribúciós törvény alkalmazásával (amely az intuitív logikában is érvényes) az következik, hogy állíthatunk

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

A 0 ≠ 1 feltevésből ez következik

(3) A ∨ KU ≠ KV

érvényesíthető. Az (1) pontból azonban következik, hogy állíthatjuk A → U ≈ V-et, és így, a Funkciók Extensionalitása felhasználásával, A → KU = KV. Ez megmutatja a KU ≠ KV → ¬ A állíthatóságát, amely a (3) -val együtt viszont a

A ∨ ¬ A,

vagyis a kirekesztett középső törvény.

Az a tény, hogy a választás axióma magában foglalja a kirekesztett középpontot, első pillantásra ellentmond annak, hogy az előbbiet gyakran tekintik érvényes elvnek az intuitív logika által irányított konstruktív matematika rendszerekben, például Bishop konstruktív elemzése [17] és Martin. - Löf konstruktív típuselmélete [18], amelyben a Kizárt Közép nem áll fenn. Bishop szavaival: "A választási függvény létezik az építő matematikában, mert a választást a létezés lényege jelenti." Így például az ACL te x ∃ y φ (x, y) előzménye, megadva egy konstruktív construal-t, csak azt jelenti, hogy van egy olyan eljárásunk, amely minden x-re alkalmazva olyan ay-t eredményez, amelyre φ (x, y). De pontosan ezt fejezi ki az ACL következménye ∃ f ∀ x φ (x, fx).

A nehézség megoldására megjegyezzük, hogy az ACL1- ből való kizárás levonásakor alapvető fontosságú volt a függvények előrejelző megértése és kiterjeszthetősége elveinek alkalmazása [19]. Ebből következik, hogy az AC-t megerősítő konstruktív matematikai rendszerekben(de nem zárja ki a középtávot) sem a prediktív megértés elvének, sem a funkciók kiterjeszthetőségének elveinek nem kell teljesülnie. Noha a prediktív megértés elve konstruktív indoklással szolgálhat, a funkciók kiterjeszthetőségének elvét nem lehet ilyen igazolni. A predikátumok funkcióit intenzíven adják, és csak a megfelelõ intenzitás elvének felelnek meg ∀ X ∀ Y ∀ F [X = Y → FX = FY]. A kiterjeszthetőség elve könnyen meghiúsulhat, ha figyelembe vesszük például a P predikátumokat: racionális toll nélküli kétlábú és Q: emberi lény, valamint a predikátumok K funkcióját, amely minden egyes predikátumhoz rendeli a leírásban szereplő szavak számát. Akkor egyetérthetünk abban, hogy P ≈ Q, de KP = 3 és KQ = 2.

Az intuitionista halmozott elméletben (vagyis az intuícióra alapozott halmazelmélet, szemben a klasszikus logikával - ezt IST- ként rövidítjük) és a topos-elméletben a függvények prediktív megértése és kiterjeszthetősége (mindkettő megfelelően értelmezve) alapelvei érvényesek, tehát AC azt jelenti. Kizárt Közép. [20], [21]

Az AC-ből származó kirekesztett közeg származékát Diaconescu (1975) adta először kategóriaelméleti környezetben. Bizonyítéka lényegében eltérő ötleteket alkalmazott, mint a fentebb bemutatott; különösen nem alkalmazza az extenzivitás elveit, hanem egy objektum (vagy halmaz) hányadosának ötletét alkalmazza ekvivalencia relációval. Nevezetesen megfogalmazni a Diaconescu érvelését az IST- n belül. Ehhez hívjuk le egy A készlet U részhalmazát, ha van olyan A V részhalmaz, amelyre U ∩ V = ∅ és U ∪ V = A. A Diaconescu érvelése abból áll, hogy az állítás AC4-ből származik (lásd fent), hogy a halmaz minden részhalmaza leválasztható, ahonnan az Exkluzív középső könnyen következik. Itt van.

Először, adva U ⊆ A, az U mutatója (A-ban) g térkép: A × 2 → 2 kielégítő

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

Ezután könnyű megmutatni, hogy egy részhalmaz akkor és csak akkor válik szét, ha van indikátora.

Megmutatjuk, hogy ha az AC4 rendelkezik, akkor a készlet bármely részhalmazának van indikátora, és így leválasztható.

U ⊆ A esetén R legyen az A + A = A × {0} ∪ A × {1} bináris relációja, amelyet megadott:

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

Ellenőrizhető, hogy R ekvivalencia reláció. Írjunk r értéket az A + A és az A (A) A [22] Q hányadosa közötti természetes térképhez R-rel, amely az A + A minden tagját R-ekvivalencia osztályába hordozza.

Most alkalmazza az AC4-et, hogy megkapja az f: Q → A + A megfelelő f (X) ∈ X minden X ∈ Q térképét. Ezután nem nehéz megmutatni, hogy π 1- et írva az első koordinátára vetítéshez,

(*) n = 0, 1 és x ∈ A esetén, π 1 (f (r (x, n)) = x;

és

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

Most határozza meg g: A × 2 → 2 g = π 2

összeállít
összeállít

f

összeállít
összeállít

r értékkel, ahol π 2 a második koordináta vetülete. Akkor g az U mutatója, ahogy a következő ekvivalenciák mutatják:

x ∈ U f (r (x, 0)) = f (r (x, 1))… által (**)
π 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)))… a (*) gombbal
g (x, 0) = g (x, 1).

A bizonyítás teljes.

Megmutatható (Bell 2006), hogy számos intuitív szempontból érvénytelen logikai alapelv, beleértve a kirekesztett középső törvényt is (ekvivalens halmazelméletben) egyenértékű a választott axióma megfelelően gyengített változatával. Ennek megfelelően ezeket a logikus elveket választási alapelveknek tekinthetjük.

Íme a szóban forgó logikai alapelvek:

SLEM α ∨ ¬ α (α bármilyen mondat)
Lin (α → β) ∨ (β → α) (α, β bármilyen mondat)
¬ α ∨ ¬ α (α bármilyen mondat)
Volt ∃ x [∃ x α (x) → α (x)] (α (x) bármelyik képlet legfeljebb x szabad)
ENSZ ∃ x [α (x) → ∀ x α (x)] (α (x) bármely képlet legfeljebb x szabad)
Dis ∀ x [α ∨ β (x)] → α ∨ ∀ x β (x) (α bármilyen mondat, β (x) bármely képlet legfeljebb x szabad)

Az intuitív logikán túl a Lin, a Stone és az Ex a SLEM következményei; és Un azt jelenti, Dis. Mindezek a sémák természetesen a kizárt középérték teljes törvényéből fakadnak, azaz az önkényes képletekhez tartozó SLEM.

A következőkben az üres halmazt 0, {0} 1-gyel és {0, 1} -vel 2 jelöljük.

A következő választási alapelveket fogalmazzuk meg: itt X egy önkényes halmaz, Fun (X) az X tartományú függvényosztály és φ (x, y) a halmazelmélet nyelvének tetszőleges képlete, legfeljebb az x, y szabad változókkal.:

AC X ∀ x ∈ X ∃ y φ (x, y) → ∃ f ∈ Fun (X) ∀ x ∈ X φ (x, fx)
AC * X ∃ f ∈ Szórakozás (X) [∀ x ∈ X ∃ y φ (x, y) → ∀ x ∈ X φ (x, fx)]
DAC X ∀ f ∈ Szórakozás (X) ∃ x ∈ X φ (x, fx) → ∃ x ∈ X ∀ y φ (x, y)
DAC * X ∃ f ∈ Szórakozás (X) [∃ x ∈ X φ (x, fx) → ∃ x ∈ X ∀ y φ (x, y)]

Ezek közül az első két az AC formája az X számára; bár klasszikusan ekvivalens, az IST-ben az AC * X jelentése AC X, de nem fordítva. A DAC X és a DAC * X alapelvei az X által választott axióma kettős formái: klasszikusan mind egyenértékűek az AC X-rel és az AC * X-vel, de intuitív szempontból a DAC * X jelentése DAC X, és nem fordítva.

Megfogalmazjuk azt is a gyenge kiterjesztéses kiválasztási alapelvet, amelyben az α (x) és β (x) olyan képletek, amelyek legfeljebb az x változót mentesek:

WESP:

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

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

Ez az elv, a választott axióma egyértelmű következménye, azt állítja, hogy a 2 tagok bármelyik párhuzamos tulajdonságainak esetében az eseteket olyan tulajdonságokhoz lehet rendelni, amelyek éppen azok kiterjesztésétől függenek.

A fenti táblázatban szereplő logikai alapelvek egyenértékűek (az IST-ben) a választási elvekkel. Valójában:

  • A WESP és a SLEM azonosak az IST-vel szemben.
  • Az AC * 1 és Ex azonosak az IST-vel szemben.

Ezen túlmenően, bár a DAC 1 könnyen bebizonyítható, hogy bizonyítható az IST területén, megvan

A DAC * 1 és Un azonos az IST-vel szemben

Ezután, míg az AC 2 könnyen bebizonyítható az IST- ben, ezzel szemben

  • A DAC 2 és a Dis azonos az IST-vel.
  • Az IST -n túl a DAC * 2 egyenértékű Un-val, és így a DAC * 1-vel.

Annak érdekében, hogy a Lin-rel és Stone- nal egyenértékű választási sémákat biztosítsunk, bemutatjuk

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)], feltéve, hogy az IST-ben igazolható, hogy ∀ x [φ (x, 0) → ¬φ (x, 1)]

Világos, hogy ac * X egyenértékű

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

és hasonlóan a dac * X-hez.

Ezután, mint IST, AC * 1 és DAC * 1 egyenértékűek, illetve, hogy Lin és a .

Ezek az eredmények azt mutatják, hogy a választási elvek mélyen milyen kölcsönhatásba lépnek a logikával, amikor a háttérlogikának intuíciósnak tekintik. Egy klasszikus környezetben, ahol feltételezik a kirekesztett közép törvényét, ezek a kapcsolatok megszűnnek.

Azok az olvasók, akiket érdekel a választott axióma és a típuselmélet témája, beolvashatják a következő kiegészítő dokumentumot:

A választás és a típus elmélete

Bibliográfia

  • Aczel, P., 1978. "A konstruktív halmazelmélet típus-elméleti értelmezése", A. ManIntyre, L. Pacholski és J. Paris (szerk.), Logic Colloquium 77, Amszterdam: Észak-Holland, 55. oldal. -66.
  • ––– 1982. "A konstruktív halmazelmélet típus-elméleti értelmezése: választási elvek", AS Troelstra és D. van Dalen (szerk.), A LEJ Brouwer Centenary Symposium, Amszterdam: Észak-Holland, 1. oldal 40.
  • Aczel, P. és N. Gambino, 2002. "Gyűjtési alapelvek a függő típusú elméletben", P. Callaghan, Z. Luo, J. McKinna és R. Pollack (szerk.), Igazolások és programok típusai (Előadói megjegyzések a Computer Science, 2277. kötet), Berlin: Springer, 1-23.
  • ––– 2005. „A konstruktív halmazelmélet általánosított típus-elméleti értelmezése”, Journal of Symbolic Logic, 71/1: 67-103. [Előzetes nyomtatás elérhető online tömörített Postscript-ben]
  • Aczel, P. és Rathjen M., 2001. Megjegyzések a konstruktív készletelmélethez. Technikai jelentés 40, Mittag-Leffler Intézet, a Svéd Királyi Tudományos Akadémia. [On-line nyomtatás elérhető online]
  • Banach, S. és Tarski, A., 1924. "Sur la décomposition des ansembles de points for the pills for the attiecīgā congruentes", Fundamenta Mathematicae, 6: 244-277.
  • Bell, JL, 1983. "A Bikói algebrák Sikorski kiterjesztésének tételének erejéről", Journal of Symbolic Logic, 48: 841-846.
  • ––– 1988. Toposes és lokális elméletek: Bevezetés, Oxford: Clarendon Press, 1988.
  • –––, 1997. "Zorn lemma és teljes logikai algebrák intuitív típusú elméletekben", Journal of Symbolic Logic, 62: 1265-1279.
  • –––, 2003. "Zorn Lemma néhány új intuitív ekvivalense", Archive for Mathematical Logic, 42: 811-814.
  • –––, 2005. Elmélet: Boolean által értékelt modellek és függetlenségi bizonyítékok, Oxford: Clarendon Press.
  • ––– 2006. „Választási alapelvek az intuitív beállított elméletben”, A logikai megközelítés a filozófiához, Devidi, D. és Kenyon, T. (szerk.), Berlin: Springer: 36–44.
  • –––, 2008. „A választott axióma és a kirekesztett középső törvénye a gyenge halmazelméletekben.” Matematikai logikai negyedéves kiadvány.
  • Bell, JL és Fremlin, D., 1972. "A maximális ideális tétel a készletek rácsaihoz", a London Mathematical Society bulletin, 4: 1-2.
  • –––, 1972a. "A választott axióma geometriai alakja", Fundamenta Mathematicae, 77: 167-170.
  • Bell, JL és Machover, M., 1977. Matematikai logika tanfolyam. Amszterdam: Észak-Holland.
  • Bernays, P., 1942. "Az axiomatikus halmazelmélet rendszere, III. Rész," Journal of Symbolic Logic, 7: 65-89.
  • Bishop, E. és Bridges, D., 1985. Konstruktív elemzés, Berlin: Springer.
  • Blass, A., 1984. "Az alapok megléte magában foglalja a választott axiómát", az Axiomatic Set Theory-ban, Baumgartner, Martin és Shelah (szerk.) (Contemporary Mathematics Series, 31. kötet), American Mathematical Society, 31-33..
  • Bochner, S., 1928. "Fortsetzung Riemannscher Flachen", "Mathematische Annalen 98: 406-421.
  • Bourbaki, N., 1939. Elements de Mathematique, I. Livre: Theorie des Ensembles, Párizs: Hermann.
  • ––– 1950. "Zorn Sur le theoreme", Archiv dem Mathematik, 2: 434-437.
  • Cohen, PJ, 1963. "A kontinuum hipotézis függetlensége", Proceedings of the US National Academy of Sciemces, 50: 1143-48.
  • ––– 1964. "A kontinuumhipotézis II. Függetlensége", az USA Nemzeti Akadémia Sciemces, 51: 105-110.
  • ––– 1966. Set Theory and Continuum Hypotheis, New York: Benjamin.
  • Curry, HB és R. Feys, 1958. Kombinációs logika, Amszterdam: Észak-Holland.
  • Devidi, D., 2004. "Választási alapelvek és konstruktív logika", Philosophia Mathematica, 12/3: 222-243.
  • Diaconescu, R., 1975. "A választott és komplexáló axióma", Proceedings of the American Mathematical Society, 51: 176–8.
  • Fraenkel, A., 1922. "Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre", Mathematische Annalen, 86: 230-237.
  • Fraenkel, A., 1922a. "Über den Begriff" határozott "és az Unabhängigkeit des Auswahlsaxioms", Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physik-math. Klasse, 253-257. Fordítva van Heijenoort-ban, Frege-ról Gödel-re: Forráskönyv a matematikai logikában 1879–1931, Harvard University Press, 1967, 284–289.
  • Fraenkel, A., Y. Bar-Hillel és A. Levy, 1973 halmazelmélet alapjaihoz, Amsterdam: North-Holland, 2 nd edition.
  • Gödel, K., 1938. "A választott axióma és az általános kontinuum-hipotézis konzisztenciája", Proceedings of the US National Academy of Sciences, 24: 556-7.
  • Gödel, K., 1938. "Az általánosított kontinuum-hipotézis konzisztenciájának bizonyítéka", Proceedings of the US National Academy of Sciemces, 25: 220-4.
  • Gödel, K., 1940. A választás axiómájának és az általánosított kontinuum-hipotézisnek a meghatározott elmélet axiómáival való konzisztenciája, Matematika Tanulmányok, 3. szám, Princeton: Princeton University Press.
  • Gödel, K., 1964. "Megjegyzések a Princeton Bicentennial Conference előtt", The Undecidable, Martin Davis (szerk.), CITY: Raven Press, 84-88.
  • Goodman, N. és Myhill, J., 1978. "A választás magában foglalja a kizárt középső részt", Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 24/5: 461.
  • Grayson, RJ, 1975. "A halmozott megközelítés a halmazelmélet modelleire", M. Sc. értekezés, Oxfordi Egyetem Matematikai Tanszéke.
  • Halpern, JD és Levy, A., 1971. "A logikai próba ideális tétel nem jelenti a választott axiómát." Axiomatikus elmélet, Symposia Proceedings of Pure Mathematics, Vol. XIII. Rész, I. Amerikai Matematikai Társaság, 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. - Phys. Klasse, Sitzungberichte, 61: 297-334.
  • –––, 1914. Grundzüge der Mengenlehre, Lipcse: de Gruyter. Újra nyomtatva, New York: Chelsea, 1965.
  • –––, 1914a. "Bemerkung über den Inhalt von Punktmengen", Mathematische Annalen, 75: 428-433.
  • D. Hilbert, 1926. "Über das Unendliche", Mathematische Annalen, 95. Fordítva: J. van Heijenoort (szerk.) Frege-től Gödel-hez: Forráskönyv a matematikai logikában, 1879–1931, Cambridge, MA: Harvard University Press, 1967, 367-392.
  • Hodges, W., 1979. "Krull Zorn-ra utal", a London Mathematical Society, 19: 285-7.
  • Howard, P. és Rubin, JE, 1998. A választás axiómájának következményei, American Mathematical Society Surveys and Monographs, Vol. 59.
  • Howard, WA, 1980. "A képlet-típusú építés fogalma", JR Hindley és JP Seldin (szerk.), HB Curry: Esszék a kombinatorikus logikáról. Lambda kalkulus és formalizmus, New York és London: Academic Press, 479-490.
  • Jacobs, B., 1999. Kategorikus logika és típuselmélet, Amszterdam: Elsevier.
  • Jech, T., 1973. A Choice Axiom, Amszterdam: Észak-Holland.
  • Kelley, JL, 1950. "A Tychonoff-tétel tétele a választott axiómát vonja maga után", Fundamenta Mathematicae, 37: 75-76.
  • Klimovsky, G., 1958. "A Zorn-féle filozófia és a filozófia egy ötlete a maximális összegű és a későbbi elosztási cikkek elkészítéséhez", Revista de la Union Matematica Argentina, 18: 160-64.
  • Kuratowski, K., 1922. "A matematikai technikák nem átalakításának áttekintése", Fundamenta Mathematicae, 3: 76-108.
  • Lawvere, FW és Rosebrugh, R., 2003. Matematikai készletek, Cambridge: Cambridge University Press.
  • Lindenbaum, A. és Mostowski, A., 1938. "Über die Unabhängigkeit des Auswahlsaxioms und einiger seiner Folgerungen".
  • Maietti, ME, 2005. "A függő típusú elméletek és kategóriák közötti moduláris megfelelés, beleértve az pretopoit és a topoit," Matematikai struktúrák a számítógépes tudományban, 15/6: 1089-1145.
  • Martin-Löf, P., 1975. "Intuicionista típuselmélet; prediktív rész", HE Rose és JC Shepherdson (szerk.), Logic Colloquium 73, Amszterdam: Észak-Holland, 73-118.
  • ––– 1982. „Konstruktív matematika és számítógépes programozás”, LC Cohen, J. Los, H. Pfeiffer és KP Podewski (szerk.), Logika, módszertan és filozófia VI, Amszterdam: Észak-Holland, pp 153-179.
  • –––, 1984. Intuicionista típuselmélet, Nápoly: Bibliopolis.
  • –––, 2006. "Zermelo választott axiómájának 100 éve: mi volt a probléma ezzel?", A Computer Journal, 49/3: 345-350.
  • Mendelson, E., 1956. "A választott gyenge axióma függetlensége", Journal of Symbolic Logic, 21: 350-366.
  • ––– 1958. "Az alapkezelő axióma és a választott axióma", Arkiv fur Mathematische Logik und Grundlagenforschung, 4: 67-70.
  • –––, 1987. Bevezetés a matematikai logikába, CITY: Wadsworth & Brooks, 3. kiadás.
  • Moore, GH, 1982. Zermelo választási axióma, Berlin: Springer-Verlag.
  • Moore, RL, 1932 13.
  • Myhill, J. és Scott, DS, 1971. "Rendes meghatározhatóság", Axiomatikus elmélet. Symposia in Pure Mathematics, Vol. XIII. Rész, I. Amerikai Matematikai Társaság, 271–8.
  • Post, EL, 1953. "A transzfinit von Neumann-Gödel halmazelméleti halmazok definiálhatóságának szükséges feltétele, alkalmazva a folytonosság meghatározható, jól megrendelhető rendjének fennállására." Előzetes jelentés, az American Mathematical Society közleménye, 59: 246.
  • Ramsey, FP, 1926. "A matematika alapjai", Proceedings of the London Mathematical Society, 25: 338-84. Újra nyomtatva a Matematika és más esszé alapjaiban, DH Mellor, ed. London: Routledge, 2001.
  • Rubin, H. és Rubin, JE, 1985. A Choice II Axiom ekvivalensei, Amszterdam: Észak-Holland.
  • Rubin, H. és Scott, DS, 1954. "Néhány topológiai tétel, amely megegyezik az elsődleges ideális tételrel", Bulletin of the American Mathematical Society, 60: 389.
  • Russell, B., 1906. "A transzfinit számok és sorrendtípusok elméleti nehézségeiről", Proceedings of the London Mathematical Society, 4/2: 29-53.
  • Shoenfield, JR, 1955. "A választott axióma függetlensége", Journal of Symbolic Logic, 20: 202.
  • Sikorski, R., 1948. "Tétel a homomorfizmusok kiterjesztéséről", Annales de la Societé Polonaise de Mathématiques, 21: 332-35.
  • Solovay, R., 1970. "A halmazelmélet olyan modellje, amelyben minden reálkészlet Lebesgue mérhető", Annals of Mathematics, 92: 1-56.
  • Specker, E., 1957. "Zur Axiomatik der Mengenlehre (Fundierungs- und Auswahlaxiom)", Zeit. Math. 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. "A logikai algebrák reprezentációjának elmélete", Transactions of the American Mathematical Society, 40: 37-111.
  • Tait, WW, 1994. "A kirekesztett középső és a választott axióma törvénye", Mathematics and Mind, A. George (szerk.), New York: Oxford University Press, 45-70.
  • Takeuti, G., 1961. "Remarks on Cantor Absolute", Japán Mathematical Society Journal, 13: 197-206.
  • Tarski, A., 1948. "Két tétel axiomatikus és algebrai vonatkozásai a bíborosok összegére", Fundamenta Mathematicae, 35: 79-104.
  • Teichmuller, O., 1939. "Brauch der Algebraiker das Auswahlaxiom?" Deutsches Mathematik 4: 567-577.
  • Vitali, G., 1905. A probléma elhárítása a bűncselekményekkel kapcsolatban, Bologna: Tipp. 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. Fordítva: J. van Heijenoort (szerk.), Frege-ról Gödel-re: Forráskönyv a matematikai logikában, 1879–1931, Cambridge, MA: Harvard University Press, 1967, 139–141.
  • ––– 1908. Neuer Beweis für die Möglichkeit einer Wohlordnung, Mathematische Annalen, 65: 107–128. Fordítva: J. van Heijenoort (szerk.), Frege-ról Gödel-re: Forráskönyv a matematikai logikában, 1879–1931, Cambridge, MA: Harvard University Press, 1967, 183–198.
  • –––, 1908a. "Untersuchungen uber die Grundlagen der Mengenlehre", Mathematische Annalen, 65: 107-128. Fordítva: J. van Heijenoort (szerk.), Frege-ról Gödel-re: Forráskönyv a matematikai logikában, 1879–1931, Cambridge, MA: Harvard University Press, 1967, 199–215.
  • Zorn, M., 1935. Megjegyzés a transzfinit algebrában alkalmazott módszerről, Bulletin of the American Mathematical Society, 41: 667-70.

Egyéb internetes források

Ajánlott: