Glosario para Filosof´ıa de las Matem´aticas Pablo Cobreros
[email protected] July 28, 2015 Abstract Una parte importante dentro de cualquier disciplina cient´ıfica es el manejo de un vocabulario t´ecnico. La intenci´on de este glosario es dar definiciones breves sobre nociones relativamente t´ecnicas que puedan aparecer a lo largo de la asignatura. Este glosario no sustituye los apuntes ni la participaci´ on en clase y no tiene sentido estudiarlo de memoria. Se trata de venir a ´el cuando alguna noci´on no est´e clara del todo. Ir´e completando este glosario poco a poco. Agradecer´ıa que adem´ as de los t´erminos que ya he incluido, me fuerais diciendo cu´ales os parece que deber´ıan estar aqu´ı. Otras sugerencias, sobre el modo de organizarlo, por ejemplo, tambi´en ser´an bienvenidas (de momento est´ a todo un poco desordenado...)
• Conjunto (noci´ on intuitiva). Colecci´on de elementos. Los conjuntos son extensionales en el sentido de que la identidad de un conjunto depende enteramente de su extensi´on, esto es, si los conjuntos A y B tienen los mismos elementos, entonces son el mismo conjunto (A ≡ B). Un conjunto se puede definir por extensi´ on (listando sus elementos) o por intensi´ on (seleccionando una propiedad de los elementos del conjunto). {2, 4, 6} y {x | x es par y x < 8} son el mismo conjunto. • Pertenencia.Es la relaci´on entre un elemento y el conjunto al que pertenece. a ∈ A se lee: ‘a pertenece (es un elemento de) A’. ¬(a ∈ A) suele escribirse a ∈ / A. No confundir con inclusi´on. • Inclusi´ on. Es una relaci´on entre conjuntos. A ⊆ B significa que todos los elementos de A son tambi´en elementos de B (formalmente, A ⊆ B ssi ∀x(x ∈ A ⊃ x ∈ B)). Dado que los conjuntos son extensionales, si A ⊆ B y B ⊆ A entonces A ≡ B. ¬(B ⊆ A) suele escribirse B 6⊆ A. No confundir con pertenencia. • Intersecci´ on. Es una operaci´on entre conjuntos. A ∩ B es el conjunto de los elementos que pertenecen a ambos, A y B. Formalmente, A ∩ B = {x|x ∈ A ∧ x ∈ B}. 1
• Uni´ on. Es una operaci´on entre conjuntos. A ∪ B es el conjunto de los elementos que pertenecen a al menos uno de A y B. Formalmente, A ∪ B = {x|x ∈ A ∨ x ∈ B}. • Conjunto potencia. Es una operaci´on sobre un conjunto. ℘(A) es el conjunto de todos los subconjuntos de A. Formalmente, ℘(A) = {x|x ⊆ A}. • Conjunto vac´ıo. Es el conjunto que no tiene elementos, denotado por ∅. Formalmente puede definirse como ∅ = {x|x ∈ A ∧ x ∈ / A} para cualquier conjunto A. Dado que los conjuntos son extensionales, hay un u ´nico conjunto vac´ıo. Adem´as, el conjunto vac´ıo es subconjunto de todo conjunto (incluido ´el mismo) pues siempre se cumple: ∀x(x ∈ ∅ ⊃ x ∈ A) para todo conjunto A. • Par ordenado. Un par ordenado es un conjunto de dos elementos con un orden (el orden importa). El par ha, bi es distinto del par hb, ai (por el contrario, {a, b} ≡ {b, a}). Una n-tupla ordenada, ha1 , . . . an i, es un conjunto de n elementos con un orden. •
B A.
Se escribe de esta manera el conjunto formado por todas las funciones de B en A ({f |f : B 7→ A}).
• Cardinal. La cardinalidad de un conjunto A, escrito |A|, es, intuitivamente, el tama˜ no de ese conjunto. |A| ≤ |B| ssi existe una funci´on biun´ıvoca de A a B. |A| = |B| ssi existe una correspondencia entre A y B. • Operaciones sobre cardinales. Podemos definir las operaciones aritm´eticas b´ asicas en t´erminos de operaciones entre conjuntos: – |A| + |B| = |A ∪ B| (uni´on) – |A| · |B| = |A × B| (producto cartesiano) – |A||B| = |B A| (B A) En el caso de conjuntos finitos, el resultado de aplicar la correspondiente operaci´ on aritm´etica a los n´ umeros que expresan el tama˜ no del conjunto es el mismo. Este segundo procedimiento, sin embargo, no se puede establecer para hacer afirmaciones de tama˜ no para conjuntos infinitos (pues ning´ un n´ umero natural expresa el tama˜ no de un conjunto infinito). • Predicado y relaci´ on. En l´ogica, el significado de el conjunto de objetos correspondiente a su extensi´on (esto es una idealizaci´on, pero funciona en muchos sentidos). Por ejemplo, el predicado ‘es hombre’ tiene como significado el conjunto de todos los hombres. Las relaciones 2
pueden entenderse tambi´en extensionalmente. En este sentido, una relaci´ on es un conjunto de pares ordenados. Por ejemplo, (el significado de) la relaci´ on ‘es madre de’ es el conjunto de todos los pares ordenados en los que el primer elemento del par es madre del segundo elemento (el par hLa Pantoja, Paquirr´ıni pertenece a la relaci´on ‘es madre de’, pero no el par hPaquirr´ın, La Pantojai). • Producto Cartesiano. Es una operaci´on entre conjuntos. El producto cartesiano A × B es el conjunto de todos los pares ordenados en los que el primer elemento del par es un elemento de A y el segundo un elemento de B, esto es A × B = {hx, yi|x ∈ A, y ∈ B}. El producto cartesiano A × A se escribe tambi´en A2 y, en general, An es n veces el producto de A. • Funci´ on. Una funci´ on f de un conjunto A a un conjunto B (f : A 7→ B) es una relaci´ on que empareja cada elemento de A con un u ´nico elemento en B. Como toda relaci´on, una funci´on de A a B se puede entender como un conjunto de pares en A × B. Si b es el elemento de B con que f empareja al elemento a de A se dice que b es ‘la imagen bajo f de a’, escrito, f (a). • Funci´ on biun´ıvoca. Una funci´on biun´ıvoca de A a B es una funci´on que no empareja distintos elementos de A con el mismo elemento en B; distintos elementos en A tienen distintas im´agenes en B bajo la funci´ on (esto es, si {a, b} ⊆ A y a 6= b entonces f (a) 6= f (b)). • Correspondencia. Una correspondencia entre A y B es una funci´on biun´ıvoca sobre la totalidad de B; es decir, no hay en B ning´ un elemento que no sea imagen bajo la funci´on de alg´ un elemento en A. • Relaci´ on reflexiva (en un conjunto A). Cuando todo elemento de A est´ a conectado consigo mismo por la relaci´on: ∀x ∈ A : Rxx o, alternativamente, ha, ai ∈ A para todo a ∈ A. • Relaci´ on sim´ etrica (en un conjunto A). Cuando para cualesquiera elementos a y b en A, si Rab entonces Rba. • Relaci´ on transitiva (en un conjunto A). Cuando para cualesquiera elementos a, b y c en A, si Rab y Rbc entonces Rac. • Relaci´ on de equivalencia (en un conjunto A). Relaci´on reflexiva, sim´etrica y transitiva. • Relaci´ on antisim´ etrica (en un conjunto A). Cuando para cualesquiera elementos a y b en A, si Rab y Rba entonces a = b.
3
• Ordenaci´ on parcial (de un conjunto A). Es una relaci´on reflexiva, transitiva y antisim´etrica en A. Se dice que es una ordenaci´ on porque los elementos de A pueden representarse llevando la relaci´on en una u ´nica direcci´ on. • Ordenaci´ on parcial lineal (de un conjunto A). Es una ordenaci´on parcial de A en la que, adem´as, se cumple que para cualesquiera elementos a y b de A o bien Rab o bien Rba. Como todos los elementos est´ an conectados por la ordenaci´on podemos representarla sobre una l´ınea. La relaci´ on ≤ sobre los n´ umeros naturales, por ejemplo, es una ordenaci´ on parcial lineal. • Elemento m´ınimo, elemento m´ aximo. Un elemento m´ınimo en una ordenaci´ on R de un conjunto A es un elemento de a de A tal que ¬∃xRxa. Un elemento m´aximo en una ordenaci´on R de un conjunto A es un elemento de a de A tal que ¬∃xRax. Una ordenaci´on lineal puede tener a lo sumo un elemento m´aximo y un elemento m´ınimo. • Ordenaci´ on densa (de un conjunto A). Una ordenaci´on lineal de A en la que para cualesquiera elementos distintos a y b de A, si Rab entonces hay un c distinto de a y b tal que Rac y Rcb (entre dos elementos cualesquiera de A siempre hay un tercero). • Corte (en una ordenaci´ on lineal de un conjunto A). Un corte en una ordenaci´ on lineal de un conjunto A es el formado por dos subconjuntos inf (A) y sup(A) de A tal que: inf (A) ∪ sup(A) ≡ A y ∀x∈inf (A) ∀y∈sup(A) Rxy. En cristiano: todos los elementos de inf (A) son “menores” (respecto a la ordenaci´on R) que cualquier elemento en sup(A) (por eso se dice que inf (A) es el conjunto “de abajo” y sup(A) el conjunto “de arriba”). Intuitivamente, un corte en un conjunto A linealmente ordenado por R consiste en separar en dos la l´ınea que representa la el modo en que R ordena los elementos de A. • Salto (tipo de corte). Un salto en (una ordenaci´on lineal de) A es un corte donde inf (A) tiene elemento m´aximo y sup(A) tiene elemento m´ınimo. • Hueco (tipo de corte). Un hueco en (una ordenaci´on lineal de) A es un corte donde ni inf (A) tiene elemento m´aximo ni sup(A) tiene elemento m´ınimo. • Corte continuo. Un corte continuo en (una ordenaci´on lineal de) A es un corte donde o bien inf (A) tiene elemento m´aximo pero sup(A) no tiene elemento m´ınimo o bien sup(A) tiene elemento m´ınimo pero inf (A) no tiene elemento m´aximo.
4
• N´ umeros naturales. Formados por el 0 y todos aquellos alcanzables a partir de 0 por un n´ umero finito de aplicaciones de la funci´on sucesor. Se suelen denotar con N. Est´an linealmente ordenados por ≤ con elemento m´ınimo y sin elemento m´aximo. Los u ´nicos cortes sobre los n´ umeros naturales (en su orden habitual) son los saltos . • N´ umeros enteros. Formados por los n´ umeros naturales y los enteros negativos. Se suelen denotar por Z. Ordenados linealmente por ≤ sin elementos m´ aximos o m´ınimos. Como los n´ umeros naturales, los u ´nicos cortes sobre los enteros (en su orden habitual) son los saltos. • N´ umeros racionales. Son los n´ umeros expresables como una fracci´on de enteros (pueden tener m´as de una expresi´on racional, por ejemplo, 1 2 umeros racionales pueden ex2 = 4 ). Se suelen denotar por Q. Los n´ presarse tambi´en con expansiones decimales, sin embargo, la expansi´on decimal de un n´ umero racional es peri´ odica (un n´ umero con expansi´on decimal no peri´ odica es irracional). Est´an linealmente ordenados por ≤ sin elementos m´ aximos o m´ınimos, pero esta vez densamente (entre dos racionales cualesquiera siempre hay un tercero). Por este motivo, los n´ umeros racionales no tienen saltos. Tienen cortes continuos pero tambi´en huecos. A pesar de estar densamente ordenados, su cardinalidad es ℵ0 . • N´ umeros reales. Son los n´ umeros expresables con una expansi´on decimal. Se suelen denotar por R. Los n´ umeros √ reales que no son expresables con una fracci´on de enteros, como 2, son llamados irracionales, no por nada, sino porque no se pueden expresar como una raz´ on (= fracci´ on) de enteros. Otro modo de caracterizar los n´ umeros irracionales es como aquellos cuya expansi´on decimal no es peri´odica. Est´ an ordenados por ≤ sin elementos m´aximos o m´ınimos lineal y densamente (por tanto no tienen saltos). A diferencia de los n´ umeros racionales, sin embargo, los reales s´olo tienen cortes continuos (de ah´ı que a la l´ınea real se le llame ‘el cont´ınuo’). Su cardinalidad es 2ℵ0 ; sin embargo desconocemos si hay alg´ un conjunto con cardinalidad entre los reales y los naturales (lo que s´ı sabemos es que esta cuesti´on es independiente de ZFC). Naturalemente, N ⊆ Z ⊆ Q ⊆ R. • A priori. El conocimiento puede entenderse como creencia verdadera justificada. La a prioricidad de un juicio tiene que ver con el tipo de justificaci´ on: se dice que un juicio es a priori cuando su justificaci´on no depende de ning´ un evento particular de la experiencia sensible. De otro modo el juicio es a posteriori. Kant argumenta que los juicios de la geometr´ıa y la aritm´etica son, aunque sint´eticos, a priori. • Anal´ıtico. De acuerdo con Kant, un juicio es anal´ıtico cuando el predicado est´ a contenido en lo significado por el sujeto. Por ejemplo, 5
‘Todo hombre soltero es no casado’ es anal´ıtico, pues ser no casado es, al menos, parte del significado de ‘soltero’. Son triviales en el sentido de que no pueden ampliar nuestro conocimiento del mundo (como mucho, nuestro conocimiento del idioma en que se formulen, el castellano en nuestro caso). La distinci´on entre anal´ıtico y sint´etico es, de acuerdo con Quine (1951), uno de los dos dogmas del empirismo. • Realismo (en Filosof´ıa de las Matem´ aticas). El realismo en Filosof´ıa de las Matem´ aticas es la doctrina que sostiene que los objetos matem´ aticos (o aquello de lo que habla el lenguaje matem´atico) tienen una existencia independiente de nuestra mente. La visi´on habitual asociada con el realismo es el platonismo que mantiene que estos objetos tienen una existencia separada de los objetos f´ısicos: son eternos, acausales y no forman parte del espacio-tiempo (existen en el “mundo de las ideas”). El realismo tiene como compa˜ neros naturales la objetividad del conocimiento matem´atico, el realismo en el valor de verdad, la diferencia entre cognoscibilidad y verdad matem´atica y la l´ ogica cl´ asica (sobre todo el principio de bivalencia). Esta posici´on es an´ aloga a la del realismo dentro del problema de los universales. • Idealismo (en Filosof´ıa de las Matem´ aticas) El idealismo en Filosof´ıa de las Matem´ aticas es una forma de oposici´on al realismo (de ah´ı que se incluya bajo la etiqueta de ‘antirrealismo’). Mantiene que los objetos matem´ aticos, aquello de lo que habla el lenguaje matem´atico, no tiene una existencia independiente de la mente. La visi´on habitual asociada con el idealismo es que los objetos matem´aticos son de alguna manera producidos por nuestra mente, un cierto tipo de construcciones mentales. Kant mantiene, por ejemplo, que las proposiciones de la geometr´ıa y de la aritm´etica describen (respectivamente) las intuiciones del espacio y el tiempo que son la forma de los sentidos externos e internos (respectivamente, otra vez). Brower rescata parte de la filosof´ıa de Kant en su propuesta intuicionista. El idealismo presenta ciertas ventajas a la hora de explicar la necesidad y la a prioricidad del conocimiento matem´atico. Tiene como compa˜ neros naturales la asimilaci´ on de cognoscibilidad y verdad matem´atica y el rechazo de parte de la l´ ogica cl´asica (como el principio de bivalencia y algunas inferencias asociadas). • Nominalismo (en Filosof´ıa de las Matem´ aticas). El nominalismo en Filosof´ıa de las Matem´aticas mantiene que no existen los objetos matem´ aticos (se opone, por tanto, de modo directo al realismo, de ah´ı que, como el idealismo, caiga bajo la etiqueta de ‘antirrealismo’). El nominalismo de t´erminos mantiene que, en el caso del lenguaje matem´ aticos, no existe distinci´on entre uso y menci´on. No est´a claro, sin embargo, que pueda deshacerse de esta manera del compromiso 6
con entidades abstractas. Una forma m´as radical de nominalismo es el nihilismo que mantiene que el lenguaje matem´atico no habla propiamente de nada. • Tipo e instancia Aunque se trata de una distinci´on intuitivamente clara, resulta dif´ıcil definirla. Un tipo es un caso general o abstracto y una instancia es una realizaci´ on particular. La distinci´on surge de modo natural en el uso del lenguaje. Por ejemplo, la palabra ‘hombre’ como tipo es una u ´nica palabra del castellano con m´ ultiples instancias (una instancia distinta, por ejemplo, en cada diccionario de la RAE). Hay, aparentemente, una gradaci´on en aquello que se cuenta como instancia. Podemos entender que una instancia de la palabra ‘hombre’ es una entidad f´ısica (como unas manchas en un papel, unos destellos en la pantalla del ordenador, unas ondas en el aire), pero tambi´en (y, me parece a m´ı que este es el modo de entenderlo) una instancia es un uso particular de la palabra. • Uso y menci´ on Habitualmente empleamos un t´ermino para hacer referir a una entidad no ling¨ u´ıstica. Por ejemplo, el uso de ‘Giorgione’ en (una proferencia o uso particular de) ‘Giorgione era un pintor italiano’ sirve para hacer referencia al pintor italiano. En ocasiones, sin embargo, un t´ermino puede adem´as hacer referencia a s´ı mismo como en ‘Giorgione fue llamado as´ı por su estatura’: en este caso, la referencia del pronombre ‘as´ı’ no es la referencia del t´ermino ‘Giorgione’ [el pintor italiano] sino el propio t´ermino. Para evitar la posible equivocaci´ on que puede surgir en estos casos hay que distinguir el uso de un t´ermino de su menci´on. En el lenguaje escrito podemos evitar la ambig¨ uedad empleando comillas para formar nombres para los t´erminos. As´ı, ‘Giorgione fue llamado as´ı por su estatura’ podr´ıa traducirse como ‘Giorgione fue llamado ‘Giorgione’ por su estatura’ (y no por ‘Giorgione fue llamado Giorgione por su estatura’ que dar´ıa lugar una especie de error categorial). • Bivalencia. De acuerdo con la l´ogica y sem´antica cl´asicas, toda oraci´ on enunciativa (fuera de casos de ambig¨ uedad), tiene un valor de verdad (verdadero o falso) y s´olo uno. • Aritm´ etica. Se suele entender por aritm´etica (o aritm´etica b´asica) la estructura formada por el conjunto N de los n´ umeros naturales con las funciones de sucesi´ on, suma y multiplicaci´on. Mientras que N denota el conjunto de los n´ umeros naturales, usaremos N para denotar la estructura de la aritm´etica. • Estructura. Una estructura matem´atica en general es un conjunto con un grupo de funciones y relaciones dentro de ese conjunto. De modo general, por tanto, especificaremos una estructura se˜ nalando su 7
universo, funciones y relaciones; por ejemplo A = (A, f, g, R). En este sentido la estructura de la aritm´etica es N = (N, 0, s, +, ·) (un objeto dentro de un conjunto, como el 0 en este caso, puede considerarse una funci´ on de 0 argumentos). En l´ ogica, una estructura A para un lenguaje L es un conjunto en el que se interpreta el vocabulario extral´ogico de L con funciones y relaciones dentro de este conjunto. Cuando se habla de una estructura en este sentido, se suele hablar tambi´en de ‘interpretaci´on’ para L o ‘modelo’ (aunque el t´ermino ‘modelo’ suele emplearse en un sentido m´ as espec´ıfico; ver “modelo”). Cuando se habla de una estructura para un lenguaje L, la estructura se suele especificar A = (A, I) donde A es el universo de la estructura y I es una funci´on que empareja cada elemento del vocabulario extral´ogico de L con un objeto, funci´ on o relaci´ on en A seg´ un la categor´ıa gramatical del elemento. N´ otese que ´este es s´ olo otro modo de hablar de estructuras, tal como se definieron en el primer p´arrafo (que es conveniente pues nos evita tener que especificar a cada paso qu´e estructuras son adecuadas a qu´e lenguajes). Si suponemos que un lenguaje L es el conjunto de f´ ormulas generadas por su vocabulario extral´ogico y que este conjunto est´ a ordenado: l10 , l20 . . . l11 , l21 . . . (las ls son las constantes, s´ımbolos de funci´ on o de relaci´ on; los super´ındices indican el n´ umero de argumentos) una interpretaci´on es una estructura del tipo adecuado a ese lenguaje: A = (A, a01 , a02 . . . a11 , a12 . . .) (las as son los objetos, funciones y relaciones en A; los super´ındices indican el n´ umero de argumentos). En este caso la funci´ on de interpretaci´on I queda definida por el orden de los elementos en el vocabulario de L y de las funciones y relaciones n = an . en A de modo que lm m • Modelo. En l´ ogica, un modelo para un conjunto de oraciones Γ de un lenguaje L es una estructura o interpretaci´on para L que hace verdadero a todos los elementos de Γ. A veces se emplea el t´ermino ‘modelo’ en el sentido m´as amplio de estructura o interpretaci´on para un lenguaje L. • Teor´ıa (en un lenguaje formal). Una teor´ıa en lenguaje formal es un conjunto de oraciones Γ de ´ese lenguaje. A veces se habla tambi´en de teor´ıa como un conjunto de oraciones Γ incluyendo todas las consecuencias l´ ogicas de Γ (la “clausura” de Γ bajo ). En un sentido m´as espec´ıfico, se suele hablar de ‘la teor´ıa de una estructura A’ (formulada en un lenguaje L), formalmente: T eo(A), entendiendo por esto el conjunto de oraciones verdaderas de un determinado lenguaje L para esa estructura. En este sentido, ‘la teor´ıa de A’ es, por definici´on, una teor´ıa completa. En determinados contextos el t´ermino ‘teor´ıa’ puede hacer referencia tambi´en a la idea m´as espec´ıfica de teor´ıa axiom´atica. 8
• Teor´ıa axiom´ atica. En t´erminos generales, una teor´ıa axiom´atica es un conjunto de enunciados formulados en un lenguaje formal (los axiomas de la teor´ıa) junto con un conjunto de reglas formales (un sistema deductivo) que nos permite construir demostraciones a partir de los axiomas. Debido a diversos avances dentro de las matem´aticas (como el descubrimiento de geometr´ıas no eucl´ıdeas, las paradojas dentro de la teor´ıa intuitiva de conjuntos) surgi´o la necesidad de elevar los est´ andares de rigor en el empleo del lenguaje matem´atico y hacer expl´ıcitas las reglas de inferencia empleadas en los razonamientos. Aunque muchos textos en matem´aticas, incluso dentro de las ramas ligadas a expresiones m´as formales como la teor´ıa de conjuntos, presentan sus resultados de un modo s´olo semi-formal, la axiomatizaci´ on de una teor´ıa es una especie de ideal presente en la pr´actica matem´ atica (Smith, 2007, 17-19). Lo siguiente es una definici´on m´as precisa de la noci´ on de teor´ıa axiom´ atica: T es una teor´ıa formal axiomatizada (e interpretada) s´olo si T est´ a expresada en un lenguaje formal (interpretado) hL, Ii, tal que es efectivamente decidible qu´e cuenta como una f´ ormula bien formada u oraci´on de L y cu´ales son las condiciones de verdad de tales oraciones, (ii) es efectivamente decidible qu´e oraciones son los axiomas de T y (iii) cuenta con un sistema deductivo tal que es efectivamente decidible si una determinada lista de f´ormulas de L se ajustan a las reglas de demostraci´on y, por tanto, (iv) es efectivamente decidible si una determinada lista de f´ormulas de L constituye una demostraci´on a partir de los axiomas de T . (Smith, 2007, 22-3) En esta definici´ on, L es un lenguaje formal e I una estructura o interpretaci´ on para L. Intuitivamente, una propiedad es efectivamente decidible si existe un procedimiento mec´anico (por ejemplo, un programa de ordenador) que puede decidir, en un n´ umero finito de pasos, si la propiedad se da o no se da en cualquier caso que se proponga (por ejemplo, (iii) significa que existe un programa de ordenador que, para una f´ ormula cualquiera de L puede decidir, en un n´ umero finito de pasos, si esa f´ ormula es uno de los axiomas de T ). Algunas veces nos convendr´a hablar de una teor´ıa axiom´atica como un conjunto de oraciones (igual que definimos T eo(N ) como el conjunto de oraciones de LA que son verdaderas en N ). Podemos pensar en, por ejemplo, la Aritm´etica de Peano como el conjunto de oraciones (AP, `), esto es, el conjunto de oraciones generado por los axiomas de AP m´ as un sistema deductivo adecuado para la l´ogica de primer orden. En este sentido, toda teor´ıa axiom´atica es una teor´ıa, pero no 9
al rev´es. La teor´ıa de la aritm´etica T eo(N ) es una teor´ıa en el sentido amplio, pero no es una teor´ıa axiom´atica (por el Primer teorema de incompletud de G¨ odel sabemos que este conjunto de oraciones no es recursivamente enumerable). • Independencia. Se dice que una oraci´on A es independiente de un conjunto de oraciones Γ cuando Γ 2 A y Γ 2 ¬A. [Comprobar si se habla de independencia en sentido deductivo]. Si A es independiente de Γ, la teor´ıa Γ∪{A} es m´as fuerte (tiene “m´as” consecuencias l´ogicas) que Γ. Si A es independiente de Γ y Γ es consistente, tanto Γ ∪ {A} como Γ ∪ {¬A} son consistentes. • Teor´ıa completa. Una teor´ıa (axiom´atica) est´a dise˜ nada para demostrar afirmaciones formulables en el lenguaje de la teor´ıa, L. Se dice que una teor´ıa es completa (a veces se dice que la teor´ıa es completa respecto a la negaci´ on) cuando para toda oraci´on A de L, o bien Γ ` A o bien Γ ` ¬A. En caso contrario, se dice que la teor´ıa es incompleta. En otras palabras, una teor´ıa incompleta es aquella para la que hay una oraci´ on A, del lenguaje de la teor´ıa, que es indecidible dentro de la teor´ıa: Γ 0 A o bien Γ 0 ¬A. No confundir con la completud de un sistema deductivo. • Teor´ıa consistente (consistencia). Un conjunto de oraciones Γ de un lenguaje L es inconsistente cuando Γ ` ⊥. Alternativamente, un conjunto de oraciones Γ es inconsistente cuando Γ ` A, para toda oraci´ on A de L (distintas definiciones pueden resultar no-equivalentes fuera de la l´ ogica cl´ asica). Un conjunto de oraciones Γ de un lenguaje L es consistente cuando no es inconsistente. Como una teor´ıa es, b´ asicamente, un conjunto de oraciones, se suele hablar de teor´ıa consistente o inconsistente. A veces se asume que una teor´ıa es un conjunto consistente de oraciones. La teor´ıa de una estructura A es, por definici´ on, consistente (al menos en l´ogica y sem´antica cl´asica). N´otese que la noci´ on de consistencia es una noci´on sint´ actica. • Consecuencia l´ ogica y deducci´ on. En general, dadas una f´ormula A y un conjunto de f´ ormulas Γ de un lenguaje L, se dice que A es una consecuencia l´ ogica de Γ, escrito Γ A, cuando no hay ninguna interpretaci´ on (o estructura) para L tal que todo elemento en Γ es verdadero y A es falsa (la consecuencia l´ogica se puede definir, m´as generalmente, como una relaci´ on entre conjuntos). Para que esta definici´on d´e lugar a una relaci´ on de consecuencia l´ogica en particular hay que especificar: qu´e lenguaje es L (proposicional? de primer orden? de segundo orden? con operadores modales? por ejemplo) y en qu´e consiste una estructura o interpretaci´ on para tal lenguaje (pueden las oraciones tomar
10
m´ as de un valor de verdad? c´omo se extiende el valor de verdad de las f´ ormulas at´ omicas al resto de f´ormulas?). Se dice que A es una consecuencia deductiva (en un cierto sistema deductivo) de Γ, escrito, Γ ` A, cuando existe una demostraci´on (en tal sistema). Las relaciones de consecuencia l´ogica () y consecuencia deductiva (`) son relaciones de naturaleza distinta. La primera es una relaci´on sem´ antica en el sentido de que es una relaci´on que depende de qu´e sucede a las distintas f´ormulas en las distintas interpretaciones. La segunda es una relaci´ on sint´ actica o formal, en el sentido de que la aplicaci´ on de las reglas del sistema deductivo depende exclusivamente de la forma de los enunciados. Gran parte del juego de la l´ogica y de las teor´ıas formales tiene que ver con la relaci´ on entre estas dos nociones y, m´as en general, entre sintaxis y sem´ antica – qu´e argumentos son v´alidos y cu´ales demostrables, qu´e es expresable y qu´e es capturable. La l´ ogica (cl´ asica) de primer orden es correcta y completa. • Sistema deductivo. Un sistema deductivo es un procedimiento formal para establecer demostraciones. Los sistemas deductivos son formales en el sentido (un poco vago) de que la aplicaci´on del procedimiento para construir las demostraciones no requiere ninguna comprensi´ on del significado de las f´ormulas involucradas en la demostraci´on, sino s´ olo el reconocimiento de la forma de las f´ormulas. Esta definici´on es muy vaga pero tiene que ser as´ı pues existen muchos tipos de sistemas deductivos distintos: los antiguos sistemas de pruebas lineales con un conjunto de axiomas y alguna regla de inferencia, los varios tipos de sistemas de deducci´on natural o los procedimientos de tableaux son algunos ejemplos. • Consecuencias m´ ultiples. Una generalizaci´on natural de la relaci´on de consecuencia l´ ogica es definirla como una relaci´on entre conjuntos de f´ ormulas (en lugar de como una relaci´on entre un conjunto y una f´ ormula). Sean Γ y ∆ conjuntos de f´ormulas de un lenguaje L. Γ ∆ ssi no hay una estructura en la que todas las f´ormulas en Γ son verdaderas y toda f´ormula en ∆ es falsa. Este estilo de definir la consecuencia l´ ogica empleando consecuencias m´ ultiples (adem´as de premisas m´ ultiples) tiene algunas ventajas, como la de poder expresar f´ acilmente algunos conceptos b´asicos. Por ejemplo, que un conjunto Γ no es satisfacible se puede representar: Γ ∅. El uso de conclusiones m´ ultiples suele ser habitual en los sistemas de deducci´on natural estilo Gentzen.
11
• Interpretaci´ on. Interpretar es, intuitivamente, asignar significados a un conjunto de expresiones. En l´ogica una interpretaci´on es una asignaci´ on de “significados” a las expresiones del vocabulario extral´ogico (asignando, de esta manera, un valor de verdad a las oraciones at´omicas del lenguaje). El truco en l´ogica es que la idea de intepretaci´ on debe especificarse con precisi´on matem´atica. Lenguajes distintos podr´an tener distintas especificaciones de la idea de interpretaci´on. Por ejemplo, una interpretaci´ on (cl´asica) para el lenguaje proposicional es una funci´ on del conjunto de variables proposicionales al conjunto de “valores de verdad” (I : V P 7→ {1, 0}). Una interpretaci´on (cl´asica) para un lenguaje de primer orden es una estructura, hD, Ii, donde D es un conjunto no vac´ıo de objetos e I una funci´on que empareja cada expresi´ on del vocabulario no-l´ogico con “objetos” adecuados a la categor´ıa gramatical de la expresi´on: a las constantes (o variables) les asignar´ a objetos en D, a las funciones de n argumentos, funciones de n D en D y a las relaciones de n argumentos, funciones de Dn a {1, 0}. • F´ ormula y oraci´ on. Una f´ormula (tambi´en f´ormula bien formada o, abreviadametne, fbf) de un lenguaje L es una secuencia de signos del vocabulario de L que se ajusta a las reglas gramaticales del lenguaje. En un lenguaje de primer orden una f´ormula puede contener variables libres, como en ∃y(y + y = x) o no contener variables libres, como en ∀x∀y(x = y ⊃ (f (x) ⊃ f (y)). Las primeras se llaman simplemente f´ ormulas (o f´ormulas abiertas), las segundas oraciones (o f´ ormulas cerradas). En general (en sem´antica cl´asica, particularmente), las oraciones son verdaderas o falsas en una interpretaci´on. Las f´ ormulas abiertas no son, propiamente, verdaderas o falsas en una interpretaci´ on sino satisfechas por un conjunto de objetos (o por un conjunto de secuencias de objetos si tiene m´as de una variable libre) en una interpretaci´ on. Por ejemplo, la f´ormula ∃y(y + y = x) en la interpretaci´ on en que el s´ımbolo ‘+’ es interpretado con la suma sobre los n´ umeros naturales, ser´a satisfecha por los n´ umeros que sean pares. En este sentido ´esa f´ ormula expresa, en esa interpretaci´on, el conjunto de los pares. • ω-consistente (teor´ıa aritm´ etica). Una teor´ıa aritm´etica es una teor´ıa axiom´ atica cuya intenci´on es capturar en unos pocos axiomas determinadas nociones aritm´eticas como los n´ umeros naturales, las sucesi´ on, la suma y la multiplicaci´on (ver, por ejemplo, aritm´etica de Peano). • Teor´ıa (axiom´ atica) correcta. Una teor´ıa T es correcta (respecto a una estructura N ) ssi los axiomas de T son verdaderos en N y el sistema deductivo es tambi´en correcto. Existen sistemas deductivos para la l´ ogica de primer orden completos y correctos, y, por lo que 12
podemos decir, los axiomas de la Aritm´etica de Peano son verdaderos en la estructura de la Aritm´etica. En tal caso, la Aritm´etica de Peano es una teor´ıa correcta (en ingl´es se emplea la palabra ‘sound’). O al menos eso parece, otro asunto es si podemos demostrarlo (segundo Teorema de Incompletud). • Representaci´ on. Se dice que un conjunto de oraciones Γ representa una estructura A cuando A es un modelo de Γ. Un conjunto de oraciones, o teor´ıa, puede representar una estructura con mayor o menor precisi´ on (dependiendo de cu´anto se parezcan los modelos de la teor´ıa). Los lenguajes de primer orden (en verdad, un lenguaje l´ogico en general) no puede discriminar estructuras m´as all´a del isomorfismo; es decir para cualquier conjunto de oraciones Γ de un lenguaje de primer orden, si Γ tiene una estructura A como modelo, tiene como modelo toda otra estructura B isomorfa con A. La m´axima precisi´on, por tanto, con que una teor´ıa puede representar una estructura es hasta el isomorfismo (se dice entonces que tal teor´ıa es categ´orica). Toda teor´ıa categ´ orica es completa pero no toda teor´ıa completa (en un lenguaje de primer orden) es categ´orica. Una teor´ıa completa (en un lenguaje de primer orden) con un modelo finito es categ´orica (pues, en la l´ogica de primer orden, las estructuras finitas son representables hasta el isomorfismo (Zalabardo, 2002, buscar)). Sin embargo, ninguna teor´ıa en un lenguaje de primer orden con un modelo infinito es categ´orica (ver Teoremas de L¨ owenheim-Skolem y modelos no est´andar de la Aritm´etica). • Teor´ıa categ´ orica. Una teor´ıa categ´orica es una teor´ıa que tiene modelos y todos sus modelos son isomorfos. Se dice que la teor´ıa representa sus modelos hasta el isomorfismo (o que tiene un u ´nico modelo “hasta el isomorfismo”). • Numeraci´ on de G¨ odel. Una teor´ıa axiom´atica como la Aritm´etica de Peano est´ a dise˜ nada para expresar y demostrar afirmaciones aritm´eticas, esto es, afirmaciones sobre los n´ umeros naturales. Una de las ideas geniales de G¨ odel en su famosa demostraci´on es que una teor´ıa axiom´ atica, como la Aritm´etica de Peano, es un objeto matem´atico m´ as (esta idea, por cierto, est´a de alg´ un modo presente en la idea de Hilbert de que la metamatem´ atica es una rama de las matem´aticas). Aunque la Aritm´etica de Peano est´e dise˜ nada para hablar de n´ umeros, G¨ odel idea un procedimiento para codificar afirmaciones acerca de la propia Aritm´etica en t´erminos de n´ umeros naturales y propiedades o relaciones entre n´ umeros naturales. De este modo, una teor´ıa aritm´etica que sea capaz de expresar y/o demostrar suficientes afirmaciones sobre la aritm´etica podr´a, a trav´es de la codificaci´on, expresar y/o demostrar afirmaciones acerca de la propia teor´ıa. Impresionante. 13
Existen muchas maneras de codificar, dentro de una teor´ıa, afirmaciones acerca de la teor´ıa; a estas codificaciones se les suele llamar ‘numeraci´ on de G¨ odel’ (G¨ odel numbering), no necesaria y exclusivamente a la empleada por G¨odel en 1931. En t´erminos generales, una numeraci´ on de G¨ odel es una funci´on biun´ıvoca f : exp 7→ N, esto es, una funci´ on biun´ıvoca del conjunto de expresiones del lenguaje L de la teor´ıa al conjunto de los n´ umeros naturales. Esta funci´on asignar´ a distintos n´ umeros a los s´ımbolos de L, a secuencias de s´ımbolos de L, y a secuencias de secuencias de s´ımbolos de L. De este modo, a cada s´ımbolo corresponder´a un c´odigo (code), a cada secuencia de s´ımbolos (por tanto, a cada f´ormula) un c´odigo y a cada secuencia de secuencias de s´ımbolos (y por tanto, a cada demostraci´on) un c´odigo. Resulta fundamental que esta funci´on tenga ciertas propiedades, en particular, que se trate de un funci´on recursiva (en la prueba original de G¨ odel, como ahora se les llama, las funciones son recursivas primitivas). Esto significa, a grandes rasgos, que el procedimiento para encontrar el c´ odigo para una f´ormula (o secuencia de f´ormulas) envuelve una b´ usqueda acotada, un b´ usqueda restringida a un n´ umero finito de casos, y, por tanto, algo que en principio podr´ıa realizar un programa de ordenador. El procedimiento para encontrar, a partir de un code, la f´ ormula (o secuencia de f´ormulas) correspondiente, si es que hay alguna, tambi´en debe ser de este tipo. Una teor´ıa como la Aritm´etica de Peano es capaz de expresar (e incluso capturar) cualquier funci´ on de este tipo. Por tanto, la Aritm´etica de Peano podr´a expresar (y demostrar), por ejemplo, si cierto n´ umero es el code de una f´ormula del lenguaje de la teor´ıa o si para un determinado par de n´ umeros (n, m) n codifica una secuencia de f´ormulas que constituyen una demostraci´ on de m dentro de la teor´ıa (m´as brevemente: si n es una demostraci´ on de m). M´ as concretamente y a modo de ejemplo presentamos r´apidamente la numeraci´ on de G¨ odel empleada en el libro de Peter Smith (Smith, 2007, 124-7). Asignamos a cada expresi´on del vocabulario un c´ odigo b´ asico (n´ umeros pares a las variables, n´ umeros impares ≤ 27 al resto de expresiones): ¬ 1
∧ 3
∨ 5
⊃ 7
≡ ∀ ∃ 9 11 13
= ( ) 0 s + · x y z... 15 17 19 21 23 25 27 2 4 6 . . .
A cada secuencia de signos del lenguaje le asignamos un n´ umero de acuerdo al siguiente procedimiento: Sea e la expresi´ on de L formada por la secuencia s0 s1 s2 . . . sk , el n´ umero de G¨ odel de e (escrito g.n(e)) es el resultado de multiplicar la exponenciaci´on de los primeros k n´ umeros pri14
mos elevados, por orden, a la potencia correspondiente a cada c´ odigo b´ asico de cada si en la secuencia. En otras palabras, si para cada si el c´odigo b´asico ci , entonces, g.n(e) = 2c1 · 3c2 · 5c3 . . . πkck Por ejemplo, el n´ umero de G¨odel de ss0 = 223 · 323 · 521 (este n´ umero es considerablemente grande: que la funci´on sea primitiva recursiva no significa que la computaci´on se realice r´apidamente, s´olo que es posible realizarla, aunque tengamos que tengamos que esperar varias veces la edad del universo hasta obtener el resultado...) Si asumimos que las demostraciones en el sistema deductivo de nuestra teor´ıa son secuencias de f´ormulas (´este es el caso, por ejemplo, de las demostraciones en sistemas axiom´aticos estilo Hilbert) una demostraci´ on podr´ a codificarse como una secuencia de f´ormulas en las que cada f´ ormula es, o bien un axioma, o bien una f´ormula que se puede obtener de los axiomas de la teor´ıa aplicando (cuantas veces sea necesario) las reglas de inferencia. Podemos codificar secuencias de secuencias de f´ ormulas empleando el mismo procedimiento: Supongamos que e1 e2 . . . en es una secuencia de f´ormulas de L. Aplicamos nuestro procedimiento de codificaci´on para asignar a cada elemento ei en la secuencia el correspondiente n´ umero de G¨ odel gi , obteniendo una secuencia de n´ umeros de G¨ odel: g1 g2 . . . gn A continuaci´ on codificamos esta secuencia repitiendo el mismo patr´ on que antes para dar lugar a un u ´nico “super”-n´ umero de G¨ odel: 2g1 · 3g2 · 5g3 . . . πngn A trav´es de este procedimiento podemos expresar y/o demostrar en el lenguaje propiedades acerca del lenguaje y la teor´ıa a trav´es de su codificaci´ on. Por ejemplo, podemos encontrar una f´ormula de L T erm(x) con una variable libre que ser´a verdadera de un n´ umero n exactamente cuando n sea el n´ umero de G¨odel de un t´ermino de L. De hecho, la funci´ on correspondiente a T erm(x) (para esta numeraci´on de G¨ odel y cualquiera que sea tan razonable como ´esta (Smith, 2007, 126)) es una funci´ on recursiva primitiva. Este u ´ltimo asunto es importante, ya que una teor´ıa como la Aritm´etica de Peano (en verdad, teor´ıas m´as modestas, como la Aritm´etica de Robinson) tiene el suficiente poder expresivo y de demostraci´on, no s´olo para expresar, sino tambi´en para
15
capturar todas las funciones recursivas primitivas. Un asunto central en la demostraci´ on de G¨odel es que la siguiente funci´on: P rf (m, n) ssi m es el “super”-n´ umero de G¨odel de una demostraci´on de la oraci´ on con n´ umero de G¨odel n es recursiva primitiva. • Diagonalizaci´ on • Aritm´ etica de Robinson, Q. La Aritm´etica de Robinson Q es una teor´ıa aritm´etica formulada en el mismo lenguaje que la Aritm´etica de Peano LA y que es un subsistema de ´esta: para todo A en LA , Si Q ` A entonces AP ` A pero no en la otra direcci´on (brevemente: AP puede demostrar m´ as cosas que Q). Los axiomas de la Aritm´etica de Robinson son ligeramente distintos de los de la Aritm´etica de Peano ((Smith, 2007, c. 8)); crucialmente, la Aritm´etica de Robinson no tiene el (esquema de) axioma de inducci´on de AP. Por este motivo, el “poder demostrativo” de la Aritm´etica de Robinson es muy d´ebil; por ejemplo Q 0 ∀x(0 + x = 0) de modo que esta teor´ıa es “aburridamente” incompleta. Lo que hace que la Aritm´etica de Robinson sea interesante es el hecho de que, a pesar de ser deductivamente pobre en el sentido se˜ nalado, es deductivamente poderosa en otro sentido; particularmente, las funciones recursivas primitivas se pueden capturar dentro de esta teor´ıa. Este hecho muestra los supuesto tan modestos sobre los que se apoyan los teoremas de incompletud de G¨odel. • Aritm´ etica Baby. La “aritm´etica baby” AB es una teor´ıa aritm´etica formulada en el lenguaje que resulta de eliminar los cuantificadores en LA . Como su lenguaje no tiene cuantificadores, para formular la teor´ıa empleamos esquemas de axiomas en lugar de axiomas propiamente (es decir, AB incluye todas las instancias formulables en su lenguaje de los siguientes axiomas): 1 0 6= Sζ 2 Sζ = Sξ → ζ = ξ 3 ζ +0=ζ 4 ζ + Sξ = S(ζ + ξ) 5 ζ ·0=0 6 ζ · Sξ = (ζ · ξ) + ζ AB s´ olo puede demostrar cuestiones acerca de n´ umeros particulares, no generalizaciones. Por este motivo, tambi´en, AB es una teor´ıa completa (a diferencia de Q o AP). Intuitivamente: cualquier cuesti´on particular acera de n´ umeros, por grande que sean, se puede solucionar a trav´es de una b´ usqueda acotada a un n´ umero finito de casos. 16
• Teor´ıa aritm´ etica. El lenguaje de la aritm´etica LA es un lenguaje de primer orden (aunque no en el caso de la aritm´etica baby) con identidad con una constante, un s´ımbolo de funci´on de un argumento y dos s´ımbolos de funci´ on de dos argumentos. Cualquier estructura A = (A, f10 , f21 , f32 , f42 ) proporciona una interpretaci´on para este lenguaje. Una teor´ıa aritm´etica es un conjunto de oraciones dentro de este lenguaje dise˜ nados para representar la estructura de la aritm´etica N = (N, 0, s, +.·); es decir, un conjunto de oraciones de LA que tenga como modelo exactamente la estructura de la aritm´etica. Por este motivo, especificaremos el vocabulario no l´ogico de LA : {0, S, +, ·} (en recuerdo de la intenci´ on de las teor´ıas aritm´eticas de capturar estas nociones); sin embargo, hay que tener muy claro que una cosa son los t´erminos, s´ımbolos de funci´on y de predicado de LA y otra los objetos, funciones y relaciones en N . Existen muchas teor´ıa aritm´eticas que difieren en su capacidad de expresar y/o demostrar afirmaciones acerca de N . La “aritm´etica baby” AB es una teor´ıa aritm´etica completa porque su lenguaje no incluye cuantificadores de modo que su poder expresivo es relativamente peque˜ no (esta teor´ıa no est´a, propiamente, formulada en LA , sino en la reducci´ on de LA eliminando la cuantificaci´on). La aritm´etica de Robinson Q est´ a formulada en el lenguaje de primer orden LA pero no contiene, a diferencia de AP, el esquema de inducci´on (los axiomas de Q difieren algo de los de AP). Podemos obtener teor´ıas entre Q y AP incluyendo distintas instancias del esquema de inducci´on (Smith, 2007, c. 10). • Funci´ on recursiva primitiva, funci´ on recursiva En el transcurso de la demostraci´ on de sus teoremas de incompletud, G¨odel define una clase de funciones sobre conjuntos de n´ umeros y muestra que una teor´ıa como AP (en realidad la demostraci´on de G¨odel emplea otro sistema) es capaz de capturar todas estas funciones (despu´es, a trav´es de la numeraci´ on de G¨ odel, este hecho le permitir´a demostrar afirmaciones sobre AP dentro de AP). Tal clase de funciones es el conjunto de funciones recursivas primitivas. Son el conjunto de todas las funciones que se pueden definir a trav´es de cadenas de definiciones empleando la composici´ on de funciones y la recursi´on primitiva partiendo de funciones aritm´eticas claramente computables como la sucesi´on, la suma, la multiplicaci´ on y la(s) funci´on(es) identidad. Esta definici´on quiz´a no te diga mucho; para una caracterizaci´on precisa ver (Smith, 2007, c. 11); aqu´ı va la idea intuitiva, a trav´es de un ejemplo: 0! = 0 sx! = x! · sx
17
Esta definici´ on caracteriza la funci´on factorial (!) sobre los n´ umeros naturales. Las funciones recursivas pueden definirse a trav´es de la composici´ on de funciones (en la segunda cl´ausula, ! se define a trav´es de la composici´ on de !, · y s) y empleando la recursi´on (primitiva). La idea de recursi´ on consiste en que el valor de una funci´on para un argumento sn se fija en t´erminos de la misma funci´ on (posiblemente en combinaci´ on con otras funciones) para el argumento n. Es decir, para determinar el valor de un argumento, la funci´on nos remite al resultado de aplicar la funci´on para un argumento menor. La primera cl´ ausula garantiza que siempre conocemos el valor de la funci´on para el argumento m´ınimo. Es necesario un “pack” inicial de funciones; ´estas son la sucesi´ on, suma y multiplicaci´on m´as funciones de identidad (como I(a1 , . . . an ) = ak [1 ≤ k ≤ n]). Estas funciones son claramente computables y la computabilidad se preserva a trav´es de composici´ on y recursi´ on primitiva, de modo que cualquier funci´on recursiva primitiva es computable ((Smith, 2007, 88)). No todas las funciones computables, sin embargo, son recursivas primitivas. Esta noci´ on se puede extender para dar lugar a la noci´on m´as general de funci´ on recursiva (no me siento con fuerzas: ver (Smith, 2007, c. 29)). La tesis de Church se refiere a esta clase m´as general de funciones. • recursivamente enumerable. Un conjunto Σ es enumerable ssi Σ est´ a vac´ıo o existe una funci´on f : N 7→ Σ que es ‘onto’ (sobre la totalidad de Σ) (en esta definici´on, un conjunto es enumerable ssi es contable; no s´e c´ omo ha surgido esta ambig¨ uedad, pero espero resolverla del mejor modo posible). Un conjunto Σ es recursivamente enumerable cuando o bien es vac´ıo o hay una funci´on recursiva f : N 7→ Σ sobre la totalidad de Σ. Naturalmente, todo conjunto recursivamente enumerable es enumerable pero no al rev´es. T eoN , por ejemplo, es enumerable (pues es un subconjunto del conjunto de f´ormulas de LA que es enumerable) pero, como consecuencia de los teoremas de G¨odel, no es recursivamente enumerable. • Algoritmo. La idea de algoritmo es la idea intuitiva de un procedimiento mec´ anico para dar respuesta a una pregunta: un procedimiento paso-a-paso cuyas reglas son completamente expl´ıcitas de modo que su aplicaci´ on no requiere ninguna comprensi´on de los objetos que se manipulan en el proceso ni ning´ un conocimiento previo y tal que aporta un resultado en un n´ umero finito de pasos (Smith, 2007, 316). • Tesis de Church El conjunto de funciones computables (cualquier funci´ on computable por una rutina algor´ıtmica) es el conjunto de funciones recursivas. De acuerdo con la Tesis de Church, la noci´on intu18
itiva de algoritmo queda completamente caracterizada por la noci´on matem´ atica de funci´ on recursiva. • Expresar (en el lenguaje de una teor´ıa) Una f´ormula de un lenguaje de primer orden con una variable libre no es, propiamente, no verdadera ni falsa en una interpretaci´on: ser´a verdadera para algunas sustituciones de la variable y falsa para otras. En este sentido, podemos emplear una f´ ormula con una variable libre (la misma variable puede tener varias ocurrencias) para expresar una propiedad y podemos emplear una f´ ormula con dos variables libres para expresar una relaci´ on (esto puede generalizarse para cualquier n´ umero de variables). M´ as espec´ıficamente, para el caso del lenguaje de la aritm´etica LA : Una propiedad P es expresada por una f´ormula abierta A(x) del LA con x como u ´nica variable libre exactamente cuando para todo n´ umero n: si n tiene la propiedad P entonces A(n) es verdadera si n no tiene la propiedad P entonces ¬A(n) es verdadera (En esta definici´ on, n es un n´ umero natural y n es el numeral que denota ´ese n´ umero. El numeral de n es el t´ermino de n z }| { LA : s . . . s 0). De manera an´ aloga, una relaci´on R es expresada por una f´ ormula abierta A(x, y) de LA con x e y como u ´nicas variables libres exactamente cuando para todo par de n´ umeros m, n: si m est´ a conectado por R con n entonces A(m, n) es verdadera si m no est´ a conectado por R con n entonces ¬A(m, n) es verdadera Hay que notar que las funciones son un cierto tipo de relaciones (ver funci´ on) de modo que esta definici´on puede extenderse para el caso de funciones. Si f es una funci´ on de un argumento sobre n´ umeros naturales, f es expresada por una f´ormula abierta A(x, y) de LA con x e y como u ´nicas variables libres exactamente cuando para todo par de n´ umeros m, n: si f (m) = n entonces A(m, n) es verdadera si f (m) 6= n entonces ¬A(m, n) es verdadera
19
Esta noci´ on de expresar es una noci´on sem´antica: depende del lenguaje de la teor´ıa. La noci´ on de capturar es una noci´on sint´actica, en el sentido de que depende de los axiomas y el sistema deductivo de la teor´ıa. En esta entrada hemos hablado de expresar, en el mismo sentido en algunos textos se habla de definir. • Capturar (en una teor´ıa). Adem´ as de expresar ciertas cuestiones acerca de la estructura de la aritm´etica dentro de una teor´ıa como la Aritm´etica de Peano queremos, naturalmente, demostrar algunas de esas afirmaciones. La Aritm´etica de Peano es una teor´ıa aritm´etica; existen otras teor´ıas que tienen distinto “poder demostrativo” (aunque compartan lenguaje y, por tanto, tengan el mismo poder expresivo), por ejemplo la Aritm´etica de Robinson. De ah´ı que en la siguiente definici´on hablemos de capturar una cierta relaci´ on o funci´ on num´erica dentro de una teor´ıa (una teor´ıa aritm´etica, se entiende). Sea R una relaci´ on entre n´ umeros naturales. Una f´ormula A(x, y) de LA captura la relaci´on R en una teor´ıa T exactamente cuando para todo par de n´ umeros m, n: si m est´ a conectado por R con n entonces T ` A(m, n) si m no est´a conectado por R con n entonces T ` ¬A(m, n) Esta definici´ on se adapta al caso de funciones, ya que las funciones son un tipo de relaciones. Sea f una funci´ on de un argumento dentro n´ umeros naturales. Una f´ ormula A(x, y) de LA captura la funci´on f en una teor´ıa T exactamente cuando para todo par de n´ umeros m, n: si f (m) = n entonces T ` A(m, n) si f (m) 6= n entonces T ` ¬A(m, n) Los teoremas de incompletud de G¨odel funcionan sobre la base de teor´ıas capaces de expresar y/o demostrar suficiente aritm´etica. En particular (al menos en una de las versiones de la demostraci´on) para que el procedimiento de G¨odel genere una oraci´on indecidible para una teor´ıa T hay que mostrar, entre otras cosas, que T es capaz de capturar toda funci´ on recursiva primitiva. La Aritm´etica de Robinson puede capturar todas las funciones recursivas primitivas (por tanto, tambi´en la Aritm´etica de Peano). 20
El t´ermino ‘capturar’ es empleado por Smith (2007). Algunos autores hablan de ‘representar’ para referirse a lo mismo. • Teor´ıa intuitiva de conjuntos. Un conjunto es, intuitivamente, una colecci´ on de elementos. La teor´ıa de conjuntos estudia la relaci´on entre un conjunto y los elementos que contiene (pertenencia) y define, en t´erminos de ´esta, gran cantidad de operaciones y relaciones entre distintos tipos de conjuntos. A finales del siglo XIX se sab´ıa que la teor´ıa de conjuntos era una potente teor´ıa matem´atica en la que era posible definir importantes partes de la matem´atica como el c´ alculo. De ah´ı que la teor´ıa de conjuntos juegue un papel esencial en las discusiones sobre los fundamentos de las matem´aticas. Sin embargo, tambi´en se sab´ıa, ya a finales del XIX, que la teor´ıa (intuitiva) de conjuntos es inconsistente. La teor´ıa intuitiva de conjuntos es aquella formulada en un lenguaje natural, donde las nociones clave de conjunto y pertenencia no se definen expl´ıcitamente, sino que descansan sobre una comprensi´ on intuitiva. Dentro de la teor´ıa intuitiva, la existencia de un conjunto viene garantizada por la especificaci´on de una propiedad cualquiera. Por ejemplo, en la teor´ıa intuitiva existe el conjunto R = {x|x ∈ / x}. Por este motivo, se propusieron teor´ıas formales, como ZF, donde las nociones de conjunto y pertenencia son definidas a trav´es de los axiomas, donde podemos seguir definiendo conceptos matem´ aticos interesantes y que, por lo que sabemos, son consistentes. • ZF y ZFC. ZF (por Zermelo-Fraenkel) es una teor´ıa formulada en un lenguaje de primer orden, LZF , que incluye una relaci´on ∈ como u ´nico s´ımbolo extral´ ogico [check]. Se trata de una “nice theory”. A finales del siglo XIX se sab´ıa que la teor´ıa intuitiva de conjuntos era inconsistente (paradoja de Russell etc.) La teor´ıa de Zermelo-Fraenkel impone restricciones sobre la construcci´on de conjuntos, como la existencia de un conjunto universal, por ejemplo, para evitar este tipo de paradojas. Por lo que sabemos, esta teor´ıa es consistente (aunque, como se comenta en Aritm´etica de Peano, el segundo teorema de incompletud de G¨ odel impone serias restricciones para demostrar si lo es). En 19xx G¨ odel demostr´o que ZF era consistente con ... y en 19xx Cohen que ZF era consistente con... Esto significa que el Axioma de elecci´ on es independiente de ZF. Se llama ZFC al resultado de a˜ nadir el equivalente formal al axioma de elecci´on a la teor´ıa ZF (ZFC = Zermelo-Fraenkel + “Choice”). • Aritm´ etica de Peano. Es una teor´ıa axiom´atica formulada en el lenguaje de primer orden, LAP , que incluye una funci´on de un argumento s, dos funciones de dos argumentos + y · y una constante 0. La intenci´ on de la Aritm´etica de Peano es representar la estructura de
21
la aritm´etica (N : N con las funciones de sucesi´on, suma y multiplicaci´ on). Est´ a formada por los axiomas: 1. ∀x¬s(x) = 0 2. ∀x∀y(x 6= y ⊃ s(x) 6= s(y)) 3. ∀x(x + 0) = x 4. ∀x∀y(x + s(y)) = s(x + y) 5. ∀x(x · 0) = 0 6. ∀x∀y(x · s(y)) = ((x · y) + x) m´ as todas las instancias del siguiente esquema de inducci´ on,
7. ((ϕ)[0/x] ∧ ∀x(ϕ ⊃ (ϕ)[s(x)/x])) ⊃ ∀xϕ donde ϕ es una f´ ormula cualquiera de LA con x como u ´nica variable libre y (ϕ)[x/t] el resultado de sustituir todas las ocurrencias libres de x por un t´ermino t de LA .
M´ as un sistema deductivo adecuado para la l´ogica de primer orden. Por estar formulada en un lenguaje de primer orden sabemos que la Aritm´etica de Peano no representa esta estructura hasta el isomorfismo, pues tiene modelos de distintas cardinalidades (Teoremas de L¨ owenheim-Skolem). Adem´as, la Aritm´etica de Peano tampoco representa esta estructura hasta el isomorfismo en su potencia, pues ni siquiera T eo(N ), es decir, el conjunto de oraciones de LAP verdaderas en la estructura de la aritm´etica lo hace (modelos no est´andar de la Aritm´etica). Adem´ as, la Aritm´etica de Peano (si resulta ser ωconsistente) es incompleta (Primer Teorema de Incompletud). Por u ´ltimo, aunque no tenemos indicios para pensar lo contrario, hay serias limitaciones para demostrar que la Aritm´etica de Peano es conistente (Segundo Teorema de Incompletud), no digamos ya demostrar que es verdadera en N . • Numerable. La cardinalidad de N es ℵ0 . Un conjunto A es numerable ssi |A| = ℵ0 . • Contable. Un conjunto es contable cuando es finito o numerable. De otro modo se dice que el conjunto es incontable. Por el teorema de Cantor sabemos que |℘(N)| es incontable. • Teorema de Schr¨ oder-Bernstein: Para cualesquiera conjuntos X e Y , si existe una funci´on biun´ıvoca de X en Y y una funci´on bioun´ıvoca de Y en X, entonces existe una correspondencia entre X e Y . (Zalabardo: 236, Hedman: 75). • Teorema de Cantor. Para cualquier conjunto A, |A| < |℘(A)| (Zalabardo, 2002, 248), (Hedman, 2006, 77) 22
• Teoremas de incompletud. Los teoremas de incompletud de G¨odel (1931) son dos teoremas que muestran serias limitaciones en el intento de formalizar nociones matem´aticas, como las de la aritm´etica b´asica, en una teor´ıa axiom´ atica. El primer teorema muestra que cualquier teor´ıa axiom´ atica capaz de capturar (o expresar, seg´ un la versi´on del argumento; ver (Smith, 2007, 48)) cierta cantidad de aritm´etica (una cantidad modesta, por cierto, ver Q) es incompleta. El segundo teorema, que se sigue del anterior, muestra que cualquier teor´ıa axiom´ atica capaz de capturar cierta cantidad de aritm´etica (algo m´as que para el primer teorema, pero una cantidad modesta todav´ıa) no puede demostrar, si es consistente, la oraci´on que expresa que tal teor´ıa es consistente (por ejemplo, en el caso de la Aritm´etica de Peano, AP, el segundo teorema dice: si AP es consistente entonces 0AP con [donde con es una oraci´ on de AP que “dice” que AP es consistente]). Comentarios muy breves sobre el significado de los teoremas. Mirar Smith y si acaso dejar alguna referencia. • Programa de Hilbert. • Intuicionismo • Paradoja: Definici´ on. Paradojas sem´anticas y de la teor´ıa de conjuntos. • L´ ogica. En t´erminos generales, se suele entender la L´ogica como la disciplina interesada en la relaci´on de consecuencia l´ogica. Contempor´ aneamente, la l´ ogica emplea m´etodos matem´aticos para el estudio de esta relaci´ on de modo que la L´ogica es una disciplina que suele abordarse desde distintos ´angulos; fundamentalmente la Filosof´ıa, las matem´ aticas y la inform´atica te´orica. Se suele hablar, m´ as concretamente, de una l´ ogica como un lenguaje formal con una sem´ antica que permite definir una relaci´on de consecuencia l´ ogica m´ as una teor´ıa de la demostraci´on o sistema deductivo. • Lenguaje (formal). Un lenguaje formal puede entenderse como un conjunto de s´ımbolos (el vocabulario) y una gram´atica que define (inductivamente) las secuencias de s´ımbolos del vocabulario que constituyen las f´ ormulas del lenguaje. Lo m´as habitual es que un lenguaje formal contenga un vocabulario extral´ogico (´estas son las expresiones que generar´ an las oraciones at´omicas del lenguaje) y un vocabulario l´ ogico con conectivas y cuantificadores (´estas expresiones nos permitir´ an construir oraciones complejas). Ver (Humberstone, 2011, 1.11) para una caracterizaci´ on m´as abstracta. • Definici´ on inductiva. Una definici´on inductiva es un medio para definir un conjunto de objetos. Las definiciones inductivas constan 23
de tres partes: una cl´ ausula base, una cl´ausula de inducci´on y una cl´ ausula de clausura. La cl´ausula base indica el conjunto de elementos de los que parte nuestra definici´on; la cl´ausula de inducci´on nos proporciona instrucciones para construir elementos de complejidad n+1 a partir de elementos de complejidad n; la clausura establece que s´olo los objetos que puedan construirse de esta manera pertenecen al conjunto. Ejemplo. El conjunto de f´ormulas del lenguaje proposicional cl´ asico LP , siendo su vocabulario {p1 , p2 . . . ∨, ∧} puede definirse: Base Toda variable proposicional (p1 , p2 . . . .) est´a en LP Inducci´ on Para cualesquiera secuencias de signos, A y B, del vocabulario de LP , si A y B est´an en LP tambi´en lo est´an las secuencias (A ∧ B) y ¬A Clausura Ninguna otra secuencia est´a en LP La gracia de las definiciones inductivas es que la cl´ausula de inducci´on puede aplicarse repetidas veces para construir un elemento (por ejemplo, ∧ ∧ ∧p1 y ∧(p1 ∧ ¬p2 ) son f´ormulas de LP ) de modo que las definiciones inductivas establecen una jerarqu´ıa en el conjunto que definen dependiendo del n´ umero de aplicaciones de la cl´ausula de inducci´on requeridas para construcci´on del elemento (en las definiciones de lenguajes esto se suele llamar la complejidad de una f´ormula y se mide por el n´ umero de constantes que aparecen en la f´ormula; en los ejemplos de este p´ arrafo, ambas f´ormulas tienen complejidad 3 [las variables proposicionales tienen complejidad 0]). Esta jerarqu´ıa (u ordenaci´on) en los elementos del conjunto nos permitir´a establecer definiciones recursivas y pruebas por inducci´on. [En realidad hace falta un poco m´as que que un conjunto est´e definido inductivamente para poder hacer esto u ´ltimo, creo que tiene que est´ar generado libremente] • Pruebas por inducci´ on. Una prueba por inducci´on, o demostraci´on inductiva, es un m´etodo para demostrar propiedades sobre conjuntos definidos inductivamente. Las demostraciones inductivas explotan el hecho de que un conjunto inductivo est´a ordenado de acuerdo a la complejidad de sus elementos; de ah´ı que consten de dos partes. En la primera demostramos que los elementos de la base poseen la propiedad que queremos demostrar (esto se puede llamar “Caso base”). En la segunda (“Paso de inducci´on”) demostramos el siguiente condicional: si un elemento (o varios) de complejidad n posee la propiedad, el elemento de complejidad n + 1 construido a partir de ´este tambi´en posee la propiedad (al antecedente de este condicional se le llama “hip´otesis de inducci´ on”). En otras palabras, el paso de inducci´on muestra que la propiedad en cuesti´ on se hereda de un nivel n cualquiera al siguiente (si hemos demostrado que el nivel 0 tiene la propiedad, la propiedad se heredar´ a a todos los niveles). Ejemplo. 24
De acuerdo con la definici´on de LP en el ‘definici´on inductiva’ demuestre que toda f´ormula de LP tiene el mismo n´ umero de par´entesis izquierdos que derechos. Caso Base Las variables proposicionales no tienen par´entesis de modo que tienen el mismo n´ umero de par´entesis izquierdos que derechos. Inducci´ on Supongamos que A y B tienen el mismo n´ umero de par´entesis izquierdos que derechos (sean m y n el n´ umero de par´entesis izquierdos de A y B respectivamente). Est´ a claro que ¬A tiene el mismo n´ umero de par´entesis izquierdos que derechos (a saber m). Adem´as (A ∧ B) tambi´en tiene el mismo n´ umero de par´entesis izquierdos que derechos (a saber m + n + 1). Naturalmente, demostrar esta afirmaci´on por inducci´on es como abrir una nuez con una apisonadora (Priest, 2008, xxx). • L´ ogica de primer orden. Los lenguajes formales pueden variar en su vocabulario l´ ogico y estructura, dando lugar a lenguajes con distinto poder expresivo. Oraciones que expresan ciertos tipos de generalizaci´ on, como ‘Todos los hombres son mortales’, no tienen una traducci´ on natural en un lenguaje proposicional. Se dice que son “de primer orden” a aquellas l´ogicas cuyo lenguaje permite la cuantificaci´ on sobre individuos. El vocabulario extral´ogico contendr´a s´ımbolos de predicado y s´ımbolos para t´erminos singulares y su vocabulario extral´ ogico contendr´ a cuantificadores y variables individuales (variables que pueden situarse en la posici´on de un nombre). Se habla de un l´ ogica de primer orden en general cuando se considera una l´ogica para un lenguaje de este tipo. Cuando se habla de “la l´ogica de primer orden” se suele entender que hablamos de la l´ogica cl´ asica de primer orden. Por contraste con los lenguajes de primer orden, un lenguaje de segundo orden es aqu´el que, adem´as de la cuantificaci´on sobre individuos, permite cuantificar sobre propiedades (contiene variables que pueden situarse en la posici´ on de un predicado). Dadas ciertas convenciones sobre su sem´ antica (sobre qu´e es una interpretaci´on para un lenguaje de segundo orden), los lenguajes de segundo orden tienen una capacidad expresiva mucho mayor que la de lenguajes de primer orden. Por ejemplo, la aritm´etica es representable hasta el isomorfismo por un conjunto finito de oraciones en un lenguaje de segundo orden (de nuevo, con ciertos supuestos sobre su sem´antica) (para comprobar la extraordinaria diferencia con el caso de lenguajes de primer orden, ve´ase modelos no est´ andar de la aritm´etica).
25
• L´ ogica cl´ asica. Se suele entender, en primer lugar, que la l´ogica cl´ asica es una l´ ogica basada en un vocabulario l´ogico con las constantes habituales (como ¬ y ∧) pero no constantes ex´ oticas (como 2 o ). Adem´ as, se aceptan los cuantificadores ∀ y ∃ pero cuando ´estos ligan variables individuales (algunos autores argumentan que ir m´as all´a de la l´ ogica de primer orden es abandonar el terreno supuestamente neutro de la l´ ogica). En segundo lugar, la l´ogica de primer orden suele ir asociada a una sem´antica caracter´ıstica donde las oraciones pueden tomar un u ´nico valor de verdad entre lo verdadero y lo falso (bivalencia) y las conectivas tienen un funcionamiento particular (por ejemplo, A ∧ B debe siempre tomar el valor del m´ınimo entre A y B). Se suele entender, por u ´ltimo, que hay una serie de inferencias caracter´ısticas de la l´ ogica cl´asica como, LEM ∅ p ∨ ¬p LNC p ∧ ¬p ∅ MP p, p ⊃ q q adem´ as de ciertas relaciones entre inferencias como, TD Γ, A B ⇐⇒ Γ A ⊃ B Existe mucha discusi´ on en Filosof´ıa de la L´ogica (y disciplinas afines) sobre si debemos o no separarnos en ciertos puntos de la l´ogica cl´asica, como si esta u ´ltima noci´on fuera un concepto perfectamente definido. Lo cierto es que no est´ a tan claro qu´e cuenta exactamente como l´ogica cl´ asica, especialmente cuando salimos de los confines del vocabulario cl´ asico para solucionar problemas como los planteados por las paradojas (estos tipos: Cobreros et al. (2010) y Cobreros et al. (2011) argumentan que su l´ ogica es cl´asica aunque no sea transitiva!) • Sintaxis y sem´ antica Gran parte del inter´es de la l´ogica reside en la relaci´ on entre aspectos sint´acticos de una teor´ıa y aspectos sem´anticos, entre el lenguaje (y aspectos ligados a la forma del lenguaje, como la deducci´ on) y la interpretaci´on de un lenguaje (y aspectos ligados a la interpretaci´ on del lenguaje, como la relaci´on de consecuencia l´ogica). En un sentido restringido de estos t´erminos se entiende lo siguiente por sintaxis y sem´ antica: Sintaxis: El vocabulario (l´ogico y no l´ogico) de un lenguaje L m´ as las reglas de formaci´on de t´erminos y f´ormulas (la “gram´ atica”) por las que se generan (inductivamente) todos los t´erminos y f´ ormulas de L . Sem´ antica: Una estructura para L (es decir, una interpretaci´ on) que asigna a cada elemento del vocabulario no 26
l´ ogico de L un “objeto” adecuado a su categor´ıa gramatical. Algunas veces un determinado lenguaje tendr´a una “interrpetaci´ on pretendida” (la interpretaci´on pretendida para LA , por ejemplo, es la estructura de la aritm´etica). En un sentido m´ as amplio, sin embargo, se emplea el t´ermino ‘sint´actico’ para aquellas cuestiones que est´an ligadas al lenguaje y su forma, se emplea el t´ermino ‘sem´antico’ para aquellas cuestiones relacionadas con la noci´ on de interpretaci´on. En este sentido, una relaci´on de consecuencia deductiva es sint´actica, mientras que la relaci´on de consecuencia l´ ogica es sem´ antica. Una teor´ıa axiom´atica es un objeto sint´actico pues es un conjunto de oraciones Γ con una relaci´on de consecuencia deductiva ` (naturalmente, dado que la l´ogica de primer orden es completa, si Γ es un conjunto de oraciones de un lenguaje de primer orden, el conjunto (Γ, `) ser´a igual al conjunto (Γ, ). La mayor parte de los resultados interesantes de la l´ogica tienen que ver de un modo u otro con cierta relaci´on entre sem´antica y sintaxis. Por ejemplo, la correcci´on y completud de la l´ogica de primer orden muestra que hay relaciones de consecuencia deductiva (sint´acticas) extensionalmente equivalentes a la relaci´on de consecuencia l´ogica para lenguajes de primer orden (sem´antica). La compacidad de la l´ogica de primer orden tiene que ver directamente con la relaci´on de consecuencia l´ ogica (sem´ antica) pero indica que la l´ogica de primer orden puede tener sistemas deductivos finitarios (donde todas las demostraciones constan de un n´ umero finito de pasos). Los teoremas de L¨owenheim y Skolem muestran limitaciones expresivas (sem´antico) inherentes a cualquier lenguaje de primer orden (sint´actico) a la hora de representar estructuras (sem´ antico) infinitas. El Primer teorema de incompletud se suelen presentar en dos estilos: sem´antico y sint´actico. En su versi´on sem´ antica muestran que para cualquier teor´ıa (axiom´atica) aritm´etica A en el lenguaje de LA (sint´actico) que sea correcta (es decir, tal que (A, `) ⊆ T eo(N )), hay una oraci´on G ∈ T eo(N ) pero G ∈ / (A, `). En otras palabras, para cualquier teor´ıa aritm´etica del lenguaje LA que sea correcta hay una oraci´on verdadera que no est´a dentro de la teor´ıa (n´ otese que T eo(N ) es definida en t´erminos sem´anticos de modo que la idea de correcci´ on es tambi´en sem´antica). En su versi´on sint´actica muestra que para cualquier teor´ıa (axiom´atica) aritm´etica A que sea (ω)-consistente, es incompleta (todo nociones sint´acticas). • Compacidad. Se dice que una l´ogica (un lenguaje con una relaci´on de consecuencia l´ ogica) es compacta cuando Γ A s´olo si existe un subconjunto finito Γ+ ⊆ Γ tal que Γ+ A. Con una formulaci´on equivalente, una l´ ogica es compacta cuando si todo subconjunto finito de Γ es satisfacible, entonces Γ tambi´en es satisfacible. La l´ogica de 27
primer orden es compacta. • Correcci´ on y completud (de un sistema deductivo). Un sistema deductivo da lugar a una relaci´on de consecuencia entre f´ormulas de un lenguaje. Se dice que el sistema es correcto (respecto a una determinada relaci´ on de consecuencia l´ogica) cuando s´olo nos permite demostrar consecuencias l´ogicas. Se dice que es completo cuando nos permite deducir todas las consecuencias l´ogicas. M´as brevemente, un sistema deductivo es correcto y completo cuando para cualquier f´ ormula A y conjunto de f´ormulas Γ, Γ ` A si y s´olo si Γ A. • Compacidad. Una relaci´on de consecuencia l´ogica es compacta cuando se cumple que, si Γ A entonces Γ∗ A (para un subconjunto finito Γ∗ ⊆ Γ). Con una formulaci´on alternativa, una relaci´on de consecuencia l´ ogica es compacta cuando sucede que, para cualquier conjunto Γ de oraciones, si todo subconjunto finito de Γ tiene un modelo entonces Γ tiene un modelo. El teorema de L¨ owenheim-Skolem ascendente es una consecuencia de la compacidad de la l´ ogica de primer orden, al igual que la existencia de modelos no est´ andar de la Aritm´etica. • Modelos no est´ andar de la Aritm´ etica. Una consecuencia de los Teoremas de L¨ owenheim-Skolem es que ninguna teor´ıa formulada en un lenguaje de primer orden con un modelo infinito es categ´orica [revise]. Por ejemplo, la teor´ıa de la aritm´eticaaritm´etica, T eo(N ), tiene modelos incontables. Podemos, sin embargo, hacernos una pregunta un poco m´ as modesta. Sabemos que el tama˜ no de N es ℵ0 ; ¿son todos los modelos de T eo(N ) de tama˜ no ℵ0 isomorfos entre s´ı? es decir, ¿representa T eo(N ) a la estructura de la Aritm´etica hasta el isomorfismo en su potencia? La respuesta es ‘no’ y la demostraci´on emplea nuevamente la compacidad de la l´ogica de primer orden (el razonamiento es similar a la demostraci´on de LS ascendente empleando, adem´ as, LS descendente)[citar Zalabardo]. Las estructuras generadas por esta demostraci´ on son modelos de T eo(N ) (modelos, por tanto, de la (teor´ıa de la) Aritm´etica), con la misma cardinalidad que N pero no-isomorfos con N . La primera raz´on por la que estos modelos no son isomorfos con N es porque contienen elementos no-est´ andar : objetos que se sit´ uan m´ as all´ a de cualquier n´ umero finito de aplicaciones de la funci´ on sucesor a partir de cero. Podemos visualizar la situaci´on: Modelo est´ andar (N): 1
2
3
4
5
6...
Modelo no-est´ andar: 28
1
2
3
4
5
6...
cA+
Dado que los modelos no-est´andar son modelos de T eo(N ), ´estas oraciones se cumplir´ an, tambi´en, para los modelos no-est´andar. Esto nos da la pista para descubrir algunas caracter´ısticas generales que debe cumplir cualquiera de estos modelos 1. Los modelos no-est´andar contienen los n´ umeros naturales hasta el isomorfismo. 2. Un elemento no-est´andar es mayor que cualquier n´ umero natural, no es sucesor de ning´ un natural ni el resultado de la suma o producto de naturales. 3. Un n´ umero natural es menor que cualquier elemento no-est´andar, no es sucesor de ninguno de ellos ni el resultado de la suma o producto de un elemento no-est´andar con otro elemento del universo (est´ andar o no). 4. Ning´ un elemento no-est´andar est´a a una distancia finita de un n´ umero natural (dos elementos a y b del universo de A est´an a una distancia finita ssi o bien a +A n = b o bien n +A b = a) Los elementos del universo de un modelo no-est´andar se agrupan en galaxias bajo la relaci´ on de equivalencia de ‘estar a una distancia finita’. Podemos distinguir entre la galaxia est´andar y las galaxias noest´ andar. La galaxia est´andar est´a linealmente ordenada por
