L´ogica Simb´olica y Demostraciones Introducci´on al C´alculo Diego Alejandro Mej´ıa Guzm´an

El estudio de las formas de pensamiento y los m´etodos de razonamiento se remonta desde el siglo V a.C. en las civilizaciones de China, India y Grecia. Fue en tiempo de Arist´oteles donde esta ciencia del lenguaje y la argumentaci´on tom´o el nombre de L´ogica1 , la cual se estudi´o desde la filosof´ıa. No fue sino hasta el siglo XIX que la l´ogica comenz´o a formar parte de las matem´aticas: bajo el nombre de l´ogica s´ımb´olica o matem´atica, se lograron modelar los m´etodos argumentativos a partir de un lenguaje b´asico y un (peque˜no) conjunto de principios que, mediante c´alculos “matem´aticos” sencillos, permiten generar las leyes universales del razonamiento. Si bien es cierto que la l´ogica tiene distintos enfoques, las matem´aticas est´an fundamentadas sobre la L´ogica Cl´asica y es donde centraremos el estudio de este cap´ıtulo. Otro tipo de l´ogicas, como la modal, difusa y probabil´ıstica, entre otras, aunque presentan formas alternativas e interesantes de estudiar los m´etodos de razonamiento, no har´an partes de este curso, puesto que sobre e´ stos no se fundamenta la matem´atica formal. La l´ogica simb´olica, en principio, se caracteriza por estructurar el razonamiento desde la sintaxis, es decir, desde el lenguaje y los principios l´ogicos, de forma independiente al significado de las afirmaciones involucradas. Dar a entender lo anterior ser´a el prop´osito de este cap´ıtulo, el cual no desarrollaremos con la rigurosidad total con que se estudia, pero s´ı con la suficiente para dar al razonamiento un esquema matem´atico claro y para dar un primer indicio de la estructuraci´on formal de las matem´aticas. Dividimos este cap´ıtulo en cinco secciones: en la primera secci´on estudiamos el C´alculo Proposicional, donde introducimos la notaci´on b´asica de la l´ogica simb´ologica, para luego materializar la forma de efectuar deducciones en la segunda secci´on. En la tercera secci´on extendemos el lenguaje de la l´ogica y proponemos, de forma intuitiva, el C´alculo de Predicados. Las tres secciones anteriores permiten introducir los m´etodos de demostraci´on en matem´aticas, los cuales estudiamos en la cuarta secci´on. Por u´ ltimo, introducimos la notaci´on de la Teor´ıa de Conjuntos.

1. El C´alculo Proposicional El C´alculo Proposicional es la primera forma en la l´ogica cl´asica sobre la cual se analizan el argumento l´ogico mediante m´etodos matem´aticos sencillos. Lo primero que hay que entender para su estudio es el lenguaje sobre el que se presenta, el cual consta de pocos, pero poderosos ingredientes. A continuaci´on introducimos paso a paso cada s´ımbolo de este lenguaje, junto con su respectiva interpretaci´on. 1. Letras (Predicativas). Usamos las letras del alfabeto para respresentar afirmaciones a las cuales se les 1

Proviene del griego logos, que significa “palabra, pensamiento, argumento”.

1

puede dar un valor de verdad. Por ejemplo, P : 1 + 1 = 2. Q : Est´a lloviendo. R : Las vacas vuelan. En este caso, P es una afirmaci´on verdadera, Q es verdadera o falsa seg´un el contexto y R es falsa (al menos en este planeta). Es importante que una afirmaci´on representada por una letra predicativa pueda tomar un valor de verdad, por lo cual denotamos por V el valor verdad, y por F el valor falso. Por ejemplo, frases como “π” “tres relojes” “du´ermete” o “hazme un favor” no se pueden representar por una letra predicativa, puesto que no toman valores de verdad o falso. Por lo tanto, no se consideran como afirmaciones del c´alculo proposicional. Los siguientes signos los llamaremos s´ımbolos l´ogicos, los cuales son operadores que se aplican a afirmaciones para modificar su valor de verdad. Cada s´ımbolo l´ogico tiene su propio significado y su tabla de verdad, la cual se define en relaci´on a su significado. 2. Negaci´on ¬. Si P es una letra predicativa, ¬P denota la negaci´on de P y se lee como “no P ” o “negaci´on de P ”. Retomando los ejemplos en 1., ¬P representa “1 + 1 6= 2”, ¬Q es “No est´a lloviendo” y ¬R significa “las vacas no vuelan”. Intuitivamente, ¬P toma el valor de verdad contrario al que toma P , es decir, ¬P toma el valor F si P es V, y ¬P toma el valor V si P es F. Por lo tanto, dada una letra P arbitraria, la tabla de verdad de la negaci´on est´a dada por P V F

¬P F V

Cuadro 1: Tabla de verdad de la negaci´on.

3. Disyunci´on ∨ . Dadas dos letras P y Q, denotamos por P ∨ Q la disyunci´on entre P y Q, la cual se lee ´ P o´ Q. Esta representa que se cumple al menos una de las opciones entre P y Q. Por ejemplo, si P : Q: R: S:

1+1 =2 Est´a lloviendo. 1 ∈ ∅ (∅ representa el conjunto vac´ıo) El ser humano es un mam´ıfero.

entonces P ∨ R significa “1 + 1 = 2 o 1 ∈ ∅”, la cual es una afirmaci´on verdadera, pues al menos 1 + 1 = 2 es verdad; Q ∨ S significa “est´a lloviendo o el ser humano es un mam´ıfero”, lo cual es verdad, ya que “el ser humano es un mam´ıfero” es verdad, sin importar qu´e valor de verdad tome Q. En caso en que no estuviese lloviendo en este momento, Q ∨ R es una afirmaci´on falsa, pues ninguna de las dos opciones Q ni R son verdaderas. De una forma m´as esquem´atica, para dos afirmaciones arbitrarias P y Q, presentamos la tabla de verdad de la disyunci´on como2 2

En la l´ogica cl´asica la disyunci´on se toma inclusiva, es decir, que es verdadera incluso cuando P y Q son verdaderas. Una disyunci´on exclusiva es verdad cuando s´olo una de las dos opciones es verdadera. No hay necesidad de introducir un s´ımbolo para este tipo de disyunci´on, pues m´as adelante se puede ver que est´a representada por ¬(P ⇔ Q).

2

P V V F F

Q V F V F

P

∨

Q

V V V F

Cuadro 2: Tabla de verdad de la disyunci´on.

4. Conjunci´on ∧ . Dadas dos letras P y Q, denotamos por P ∧ Q la conjunci´on entre P y Q, la cual se lee P ´ representa que se cumplen ambas afirmaciones P y Q. Si consideramos el ejemplo de 3., P ∧ R y Q. Esta significa “1 + 1 = 2 y 1 ∈ ∅”, lo cual es falso ya que 1 ∈ ∅ es falso y, por lo tanto, ambas afirmaciones no son ciertas a la vez. P ∧ Q representa “1 + 1 = 2 y est´a lloviendo”, lo cual ser´a verdadero s´olo en caso de que Q sea verdadera, y P ∧ S representa “1 + 1 = 2 y el ser humano es un mam´ıfero”, lo cual es verdadero. Lo anterior se expresa de una forma m´as sencilla con la tabla de verdad correspondiente a la conjunci´on, para P y Q letras arbitrarias. P V V F F

Q V F V F

P

∧

Q

V F F F

Cuadro 3: Tabla de verdad de la conjunci´on.

5. Implicaci´on ⇒ . Este es el s´ımbolo m´as importante del C´alculo Proposicional, pues expresa la relaci´on de causa y efecto entre dos afirmaciones. P ⇒ Q se lee de varias formas, como “P implica Q”, “P es causa de Q”, “de P se sigue Q”, “si P entonces Q”, “P es condici´on suficiente para Q”, “P solo si Q”, “Q es efecto de P ”, “Q es condici´on necesaria para P ”, entre otras. Dada una implicaci´on P ⇒ Q, llamamos P el antecedente de la implicaci´on, y a Q el consecuente de la implicaci´on. El valor de verdad de P ⇒ Q se define bajo la cl´ausula “causas verdaderas conyevan consecuencias verdaderas”, por lo cual su tabla de verdad se define como P V V F F

Q V F V F

P ⇒Q V F V V

Cuadro 4: Tabla de verdad de la implicaci´on.

Bajo la cl´ausula es evidente el valor en la primera y segunda fila, pues la consecuencia de una afirmaci´on verdadera no puede ser falsa, sino verdadera. El valor de P ⇒ Q en la u´ ltima fila es V debido a la ley del contrarrec´ıproco: “nunca se pueden cumplir las causas de una afirmaci´on falsa”; en la tercera fila el valor se presenta m´as como una convenci´on respecto a que “causas falsas pueden tener consecuencias 3

verdaderas”. Por ejemplo, P : Q: R: S:

4 divide a 3 3 es par S´ocrates es hombre S´ocrates es mortal

La afirmaci´on R ⇒ S dice que “si S´ocrates es hombre, entonces es mortal”, lo cual es verdadero ya que todos los hombres son mortales. Sin embargo, R ⇒ Q es falsa, pues significa “si S´ocrates es hombre, entonces 3 es par” indicando que una afirmaci´on verdadera (S´ocrates es hombre) tiene una consecuencia falsa (3 es par). Por otra parte, Q ⇒ S es verdadera ya que, aunque tiene una causa falsa, la consecuencia es verdadera. Por u´ ltimo, P ⇒ Q es verdad, aunque ambas afirmaciones P y Q sean falsas. Esto se debe a que “todo n´umero divisible por cuatro es par”y si se supone que 3 es divisible por cuatro (sin importar que sea falso) su consecuencia ser´a, ineludiblemente, que 3 es par. 6. Equivalencia ⇔ . Dadas dos afirmaciones P y Q, P ⇔ Q se lee P equivale a Q. Intuitivamente, P ⇔ Q denota que las afirmaciones P y Q tienen el mismo significado o, en t´erminos de tablas de verdad, que tienen el mismo valor de verdad. Bajo esta cl´ausula, la tabla de verdad de la equivalencia se presenta como sigue P V V F F

Q V F V F

P ⇔Q V F F V

Cuadro 5: Tabla de verdad de la equivalencia.

es decir, P ⇔ Q es verdad s´olo cuando P y Q tienen el mismo valor de verdad (es decir, el mismo significado). P ⇔ Q tambi´en se lee “P si y solo si Q”, “P es condici´on necesaria y suficiente para Q”, entre otras formas. Por ejemplo, P : Q: R: S:

6 es par 6 es divisible por 4 n es impar n deja residuo 1 al dividirse por 2

de donde P ⇔ Q es falsa, pues P es cierta y Q es falsa, dando lugar a que ambas no tienen el mismo significado. Por otra parte, R ⇔ S es verdadera, pues para los n´umeros enteros significa lo mismo ser impar a dejar residuo 1 al dividirse por 2. Dependiendo del valor de n, ambas afirmaciones R y S tendr´an el mismo valor de verdad V o´ F, lo cual las har´a equivalentes. Observaci´on 1.1. El uso de ⇔ tiene connotaciones muy parecidas al s´ımbolo igual (=), por eso hay que tener precauci´on al usar ambos s´ımbolos. El s´ımbolo = se utiliza para indicar que dos objetos son el mismo, mientras que ⇔ se usa para denotar que dos afirmaciones tienen el mismo significado. Por ejemplo, es correcto escribir x2 − y = 1 en el sentido que la igualdad est´a dada para dos n´umeros (objetos) que son x2 − y y 1, pero no es correcto escribir x2 − y ⇔ 1, dado que no se est´an relacionando afirmaciones a las cuales se les puede dar un valor de verdad. Del mismo modo, si P : τ es un tri´angulo equil´atero (es decir, tiene los tres lados iguales) Q : τ es un tri´angulo cuyos tres a´ ngulos son iguales 4

es l´ıcito afirmar P ⇔ Q, pero no P = Q. Aunque P y Q significan lo mismo y pueden sustituirse en una afirmaci´on m´as extensa, no se puede decir que son iguales ya que no representan cosas. Combinando los elementos del lenguaje del C´alculo Proposicional, podemos construir afirmaciones m´as complejas a las cuales tambi´en se les puede asociar una tabla de verdad. Ejemplo 1.2. Establecer la tabla de verdad de (¬P ∨ Q) ∧ P . El procedimiento para hallar la tabla de verdad de una afirmaci´on con varios conectivos l´ogicos consta de hallar los valores de verdad de las afirmaciones peque˜nas, y utilizar e´ stas para hallar el valor de verdad de las afirmaciones grandes. En este caso, hallamos los valores de verdad de ¬P , luego de ¬P ∨ Q y finalmente de la afirmaci´on completa, en cada paso ayud´andonos de los valores hallados en los pasos anteriores. La siguiente tabla muestra el orden en el cual ejecutamos esta labor. P V V F F

Q V F V F

¬P F F V V

¬P ∨ Q V F V V

(¬P

Q) ∧ P V F F F

∨

Si quitamos los pasos intermedios para hallar los valores de (¬P P V V F F

Q V F V F

(¬P

∨

Q) ∧ P , obtenemos la siguiente tabla:

Q) ∧ P V F F F

∨

Con esta tabla, podemos hallar la tabla de verdad de la afirmaci´on ((¬P P V V F F

Q V F V F

(¬P

Q) ∧ P V F F F

∨

P

∧

Q

V F F F

((¬P

∨

∨

Q) ∧ P ) ⇔ (P

Q) ∧ P ) ⇔ (P V V V V

∧

∧

Q), as´ı

Q)

Notese que los valores de verdad de estas afirmaciones no dependen del significado de P ni de Q, sino de sus valores de verdad, de modo que podemos conocer si la afirmaci´on es cierta o falsa respecto a cada “interpretaci´on” que se tome para P y Q. Por ejemplo, si P es “S´ocrates es hombre” y Q es “S´ocrates es mortal”, entonces (¬P ∨ Q) ∧ P ) representa “o S´ocrates no es hombre o es mortal, y S´ocrates es hombre”. Analizar el significado de esta afirmaci´on nos permite concluir que es verdadera, sin embargo, matem´aticamente solo necesitamos verificar que P y Q son ciertas para concluir que la afirmaci´on compuesta es verdadera. Al analizar ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q) nos damos cuenta que es verdadera independientemente de los valores de verdad que tomen P y Q, por lo cual se puede deducir que (¬P ∨ Q) ∧ P ) significa lo mismo que P ∧ Q. Por lo tanto, es lo mismo decir “o S´ocrates no es hombre o es mortal, y S´ocrates es hombre” a decir “S´ocrates 5

es hombre y es mortal”. Por otra parte, si P es “n es par” y Q es “n es impar”, entonces (¬P ∨ Q) ∧ P ) denota “o n es impar o es impar, y n es par” pero, como esto significa lo mismo que P ∧ Q, es decir, “n es par e impar”, directamente se infiere que es falsa, sin necesidad de analizar la afirmaci´on larga. Definici´on 1.3 (Tautolog´ıa, Contradicci´on). Una tautolog´ıa es una afirmaci´on cuya tabla de verdad siempre toma el valor V. Una contradicci´on es una afirmaci´on cuya tabla de verdad siempre toma el valor F. Ejemplo 1.4. ((¬P ∨ Q) ∧ P ) ⇔ (P ∧ Q) es una tautolog´ıa (ver ejemplo anterior), P ∨ ¬P , P ⇒ P y P ⇔ P tambi´en son tautolog´ıas. P ∧ ¬P , P ⇔ ¬P y (P ⇒ Q) ∧ (P ∧ ¬Q) son contradicciones. Pero (¬P ∨ Q) ∧ P ) no es tautolog´ıa ni contradicci´on (ver ejemplo anterior). Ver las tablas de verdad a continuaci´on. P V F

P V V F F

¬P F V

P

Q V F V F

¬Q F V F V

¬P V V

∨

P ⇒P V V

P ⇒Q V F V V

P

P ⇔P V V

¬Q F V F F

∧

P

¬P F F

∧

P ⇔ ¬P F F

(P ⇒ Q) ∧ (P F F F F

∧

¬Q)

Las tautolog´ıas son las afirmaciones m´as importantes en la l´ogica simb´olica ya que, como son verdaderas independientemente del valor de verdad de sus letras, se consideran como leyes del razonamiento y, por lo tanto, son afirmaciones que describen la naturaleza de los s´ımbolos l´ogicos y sus propiedades. Las contradicciones tienen una importancia equivalente porque toda contradicci´on equivale a la negaci´on de una tautolog´ıa. A continuaci´on enunciamos las tautolog´ıas m´as importantes de la l´ogica cl´asica. La palabra Proposici´on la usaremos, durante esta secci´on y la secci´on 2, para enunciar tautolog´ıas y propiedades generales del c´alculo proposicional. A cada proposici´on le corresponde una justificaci´on que verifica su validez. Proposici´on 1.5. Las siguientes afirmaciones son tautolog´ıas. (a) P ⇒ P .

(b) P ⇔ P .

(c) P

∨

¬P (Tercer exclu´ıdo).

Justificaci´on. Se verifica con las tablas de verdad del ejemplo anterior. Proposici´on 1.6 (Principales Equivalencias L´ogicas). Las siguientes afirmaciones son tautolog´ıas. (a) ¬¬P ⇔ P (Doble negaci´on). (b) (P

∨

Q) ⇔ (Q ∨ P ) (Conmutatividad de la disyunci´on).

(c) (P

∧

Q) ⇔ (Q ∧ P ) (Conmutatividad de la conjunci´on). 6

(d) ((P

∨

Q) ∨ R) ⇔ (P

∨

(Q ∨ R)) (Asociatividad de la disyunci´on).

(e) ((P

∧

Q) ∧ R) ⇔ (P

∧

(Q ∧ R)) (Asociatividad de la conjunci´on).

(f) (P

∨

(Q ∧ R)) ⇔ ((P

∨

Q) ∧ (P

∨

R)) (Ley distributiva).

(g) (P

∧

(Q ∨ R)) ⇔ ((P

∧

Q) ∨ (P

∧

R)) (Ley distributiva).

(h) ¬(P

∨

Q) ⇔ (¬P

∧

¬Q) (ley D’Morgan).

(i) ¬(P

∧

Q) ⇔ (¬P

∨

¬Q) (ley D’Morgan).

(j) ¬(P ⇒ Q) ⇔ (P

∧

¬Q) (Negaci´on de la implicaci´on)

(k) (P ⇒ Q) ⇔ (¬Q ⇒ ¬P ) (Contrarrec´ıproco). (l) (P ⇔ Q) ⇔ ((P ⇒ Q) ∧ (Q ⇒ P )) (Principio de doble implicaci´on). (m) (P ⇔ Q) ⇔ (Q ⇔ P ) (Conmutatividad de la equivalencia). (n) (P ⇒ Q) ⇔ (¬P

∨

Q).

(˜n) (P

∧

Q) ⇔ ¬(¬P

∨

¬Q).

(o) (P

∨

P) ⇔ P.

(p) (P

∧

P) ⇔ P.

Justificaci´on. Es f´acil comprobar que todas estas afirmaciones son tautolog´ıas observando que la tabla de verdad de cada una toma siempre el valor V. Observaci´on 1.7. En adelante, decimos que dos afirmaciones son equivalentes cuando la equivalencia entre ambas sea una tautolog´ıa. Seg´un el resultado anterior, P ∧ Q equivale a Q ∧ P , y ¬¬P equivale a P . Por otra parte, como ∨ y ∧ son opedores asociativos, no habr´a confusi´on al escribir (P ∨ Q ∨ R) ni (P ∧ Q ∧ R) sin indicar cu´al s´ımbolo l´ogico aplica primero. Observaci´on 1.8. De (n) y (˜n) se tiene que ⇒ y ∧ se pueden escribir en t´erminos de ¬ y ∨ . Tambi´en, de (l), ⇔ se puede escribir en t´erminos de ⇒ y ∧ y, por lo tanto, en t´erminos de ¬ y ∨ . Esto indica que los s´ımbolos ¬ y ∨ bastan para construir el c´alculo proposicional. Las tautolog´ıas citadas en la Proposici´on anterior son leyes importantes que permiten comprobar que ciertas afirmaciones son tautolog´ıas sin necesidad de construir su tabla de verdad, sino mediante un razonamiento paso-a-paso, el cual se fundamenta en el siguiente principio. Proposici´on 1.9 ((Principio de Sustituci´on.). La sustituci´on de una afirmaci´on por otra equivalente dentro de otra afirmaci´on genera f´ormulas equivalentes. Este principio se fundamenta en que dos afirmaciones equivalentes tienen el mismo significado y funciona de forma an´aloga al principio de sustituci´on de la igualdad: si a = b entonces a se puede sustituir por b en una ecuaci´on, generando objetos iguales. Como notaci´on, a 6= b es lo mismo que ¬(a = b).

7

Ejemplo 1.10. Veamos que (P ⇒ Q) ∧ (P ∧ ¬Q) es una contradicci´on, sin necesidad de construir su tabla de verdad. De la Proposici´on 1.6(j) tenemos que ¬(P ⇒ Q) ⇔ (P ∧ ¬Q) es una tautolog´ıa (la negaci´on de la implicaci´on), por lo cual, por el Principio de Sustituci´on, podemos sustituir (P ∧ ¬Q) por ¬(P ⇒ Q) en la primera afirmaci´on, lo cual genera que (P ⇒ Q) ∧ (P

∧

¬Q) ⇔ (P ⇒ Q) ∧ ¬(P ⇒ Q)

es una tautolog´ıa. Es claro que la afirmaci´on de la derecha de ⇔ es una contradicci´on, por lo cual tambi´en lo es su equivalente, la afirmaci´on de la izquierda. Ejemplo 1.11. Veamos (˜n) de la Proposici´on 1.6 sin utilizar tablas de verdad. Por (h) (ley D’Morgan) tenemos que ¬(¬P ∨ ¬Q) equivale a ¬¬P ∧ ¬¬Q y luego, por (a) (doble negaci´on) y el principio de sustituci´on, la u´ ltima f´ormula equivale a P ∧ Q. Por lo tanto, ¬(¬P ∨ ¬Q) equivale a P ∧ Q, es decir, (P ∧ Q) ⇔ ¬(¬P ∨ ¬Q) es una tautolog´ıa. Las siguientes tautolog´ıas se consideran como reglas de inferencia, pues ilustran los pasos b´asicos para seguir un razonamiento l´ogico. Proposici´on 1.12 (Reglas de inferencia.). Las siguientes afirmaciones son tautolog´ıas. (a) ((P ⇒ Q) ∧ P ) ⇒ Q (Modus Ponens). (b) ((P ⇒ Q) ∧ ¬Q) ⇒ ¬P . (c) (P

∧

Q) ⇒ P (Simplificaci´on).

(d) (P

∧

Q) ⇒ Q (Simplificaci´on).

(e) P ⇒ (P

∨

Q) (Adici´on).

(f) Q ⇒ (P

∨

Q) (Adici´on).

(g) ((P

∨

Q) ∧ ¬P ) ⇒ Q (Eliminaci´on de la falsa en una disyunci´on).

(h) ((P

∨

Q) ∧ ¬Q) ⇒ P (Eliminaci´on de la falsa en una disyunci´on).

(i) (P ⇔ Q) ⇒ (P ⇒ Q) (Descomposici´on de la equivalencia). (j) (P ⇔ Q) ⇒ (Q ⇒ P ) (Descomposici´on de la equivalencia). (k) ((P ⇒ Q) ∧ (Q ⇒ P )) ⇒ (P ⇔ Q) (Composici´on de la equivalencia)). (l) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R) (Transitividad de la implicaci´on). (m) ((P

∨

Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)) ⇒ R (Disyunci´on de casos).

Justificaci´on. Cada afirmaci´on se puede comprobar mediante tablas de verdad, aunque no es necesario en todos los casos. Por ejemplo, para verificar (i), por (c) tenemos que (P ⇒ Q) ∧ (Q ⇒ P ) ⇒ (P ⇒ Q) es tautolog´ıa y, como (P ⇒ Q) ∧ (Q ⇒ P ) equivale a P ⇔ Q (1.6(l), principio de doble implicaci´on), entonces, al sustituir, se obtiene que (P ⇔ Q) ⇒ (P ⇒ Q) es una tautolog´ıa. De forma an´aloga se puede verificar (j) usando (d). Observaci´on 1.13. En adelante, decimos que una afirmaci´on P implica otra afirmaci´on Q si al formar P ⇒ Q resulta una tautolog´ıa. Por ejemplo, seg´un el resultado anterior, (P ⇒ Q) ∧ P implica a Q, y P ⇔ Q implica a Q ⇒ P . 8

Conclu´ımos esta secci´on con una discusi´on sobre la implicaci´on. Cuand P ⇒ Q es verdad, podemos decir que P es condici´on suficiente para Q, esto debido a que basta que P sea verdadero para que Q sea verdadero. Por otra parte, tambi´en decimos que Q es condici´on necesaria para P ya que se necesita que Q sea verdadero para que P sea verdadero. Para explicar esto u´ ltimo, sup´ongase que buscamos saber si P es verdadero y para esto observamos a Q. Si Q es falso, como P ⇒ Q es verdad entonces P es falso. Si Q es verdadero, P ⇒ Q no permite afirmar nada sobre P pero al menos deja abierta la posibilidad de que sea verdadera. Por lo tanto, se necesita que Q sea verdad para que P sea verdad. Ejemplo 1.14. Sea P la afirmaci´on “n es divisible por 6”y sea Q “n es divisible por 3”. Es claro que P ⇒ Q es verdad, as´ı que podemos afirmar que “es suficiente que n sea divisible por 6 para que sea divisible por 3”, o tambi´en que “se necesita que n sea divisible por 3 para que sea divisible por 6”. Por u´ ltimo, en relaci´on con P ⇒ Q, llamamos a Q ⇒ P el rec´ıproco de P ⇒ Q y ¬Q ⇒ ¬P se llama el contrarrec´ıproco de P ⇒ Q. Es claro que P ⇒ Q equivale a su contrarrec´ıproco, pero no tiene ninguna relaci´on con su rec´ıproco. Del ejemplo anterior, el rec´ıproco de P ⇒ Q es “si n es divisible por 3 entonces es divisible por 6”, lo cual no siempre es cierto, por ejemplo, con n = 9. Por otra parte, el contrarrec´ıproco de P ⇒ Q es “si n no es divisible por 3 entonces no es divisible por 6”, lo cual tiene sentido en relaci´on con P ⇒ Q, siendo su equivalente. En el caso en que P ⇒ Q y su rec´ıproco sean verdaderos, se obtendr´a P ⇔ Q por 1.12(k).

2. Deducciones L´ogicas El fundamento del razonamiento, en especial en matem´aticas, es la forma de efectuar argumentos v´alidos mediante relaciones de causa y efecto. Seg´un la teor´ıa de la secci´on anterior, esta relaci´on est´a establecida mediante la implicaci´on y, en la Proposici´on 1.12, listamos las reglas de causa y efecto b´asicas sobre la cual se puede fundamentar un razonamiento. En la Proposici´on 1.12 todas las reglas de inferencia tienen la forma (H1 ∧ H2 ∧ · · · ∧ Hn ) ⇒ C, es decir, un antecedente formado por conjunciones de varias f´ormulas y un consecuente. En estas implicaci´on, H1 , . . . , Hn representan hip´otesis que permiten concluir a C. Una forma esquem´atica en que podemos escribir que H1 ∧ H2 ∧ · · · ∧ Hn implica a C es  H1     H2    · Hip´otesis ·      ·   Hn C Conclusi´on. Por ejemplo, las primeras tres reglas de inferencia en 1.12 se representan, esquem´aticamente, por (a) P ⇒ Q P Q

(b) P ⇒ Q ¬Q ¬P

(c) P P

∧

Q

Como ejercicio importante antes de continuar la lectura, sugerimos escribir como esquemas las dem´as reglas de inferencia de la Proposici´on 1.12.

9

Otra regla de inferencia es la simultaneidad, la cual es la tautolog´ıa (P se representa por P Q P ∧ Q Simultaneidad

∧

Q) ⇒ (P

∧

Q). Como esquema,

Estos esquemas son importantes para proponer una forma de escritura con la cual se pueden verificar implicaciones sin utilizar tablas de verdad. Lo anterior se reduce en el siguiente resultado. Proposici´on 2.1 (M´etodo de la Deducci´on). Si se toman H1 , H2 , . . . , Hn como hip´otesis y, mediante reglas de inferencia y equivalencias se concluye C, entonces H1 ∧ H2 ∧ · · · ∧ Hn implica a C, es decir,  H1     H2    · Hip´otesis ·      ·   Hn C Conclusi´on. En un primer curso basado en este texto, no se espera que el lector entienda directamente el enunciado anterior, sino que basta con que comprenda pr´acticamente su aplicaci´on mediante los siguientes ejemplos. ´ Ejemplo 2.2. Veamos que ((P ⇔ Q) ∧ (Q ⇔ R)) ⇒ (P ⇔ R) es una tautolog´ıa. Esto, escrito como esquema, es P ⇔Q Q⇔R P ⇔R

De modo que basta verificar que, al tomar P ⇔ Q y Q ⇔ R como hip´otesis, se concluye P ⇔ R. El procedimiento se sigue de la siguiente forma 1. 2. 3. 4. 5. 6. 7. 8. 9.

P ⇔Q Q⇔R P ⇒Q Q⇒P Q⇒R R⇒Q P ⇒R R⇒P P ⇔R

Hip´otesis Hip´otesis 1, descomposici´on de ⇔ 1, desc. de ⇔ 2, desc. de ⇔ 2, desc. de ⇔ 3,5, transitividad de ⇒ 4,6, transitividad de ⇒ 7,8, composici´on de ⇔ .

As´ı, mediante las hip´otesis P ⇔ Q y Q ⇔ R se concluye, por medio de reglas de inferencia, que P ⇔ R, lo cual permite concluir que (P ⇔ Q) ∧ (Q ⇔ R)) implica a P ⇔ R. Ejemplo 2.3. Consideremos la siguiente deducci´on: “Si la m´aquina es barata o´ consume mucha energ´ıa, entonces no es productiva. Si la m´aquina es roja entonces es productiva. Pero la m´aquina es barata. Por lo tanto, la m´aquina no es roja.” Este tipo de razonamientos se puede escribir mediante l´ogica simb´olica. Primero, asignamos letras a las frases que componen el razonamiento, a saber, B: E: P : R:

La m´aquina es barata. La m´aquina consume mucha energ´ıa. La m´aquina es productiva. La m´aquina es roja. 10

Luego, la deducci´on se puede escribir, en forma esquem´atica, as´ı (B ∨ E) ⇒ ¬P R⇒P B ¬R

Si la m´aquina es barata o´ consume mucha energ´ıa, entonces no es productiva. Si la m´aquina es roja entonces es productiva. La m´aquina es barata. La m´aquina no es roja.

N´otese que las primeras tres frases se toman como hip´otesis, mientras que la u´ ltima corresponde a la conclusi´on. El sentido com´un indica claramente que, bajo dichas hip´otesis, la m´aquina no es roja, pues al ser barata no es productiva y, si fuera roja, entonces ser´ıa productiva. Sin embargo, independientemente del significado de las frases, podemos llegar a la misma conclusi´on utilizando l´ogica simb´olica y un razonamiento mediante reglas de inferencia (como se hizo en el ejemplo anterior), lo cual se ilustra a continuaci´on: 1. 2. 3. 4. 5. 6. 7.

(B ∨ E) ⇒ ¬P R⇒P B B∨E ¬P ¬P ⇒ ¬R ¬R

Hip´otesis Hip´otesis Hip´otesis 3, adici´on 1,4, modus ponens 2, contrarrec´ıproco 5,6, modus ponens.

Precisamente el objetivo de la l´ogica simb´olica es precisamente lo que se logr´o en el ejemplo anterior: convertir los razonamientos en s´ımbolos y reglas matem´aticas, independiente del significado de las afirmaciones involucradas. Esta forma de proceder logra tambi´en convertir el llamado sentido com´un en “reglas l´ogico-matem´aticas”. Ejemplo 2.4. Justifiquemos la siguiente deducci´on: S ⇒ (P S ¬P Q

∨

Q)

Mediante reglas de inferencia, la justificaci´on se procede como sigue: 1. 2. 3. 4. 5.

S ⇒ (P S ¬P P ∨Q Q

∨

Q) Hip´otesis Hip´otesis Hip´otesis 1,2, modus ponens 3,4, eliminaci´on de falsa en

Ejemplo 2.5. P ∨ (Q ∧ P ) S∨T S ⇒ ¬(P ∨ Q) P ∧T

11

∨

.

La deducci´on anterior se justifica como sigue: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

P ∨ (Q ∧ P ) S∨T S ⇒ ¬(P ∨ Q) (P ∨ Q) ∧ (P ∨ P ) P ∨Q ¬¬(P ∨ Q) ⇒ ¬S (P ∨ Q) ⇒ ¬S ¬S T P ∨P P P ∧T

Hip´otesis Hip´otesis Hip´otesis 1, distributiva 4, simplificaci´on 3, contrarrec´ıproco 6, doble negaci´on 5,7, modus ponenes 2,8, eliminaci´on de la falsa en ∨ 4, simplificaci´on 10, equivalencia (P ∨ P ) ⇔ P 9,11, simultaneidad.

En resumidas cuentas, para efectuar una deducci´on l´ogica como en los ejemplos anteriores, tenemos en cuenta las siguientes instrucciones: 1. Enunciar las hip´otesis, 2. justificar, mediante reglas de inferencia, una nueva afirmaci´on en base a las anteriores de la lista y 3. mediante la instrucci´on 2, llegar finalmente a la conclusi´on. Ejemplo 2.6. ¬(P ∨ ¬R) Q∨P R⇒S (Q ∧ S) ⇒ (T T

∧

S)

La justificaci´on de la anterior deducci´on es: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

¬(P ∨ ¬R) Q∨P R⇒S (Q ∧ S) ⇒ (T ¬P ∧ ¬¬R ¬P ¬¬R R Q S Q∧S T ∧S T

Hip´otesis Hip´otesis Hip´otesis ∧ S) Hip´ otesis 1, Ley D’Morgan 5, simplificaci´on 5, simplificaci´on 7, doble negaci´on 2,6, eliminaci´on de la falsa en 3,8, modus ponens 9,10, simultaneidad 4,11, modus ponens 12, simplificaci´on.

∨

Aunque todos los razonamientos de los ejemplos anteriores pueden efectuarse mediante tablas de verdad, optamos a dejar de lado esta forma de razonamiento por dos razones. La primera es que, a partir de la pr´oxima secci´on, extenderemos el lenguaje de la l´ogica con el fin de describir el lenguaje de las matem´aticas, de modo que en este punto las tablas de verdad dejan de funcionar como forma de razonamiento, aunque si 12

se preservan las t´ecnicas de razonamiento planteadas en esta secci´on. La segunda raz´on es que, cuando las afirmaciones contienen muchas letras, la tabla de verdad contiene demasiadas filas, lo cual se vuelve tedioso de analizar a comparaci´on del m´etodo por deducciones. Por ejemplo, si una afirmaci´on tiene 3 letras, su tabla de verdad tiene 8 filas, con 4 letras resulta una tabal de 16 filas, con 5 letras una tabla de 64 filas y, con 6 letras, una tabla de 128 filas.

3. Cuantificadores En las secciones anteriores introducimos una simbolog´ıa mediante la cual se pueden materializar las leyes de razonamiento. Sin embargo, no basta para describir todo el lenguaje complejo de la matem´atica, aunque si da unas bases de razonamientos como vimos. El objetivo en esta secci´on es, entonces, introducir una nueva simbolog´ıa que permite describir de forma precisa afirmaciones en matem´aticas. Una primera variaci´on en el lenguaje trabajado en las secciones anteriores es que, en la mayor´ıa de los casos, estas afirmaciones dependen de una variable. Por ejemplo, la afirmaci´on “x2 ≤ 3 depende de una variable x (que, en este caso, var´ıa entre los n´umeros reales), de modo que no es del todo apropiado asignar3 P : x2 ≤ 3. Una raz´on para esto es que no se le podr´ıa asignar un valor de verdad a P , pues e´ ste depende de x. De este modo, al tomar una letra para representar una afirmaci´on, debemos enunciar tambi´en las variables de las que dependen. La forma correcta de asignar es, entonces, P (x) : x2 ≤ 3 ´ ya que se considera que la afirmaci´on depende de x. Esta notaci´on permite tambi´en determinar la f´ormula que resulta al dar un valor a x. Por ejemplo, P (3) representa 32 ≤ 3, es decir, dar el valor 3 a la variable x. Tambi´en P (−1) representa (−1)2 ≤ 3 y P (y + 1) es (y + 1)2 ≤ 3. Aqu´ı es claro que P (3) es falsa, P (−1) es verdadera y P (y + 1) depende del valor de y. Consideremos los siguientes ejemplos de notaci´on de afirmaciones dependiente de variables: P (n) : Q(n) : R(x) : S(x) :

n es divisible por 3. n es divisible por 6. la persona x vive en Medell´ın. la persona x conoce el pueblito paisa.

Podemos utilizar estas afirmaciones y los s´ımbolos l´ogicos para formar nuevas afirmaciones. Por ejemplo, Q(n) ⇒ P (n) representa “si n es divisible por 6 entonces es divisible por 3”, lo cual es verdadero independientemente del valor de n. P (n) ∧ ¬Q(n) representa “n es divisible por 3 pero no por 6”, de donde P (9) ∧ ¬Q(9) es verdadero y P (18) ∧ ¬Q(18) es falsa. R(x) ⇔ S(x), lo cual significa “la persona x vive en Medell´ın si y solo si conoce el pueblito paisa”, lo cual no es cierto para todos los casos de x. Adem´as de modificar la notaci´on para las afirmaciones, introducimos tambi´en dos nuevos s´ımbolos l´ogicos. Definici´on 3.1 (Cuantificadores). Introducimos los siguientes s´ımbolos l´ogicos ∀ el cuantificador universal. ∃ el cuantificador existencial. 3

En la secci´on anterior nos permitimos este tipo de asignaci´on con el fin de ilustrar los m´etodos del C´alculo Proposicional.

13

Dada una afirmaci´on P (x) que depende de la variable x, utilizamos los cuantificadores para abreviar las siguientes afirmaciones ∀x P (x) todos los objetos cumplen P (x). ∃x P (x) existe un objeto que cumple P (x). Otra forma de leer ∃x P (x) es alg´un objeto cumple P (x). Ejemplo 3.2. Seg´un el ejemplo previo a la definici´on, ∀n (Q(n) ⇒ P (n)) significa, teniendo en cuenta a n como n´umero entero, que “todos n´umero entero divisible por 6 es divisible por 3”, lo cual es verdad en matem´aticas. ∃n (P (n) ∧ ¬Q(n)) significa “existe un entero divisible por 3 y no divisible por 6”, lo cual tambi´en es verdad. ∀x (R(x) ⇔ S(x)) significa, teniendo en cuenta la variable x como seres humanos, que “toda persona vive en Medell´ın si y solo si conoce el pueblito paisa”, lo cual es falso ya que hay personas que viven en Medell´ın y no conocen el pueblito paisa (algunos reci´en nacidos, por ejemplo) y hay turistas que conocen el pueblito paisa y no viven en Medell´ın. Observaci´on 3.3. Cuando una f´ormula tiene un cuantificador, la variable que aplica ese cuantificador pierde significado material ya que se convierte solo en una referencia para el cuantificador. N´otese del ejemplo anterior que ∀x (R(x) ⇔ S(x)) se lee “toda persona vive en Medell´ın si y solo si conoce el pueblito paisa”, no necesariamente se escribi´o como “toda persona x vive en Medell´ın si y solo si conoce el pueblito paisa”, pues el x es reduntande ya que se refiere a personas. Adem´as, si cambiamos la variable z y escribimos ∀z (R(z) ⇔ S(z)), esto se lee “toda persona vive en Medell´ın si y solo si conoce el pueblito paisa”, es decir, significa exactamente lo mismo que ∀x (R(x) ⇔ S(x)), por lo cual la variable x o z no tienen importancia en el significado material de la afirmaci´on, sino que sirve como referencia para indicar “todas las personas”. Ejemplo 3.4. La afirmaci´on ∀x (x2 ≥ 0) representa, al variar x en los n´umeros reales, que “el cuadrado de cualquier n´umero real es mayor o igual que 0”, lo cual es verdadero en matem´aticas. Es claro que x2 ≥ 0 no significa lo mismo que y 2 ≥ 0, pues se refieren directamente a variables distintas. Pero ∀x (x2 ≥ 0) significa lo mismo que ∀y (y 2 ≥ 0). En los ejemplos anteriores, al introducir un cuantificador, nos hemos referido a variables entre n´umeros enteros, entre humanos o entre n´umeros reales, pero en la f´ormula e´ sto no queda especificado. Es bueno introducir una notaci´on en la cual se tenga el cuenta el conjunto donde var´ıa la variable de un cuantificador. Definici´on 3.5 (Cuantificadores acotados). Dado un conjunto U y una afirmaci´on P (x), introducimos la siguiente notaci´on ∀x∈U P (x) todos los objetos de U cumplen P (x). ∃x∈U P (x) existe un objeto en U que cumple P (x). ∀x∈U y ∃x∈U se llaman cuantificadores acotados. Ejemplo 3.6. Denotemos por Z al conjunto de los n´umeros enteros, por U al conjunto de los humanos y R el conjunto de los n´umeros reales. De los ejemplos anteriores, es m´as adecuado escribir ∀n∈Z (Q(n) ⇒ P (n)) (todo n´umero entero divisible por 6 es divisible por 3), ∃n∈Z(P (n) ∧ ¬Q(n)) (existe un n´umero entero divisible por 3 pero que no es divisible por 6), ∀x∈U (R(x) ⇔ S(x)) (toda persona vive en Medell´ın si y solo si conoce el pueblito paisa) y ∀x∈R (x2 ≥ 0) (todo n´umero real al cuadrado es mayor o igual que 0). Definici´on 3.7 (Existencia u´ nica). Dada una afirmaci´on P (x) y un conjunto U , denotamos por ∃!x P (x) existe un u´ nico objeto que cumple P (x). ∃!x∈U P (x) existe un u´ nico objeto en U que cumple P (x). ∃! se denomina el cuantificador de existencia u´ nica y ∃!x∈U es el cuantificador acotado de existencia u´ nica. 14

Ejemplo 3.8. Denotemos por P (x, y) a “y es la madre de x” y sea U el conjunto de los humanos. Luego, la afirmaci´on ∀x∈U ∃!y∈U P (x, y) significa “todo ser humano tiene una u´ nica madre”. Otro ejemplo es la afirmaci´on “existe un u´ nico numero real tal que al sumarse con cualquier otro real es igual a e´ ste u´ ltimo”, lo cual se representa por ∃!z∈R ∀x∈R (x + z = x). Aquel u´ nico n´umero real es el que se conoce por 0. En esta nueva notaci´on tambi´en se puede determinar cu´ando una afirmaci´on es verdadera, pero en estos casos no las llamamos tautolog´ıa puesto que en matem´aticas no se razona en base a las tablas de verdad. En este caso la noci´on de verdad tiene otro significado que, incluso, est´a ligado a una teor´ıa. Definici´on 3.9 (C´alculo de Predicados). El C´alculo de Predicados es la extensi´on del C´alculo Propocisional al lenguaje con variables y cuantificadores. Llamamos Teorema a una afirmaci´on que es verdadera (ya sea en el C´alculo de Predicados y en las matem´aticas). Directamente, todas las tautolog´ıas son teoremas del C´alculo de Predicados. De los ejemplos anteriores, “todo n´umero entero divisible por 6 es divisible por 3”, “existe un n´umero entero divisible por 3 que no es divisible por 6”, “todo n´umero real elevado al cuadrado es mayor o igual que 0”y ∃!z∈R ∀x∈R (x + z = x) son teoremas de las matem´aticas. Para los teoremas del C´alculo de Predicados que expondremos en esta secci´on no daremos sus justificaciones rigurosas, ya que esto corresponde a un curso de L´ogica Matem´atica. Sin embargo, explicaremos las razones intuitivas de por qu´e tales afirmaciones son verdaderas. Respecto a las secciones anteriores variamos el significado de Proposici´on: con esta palabra enunciamos teoremas y propiedades generales del c´alculo de predicados. Inclusive, se suele usar para enunciar teoremas de las matem´aticas. Daremos este uso de proposici´on a lo largo de todo el texto. Proposici´on 3.10. Los siguientes son teoremas del C´alculo de Predicados. (a) (∀x∈U P (x)) ⇔ ∀x (x ∈ U ⇒ P (x)). (b) (∃x∈U P (x)) ⇔ ∃x (x ∈ U

∧

P (x)).


(c) (∃!x P (x)) ⇔ (∃x P (x)) ∧ ∀x ∀y ((P (x) ∧ P (y)) ⇒ x = y) .
(d) (∃!x∈U P (x)) ⇔ (∃x∈U P (x)) ∧ ∀x∈U ∀y∈U ((P (x) ∧ P (y)) ⇒ x = y) . (e) (∃!x∈U P (x)) ⇔ ∃!x (x ∈ U

∧

P (x)).

Justificaci´on (no formal). (a) ∀x (x ∈ U ⇒ P (x)) significa que para cualquier objeto, si e´ ste est´a en U entonces cumple P (x), lo cual puede reescribirse como cualquier objeto de U cumple P (x), es decir, ∀x∈U P (x). De esta forma vemos que ∀x∈U P (x) y ∀x (x ∈ U ⇒ P (x)) significan lo mismo, es decir, son equivalentes. (b) ∃x (x ∈ U ∧ P (x)) significa que existe un objeto que est´a en U y que cumple P (x), lo cual podemos reescribir como existe un objeto en U que cumple P (x), es decir, ∃x∈U P (x). De este modo tenemos que ambas afirmaciones significan lo mismo y, por lo tanto, son equivalentes. (c) Vamos a dividir la f´ormula de la derecha de la equivalencia en dos componentes: Existencia ∃x P (x).

Unicidad ∀x ∀y ((P (x) ∧ P (y)) ⇒ x = y).

15

Existencia indica que existe un objeto que cumple P (x). La unicidad dice que si dos objetos cumplen la propiedad entonces son iguales, o, lo que es lo mismo, que no hay m´as de un objeto que cumple la P (x), o dicho de otra forma, existe a lo sumo un objeto que cumple P (x). Por lo tanto, si formamos la conjunci´on entre existencia y unicidad estamos indicando, con la existencia, que existe un objeto y, m´as la unicidad, que no hay m´as de uno, es decir, que existe un u´ nico objeto que cumple P (x). (d) Se razona an´alogamente al inciso anterior, dividiendo la afirmaci´on de la derecha en existencia y unicidad. (e) Se razona an´alogamente a (b). Observaci´on 3.11. El resultado anterior dice que los cuantificadores acotados y de existencia u´ nica se pueden definir a partir de ∀ y ∃. Proposici´on 3.12 (Negaci´on de cuantificadores). Los siguientes son teoremas del C´alculo de Predicados. (a) (¬∀x P (x)) ⇔ ∃x (¬P (x)) (negaci´on del cuantificador univeral). (b) (¬∃x P (x)) ⇔ ∀x (¬P (x)) (negaci´on del cuantificador existencial). (c) (¬∀x∈U P (x)) ⇔ ∃x∈U (¬P (x)) (negaci´on del cuantificador univeral acotado). (d) (¬∃x∈U P (x)) ⇔ ∀x∈U (¬P (x)) (negaci´on del cuantificador existencial acotado). Justificaci´on (no formal). (a) ¬∀x P (x) significa que no todos los objetos cumplen P (x). Esto, dicho de otra forma, significa que hay un objeto que no cumple P (x) lo cual es, exactamente, ∃x (¬P (x)). Por lo tanto, ambas expresiones tienen el mismo significado, es decir, son equivalentes. (b) ¬∃x P (x) significa que no existe un objeto que cumple P (x), dicho de otra forma, ning´un objeto cumple ´ P (x). Esto da a entender que todos los objetos no cumplen P (x), es decir ∀x (¬P (x)). Por lo tanto, ambas afirmaciones tienen el mismo significado. (c) Se razona an´alogamente a (a). Sin embargo, podemos dar una justificaci´on formal de este hecho (x ∈ /U representa ¬(x ∈ U ): ¬∀x∈U P (x)

⇔ ¬∀x (x ∈ U ⇒ P (x)) ⇔ ∃x ¬(x ∈ U ⇒ P (x)) ⇔ ∃x (x ∈ U ∧ ¬P (x)) ⇔ ∃x∈U (¬P (x))

3.10(a) negaci´on de ∀ negaci´on de ⇒ 3.10(b)

(d) Se razona an´alogamente a (b). Sin embargo, de una forma muy similar al inciso anterior, podemos proporcionar una justificaci´on formal: ¬∃x∈U P (x)

⇔ ¬∃x (x ∈ U ∧ P (x)) ⇔ ∀x ¬(x ∈ U ∧ P (x)) ⇔ ∀x (x ∈ / U ∨ ¬P (x)) ⇔ ∀x (x ∈ U ⇒ ¬P (x)) ⇔ ∀x∈U (¬P (x))

16

3.10(b) negaci´on de ∃ ley D’Morgan 1.6(n) 3.10(a)

Observaci´on 3.13. N´otese que ∃x P (x) equivale a ¬∀x ¬P (x). En efecto, ∀x ¬P (x) equivale a ¬∃x P (x) y, por lo tanto, ¬∀x ¬P (x) equivale a ¬¬∃x P (x), lo cual equivale a ∃x P (x). Lo anterior indica que el ∃ se puede definir en t´erminos de ∀. Por lo tanto, seg´un las observaciones 1.8 y 3.11 todo el C´alculo de Predicados se puede construir s´olo con los s´ımbolos ¬, ∨ y ∀. Ejemplo 3.14. Denotemos por P (x, y) la afirmaci´on “a la persona x le gusta la fruta y”. Expresemos las siguientes afirmaciones: ∀x ∀y P (x, y) ∀y ∀x P (x, y) ∃x ∀y P (x, y) ∀y ∃x P (x, y) ∃y ∀x P (x, y) ∀x ∃y P (x, y) ∃x ∃y P (x, y) ∃y ∃x P (x, y)

A todas las personas les gusta todas las frutas. Todas las frutas les gustan a todas las personas. Hay una persona que le gustan todas las frutas. Cualquier fruta le gusta al menos a una persona. Hay una fruta que le gusta a todas las personas. A cualquier persona le gusta al menos una fruta. Hay una persona a la que le gusta alguna fruta. Hay una fruta que le gusta a alguna persona.

Podemos notar que las dos primeras afirmaciones significan lo mismo, al igual que las dos u´ ltimas. Esto es un indicio de que el orden de los cuantificadores del mismo tipo no importa en una afirmaci´on. Sin embargo, la tercera afirmaci´on no significa lo mismo que la cuarta, y la quinta no significa lo mismo que la sexta, lo cual es evidencia de que el orden si importa para cuantificadores de distinto tipo. El siguiente resultado ilustra estos hechos. Proposici´on 3.15. Los siguientes son teoremas del C´alculo Proposicional. (a) (∀x ∀y P (x, y)) ⇔ ∀y ∀x P (x, y) (conmutatividad de cuantificadores del mismo tipo). (b) (∃x ∃y P (x, y)) ⇔ ∃y ∃x P (x, y) (conmutatividad de cuantificadores del mismo tipo). (c) (∃x ∀y P (x, y)) ⇒ ∀y ∃x P (x, y). Este resultado es v´alido tambi´en para cuantificadores acotados. En matem´aticas es usual demostrar afirmaciones que tienen la forma ∀x P (x) y ∀x∈U P (x). En la pr´oxima secci´on veremos el modo de proceder con sus demostraciones. Por otra parte, cuando son falsas, es m´as sencillo de verificar: para ver que ∀x P (x) es falsa hay que encontrar un objeto que cumpla ¬P (x) y, para ver que ∀x∈U P (x) es falsa, hay que encontrar un objeto en U que cumpla ¬P (x). Dicho objeto es el que usualmente se llama contraejemplo de la afirmaci´on. Ejemplo 3.16. Veamos que ∀x∈R (x2 > 1) es falsa. Esto es claro porque (0,5)2 < 1. As´ı, 0,5 es un contraejemplo de ∀x∈R (x2 > 1). Ejemplo 3.17. Sea P (n) “n es par” y Q(n) “n es divisible por 4”. Veamos que ∀n∈Z (P (n) ⇒ Q(n)) es falsa. Para esto, basta hallar un contraejemplo, el cual puede ser 2, 6, 10, 14, entre otros. En particular, P (2) ∧ ¬Q(2) es cierto, o lo que es lo mismo, ¬(P (2) ⇒ Q(2)) (negaci´on de la implicaci´on). Al encontrar un objeto en U que cumpla ¬P (x) se est´a probando que ∃x∈U ¬P (x) es verdadera, lo cual equivale a ¬∀x∈U P (x). Por esta raz´on, basta hallar un contraejemplo para verificar que ∀x∈U P (x) es falsa.

17

4. M´etodos de Demostraci´on Todos los elementos de la L´ogica Simb´olica definidos en las secciones anteriores son los fundamentos de los razonamientos sobre los cuales se puede comprobar cu´ando una afirmaci´on en matem´aticas es un Teorema, es decir, es verdadera. Una afirmaci´on se comprueba verdadera en matem´aticas por medio de la noci´on de demostraci´on o, lo que es lo mismo, prueba. Aunque en la L´ogica Simb´olica hay una forma rigurosa de definir esta noci´on, en este texto s´olo nos centramos en su significado intuitivo. Una demostraci´on de un afirmaci´on es un razonamiento finito donde cada paso est´a justificado por los pasos anteriores, reglas de inferencia y/o teoremas ya demostrados. En la secci´on 2 vimos muchos ejemplos de demostraciones, pues consisten en razonamientos que se justifican por reglas de inferencia. El objetivo principal de esta secci´on ser´a mostrar los diferentes m´etodos para generar demostraciones de afirmaciones en matem´aticas. Antes de proceder, fijaremos la notaci´on y expondremos algunos teoremas matem´aticos iniciales (los cuales no demostraremos para tener un punto de partida). Denotemos por N el conjunto de los n´umeros naturales, es decir, N = {1, 2, 3, 4, . . .}4 . Z denota el conjunto de los n´umeros enteros, es decir, Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}. Q es el conjunto de los n´umeros racionales (de la forma ab con a, b ∈ Z y b 6= 0), R es el conjunto de los n´umeros reales y Q∗ el conjunto de los n´umeros irracionales (es decir, los reales que no son racionales). Conocemos que R = Q ∪ Q∗ (uni´on de conjuntos) y Q ∩ Q∗ = ∅ (no hay n´umeros reales que sean racionales e irracionales a la vez), lo cual introducimos sin demostraci´on. Tambi´en sabemos que estos conjuntos tienen unas operaciones definidas que cumplen ciertas propiedades, lo cual utilizaremos sin recurrir a sus demostraciones. ´ consiste en cuatro componentes: Recordemos alguna notaci´on sobre la divisi´on de n´umeros enteros. Esta dividendo, divisor, cociente y residuo. Por ejemplo, dividendo residuo

1073 3

5 214

divisor cociente

Cuadro 6: Ejemplo del esquema de la divisi´on de dos enteros

El residuo es lo que le falta al producto del conciente con el divisor para llegar al dividendo. En este ´ caso, a 5 · 214 (lo cual es 1070) le faltan 3 para llegar a 1073. Esto se expresa como 1073 = 5 · 214 + 3. De forma general, si a y b son enteros con b 6= 0, al efectuar la divisi´on entre a con b resulta un cociente que llamaremos q y un residuo que llamaremos r. De este forma, se tiene el esquema dividendo residuo

a r

b q

divisor cociente

Cuadro 7: Esquema de la divisi´on de dos enteros

Es decir, a b · q la falta r para llegar a a, es decir a = bq + r. Esta expresi´on es lo que se conoce como el algoritmo de la divisi´on y se le exige a r que sea no negativo y menor que |b|. Aqu´ı |b| denota el valor absoluto de b, el cual se define como el n´umero no negativo que representa a b (por ejemplo, | − 2| = 2, |5| = 5 y |0| = 0). 4

En algunos textos, definen N = {0, 1, 2, 3, 4, . . .}.

18

Teorema 4.1 (Algoritmo de la divisi´on.). Dados a y b enteros con b 6= 0, existen u´ nicos enteros q y r tal que a = bq + r y 0 ≤ r < |b|. Como f´ormula del lenguaje de la l´ogica, esto se enuncia por
∀a∈Z ∀b∈Z b 6= 0 ⇒ ∃!q∈Z ∃!r∈Z (a = bq + r ∧ 0 ≤ r < |b|) . Observaci´on 4.2. Lo anterior ilustra que el cociente y el residuo (entre 0 y el divisor) son u´ nicos al efectuar una divisi´on por un divisor diferente de 0. El caso de un divisor igual a cero no se considera porque una divisi´on por cero no tiene sentido. Un algoritmo de la divisi´on con b = 0 se escribir´ıa como a = 0q + r ´ con 0 ≤ r < 0. Esta desigualdad es inconsistente, lo cual indica que la divisi´on por 0 no admite residuos (nisiquiera residuo igual a cero). Es de conocer que un n´umero divide a otro cuando, al efectuar la divisi´on entre ellos, no dejan residuo, es decir, el residuo es 0. De esta forma, podemos dar la siguiente definici´on. Al dividir a por b, con b 6= 0 resulta, por el algoritmo de la divisi´on, que existen q, r ∈ Z (´unicos) tal que a = bq + r. Si b divide a a ´ entonces el residuo r = 0, por lo cual a = bq. Esto motiva la siguiente definici´on. Definici´on 4.3 (Divisibilidad). Sean a, b ∈ Z. Decimos que b divide a a sii5 ∃k∈Z(a = bk). Tambi´en se lee a es divisible por b, a es m´ultiplo de b o b es divisor de a y, como notaci´on, se abrevia b | a. Escribimos b ∤ a (b no divide a a) para representar ¬(b | a). Por ejemplo, 5 ∤ 1073, pues al dividir 1073 entre 5 deja residuo 3, mientras que 7 | 343, pues al dividir 343 entre 7 deja residuo 0 y cociente 49, es decir, 343 = 7 · 49, por lo cual ∃k∈Z(343 = 7k) (dicho k es 49). Observaci´on 4.4. En la definici´on de divisibilidad no enunciamos la restricci´on de que b debe ser diferente de cero. La raz´on de esto es que la definici´on presenta cierta consistencia a´un cuando b = 0. As´ı, 0 | a si y solo si a = 0 · k para alg´un k ∈ Z. De esto es claro que el u´ nico caso en que 0 | a es a = 0, por lo cual puede decirse que 0 divide a 0. Sin embargo, esta posici´on se rechaza en matem´aticas por la siguiente raz´on: cuando un n´umero b 6= 0 divide a un n´umero a, es decir, a = bk, el cociente k que resulta de la divisi´on es u´ nico, pero en el caso “0 divide a 0” el cociente no es u´ nico, pues 0 = 0k es v´alido para cualquier entero k. As´ı, no puede indicarse un resultado de dividir 0 entre 0. En adelante, nunca vamos a considerar una divisi´on por 0. Es de conocer que un n´umero es par cuando es divisible por 2, es decir, que deja residuo 0 al dividirse por 2. De este modo, un entero n es par si y solo si 2 | n, es decir, n = 2k para alg´un entero k. Por otra parte, un entero n es impar si y solo so 2 ∤ n (2 no divide a n), lo cual significa que no deja residuo 0 al dividirse por 2. Al efectuar la divisi´on de n entre 2, resulta un cociente k y un residuo r y se cumple n = 2k + r. Seg´un el algoritmo de la divisi´on 0 ≤ r < 2, por lo cual r s´olo puede ser 0 o´ 1. Si r es cero tenemos que el n´umero es par y, si r = 1, se sigue que el n´umero es impar. Lo anterior motiva la siguiente definici´on. Definici´on 4.5 (Par,Impar). Un entero n es par sii ∃k∈Z(n = 2k). n es impar sii ∃k∈Z (n = 2k + 1). Del algoritmo de la divisi´on se obtiene la siguiente consecuencia. Corolario 4.6. Un n´umero entero es par o impar, pero no es ambos a la vez. Por ejemplo, 11, −1 y 1 son impares, pues 11 = 2 · 5 + 1, −1 = 2 · (−1) + 1 y 1 = 2 · 0 + 1, mientras que 150, 0 y −6 son pares, pues 150 = 2 · 75, 0 = 2 · 0 y −6 = 2 · (−3). Antes de pasar a explicar los m´etodos de demostraci´on, explicamos qu´e queremos decir con Teorema, Corolario y Lema. Estas palabras solo denotan teoremas de las matem´aticas, solo que cada una representa 5

la expresi´on sii abrevia “si y solo si”.

19

una categor´ıa de teorema. Lema representa un teorema sencillo de probar que precede a otro teorema m´as importante, Teorema se utiliza para enuncias resultados importantes y Corolario representa un teorema que es consecuencia directa de un resultado que lo precede. En ocasiones tambi´en se utiliza la palabra Proposici´on para denotar teoremas en matem´aticas, aunque la seguiremos usando tambi´en para denotar propiedades del c´alculo de predicados. Los principales m´etodos de demostraci´on en matem´aticas son el m´etodo directo, contrarrec´ıproco, reducci´on al absurdo, disyunci´on de casos, doble implicaci´on e inducci´on matem´atica, los cuales estudiaremos en esta secci´on.

4.1. M´etodos directo El m´etodo est´a basado en la Proposici´on 2.1 y en los siguientes principios del c´alculo de predicados. Proposici´on 4.7 (M´etodo directo). Para demostrar P ⇒ Q basta tomar a P como hip´otesis y, mediante un razonamiento l´ogico, concluir Q. Proposici´on 4.8 (Principio de Generalizaci´on). Si P (x) es un teorema, entonces ∀x P (x) es un teorema. Como consecuencia directa de estas Proposiciones, se siguen Proposici´on 4.9 (M´etodo directo - Variaci´on 1). Para demostrar ∀x (P (x) ⇒ Q(x)) basta tomar a P (x) como hip´otesis y concluir Q(x). Justificaci´on. Al tomar P (x) como hip´otesis y concluir Q(x), por el m´etodo directo P (x) ⇒ Q(x) es un teorema. Luego, por el principio de generalizaci´on, ∀x (P (x) ⇒ Q(x)) es un teorema. Proposici´on 4.10 (M´etodo directo - Variaci´on 2). Para demostrar ∀x∈U Q(x) basta tomar a x ∈ U como hip´otesis y concluir Q(x). Justificaci´on. Como ∀x∈U Q(x) equivale a ∀x (x ∈ U ⇒ Q(x)), e´ ste u´ ltimo se demuestra al tomar x ∈ U en vez de P (x) en la primera variaci´on del m´etodo directo. Las anteriores afirmaciones tienen un fuerte contenido t´ecnico que no es necesario tener en cuenta cuando se procede a aplicar el m´etodo directo de demostraci´on. Como primer ejemplo, vamos a utilizar el m´etodo directo para probar que todos los enteros dividen al cero6 . Al escribir esta afirmaci´on en lenguaje matem´atico, resulta ∀n∈Z (n | 0). La segunda variaci´on del m´etodo directo da la pauta para probar esta afirmaci´on, a saber, tomar a n ∈ Z como hip´otesis y concluir n | 0. Teorema 4.11. Todo n´umero entero divide a 0 (∀n∈Z (n | 0)). Demostraci´on. Tomemos n ∈ Z como hip´otesis y veamos que n | 0 es cierto. En efecto, n | 0, por definici´on de divisibilidad, equivale a ∃k∈Z (0 = nk). Esto u´ ltimo es verdad, pues7 0 = n0 y, al tomar k = 0, tenemos que existe un k entero tal que 0 = nk. Por lo tanto, n | 0. 6

Aunque insistimos en no considerar al cero como divisor de un n´umero, esta propiedad se cumple a´un al tomar a 0 como divisor, pues 0 = 0k para cualquier k ∈ Z. 7 Esto muestra que el cociente de dividir 0 por un n´umero diferente de cero es 0.

20

Ahora vamos a demostrar que el producto de dos n´umeros enteros impares tiene que ser impar. En lenguaje matem´atico, e´ sto se expresa como ∀a∈Z ∀b∈Z ((a impar ∧ b impar) ⇒ ab impar)8 . Seg´un la primera variaci´on del m´etodo directo, esto se prueba al tomar a y b impares, como hip´otesis, y concluir que ab es impar. Teorema 4.12. El producto de dos enteros impares es impar. Demostraci´on. Supongamos que a y b son dos enteros impares y probemos que ab es impar. Seg´un la definici´on de impar, a = 2k + 1 para alg´un k ∈ Z y b = 2t + 1 para alg´un t ∈ Z9 . Luego, ab = (2k + 1)(2t + 1) = 4kt + 2k + 2t + 1 = 2(2kt + k + t) + 1. Si llamamos p = 2kt + k + t obtenemos que ab = 2p + 1 con p un entero. Por lo tanto, ab es impar (por definici´on de impar). Como consecuencia directa, se tiene el siguiente resultado. Corolario 4.13. El cuadrado de un entero impar es impar. Demostraci´on. Si a es impar, del Teorema anterior se tiene que aa es impar, es decir a2 es impar. Como u´ ltimo ejemplo, vamos a probar que la suma de un entero impar con un par resulta ser impar. En lenguaje matem´atico, e´ sto se enuncia como ∀m∈Z ∀n∈Z ((m impar ∧ n par) ⇒ m + n impar). Al recurrir de nuevo a la primera variaci´on del m´etodo directo, nos damos cuenta que su demostraci´on consta de suponer como hip´otesis m impar y n par, para concluir m + n impar. Teorema 4.14. La suma de un entero impar con uno par es un entero impar. Demostraci´on. Supongamos que m es un entero impar y n uno par. Veamos que m + n es impar. Por la definici´on de par e impar, m = 2k + 1 para alg´un k ∈ Z y n = 2t para alg´un t ∈ Z. Luego, m + n = 2k + 1 + 2t = 2(k + t) + 1. Si llamamos p = k + t entonces m + n = 2p + 1 con p ∈ Z. Por lo tanto, m + n es impar (por definici´on de impar). Es claro que los teoremas probados son hechos intuitivamente claros sobre n´umeros enteros, por lo cual puede sorprender el porqu´e de ofrecer una t´ecnica para justificar su verdad. El hecho principial, espec´ıficamente para estos teoremas, es que se trata de justificar un enunciado que cumplen infinita cantidad de n´umeros. Por ejemplo, para el u´ ltimo teorema, sabemos que hay infinitos n´umeros pares e infinitos impares. Por lo tanto, una demostraci´on para el Teorema 4.14 no puede ser as´ı: “por ejemplo, 5+4 = 9, −9+8 = −1, 9 + 0 = 9, etc, entonces la experiencia nos indica que la suma de un impar con un par es impar”. Esto no es v´alido por el “etcetera”, pues si de esa forma se quiere ver que en todos los casos se cumple la afirmaci´on, habr´ıa que sumar todos los impares con todos los pares y llegar a que todas esas sumas resultan un impar. El problema radica en que hay que hacer infinitas sumas, lo cual es humanamente imposible. La experiencia no es evidencia suficiente para probar un teorema, realmente hay que dar una justificaci´on fuerte y concisa como las que hemos expuesto. Por eso es que nuestra demostraci´on toma un m impar, un n par, y procede a verificar que su suma es impar, pues aqu´ı m y n son representantes variables de enteros, es decir, representan a cualquiera, lo cual verifica, en un solo caso, todas las infinitas posibilidades. 8

No expresamos impar en s´ımbolos matem´aticos con el fin de ofrecer una expresi´on m´as legible al lector y no obscurecer su significado. 9 tomamos t en vez de k en el caso de b porque nada asegura que el mismo n´umero funcione para a y b.

21

4.2. M´etodo del contrarrec´ıproco La ley del contrarrec´ıproco dice que P ⇒ Q equivale a ¬Q ⇒ ¬P . Por lo tanto, para probar una afirmaci´on de la forma P ⇒ Q basta demostrar su contrarrec´ıproco, ¬Q ⇒ ¬P , lo cual puede hacerse por m´etodo directo. Teorema 4.15. Si a ∈ Z y a2 es par, entonces a es par. Demostraci´on. Sea a ∈ Z. Del Corolario 4.13 se tiene a impar ⇒ a2 impar. Luego, por contrarrec´ıproco, (¬(a2 impar)) ⇒ ¬(a impar), es decir a2 par ⇒ a par, lo cual prueba el resultado. Teorema 4.16. Dados a, b ∈ Z, si ab es par, entonces a es par o´ b es par. ´ Demostraci´on. Sean a, b ∈ Z. Del Teorema 4.12 tenemos que (a impar ∧ b impar) ⇒ ab impar. Esto equivale a su contrarrec´ıproco, que es (¬(ab impar)) ⇒ ¬(a impar ∧ b impar). Por ley D’Morgan, esto es ab par ⇒ (a par ∨ b par) que es lo que se quer´ıa probar. Teorema 4.17. Sea a ∈ Z. Si a2 es impar, entonces a es impar. Demostraci´on. Procedamos en esta prueba por contrarrec´ıproco y veamos que a par ⇒ a2 par (esto lo probamos por m´etodo directo). En efecto, si a es par, por definici´on a = 2k para alg´un k ∈ Z. Luego, a2 = (2k)2 = 4k2 = 2(2k2 ). Si llamamos p = 2k2 , obtenemos a2 = 2p con p ∈ Z, lo cual garantiza que a2 es par.

4.3. M´etodo de reducci´on al absurdo El m´etodo de reducci´on al absurdo representa una forma de razonar del sentido com´un. Supongamos que queremos argumentar que una afirmaci´on Q es cierta. Una forma de hacerlo es suponiendo que es falsa y llegar a un absurdo, es decir, a una contradicci´on en el argumento. De esta forma, no hay modo que Q sea falsa y tiene que ser cierta. Un peque˜no ejemplo es el siguiente: supongamos que x ∈ R tal que x ≥ 2 y veamos que x 6= 1 es cierta. Un argumento l´ogico es que, si suponemos que x 6= 1 es falsa, es decir, x = 1, entonces resulta 1 ≥ 2, lo cual es una contradicci´on (o absurdo) en el argumento. Por lo tanto, x 6= 1 es verdad. Antes de proceder a dar ejemplos sobre la aplicaci´on del m´etodo de reducci´on al absurdo, introduzcamos algunas nociones. Definici´on 4.18 (M´aximo com´un divisor). Dados dos enteros a y b, el m´aximo com´un divisor de a y b, denotado por mcd(a, b), es el m´aximo entero no negativo que divide a a y b. En lenguaje matem´atico,
d = mcd(a, b) ⇔ d ≥ 0 ∧ d | a ∧ d | b ∧ ∀c∈Z((c | a ∧ c | b) ⇒ c ≤ d) . Definici´on 4.19 (Primos relativos). Dos enteros a y b son primos relativos sii mcd(a, b) = 1, es decir, el u´ nico entero positivo en com´un que los divide es el 1. Por ejemplo mcd(16, 88) = 8, mcd(2, 11) = 1 y mcd(−7, 343) = 7. Aqu´ı podemos observar que 2 y 11 son primos relativos. Como ejemplo, probado con m´etodo directo, tenemos lo siguiente. Lema 4.20. Dos n´umeros pares no son primos relativos. 22

Demostraci´on. Supongamos que a y b son n´umeros pares. Luego, 2 | a y 2 | b. Por lo tanto, como 2 divide a a y b y mcd(a, b) es el m´aximo que divide a ambos, entonces mcd(a, b) ≥ 2. Por lo tanto, mcd(a, b) 6= 1. Como consecuencia de la notaci´on, presentamos el siguiente teorema sobre n´umeros racionales (el cual no demostramos). Teorema 4.21 (Simplificaci´on de n´umeros racionales). Dado un n´umero racional q existen u´ nicos enteros a y b primos relativos, con b > 0, tal que q = ab . En lenguaje matem´atico e´ sto se expresa por ∀q∈Q ∃!a∈Z ∃!b∈Z (q =

a b

∧

b > 0 ∧ mcd(a, b) = 1).

Es cierto que hay infinitas formas de expresar un n´umero racional. Por ejemplo, si q = 15 ´ ste tambi´en 9 ,e 40 −500 es igual a 10 que no se pueden simplificar, a , , , etc. Pero entre esas infinitas formas existen solo dos 6 24 −300 5 −5 5 saber, 3 y −3 . Entre e´ stas, solo una tiene denominador positivo, 3 , el fraccionario al cual se refiere el teorema anterior (n´otese que 5 y 3 son primos relativos). Con este ejemplo ilustramos que el anterior teorema dice que un fraccionario se puede simplificar de manera u´ nica con el denominador positivo. Tambi´en se sabe que, en un fraccionario simplificado, el numerador y denominador son primos relativos. El hecho anterior lo utilizamos para probar el siguiente resultado mediante el m´etodo de reducci´on al absurdo. √ Teorema 4.22. 2 es irracional. √ Demostraci´on. Supongamos, por lo contrario, que racional. Por el Teorema 4.21 existen u´ nicos √ 2 es 2 enteros a y b primos relativos, con b > 0, tal que 2 = ab . Al elevar al cuadrado, obtenemos 2 = ab2 , de donde a2 = 2b2 . De lo anterior se sigue que a2 es un n´umero par y, por el Teorema 4.15, a es par. Luego, por definici´on, a = 2k para alg´un k ∈ Z y, como a2 = 2b2 , al sustituir a obtenemos (2k)2 = 2b2 , es decir, 4k2 = 2b2 y, al dividir por 2 en la igualdad, obtenemos 2k2 = b2 . Lo anterior permite concluir que b2 es par, por lo que b es par seg´un el Teorema 4.15. As´ı, como a y b son pares, del Lema 4.20 √ se sigue que a y b no son primos relativos, cuando si lo son. Este absurdo es el que permite concluir que 2 es irracional. Los m´etodos de demostraci´on se pueden combinar para elaborar una sola prueba. Por ejemplo, para probar P ⇒ Q podemos proceder por m´etodo directo y tomar a P como hip´otesis. Luego, para concluir Q, podemos proceder por reducci´on al absurdo y suponer ¬Q para llegar a una contradicci´on. Como ejemplo de este esquema tenemos el siguiente resultado. Teorema 4.23. El producto de un irracional con un racional distinto de cero resulta en un irracional. Demostraci´on. Mediante m´etodo directo, supongamos x ∈ Q∗ y y ∈ Q con y 6= 0 y veamos que xy es irracional. Pero esto u´ ltimo lo probamos por reducci´on al absurdo: supongamos que xy es un racional. Como y es un racional distinto de cero, es claro que y1 es un racional. Tambi´en, como el producto de dos racionales   es racional, entonces xy y1 es racional, es decir, x es un racional, lo cual contradice la hip´otesis de que x ∈ Q∗ .

4.4. M´etodo de disyunci´on de casos Las demostraciones por disyunci´on de casos casi siempre se presentan acompa˜nanas de los dem´as m´etodos de demostraci´on. El esquema que representa este m´etodo es la regla de inferencia en la Propocisi´on

23

1.12(m), a saber, P ∨Q P ⇒R Q⇒R R En la hip´otesis tenemos P ∨ Q, es decir, uno de los dos casos P o´ Q son ciertos. Pero tanto el primer caso como el segundo implican a R, por lo cual, independiente del caso, R es cierta y es la conclusi´on de la inferencia. En el siguiente ejemplo vamos a utilizar la disyunci´on de casos para probar que, dados dos enteros a y b, si alguno de los dos es par, entonces ab es par. Denotemos primero por P : “a es par”, Q: “b es par”y R: “ab es par”. As´ı que suponemos P ∨ Q como hip´otesis para concluir R. P ∨ Q representa que tenemos dos casos posibles. Si probamos que el primer caso implica a R (P ⇒ R) y que el segundo caso tambi´en lo implica (Q ⇒ R), esto significa que R es cierta independiente de los casos (lo cual se justifica por la regla de inferencia citada anteriormente). Teorema 4.24. Sean a, b ∈ Z. Si a es par o´ b es par, entonces ab es par. Demostraci´on. Supongamos que a es par o´ b es par. Analicemos cada caso por separado. a es par. Por definici´on, a = 2k para alg´un k ∈ Z. Luego, ab = 2kb lo cual indica que ab es m´ultiplo de 2, es decir, par (aqu´ı se prob´o a par ⇒ ab par). b es par. Por definici´on, b = 2t para alg´un t ∈ Z. Luego, ab = 2ta lo cual indica que ab es m´ultiplo de 2, es decir, par (aqu´ı se prob´o b par ⇒ ab par). Por disyunci´on de casos, podemos conluir que ab es par. Corolario 4.25. Si n ∈ Z entonces n(n + 1) es par. Demostraci´on. Supongamos n ∈ Z. Por el Corolario 4.6 tenemos que n es par o impar. Veamos que cada caso permite concluir que n(n + 1) es par. n par. Del Teorema 4.24 se sigue que n(n + 1) es par. n impar. Por definici´on, n = 2k + 1 para alg´un k ∈ Z. Luego, n + 1 = 2k + 1 + 1 = 2k + 2 = 2(k + 1), es decir, n + 1 es multiplo de dos, o sea, par. Por lo tanto, del Teorema 4.24 conclu´ımos que n(n + 1) es par. Por disyunci´on de casos, conclu´ımos que n(n + 1) es par.

4.5. Pruebas de doble implicaci´on En este segmento no introducimos un m´etodo de demostraci´on sino una pauta para probar afirmaciones de la forma P ⇔ Q. Sabemos que e´ sta equivale a (P ⇒ Q) ∧ (Q ⇒ P ) por lo cual, para probar la equivalencia, basta demostrar las dos implicaciones P ⇒ Q y Q ⇒ P . Cada implicaci´on puede probarse con los m´etodos de demostraci´on introducidos anteriormente. Teorema 4.26. Sean a, b, c ∈ Z tal que c 6= 0. Entonces b | a si y solo si bc | ac. Demostraci´on. Se nos pide demostrar (b | a) ⇔ (bc | ac). Procedamos a probar cada implicaci´on por m´etodo directo (recuerde que c 6= 0). 24

“ ⇒ ” Supongamos b | a. Por definici´on, a = bk para alg´un k ∈ Z. Luego, al multiplicar en la igualdad por c, ac = (bc)k, es decir, ∃k∈Z (ac = (bc)k). Por lo tanto, bc divide a ac. “⇐” Supongamos bc | ac, es decir, ac = (bc)t para alg´un entero t. La igualdad la podemos expresar como ac = btc y, como c 6= 0, al cancelarlo de la igualdad se sigue a = bt, es decir, a es m´ultiplo de b. Teorema 4.27. Sean a, b ∈ Z. ab es impar si y solo si a es impar y b es impar. Demostraci´on. “ ⇒ ” Es el contrarrec´ıproco del Teorema 4.24. “⇐” Del Teorema 4.12. La siguiente es una de las nociones m´as importantes de la aritm´etica. Definici´on 4.28 (N´umero primo). Sea n un entero mayor que 1. Decimo que n es primo si sus u´ nicos divisores son 1 y n. De lo contrario, n es compuesto. Por ejemplo, 2,3,5,11,41 son primos, 4,6,48 son compuestos y 1 no es primo ni compuesto, pues la definici´on se restringe a los enteros mayores que 1. Una forma de clasificar los n´umeros compuestos la da el siguiente resultado. Teorema 4.29. Sea n un entero mayor que 1. Entonces n es compuesto si y solo si n = ab para algunos enteros a y b mayores que 1. Demostraci´on. “ ⇒ ” Supongamos que n es compuesto, es decir, que no es primo. Luego, existe un entero a > 0 que divide a n y que no es 1 ni n. Como a | n se sigue que existe b ∈ Z tal que n = ab. Como n y a son positivos, es claro que b debe ser positivo y, como a 6= 1 entonces a > 1. Falta probar que b > 1. Por reducci´on al absurdo, supongamos que b ≯ 1, es decir, b = 1. Como n = ab se sigue que n = a, lo cual contradice que a no es n. “⇐” Supongamos que existen enteros a y b mayores que 1 tal que n = ab. Primero veamos que a 6= n por reducci´on al absurdo. En efecto, si a = n entonces n = nb y, como n es mayor que 1, se sigue que 1 = b, lo cual es absurdo (pues b > 1). Por lo tanto, a 6= n. Por otra parte, como n = ab, se tiene que a | n y a no es 1 (porque es mayor) ni n. Por lo tanto, n tiene un divisor diferente de 1 y n, es decir, es compuesto.

4.6. Inducci´on Matem´atica La inducci´on matem´atica es una t´ecnica poderosa para probar propiedades sobre los n´umeros naturales. Proposici´on 4.30 (Principio de Inducci´on Matem´atica). Sea Q(n) una afirmaci´on. Si se tiene (i) (Paso base) Q(1) (1 cumple la afirmaci´on), (ii) (Paso inductivo) Q(n) ⇒ Q(n + 1) para cualquier n ∈ N (si n cumple la afirmaci´on, entonces n + 1 tambi´en la cumple) se concluye que ∀n∈N Q(n), es decir, que Q(n) es cierta para todos los naturales.

25

Justificaci´on (no formal). Supongamos que se cumple (i) y (ii). Veamos que, dado n ∈ N, Q(n) es cierta. Como (ii) muestra una implicaci´on que se cumple para todos los n´umeros naturales, las siguientes implicaciones son ciertas Q(1) ⇒ Q(2), Q(2) ⇒ Q(3), Q(3) ⇒ Q(4), . . . , Q(n − 2) ⇒ Q(n − 1), Q(n − 1) ⇒ Q(n) luego, por la transitividad de ⇒ , se sigue Q(1) ⇒ Q(n). Por (i) y modus ponens, Q(n) es cierta. El siguiente resultado contiene una prueba por inducci´on matem´atica. Lema 4.31. 2n > n para todo n ∈ N

Demostraci´on. Procedamos por inducci´on matem´atica con Q(n) : “n < 2n ”. Debemos probar Paso base. Q(1) es claro porque 1 < 2 y 21 = 2. Paso inductivo. Supongamos Q(n), es decir, n < 2n (la llamamos hip´otesis inductiva), y veamos Q(n+1), es decir, n + 1 < 2n+1 . En efecto, 2n+1 = 2n · 2 > n · 2 = n + n ≥ n + 1. El primer “mayor que” se justifica por la hip´otesis inductiva. As´ı, obtenemos n + 1 < 2n+1 . De esta forma, hemos visto que (i) y (ii) del principio de inducci´on se cumple para Q(n). Por lo tanto, conclu´ımos que Q(n), es decir, n < 2n , es cierto para todo n ∈ N. A primera vista, es tedioso realizar la suma de los n´umeros del 1 al 100. Sin embargo, hay una forma r´apida e ingeniosa de efectuarla. Primero, sumemos los n´umeros entre los primeros y los u´ ltimos, as´ı 1 + 100, 2 + 99, 3 + 98, 4 + 97 , . . . , 49 + 52, 50 + 51. Aqu´ı hay un total de 50 sumas. Pero cada una de ellas da 101. Por lo tanto, la suma de los n´umeros del 1 . Este resultado permite pensar en una conjetura para hallar una f´ormula que al 100 es 50 · 101 = 100·101 2 exprese la suma de los n´umeros desde 1 hasta n para cualquier n un n´umero natural. Teorema 4.32. Dado n ∈ N,

n(n + 1) . 2 Demostraci´on. Como es una propiedad sobre n´umeros naturales, procedemos su demostraci´on por inducci´on matem´atica. Sea n(n + 1) . Q(n) : 1 + 2 + · · · + n = 2 Paso base. Q(1) es 1 =

1(1+1) 2

1 + 2 + ··· + n =

(la suma de 1 hasta 1), lo cual es cierto.

Paso inductivo. Supongamos Q(n) (hip´otesis inductiva) y probemos Q(n + 1). Q(n + 1) expresa el resultado de sumar los n´umeros desde 1 hasta n + 1. Seg´un la hip´otesis inductiva, ya sabemos el valor al sumar hasta n, por lo cual solo falta sumar n + 1. 1 + · · · + (n + 1) = (1 + · · · + n) + (n + 1) + (n +
1) hip´otesis inductiva = n(n+1) 2 n factor com´un n + 1 = (n + 1) 2 +
1 = (n + 1) n+2 2 = (n+1)((n+1)+1) 2 lo cual permite concluir Q(n + 1). Por lo tanto, por inducci´on matem´atica, Q(n) es cierta para todo n ∈ N. 26

5. Teor´ıa de Conjuntos Intuitiva La Teor´ıa de Conjuntos es el fundamento de las matem´aticas, pues aqu´ı se describen todas las leyes que fundamentan el comportamiento de los objetos matem´aticos, adem´as de que permite construir los conjuntos num´ericos N, Z, Q y R, definir sus operaciones y probar todas sus propiedades. Todas las demostraciones que se presentan en esta teor´ıa est´an fundamentadas en el c´alculo de predicados y en 9 axiomas (afirmaciones que son el punto de partida de la teor´ıa), elementos simples desde donde se construye toda la matem´atica de una forma muy rigurosa. En cursos de L´ogica Matem´atica y Teor´ıa de Conjuntos se estudian toda la estructura que construye las matem´aticas de una forma muy rigurosa. Sin embargo, en este texto solo vamos a estudiar los principios b´asicos de la Teor´ıa de Conjuntos de una forma muy intuitiva, similar a como procedimos en la secci´on 3. Aunque en ocasiones desarrollamos pruebas formales, no haremos una exigencia total en este proceder. ´ se presenta como una El s´ımbolo principal de la teor´ıa de conjuntos es el ∈, el cual se lee pertenece. Este relaci´on binaria, en donde x ∈ y se lee “x pertenece a y”. Intuitivamente, un conjunto se ve como una colecci´on de objetos, por lo cual x ∈ y significa, intuitivamente, que x es uno de los elementos de la colecci´on de objetos llamada y. En ocasiones, x ∈ y se lee como x es elemento de y. Como notaci´on, x ∈ / y es lo mismo que ¬(x ∈ y). A continuaci´on, mencionamos los dos primeros axiomas de la teor´ıa de conjuntos. Axioma de Extensionalidad. Dos conjuntos son iguales si tienen los mismos elementos. En el lenguaje matem´atico, esto se expresa por 
 ∀A ∀B ∀x (x ∈ A ⇔ x ∈ B) ⇒ A = B . La expresi´on ∀x (x ∈ A ⇔ x ∈ B) significa que A y B tienen los mismos elementos. Axioma de Comprensi´on. Dado un conjunto A y una afirmaci´on P (x) se puede construir el conjunto cuyos elementos son los objetos en A que cumplen P (x) Estos dos axiomas sugieren las dos formas en que se pueden definir conjunto. Notaci´on por extensi´on. Consiste en definir un conjunto mediante la lista de sus elementos, coloc´andolos entre llaves10 . Por ejemplo, A = {1, 2, 3}, B = {a, b} para definir los conjuntos A y B, respectivamente. Es claro que 1 ∈ A, 4 ∈ / A, a ∈ B, c ∈ / B, 1 ∈ / B. Notaci´on por Compresi´on. Dado un conjunto A y una afirmaci´on P (x), el conjunto al que se se hace referencia en el axioma de Comprensi´on se denota por {x ∈ A / P (x)} y representa el conjunto cuyos elementos son los objetos de A que cumplen P (x). Por ejemplo, {n ∈ Z / ∃k∈Z (n = 2k)} representa el conjunto formado por los n´umeros pares, {x ∈ R / −1 < x < 3} representa el conjunto de los n´umeros reales entre −1 y 3 (el cual se denota por (−1, 3)). Ejemplo 5.1. El axioma de Extensionalidad justifica que las siguientes parejas de conjuntos son iguales, pues son conjuntos que tienen los mismos elementos, a saber, {1, 2, 3} = {3, 1, 2}, {a, b, b} = {a, b}, {1, 2, 3, 4, 5} = {n ∈ Z / 1 ≤ n ≤ 5} y {n ∈ N / n primo y par} = {2}. Aqu´ı vemos que un conjunto finito siempre puede expresarse por extensi´on y comprensi´on. Otro ejemplo es {n ∈ Z / n par} = 6 {2, 4, 6}, 10 Para definir este tipo de conjuntos finitos con llaves, se necesitan otros axiomas de la teor´ıa de conjuntos, a saber, el axioma de Pares y el axioma de Uni´on.

27

pues 8 es elemento del primer conjunto y no del segundo, dando lugar a que ambos no tienen los mismos elementos. En teor´ıa de conjuntos se puede demostrar que existe un u´ nico conjunto que no tiene elementos, es decir, ∃!y ∀x (x ∈ / y). Por ejemplo, {x ∈ A / x 6= x} es un conjunto que no tiene elementos. Definici´on 5.2 (Conjunto vac´ıo). Denotamos por ∅ al u´ nico conjunto que no tiene elementos. Es claro que los conjuntos {n ∈ Z / n 6= n}, {x ∈ R / x = x + 1} y {x ∈ R / 0 = 1} son iguales a ∅, pues ninguno de ellos posee elementos. ´ Una notaci´on muy com´un en teor´ıa de conjuntos es la representaci´on de diagramas de Venn. Esta es u´ til para conocer intuiivamente el comportamiento de los conjuntos, pero no se usa para efectuar demostraciones formales. El diagrama de Venn de un conjunto consiste en dibujar un c´ırculo que representa el conjunto y, por dentro, los elementos de e´ ste se˜nalados con puntos. Por ejemplo, el diagrama de Venn del conjunto A = {1, 2, 3} es A 1 b

b

b

2

3

´ Definici´on 5.3 (Contenci´on.). Definimos A ⊆ B como A est´a contenido en B. Esto significa que todos los elementos de A est´an en B, es decir, ∀x (x ∈ A ⇒ x ∈ B). A ⊆ B tambi´en se lee A es subconjunto deB, B contiene a A o´ B es superconjunto de A. Como notaci´on, A * B representa ¬(A ⊆ B). El siguiente diagrama de Venn representa A ⊆ B. B A

De la contenci´on se tiene la siguiente regla de inferencia: A⊆B x∈A x ∈ B. N´otese que A*B

⇔ ¬(A ⊆ B) ⇔ ¬∀x (x ∈ A ⇒ x ∈ B) ⇔ ∃x ¬(x ∈ A ⇒ x ∈ B) negaci´on de ∀ ⇔ ∃x (x ∈ A ∧ x ∈ / B) negaci´on de ⇒ .

Por lo tanto, A * B ⇔ ∃x (x ∈ A ∧ x ∈ / B), es decir, A no est´a contenido en B si y solo si existe un elemento en A que no pertenece a B. 28

Ejemplo 5.4. {0, 1} * {1, 2}, pues 0 est´a en el primer conjunto, pero no en el segundo. N ⊆ Z, pues todos los naturales son enteros. {n ∈ Z / 4 | n} ⊆ {n ∈ Z / 2 | n}, ya que todos los m´ultiplos de 4 son pares, pero {n ∈ Z / 2 | n} * {n ∈ Z / 4 | n}, pues n´umeros como 6, 10, −14 est´an en el primer conjunto pero no en el segundo. Proposici´on 5.5. Para probar A ⊆ B, basta tomar x ∈ A como hip´otesis y concluir x ∈ B Justificaci´on. Si se toma x ∈ A como hip´otesis y se concluye x ∈ B, por m´etodo directo se tiene x ∈ A ⇒ x ∈ B. Como x se toma arbitrario, significa que esta afirmaci´on se cumple para todo x, lo cual significa que A ⊆ B. La proposici´on anterior indica la t´ecnica m´as com´un para demostrar (formalmente) que un conjunto est´a contenido en otro. Teorema 5.6. Dados A, B, C conjuntos, (a) ∅ ⊆ A (el vac´ıo es subconjunto de cualquier conjunto). (b) A ⊆ A (un conjunto est´a contenido en s´ı mismo). (c) (A ⊆ B ∧ B ⊆ C) ⇒ A ⊆ C (la contenci´on de conjuntos es transitiva). B

C

A

(d) (A ⊆ B ⇒ B ⊆ A) ⇒ A = B (antisimetr´ıa de la contenci´on). Demostraci´on. Estas afirmaciones se pueden ilustrar mediante diagramas de Venn. Sin embargo, vamos a dar sus justificaciones formales. (a) Como el vac´ıo no tiene elementos, x ∈ / ∅ es teorema. Luego, por adici´on, x ∈ / ∅ ∨ x ∈ A es teorema, lo cual equivale a x ∈ ∅ ⇒ x ∈ A. Por el principio de generalizaci´on, ∀x (x ∈ ∅ ⇒ x ∈ A) es teorema, es decir, ∅ ⊆ A. (b) Es claro que x ∈ A ⇒ x ∈ A es un teorema (por la tautolog´ıa P ⇒ P ). Luego, por el principio de generalizaci´on, ∀x (x ∈ A ⇒ x ∈ A) es teorema, lo cual es A ⊆ A. (c) Supongamos A ⊆ B y B ⊆ C y probemos, por el m´etodo de la Proposici´on 5.5, que A ⊆ C. Para e´ sto, supongamos x ∈ A y veamos x ∈ C. Como A ⊆ B y x ∈ A entonces x ∈ B y, como B ⊆ C, conclu´ımos que x ∈ C. (d) Si A ⊆ B y B ⊆ A entonces x ∈ A ⇒ x ∈ B y x ∈ B ⇒ x ∈ A para todo x. Por lo tanto, x ∈ A ⇔ x ∈ B para todo x, es decir, A y B tienen los mismos elementos. Por el axioma de Extensionalidad, conclu´ımos que A = B.

El inciso (d) sugiere una estrategia para probar la igualdad de dos conjuntos, la cual se conoce por doble contenci´on: 29

Proposici´on 5.7 (Doble Contenci´on). Basta probar que A ⊆ B y B ⊆ A para garantizar que A = B.  Ejemplo 5.8. Sea A = {a ∈ Z / a par} y B = a ∈ Z / a2 par . Dado a ∈ Z se sabe que a par ⇒ a2 par, por lo cual a ∈ A ⇒ a ∈ B para todo a, es decir, A ⊆ B. Por otra parte, a2 par ⇒ a par para todo entero a, por lo cual a ∈ B ⇒ a ∈ A, es decir, B ⊆ A. Por lo tanto, como A ⊆ B y B ⊆ A, conclu´ımos que A = B. Definici´on 5.9 (Contenci´on estricta.). Definimos A ( B como A ⊆ B ∧ A 6= B. A ( B significa que A es un subconjunto de B que es diferente a B, lo cual se lee como A est´a estrictamente contenido en B o A es subconjunto propio de B. Ejemplo 5.10. {n ∈ Z / 4 | n} ( {n ∈ Z / 2 | n}, pues el primer conjunto se contiene en el otro y no son iguales, ya que no comparten los mismos elementos. Es evidente {1, 2} ( {1, 2, 3}. A ( A es falso, pues son conjuntos iguales. {a, b} ( {b, c} es falso, pues ni siquiera se cumple la contenci´on. Definici´on 5.11 (Operaciones entre conjuntos). Dados dos conjuntos A y B definimos los siguientes conjuntos.11 A ∪ B = {x / x ∈ A ∨ x ∈ B} Uni´on de A con B. A ∩ B = {x / x ∈ A ∧ x ∈ B} Intersecci´on de A con B. A − B = {x / x ∈ A ∧ x ∈ / B} Complemento de B respecto a A. En cada diagrama de Venn, cada conjunto est´a representado por el a´ rea sombreada.

A

A∪B

B

A

A∩B

B

A

A−B

B

Al observar estos diagramas de Venn, A ⊆ A ∪ B, B ⊆ A ∪ B, A ∩ B ⊆ A, A ∩ B ⊆ B y A − B ⊆ A (lo cual se puede demostrar formalmente). Seg´un la definici´on de e´ stas operaciones, se siguen las siguientes equivalencias: x∈A∪B ⇔x∈A∨x∈B x∈A∩B ⇔x∈A∧x∈B x∈A−B ⇔x∈A∧x∈ / B. Tambi´en podemos ver qu´e significan afirmaciones como x ∈ / A ∪ B seg´un las equivalencias anteriores. Por ejemplo, x∈ / A ∪ B ⇔ ¬(x ∈ A ∪ B) notaci´on ⇔ ¬(x ∈ A ∨ x ∈ B) definici´on de uni´on ⇔ (x ∈ / A∧x∈ / B) ley D’Morgan. Se puede garantizar que x∈ / A∪B x∈ / A∩B x∈ / A−B

⇔x∈ / A∧x∈ /B ⇔x∈ / A∨x∈ /B ⇔x∈ / A ∨ x ∈ B.

Cuando A ∩ B = ∅ decimos que A y B son disjuntos, pues esto significa que no tienen elementos en com´un. 11 La intersecci´on y el complemento se pueden definir gracias al axioma de Comprensi´on. Sin embargo, para definir la uni´on se necesita otro axioma que se conoce como el axioma de Uni´on.

30

A∩B =∅

A

B

De los diagramas de Venn se infiere que A ∩ (B − A) = ∅, pues A y B − A no tienen elementos en com´un. Ejemplo 5.12. Sean P = {n ∈ Z / n par} y I = {n ∈ Z / n impar}. Tenemos que P ∪ I = Z, P ∩ I = ∅, Z − P = I y Z − I = P . Aqu´ı P y I son disjuntos, pues no existen enteros que sean pares e impares a la vez. Lema 5.13. Si A ⊆ B entonces A ∪ B = B y A ∩ B = B. A∪B =B

A∩B =A

B

A

B

A

Demostraci´on. Aunque los diagramas de Venn proporcionan una evidencia intuitiva de estas igualdades, tambi´en se pueden demostrar de manera formal. Procedamos, por ejemplo, con A ∪ B = B por doble contenci´on. B ⊆ A ∪ B se sigue porque x ∈ B ⇒ (x ∈ A ∨ x ∈ B) (adici´on) lo cual es, por definici´on de uni´on, x ∈ B ⇒ x ∈ A ∪ B que se cumple para todo x. Falta probar entonces que A ∪ B ⊆ B. En efecto, si x ∈ A ∪ B, por definici´on de uni´on x ∈ A o´ x ∈ B. Procedemos por disyunci´on de casos: x ∈ A. Como A ⊆ B se sigue x ∈ B. x ∈ B. En este caso es claro que x ∈ B. Conclu´ımos que x ∈ B. Teorema 5.14. (a) A ∪ A = A, A ∩ A = A. (b) A − A = ∅, A ∪ ∅ = A, A ∩ ∅ = ∅, A − ∅ = A, ∅ − A = A. (c) A ∪ B = B ∪ A, A ∩ B = B ∩ A (Leyes conmutativas). (d) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C (Leyes asociativas). (e) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (Leyes distributivas). (f) C − (A ∩ B) = (C − A) ∪ (C − B), C − (A ∪ B) = (C − A) ∩ (C − B) (Leyes D’Morgan). (g) A − B = A − (A ∩ B). Demostraci´on (no del todo formal). De manera no formal, estas igualdades se pueden justificar mediante diagramas de Venn. Ilustramos c´omo funciona este tipo de argumento en cada caso, adem´as que, en algunos, haremos la demostraci´on formal. 31

(a) Como A ⊆ A, del Lema 5.13 se sigue que A ∪ A = A y A ∩ A = A. (b) Como ∅ ⊆ A entonces A ∪ ∅ = A y A ∩ ∅ = ∅ por el Lema 5.13. Por otra parte, x ∈ / A ∨ x ∈ A es cierta (por tercer exclu´ıdo), lo cual es x ∈ / A − A (ver Definici´on 5.11). Como esto se cumple para todo x, significa que A − A no tiene elementos, lo cual dice que A − A = ∅. Como ∅ − A ⊆ ∅ (ver Definici´on 5.11) y ∅ ⊆ ∅ − A (el vac´ıo est´a contenido en cualquier conjunto, ver Teorema 5.6), por doble contenci´on se sigue la igualdad. Finalmente, veamos que A − ∅ = A por doble contenci´on. Es claro que A − ∅ ⊆ A, as´ı que falta ver A ⊆ A − ∅. En efecto, si x ∈ A, como x ∈ / ∅ es verdad, entonces x ∈ A ∧ x ∈ / ∅, es decir, x ∈ A − ∅ (por definici´on de resta). (c) Mediante un diagrama de Venn es f´acil verificar dichas A ∩ B de manera formal. x∈A∩B ⇔x∈A∧x∈B ⇔x∈B∧x∈A ⇔x∈B∩A

igualdades, pero veamos la conmutatividad de Def. de ∩ Conmutatividad de Def. de ∩.

∧

Por lo tanto, x ∈ A∩B ⇔ x ∈ B ∩A para todo x, de donde, por axioma de Extensionalidad, conclu´ımos que A ∩ B = B ∩ A.

(d) Los siguientes diagramas de Venn ilustran dichas igualdades. A ∪ (B ∪ C) = (A ∪ B) ∪ C A

A ∩ (B ∩ C) = (A ∩ B) ∩ C

B

De manera formal: x ∈ A ∪ (B ∪ C)

A

⇔x∈A∨x∈B∪C ⇔ x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇔ (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇔x∈A∪B ∨x∈C ⇔ x ∈ (A ∪ B) ∪ C

B

def. de ∪ def. de ∪ asociatividad de def. de ∪ def. de ∪.

∨

Por lo tanto, x ∈ A ∪ (B ∪ C) ⇔ x ∈ (A ∪ B) ∪ C para todo x, de donde se concluye que A ∪ (B ∪ C) = (A ∪ B) ∪ C por el Axioma de Extensionalidad. (e) El a´ rea sombreada de los diagramas de Venn a la derecha evidencia que A∩(B∪C) = (A∩B)∪(A∩C). A A

B

A

A ∩ (B ∪ C)

B∪C

C

B

C

32

A

B

C

A

A∩B

B

A

(A ∩ B) ∪ (A ∩ C)

A∩C

C

B

A

B

C

C

El a´ rea sombreada de los diagramas de Venn a la derecha evidencia que A∪(B∩C) = (A∪B)∩(A∪C). A A

B

A

C

A

A∪B

A ∪ (B ∩ C)

B∩C

B

A

C

C

B

A

(A ∪ B) ∩ (A ∪ C)

A∪C

C

B

B

A

C

B

C

Veamos la primera situaci´on de manera formal: x ∈ A ∩ (B ∪ C)

⇔x∈ A∧x∈ B∪C ⇔ x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇔ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇔x∈ A∩B ∨x ∈A∩C ⇔ x ∈ (A ∩ B) ∪ (A ∩ C)

def. de ∩ def. de ∪ distributividad def. de ∩ def. de ∪.

Como dicha equivalencia se cumple para todo x, por el axioma de Extensionalidad se sigue A∩(B∪C) = (A ∩ B) ∪ (A ∩ C). (f) El a´ rea sombreada de los diagramas de Venn a la derecha evidencia que C−(A∩B) = (C−A)∪(C−B).

33

C A

B

A

C

A

C −A

C − (A ∩ B)

A∩B

B

A

B

C

B

A

(C − A) ∪ (C − B)

C−B

C

C

B

A

B

C

C

El a´ rea sombreada de los diagramas de Venn a la derecha evidencia que C−(A∪B) = (C−A)∩(C−B). C A

B

A

C

A

C −A

C − (A ∪ B)

A∪B

B

A

C

B

A

C

(C − A) ∩ (C − B)

C−B

C

B

B

A

C

B

C

Veamos la primera situaci´on de manera formal: x ∈ C − (A ∩ B)

⇔x∈C∧x∈ / A∩B ⇔ x ∈ C ∧ ¬(x ∈ A ∩ B) ⇔ x ∈ C ∧ ¬(x ∈ A ∧ x ∈ B) ⇔ x ∈ C ∧ (x ∈ / A∨x∈ / B) ⇔ (x ∈ C ∧ x ∈ / A) ∨ (x ∈ C ∧ x ∈ / B) ⇔x∈ C −A∨x∈ C −B ⇔ x ∈ (C − A) ∪ (C − B) 34

def. de − notaci´on def. de ∩ ley D’Morgan distributividad def. de − def. de ∪.

De la equivalencia y el axioma de Extensionalidad se sigue la igualdad. (g) Los siguientes diagramas de Venn ilustran la situaci´on de la afirmaci´on. A A

B

A

A − (A ∩ B) = A − B

A∩B

B

A

B

Tambi´en damos el siguiente argumento formal: A − (A ∩ B) = (A − A) ∪ (A − B) = ∅ ∪ (A − B) = (A − B) ∪ ∅ =A−B

por (f) por (b) por (c) por (b).

Ejemplo 5.15. Los resultados anteriores se pueden utilizar para demostrar afirmaciones sobre conjuntos. Por ejemplo, A ∩ (A ∪ B) = (A ∩ A) ∪ (A ∩ B) ley distributiva = A ∪ (A ∩ B) ya que A ∩ A = A,

lo cual garantiza que A ∩ (A ∪ B) = A ∪ (A ∩ B). Por otra parte, sabemos que A ∩ B ⊆ A por lo cual, del Lema 5.13, A ∪ (A ∩ B) = A. As´ı, podemos concluir que A ∩ (A ∪ B) = A ∪ (A ∩ B) = A. Cuando los conjuntos en los que se trabajan est´an contenidos en un espacio espec´ıfico (como R o´ Z), es muy com´un adoptar la siguiente notaci´on. Definici´on 5.16 (Complemento relativo). Supongamos que se est´a trabajando en un conjunto U . Si A ⊆ U , denotamos A′ = U − A, el cual llamamos el complemento de A (respecto a U ). En el siguiente diagrama de Venn, el a´ rea sombreada representa A′ . U A

A′

Ejemplo 5.17. Llamemos P = {n ∈ Z / n par} I = {n ∈ Z / n impar} C = {n ∈ N / n compuesto}

Respecto a Z, P ′ = I, I ′ = P y C ′ = {n ∈ Z / n ≤ 1} ∪ {n ∈ N / n primo}. Por otra parte, respecto a N se tiene que C ′ = {1} ∪ {n ∈ N / n primo}. Notese que C ′ no denota el mismo conjunto, sino que depende del conjunto base respecto al cual se le tome el complemento. Respecto a R, si A = {x ∈ R / 0 < x < 1}, entonces A′ = {x ∈ R / x ≥ 1} ∪ {x ∈ R / x ≤ 0}. 35

Teorema 5.18. Sean A y B subconjuntos de U . Tomando los complementos respecto a U se tienen las siguientes propiedades. (a) A ∪ B, A ∩ B, A − B y A′ son subconjuntos de U . (b) ∅′ = U , U ′ = ∅. (c) (A′ )′ = A. (d) (A ∪ B)′ = A′ ∩ B ′ . (e) (A ∩ B)′ = A′ ∪ B ′ . Demostraci´on (no del todo formal). En algunos casos justificaremos enunciados con diagramas de Venn, en otros, formalmente. (a) El siguiente diagrama de Venn ilustra claramente la situaci´on. U A

B

De manera formal, como A ∩ B y A − B son subconjuntos de A entonces, como A ⊆ U , se sigue por transitividad de ⊆ que A ∩ B y A − B son subconjuntos de U . Por otra parte, A′ = U − A ⊆ U . (b) ∅′ = U − ∅ = U y U ′ = U − U = ∅ por el Teorema 5.14. (c) Un diagrama de Venn hace obvio este resultado, pero veamos una prueba formal. (A′ )′ = U − A′ = U − (U − A) = (U − U ) ∪ (U ∩ A) = ∅ ∪ (U ∩ A) =U ∩A =A

def. de ′ def. de ′ igualdad C − (A − B) = (C − A) ∪ (C ∩ B) (ver taller) Teorema 5.14 Teorema 5.14 pues A ⊆ U y Lema 5.13.

(d) De manera formal: (A ∪ B)′ = U − (A ∪ B) def. de ′ = (U − A) ∩ (U − B) D’Morgan = A′ ∩ B ′ def. de ′ (e) De manera formal: (A ∩ B)′ = U − (A ∩ B) def. de ′ = (U − A) ∪ (U − B) D’Morgan = A′ ∪ B ′ def. de ′

36

Observaci´on 5.19. En teor´ıa de conjuntos no hay distinci´on entre conjuntos y elementos, es decir, todos los objetos son conjuntos. Incluso cada n´umero real es un conjunto, pues son objetos de la teor´ıa. Por ello no hay nada de raro decir que un conjunto pertence a otro conjunto, por ejemplo ∅ ∈ {∅} y {∅} ∈ {{∅}}. La palabra elemento s´olo se utiliza de forma relativa para indicar que un conjunto pertenece a (o es elemento de) otro conjunto. Definici´on 5.20 (Conjunto de Partes). Dado un conjunto A definimos P(A) = {X / X ⊆ A}, el cual ´ llamamos partes12 de A. Este es el conjunto formado por todos los subconjuntos de A. Esta definici´on genera la siguiente equivalencia X ∈ P(A) ⇔ X ⊆ A. Ejemplo 5.21. ∅ es el u´ nico conjunto que no tiene elementos, por lo cual s´olo tiene un subconjunto, a saber, el mismo ∅. Por lo tanto, P(∅) = {∅}. {a} solo tiene dos tipos de subconjuntos, de cero elementos que solo es ∅ y de un elemento que solo es {a}. Por lo tanto, P({a}) = {∅, {a}}. {a, b} tiene tres tipos de subconjuntos, de cero elementos que solo es ∅, de un elemento que son {a} y {b}, y de dos elementos que solo es {a, b}. Por lo tanto, P({a, b} = {∅, {a}, {b}, {a, b}}. {a, b, c} tiene cuatro tipos de subconjuntos, de cero elementos que solo es ∅, de un elemento que son {a}, {b} y {c}, de dos elementos que son {a, b}, {a, c} y {b, c}, y de tres elementos que solo es {a, b, c}. Por lo tanto, P({a, b, c} = {∅, {a}, {b}, {c}, {a, b}, {a, c}.{b, c}, {a, b, c}}. En estos ejemplos podemos determinar una relaci´on entre un conjunto y sus partes: si el conjunto tiene 0 elementos, sus partes tiene 1; si el conjunto tiene 1 elemento, sus partes tiene 2; si el conjunto tiene 2 elementos, sus partes tiene 4 y, si el conjunto tiene 3 elementos, sus partes tiene 8. Esto permite conjeturar que si un conjunto tiene n elementos, sus partes tiene 2n , hecho el cual puede probarse en la teor´ıa de conjuntos.

12

Para definir este conjunto se necesita un axioma llamado axioma de Partes.

37