Introducción a la lógica y teoría axiomática de conjuntos. Construcción del conjunto de los números naturales

Facultad de Ciencias Trabajo Fin de Grado Grado en Matemáticas Introducción a la lógica y teoría axiomátca de connuntos. Construcción del connunto de los números naturales. Autor: Rubén Martn Valmaseda Tutor/es: José María Cano Torres Agradecimientos Deseo expresar mi sincero agradecimiento al profesor José María Cano Torres, tutor de este trabajo, por su ayuda, dedicación y paciencia. Agradezco también a mis padres, hermanos y familiares, el apoyo recibido durante esta etapa. Índice general Introducción............................... 3 1. Lógica Proposicional 5 1.1. Sistemas Formales . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Sistema Formal de la Lógica proposicional . . . . . . . . . . . 7 2. Lógica de Primer Orden 37 2.1. Sintaxis y semántica de la lógica de primer orden. . . . . . . . 37 2.2. Sistema formal de la lógica de primer orden. . . . . . . . . . . 58 3. Fundamentación de las Matemáticas 67 3.1. Sistema axiomático de la teoría de conjuntos de Zermelo-Fraenkel. 67 3.2. Sistema de Peano y los números naturales. . . . . . . . . . . . 73 3.3. Suma y producto de los números naturales. . . . . . . . . . . . 77 3.4. Ordenación de los números naturales. . . . . . . . . . . . . . . 82 1 2 Introducción Este trabajo es una pequeña recopilación de diferentes libros y notas sobre lógica y teoría de conjuntos con el objeto de conocer la base sólida en la que se apoyan todas las matemáticas. Observando que todas las ramas de la matemática parten de unos axiomas y se demuestran enunciados a partir de ellos se intuía que podía haber una relación entre la matemática y la lógica y por eso matemáticos como Zermello y Hilbert redujeron las matemáticas a la lógica y a la teoría de conjuntos. Este trabajo comienza con lógica proposicional y de primer orden viendo sus sintaxis y algunos resultados porque saber razonar en lógica es saber razonar en matemáticas y en la vida en general. El trabajo acaba con los axiomas de Zermello-Fraenkel y la construcción de los números naturales. 3 4 Capítulo 1 Lógica Proposicional La lógica y las matemáticas son las dos únicas ciencias deductivas. La lógica es un sistema que permite verificar si un razonamiento es correcto o incorrecto cuya finalidad es el estudio de la razón en el conocimiento. En este primer capítulo trataremos un poco la lógica proposicional, también llamada lógica simbólica o matemática, esta lógica se basa en la aplicación de símbolos por medio de tablas que nos permite ver lo verdadero o falso de las proposiciones. 1.1. Sistemas Formales Definición 1.1. Un sistema formal está compuesto de: 1. Un alfabeto A. Es el conjunto de todos los símbolos que podremos utilizar. 2. Un conjunto de fórmulas. Una fórmula es una secuencia finita de símbolos del alfabeto. El sistema formal proporcionará un algoritmo que determine si una secuencia finita de símbolos es una fórmula del sistema o no, ya que no toda secuencia finita de símbolos es una fórmula. 3. Un conjunto de axiomas. El cual es un subconjunto del conjunto de fórmulas. Al igual que para el conjunto de fórmulas también habrá un algoritmo que determine si una fórmula es un axioma. 5 F= (b1b2b3...br#c1c2c3...ct). Observemos que el conector # está en la posición r+ 2. Podemos comprobar que p(r+ 2) = 1 debido a que en la cadena b1b2b3...brhay el mismo número de paréntesis de ambos tipos por el lema de los paréntesis(recordemos que G es una fórmula) y además a1=0(0. Veamos ahora que si ases un conector pero no es el conector principal entonces p(s)>1. Primero observemos que el conector principal es ar+2, entonces, o bien s<r+ 2, o bien s>r+ 2. Si s<r+ 2 entonces as=bs−1es un símbolo de la fórmula G. Por ser G una fórmula en el segmento inicial b1b2b3...bs−1debe haber más paréntesis abiertos que cerrados y a1es un paréntesis abierto, luego p > 1. Si s>r+ 2 entonces as=cs−r−2es un símbolo de la fórmula H. Por ser G una fórmula hay la misma cantidad de paréntesis abiertos que cerrados en el segmento b1b2b3...bry por ser H una fórmula hay más paréntesis abiertos que cerrados en el segmento c1c2c3...cs−r−2, además a1es un paréntesis abierto y ar+2 es un conector, luego p(s)>1. El algoritmo que determina si una sucesión de símbolos es una fórmula o no es el siguiente: Sea F una sucesión de n símbolos. Si n= 1 entonces F fórmula si y solo si F es una variable proposicional. Si n > 1primeros debemos verificar que se cumple el lema de los paréntesis, es decir hay que comprobar que p(i)>1para i∈ {2,3,4, ..., n −1}, a1= ‘(0yan= ‘)0. Después comprobamos que se cumple el 1.2, es decir, tenemos que ver que existe un único conector en la j-ésima posición tal que p(j) = 1. Si aj= ‘¬0 j= 2 y tomamos la sucesión G=a3a4a5...an−1, la cual renombraremos G=b1b2b3...br. Si aj= # n > −1j > 2y tomamos las sucesiones H=a3a4a5...aj−1y J=aj+1aj+2aj+3...an−1, las cuales renombraremos H=c1c2c3...csy J=d1d2d3...dt. Repetimos el proceso con la sucesión G o con las sucesiones H y J según el caso en el que nos encontremos. Finalmente las sucesiones de un único símbolo deben ser variables proposicionales. Ejemplo 1.2. Haciendo uso del algoritmo anterior verificaremos si las sucesiones (()),(¬)y(p→(¬(¬p))) son fórmulas o no. Para la sucesión (()) vemos que a1= ‘(0ya4=0)0y 12 i= 2 i= 3 p(i) 1 2 Aquí no encontramos ningún conector, luego no es fórmula. Para la sucesión (¬)vemos que se verifica el lema de los paréntesis y a2es el conector ‘¬0. La siguiente sucesión que tendríamos que estudiar ahora es una sucesión sin símbolos. Por tanto (¬)no es una fórmula. La sucesión (p→(¬(¬p))) verifica el lema de los paréntesis, pues tenemos: i= 1 i= 2 i= 3 i= 4 i= 5 i= 6 i= 7 i= 8 i= 9 i= 10 i= 11 ai‘(0p→‘(0‘¬0‘(0‘¬0p‘)0‘)0‘)0 p(i)0111223332 1 Vemos que el símbolo a3= ‘ →0es conector y p(3) = 1. Además es el único símbolo que cumple estas dos propiedades simultáneamente. Ahora tenemos que estudiar las sucesiones py(¬(¬p)). La sucesión ptiene un único símbolo y es una variable proposicional. Para la sucesión (¬(¬p)) = b1b2b3...b7vemos que i= 1 i= 2 i= 3 i= 4 i= 5 i= 6 i= 7 bi‘(0‘¬0‘(0‘¬0p‘)0‘)0 p(i)0112221 Vemos que el símbolo b2= ‘¬0es un conector y p(2) = 1 ningún otro símbolo de la sucesión cumple simultáneamente estas dos propiedades. Estudiamos la sucesión (¬p) = c1c2c3c4. i= 1 i= 2 i= 3 i= 4 ci‘(0‘¬0p‘)0 p(i) 0 1 1 1 Vemos que el símbolo c2= ‘¬0es un conector y p(2) = 1 ningún otro símbolo de la sucesión cumple simultáneamente estas dos propiedades. 13 Estudiamos la sucesión p, la cual tiene un único símbolo y es una variable proposicional. Por tanto (p→(¬(¬p))) es una fórmula. Observación 1.2. Sea F una fórmula podemos obtener el árbol que la representa utilizando un algoritmo análogo al algoritmo que nos permite determinar si F es una fórmula. El conector principal de la primera sucesión lo escribiremos en la raíz del árbol que construiremos. Si F es de la forma (¬G)establecemos una relación padre-hijo entre dos nodos en los que escribiremos los conectores principales de F y de G. Si F es de la forma (G#H)establecemos relaciones padre-hijo entre un nodo en el que escribiremos el conector principal de F y dos nodos en los que escribiremos los conectores principales de G y H. Si una de las sucesiones es una variable proposicional sería una hoja. Ejemplo 1.3. Tomemos la fórmula F= (p→(¬(¬p))). Como hemos visto antes el conector principal es ‘→0. Es decir la raíz del árbol es el nodo en el que escribiremos ‘→0y las dos siguientes fórmulas con las que tenemos que trabajar son py(¬(¬p)), la primera es una variable proposicional que en el árbol la representaríamos con una hoja y el conector principal de la segunda fórmula es ‘¬0. Hasta el momento la representación en árbol sería: → ¬p Ahora tenemos que trabajar con la fórmula (¬p)cuyo conector principal es ‘¬0. Si añadimos este nuevo nodo el árbol quedaría: → ¬ ¬ p Finalmente nos queda la fórmula p, la cual es una fórmula proposicional, por tanto, el nodo con el que lo representaríamos sería una hoja. El árbol final es: 14 → ¬ ¬ p p Ejemplo 1.4. Sea F la fórmula (((p∨q)∧(p∨r)) →((¬(¬r)) ∨((¬p)→(¬r)))). Vemos que F es de la forma G→Hcon G=((p∨q)∧(p∨r))yH=((¬(¬r)) ∨((¬p)→(¬r))). Para la fórmula G=((p∨q)∧(p∨r))tenemos: i= 1 i= 2 i= 3 i= 4 i= 5 i= 6 i= 7 bi‘(0‘(0p‘∨0q‘)’ ‘∧0 p(i)0122221 i= 8 i= 9 i= 10 i= 11 i= 12 i= 13 bi‘(0p‘∨0r‘)0‘)0 p(i) 1 2 2 2 2 1 El conector principal de la fórmula G es ‘∧0y G es de la forma (J∧K) con J=(p∨q)yK= (p∨r). Siguiendo el algoritmo obtendremos el árbol que representa a la fórmula G=((p∨q)∧(p∨r)). ∧ ∨ rp ∨ qp Hacemos lo propio con la fórmula H=((¬(¬r))∨((¬p)→(¬r))). 15 ∨ → ¬ r ¬ p ¬ ¬ r El árbol que representa la fórmula F sería: → ∨ → ¬ r ¬ p ¬ ¬ r ∧ ∨ rp ∨ qp Definición 1.8. Llamaremos valoración a una aplicación υ:P −→ {0,1} que verifica para cualquier F, G ∈ P: υ((F∧G)) = 1 si y solo si υ(F) = 1 yυ(G)=1, υ((F∨G)) = 1 si y solo si υ(F)=1oυ(G) = 1, υ((F→G)) = 1 si y solo si υ(F) = 0 oυ(G)=1, υ((¬F)) = 1 si y solo si υ(G) = 0. Lema 1.2. Una valoración queda determinada por su restricción al conjunto P0. Demostración. Si F∈P0entonces es trivial que υ(F)queda determinada por su restricción al conjunto P0. Suponemos que se cumple para todo l≤kcon k≥1. Tomamos G∈Pk+1\Pk, entonces G es de la forma (¬H)o(H#J)con H y J fórmulas de Pn−1y # un conector binario. Por el teorema 1.1 sabemos que H y J son únicas. Usando la hipótesis de inducción y la definición de υqueda demostrado. 16 Dada una fórmula cualquiera podemos resumir en una tabla los valores que toma υsegún los valores que tomen las variables proposicionales. A estas tablas las llamaremos tablas de la verdad. p q (p∧q) (p∨q) (p→q) 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 p(¬p) 1 0 0 1 Definición 1.9. Sea Σun conjunto de fórmulas de la lógica proposicional yυuna valoración diremos que Σes consistente testado por υsi υ(F) = 1 para todo F∈Σ(escribimos υ|Σ≡1). Definición 1.10. Un conjunto de fórmulas Σes satisfacible si existe una valoración υtal que υ|Σ≡1. Definición 1.11. Sea F∈ P. Diremos que F es una tautología si υ(F) = 1 para cualquier valoración υ. Diremos que F es una contradicción si υ(F)=0 para cualquier valoración υ. Una fórmula F es una contingencia si no es ni tautología ni contradicción. Definición 1.12. Una fórmula F es válida si es una tautología y lo representaremos de la siguiente manera |=F. Definición 1.13. Sea Σun conjunto de fórmulas y F una fórmula. Diremos que Σimplica F tautológicamente si para cada valoración υcon υ|Σ≡1se cumple υ(F) = 1 y escribiremos Σ|=F. También diremos que F es una consecuencia lógica de Σ. 17 Observación 1.3. En el caso Σ|=Fla consecuencia lógica es una consecuencia semántica y no sintáctica. Siempre que no haya ambigüedad diremos simplemente consecuencia. Definición 1.14. Dos fórmulas F, G ∈ P son equivalentes si υ(F) = υ(G) para cualquier valoración. Escribimos F≈Gpara representar que las fórmulas F y G son equivalentes. Ejemplo 1.5. Veamos que (F∧G)≈(¬(F→(¬G))). F G (F∧G) (¬G) (F→(¬G)) (¬(F→(¬G))) 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 Las columnas 3 y 6 prueban (F∧G)≈(¬(F→(¬G))). Ejemplo 1.6. Veamos que (F∨G)≈(¬(F)→G). F G (F∨G) (¬F) ((¬F)→G)) 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 Las columnas 3 y 5 prueban (F∨G)≈(¬(F)→G). Definición 1.15. Sea F, G, H ∈ P fórmulas denotamos por Sb(F)al conjunto de subfórmulas de F y lo definimos de la siguiente manera: 1. Sb(F) = {p}si p=Fes una variable proposicional. 2. Sb((¬F)) = Sb(F)∪ {(¬F)}. 3. Sb(F) = Sb((G#H)) = Sb(G)∪Sb(H)∪ {F}si F=G#Hy # un conector binario. 18 Teorema 1.3. (Teorema de sustitución) Si se sustituyen subfórmulas de una fórmula F por otras que les son respectivamente equivalentes el resultado es una fórmula equivalente a F. Demostración. La afirmación es equivalente para fórmulas en P0, pues las variables proposicionales solamente son equivalentes a ellas mismas. Suponemos que se cumple para fórmulas en Pjcon j < n y consideremos una fórmula G∈Pn, entonces G es de la forma (¬H)o(H#J)con H y J fórmulas de Pn−1y # un conector binario. Por la definición de subfórmula una subfórmula de G distinta de G es también subfórmula de H o J. Sin pérdida de generalidad suponemos que sustuimos en H una subórmula por otra que le es equivalente. Por hipótesis de inducción H0≈H. Las siguientes tablas de verdad concluyen (H0#J)≈(H#J)y(¬H)≈(¬H0). H H0J(H∨J) (H0∨J) (H∧J) (H0∧J) 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 H H0J(H→J) (H0→J) 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 H H0(¬J) (¬J0) 1 1 0 0 0 0 1 1 Definición 1.16. Un sistema axiomático para una lógica de primer orden viene dado por un conjunto de axiomas y unas reglas de inferencia. 19 Definición 1.17. Vamos a definir dos sistemas axiomáticos para la lógica proposicional. Aunque solamente vamos a trabajar con uno de ellos también demostraremos que cualquier teorema de la lógica proposicional puede ser demostrado desde el otro sistema axiomático. La única regla con la que trabajaremos en ambos sistemas axiomáticos será la regla de inferencia denominada modus ponens, mp. Dadas dos fórmulas del tipo F→Gy F entonces tenemos G. El primer conjunto de axiomas lo constituyen los siguientes axiomas: 1. axioma 1 (F→(G→F)). 2. axioma 2 ((F→(G→H)) →((F→G)→(F→H))). 3. axioma 3 (((¬F)→(¬G)) →(G→F)). El segundo conjunto de axiomas lo constituyen los siguientes axiomas: 1. axioma 1 (F→(G→F)). 2. axioma 2 ((F→(G→H)) →((F→G)→(F→H))). 3. axioma 3 (((¬G)→(¬F)) →(((¬G)→F)→G)). Vamos a trabajar con el primer sistema axiomático, es decir, el sistema aximático formado por la regla de inferencia modus ponens y por los tres primeros axiomas. Observación 1.4. (Esta observación es importante). En los dos sistemas axiomáticos que hemos definido los únicos conectores que hemos utilizado son ¬y→. Por los ejemplos 1.5 y 1.6 y por el teorema de sustitución cualquier fórmula es equivalente a otra fórmula que solo utilice ¬y→como símbolos conectores . Esto resulta útil para ganar claridad. Observación 1.5. Los axiomas son equivalentes a otras fórmulas. Por ejemplo: ((¬F)→(¬G)) →(G→F)≈(((F∧G)∨(F→G)) →(G→F)). (F→(G→F)) ≈(F→((¬G)) ∨F). Existen algoritmos que determinan si una fórmula es alguno de los axiomas anteriores. Estos algoritmos están basados en el algoritmo que determina si una secuencia es o no una fórmula. Veamos de modo breve un algoritmo 20 para determinar si una fórmula es un axioma del primer tipo: Sea F una fórmula de la lógica proposicional. La fórmula F debe ser de la forma (G→H), es decir, el conector principal de F debe ser →. La fórmula H debe ser de la forma (J→K), es decir, el conector principal de H debe ser →. Finalmente para que F sea un axioma del tipo 1 debe verificarse que G=K, es decir, si G=b1b2b3...bnyK=e1e2e3...enentonces G=Ksi y solo si bi=eipara todo i∈ {1,2,3, ..., n}. Lema 1.3. Para cualquier fórmula F∈ P,(F→F)es un teorema de la lógica proposicional, es decir ∅ ` (F→F). Demostración. 1. ((F→((F→F)→F)) →((F→(F→F)) → (A→A))) axioma 2 (sustituyendo G por (F→F)). 2. (F→((F→F)→F)) axioma 1 (sustituyendo G por (F→F)). 3. ((F→(F→F)) →(F→F)) mp 1,2. 4. (F→(F→F)) axioma 1 (sustituyendo G por F). 5. (F→F)mp 3,4. Teorema 1.4. (Teorema de la deducción) Si Σ∪ {F} ` Gentonces Σ`(F→G). Demostración. Por hipótesis sabemos que existe una demostración B1, B2B3, ...Bn=Gque prueba Σ∪ {F} ` G. Demostraremos el resultado por inducción en n. Para el caso n= 1 tenemos que B1es un axioma, una fórmula de Σo es F. Si B1=Ges una fórmula de Σ: 1. Σ`(B→(F→G)) axioma 1. 2. Σ`Bya que G∈Σ. 3. Σ`(F→G)mp 1,2. Si G es un axioma: 1. Σ`(G→(F→G)) axioma 1. 2. Σ`Gpor ser G un axioma. 21 1. Σ`(¬F)ya que (¬F)∈Σ. 2. Σ`Fya que F∈Σ. 3. Σ`(F→((¬G)→F)) axioma 1 (sustituyendo G por (¬G)). 4. Σ`((¬F)→((¬G)→(¬F))) axioma 1 (sustituyendo F por (¬F)y G por (¬G)). 5. Σ`((¬G)→F)mp 3,2. 6. Σ`((¬G)→(¬F)) mp 4,1. 7. Σ`(((¬G)→F)→(((¬G)→(¬F)) →G)) lema 1.5. 8. Σ`(((¬G)→(¬F)) →G)mp 7,5. 9. Σ`Gmp 8,6. Lema 1.13. La fórmula ((F→G)→(((¬F)→G)→G)) es un teorema de la lógica proposicional. Demostración. Probaremos {(F→G),((¬F)→G)} ` Gy aplicaremos dos veces el teorema de la deducción para demostrar el lema. Sea Σ = {(F→G),((¬F)→G)}entonces: 1. Σ`(F→G)ya que (F→G)∈Σ. 2. Σ`((¬F)→G)ya que ((¬F)→G)∈Σ. 3. Σ`((F→G)→((¬G)→(¬F))) lema 1.9. 4. Σ`((¬G)→(¬F)) mp 3,1. 5. Σ`(((¬F)→G)→((¬G)→(¬(¬F)))) lema 1.9 (sustituyendo F por (¬F)). 6. Σ`((¬G)→(¬(¬F))) mp 5,2. 7. Σ`(((¬G)→(¬F)) →(((¬G)→((¬(¬F)) →G)) lema 1.5 (sustituyendo F por G y G por (¬F)). 8. Σ`(((¬G)→(¬F)) →G)por transitividad 7,6. 28 9. Σ`Gmp 8,4. Cualquier teorema de la lógica proposicional puede ser demostrado tomando el segundo sistema axiomático, es decir, tomaríamos como axioma la fórmula (((¬G)→(¬F)) →(((¬G)→F)→G)) en vez de (((¬G)→(¬F)) →(F→G)). Esto se debe a que (((¬G)→(¬F)) →(F→G)) es un teorema de la lógica proposicional que se puede demostrar desde el segundo sistema axiomático. Lema 1.14. La fórmula (((¬F)→(¬G)) →(G→F)) es un teorema de la lógica proposicional demostrable desde el segundo sistema axiomático definido. Demostración. Probaremos {((¬G)→(¬F))} ` (G→F)y aplicaremos el teorema de la deducción. 1. {((¬G)→(¬F))} ` ((¬G)→(¬F)) ya que ((¬G)→(¬F)) ∈ {((¬G)→(¬F))}. 2. (((¬G)→F)→(((¬G)→(¬F)) →G)) axioma 3. 3. (((¬G)→F)→G)lema 1.4 3,1. 4. (F→((¬G)→F)) axioma 1 (sustituyendo B por (¬G)). 5. (F→G)por transitividad 4,3. Observación 1.7. Notemos que para demostrar el corolario 1.1 y el lema 1.4 no hemos usado el tercer axioma de nuestro sistema axiomático(tampoco lo hemos usado para ningún resultado previo necesario para poder demostrar el corolario 1.1 y el lema 1.4). El hecho de que (((¬G)→(¬F)) →(F→G)) sea un teorema de la lógica proposicional demostrado desde el segundo sistema axiomático demuestra que cualquier teorema de la lógica proposicional demostrado desde el primer sistema axiomático también puede ser demostrado desde el segundo sistema axiomático. También hemos demostrado que la fórmula (((¬G)→(¬F)) →(((¬G)→F)→G)) es un teorema de la lógica proposicional demostrable si trabajamos con el primer sistema axiomático, es decir, cualquier teorema de la lógica proposicional demostrable desde el segundo sistema axiomático es demostrable desde el primer sistema axiomático. Finalmente concluimos que no varían los teoremas si trabajamos con el primer sistema axiomático o con el segundo. 29 Dada una valoración cualquiera y una fórmula F definimos la fórmula ˆ F de la siguiente manera: ˆ F=((¬F) si υ(F) = 0 Fcaso contrario (1.1) Lema 1.15. Sea F∈ P sobre P0={p1, p2, p3, ..., pk}yυuna valoración entonces {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ F. Demostración. Haremos inducción sobre el número de conectores en F. Si n= 0 entonces F es una variable proposicional, es decir F=picon i∈ {1,2,3, ..., k}y por tanto ˆ F= ˆpi. Para probar {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆpi basta hacer: 1. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆpiya que ˆpi∈ { ˆp1,ˆp2,ˆp3, ..., ˆpk}. Suponemos que el lema es válido para una cualquier fórmula con una cantidad de conectores menor que n. Sea G una fórmula con n conectores. La fórmula G es de la forma (¬H)o(H→J)con H y J fórmulas con una cantidad de conectores menor que n. Caso G= (¬H)yυ(H) = 1. Por ser υ(H) = 1 entonces ˆ H=Hyυ(G) = υ(¬H) = 0 entonces ˆ G= (¬G). Por hipótesis {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ H; {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` H. Probaremos {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ G. 1. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ Hya explicado. 2. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (H→(¬(¬H))) por el lema 1.8. 3. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬(¬H)) mp 2,1. (¬(¬H)) = (¬G) = ˆ G. Caso G= (¬H)con υ(H) = 0. Por ser υ(H) = 0 tenemos ˆ H= (¬H)yυ(G) = υ(¬H) = 1 y por consiguiente ˆ G=G. Por hipótesis {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ H; {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬H); {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` G. (G= (H→J)) con υ(H)=0. En este caso ˆ H= (¬H)yυ(G) = υ(C→J)=1entonces ˆ G=G. Por hipótesis {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ H; {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬H). Probaremos {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ G. 30 1. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬H)ya explicado. 2. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ((¬H)→(H→J)) lema 1.12. 3. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (C→J)mp 2,1. ˆ G=G= (H→J) Caso (G= (H→J)) con υ(J) = 1. En este caso ˆ J=Jyυ(G) = υ(H→J)=1entonces ˆ G=G. Por hipótesis {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ J;{ˆp1,ˆp2,ˆp3, ..., ˆpk} ` J. Probaremos {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ G. 1. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` Jya explicado. 2. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (J→(H→J)) axioma 1. 3. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (H→J)mp 2,1. ˆ G=G= (H→J) Caso (G= (H→J)) con υ(H)=1yυ(J)=0 υ(G) = υ(G= (H→J)) = 0 entonces ˆ G= (¬G) = (¬(H→J)). En este caso ˆ H=Hyˆ J= (¬J), por tanto {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` Hy {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬J). Probaremos {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ G 1. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` Hya explicado. 2. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬H)ya explicado. 3. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (H→((¬J)→(¬(H→J)))) lema 1.11. 4. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ((¬D)→(¬(C→J))) mp 3,1. 5. {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` (¬(H→J)) mp 4,2. Teorema 1.6. 1. Una fórmula es un teorema si y solo si es una tautología. 2. Un conjunto Σes consistente si y solo si existe una valoración tal que υ(x)=1para todo x∈Σ. 3. Una fórmula F es una consecuencia sintáctica del conjunto Σsi y solo si F es una consecuencia semántica del conjunto Σ, es decir Σ`Fsi y solo si Σ|=F. 31 Demostración. 1. Veremos que si F un teorema entonces F es una tautología. Cualquier teorema es el último término de una sucesión formada por axiomas o que han sido obtenidos por modus ponens, en ambos casos ya hemos comprobado que los axiomas y cualquier fórmula obtenida mediante modus ponens son tautologías. Veamos que si F es una tautología entonces es un teorema. Por ser tautología υ(F) = 1 para cualquier valoración, entonces ˆ F=F para cualquier valoración. Por el lema 1.15 tenemos {ˆp1,ˆp2,ˆp3, ..., ˆpk} ` ˆ F;{ˆp1,ˆp2,ˆp3, ..., ˆpk} ` F. Usando dos valoraciones diferentes υy tal que υ(pk) = 1,(pk) = 0 yυ(pi) = (pi)para todo i menor que k tenemos {ˆp1,ˆp2,ˆp3, ..., pk} ` Fy{ˆp1,ˆp2,ˆp3, ..., (¬pk)} ` F, aplicando el teorema de la deducción tenemos {ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` ( ˆpk→F)y{ˆp1,ˆp2,ˆp3, ..., ( ˆpk−1)} ` ((¬pk)→F). Veamos que {ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` Fde la siguiente manera: a){ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` ((pk→F)→(((¬pk)→F)→F)) por el lema 1.13. b){ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` (pk→F)ya explicado. c){ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` (((¬pk)→F)→F)mp a,b. d){ˆp1,ˆp2,ˆp3, ..., (ˆpk−1)} ` ((¬pk)→F)ya explicado. e){ˆp1,ˆp2,ˆp3, ..., ˆpk−1} ` Fmp c,d. De la misma forma se demuestra {ˆp1,ˆp2,ˆp3, ..., ˆpk−2} ` F. Si repetimos el proceso k−1veces demostramos ∅ ` F. 2. Primero veamos el siguiente lema: Si un conjunto Σes consistente entonces para cualquier fórmula G, bien Σ∪ {G}es consistente, bien Σ∪ {(¬G)}es consistente. Ya hemos probado que al menos uno de los dos conjuntos es inconsistente, ahora probaremos por reducción al absurdo que uno de ellos es consistente. Para probarlo supondremos que existe una fórmula G tal que ni Σ∪{G}ni Σ∪{(¬G)}son consistentes. Sea k una contradicción entonces por el teorema de la deducción tenemos Σ`((¬G)→k)y Σ`(G→k). Veamos que Σ`k: a)Σ`((¬G)→k)ya probado. b)Σ`(G→k)ya probado. 32 c)Σ`((G→k)→(((¬G)→k)→k)) lema 1.13. d)Σ`(((¬G)→k)→k)mp c,b. e)Σ`kmp d,a. Esto es absurdo, pues Σes consistente, luego o Σ∪ {G}oΣ∪ {(¬G)} es consistente. Definimos el conjunto de fórmulas Σ+de la siguiente manera: Σ+=(Σ∪ {G}si Σ ∪ {G}si es consistente Σ∪ {(¬G)}caso contrario (1.2) Observemos que Σ⊂Σ+ysiG∈Σ+entonces (¬G)/∈Σ+. Definimos υ(p)=1si p∈Σ+yυ(p)=0caso contrario y extendemos υa una valoración. Probaremos υ(G) = 1 si y solo si G∈Σ+. Haremos inducción sobre el número de símbolos de G. Caso n= 1. En este caso G es una variable proposicional. Por la definición dada se cumple el teorema. Suponemos que se cumple para cualquier fórmula con una cantidad de símbolos menor que n. Tenemos dos casos: Si G una fórmula del tipo (¬H)entonces υ(G) = 1 si y solo si υ(¬H)=1si y solo si υ(H)=0. Por hipótesis de inducción υ(H)=0si y solo si H /∈Σ+si y solo si (¬H)∈Σ+si y solo si G∈Σ+. Si G es una fórmula del tipo (H→J)entonces υ(G)=1si y solo si υ(H→J) = 1 si y solo si υ(H) = 0 oυ(J) = 1. Por hipótesis de inducción υ(H)=0oυ(J)=1si y solo si H /∈Σ+oJ∈Σ+ si y solo si (¬H)∈Σ+oJ∈Σ+. Veremos que en ambos casos Σ+`G. Si (¬H)∈Σ+entonces: a)Σ+`((¬H)→(H→J)) lema 1.12. b)Σ+`(¬H)ya que (¬H)∈Σ+. c)Σ+`(H→J)mp a,b. Como G= (H→J)entonces Σ+`G. Si J∈Σ+entonces: 33 a)Σ+`(J→(H→J)) axioma 1. b)Σ+`Jya que J∈Σ+. c)Σ+`(H→J)mp a,b. Por lo tanto Σ+`G. El conjunto Σ+es consiste, por lo tanto (¬G)/∈Σ+y por consiguiente G∈Σ+. Suponemos υ(G)=0. υ(G) = 0 si y solo si υ(H→J)=0si y solo si υ(H) = 1 yυ(J) = 0 si y solo si H∈Σ+yJ /∈Σ+si y solo si H∈Σ+y(¬J)∈Σ+. Veamos que Σ+`(¬G): a)Σ+`Hya que H∈Σ+. b)Σ+`(¬J)ya que (¬J)∈Σ+. c)Σ+`(H→((¬J)→(¬(H→J)))) teorema 1.11. d)Σ+`((¬J)→(¬(H→J))) mp c,a. e)Σ+`(¬(H→J)) mp d,b. Por lo tanto Σ+(¬G)como Σ+es consistente G /∈Σ+. Concluimos que υ(G)=1si y solo si G∈Σ+si y solo si G∈Σ. Veamos ahora que si existe una valoración υtal que υ(x)=1para todo x∈Σentonces Σes consistente. Para demostrar esto probaremos que si Σes inconsistente entonces no existe ninguna valoración υtal que υ(x) = 1 para todo x∈Σ. En el siguiente párrafo demostraremos que si existe una valoración υ tal que υ(x)=1para todo x∈Σentonces υ(F)=1si Σ`F. Por ser Σinconsistente existe una fórmula F tal que Σ`FyΣ`(¬F), por lo tanto υ(F) = υ(¬F) = 1, lo cual es absurdo. Por lo tanto, si el conjunto Σes inconsistente no existe ninguna valoración υtal que υ(x)=1para todo x∈Σ. 3. Veamos que si Σ`Fentonces Σ|=F. Si Σ`Fentonces existe una sucesión de fórmulas A1, A2, A3, ..., An=Ftal que para todo i∈ {1,2,3, ..., n}Aies, bien un 34 axioma, bien una fórmula de Σ, bien ha sido obtenido mediante modus ponens de AnyAmcon m, n < i. Sea υuna valoración cualquiera tal que para todo x∈Συ(x) = 1. Veamos por inducción sobre el número de términos de la sucesión A1, A2, A3, ..., An=Fque υ(F) = 1. Para n= 1 si A1∈Σentonces υ(A1)=1por hipótesis. Si A1es un axioma entonces υ(A1)=1para cualquier valoración, si A1 ha sido obtenido mediante la regla de inferencia modus ponens entonces existen dos fórmulas (G→A1)yGque son axiomas o pertenecen Σ, es decir, en ambos casos por hipótesis υ((G→A1)) = 1 yυ(G)=1. Sabemos que υ((G→A1)) = 1 si y solo si υ(G)=0oυ(A1) = 1, como υ(G)6= 0 entonces υ(A1)=1. Suponemos que para todo i<nse cumple υ(Ai)=1, veamos que υ(An) = 1. Si Anes un axioma o una fórmula de Σentonces, por los mismos razonamientos del párrafo anterior, υ(A1) = 1. Si Anha sido obtenido mediante la regla de inferencia modus ponens entonces existen dos fórmulas (G→An)yGque son axiomas o pertenecen Σo son términos de la sucesión anteriores a An. Si las fórmulas (G→An)yGson axiomas o pertenecen a Σentonces υ((G→An)) = 1 yυ(G)=1si son términos anteriores Anentonces, por hipótesis de inducción, υ((G→An)) = 1 yυ(G)=1. Al igual que en el párrafo anterior υ((G→A1)) = 1 si y solo si υ(G) = 0 o υ(A1) = 1, como υ(G)6= 0 entonces υ(A1) = 1. Veamos ahora que si Σ|=Fentonces Σ`F. Atendiendo a la definición de consecuencia semántica no descartaremos el caso en el que no exista ninguna valoración tal que para todo x∈Σ υ(x) = 1. Si estamos en este caso, hemos visto que un conjunto Σes consistente si y solo existe una valoración tal que para x∈Συ(x) = 1, es decir, Σes inconsistente. Por otra parte hemos probado que cualquier fórmula es una consecuencia sintáctica de un conjunto inconsistente, por tanto Σ`F. Suponemos ahora que existe al menos una valoración υtal que para todo x∈Συ(x)=1. Como Σ|=Fentonces υ(F) = 1. Por el apartado 2 de este teorema tanto Σcomo Σ∪ {F}son consistentes y Σ∪ {(¬F)}es inconsistente. En la demostración del lema 1.5 vimos que si Σ∪{(¬F)} es inconsistente entonces Σ`F. 35 Teorema 1.7. Sea Σun conjunto de fórmulas proposicionales entonces Σ es consistente si y solo si cada subconjunto finito de Σes consistente. Demostración. 1. Veamos que si Σes consistente entonces cada subconjunto finito de Σes consistente. Probar esta implicación es equivalente a probar que si existe un subconjuto finito de Σinconsiste entonces Σes inconsistente. Sea Γ⊂Σ inconsistente. Por el teorema anterior Γ`kcon k contradicción. La contradicción ha sido obtenida mediante axiomas, modus ponens y fórmulas en Γ⊂Σ, es decir, desde Σpodemos obtener la misma contradicción, por tanto, Σes inconsistente. 2. Veamos que si cada subconjunto finito de Σes consistente entonces Σ es consistente. Para probar esto veamos que si Σes inconsiste entonces existe algún subconjunto Γ⊂Σinconsistente. Por ser Σun conjunto inconsistente podemos obtener con una sucesión finita una contradicción, es decir, existe una sucesión A1, A2, A3, ..., An tal que An=ksiendo k una contradicción y cada Aicon i∈Nes, bien un axioma, bien una fórmula de Σ, bien ha sido obtenido mediante modus ponens. Entonces el conjunto Γ = S{Aj}tal que Aj∈Σes un conjunto finito contenido en Σy del cual deriva una contradicción, por tanto inconsistente. 36 Capítulo 2 Lógica de Primer Orden La lógica de primer orden toma la lógica proposicional y la amplia con el fin de ser más expresiva y reducir el número de sentencias que tenemos en la lógica proposicional. La lógica de primer orden es un sistema formal muy útil para analizar argumentos y para las matemáticas. Estudiaremos la lógica de primer orden por las limitaciones de la lógica proposicional. Por ejemplo: Si un gato juega con un segundo gato entonces el segundo gato juega con el primero. El gato Félix juega con el gato Isidoro, por lo tanto Isidoro juega con Félix. Es imposible de representar en la lógica proposicional, en cambio en la lógica de primer orden escribiríamos: {(∀x)(∀y)(juega(x, y)→juega(y, x)), juega(Félix, Isidoro)} |=juega(Isidoro, Félix). 2.1. Sintaxis y semántica de la lógica de primer orden. Definición 2.1. Definimos un alfabeto Adel sistema formal de la lógica de primer orden: Un conjunto de variables {u, v, w, ...}. Un conjunto de conectores {¬,∧,∨,→,↔}. Cuantificadores ‘∀0(para todo) y ‘∃0(existe). 37 El árbol que representa a la fórmula G es: = yf g xc Y finalmente el árbol que representa a la fórmula (∀y)(f(g(c, x)) = y) es: (∀y) = yf g xc 2. La fórmula atómica p(x, y, c)queda representada por el árbol: p cyx 3. La fórmula ((∀y)(f(g(c, x)) = y)→p(x, y, c)) es una fórmula de la forma (F→G). Conocemos los árboles que representan a (∀y)(f(g(c, x)) = y)yp(x, y, c). Según la definición y los árboles de las fórmulas F y G el árbol que representa a la fórmula ((∀y)(f(g(c, x)) = y)→p(x, y, c)) es: 44 → p cyx (∀y) = yf g xc Definición 2.11. Sea tun término denotaremos al conjunto de las variables de tde la forma V(t)y los definimos de la siguiente manera: 1. Si t=ccon c constante entonces V(t) = ∅. 2. Si t=xcon x variable entonces V(t) = {x}. 3. Si t=f(t1, t2, t3, ..., tn)con f una función entonces V(t) = SV(ti)con i∈ {1,2,3, ..., n}. Definición 2.12. Si Fes una fórmula denotaremos al conjunto de las variables de Fde la forma V(F)y lo definimos de la siguiente manera: 1. Si F= (t1=t2)con t1yt2términos entonces V(F) = V(t1)∪V(t2). 2. Si F=p(t1, t2, t3, ..., tn)con ppredicado entonces V(F) = SV(ti)con i∈ {1,2,3, ..., n}. 3. Si F= (¬G)entonces V(F) = V(G). 4. Si F= (G#H)con #conector binario entonces V(F) = V(G)∪V(H). 5. Si F= (∀x)GoF= (∃x)Gentonces V(F) = {x} ∪ V(G). Ejemplo 2.7. Sea F= (∃x)((∀y)p(x, y)∧(0 = f(z))) con ppredicado, f función y x,y,z variables veamos que V(F) = {x, y, z}. V(F) = {x} ∪ V(((∀y)p(x, y)∧(0 = f(z)))). 45 V(((∀y)p(x, y)∧(0 = f(z)))) = V((∀y)p(x, y)) ∪V((0 = f(z))). V((∀y)p(x, y)) = {y} ∪ V(x)∪V(y) = {y}∪{x}∪{y}. V((0 = f(z))) = V(0) ∪V(f(z)) = ∅ ∪ V(z) = ∅∪{z}={z}. Finalmente vemos que V(F) = {x, y, z}. Definición 2.13. Sea F una fórmula diremos que una aparición u ocurrencia de una variable x en la fórmula F es ligada(a un cuantificador) si es una aparición en una subfórmula del tipo (∀x)Go(∃x)G. Sea F una fórmula diremos que una aparición u ocurrencia es libre si no es ligada. Ejemplo 2.8. Sean p y q predicados vemos que en la fórmula F= ((∃x)p(x)→q(x)) la variable x tiene dos apariciones ligadas y una libre. El alcance del único cuantificador que hay en la fórmula F es la subfórmula (∃x)p(x), por lo tanto las dos primeras apariciones son ligadas y la tercera aparición es libre. Definición 2.14. Una variable x en una fórmula F es una variable ligada si tiene alguna aparición ligada en F. Una variable x en una fórmula F es una variable libre si tiene alguna aparición libre en F. Observación 2.7. Una aparición de una variable en una fórmula es, o bien libre, o bien ligada, pero una variable puede ser libre y ligada al mismo tiempo, como muestra la fórmula ((∃x)p(x)→q(x)). Teorema 2.2. Si Fes una fórmula el conjunto V L(F)de variables libres de F es: 1. Si Fes una fórmula atómica V L(F) = V(F). 2. Si F= (¬G)entonces V L(F) = V L(G). 3. Si F= (G#H)con #conector binario entonces V L(F) = V L(G)∪V L(H). 4. Si F= (∀x)GoF= (∃x)Gentonces V L(F) = V L(G)\{x}. Demostración. Sea Funa fórmula atómica. Usando la definición de fórmula atómica vemos que Fno puede tener cuantificadores, luego cualquier variable que haya en Fdebe ser libre, esto es V L(F) = V(F). 46 Sea Funa fórmula de la forma (¬G). Usando la definición de subfórmula sabemos que el conjunto de subfórmulas de Fes {(¬G)} ∪ Sb(G). Usando esta definición podemos deducir que si una variable está ligada a un cuantificador este cuantificador debe ser un símbolo de una subfórmula de G. Si F= (G#H)utilizamos un razonamiento similar al anterior. Sea Funa fórmula de la forma (∀x)Go(∃x)G. La variable x no tiene ninguna aparición libre en F ya que el alcance del cuantificador es la subfórmula G, luego la variable x no es una variable libre. Las subfórmulas de G son subfórmulas de F, luego si una variable distinta de x tiene una aparición libre o ligada en G también es libre o ligada en F. Definición 2.15. Llamaremos fórmula cerrada o sentencia a una fórmula sin variables libres. Ejemplo 2.9. Unos ejemplos de sentencias son: (∀x)(p(x)→p(x)) y (p(3,4) ∧(∃y)(∃x)(f(x, y) = f(y, x))). Definición 2.16. Llamaremos fórmula básica a una fórmula sin variables. Ejemplo 2.10. Una fórmula básica es (0 = 0) o>(8,4). Definición 2.17. Una sustutición σen un lenguaje L es una aplicación σ:V ar −→ Term(L)siendo Var el conjunto de las variables de L. Escribiremos [t1/x1, t2/x2, t3/x3, ..., tn/x3]para denotar a la aplicación σtal que σ(x) = (tisi xi=ti xsi x /∈ {x1, x2, x3, ..., xn}(2.1) Ejemplo 2.11. Sea c una constante y f una función escribimos [f(c)/x, c/y] para denotar la sustitución σen L tal que σ(x) = f(c)yσ(y) = cy las demás variables las envía a ellas mismas. Definición 2.18. Sea t un término escribiremos t[t1/x1, t2/x2, t3/x3, ..., tn/xn] para denotar al término obtenido tras sustituir las apariciones xipor tien el término t. Si σ= [t1/x1, t2/x2, t3/x3, ..., tn/xn]podemos escribir tσ. 47 Definición 2.19. La extensión de σen términos es la aplicación σ:Term(L)−→ Term(L)definida de la siguiente manera: tσ =     csi t es la constante c σ(x) si t es la variable x f(t1σ, t2σ, t3σ, ..., tnσ) si t es la función f (2.2) Ejemplo 2.12. Sea σ= [f(g(a, z), z)/x, g(a, z)/y, a/z]con a símbolo de constante. Según la definición el término f(g(a, z), z)σes f(g(a, z)σ, zσ) = f(g(aσ, zσ), σ(z)) = f(g(a, σ(z)), a) = f(g(a, a), a). Por tanto f(g(a, z), z)σ=f(g(a, a), a). Observación 2.8. Sean σ1= [f(y, a)/x],σ2= [a/y]yσ= [f(y, a)/x, a/y] con a constante veamos que f(x, y)σ1σ26=f(x, y)σ. f(x, y)σ1=f(xσ1, yσ1) = f(σ1(x), σ1(y)) = f(f(y, a), y); f(f(y, a), y)σ2=f(f(y, a)σ2, aσ2) = f(f(yσ2, aσ2), a) = f(f(σ2(y), a), a) = f(f(a, a), a). f(x, y)σ1σ2=f(f(a, a), a)f(x, y)σ=f(xσ, yσ) = f(σ(x), σ(y)) = f(f(y, a), a). Esto se debe a que σ1σ2yσson sustituciones diferentes, ya que σ1σ2= [f(a, a)/x, a/y]yσ[f(y, a)/x, a/y], por lo que σ1σ2(x)6=σ(x). Observación 2.9. Las sustituciones se pueden componer, sean σ1yσ2las sustituciones del ejemplo anterior, entonces la composición σ1σ2es [f(a, a)/x, a/y]. Definición 2.20. Sea σuna sustitución y x una variable definimos la sustitución σxde la siguiente forma: σx(y) = (xsi x=y σ(y) si x6=y(2.3) Definición 2.21. La extensión de σen la fórmula F es la aplicación σ:F(L)−→ F(L)definida de la siguiente manera: Fσ =                (t1σ=t2σ) si F es de forma (t1=t2) (Gσ#Hσ) si F es de la forma G#Hcon # conector binario. (¬(Gσ)) si F es de forma (¬G) (∀x)Gσxsi F es de forma (∀x)G (∃x)Gσxsi F es de forma (∃x)G (2.4) 48 Definición 2.22. Escribimos F[t1/x1, t2/x2, t3/x3, ..., tn/xn]para denotar al término obtenido tras sustituir las apariciones libres xipor tien la fórmula F. Si σ= [t1/x1, t2/x2, t3/x3, ..., tn/xn]podemos escribir tσ. Definición 2.23. Sea F una fórmula y σuna sustitución diremos que σes libre para F si todas las apariciones de variables introducidas por la sustitución son libres. Al escribir Fσ la sustitución σes libre en F a no ser que indiquemos lo contrario. Ejemplo 2.13. Para la fórmula F con F= (x=y)cualquier sustitución es libre(cualquier sustitución en una fórmula sin cuantificadores es una sustitución libre). Sea σ= [y/x]vemos que σes libre para (∀x)f(x)pero no es libre para (∃y)f(x). Observación 2.10. Cuando sustituimos en una fórmula lo hacemos como máximo una vez por variable, es decir (f(x) = 0)[f(x)/x]es (f(f(x)) = 0) y no repetiríamos infinitas veces una sustitución. Definición 2.24. Sea L un lenguaje. Una L-estructura es un par M= (M, I)donde M es un conjunto no vacío denominado dominio e I es una función. El dominio de I es el conjunto de símbolos de L. La función I debe cumplir: I(c)∈Msi c∈Les un símbolo de constante. I(f) : Mn−→ Msi f∈Les una función de aridad n. I(p)⊆Mnsi p∈Les una relación de aridad n. Habitualmente diremos que Mes una estructura si no hay lugar a confusión. Definición 2.25. Una asignación Aen una estructura M= (M, I)es una función A:V ar −→ Mdonde V ar es el conjunto de las variables del alfabeto. Definición 2.26. Una interpretación(o valoración según algunos autores) de L es un par formado por una L-estructura My una asignación A en M. 49 Ejemplo 2.14. Sean aybconstantes y fayfbfunciones crearemos para el lenguaje L={a, b, fa, fb}una estructura. El dominio Mes el conjuto de las palabras que empiezan por a y tienen al menos dos símbolos, escribiremos M=a{a, b}+. I(a) = aa. I(b) = ab. I(fa) : M−→ Mcon I(fa)(w) = wa. I(fb) : M−→ Mcon I(fb)(w) = wb. Veamos otro ejemplo para el mismo lenguaje siendo el dominio Mpuede ser los palíndromos pares: I(a) = aa. I(b) = bb. I(fa) : M−→ Mcon I(fa)(w) = awa. I(fb) : M−→ Mcon I(fb)(w) = bwb. Definición 2.27. Sean M= (M, I)una L-estructura y Auna asignación en Mllamaremos evaluación de términos a la función MA:Térm(L)−→ M definida de la siguiente manera: MA(t) = I(c)si t es el símbolo de constante c. MA(t) = A(x)si t es la variable x. MA(t) = I(f(MA(t1),MA(t2),MA(t3), ..., MA(tn))) si t es la función f(t1, t2, t3, ..., tn). MA(t)se lee “el valor de t en Mrespecto de A". Ejemplo 2.15. Sean t=fa(fb(a)) yt=fa(fb(x)) términos, a una constante, fayfblas funciones del ejemplo anterior y A(x) = buna asignación. Veamos el valor de estos términos en Mcon respecto de A. MA(fa(fb(a))) = I(fa(MA(fb(a)))) = I(fa(I(fb(MA(a))))) = I(fa(I(fb)(I(a)))); MA(fa(fb(a))) = I(fa(I(fb)(aa)) = I(fa(aab)) = aaba. MA(fa(fb(x))) = I(fa(MA(fb(x)))) = I(fa(I(fb(MA(x))))) = I(fa(I(fb)(I(x)))); MA(fa(fb(x))) = I(fa(I(fb)(A(x))) = I(fa(I(fb)(b)) = I(fa(bb)) = abb. 50 Definición 2.28. Sean M= (M, I)una L-estructura, Auna asignación en M, x e y variables y m∈Mdefinimos la asignación A[x/m](y)de la siguiente manera: A[x/m](y) = (msi y=x A(y) si y6=x(2.5) Definición 2.29. La función de verdad de la igualdad en un dominio M es la función V=:M2−→ {0,1}definida de la siguiente manera: V=(t1, t2) = (1 si t1=t2 0 caso contrario (2.6) La función de verdad para una relación p en un dominio M es la función Vp:Mn−→ {0,1}definida de la siguiente manera: Vp(t1, t2, t3, ..., tn) = (1 si (t1, t2, t3, ..., tn)∈p 0 caso contrario (2.7) Definición 2.30. Sean M= (M, I)una estructura y A una asignación sobre M, la función evaluación de fórmulas es la función MA:Fórm(L)−→ {0,1}definida de la siguiente manera: MA((t1=t2)) = V=(MA(t1),MA(t2)). MA(p(t1, t2, t3, ..., tn)) = VI(p)(MA(t1),MA(t2),MA(t3), ..., MA(tn)). MA(¬F) = V¬(F) = (1 siMA(F)=0 0 caso contrario (2.8) Sea F= (G∧H)entonces MA(G∧H) = V∧(F) = (1 si MA(G) = 1y MA(H)=1 0 caso contrario (2.9) Sea F= (G∨H) MA(G∨H) = V∨(F) = (0 si MA(G) = 0y MA(H)=0 1 caso contrario (2.10) 51 Sea F= (G→H) MA(G→H) = V→(F) = (0 si MA(G) = 1y MA(H) = 0 1 caso contrario (2.11) Sea (∃x)G=F MA((∃x)G) = V∃(F) = (1 si existe al menos un m∈Mtal que MA[x/m](G)=1 0 caso contrario (2.12) Sea (∀x)G=F MA((∀x)G) = V∀(F)(1 si para todo m∈Mtenemos MA[x/m](G)=1 0 caso contrario (2.13) (Cuando escribamos MA(F)leeremos “el valor de F en Mrespecto de A"). Si MA(F)=1escribiremos MA|=F, en el caso contrario escribiremos MA |=F. Observación 2.11. Un forma más resumida de la definición anterior es: dado una estructura M= (M, I)y una asignación A en Mentonces: 1. MA|= (t1=t2)si y solo si MA(t1) = MA(t2). 2. MA|=p(t1, t2, t3, ..., tn)si y solo si (MA(t1),MA(t2),MA(t3), ..., MA(tn)) ∈I(p). 3. MA|= (¬F)si y solo si MA |=(F). 4. MA|= (F∧G)si y solo si MA|=FyMA|=G. 5. MA|= (F∨G)si y solo si MA|=FoMA|=G. 6. MA|= (F→G)si y solo si MA |=FoMA|=G. 7. MA|= (∃x)Fsi y solo si existe al menos un a∈Mtal que MA[x/a]|=F. 8. MA|= (∀x)Fsi y solo si para todo a∈Mtenemos MA[x/a]|=F. 52 Definición 2.31. Sean Muna estructura y A una asignación en Mdiremos que el par (M, A)es una realización de la fórmula F si MA(F)=1y lo representaremos por MA|=F(diremos que F se verifica en Mrespecto de A). Diremos que el par (M, A)es una realización del conjunto de fórmulas Σsi para todo F∈Σtenemos MA|=Fy denotaremos MA|= Σ. El par (M, A)no es una realización de la fórmula F si MA(F)=0y lo representaremos por MA |=F(diremos que F no se verifica en Mrespecto de A). El par (M, A)no es una realización del conjunto de fórmulas Σsi existe F∈Σtal que MA(F)=0y lo representaremos por MA |=Σ. Definición 2.32. Sean Funa fórmula y M= (M, I)una L-estructura diremos que F es satisfacible en Msi existe una asignación Aen Mtal que MA|=F. Si F no es satisfacible diremos que es insatisfacible. Ejemplo 2.16. Sean M= (M, I)una L-estructura, +y∗símbolos de funciones binarias y ≥y<símbolos de predicados binarios. La fórmula F= (∗(0, x) = 0) es satisfacible, ya que para cualquier asignación A tenemos MA|= (∗(0, x) = 0). La fórmula F= (∗(1,1) = 0) es insatisfible, no existe ninguna asignación A tal que MA|= (∗(1,1) = 0). Nos podemos preguntar si la fórmula F= (∃y)p(3, y)es satisfacible en M= (N, I)con I(p) = |(x, y). Si tomamos la asignación A(x) = 12 vemos que MA|=F, luego F es satisfacible. Definición 2.33. Una estructura M= (M, I)es un modelo para una fórmula F si para toda asignación A en Mtenemos MA|=Fy denotaremos M |=F. Una estructura Mes un modelo para un conjunto de fórmulas Σsi para todo F∈Σtenemos M |=F. Ejemplo 2.17. La estructura M= (N, I)es un modelo para la fórmula (0 = 0) ya que para cualquier asignación A tenemos MA((0 = 0)) = V=(MA(0),MA(0)) = 1, por lo tanto |=(0 = 0). Veamos que la estructura M= (N, I)con I(c) = cpara cualquier constante es un modelo para la fórmula (∀x)≥(x, 0). Sea A una asignación cualquiera. Por definición MA((∀x)≥(x, 0)) = 1 si y solo si para todo n∈NMA[x/n](≥(x, 0)) = 1. 53 Cuando usemos la regla de inferencia generalización para deducir una consecuencia lógica sintáctica de un conjunto Σdebemos hacerlo con variables que no tengan ninguna aparición libre en ninguna fórmula de Σ. Veámoslo con un ejemplo: Sea Σ = {(∃y)(y=z)}siendo y una variable entonces: 1. Σ`(∃y)(y=z)ya que (∃y)(y=z)∈Σ. 2. Σ`(∀y)(∃y)(y=z)por generalización(y no tiene ninguna aparación libre en la única fórmula de Σ, no podríamos usar la regla de generalización para inferir (∀z)(∃y)(y=z)ya que la variable z si tiene una aparición libre en una fórmula de Σ). Observación 2.12. Todos los teoremas probados para la lógica proposicional son válidos para la lógica de primer orden. Esto se debe a que en la lógica proposicional se razona con axiomas y reglas de inferencia que también pertenecen al sistema formal de la lógica de primer orden. Observación 2.13. Si F es un axioma entonces MA(F)=1para cualquier estructura My cualquier asignación A en M. Vamos a verlo con alguno de ellos: Tomemos el axioma (F→(G→F)). Por reducción al absurdo veamos que MA(F→(G→F)) = 1. Si MA((F→(G→F))) = 0 entonces MA(F)=1yMA((G→F)) = 0. Como MA((G→F)) = 0 entonces MA(F)=0, por tanto absurdo. Tomemos el axioma ((∀x)(F→G)→(F→(∀x)G)) donde la variable x no tiene apariciones libres en la fórmula F. Por reducción al absurdo veamos que MA(((∀x)(F→G)→(A→(∀x)G))) = 1. Si MA(((∀x)(F→G)→(F→(∀x)G))) = 0 entonces MA((∀x)(F→G)) = 1 yMA((F→(∀x)G)) = 0. Por definición MA((∀x)(F→G)) = 1 si para todo a∈M MA[x/a](F→G)=1y esto último se da siempre que no se cumplan de forma simultáneas MA[x/a](F) = 1 yMA[x/a](G) = 0. Por otra parte si MA((F→(∀x)G)) = 0 entonces MA(F) = 1 y MA((∀x)G) = 0. La variable x no tiene aparaiciones libres en la fórmula F, luego x es una variable ligada en F y por tanto las asignaciones A y A[x/a] coinciden sobre las variables libres de F, por lo tanto MA(F) = MA[x/a](F) = 1. Como MA[x/a](F) = 1 entonces MA[x/a](G) = 1 60 para todo a∈M. Por otra parte tenemos MA((∀x)G) = 0, luego existe a∈Mtal que MA[x/a](G)=0, por tanto absurdo. Teorema 2.3. (De la Deducción)Si Σ∪{F} ` Gentonces Σ`(F→G). Demostración. Como Σ∪ {F} ` Gentonces existe una demostración G1, G2, G3, ..., Gn=Gdonde Gies un axioma, una fórmula de Σ∪ {F}o ha sido obtenida mediante una regla de inferencia(modus pones o generalización). Veamos por inducción sobre la longitud de la demostración que Σ`(F→G). Si n= 1 entonces G1=Ges un axioma o G∈Σ{F}. Si G=Fya vimos que G→Ges un teorema de la lógica proposicional y por tanto también es un teorema de la lógica de primer de orden. Si G6=F: 1. Σ`(G→(F→G)) axioma 1. 2. Σ`Gya que G es axioma o G∈Σ. 3. Σ`(F→G)mp 1,2. Suponemos ahora que el teorema se cumple para cualquier demostración con una longitud menor que n. Si G es axioma o G∈Σ∪{F}utilizamos la demostración anterior. Si G ha sido obtenido mediante modus ponens entonces existen Gmy(Gm→G)tales que Σ∪{F}GmyΣ∪{F} ` (Gm→G)(observemos que m < n). Veamos que Σ`G: 1. Σ(F→Gm)por hipótesis de inducción. 2. Σ`(F→(Gm→G)) por hipótesis de inducción. 3. Σ`((F→(Gm→G)) →((F→Gm)→(F→G))) axioma 2 (sustituyendo A por F, B por Gmy C por G). 4. Σ`((F→Gm)→(F→G)) mp 3,2. 5. Σ`(F→G)mp 4,1. Si G ha sido obtenido por generalización entonces G es de la forma (∀x)H donde x no es una variable en ninguna fórmula de Σ∪ {F}además existe una demostración menor que n que pruebe Σ∪{F} ` H. Veamos que Σ`G: 1. Σ`(F→H)por hipótesis de inducción. 61 2. Σ`(∀x)(F→H)generalización 1. 3. Σ`((∀x)(F→H)→(F→(∀x)H)) axioma 5(recordemos que x no tiene apariciones libres en F, luego no es una variable libre de F). 4. Σ`(F→(∀x)H)mp 3 y 2. Definición 2.37. El conjunto Σes inconsistente si existe una fórmula F tal que Σ`FyΣ`(¬F). El conjunto Σes consistente si no es inconsistente. Definición 2.38. Una fórmula F es consecuencia lógica(semántica) de un conjunto de fórmulas Σsi todas las realizaciones de Σson realizaciones del conjunto unitario {F}y denotaremos Σ|=F. Si una fórmula F no es consecuencia lógica de un conjunto de fórmulas Σ escribiremos Σ |=F. Definición 2.39. Un conjunto de fórmulas Σes completo si, para cualquier fórmula F, o F o (¬F)pertenecen al conjunto Σ. Teorema 2.4. Si Σ`Fentonces Σ|=F. Demostración. Veamos por inducción sobre la longitud de la demostración que si Σ`Fentonces Σ|=F. Si la demostración tiene un único término A1=Fentonces F es un axioma o F∈Σ. Si F es un axioma por el lema 2.13 sabemos que MA(F)=1para cualquier estructura My cualquier asignación A en M. Si F∈Σ. Sea (M, A)una realización tal que para todo x∈ΣMA(x) = 1. Como F∈Σentonces MA(F) = 1. Supongamos ahora que para toda sucesión con menos de n términos se cumple el teorema. Sea A1, A2, A3, ..., An=Funa demostración de n términos veamos que Σ|=F. Si F es un axioma o F∈Σes el mismo raonamiento que el caso base. Si no es el caso entonces F ha sido obtenido mediante modus ponens o generalización. Si F ha sido obtenida mediante modus ponens entonces existen Ai= (Aj→F)yAjcon i, j < n tales que, por hipótesis de inducción MA((Aj→F)) = 1 yMA(Aj) = 1, por lo tanto MA(F) = 1. Si F ha sido obtenida mediante generalización entonces F es de la forma 62 (∀x)Gy existe Aj=Gcon j < 1tal que, por hipótesis de inducción, MA(G)=1. Por definición MA((∀x)G)=1si y solo si para todo a∈M MA[x/a](G)=1. Recordemos que la variable x no tiene apariciones libres en G, por tanto no es una variable libre en G, entonces las asignaciones A y A[x/a]coinciden sobre las variables libres de G, luego MA(G) = MA[x/a](G) = 1. Teorema 2.5. Sea L un lenguaje de primer orden con una cantidad finita o numerable de símbolos de función, relación y constantes. Si existe una L-estructura My una asignación A en Mtal que MA(x)=1para todo x∈Σentonces el conjunto de fórmulas Σes consistente. Demostración. Veamos que si existe un par (M, A)tal que MA(x) = 1 para todo x∈Σentonces Σes consistente. Para ello probaremos que si Σ es inconsistente no existe ningún par (M, A)tal que MA(x) = 1 para todo x∈Σ. Si Σfuera inconsistente existiría una fórmula F tal que Σ`FyΣ`(¬F). Por el teorema anterior Σ|=FyΣ|= (¬F). Si existiera al menos un par (M, A)tal que MA(x) = 1 para todo x∈Σentonces MA(F) = 1 y MA((¬F)) = 1, lo cual es imposible. Por lo tanto si Σes inconsistente no existe ningún par (M, A)tal que MA(x)=1para todo x∈Σ. Lema 2.5. Sean L un lenguaje de primer orden con una cantidad finita o contable de símbolos de función, relación y constantes y Σun conjunto consistente de fórmulas de L, entonces Σestá contenido en un conjunto completo consistente. Demostración. Como hemos visto en el teorema 1.6, si Σconsistente entonces para cualquier fórmula F entonces Σ∪{F}oΣ∪{(¬F)}es consistente, ya que si Σ∪{F}yΣ∪{(¬F)}fueran inconsistentes llegaríamos a una contradicción utilizando los axiomas 1, 2 y 3 de la lógica de primer orden. Sea F0, F1, F2, ... la secuencia de los elementos del conjunto Σpodemos ampliarla en el n-ésimo término con Fno(¬F)(eligiendo siempre la fórmula con la que obtendremos un nuevo conjunto consistente). Demostraremos el teorema por inducción. Definimos Σ0de la siguiente manera: Σ0=(Σ∪ {F}si Σ ∪ {F}es consistente Σ∪ {(¬F)}si Σ ∪ {(¬F)}es consistente (2.14) 63 Definimos Σnde la siguiente manera: Σn=(Σn−1∪ {Fn}si Σn−1∪ {Fn}si es consistente Σn−1∪ {(¬Fn)}si Σn−1∪ {(¬Fn)}es consistente (2.15) Sea Σ+=SΣn, veamos que Σestá contenido en el conjunto completo Σ+. Por definición del conjunto Σ+vemos que Σ⊂Σ0⊂Σ1⊂Σ2⊂...Σ+. YΣ+es un conjunto completo, ya que para cualquier fórmula Fn, o bien Fn∈Σn⊂Σ+, o bien (¬Fn)∈Σn⊂Σ+. Veamos por inducción sobre n que Σ+es consistente. Para n= 0 veamos que Σ0es consistente. El conjunto Σes consiste según el enunciado y hemos probado(en la demostración del teorema 1.6) que Σ∪ {F0}oΣ∪ {(¬F0)}es consistente. Usando la definición de Σ0concluimos que Σ0es consistente (es consistente por que hemos podido definirlo de tal manera que sea consistente). Veamos que si Σnes consistente entonces Σn+1 es consistente. El conjunto Σnes consiste por hipótesis y hemos probado(en la demostración del teorema 1.6) que Σn∪ {Fn+1}oΣn∪ {(¬Fn+1)}es consistente. Usando la definición de Σn+1 concluimos que Σn+1 es consistente (es consistente por que hemos podido definirlo de tal manera que sea consistente). Lema 2.6. Sean L un lenguaje de primer orden con una cantidad finita o contable de símbolos de función, relación y constantes y Σun conjunto consitente de fórmulas de L entonces existe una realización para Σ. Demostración. Por el lema anterior podemos extender el conjunto Σa un conjunto Σ+consistente y completo. Construimos una L-estructura M= (M, I)y A una asignación donde el dominio M es el conjunto de todos los términos cerrados del lenguaje, es decir, términos sin variables. Observemos que M es un conjunto numerable. Para la función I tenemos: I(c) = csi c es un símbolo de constante. I(f(t1, t2, t3, ..., tn)) = f(I(t1), I(t2), I(t3), ..., I(tn))) si f es una función de aridad n y t1, t2, t3, ..., tntérminos cerrados. Para un predicado p I(p)((t1, t2, t3, ..., tn)) es verdad ((t1, t2, t3, ..., tn) están relacionados por I(p)) si Σ`p(t1, t2, t3, ..., tn). A partir de la estructura Mvamos a definir la estructura ¯ M= ( ¯ M, ¯ I). Sean t1yt2términos definimos en el conjunto M la relación binaria de 64 la siguiente manera: ∼(t1, t2)(habitualmente escribimos t1∼t2) si y solo si Σ`(t1=t2)(por los axiomas 6,7 y 8 sabemos que es una relación de equivalencia en M). Tomamos el cociente ¯ M=M/∼Veamos que ¯ Mes un modelo para Σ+y por tanto también para Σ. Veamos que ¯ M(x)=1si y solo si x∈Σ+(solamente necesitamos probar la implicación indirecta). Sea F∈Pk⊂ P una fórmula de Σ+veamos por inducción sobre k que ¯ M(F) = 1. Si k= 0 entonces F es una fórmula átomica, es decir, F es (t1=t2)con t1 yt2términos o F es un predicado. Supongamos que F es de la forma (t1=t2). F∈Σ+si y solo si Σ+`Fsi y solo si t12(es decir, la clase de t1es la clase de t2) si y solo si ¯ M(t1) = ¯ M(t2)si y solo si ¯ M((t1=t2)) = 1. Si F es un predicado ya hemos visto por construcción que se cumple. Supongamos que para todo k < n se cumple el teorema, es decir, si F∈Pk⊂ P entonces ¯ M(F)=1. Sea F una fórmula de la forma (¬G). (¬G)∈Σ+si y solo si G /∈Σ+por ser Σ+consistente, G /∈Σ+si solo si Σ+  `Gsi y solo si ¯ M(G) = 0 por hipótesis de inducción. Por definición ¯ M(G)=0si y solo si ¯ M((¬G)) = 1. Sea F una fórmula de la forma (G→H). Veamos que si F∈Σ+entonces ¯ M(F)=1. Por ser Σ+un conjunto completo tenemos estas cuatro posibilidades: {G, H} ⊂ Σ+. {G, (¬H)} ⊂ Σ+. {(¬G), H} ⊂ Σ+. {(¬G),(¬H)} ⊂ Σ+. Si {G, H} ⊂ Σ+entonces ¯ M(H)=1por hipótesis de inducción, luego ¯ M(F)=1por definición. Si {(¬G)} ∈ Σ+entonces ¯ M(¬G) = 1 por hipótesis, luego ¯ M(G) = 1 y ¯ M(F)=1. Si {G, (¬H),(G→H)} ⊂ Σ+entonces Σ+`H(usando modus ponens) y Σ+`(¬H), luego Σ+es inconsistente, por lo tanto {G, (¬H)}  ⊂Σ+. Si F es de la forma (∀x)Gveamos que G∈Σ+: 65 1. Σ+`(∀x)Gya que (∀x)G∈Σ+. 2. Σ+`((∀x)G→G[x/x]) axioma 4. 3. Σ+`G[x/x]mp 1,2. Observemos que G[x/x] = G. Por ser Σ+completo entonces G∈Σ+o (¬G)∈Σ+. Por ser Σ+consistente G∈Σ+. Para una asignación A cualquiera tenemos ¯ MA((∀x)G)si y solo si para todo a∈¯ Mtenemos ¯ MA[x/a](G) y esto último se cumple por hipótesis. Hemos probado que ¯ Mes modelo para Σ+, por lo tanto también es modelo para Σ. Teorema 2.6. Sea L un lenguaje de primer orden con una cantidad finita o contable de símbolos de constantes, funciones y predicados entonces: si Σ|=Fentonces Σ`F. Demostración. Si Σes inconsistente entonces Σ`Fpara cualquier fórmula F de la lógica de primer orden(por el lema 1.5, que solo usa la definición de conjunto inconsistente y los axiomas 1,2 y 3). Si Σes consistente entonces existe al menos una interpretación (M, A)tal que MA(x) = 1 para todo x∈Σ. Como Σ|=Fentonces MA(F) = 1, por lo tanto MA(¬F) = 0. Es decir, no existe ningún par (M, B)tal que MB(x) = 1 para todo x∈Σ∪ {(¬F)}, luego Σ∪ {(¬F)}es inconsistente. Por ser Σ∪ {(¬F)}inconsistente podremos deducir de él cualquier fórmula, por lo tanto si C es un axioma Σ∪{(¬F)} ` CyΣ∪{(¬F)} ` (¬C). Veamos que Σ`F. 1. Σ`((¬F)→(¬C)) aplicando el teorema de la deducción a Σ∪ {(¬F)} ` (¬C). 2. Σ`(((¬F)→(¬C)) →(C→F)) axioma 3. 3. Σ`(C→F)mp 1,2. 4. Σ`Cpor ser C un axioma. 5. Σ`Fmp 3,4. 66 Capítulo 3 Fundamentación de las Matemáticas Los matemáticos Zermelo(1871-1953) y Fraenkel(1891-1965) plantearon una lista de axiomas que fundamentaron las matemáticas de manera que, junto con el axioma de elección, se construyen todos los conceptos, resultados y teoremas que se conocen de la matemáticas utilizando solamente la noción de conjunto como concepto primitivo no definido. 3.1. Sistema axiomático de la teoría de conjuntos de Zermelo-Fraenkel. La teoría de conjuntos se formaliza con el lenguaje L={∈} de primer orden, siendo ∈un predicado binario(escribiremos x∈yox /∈yen vez de ∈(x, y)o(¬(∈(x, y)))). Distintos autores dan diferentes conjuntos de axiomas de Zermelo-Fraenkel. Aquí escribiremos los axiomas de ZermeloFraenkel, ZF, según el libro [3]. 1. Axioma del conjunto vacío. Existe un conjunto ∅sin ningún elemento. (∃x)(∀u)(u /∈x). 2. Axioma de extensionalidad. Si dos conjuntos tienen los mismos conjuntos como elementos entonces 67 los dos conjuntos son iguales. (∀x)(∀y)((∀u)((u∈x)←→ (u∈y)) →(x=y)). Definimos el símbolo ⊆de la siguiente manera: (∀x)(∀y)((x⊆y)←→ (∀z)((z∈x)→(z∈y))). 3. Axioma de formación de pares. Definimos el par no ordenado formado por los conjuntos x e y(escrito habitualmente como {x, y}). (∀x)(∀y)(∃z)(∀u)((u∈z)←→ ((u=x)∨(x=y))). 4. Axioma del conjunto potencia o axioma de las partes del conjunto. Existe un conjunto x que contiene a cualquier subconjunto de cualquier conjunto. (∀x)(∃y)(∀u)((u∈y)←→ (∀v)((v∈u)→(v∈x))). A partir de ahora llamaremos conjunto de partes de un conjunto cualquiera X al conjunto P(X)cuyos elementos son los subconjuntos de X. (∀x)(∃y)((y=P(x)) ←→ (∀z)((z∈y)←→ (z⊆x))). 5. Axioma del conjunto unión. Dado un conjunto x existe un conjunto cuyos elementos son los elementos de los elementos de x. (∀x)(∃y)(∀u)((u∈y)←→ (∃v)((u∈v)∧(v∈x))). Dado un conjunto x definimos el conjunto Sxcomo la unión de los conjuntos pertenecientes al conjunto x: (∀x)(∀y)((y=[x)←→ (∀z)((z∈y)←→ (∃t)((t∈x)∧(z∈t)))). Por ejemplo S{x, y}=x∪y. 6. Axioma del infinito. Este axioma garantiza la existencia de un conjunto con una cantidad infinita de elementos. (∃x)((∃u)((u∈x)∧(∀v)(v /∈u)) ∧(∀u)((u∈x)→ (∃v)((v∈x)∧(∀w)((w∈v)←→ ((w∈u)∨(w=u)))))). 68 7. Axioma de reemplazamiento. Este axioma nos garantiza que la imagen de un conjunto por una función definida a través de una fórmula es también un conjunto. (∀x1)(∀x2)(∀x3)...(∀xn)((∀y)(∃!vF(u, v, x1, x2, x3, ..., xn)) →(∀x)(∃y)(∀v)((v∈y)←→ (∃u)((u∈x)∧(F(u, v, x1, x2, x3, ..., xn))))). 8. Axioma de regularidad. Este axioma impide que un conjunto pueda pertenecerse a si mismo y además para para cualquier conjunto no vacío x existe un conjunto y tal que y∈xyx∩y=∅. (∀x)((∃u)(u∈x)→(∃v)((v∈x)∧(∀w)(¬((w∈x)∧(w∈v))))). Definición 3.1. De los axiomas de Zermelo-Fraenkel se deduce el esquema axiomatico de separación en el que para un predicado p tenemos: (∀x)(∃y)(∀z)((z∈y)←→ ((z∈x)∧p(z))). El esquema axiomático de separación permite concluir que los elementos de un conjunto que cumplen una fórmula es también un conjunto. Definimos el conjunto Txcomo el conjunto cuyos elementos son los elementos de los elementos de x, es decir \x={t|(∃y)((t∈y)∧(y∈x))}. La intersección entre dos conjuntos X e Y la definimos como TZdonde Z= {X, Y }(escribiremos X∩Y).Laobtencióndelesquemaaxiomáticodeseparaciónnonosdetendremosadesarrollarla, noobstanteindicamosqueenlaspágincas114y115dellibro[2]vieneprobado. Lema 3.1. Si x0, x1, x2, ... son conjuntos entonces no se puede dar el caso xi+1 ∈xipara todo n∈N, es decir, no existe la cadena infinita ...x2∈x1∈x0. Demostración. Supongamos que x={xn|n∈N}es un conjunto. Por el axioma de regularidad debe existir un xi∈xtal que xi∩x=∅, mas para todo i∈Nxi+1 ∈xiyxi+1 ∈x, luego x∩xi6=∅para todo i∈N. Por lo tanto x={xn|n∈N}no es un conjunto. Lema 3.2. Si x es un conjunto entonces {x}yx∪ {x}son conjuntos. Demostración. Si x es conjunto entonces por el axioma de formación de pares {x, x}es un conjunto y por el conjunto de extensionalidad {x, x}={x}, luego {x}es un conjunto y finalmente por el axioma del conjunto unión concluimos que x∪ {x}es un conjunto. 69 tanto (S(n), h(p(n))) ∈fyp(n) = f(n)por definición de f, luego (∀n)((n∈N)→((n∈dom(f)) ∧(f(S(n)) = h(f(n))))). Veamos por el principio de inducción que dom(f) = N. Como 0∈dom(p)para todo p∈ A yA 6=∅entonces 0∈dom(f). Si n∈dom(f)entonces existe una función p∈ A con n∈dom(p). Tomando q=p∪ {(S(n), h(p(n)))} ∈ A vemos que S(n)∈dom(q)⊆dom(f). Luego dom(f) = N Corolario 3.1. Para dos conjuntos cualesquiera Y y E y funciones g:Y−→ E,h:E×Y−→ Eexiste una única función f:N×Y−→ Eque satisface f(0, y) = g(y)yf(S(n), y) = h(f(n, y), y). Demostración. Para cada y∈Ydefinimos la función hy:E−→ Emediante la fórmula hy(w) = h(w, y). Por el teorema de recursión sabemos que existe una única función fy:N−→ Etal que fy(0) = g(y)y fy(S(n)) = hy(fy(n)) = h(fy(n), y). Sea f(n, y) = fy(n)veamos que f(0, y) = g(y)yf(S(n), y) = h(f(n, y), y). Por definión f(0, y) = fy(0) yfy(0) = g(y), luego f(0, y) = g(y). Por definición f(S(n), y) = fy(S(n)) y fy(S(n)) = hy(fy(n)) = h(fy(n), y) = h(f(n, y), y), luego f(S(n), y) = h(f(n, y), y). Lema 3.5. Si existen dos sistemas de Peano (N1,01, S1)y(N2,02, S2)entonces existe una biyección Π : N1−→ N2tal que Π(01)=02y Π(S1(n)) = S2(Π(n)) para todo n∈N1, es decir, los sistemas de Peano son únicos salvo isomorfismos. Demostración. Por el teorema de recursión en (N1,01, S1)con E=N2, a= 0 yh=S2sabemos que existe una única función Πque satisface Π(01) = 02yΠ(S1(n)) = S2Π(n)para todo n∈N1. Veamos ahora que Πes una función sobreyectiva e inyectiva. Veamos que la función Πes sobreyectiva: Como Π(01)=02entonces 02∈Π[N2]. Si m∈Π[N2]entonces existe n∈N1tal que Π(n) = m, luego S2(Π(n)) = S2(m) = Π(S1(n)), por lo tanto S2(m)∈Π[N1]. Aplicando el principio de inducción obtenemos Π[N1] = N2. Veamos que la función Πes inyectiva: Sea X={(n∈N1)|(∀m)((m∈N1)→((Π(m) = Π(n)) →(m=n)))}. Veamos que 01∈Xysin∈Xentonces S1(n)∈X. Veamos que 01∈X: 76 Sea m6= 01, por el lema 3.4 existe ˆm∈N1tal que S1( ˆm) = m, luego Π(m) = Π(S1( ˆm)) = S2(Π( ˆm)) 6= 02. Por lo tanto si Π(m) = Π(01) = 02 entonces m= 01y01∈X. Veamos que si n∈Xentonces S1(n)∈X: Probaremos que si n∈XyΠ(m) = Π(S1(n)) entonces m=S1(n). Por hipótesis Π(m) = Π(S1(n)) = S2(Π(n)) 6= 02, por lo tanto m6= 01. Por el lema 3.4 sabemos que existe ˆm∈N1tal que S1( ˆm) = m. Como Π(m) = Π(S1( ˆm)) = S2(Π( ˆm)) yΠ(m) = Π(S1(n)) = S2(Π(n)) por hipótesis entonces S2(Π( ˆm)) = S2(Π(n)), luego Π( ˆm) = Π(n), por lo tanto ˆm=n ya que n∈Xy finalmente vemos que m=S1( ˆm) = S1(n). Por el principio de inducción concluimos que X=N1. 3.3. Suma y producto de los números naturales. Definición 3.9. Definimos la suma en Ncomo la función + : N×N−→ N tal que +(n, 0) = 0 para todo n∈Ny+(n, S(m)) = S(+(n, m)) para todo (n, m)∈N×N. Veamos que existe la función suma. Sea g1:N−→ Nla función identidad yh1:N×N−→ Nla función que a cada par (z, n)le corresponde S(z), es decir h1={((z, n), w)∈(N×N)×N|w=S(z)}. El corolario 3.1 nos garantiza que existe una única función f1:N×N−→ N tal que f1(0, n) = g1(n)yf1(S(m), n) = h1(f1(m, n), n). Finalmente definimos la función suma de la siguiente manera: + = {((n, m), w)|((m, n), w)∈f1}. Definición 3.10. Definimos la función producto en Ncomo la función ∗:N×N−→ Ntal que ∗(n, 0) = 0 para todo n∈Ny ∗(n, S(m)) = +(∗(n, m), n). Veamos que la función producto está bien definida. Sean g2:N× {0} −→ Nuna función tal que g2(n) = 0 para todo n∈Nyh2 la función suma. El corolario 3.1 nos garantiza que existe una única función f2:N×N−→ N tal que f2(0, n) = g2(n)yf2(S(m), n) = h2(f2(m, n), n). 77 Finalmente definimos la función multiplicación de la siguiente manera: ∗={((n, m), w)|((m, n), w)∈f2}. Escribiremos n+myn∗men lugar de +(n, m)y∗(n, m). De la definicion de suma obtenemos las dos siguientes propiedades (S1) y (S2): 1. (S1) n+ 0 = n. 2. (S2) n+S(m) = S(n+m). De la definicion de producto obtenemos las dos siguientes propiedades (P1) y(P2): 1. (P1) n∗0=0. 2. (P2) n∗S(m)=(n∗m) + n. Teorema 3.3. (Asociatividad) La función suma es asociativa, es decir, para todo m, n, k ∈Nse cumple (n+m) + k=n+ (m+k). Demostración. Lo demostraremos utilizando el principio de inducción. Fijados m y n en Ndefinimos el conjunto X={k∈N|(m+n) + k=n+ (m+k)}. Para k= 0 tenemos (n+m) + 0 = n+m=n+ (m+ 0), luego 0∈X. Veamos que (n+m) + S(k) = n+ (m+S(k)) asumiendo que para un k se cumple (n+m) + k=n+ (m+k). Por la propiedad (S2) de la suma tenemos (n+m) + S(k) = S((n+m) + k), como (n+m) + k=n+ (m+k)entonces S((n+m) + k) = S(n+ (m+k)) y otra vez por la propiedad (S2) de la suma tenemos S(n+ (m+k)) = n+S(m+k) = n+ (n+S(k)). Por el principio de inducción X=N. Lema 3.6. Para todo natural n se cumple 0 + n=n. Demostración. Lo demostraremos utilizando el principio de inducción, para ello definimos el conjunto X={n∈N|0 + n= 0}. El elemento 0pertenece a X por la propiedad (S1) de la suma, es decir se cumple 0 + 0 = 0. 78 Veamos que si 0 + n=nentonces 0 + S(n) = S(n). Por la propiedad (S2) de la suma vemos que 0 + S(n) = S(0 + n), como 0 + n=nentonces S(0 + n) = S(n), luego 0 + S(n) = S(n)yS(n)∈X. Por el principio de inducción X=N. Lema 3.7. Para todo m, n ∈Nse cumple n+S(m) = S(n) + m. Demostración. Demostraremos el lema utilizando el principio de inducción. Fijando n en Ndefinimos el conjunto X={m∈N|n+S(m) = S(n) + m}. El elemento 0pertenece al conjunto X ya que por la propiedad (S2) de la suma se cumple n+S(0) = S(n+ 0) y por la propiedad (S1) de la suma S(n+ 0) = S(n) = S(n)+0. Veamos que si existe m∈Ntal que n+S(m) = S(n) + mentonces n+S(S(m)) = S(n) + S(m). Por la propiedad (S2) de la suma n+S(S(m)) = S(n+S(m)), como n+S(m) = S(n)+mentonces S(n+S(m)) = S(S(m)+n)y por la propiedad (S2) de la suma S(S(m) + n) = S(m) + S(n), luego n+S(S(m)) = S(n) + S(m), por consiguiente S(m)∈N. Utilizando el principio de inducción se concluye X=N. Teorema 3.4. La función suma es conmutativa, es decir n+m=m+n. Demostración. Demostraremos el teorema utilizando el principio de inducción. Fijado un n en Ny definimos el conjunto X={m∈N|n+m=m+n}. Por el lema 3.6 el elemento 0pertenece a X. Veamos que si n+m=m+nentonces n+S(m) = S(m) + n. Por la propiedad (S2) de la suma n+S(m) = S(n+m), como n+m=m+nentonces S(n+m) = S(m+n)y por la propiedad (S2) de la suma S(m+n) = m+S(n). Aplicando el lema 3.7 vemos que m+S(n) = S(m) + n, concluyendo n+S(m) = S(m) + nyS(m)∈X. Por el principio de inducción X=N. Denotaremos por 1al elemento S(0) y observemos que S(n) = n+ 1, ya que por la propiedad (P2) obtenemos n+S(0) = S(n+ 0) y por la propiedad (P1) n+ 0 = n, luego n+ 1 = S(n). Lema 3.8. Para todo n∈Nse tiene 0∗n= 0. Demostración. Probaremos el lema utilizando el principio de inducción. Definimos el conjunto X={n∈N|n∗0=0}. Para n= 0 basta aplicar la 79 propiedad (P1) del producto y ver que 0∗0=0. Veamos que si 0∗n= 0 entonces 0∗S(n)=0. Por la propiedad (P2) del producto 0∗S(n) = (0 ∗n)+0, como 0∗n= 0 entonces (0∗n)+0 = 0+0 y por el lema 3.6 0+0 = 0, luego 0∗S(n)=0yS(n)∈X. Por el principio de inducción X=N. Teorema 3.5. La función producto es distributiva por la derecha, es decir, para todo n, m, k ∈Nse cumple (n+m)∗k= (n∗k)+(m∗k). Demostración. Demostraremos el teorema usando el principio de inducción. Fijados dos elementos de Nn y m definimos el conjunto X={k∈N|(n+m)∗k= (n∗k)+(m∗k)}. Para k= 0 vemos que (n+m)∗k= 0 por la propiedad (P2), por otra parte, por la propiedad (P1) del producto n∗0=0ym∗0 = 0 y por (S1) 0+0 = 0, luego (n+m)∗k= 0 = (n∗k)+(m∗k),es decir 0∈X. Veamos que si (n+m)∗k= (n∗k)+(m∗k)entonces (n+m)∗S(k) = (n∗S(k)) + (m∗S(k)). Por (P2) vemos que (n+m)∗S(k)=(n+m)∗k+ (n+m). Como (n+m)∗k= (n∗k)+(m∗k)entonces (n+m)∗k+ (n+m) = ((n∗k)+(m∗k)) + (n+m). Por las propiedades asociativa y conmutativa de la suma ((n∗k)+(m∗k)) + (n+m) = ((n∗k) + n) + ((m∗k) + m). Usando la propiedad (P2) del producto obtenemos ((n∗k) + n) + ((m∗k) + m)=(n∗S(k)) + (m∗S(k)) concluyendo (n+m)∗S(k) = (n∗S(k)) + (m∗S(k)) yS(k)∈X. Por el principio de inducción X=N. Teorema 3.6. La función multiplicación es distributiva respecto de la suma, es decir, para todo n, m, k ∈Nse cumple n∗(m+k)=(n∗m)+(n∗k). Demostración. Probaremos el teorema usando el principio de inducción. Fijados dos elementos de Nn y m definimos el conjunto X={k∈N|n∗(m+k)=(n∗m)+(n∗k)}. El elemento 0pertenece al conjunto X ya que por la propiedad (S1) de la suma n∗(m+ 0) = n∗my n∗m= (n∗m) + 0 = (n∗m)+(n∗0), luego n∗(m+ 0) = (n∗m)+(n∗0). Veamos que si n∗(m+k) = (n∗m)+(n∗k)entonces n∗(m+S(k)) = (n∗m)+(n∗S(k)). 80 Por la propiedad (S2) de la suma n∗(m+S(k)) = n∗S(m+k) = (n∗(m+k)) + n. Como n∗(m+k)=(n∗m)+(n∗k)entonces (n∗(m+k))+n= ((n∗m)+(n∗k))+n, por el teorema de la asociatividad de la suma ((n∗m)+(n∗k)) + n= (n∗m) + ((n∗k) + n)y por la propiedad (P2) del producto concluimos (n∗m)+((n∗k)+n)=(n∗m)+(n∗S(k)) yS(k)∈X. Por el principio de inducción X=N. Teorema 3.7. El producto tiene elemento unidad, siendo este el elemento 1, es decir, para todo n∈Nse cumple n∗1 = n= 1 ∗n. Demostración. Por la propiedad (P2) del producto vemos que n∗1 = (n∗0) + ny por la propiedad (P1) del producto (n∗0) + n= 0 + n. Por el lema 3.6 0 + n=n, luego n∗1 = n. Utilizaremos el principio de inducción para probar 1∗n=npara todo n∈N. Definimos el conjunto X={n∈N|1∗n=n}. El elemento 0pertenece al conjunto X por la propiedad (P1) del producto. Veamos que si 1∗n=nentonces 1∗S(n) = S(n). Recordando que S(n) = n+ 1 vemos que 1∗S(n) = 1 ∗(n+ 1). Por la propiedad distributiva del producto respecto de la suma tenemos 1∗(n+ 1) = (1 ∗n) + (1 ∗1). Por otra parte hemos probado que (n∗1) = 1 para todo n∈N, luego 1∗1 = y por consiguiente (1∗n)+(1∗1) = (1∗n)+1. Como 1∗n=nentonces (1 ∗n) + 1 = n+ 1 = S(n)y1∗S(n) = S(n), luego S(n)∈N. Por el principio de inducción X=N. Lema 3.9. La función multiplicación es asociativa, es decir, para todo m, n, k ∈Nse cumple n∗(m∗k)=(n∗m)∗k. Demostración. Probaremos el lema utilizando el principio de inducción. Fijados n y m en Ndefinimos el conjunto X={k∈N|n∗(m∗k)=(n∗m)∗k}. El elemento 0pertenece al conjunto X ya que por la propiedad (P1) del producto obtenemos n∗(m∗0) = n∗0=0=(n∗m)∗0. Veamos que si n∗(m∗k) = (n∗m)∗kentonces n∗(m∗S(k)) = (n∗m)∗S(k). Por la propiedad (P2) del producto n∗(m∗S(k)) = n∗((m∗k) + m)y por la propiedad distributiva del producto respecto de la suma obtenemos n∗((m∗k) + m)=(n∗(m∗k)) + (n∗m). Como n∗(m∗k) = (n∗m)∗k entonces (n∗(m∗k))+(n∗m) = ((n∗m)∗k)+(n∗m)y por la propiedad (P2) del producto ((n∗m)∗k)+(n∗m) = (n∗m)∗S(k). Finalmente concluimos 81 que n∗(m∗S(k)) = (n∗m)∗S(k)yS(k)∈X. Por el principio de inducción X=N. Lema 3.10. La función multiplicación es conmutativa, es decir para todo n, m ∈Nse cumple n∗m=m∗m. Demostración. Demostraremos el teorema utlizando el principio de inducción. Fijamos n∈Ny definimos el conjunto X={m∈N|n∗m=m∗n}. El elemento 0pertenece al conjunto X ya que por la propiedad (P1) del producto y por el lema 3.8 se cumple n∗0=0=0∗n. Veamos que si n∗m=m∗nentonces n∗S(m) = S(m)∗ny por consiguiente S(m)∈X. Usando la propiedad del producto (P2) vemos que n∗S(m) = (n∗m)+n. Como n∗m=m∗nentonces (n∗m)+n= (m∗n)+n. En el teorema 3.7 hemos probado 1∗n=n, luego (m∗n)+n= (m∗n)+(1 ∗n)y usando la propiedad distributiva por la derecha concluimos (m∗n)+(1∗n)=(m+1)∗n=S(m)∗n yS(m)∈N. Por el principio de inducción X=N. El par (N,+) es un semigrupo conmutativo con elemento neutro 0debido a las propiedades asociativa y conmutativa de la suma junto con la propiedad (S1) de la suma. La terna (N,+,∗)es un semianillo conmutativo con elemento unidad por las propiedades distributivas, asociativa y conmutativa del producto y la existencia de elemento unidad. 3.4. Ordenación de los números naturales. Definición 3.11. Definimos la relación menor que <como el conjunto {(n, m)∈N×N|(∃p)(((p∈N)∧(n+p=m)) ∧(p6= 0))}. y la relación menor o igual que ≤como el conjunto {(n, m)∈N×N|(∃p)((p∈N)∧(n+p=m))}. Lema 3.11. (Propiedad cancelativa de la suma.) Para todo m, n, p ∈Nsi m+n=m+pentonces n=p. Si m6= 0 entonces m+n6= 0. 82 Demostración. Para probar que m+n=m+pimplica n=pprobaremos que n6=pimplica m+n6=m+p. Para ello fijamos n, p ∈Ntales que n6=p y definimos el conjunto Sn,p ={k∈N|k+n6=k+p}. El elemento 0∈Sn,p ya que 0 + n=n6=p= 0 + p, luego 0 + n6= 0 + p. Veamos que si k∈Sn,p entonces S(k)∈Sn,p. Por la propiead conmutativa de la suma S(k)+n=n+S(k)y por la propiedad (S2) de la suma n+S(k) = S(n+k). Por hipótesis de inducción y por ser S una función inyectiva S(n+k)6=S(p+k)y otra vez por la propiedad (S2) de la suma y por conmutatividad S(p+k) = p+S(k), luego S(k) + n6=S(k) + p, por lo tanto S(k)∈Sn,p. Aplicando el axioma de inducción de Peano concluimos que Sn,p =N. Probamos ahora que si m6= 0 entonces m+n6= 0. Como m6= 0 sabemos por el lema 3.4 que existe m0tal que S(m0) = m. Por la propiedad conmutativa de la suma tenemos m+n=n+m, como m=S(m0)entonces n+m=n+S(m0). Por la propiedad (S2) de la suma n+S(m0) = S(n+m0). El axioma 4 de Peano nos garantiza que el elemento 0no es ningún sucesor, luego 06=S(n+m0)concluyendo así que si m6= 0 entonces m+n6= 0. La propiedad cancelativa de la suma es fundamental en la demostración del siguiente lema. Lema 3.12. El orden en Nes total, es decir, para todo m, n ∈Nsolamente una de las siguientes afirmaciones es válida: 1. m<n. 2. m=n. 3. n<m. Demostración. Veamos que si m < n on < m entonces no se puede dar el caso m=n. Si m < n entonces existe un p6= 0 en Ntal que m+p=n. Por otra parte n=n+ 0, luego m+p=n+ 0. Si m=npor la propiedad cancelativa de la suma obtendríamos p= 0, lo cual es absurdo. Razonando de forma similar vemos que si n<mentonces no se puede dar el caso m=n. Si n < m entonces existe un p6= 0 en Ntal que n+p=m. Por otra parte m=m+ 0, luego n+p=m+ 0. Si m=npor la propiedad cancelativa de 83 la suma obtendríamos p= 0, lo cual es absurdo. Veamos que si m < n entonces no se puede dar el caso n < m. Si m < n yn < m entonces existen p6= 0 yp06= 0 en Ntales que m+p=n yn+p0=m. Por lo tanto (m+p) + p0=m. Por la propiedad asociativa de la suma m+ (p+p0) = m. Como m=m+ 0 entonces m+ (p+p0) = m+ 0 y por la propiedad cancelativa de la suma vemos que p+p0= 0. En el lema 3.11 hemos probado que si p6= 0 entonces p+p06= 0, luego p= 0, lo cual es absurdo. Para demostrar que necesariamente se cumple una de las tres condiciones fijamos un m∈Ny definimos el conjunto Xm={n∈N|n<m,m<nom=n}. Probaremos que 0∈Xm. Para m= 0 tomamos la igualdad 0=0para probar que 0∈Xmy si m6= 0 entonces 0 + m=m, por lo tanto 0< m. Veamos que si n∈Xmentonces S(n)∈Xm. Como n∈Xmentonces, o bien n < m, o bien m < n, o bien n=m. Si m=nentonces S(m) = S(n), luego S(n) = m+ 1, por lo tanto existe p6= 0 en Ntal que m+p=S(n), es decir m < S(n)yS(n)∈Xm. Si m < n entonces existe p6= 0 en Ntal que m+p=n, luego S(n) = S(m+p) y por la propiedad (S2) de la suma S(m+p) = m+S(p), por lo tanto m+S(p) = S(n). Como S(p)6= 0 entonces m<S(n). Si n < m entonces existe p6= 0 en Ntal que n+p=m, como p6= 0 entonces existe p0tal que S(p0) = p. Por lo tanto n+S(p0) = my por la propiedad (S2) de la suma n+S(p0) = S(n+p0). Por conmutatividad S(n+p0) = S(p0+n) = p0+S(n) = m. Si p0= 0 entonces S(n) = my si p06= 0 entonces S(n)< m, en ambos casos S(n)∈Xm. Finalmente concluimos por el principio de inducción que Xm=N. Lema 3.13. (Propiedad transitividad.) Dados m, n, p ∈Ntales que m<nyn < p entonces m < p. Demostración. Si m<nyn<pentonces existen p16= 0 yp26= 0 en N tales que m+p1=nyn+p2=p, luego (m+p1) + p2=py por la propiedad asociativa de la suma m+ (p1+p2) = p. Si p1+p2= 0 entonces p1= 0, por lo tanto p1+p26= 0, concluyendo así que m<p. Lema 3.14. Dados m, n, p ∈Nentonces m<nsi y solo si m+p<n+p. Demostración. Veamos que si m < n entonces m+p<n+p. Como m < n entonces existe p16= 0 en Ntal que m+p1=n, por lo tanto 84 n+p= (m+p1) + p. Por asociatividad y conmutatividad (m+p1) + p= (m+p) + p1, luego n+p= (m+p) + p1, es decir m+p<n+p. Veamos que si m+p<n+pentonces m < n. Como m+p<n+pentonces existe p16= 0 en Ntal que (m+p)+p1=n+p. Por asociatividad y conmutatividad (m+p) + p1= (m+p1) + p, luego (m+p1) + p=n+p. Por la propiedad cancelativa de la suma concluimos que m+p1=n, es decir m<n. Lema 3.15. Sean m, n, p ∈Ncon p6= 0 entonces m<nsi y solo si m∗p<n∗p. Demostración. Para probar que si m<nentonces m∗p<n∗pfijamos m, n ∈Ntales que m < n y definimos el conjunto Z={p∈N|m∗p<n∗p}∪{0}. El elemento 0pertenece a Z. Recordando que S(0) = 1,m∗1 = myn∗1 = n obtenemos que m∗1 = m < n =n∗1. Veamos que si p∈Zentonces S(p)∈Z. Por la propiedad (P2) del producto obtenemos m∗S(p) = (m∗p) + m. Por el lema anterior y por hipótesis (m∗p) + m < (n∗p) + m. Por la propiedad conmutativa de la suma (n∗p) + m=m+ (n∗p), por el lema anterior como m < n entonces m+ (n∗p)< n + (n∗p)=(n∗p) + n. Finalmente por transitividad probamos m∗S(p)<(n∗p) + n=n∗S(p). Por el axioma de inducción se concluye que Z=N. Para demostrar que si m∗p < n ∗pentonces m < n probaremos que si no se cumple que m < n entonces no se cumplirá m∗p<n∗p. Si no se cumple m < n entonces, bien m=n, bien n<m. Si m=nentonces m∗p=n∗p, luego no se cumple m∗p<n∗p. Si n < m entonces hemos demostrado que n∗p<m∗p, luego no se cumple m∗p<n∗p. Teorema 3.8. (Teorema del buen orden). Sea S un subconjunto no vacío de Nentonces existe m∈Stal que m≤npara todo n∈S. Demostración. Sea A={n∈m|si m < n entonces m /∈S}. Veamos que A6=N. Si A=Nentonces S⊂A, es decir si u∈Sentonces u∈A. Por otra parte u<S(u)yu∈Sy por definición del conjunto A 85