En matemáticas , lógica y filosofía de las matemáticas , algo que es impredicativo es una definición autorreferencial . En términos generales, una definición es impredicativa si invoca (menciona o cuantifica sobre) el conjunto que se define, o (más comúnmente) otro conjunto que contiene la cosa que se define. No existe una definición precisa generalmente aceptada de lo que significa ser predicativo o impredicativo. Los autores han dado definiciones diferentes pero relacionadas.
El opuesto de la impredicatividad es la predicatividad, que esencialmente implica construir teorías estratificadas (o ramificadas) donde la cuantificación sobre un tipo en un "nivel" da como resultado tipos en un nuevo nivel superior. Un ejemplo prototípico es la teoría de tipos intuicionista , que conserva la ramificación (sin los niveles explícitos) para descartar la impredicatividad. Los "niveles" aquí corresponden al número de capas de dependencia en la definición de un término.
La paradoja de Russell es un ejemplo famoso de una construcción impredicativa, es decir, el conjunto de todos los conjuntos que no se contienen a sí mismos. La paradoja es que un conjunto de este tipo no puede existir: si existiera, se podría preguntar si se contiene a sí mismo o no: si lo hace, por definición no debería, y si no lo hace, por definición debería.
La máxima cota inferior de un conjunto X , glb( X ) , también tiene una definición impredicativa: y = glb( X ) si y solo si para todos los elementos x de X , y es menor o igual que x , y cualquier z menor o igual que todos los elementos de X es menor o igual que y . Esta definición cuantifica sobre el conjunto (potencialmente infinito , dependiendo del orden en cuestión) cuyos miembros son las cotas inferiores de X , siendo una de las cuales la propia glb . Por lo tanto, el predicativismo rechazaría esta definición. [1]
Propongo llamar normas (que contienen una variable) que no definen clases no predicativas ; las que sí definen clases las llamaré predicativas .
(Russell 1907, p.34) (Russell utilizó "norma" para significar una proposición: más o menos algo que puede tomar los valores "verdadero" o "falso".)
Los términos "predicativo" e "impredicativo" fueron introducidos por Russell (1907), aunque el significado ha cambiado un poco desde entonces.
Solomon Feferman ofrece una revisión histórica de la predicatividad, vinculándola con los problemas de investigación actuales más destacados. [2]
El principio del círculo vicioso fue sugerido por Henri Poincaré (1905-6, 1908) [3] y Bertrand Russell a raíz de las paradojas como un requisito para las especificaciones legítimas de los conjuntos. Los conjuntos que no cumplen el requisito se denominan impredicativos .
La primera paradoja moderna apareció con Una pregunta sobre números transfinitos de Cesare Burali-Forti de 1897 [4] y se conocería como la paradoja de Burali-Forti . Georg Cantor aparentemente había descubierto la misma paradoja en su teoría de conjuntos "ingenua" (de Cantor) y esto se conocería como la paradoja de Cantor . La conciencia de Russell sobre el problema se originó en junio de 1901 [5] con su lectura del tratado de lógica matemática de Frege , su Begriffsschrift de 1879 ; la oración ofensiva en Frege es la siguiente:
Por otra parte, también puede ser que el argumento sea determinado y la función indeterminada. [6]
En otras palabras, dada f ( a ), la función f es la variable y a es la parte invariante. Entonces, ¿por qué no sustituir el valor f ( a ) por f ? Russell le escribió rápidamente a Frege una carta en la que señalaba que:
Usted afirma... que una función también puede actuar como elemento indeterminado. Esto es lo que yo creía antes, pero ahora esta opinión me parece dudosa a causa de la siguiente contradicción. Sea w el predicado: ser un predicado que no puede predicarse de sí mismo. ¿Puede w predicarse de sí mismo? De cada respuesta se sigue su opuesto. Por lo tanto, debemos concluir que w no es un predicado. Asimismo, no hay ninguna clase (como totalidad) de aquellas clases que, cada una tomada como una totalidad, no se pertenecen a sí mismas. De esto concluyo que, bajo ciertas circunstancias, un conjunto definible no forma una totalidad. [7]
Frege respondió rápidamente a Russell reconociendo el problema:
Su descubrimiento de la contradicción me ha causado la mayor sorpresa y, casi diría, consternación, ya que ha sacudido la base sobre la que pretendía construir la aritmética. [8]
Aunque el problema tuvo consecuencias personales adversas para ambos hombres (ambos tenían obras en la imprenta que tuvieron que ser corregidas), van Heijenoort observa que "La paradoja sacudió el mundo de los lógicos, y sus retumbos todavía se sienten hoy... La paradoja de Russell, que utiliza las nociones simples de conjunto y elemento, cae de lleno en el campo de la lógica. La paradoja fue publicada por primera vez por Russell en Los principios de las matemáticas (1903) y se analiza allí en gran detalle...". [9] Russell, después de seis años de falsos comienzos, eventualmente respondería al asunto con su teoría de tipos de 1908 al "proponer su axioma de reducibilidad . Dice que cualquier función es coextensiva con lo que él llama una función predicativa : una función en la que los tipos de las variables aparentes no son superiores a los tipos de los argumentos". [10] Pero este "axioma" se encontró con resistencia de todos los sectores.
El rechazo de los objetos matemáticos definidos de manera impredicativa (mientras se aceptan los números naturales tal como se entienden clásicamente) conduce a la postura en la filosofía de las matemáticas conocida como predicativismo, defendida por Henri Poincaré y Hermann Weyl en su obra Das Kontinuum . Poincaré y Weyl argumentaron que las definiciones impredicativas son problemáticas solo cuando uno o más conjuntos subyacentes son infinitos.
Ernst Zermelo , en su obra de 1908 "Una nueva prueba de la posibilidad de un buen ordenamiento" [11], presenta una sección completa "b. Objeción concerniente a la definición no predicativa ", donde argumenta contra "Poincaré (1906, p. 307) [quien afirma que] una definición es 'predicativa' y lógicamente admisible sólo si excluye todos los objetos que dependen de la noción definida, es decir, que pueden ser determinados de alguna manera por ella". [12] Da dos ejemplos de definiciones impredicativas: (i) la noción de cadenas de Dedekind y (ii) "en el análisis dondequiera que el máximo o mínimo de un conjunto "completado" de números Z previamente definido se use para inferencias posteriores. Esto sucede, por ejemplo, en la conocida prueba de Cauchy...". [13] Termina su sección con la siguiente observación: "Una definición puede muy bien basarse en nociones que sean equivalentes a la que se define; de hecho, en cada definición definiens y definiendum son nociones equivalentes, y la estricta observancia de la exigencia de Poincaré haría imposible toda definición, y por lo tanto toda la ciencia". [14]
El ejemplo de Zermelo de mínimo y máximo de un conjunto de números "completo" definido previamente reaparece en Kleene 1952:42-42, donde Kleene utiliza el ejemplo del límite superior mínimo en su discusión de las definiciones impredicativas; Kleene no resuelve este problema. En los párrafos siguientes analiza el intento de Weyl en su Das Kontinuum ( El continuo ) de 1918 de eliminar las definiciones impredicativas y su fracaso en retener el "teorema de que un conjunto arbitrario no vacío M de números reales que tiene un límite superior tiene un límite superior mínimo (cf. también Weyl 1919)". [15]
Ramsey argumentó que las definiciones "impredicativas" pueden ser inofensivas: por ejemplo, la definición de "la persona más alta de la habitación" es impredicativa, ya que depende de un conjunto de cosas del que es un elemento, es decir, el conjunto de todas las personas en la habitación. En lo que respecta a las matemáticas, un ejemplo de una definición impredicativa es el número más pequeño de un conjunto, que se define formalmente como: y = min( X ) si y solo si para todos los elementos x de X , y es menor o igual que x , e y está en X .
Burgess (2005) analiza las teorías predicativas e impredicativas con cierta extensión, en el contexto de la lógica de Frege , la aritmética de Peano , la aritmética de segundo orden y la teoría de conjuntos axiomáticos .