Sobre proposicions formalment indecidibles de Principia Mathematica i sistemes relacionats

«Sobre proposicions formalment indecidibles de Principia Mathematica i sistemes relacionats» (en alemán: «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I») és un artícul sobre llògica matemàtica escrit per Kurt Gödel. L'artícul, en data de 17 de novembre de 1930, va ser publicat originalment en alemà en el volum de 1931 de Monatshefte für Mathematik. Existixen vàries traduccions impreses a l'anglés, i l'artícul ha segut inclós en dos coleccions d'artículs clàssics de llògica matemàtica. L'artícul conté teoremes que tenen vàries implicacions per a les proves de consistència en matemàtiques i tècniques que Gödel va inventar per a provar estes teoremes.

Resum i resultats clau

Artícul principal → Teoremes de incompletitud de Gödel.

Els resultats principals que establix l'artícul són el primer i segon teoremes de incompletitud, que tenen un enorme impacte en el camp de la llògica matemàtica. Estos apareixen com a teoremes Plantilla:Versalitas i Plantilla:Versalitas, respectivament, en l'artícul.

A fi de provar estos resultats, Gödel va introduir en l'artícul un método que es coneix com numeració de Gödel. En este método, a cada frase i prova formal en aritmètica de primer orde se li assigna un número natural particular. Gödel mostra que moltes propietats d'estes proves poden ser definides dins de qualsevol teoria d'aritmètica que siga suficientment robusta com per a definir les funcions de recursión primitiva. (La terminologia contemporànea de recursión i recursión primitiva encara no s'havia establit quan l'artícul va ser publicat; Gödel va usar a paraula rekursiv ('recursivo') para lo que hui es coneixen com a funcions de recursión primitiva.) Des de llavors, el método de numeració de Gödel s'ha tornat comuna en la llògica matemàtica.

Ya que el método de numeració de Gödel era nou, i per a evitar l'ambigüitat, Gödel va presentar una llista de 45 definicions formals explícites de funcions de recursión primitiva i relacions usades per a manipular i provar els números de Gödel. Ell va usar estos per a donar una definició explícita d'una fòrmula, Bew(x) que és verdadera si i només si x és el número Gödel d'una frase φ i existix un número natural que és el número Gödel d'una prova de φ (Beweis és la paraula alemana de "prova").

Una segona tècnica nova inventada per Gödel en este artícul va ser l'us d'oracions autorreferenciales. Gödel va mostrar que les paradoxas clàssiques de autorreferencia, com "Esta afirmació és falsa", poden ser reformulades com a afirmacions formals d'aritmètica. Informalmente, l'afirmació usada per a provar la primera teorema de incompletitud de Gödel diu "Esta afirmació no es pot provar". El fet de que dita autorreferencia puga ser expressada dins de l'aritmètica no era conegut fins que es va publicar l'artícul de Gödel; el treball independent d'Alfred Tarski en el seu Teorema de indefinibilidad de Tarski es va portar a terme aproximadament al mateix temps pero no va ser publicat sino fins a 1936.

En la nota al peu 48a, Gödel va afirmar que planejava una segona part de l'artícul que establiria un enllaç entre les proves de consistència i la teoria de tipos, pero Gödel no va publicar una segona part abans de la seua mort. No obstant, el seu artícul de 1958 en Dialectica va mostrar cóm la teoria de tipos pot ser usada per a donar una prova de consistència de l'aritmètica.

Traduccions publicades en anglés

Durant la vida de Gödel es varen imprimir tres traduccions a l'anglés de l'artícul, pero el procés va tindre vàries dificultats. La primera traducció a l'anglés va ser de Bernard Meltzer; va ser publicada en 1963 com una obra autocontenida de l'editorial Basic Books i ha segut reimpresa per Dover i per Hawking (God Created the Integers, Running Press, 2005:1097ff). La versió de Meltzer—descrita per Raymond Smullyan com una 'bona traducció'—va ser criticada negativament per Stefan Bauer-Mengelberg (Bauer-Mengelberg 1966). D'acort a la biografia de Gödel escrita per Dawson (Dawson 1997:216):

Fortunately, the Meltzer translation was soon supplanted by a better one prepared by Elliott Mendelson for Martin Davis's anthology The Undecidable; but it too was not brought to Gödel's attention until almost the last minute, and the new translation was still not wholly to his liking ... when informed that there was not clave enough to consider substituting another text, he declared that Mendelson's translation was 'on the whole very good' and agreed to its publication.3 [3 Afterward he would regret his compliance, for the published volume was marred throughout by sloppy typography and numerous misprints.]

Afortunadament, la traducció de Meltzer va ser ràpidament suplantada per una millor preparada per Elliott Mendelson per a l'antologia de Martin Davis, The Undecidable; pero tampoc se li va notificar a Gödel d'esta fins a casi l'últim minut, i la nova traducció encara no era del tot del seu agrade... quan se li va informar que no hi havia temps per a considerarsustituir un atre text, va declarar que la traducció de Mendelson era 'en lo general molt bona' i va accedir a la seua publicació.3[3 Despuix es llamentaria d'haver acceptat, perque el volum publicat estava estropejat en varis costats per tipografia descuidada i numerosos errors d'impressió.

La traducció de Elliott Mendelson apareix en la colecció The Undecidable (Davis 1965:5ff). Esta traducció també va rebre una crítica dura per Bauer-Mengelberg (1966), qui ademés de donar una llista detallada dels errors tipogràfics també va descriure lo que ell creïen ser errors sérios en la traducció.

Una traducció de Jean van Heijenoort apareix en la colecció From Frege to Gödel: A source book in Mathematical Logic (van Heijenoort 1967). Una resenya de 1972 d'Alonzo Church la va descriure com «la traducció més cuidadosa que ha segut feta» pero també va fer crítiques específiques de la mateixa. Dawson (1997:216) anota:

The translation Gödel favored was that by Jean van Heijenoort ... In the preface to the volume van Heijenoort noted that Gödel was one of four authors who had personally read and approved the translations of his works.

La traducció que Gödel va favorir va ser la de Jean van Heijenoort... En el prefacio al volum, van Heijenoort va notar que Gödel va ser un de quatre autors que havien llegit i aprovat personalment les traduccions de les seues obres.

Este procés d'aprovació va ser laboriós. Gödel va introduir canvis al seu text de 1931, i les negociacions entre els hòmens varen ser «prolongades»: «En privat van Heijenoort va declarar que Gödel era l'individu més obstinadamente fastidioso que havia conegut». Entre ells es «varen intercanviar un total de setanta cartes i es varen trobar dos voltes en l'oficina de Gödel per a resoldre qüestions sobre les subtilea en els significats i us de paraules en alemà i anglés». (Dawson 1997:216-217).

Encara que no és una traducció de l'artícul original, una útil quarta versió existix que «cobrix els tòpics de forma similar als que cobrix l'artícul original de 1931 de Gödel sobre la indecidibilidad» (Davis 1952:39), aixina com les extensions del mateix Gödel i el seu comentari sobre el tema. Açò apareix com On Undecidable Propositions of Formal Mathematical Systems (Davis 1965:39ff) i representa les conferències d'acort a la transcripció de Stephen Kleene i J. Barkley Rosser a mida que Gödel les pronunciava en l'Institut d'Estudis Alvançats en Princeton, Nova Jersey, en 1934. Dos pàgines de erratas i correccions adicionals de Gödel varen ser afegides per Davis a esta versió. Esta versió també és notable perque en ella, Gödel descriu per primera volta la sugerència de Herbrand que va donar orige a la forma general (és dir, la forma Herbrand-Gödel) de la recursión.

Bibliografia

• (1966).The Journal of Symbolic Logic.31(3)

484–494.

• (1972).The Journal of Symbolic Logic.37(2)

• (1965) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Dover. ISBN 0-486-43228-9.
• (2000) Engines of Logic: Mathematics and the Origin of the Computer, W. w. Norton & Company. ISBN 0-393-32229-7.

• (1931).Monatshefte für Mathematik und Physik.(38)doi:10.1007/BF01700692.
• (1958).Dialectica.12 Reimpreso en Gödel, Kurt (1990). Soloman Feferman et al. (ed.). Collected Works, Oxford University Press.
• (1967) From Frege to Gödel: A Source Book on Mathematical Logic 1879–1931, Harvard University Press.
• Gödel, Kurt (1962). On Formally Undecidable Propositions of Principia Mathematica and Related Systems., Basic Books. ISBN 0-486-66980-7.
• (1966).The American Mathematical Monthly.73(3)
• Dawson, John W. (1997). Logical Dilemmas: The Life and Work of Kurt Gödel, A. K. Peters. ISBN 1-56881-256-6.