Axioma de l'elecció
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Axiome_du_choix.png/220px-Axiome_du_choix.png)
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Axiom_of_choice.svg/220px-Axiom_of_choice.svg.png)
L'axioma de l'elecció (AE) és un axioma de la teoria de conjunts. El va formular Ernst Zermelo a 1904 per formalitzar la seva demostració del teorema del bon ordre,[1] i aleshores va provocar una certa controvèrsia.
Estableix el següent:
- Sigui X una col·lecció de conjunts no buits. Llavors podem escollir un membre de cada conjunt de la col·lecció.
Més formalment seria:
Una altra formulació de l'axioma d'elecció estableix que:
- Donat un conjunt de conjunts disjunts (sense interseccions) no buits, existeix almenys un conjunt que té exactament un element en comú amb cadascun dels conjunts no buits.
En una sèrie de capses amb almenys un objecte a cadascuna, l'axioma estableix senzillament que es pot escollir un objecte de cada capsa. On hi ha la dificultat?
Bé, vegem-ne alguns exemples:
- Sigui X una col·lecció finita de conjunts no buits.
Aquí tot és senzill, i l'axioma d'elecció no és necessari, només cal seguir les regles de la lògica formal.
- Sigui X la col·lecció de tots els conjunts no buits dels nombres naturals {0, 1, 2, 3...}.
Llavors f pot ser la funció que escull el menor element de cada conjunt. Novament, l'axioma d'elecció no és necessari, ja que tenim una regla per escollir.
- Sigui X la col·lecció de tots els sub-intervals de (0, 1) amb longitud superior a 0.
Llavors f pot ser la funció que escull el punt mitjà de cada interval. Una altra vegada, l'axioma d'elecció no és necessari.
- Sigui X la col·lecció de tots els conjunts no buits dels nombres reals.
Llavors tenim un problema. No existeix cap definició òbvia de f, ja que la resta d'axiomes de la teoria de conjunts ZF no ordenen adequadament els nombres reals.
Aquí hi ha la clau de l'axioma. Només estableix que existeix alguna funció f que pot escollir un element de cada conjunt de la col·lecció. No dona cap indicació de com s'hauria de definir la funció, senzillament en manté l'existència. Els teoremes la prova dels quals inclou l'axioma d'elecció són sempre no constructius: postulen l'existència de quelcom sense indicar com obtenir-ho.
S'ha demostrat que l'axioma d'elecció és independent de la resta d'axiomes de la teoria de conjunts; és a dir, no es pot demostrar ni refutar. Això és el resultat del treball de Kurt Gödel i Paul Cohen. Així, no hi ha contradiccions, tant si s'accepta com si no s'accepta; tanmateix, la majoria dels matemàtics l'accepten, o bé n'accepten una versió feble, ja que així se'ls simplifica la feina.
Una de les raons per la qual a alguns matemàtics no els agrada particularment l'axioma d'elecció és que implica l'existència d'alguns objectes estranys no intuïtius. Un exemple d'això és la paradoxa de Banach-Tarski que conclou que és possible de "dividir" l'esfera tridimensional en un nombre de peces finit i, usant només rotació i translació, ajuntar les peces formant dues boles cadascuna amb el mateix volum que l'original. Cal notar que, com totes les proves que inclouen l'axioma d'elecció, no diu com cal fer-ho, només diu que es pot fer.
Un dels aspectes més interessants de l'axioma d'elecció és els llocs curiosos de les matemàtiques on surt. Així, hi ha un nombre remarcable d'afirmacions que són equivalents a l'axioma d'elecció. Els més importants són el lema de Zorn i el principi de bon ordenament: cada conjunt pot ser ben ordenat. (De fet, Zermelo va introduir inicialment l'axioma d'elecció per formalitzar la seva prova del principi de bon ordenament).
Crítica i acceptació
[modifica]Una demostració que necessita l'axioma de l'elecció pot establir l'existència d'un objecte sense definir l'objecte explícitament en el llenguatge de la teoria de conjunts. Per exemple, així com l'axioma de l'elecció implica que hi ha un bon ordre dels nombres reals, hi ha models de la teoria de conjunts amb l'axioma de l'elecció en què no es pot definir cap bon ordre individual dels nombres reals. De manera similar, tot i que es pot demostrar que el subconjunt dels nombres reals que no és Lebesgue mesurable existeix utilitzant l'axioma de l'elecció, és consistent que tal conjunt com aquest no és definible.[2]
L'axioma de l'elecció demostra l'existència d'aquests intangibles (objectes que es demostra que existeixen, però que no es poden construir explícitament), cosa que entra en conflicte amb alguns principis filosòfics.[3] Com que no tots els conjunts tenen un bon ordre canònic, una construcció que es basa en el bon ordre pot no produir un resultat canònic, fins i tot si es vol un resultat canònic (com és sovint el cas en la teoria de categories). Aquest punt ha estat utilitzat com a argument en contra de l'ús de l'axioma de l'elecció.
Un altre argument en contra de l'axioma de l'elecció és que implica l'existència d'objectes que poden semblar contraintuïtius.[4] Un exemple d'això és la paradoxa de Banach-Tarski, que afirma que és possible descompondre una bola unitària sòlida i tridimensional en un nombre finit de peces i, utilitzant només rotacions i translacions, tornar a muntar les peces formant dues boles sòlides cadascuna d'elles amb el mateix volum que l'original. Les peces en aquesta descomposició, construïdes utilitzant l'axioma de l'elecció, són conjunts no mesurables.
A més, recentment s'han assenyalat les conseqüències paradoxals de l'axioma de l'elecció per al teorema de no comunicació en física.[5]
Malgrat aquests resultats aparentment paradoxals, la majoria dels matemàtics accepten l'axioma de l'elecció com a principi vàlid a l'hora de demostrar nous resultats matemàtics. Però el debat és prou interessant com perquè es consideri destacable que un teorema en ZFC (ZF més AC) sigui lògicament equivalent (només amb els axiomes ZF) a l'axioma de l'elecció, i els matemàtics busquen resultats que requereixin que l'axioma de l'elecció sigui fals, tot i que aquest tipus de deducció és menys comú que el tipus que requereix que l'axioma de l'elecció sigui vàlid.
En matemàtiques constructives
[modifica]Com s'ha comentat, en la teoria clàssica de ZFC, l'axioma de l'elecció permet demostracions no constructives en què l'existència d'un tipus d'objecte es demostra sense que es construeixi un cas explícitament. De fet, en teoria de conjunts i en teoria de topos, el teorema de Diaconescu demostra que l'axioma de l'elecció implica el principi del tercer exclòs. El principi és doncs no accessible en la teoria constructiva de conjunts, en què s'utilitza lògica no clàssica.
La situació canvia quan el principi és formulat en la teoria de tipus intuicionista. En aquesta teoria i en l'aritmètica de Heyting d'ordre superior, l'afirmació correcta de l'axioma de l'elecció és (en funció del plantejament) inclosa com a axioma o demostrable com a teorema.[6] El motiu d'aquesta diferència és que l'axioma de l'elecció en teoria de tipus no té les propietats d'extensionalitat que sí que té l'axioma de l'elecció en la teoria constructiva de conjunts.[7]
Diferents principis d'elecció han estat profundament estudiats en els contexts constructius i l'estatus del principi varia entre diferents escoles i varietats de les matemàtiques constructives. Alguns resultats de la teoria constructiva de conjunts utilitzen l'axioma d'elecció numerable o l'axioma de l'elecció dependent, que no impliquen el principi del tercer exclòs. Errett Bishop, que és conegut per haver desenvolupat un marc per a l'anàlisi constructiva, va defensar que un axioma de l'elecció era constructivament acceptable, en les seves paraules
« | En les matemàtiques constructives la funció elecció existeix perquè el mateix significat d'existència ja implica l'elecció.[8] | » |
Tot i que l'axioma d'eleccions numerables en particular és sovint utilitzat en matemàtiques constructives, el seu ús també ha estat qüestionat.[9]
Citacions
[modifica]« | L'axioma d'elecció és òbviament cert, el principi de bon ordenament òbviament fals, i vés a saber si ho és el lema de Zorn? | » |
— Jerry L. Bona.[10] |
Es tracta d'una broma: tot i que els tres enunciats són matemàticament equivalents, molts matemàtics troben que l'axioma de l'elecció és intuïtiu, el principi de bon ordre és contraintuïtiu i el lema de Zorn massa complex per a la intuïció.
« | Cal l'Axioma de l'Elecció per seleccionar un conjunt a partir d'un nombre infinit de parelles de mitjons, però no un nombre infinit de parelles de sabates. | » |
— Bertrand Russell[11] |
L'observació aquí és que es pot definir una funció per seleccionar d'un nombre infinit de parelles de sabates, per exemple triant l'esquerra de cada parella. Sense l'axioma de l'elecció, no es pot assegurar que tal funció existeixi per parelles de mitjons, perquè un mitjó dret i un esquerre són (suposadament) indistingibles.
« | Tarski va intentar publicar el seu teorema [l'equivalèncie entre l'Axioma de l'Elecció i "tot conjunt infinit A té la mateixa cardinalitat que A × A", vegi's més amunt] a Comptes Rendus, però Fréchet i Lebesgue van rebutjar presentar-la. Fréchet va escriure que una implicació entre dues preposicions [certes] ben conegudes no és un resultat nou, i Lebesgue va escriure que una implicació entre dues proposicions falses no té cap interès. | » |
El matemàtic polonès-estatunidenc Jan Mycielski va relaciona aquesta anècdota en un articles de 2006 al Notices of the AMS.[12]
« | L'axioma no rep aquest nom perquè els matemàtics el prefereixin respecte d'altres axiomes. | » |
— A. K. Dewdney |
Aquesta cita ve del famós article de l'April Fools' Day en la columna computer recreations de la revista Scientific American, a l'abril de 1989.
Referències
[modifica]- ↑ Zermelo, Ernst «Beweis, dass jede Menge wohlgeordnet werden kann» (reprint). Mathematische Annalen, vol. 59, 4, 1904, pàg. 514–16. DOI: 10.1007/BF01445300. Arxivat 2016-01-17 a Wayback Machine.
- ↑ Fraenkel, A. A.; Bar-Hillel, Y.; Levy, A. Foundations of Set Theory (en anglès). Elsevier, 1973-12-01, p. 69-70. ISBN 978-0-08-088705-0.
- ↑ Rosenbloom, Paul C. The Elements of Mathematical Logic (en anglès). Dover Publications, Incorporated, 2005, p. 147. ISBN 978-0-486-44617-2.
- ↑ Dawson, J. W. (August 2006), "Shaken Foundations or Groundbreaking Realignment? A Centennial Assessment of Kurt Gödel's Impact on Logic, Mathematics, and Computer Science", Proc. 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pàg. 339–341, ISBN 978-0-7695-2631-7, DOI 10.1109/LICS.2006.47.
- ↑ Baumeler, Ämin; Dakić, Borivoje; Del Santo, Flavio «The Axiom of Choice and the No-Signaling Principle». arXiv, 2022. Arxivat de l'original el 2024-01-23. DOI: 10.48550/ARXIV.2206.08467 [Consulta: 25 maig 2024].
- ↑ Per Martin-Löf, Intuitionistic type theory Arxivat 2024-01-19 a Wayback Machine., 1980. Anne Sjerp Troelstra, Metamathematical investigation of intuitionistic arithmetic and analysis, Springer, 1973.
- ↑ Martin-Lof, P. «100 years of Zermelo's axiom of choice: what was the problem with it?» (en anglès). The Computer Journal, 49, 3, 19-12-2005, pàg. 345–350. Arxivat de l'original el 2024-04-22. DOI: 10.1093/comjnl/bxh162. ISSN: 0010-4620 [Consulta: 25 maig 2024].
- ↑ Errett Bishop i Douglas S. Bridges, Constructive analysis, Springer-Verlag, 1985.
- ↑ Richman, Fred. «Constructive Mathematics without Choice». A: Peter Schuster, Ulrich Berger, Horst Osswald (eds.). Reuniting the Antipodes - Constructive and Nonstandard Views of the Continuum (en anglès). Dordrecht: Springer Netherlands, 2001, p. 199–205. DOI 10.1007/978-94-015-9757-9_17. ISBN 978-94-015-9757-9. Arxivat 2024-05-25 a Wayback Machine.
- ↑ Krantz, Steven G. The Axiom of Choice (en anglès). Boston, MA: Birkhäuser Boston, 2002, p. 121–126. DOI 10.1007/978-1-4612-0115-1_9. ISBN 978-1-4612-6619-8. Arxivat 2024-05-25 a Wayback Machine.
- ↑ La metàfora de les sabates i els mitjons va ser introduïda l'any 1919 per Russell 1993, pàg. 125–127. Va suggerir que un milionari podria tenir ℵ0 parelles de sabates i ℵ0 parelles de mitjons.
« D'entre totes les sabates es poden distingir la dreta i l'esquerra, i per tant es pot fer la selecció d'una entre les dues, és a dir, es poden triar totes les sabates dretes o totes les sabates esquerres; però amb els mitjons no hi ha cap principi de selecció que se suggereixi a sí mateix, i no podem estar segurs, a no ser que assumim l'axioma multiplicatiu, que hi hagi cap classe formada per un mitjó de cada parella. » En general, Russell utilitzava el terme "axioma multiplicatiu" per referir-se a l'axioma de l'elecció. Sobre l'ordre d'un conjunt numerablement infinit de parelles d'objectes, va escriure:
« No hi ha cap dificultat a fer això amb les sabates. Les parelles són donades formant un ℵ0, i per tant com el cos d'una progressió. En cada parella, s'agafa la sabata esquerra primer i la dreta després, deixant inalterat l'ordre de la parella; d'aquesta manera obtenim una progressió de totes les botes. Però amb els mitjons hauríem de triar arbitràriament, de cada parella, quin posar abans; i un nombre infinit d'eleccions arbitràries és una impossibilitat. A no ser que puguem trobar una regla per seleccionar, és a dir, una relació que és un selector, no sabem ni tansols si la selecció és teòricament possible. » Russell llavors proposa utilitzar la ubicació del centre de masses de cada mitjó com a selector.
- ↑ Mycielski, Jan «A system of axioms of set theory for the rationalists» (
PDF) (en anglès). Notices of the American Mathematical Society, 53, 2, 2006, pàg. 206–213. Arxivat de l'original el 2021-07-26 [Consulta: 25 maig 2024].