En matemáticas , lógica y filosofía de las matemáticas , algo que resulta impredicativo es una definición autorreferencial . En términos generales, una definición es impredicativa si invoca (menciona o cuantifica) el conjunto que se define o (más comúnmente) otro conjunto que contiene lo 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.
Lo opuesto a la impredicatividad es la predicatividad, que esencialmente implica la construcción de teorías estratificadas (o ramificadas) donde la cuantificación de un tipo en un "nivel" da como resultado tipos en un nivel nuevo y 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 impredicabilidad. Los 'niveles' aquí corresponden al número de capas de dependencia en una definición de término.
La paradoja de Russell es un ejemplo famoso de construcción impredicativa, es decir, el conjunto de todos los conjuntos que no se contienen a sí mismos. La paradoja es que tal conjunto no puede existir: si existiera, se podría plantear la pregunta de si se contiene a sí mismo o no; si lo hace, entonces, por definición, no debería, y si no, entonces, por definición, debería.
El mayor límite inferior de un conjunto X , glb( X ) , también tiene una definición impredicativa: y = glb( X ) si y sólo si para todos los elementos x de X , y es menor o igual a x , y cualquier z menor que o igual a todos los elementos de X es menor o igual a y . Esta definición cuantifica sobre el conjunto (potencialmente infinito , dependiendo del orden en cuestión) cuyos miembros son los límites inferiores de X , uno de los cuales es el propio glb. Por tanto, el predicativismo rechazaría esta definición. [1]
Normas (que contienen una variable) que no definen clases propongo llamarlas no predicativas ; aquellos que sí definen clases los llamaré predicativos .
(Russell 1907, p.34) (Russell usó "norma" para referirse a una proposición: aproximadamente 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, conectándola con problemas de investigación pendientes en la actualidad. [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 de conjuntos legítimas. Los conjuntos que no cumplen el requisito se denominan impredicativos .
La primera paradoja moderna apareció con Una pregunta sobre números transfinitos [4] de Cesare Burali-Forti de 1897 y se conocería como la paradoja de Burali-Forti . Georg Cantor aparentemente había descubierto la misma paradoja en su "ingenua" teoría de conjuntos (de Cantor) y esto se conoció 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 sentencia ofensiva en Frege es la siguiente:
Por otro lado, 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 el propio f ? Russell rápidamente le escribió a Frege una carta señalando que:
Usted afirma ... que una función también puede actuar como elemento indeterminado. Esto lo creía antes, pero ahora este punto de vista me parece dudoso debido a la siguiente contradicción. Sea w el predicado: un predicado que no puede predicarse por sí mismo. ¿ Se puede predicar w por sí mismo? De cada respuesta se desprende su opuesto. Por tanto debemos concluir que w no es un predicado. Asimismo, no existe una clase (como totalidad) de aquellas clases que, tomadas cada una de ellas como totalidad, no se pertenecen a sí mismas. De esto concluyo que bajo ciertas circunstancias una colección definible no forma una totalidad. [7]
Frege rápidamente respondió a Russell reconociendo el problema:
Su descubrimiento de la contradicción me causó 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]
Si bien el problema tuvo consecuencias personales adversas para ambos hombres (ambos tenían trabajos en la imprenta que tuvieron que ser corregidos), van Heijenoort observa que "La paradoja sacudió el mundo de los lógicos, y los rumores todavía se sienten hoy... La paradoja de Russell , que utiliza las simples nociones 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 allí se analiza con gran detalle...". [9] Russell, después de seis años de comienzos en falso, finalmente respondería a la cuestión con su teoría de tipos de 1908 "proponiendo 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 variables aparentes no son superiores a los tipos de argumentos". [10] Pero este "axioma" encontró resistencia por todos lados.
El rechazo de los objetos matemáticos definidos de manera impredicativa (aunque se aceptan los números naturales tal como se entienden clásicamente) conduce a la posición en la filosofía de las matemáticas conocida como predicativismo, defendida por Henri Poincaré y Hermann Weyl en su Das Kontinuum . Poincaré y Weyl argumentaron que las definiciones impredicativas son problemáticas sólo 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" [ cita completa necesaria ] presenta una sección completa "b. Objeción relativa a la definición no predicativa " donde argumentó en contra de "Poincaré (1906, p. 307) [que establece 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". [11] Da dos ejemplos de definiciones impredicativas: (i) la noción de cadenas de Dedekind y (ii) "en análisis dondequiera que el máximo o mínimo de un conjunto "completo" previamente definido de números Z se utilice para inferencias adicionales. Esto sucede , por ejemplo, en la conocida prueba de Cauchy...". [12] Termina su sección con la siguiente observación: "Una definición puede muy bien basarse en nociones que son equivalentes a la que se está definiendo; de hecho, en toda definición definiens y definiendum son nociones equivalentes, y la estricta observancia de la exigencia de Poincaré hacer imposible toda definición y, por tanto, toda la ciencia". [13]
El ejemplo de Zermelo de mínimo y máximo de un conjunto de números "completo" previamente definido reaparece en Kleene 1952:42-42, donde Kleene utiliza el ejemplo del límite superior mínimo en su discusión sobre definiciones impredicativas; Kleene no resuelve este problema. En los párrafos siguientes analiza el intento de Weyl en su Das Kontinuum ( El Continuum ) 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 tienen un límite superior tiene un límite superior mínimo ( cf. también Weyl 1919)". [14]
Ramsey argumentó que las definiciones "impredicativas" pueden ser inofensivas: por ejemplo, la definición de "persona más alta de la habitación" es impredicativa, ya que depende de un conjunto de cosas de las que es un elemento, es decir, el conjunto de todas las personas en la habitación. habitación. En materia de matemáticas, un ejemplo de definición impredicativa es el número más pequeño de un conjunto, que se define formalmente como: y = min( X ) si y sólo si para todos los elementos x de X , y es menor o igual que x , y y está en X.
Burgess (2005) analiza con cierta extensión las teorías predicativas e impredicativas, 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ática .