NOTAS DE TRABAJO, 29 ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

Pascual Jara Mart´ınez

´ Departamento de Algebra. Universidad de Granada Granada, 2008–2009

Primera redacci´on: Octubre 2008.

Introducci´ on Escribir un texto para la Introducci´on.

´Indice general Introducci´ on I

Conjuntos, aplicaciones y relaciones 1 Introducci´on intuitiva a la teor´ıa de conjuntos . ´ 2 Algebra de proposiciones . . . . . . . . . . . . . 3 Aplicaciones . . . . . . . . . . . . . . . . . . . . 4 Relaciones de equivalencia y de orden . . . . . 5 Cuantificadores . . . . . . . . . . . . . . . . . . 6 M´etodos de demostraci´on . . . . . . . . . . . . 7 Ejercicios . . . . . . . . . . . . . . . . . . . . . .

I

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

1 3 11 18 25 29 32 35

Bibliograf´ıa

51

´Indice alfab´etico

53

Cap´ıtulo I Conjuntos, aplicaciones y relaciones 1 2 3 4 5 6 7

Introducci´on intuitiva a la teor´ıa de conjuntos ´ Algebra de proposiciones . . . . . . . . . . . . Aplicaciones . . . . . . . . . . . . . . . . . . . . Relaciones de equivalencia y de orden . . . . . Cuantificadores . . . . . . . . . . . . . . . . . . M´etodos de demostraci´on . . . . . . . . . . . . Ejercicios . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

3 11 18 25 29 32 35

Introducci´ on Vamos a comenzar por una introducci´on intuitiva al concepto que es la base del curso: el de conjunto . Hemos preferido hacer esto as´ı ya que una introducci´on rigurosa del concepto conjunto exigir´ıa demasiado esfuerzo a un posible lector, y lo apartar´ıa de los objetivos centrales de este curso que son la introducci´on a las t´ecnicas del trabajo matem´atico, y por que deseamos fijar las notaciones y el lenguaje que vamos a emplear a lo largo del curso. Para poder comprender en su totalidad el concepto de conjunto y el a´ lgebra de subconjuntos ˜ introducci´on al a´ lgebra de proposiciones, de esta forma ya es necesario hacer una pequena tendremos dos ejemplos de a´ lgebras de Boole. El concepto de conjunto se complementa con el de funci´on o aplicaci´on entre conjuntos, veremos la definici´on y algunas de sus propiedades. Otro concepto de inter´es es el de relaci´on. Aqu´ı vamos a estudiar relaciones de equivalencia y de orden, aunque las segundas las estudiaremos en profundidad en un curso posterior.

2

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

Acabamos el capitulo con una introducci´on a los cuantificadores y el a´ lgebra de predicados y con algunos ejemplos como hacer una demostraci´on. Me gustar´ıa volver a insistir que la aproximaci´on los conceptos aqu´ı tratados no es una aproximaci´on axiom´atica sino intuitiva. Para una introducci´on a la teor´ıa de conjuntos amena, y a la vez rigurosa, recomendamos el siguiente texto: [5].

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ N INTUITIVA A LA TEOR´I A DE CONJUNTOS S EC . 1. I NTRODUCCI O

1. 1.1.

3

Introducci´ on intuitiva a la teor´ıa de conjuntos Conjuntos

Vamos a considerar un conjunto X como una colecci´on de elementos. Los elementos de un conjunto son distintos dos a dos, esto es, cualesquiera dos elementos de un conjunto o son ´ orden o relaci´on entre ellos. el mismo elemento o son elementos distintos, y no hay ningun Los conjuntos pueden ser definidos de dos formas distintas: (-) por extensi´ on, esto es, haciendo una lista de todos sus elementos, o (-) por comprensi´ on, esto es, mediante una propiedad que caracteriza a sus elementos. Ejemplo. 1.1. (Definici´ on por extensi´ on) Un ejemplo de un conjunto definido por extensi´on es: A = {1, 2, a, b, c}. ´ lo dicho antes, observar que {1, 2, a, a} no es un conjunto ya que en e´ l aparecen dos Segun elementos repetidos, esto es, un mismo elemento aparece dos veces.

Ejemplo. 1.2. (Definici´ on por comprensi´ on) Un ejemplo de un conjunto definido por comprensi´on es: ´ P = {x | x es un numero natural par}. Si un elemento x pertenece a un conjunto X , escribimos x ∈ X, y si no pertenece, escribimos x∈ / X. Ejemplo. 1.3. En los ejemplos anteriores tenemos que 1 ∈ A = {1, 2, a, b, c} y ´ 1∈ / P = {x | x es un numero natural par}.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

4

1.2.

Paradojas

Con estos conceptos que hemos introducido podemos mostrar que hacer una teor´ıa que sea libre de paradojas es una tarea dif´ıcil y exige profundizar m´as en algunos conceptos matem´aticos, pero este no es el momento ni el lugar. El lector puede al final del curso abordar la lectura de textos m´as estructurados sobre Teor´ıa de Conjuntos. El definir un conjunto por comprensi´on, esto es, atendiendo a las propiedades que cumplen sus elementos nos conduce a la siguiente definici´on: Llamamos X al conjunto de todos los conjuntos. Es claro que se tiene X ∈ X . En un principio esta definici´on es correcta, y S es un conjunto m´as entre los muchos que podemos manejar. En la misma forma podemos definir un nuevo conjunto R mediante: R = {x | x es un conjunto y x ∈ / x}. Nos planteamos ahora la siguiente pregunta: ¿pertenece R al conjunto R? Si la respuesta es si, entonces R verifica la propiedad que define R, y por tanto R ∈ / R, y si la respuesta es no, entonces R no verifica la propiedad que define a R, y por tanto R ∈ R, ya que estamos suponiendo que dados un conjunto cualquiera C y un objeto cualquiera x, siempre se tiene x ∈ C ox ∈ / C. Tenemos pues una contradicci´on, pero nuestra teor´ıa debe estar exenta de contradicciones, por lo tanto para establecer una teor´ıa buena deber´ıamos afinar m´as a la hora de definir qu´e es un conjunto. Como esta es una introducci´on intuitiva al tema, nos vamos a conformar con el hecho de que los conjuntos que vamos a manejar no son del tipo de los aqu´ı mencionado y que por lo tanto est´an libres de problemas, son conjuntos “buenos”. El conjunto R antes mencionado se debe a un matem´atico ingl´es Bertrand Russell, y puede ser utilizado para establecer la c´elebre paradoja del barbero. En el reino de E. el consejo de ministro aprob´o un Real Decreto por el que se regulaba la profesi´on de barbero, pudiendo e´ stos afeitar s´olo a aquellos que no se afeitasen a s´ı mismos. En el pueblo P., aislado en ˜ ´ las montanas, vive Bernardo, que a la postre es el unico barbero del pueblo. La pregunta es ¿quien afeita a Bernardo?

1.3.

Subconjuntos

Dado un conjunto X , un subconjunto de X es un conjunto Y verificando que para cada elemento y ∈ Y se tiene y ∈ X . Escribimos entonces Y ⊆ X. Dos subconjuntos X1 y X2 de un conjunto X son iguales si X1 ⊆ X2 y X2 ⊆ X1 , y escribimos X1 = X2 . 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ N INTUITIVA A LA TEOR´I A DE CONJUNTOS S EC . 1. I NTRODUCCI O

5

Si dos subconjuntos X1 y X2 de un conjunto X no son iguales, entonces decimos que son distintos, y escribimos X1 6= X2 . Si X1 es un subconjunto de X y X1 6= X , podemos escribir X1 ⊂ X o´ X1 $ X, y decimos que X1 es un subconjunto propio de X . Ejemplo. 1.4. (1) Cada conjunto es un subconjunto de s´ı mismo. Esto es, para cada conjunto X se tiene X ⊆ X ; llamamos a X el subconjunto impropio de X . (2) El conjunto B = {1, 2} es un subconjunto de A = {1, 2, a, b, c}. Esto se representa por B ⊆ A. En cambio el conjunto C = {1, 2, 3} no es un subconjunto de A. Esto se representa por C * A. (3) El conjunto B0 = {2, 1} es igual al conjunto B; esto es, {1, 2} = {2, 1}. Si Y es un subconjunto de un conjunto X , a veces los representamos mediante un diagrama de Venn, esto es, el conjunto X se representa por el interior del cuadrado y el conjunto Y por el interior de la l´ınea curva.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

6

1.4.

Operaciones con subconjuntos

Si X1 y X2 son dos subconjuntos de un conjunto X , podemos definir su uni´ on como el subconjunto de X definido por: X1 ∪ X2 = {x ∈ X | x ∈ X1 o´ x ∈ X2 },

y su intersecci´ on como el subconjunto de X definido por: X1 ∩ X2 = {x ∈ X | x ∈ X1 y x ∈ X2 },

Ejemplo. 1.5. (1) Sea D = {1, a}. Como B = {1, 2} y D son subconjuntos del conjunto A = {1, 2, a, b, c}, entonces podemos calcular su uni´on y su intersecci´on. Se verifica: B ∪ D = {1, 2, a}

19 de octubre de 2008

y

B ∩ D = {1}.

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ N INTUITIVA A LA TEOR´I A DE CONJUNTOS S EC . 1. I NTRODUCCI O

7

(2) Tambi´en B = {1, 2} y B0 = {2, 1} son subconjuntos del conjunto A; en este caso tenemos B ∪ B0 = B = B0 y B ∩ B0 = B = B0 . ´ elemento. Existe un conjunto especial que est´a definido por la propiedad de no tener ningun Este conjunto se llama vac´ıo y se representa por el s´ımbolo ∅. ´ ´ elemento, si represenCada conjunto X tiene un unico subconjunto que no tiene ningun tamos por ∅ a este subconjunto, entonces ∅ es un subconjunto de X . El subconjunto ∅ se llama subconjunto vac´ıo o trivial de X . Si la intersecci´on de dos subconjuntos X1 y X2 de un conjunto X es igual a ∅, decimos que son subconjuntos disjuntos.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

8

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

Sea Y un subconjunto de un conjunto X , llamamos subconjunto complemento de Y en X al siguiente subconjunto de X : Y = X \ Y = {x ∈ X | x ∈ / Y }.

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ N INTUITIVA A LA TEOR´I A DE CONJUNTOS S EC . 1. I NTRODUCCI O

9

Ejemplo. 1.6. El complemento de B = {1, 2} en A = {1, 2, a, b, c} es: B = {a, b, c} Observaci´ on. 1.7. Observar que para cada subconjunto Y de un conjunto X , los subconjuntos Y y Y son siempre disjuntos. Ejercicio. 1.8. Sea X un conjunto e Y un subconjunto de X . Probar que Y = Y . ´ . Tenemos que probar que Y ⊆ Y y que Y ⊆ Y . Para esto ultimo ´ cojamos un S OLUCI ON elemento y ∈ Y , entonces y ∈ X y adem´as y ∈ / Y , luego y ∈ Y . Rec´ıprocamente, si y ∈ Y , entonces por definici´on y ∈ X y adem´as y ∈ / Y , luego y ∈ Y .



Dado un conjunto X existe un conjunto cuyos elementos son todos los subconjuntos de X . Este conjunto lo llamamos conjunto de las partes o´ conjunto potencia de X y lo representamos por P(X ). Ejemplo. 1.9. (1) El conjunto de las partes del conjunto A = {1, 2, a, b, c} es: P(A) = { ∅, {1}, {2}, {a}, {b}, {c}, {1, 2}, {1, a}, {1, b}, {1, c}, {2, a}, {2, b}, {2, c}, {a, b}, {a, c}, {b, c}, {1, 2, a}, {1, 2, b}, {1, 2, c}, {1, a, b}, {1, a, c}, {1, b, c}, {2, a, b}, {2, a, c}, {2, b, c}, {a, b, c}, {1, 2, a, b}, {1, 2, a, c}, {1, 2, b, c}, {1, a, b, c}, {2, a, b, c}, {1, 2, a, b, c}}. (2) El conjunto de las partes del conjunto D = {u, v, w} es: P(D) = { ∅, {u}, {v}, {w}, {u, v}, {u, w}, {v, w}, {v, w}, {u, v, w}}. (3) El conjunto de las partes del conjunto ∅ es: P(∅) = {∅}. Observar que P(∅) es un conjunto con un elemento. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

10

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

(4) El conjunto de las partes del conjunto {∅} es: P({∅}) = {∅, {∅}}. ´ En lo que sigue vamos a usar, casi exclusivamente, conjuntos que tienen un numero finito de elementos, a estos conjuntos los llamaremos conjuntos finitos, y a los que no tienen un ´ numero finito de elementos los llamaremos conjuntos infinitos. Ejemplo. 1.10. (1) El conjunto A = {1, 2, a, b, c} es un conjunto finito. ´ (2) El conjunto R de los numeros reales es un conjunto infinito. ´ Cuando X es un conjunto finito el numero de sus elementos lo llamamos su cardinal. Tambi´en se define el cardinal de conjuntos infinitos, pero no vamos a tratar este problema aqu´ı. Ejercicio. 1.11. Si X es un conjunto con n elementos, probar que el conjunto P(X ) tiene 2n elementos. ´ . Subconjunto de X con 0 elementos hay exactamente uno. Subconjunto de X con S OLUCI ON ´ un elemento hay exactamente n, de elementos de X . Subconjuntos de X con dos
el numero ´ elementos hay n(n − 1)/2 = n2 . En general si t ≤ n, el numero de subconjuntos de X con t t
elementos es n . Luego en total tenemos           n n n n n + + + ··· + + = (1 + 1)n = 2n . 0 1 2 n−1 n  Dados dos subconjuntos X1 y X2 de un conjunto X llamamos diferencia de X1 y X2 al subconjunto X1 \ X2 definido por: X1 \ X2 = X1 ∩ X2 . Observar que en general se tiene X1 \ X2 6= X2 \ X1 .

Antes de abordar el problema de estudiar las propiedades que verifican la uni´on, intersecci´on y complemento, vamos a estudiar c´omo trabajar con afirmaciones o proposiciones. La raz´on es la siguiente: si X1 , X2 y X3 son tres subconjuntos de un conjunto X , ¿Qu´e relaci´on existe entre (X1 ∩ X2 ) ∪ X3 y (X1 ∪ X3 ) ∩ (X2 ∪ X3 )? 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ LGEBRA DE PROPOSICIONES S EC . 2. A

11

Para establecer la relaci´on existente entre ambos tenemos que analizar las expresiones que nos definen estos subconjuntos {x ∈ X1 y x ∈ X2 } o´ x ∈ X3 y {x ∈ X1 o´ x ∈ X3 } y {x ∈ X2 o´ x ∈ X3 }.

´ 2. Algebra de proposiciones Una proposici´ on es una afirmaci´on. Por lo tanto las proposiciones pueden tomar dos valores: V, verdadero o, F, falso. ´ Vamos a representar las proposiciones por letras mayusculas en negrita A. Ejemplo. 2.1. (1) “Hoy es lunes”, es un ejemplo de una proposici´on. (2) “El hambre en el mundo se puede erradicar”, es un ejemplo de una proposici´on. (3) “Para sacar dinero del cajero primero tienes que introducir la tarjeta”, no es una proposici´on. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

12

Si A y B son dos proposiciones, definimos nuevas proposiciones, a las que llamaremos proposiciones compuestas, mediante las siguientes construcciones: A ∧ B, que se lee “A y B”, y su definici´on est´a dada por la tabla siguiente. A∧B V F F F

A V F V F

A∧B

B V V F F

A ∨ B, que se lee “A o´ B”, y su definici´on est´a dada por la tabla siguiente. A∨B V V V F

A V F V F

A∨B

B V V F F

¬A, que se lee “no A”, y su definici´on est´a dada por la tabla siguiente A V F

¬A

¬A F V

Ejemplo. 2.2. (1) “Hoy no es lunes”ser´ıa la negaci´on de “Hoy es jueves”. (2) “El coche es rojo” o “La libreta es amarilla” ser´ıa la proposici´on “El coche es rojo o la libreta es amarilla”. (3) “El coche es m´ıo” y “yo no tengo una bicicleta” ser´ıa la proposici´on “El coche es m´ıo y yo no tengo una bicicleta”. (4) Podemos negar una proposici´on compuesta, por ejemplo la negaci´on de “El coche es m´ıo y yo no tengo una bicicleta” ser´ıa: “El coche no es m´ıo o yo tengo una bicicleta”. Dos proposiciones A y B son equivalentes si A es verdadera cuando B lo es y B es verdadera cuando A lo es. Dadas dos proposiciones definimos una nueva proposici´on mediante

A ⇐⇒ B

19 de octubre de 2008

A V F V F

A ⇐⇒ B V F F V

B V V F F

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ LGEBRA DE PROPOSICIONES S EC . 2. A

13

Entonces A y B son proposiciones equivalentes si la proposici´on A ⇐⇒ B toma solo el valor V. Ejemplo. 2.3. Las proposiciones A ∨ B y B ∨ A son proposiciones equivalentes para cualesquiera proposiciones A y B. A A V F V F

A∨B ∨ V V V F

(A ∨ B) ⇐⇒ (B ∨ A) ⇐⇒ V V V V

B B V V F F

B B V V F F

B∨A ∨ V V V F

A A V F V F

Lo mismo ocurre con las proposiciones A ∧ B y B ∧ A Ejercicio. 2.4. Probar que A ∧ B y B ∧ A son proposiciones equivalentes para cualesquiera proposiciones A y B. Una proposici´on que toma siempre el valor V se llama una tautolog´ıa. Ejercicio. 2.5. Probar que para cada proposici´on A la proposici´on A ∨ A es una tautolog´ıa.

2.1.

Aplicaciones a la teor´ıa de conjuntos

Podemos considerar ahora las propiedades elementales de las operaciones que hemos introducido entre los subconjuntos de un conjunto dado. Proposici´ on. 2.6. Sea X un conjunto y sean X1 , X2 , X3 subconjuntos de X , se verifica: X1 ∪ (X2 ∪ X3 ) X1 ∩ (X2 ∩ X3 ) X1 ∪ X2 X1 ∩ X2 X1 ∪ X1 X1 ∩ X1 X1 ∪ ∅ X1 ∩ X X1 ∩ ∅ X1 ∪ X

= = = = = = = = = =

(X1 ∪ X2 ) ∪ X3 (X1 ∩ X2 ) ∩ X3 X2 ∪ X1 X2 ∩ X1 X1 X1 X1 X1 ∅ X

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. asociativa P. conmutativa P. de idempotencia E. neutros P. absorci´ on

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

14

Otro tipo de propiedades son las siguientes: Proposici´ on. 2.7. Sea X un conjunto y sean X1 , X2 , X3 subconjuntos de X , se verifica: X1 ∪ (X2 ∩ X3 ) X1 ∩ (X2 ∪ X3 ) X1 ∪ X2 X1 ∩ X2 X1 ∪ X1 X1 ∩ X1

= = = = = =

(X1 ∪ X2 ) ∩ (X1 ∪ X3 ) (X1 ∩ X2 ) ∪ (X1 ∩ X3 ) X1 ∩ X2 X1 ∪ X2 X ∅

P. distributiva Ley de De Morgan E. complementos

Observar que en estos casos todos los conjuntos que aparecen son siempre subconjuntos de un mismo conjunto X . Para ver que estas igualdades son ciertas, esto es, que los conjuntos que en ellas aparecen son iguales, vamos a comprobar que tienen los mismos elementos. Haremos esto partiendo de la definici´on del subconjunto correspondiente y obteniendo las consecuencias oportunas. Para este fin vamos a introducir la siguientes notaci´on: Cuando de una afirmaci´on se deduce otra, escribimos las dos afirmaciones y entre ambas escribimos el s´ımbolo ⇒. En el p´arrafo anterior en realidad estamos introduciendo una nueva forma de obtener nuevas proposiciones a partir de otras dadas. Vamos a hacer una justificaci´on de esto: Si A y B son proposiciones, definimos una nueva proposici´on mediante

A =⇒ B = (¬A) ∨ B

A V F V F

A =⇒ B V V F V

B V V F F

La nueva proposici´on A =⇒ B se lee: “A implica B”, “de A se deduce B” o “si A entonces B”. Tal y como hemos indicado antes indica que si la afirmaci´on A es verdadera, entonces necesariamente B tambi´en lo es. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ LGEBRA DE PROPOSICIONES S EC . 2. A

15

˜ el hecho de que A =⇒ B es verdadera cuando A es falsa y B es verPuede parecer extrano dadera o falsa; esto refleja el bien conocido hecho de que de premisas falsas se podr´ıa obtener cualquier resultado verdadero o falso. ´ Observar que el unico caso en que A =⇒ B es falsa es cuando A es verdadera y B es falsa, esto significa que no se va a poder deducir un resultado falso de un resultado verdadero. Para probar las Proposiciones 2.6. y 2.7., antes tenemos que probar los resultados sobre proposiciones. En nuestro caso, como ya conocemos que A∨B y B∨A son proposiciones equivalentes, resulta que podemos hacer la siguiente demostraci´on: Demostraci´ on de la propiedad conmutativa para la uni´ on X1 ∪ X2 = X2 ∪ X1 . Comprobamos que se tiene X1 ∪ X2 ⊆ X2 ∪ X1 y tambi´en X2 ∪ X1 ⊆ X1 ∪ X2 . Esto es, vemos que cada elemento x ∈ X1 ∪ X2 verifica x ∈ X2 ∪ X1 . x ∈ X1 ∪ X2 ⇒ x ∈ X1 ∨ x ∈ X2 ⇒ x ∈ X2 ∨ x ∈ X1 ⇒ x ∈ X2 ∪ X1 En forma semejante se tiene que cada elemento x ∈ X2 ∪ X1 verifica x ∈ X1 ∪ X2 . x ∈ X2 ∪ X1 ⇒ x ∈ X2 ∨ x ∈ X1 ⇒ x ∈ X1 ∨ x ∈ X2 ⇒ x ∈ X1 ∪ X2 Aqu´ı hemos utilizado que se tiene una equivalencia entre las proposiciones A ∨ B y B ∨ A para cualesquiera proposiciones A y B. Veamos otro ejemplo. Si probamos que son equivalentes las proposiciones ¬(A ∨ B) y (¬A) ∧ (¬B), para cualesquiera proposiciones A y B (ley de de Morgan), esto es, si en la tabla siguiente debajo del s´ımbolo ⇔ s´olo parecen V , (¬ F V F V

A) V F V F

∧ F F F V

(¬ F F V V

B) V V F F

⇐⇒ V V V V

¬ F F F V

(A V F V F

∨ V V V F

B) V V F F

2

1

3

2

1

4

3

1

2

1

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

16

entonces podemos hacer la demostraci´on de la Ley de De Morgan para conjuntos. Demostraci´ on de la ley de De Morgan X1 ∪ X2 = X1 ∩ X2 . Comprobamos que se verifican las inclusiones X1 ∪ X2 ⊆ X1 ∩ X2 y X1 ∩ X2 ⊆ X1 ∪ X2 . Para la primera tenemos que ver que cada elemento x ∈ X1 ∪ X2 verifica tambi´en x ∈ X1 ∩ X2 . x ∈ X1 ∪ X2 ⇒ x ⇒x ⇒x ⇒x

∈ / X1 ∪ X2 ∈ / X1 ∧ x ∈ / X2 ∈ X1 ∧ x ∈ X2 ∈ X1 ∩ X2

(I.1)

La inclusi´on X1 ∩ X2 ⊆ X1 ∪ X2 se prueba simplemente invirtiendo las implicaciones que aparecen en la lista (I.1). / X1 ∪ X2 x ∈ X1 ∪ X2 ⇐ x ∈ ⇐x ∈ / X1 ∧ x ∈ / X2 (I.2) ⇐ x ∈ X1 ∧ x ∈ X2 ⇐ x ∈ X1 ∩ X2 Esta lista (I.2) podr´ıamos tambi´en haberla escrito como x ∈ X1 ∩ X2 ⇒ x ⇒x ⇒x ⇒x

∈ X1 ∧ x ∈ X2 ∈ / X1 ∧ x ∈ / X2 ∈ / X1 ∪ X2 ∈ X1 ∪ X2

(I.3)

Las listas (I.1) y (I.2) se pueden escribir abreviadamente como x ∈ X1 ∪ X2 ⇔ x ⇔x ⇔x ⇔x

∈ / X1 ∪ X2 ∈ / X1 ∧ x ∈ / X2 ∈ X1 ∧ x ∈ X2 ∈ X1 ∩ X2

(I.4)

Ejercicio. 2.8. Probar todos los resultados que aparecen en la Proposici´on 2.6. y la Proposici´on 2.7. sobre propiedades de la uni´on, intersecci´on y complementario de subconjuntos de un conjunto dado. Existen muchos otros resultados sobre la uni´on, intersecci´on y complementario que nos ir´an apareciendo a lo largo de este curso, y de otros cursos. Para su demostraci´on podremos hacer uso de la misma t´ecnica de demostraci´on que hemos empleado aqu´ı, pero tambi´en podemos hacer uso de los resultado que ya hayamos probado. Veamos un ejemplo. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´ LGEBRA DE PROPOSICIONES S EC . 2. A

17

Ejercicio. 2.9. Sean X1 , X2 subconjuntos de un conjunto X . Probar que se verifica (X1 ∩ X2 ) ∪ (X1 ∩ X2 ) = (X1 ∪ X2 ) ∩ (X1 ∩ X2 )

´ . En este caso podemos tambi´en probar que cada elemento del primer subconS OLUCI ON junto es un elemento del segundo y viceversa. Pod´eis comprobar que este proceso es largo. Es mejor entonces utilizar las relaciones que se han establecido en la Proposici´on 2.6. y la Proposici´on 2.7.. Tenemos entonces: (X1 ∩ X2 ) ∪ (X1 ∩ X2 ) = [X1 ∪ (X1 ∩ X2 )] ∩ [X2 ∪ (X1 ∩ X2 )] = [(X1 ∪ X1 ) ∩ (X1 ∪ X2 )] ∩ [(X2 ∪ X1 ) ∩ (X2 ∪ X2 )] = [X ∩ (X1 ∪ X2 )] ∩ [(X2 ∪ X1 ) ∩ X ] = (X1 ∪ X2 ) ∩ (X2 ∪ X1 ) = (X1 ∪ X2 ) ∩ (X2 ∩ X1 ) = (X1 ∪ X2 ) ∩ (X1 ∩ X2 )  El subconjunto (X1 ∩ X2 ) ∪ (X1 ∩ X2 ) se llama la diferencia sim´etrica de X1 y X2 . La vamos a representar por el s´ımbolo ∆; X1 ∆X2 = (X1 ∪ X2 ) ∩ (X1 ∩ X2 ) = X2 ∆X1 . ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

18

2.2.

Producto cartesiano de dos conjuntos

Dados dos conjuntos X e Y , existe un nuevo conjunto, al que llamamos el producto cartesiano de X e Y , cuyos elementos son: X × Y = {(x, y) | x ∈ X y y ∈ Y }. Si X 0 e Y 0 son subconjuntos de X e Y respectivamente, entonces X 0 × Y 0 se considera un subconjunto de X × Y . Ejercicio. 2.10. Sean X e Y conjuntos y X1 , X2 subconjuntos del conjunto X . Demostrar que se verifica X1 × Y ∪ X2 × Y = (X1 ∪ X2 ) × Y X1 × Y ∩ X2 × Y = (X1 ∩ X2 ) × Y Ejercicio. 2.11. Sean X e Y dos conjuntos y X 0 , Y 0 subconjuntos de X e Y respectivamente. Demostrar que se verifica X 0 × Y 0 = (X 0 × Y ) ∪ (X × Y 0 ) Observaci´ on. 2.12. Hasta ahora las operaciones que hemos realizados entre conjuntos en realidad lo han sido entre subconjuntos de un conjunto dado. Podemos definir la uni´on o la intersecci´on de dos conjuntos arbitrarios, pero preferimos establecer la siguiente convenci´on o axioma. Dados dos conjuntos X e Y , existe un conjunto Z tal que X ⊆ Z e Y ⊆ Z . Entonces podemos definir la uni´on o intersecci´on de dos conjuntos arbitrarios apelando a la definici´on de uni´on e intersecci´on de subconjuntos de un conjunto.

3.

Aplicaciones

Sean X e Y dos conjuntos, una aplicaci´ on de X a Y es una regla que permite asignar a cada ´ elemento del conjunto X un unico elemento del conjunto Y . Si f es una aplicaci´on de X en Y , vamos a representar f mediante: f : X −→ Y

f

o´ X −→ Y

´ Si x ∈ X y f : X −→ Y es una aplicaci´on, llamamos f (x) al unico elemento de Y que asigna f a x, y lo llamamos imagen de x por f . 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 3. A PLICACIONES

19

El conjunto Im(f ) = {f (x) ∈ Y | x ∈ X } se llama la imagen de la aplicaci´ on f , y es un subconjunto de Y . En general, si X1 es un subconjunto de X , llamamos imagen de X1 por f al subconjunto f (X1 ) de Y definido como: f (X1 ) = {f (x) ∈ Y | x ∈ X1 }. Si Y1 es un subconjunto de Y , llamamos imagen inversa de Y1 por f al subconjunto f −1 (Y1 ) de X definido como: f −1 (Y1 ) = {x ∈ X | f (x) ∈ Y1 }.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

20

Ejemplo. 3.1. Sean A = {1, 2, a, b, c} y E = {α, β, γ, δ} dos conjuntos y f : A −→ E la aplicaci´on definida por f (1) = β, f (2) = δ, f (a) = α, f (b) = α, f (c) = β.

Entonces la imagen de f es: Im(f ) = {α, β, δ}. La imagen de B = {1, 2} ⊆ A es: f (B) = {β, δ}. La imagen inversa de F = {γ, δ} ⊆ E es: f −1 (F ) = {2}.

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 3. A PLICACIONES

21

Ejercicio. 3.2. Sea f : X −→ Y una aplicaci´on y sean A, B ⊆ X subconjuntos de X . (1) Probar que f (A ∪ B) = f (A) ∪ f (B). (2) ¿Qu´e relaci´on existe entre f (A ∩ B) y f (A) ∩ f (B)? Ejercicio. 3.3. Sea f : X −→ Y una aplicaci´on y sean C, D ⊆ Y subconjuntos de Y . (1) Probar que f −1 (A ∪ B) = f −1 (A) ∪ f −1 (B). (2) ¿Qu´e relaci´on existe entre f −1 (A ∩ B) y f −1 (A) ∩ f −1 (B)? Vamos a establecer el concepto de aplicaci´on de forma m´as rigurosa. Sean X e Y dos conjuntos, un grafo de aplicaci´ on de X en Y es un subconjunto G del conjunto producto cartesiano X × Y verificando la siguiente propiedad: ´ para cada x ∈ X existe un unico y ∈ Y tal que (x, y) ∈ G. De la definici´on se deduce que si un par (x, y) pertenece a G, el elemento y est´a un´ıvocamente determinado por el elemento x, por lo que vamos a representar y por G(x). As´ı pues un grafo de aplicaci´on G determina una aplicaci´on x 7→ G(x), en el sentido en que las hemos definido anteriormente. Y rec´ıprocamente, si f : X −→ Y es una aplicaci´on, definimos el grafo de f mediante Gr(f ) = {(x, f (x)) ∈ X × Y | x ∈ X }. Entonces Gr(f ) es un grafo de aplicaci´on. La formalizaci´on del concepto de aplicaci´on pasa pues por identificar los dos conceptos, el de aplicaci´on y el de grafo de aplicaci´on.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

22

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

Ejemplo. 3.4. Observar que si consideramos la aplicaci´on f : R −→ R definida por f (x) = x 2 , resulta que la gr´afica de la funci´on es la par´abola siguiente. Por lo tanto f es una aplicaci´on de R en R y su grafo son los puntos de la par´abola.

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 3. A PLICACIONES

23

Observar que si consideramos la gr´afica de una circunferencia x 2 + y 2 = 1, esta gr´afica no es un grafo de aplicaci´o n, x 7→ y, de R a R, pues hay puntos, por ejemplo x = 12 que tienen dos √ √ posibles im´agenes:

3 4

y−

3 4 .

En resumen. Dados dos conjuntos X e Y , dar una aplicaci´on f de X a Y es lo mismo que dar un subconjunto G ⊆ X × Y que es un grafo de aplicaci´on. En este caso la aplicaci´on f : X −→ ´ Y lleva cada elemento x ∈ X en el unico elemento y ∈ Y tal que el par (x, y) ∈ G, entonces el elemento y est´a determinado un´ıvocamente por x y f , por lo que lo representaremos por f (x). ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

24

3.1.

Tipos de aplicaciones

Sea f : X −→ Y una aplicaci´on, decimos que f es sobreyectiva si Im(f ) = Y , esto es, si para cada elemento y ∈ Y existe un elemento x ∈ X tal que f (x) = y. Llamamos inyectiva a una aplicaci´on f : X −→ Y tal que para cualesquiera dos elementos x1 , x2 ∈ X , si f (x1 ) = f (x2 ), entonces x1 = x2 . Ejercicio. 3.5. Sea g : Q+ −→ Q+ definida por f (x) = x 2 para cada x ∈ Q+ . Probar que la aplicaci´on g es inyectiva y no es sobreyectiva. ´ . Para comprobarlo procedemos como sigue: si g (x1 ) = g (x2 ), entonces tenemos S OLUCI ON 2 2 x1 = x2 , de donde deducimos que x1 = x2 , ya que ambos son positivos. Sin embargo g no es una aplicaci´on sobreyectiva, ya que por ejemplo 2 ∈ / Im(g ). Para comprobarlo basta suponer que esto no fuese √ cierto, entonces existir´ıa un elemento + 2 ´ racional.  x ∈ Q tal que x = 2, lo cual es imposible, ya que 2 no es un numero Ejemplo. 3.6. La aplicaci´on f del ejemplo de la p´agina 20 no es sobreyectiva ya que γ ∈ / Im(f ), y no es inyectiva, ya que, por ejemplo, f (1) = β = f (c). Una aplicaci´on f : X −→ Y que es a la vez inyectiva y sobreyectiva se llama una aplicaci´ on biyectiva o una biyecci´ on. Ejemplo. 3.7. La aplicaci´on h : R+ −→ R+ definida h(x) = x 2 para cada x ∈ R es una biyecci´on.

3.2.

Composici´ on de aplicaciones

Supongamos que f : X −→ Y y g : Y −→ Z son aplicaciones, definimos una nueva aplicaci´on g ◦ f : X −→ Z como sigue: (g ◦ f )(x) = g (f (x)) para cada x ∈ X . g ◦ f se llama la composici´ on de f y g . La composici´on de f y g se suele representar tambi´en simplemente por gf . Para cada conjunto X existe una aplicaci´on especial, llamada identidad en X , a la que representamos por 1X y que est´a definida por 1X (x) = x para cada x ∈ X . 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 4. R ELACIONES DE EQUIVALENCIA Y DE ORDEN

25

Lema. 3.8. Sea f : X −→ Y una aplicaci´on. Se verifica f ◦ 1X = f y 1Y ◦ f = f . Si f : X −→ Y es una aplicaci´on, llamamos una aplicaci´ on inversa de f a una aplicaci´on g : Y −→ X que verifica f ◦ g = 1Y y g ◦ f = 1X . Observaci´ on. 3.9. En general si una aplicaci´on f tiene una inversa, esta inversa se representa por f −1 . ¡OJO!. No confundir con la notaci´on f −1 utilizada para la imagen inversa de un subconjunto. Lema. 3.10. Si una aplicaci´on f : X −→ Y tiene una inversa, entonces es una biyecci´on. Ejercicio. 3.11. Demostrar que si f : X −→ Y es una biyecci´on, entonces existe una inversa de f . Tenemos entonces que una aplicaci´on f : X −→ Y es biyectiva si y solo si tiene una inversa. Observaci´ on. 3.12. Observar que al decir que una aplicaci´on f : X −→ Y tiene una inversa hemos dicho que existe una aplicaci´on g : Y −→ X verificando fg = 1Y y gf = 1X , no basta con solo una de las igualdades, ya que dada la aplicaci´on f : {1, 2} −→ {a} existe una aplicaci´on g : {a} −→ {1, 2} verificando fg = 1{a} , pero no es biyectiva. En efecto, es f´acil ver que no es una aplicaci´on inyectiva.

4.

Relaciones de equivalencia y de orden

Una relaci´ on R en un conjunto X es una regla que permite distinguir si dos elementos est´an o no relacionados. Si dos elementos x, y ∈ X est´an relacionados mediante la relaci´on R escribimos xRy. Veamos algunas de las propiedades que puede verificar una relaci´on. Propiedad reflexiva. Decimos que la relaci´on R verifica la propiedad reflexiva si para cada elemento x ∈ X se verifica xRx. ∀x ∈ X , xRx. Propiedad sim´etrica. Decimos que R verifica la propiedad sim´etrica si cuando para dos elementos x, y ∈ X se verifica xRy, entonces tambi´en se tiene yRx. ∀x, y ∈ X , si xRy, entonces yRx. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

26

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

Propiedad transitiva. Decimos que R verifica la propiedad transitiva si cuando para tres elementos x, y, z ∈ X se verifica xRy e yRz, entonces tambi´en se verifica xRz. ∀x, y, z ∈ X , si xRy e yRz, entonces xRz. Propiedad antisim´etrica. Decimos que R verifica la propiedad antisim´etrica si cuando para dos elementos x, y ∈ X se verifica xRy e yRx, entonces se verifica x = y. ∀x, y ∈ X , si xRy e yRx, entonces x = y. Vamos a poner ejemplos de relaciones que verifican algunas de estas propiedades. Ejemplo. 4.1. ´ Consideramos el conjunto N de los numeros naturales y definimos aRb si existe c ∈ N tal que a = b + 2c o´ b = a + 2c. Entonces R verifica las propiedades reflexiva, sim´etrica y transitiva. Ejemplo. 4.2. ´ ´ Consideramos el conjunto Z de los numeros naturales y definimos aRb si a −b es un multiplo de 2, (existe c ∈ Z tal que a − b = 2c). Entonces R verifica las propiedades reflexiva, sim´etrica y transitiva. Ejemplo. 4.3. ´ Consideramos el conjunto N de los numeros naturales y definimos la relaci´on a | b si existe c ∈ N tal que b = ac. Entonces | verifica las propiedades reflexiva, antisim´etrica y transitiva. Ejemplo. 4.4. ´ Consideramos el conjunto Z de los numeros enteros y definimos la relaci´on a | b si existe c ∈ Z tal que b = ac. Entonces | verifica las propiedades reflexiva y transitiva, y no verifica la propiedad antisim´etrica. Si R es una relaci´on en un conjunto X , podemos considerar el grafo de R como el subconjunto Gr(R) = {(x, y) ∈ X × X | xRy}. Est´a claro que definir una relaci´on en un conjunto X es lo mismo que dar su grafo, esto es, un subconjunto de X × X . El uso de grafos permite hacer algunas construcciones sobre relaciones de forma f´acil. Observar los siguientes hechos: (1). Una relaci´on R es reflexiva si y solo si la diagonal de X × X est´a incluida en el grafo de R. (2). Una relaci´on R es sim´etrica si y solo si el grafo de R es sim´etrico respecto a la diagonal. (Esto es, si (x, y) ∈ Gr(R), entonces (y, x) ∈ Gr(R).

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 4. R ELACIONES DE EQUIVALENCIA Y DE ORDEN

4.1.

27

Relaci´ on de equivalencia

Decimos que una relaci´on R que verifica las propiedades reflexiva, sim´etrica y transitiva es una relaci´ on de equivalencia. Si R es una relaci´on de equivalencia en un conjunto X , para cada elemento a ∈ X definimos la clase de equivalencia de a como el subconjunto a = [a] = {x ∈ X | aRx}.

Lema. 4.5. Si a, b ∈ X , entonces se verifica a = b o´ a ∩ b = ∅, esto es, cada dos clases de equivalencia o´ son iguales o´ son disjuntas. Si R es una relaci´on de equivalencia en un conjunto X , el conjunto de todas las clases de equivalencia se llama el conjunto cociente de X por R, y se representa por X /R. Ejercicio. 4.6. En el conjunto R × R se considera la relaci´on (a1 , a2 )R(b1 , b2 ) si a12 + a22 = b12 + b22 . Probar que R es una relaci´on de equivalencia en R × R y describir el conjunto cociente. Si R es una relaci´on de equivalencia en un conjunto X y X /R es el conjunto cociente, existe una aplicaci´on sobreyectiva p: X −→ X /R que a cada elemento x ∈ X le asocia p(x) = x. Proposici´ on. 4.7. Dado un conjunto cualquiera X , para cada aplicaci´on f : X −→ Y se tiene una relaci´on de equivalencia Rf en X dada por x1 Rf x2 si f (x1 ) = f (x2 ). Adem´as cada relaci´on de equivalencia en X est´a definida en esta forma por una aplicaci´on ´ conjunto Y . conveniente de f : X −→ Y para algun Proposici´ on. 4.8. Cada relaci´on de equivalencia en un conjunto X est´a definida, y define, por una partici´on de X. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

28

4.2.

Relaci´ on de orden

Decimos que una relaci´on R que verifica las propiedades reflexiva, antisim´etrica y transitiva es una relaci´ on de orden. Un conjunto X junto con una relaci´on de orden se llama un conjunto parcialmente ordenado. Si Y es un subconjunto de un conjunto parcialmente ordenado X con relaci´on orden R, llamamos: ´ elemento y ∈ Y tal elemento maximal de Y a un elemento m ∈ Y tal que no existe ningun que mRy. cota superior de Y en X a un elemento c ∈ X tal que yRc para cada elemento y ∈ Y . elemento m´aximo de Y a un elemento m ∈ Y tal que yRm para cada elemento y ∈ Y . Esto es, un m´aximo de Y es una cota superior de Y en X que pertenece a Y . Ejercicio. 4.9. Demostrar que en un conjunto parcialmente ordenado el elemento m´aximo de un subcon´ junto, si existe, es unico. ´ . Sea Y un subconjunto de un conjunto X con una relaci´on de orden R, y supongS OLUCI ON amos que Y tiene dos elementos m´aximos m1 y m2 . Por ser m1 un m´aximo de Y y ser m2 ∈ Y se verifica m2 Rm1 . Por an´alogos motivos se verifica m1 Rm2 . Entonces como R verifica la propiedad antisim´etrica, se verifica m1 = m2 y el m´aximo de Y ´ es unico.  Tambi´en existen las nociones duales, esto es, las nociones de elemento minimal, de cota inferior y de elemento m´ınimo o´ primer elemento. Finalmente, un elemento s ∈ X se dice que es un supremo de Y si es un m´ınimo del conjunto de las cotas superiores de Y . El concepto dual es el de ´ınfimo. Ejercicio. 4.10. Escribir las nociones aqu´ı mencionadas para una relaci´on de orden en X representada por el s´ımbolo ≤ en vez del s´ımbolo R. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 5. C UANTIFICADORES

29

Ejercicio. 4.11. Orden lexicogr´afico Se considera N × N, y en e´ l la relaci´on: (a, b) ≤ (c, d), si a < c o´ a = c y b ≤ d. Demuestra que esta relaci´on es una relaci´on de orden en N × N. Nota. Es preciso destacar que las definiciones que hemos hecho de conjunto, aplicaci´on entre conjuntos y relaci´on en un conjunto carecen totalmente de rigurosidad. El objetivo hasta ˜ aqu´ı ha sido senalar que, en este momento, nos interesa m´as el manejo de los conceptos que los conceptos en s´ı mismos. De cualquier forma remitimos al alumno o alumnos interesados en profundizar en estos conceptos a los libros de la bibliograf´ıa para definiciones m´as rigurosas de las nociones aqu´ı introducidas.

5.

Cuantificadores

´ ´ Sea R el conjunto de los numeros reales. Para cada numero natural n definimos un subconjunto Cn de R mediante Cn = [0, n) = {r ∈ R | 0 ≤ r < n} = [0, n). El menor subconjunto de R que contiene a todos los Cn es exactamente [0, ∞). ´ Podemos hablar entonces de la uni´on de todos los subconjuntos Cn , para n un numero natural, y representamos esta uni´on como ∪{Cn | n ∈ N}

o´

∪n∈N Cn .

Si consideramos ahora un conjunto X y subconjuntos Xn de X , entonces tambi´en podemos definir la uni´on de los subconjuntos Xn ; esta ser´a: ∪{Xn | n ∈ N}

o´

∪n∈N Xn ,

y sus elementos son {x ∈ X | existe un n ∈ N tal que x ∈ Xn }. Aqu´ı hemos utilizado como conjunto de ´ındices el conjunto N, pero esto no es imprescindible y podr´ıamos haber utilizado otro conjunto, supongamos que Λ, con elementos λ. Tendremos entonces ∪{Xλ | λ ∈ Λ} = ∪λ∈Λ Xλ = {x ∈ X | existe un λ ∈ Λ tal que x ∈ Xλ }. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

30

La intersecci´on de los subconjuntos Xλ se define entonces como ∩{Xλ | λ ∈ Λ} = ∩λ∈Λ Xλ = {x ∈ X | para cada λ ∈ Λ se tiene x ∈ Xλ }.

En todo este proceso nos aparecen dos cuantificadores, el cuantificador existencial, usado en la definici´on de uni´on, y el cuantificador universal, usado en la intersecci´on. Vamos a representar por ∃ el cuantificador existencial y por ∀ el cuantificador universal. Escribimos entonces ∪{Xλ | λ ∈ Λ} = {x ∈ X | ∃λ ∈ Λ, x ∈ Xλ }. y ∩{Xλ | λ ∈ Λ} = {x ∈ X | ∀λ ∈ Λ, x ∈ Xλ }. Las afirmaciones que tienen una variable en vez de proposiciones las vamos a llamar funciones proposicionales, de forma que si A(x) es una funci´on proposicional, para cada valor a del argumento x tenemos que A(a) es una proposici´on. En el ejemplo anterior x ∈ Xλ es una funci´on proposicional con variable λ. Los cuantificadores ´ actuan pues sobre las variables de las funciones proposicionales. Ejemplo. 5.1. (I) Se considera la funci´on proposicional P(X ) definida por: “X es mayor que 2”. (II) Se consideran el cuantificador ∃ y la proposici´on: ∃x ∈ C, P(x). Esta proposici´on se lee: existe x en C tal que P(x) es cierta, esto es, “existe un elemento x en C tal que x es mayor que 2”. Es cierta si C es por ejemplo el conjunto {0, 1, 2, 3} y falsa si C es el conjunto {−1, 0, 1, 2}. (III) Si se considera el cuantificador ∀ y la proposici´on: ∀x ∈ C, P(x). Esta proposici´on se lee: para todo x en C se tiene que P(x) es cierta, esto es, “para todo elemento x en C se tiene que x es mayor que 2”. Es cierta si C es por ejemplo el conjunto {3, 4, 5} y es falsa si C es el conjunto {0, 1, 2, 3}. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 5. C UANTIFICADORES

5.1.

31

Relaci´ on de equivalencia y partici´ on de un conjunto

Una partici´ on de un conjunto X es un conjunto de subconjuntos de X , disjuntos dos a dos, cuya uni´on es X . Si R es una relaci´on de equivalencia en un conjunto X , entonces el conjunto de las clases de equivalencia, para la relaci´on de equivalencia R, forma una partici´on de X ; la llamamos la partici´on definida por la relaci´on R. El resultado rec´ıproco tambi´en es cierto, esto es, para cualquier partici´on {Xλ | λ ∈ Λ} de un conjunto X , existe una relaci´on de equivalencia R en X de forma que la partici´on definida por R coincide con la partici´on {Xλ | λ ∈ Λ}. En efecto, basta definir R como sigue: “si x e y son elementos de X entonces xRy si x e y pertenecen a un mismo subconjunto Xλ ”. Lema. 5.2. La relaci´on R, as´ı definida, es una relaci´on de equivalencia. ´ . (1). Propiedad reflexiva. Para cada x ∈ X , ya que la uni´on de los subconD EMOSTRACI ON juntos Xλ es X , existe un ´ındice λ ∈ Λ tal que x ∈ Xλ , luego xRx. ∀x ∈ X , xRx (2). Propiedad sim´etrica. Para cualesquiera x, y ∈ X , si xRy, entonces existe un ´ındice λ ∈ Λ tal que x, y ∈ X , pero es claro que tambi´en se verifica y, x ∈ Xλ , ya que el orden de los elementos x e y es irrelevante, entonces yRx. ∀x ∈ X , ∀y ∈ X , xRy =⇒ yRx (3). Propiedad transitiva. Para cualesquiera x, y, z ∈ X , si xRy e yRz, entonces existen ´ındices λ, µ ∈ Λ tales que x, y ∈ Xλ e y, z ∈ Xµ . Como Xλ = Xµ o´ Xλ ∩ Xµ = ∅ y se verifica y ∈ Xλ ∩ Xµ , resulta Xλ = Xµ , luego x, z ∈ Xλ y tenemos xRz. ∀x ∈ X , ∀y ∈ X , ∀z ∈ X , xRy e yRz =⇒ xRz  Ejercicio. 5.3. Se considera el conjunto N = {1, 2}. Determinar la relaci´on de equivalencia que define la partici´on {{1}, {2}}. Ejercicio. 5.4. Obtener la partici´on dada por la relaci´on de equivalencia del Ejemplo 4.1..

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

32

Ejercicio. 5.5. Dar la relaci´on de equivalencia en N \ {0} que da la siguiente partici´on: {1, . . . , 9}, {10, 11, . . . , 99}, {100, 101, . . . , 999}, . . .

˜ Queremos hacer un comentario sobre las notaciones anteriores. Como ya hemos senalado, el s´ımbolo =⇒ indica que la afirmaci´on tras el s´ımbolo es cierta cuando lo es la afirmaci´on que aparece antes de e´ l. En la p´agina 31 aparece xRy ⇒ yRx, esto es, si se verifica xRy, entonces se verifica yRx. Una forma alternativa de leerlo es la siguiente: xRy implica yRx. ´ Aqu´ı vamos a usarlo, en combinaci´on con los cuantificadores en multiples contextos. Veamos un ejemplo. Consideramos el conjunto A = {1, 2, a, b, c} y los subconjuntos B = {1, 2} y B1 = {1, 2, a}. Como B es un subconjunto de B1 se tiene: ∀x ∈ A, x ∈ B =⇒ x ∈ B1 Si quisi´eramos expresar que B1 no es un subconjunto de B tendr´ıamos que escribir: ∃x ∈ A, x ∈ B1 y x ∈ /B En efecto esta segunda expresi´on es la negaci´on de la primera, ya que A =⇒ B est´a definido como (¬A) ∨ B. En forma simb´olica se escriben ∀x ∈ A, A(x) =⇒ B(x) o equivalentemente ∀x ∈ A, (¬A(x)) ∨ B(x) y su negaci´on, que ser´ıa: ∃x ∈ A, A(x) ∧ (¬B(x)) [= ¬((¬A(x)) ∨ B(x))] .

6.

M´etodos de demostraci´ on

A continuaci´on vamos a ver c´omo hacer demostraciones de algunos resultados en Matem´aticas. ˜ Aunque ya hemos hecho alguna en lo que llevamos expuesto, se trata aqu´ı de hacer un pequeno resumen de estos m´etodos. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

´N S EC . 6. M E´ TODOS DE DEMOSTRACI O

6.1.

33

M´etodo directo

Consiste en probar A =⇒ B directamente, haciendo uso de las definiciones y resultados previos. Hasta ahora las demostraciones que hemos hecho son todas directas. Pero existen otros m´etodos de hacer demostraciones que vamos a detallar.

6.2.

M´etodo contra-rec´ıproco

Consiste en probar A =⇒ B mediante una demostraci´on directa de la proposici´on equivalente (¬B) =⇒ (¬A)

6.3.

M´etodo de reducci´ on al absurdo

Consiste en probar A =⇒ B mediante una demostraci´on directa de una de las siguientes proposiciones: A ∧ (¬B) =⇒ ¬A o´ A ∧ (¬B) =⇒ B. La siguiente es una demostraci´on por reducci´on al absurdo utilizando el siguiente argumento: “Si de una afirmaci´on (A) se deduce una afirmaci´on (B), que es falsa, entonces la afirmaci´on (A) es falsa”. (Nota. Observar la tabla de verdad de ⇒.) Teorema. 6.1. (Teorema de Euclides) ´ Existen infinitos numeros naturales primos. ´ . Supongamos que no es cierto el enunciado del Teorema, entonces hay D EMOSTRACI ON ´ ´ ´ ´ unicamente un numero finito de numeros naturales primos, sean estos p1 , . . . , pt . El numero q = p1 · · · pt + 1 da de resto 1 al dividirlo por todos los primos conocidos. Tenemos pues un ´ ´ numero distinto de 0 y 1 que no es un producto de numeros primos, lo que es una contradicci´on. Afirmaci´on (A): no es cierto el enunciado del Teorema. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

34

´ ´ Afirmaci´on (B): existe un numero natural distinto de 0 y 1 que no es un producto de numeros primos. Hemos probado que A ⇒ B, pero como sabemos que siempre se verifica ¬B, llegamos a probar la implicaci´on ¬B ⇒ ¬A que era lo que quer´ıamos.  Otro ejemplo de demostraci´on por reducci´on al absurdo se obtiene al probar el siguiente resultado: Ejercicio. 6.2. √ ´ Demostrar que 2 no es un numero racional.

6.4.

Enunciados de teoremas

Teorema directo: Teorema contrario: Teorema rec´ıproco:

A =⇒ (¬A)

=⇒

B =⇒

Teorema contra-rec´ıproco: (¬B)

=⇒

B (¬B) A (¬A)

Son equivalentes el teorema directo y el contra-rec´ıproco y tambi´en son equivalentes, entre s´ı el teorema contrario y el rec´ıproco. Veamos un ejemplo. Vamos a suponer que X e Y son conjuntos finitos y que f : X −→ Y es una aplicaci´on. Enunciado directo: Lema. 6.3. Si f es inyectiva, entonces Card(X ) ≤ Card(Y ). El enunciado contra-rec´ıproco, y equivalente, de este Lema es el siguiente: Lema. 6.4. (Principio del palomar) Si Card(Y ) < Card(X ), entonces f no es inyectiva. Es claro que los enunciados son equivalentes: 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

35

Vamos a llamar A a la afirmaci´on “f es inyectiva” y B a la afirmaci´on “Card(X ) ≤ Card(Y )”. Entonces el Lema 6.3. se escribe A =⇒ B y el Lema 6.4. se escribe (¬B) =⇒ (¬A).

7.

Ejercicios

Introducci´ on intuitiva a la teor´ıa de conjuntos Ejercicio. 7.1. Preparaci´on para probar la f´ormula del binomio de Newton:
n! ´ Se define el numero combinatorio ni = n(n−1)···(n−i+1) = i! (n−i)! , para 1 ≤ i ≤ n y i(i−1)···2·1 Probar que se verifica la igualdad siguiente:       n n n+1 + = . i i+1 i+1 ´ . S OLUCI ON

n
n
n! i + i+1 = i! (n−i)!

+

= 1.

n! (i+1)! (n−(i+1))!

=

n!(i+1) (i+1)! (n−i)!

=

n!(i+1)+n!(n−i) (i+1)! (n−i)!

=

n!(n+1) (i+1)! (n−i)!

=

(n+1)! (i+1)! ((n+1)−(i+1))!

=

n
0

+

n!(n−i) (i+1)! (n−i))!

n+1
i+1 .

 Ejercicio. 7.2. ¿Cu´antos elementos tiene el conjunto {1, 2, {1, 2}}. ´ . Tiene tres elementos; estos son: 1, 2 y {1, 2}. S OLUCI ON

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

 P. Jara

36

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

Ejercicio. 7.3. Dada la figura siguiente:

describir mediante una f´ormula, cada una de las regiones del dibujo. Por ejemplo la parte coloreada es A ∩ B ∩ C. ´ . Veamos diferentes regiones: S OLUCI ON

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

37

es A ∩ B \ C = A ∩ B ∩ C.

es A ∩ C \ B = A ∩ B ∩ C.

es B ∩ C \ A = A ∩ B ∩ C. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

38

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

es C \ (A ∪ B) = A ∩ B ∩ C.

es B \ (A ∪ C) = A ∩ B ∩ C. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

39

es A \ (B ∪ C) = A ∩ B ∩ C.

es A ∪ B ∪ C = A ∩ B ∩ C. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

 P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

40

´ Algebra de proposiciones Ejercicio. 7.4. Probar que las proposiciones (A ∧ B) ∨ C y (A ∨ C) ∧ (B ∨ C) son equivalentes, y que como consecuencia para tres subconjuntos X1 , X2 y X3 de un conjunto dado se tiene la igualdad: (X1 ∩ X2 ) ∪ X3 = (X1 ∪ X3 ) ∩ (X2 ∪ X3 ). ´ . S OLUCI ON (A V F V F V F V F 1

∧ V F F F V F F F 2

B) V V F F V V F F 1

∨ V V V V V F F F 3

C V V V V F F F F 1

⇔ V V V V V V V V 4

(A V F V F V F V F 1

∨ V V V V V F V F 2

C) V V V V F F F F 1

∧ V V V V V F F F 3

(B V V F F V V F F 1

∨ V V V V V V F F 2

C) V V V V F F F F 1

Dado x ∈ (X1 ∩ X2 ) ∪ X3 , tenemos: x ∈ (X1 ∩ X2 ) ∪ X3 ⇔(x ∈ X1 ∩ X2 ) ∨ (x ∈ X3 ) ⇔[(x ∈ X1 ) ∧ (x ∈ X2 )] ∨ (x ∈ X3 ) ⇔[(x ∈ X1 ) ∨ (x ∈ X3 )] ∧ [(x ∈ X2 ) ∨ (x ∈ X3 )] ⇔(x ∈ X1 ∪ X3 ) ∧ (x ∈ X2 ∪ X3 ) ⇔x ∈ (X1 ∪ X3 ) ∩ (X2 ∪ X3 )  Ejercicio. 7.5. Probar que para dos subconjuntos X1 y X2 de un conjunto dado X se verifica: (X1 ∩ X2 ) ∪ X1 = X1 . ´ . Podemos proceder probando la equivalencia (A ∧ B) ∨ A ⇔ A, y a partir de aqu´ı, S OLUCI ON el resultado se sigue f´acilmente. (A V F V F 1

∧ V F F F 2

B) V V F F 1

∨ V F V F 3

A V F V F 1

⇔ V V V V =

A V F V F 1 

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

41

Ejercicio. 7.6. Probar que para dos subconjuntos X1 y X2 de un conjunto dado X se verifica: (X1 ∪ X2 ) ∩ X1 = X1 . ´ . Procedemos como sigue: S OLUCI ON (X1 ∪ X2 ) ∩ X1 = (X1 ∩ X1 ) ∪ (X2 ∩ X1 ) = X1 ∪ (X2 ∩ X1 = X1 . Observar que hemos utilizado el resultado contenido en el (Ejercicio 7.5.).



Ejercicio. 7.7. Si A, B y C son proposiciones, ¿son equivalentes las siguientes proposiciones?: (1) A ⇒ B y B ⇒ A, (2) (A ⇒ B) ⇒ C y A ⇒ (B ⇒ C), (3) ¬(A ⇒ B) y B ⇒ A, (4) 6= A ⇒6= B y B ⇒ A, (5) 6= (A ⇒ B) y 6= A ⇒6= B. ´ . Hacer S OLUCI ON Ejercicio. 7.8. Si A, B y C son proposiciones, ¿son tautolog´ıas las siguientes proposiciones?:



(1) A ∧ B ⇒ A ∨ C, (2) A ∨ B ⇒ A ∧ C. ´ . Hacer S OLUCI ON



Aplicaciones Ejercicio. 7.9. Sean X e Y conjuntos y X1 , X2 subconjuntos del conjunto X . Demostrar que se verifica X1 × Y ∪ X2 × Y = (X1 ∪ X2 ) × Y X1 × Y ∩ X2 × Y = (X1 ∩ X2 ) × Y ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

42

Nota: hacer previamente una representaci´on gr´afica. ´ . Primera igualdad. Una representaci´on gr´afica podr´ıa ser la siguiente: S OLUCI ON

Y

X1

X2

X

˜ ˜ en donde el subconjunto X1 ⊆ X est´a senalado en azul y el subconjunto X2 ⊆ X est´a senalado en rojo. Tenemos X1 × Y es la parte rayada en azul y X2 × Y es la rayada en rojo. Por otro lado la parte rayada, tanto en azul como en rojo es el subconjunto (X1 ∩ X2 ) × Y . Una demostraci´on por elementos ser´ıa la siguiente: (x, y) ∈ X1 × Y ∪ X2 × Y ⇔ ((x, y) ∈ X1 × Y ) ∨ ((x, y) ∈ X2 × Y ) ⇔ ((x ∈ X1 ) ∧ (y ∈ Y )) ∨ ((x ∈ X2 ) ∧ (y ∈ Y )) ⇔ ((x ∈ X1 ) ∨ (x ∈ X2 )) ∧ ((x ∈ X1 ) ∨ (y ∈ Y ))∧ ((y ∈ Y ) ∨ (x ∈ X2 )) ∧ ((y ∈ Y ) ∨ (y ∈ Y )) ⇔ ((x ∈ X1 ) ∨ (x ∈ X2 )) ∧ (y ∈ Y ) ⇔ (x ∈ X1 ∪ X2 ) ∧ (y ∈ Y ) ⇔ (x, y) ∈ (X1 ∪ X2 ) × Y . Se puede observar que hemos hecho uso de las siguientes propiedades para proposiciones: A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C), B∧B⇔B y (A ∨ B) ∧ B ⇔ B, las cuales las pod´eis probar mediante el uso de tablas de verdad. Primera igualdad. Hacer una representaci´on gr´aficas para esta igualdad. 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

43

Para una demostraci´on por elementos podemos proceder como sigue: (x, y) ∈ X1 × Y ∩ X2 × Y ⇔ ((x, y) ∈ X1 × Y ) ∧ ((x, y) ∈ X2 × Y ) ⇔ ((x ∈ X1 ) ∧ (y ∈ Y )) ∧ ((x ∈ X2 ) ∧ (y ∈ Y )) ⇔ (x ∈ X1 ) ∧ (x ∈ X2 ) ∧ (y ∈ Y ) ⇔ ((x ∈ X1 ) ∧ (x ∈ X2 )) ∧ (y ∈ Y ) ⇔ (x ∈ X1 ∩ X2 ) ∧ (y ∈ Y ) ⇔ (x, y) ∈ (X1 ∩ X2 ) × Y .  Ejercicio. 7.10. Sean X e Y dos conjuntos y X 0 , Y 0 subconjuntos de X e Y respectivamente. Demostrar que se verifica X 0 × Y 0 = (X 0 × Y ) ∪ (X × Y 0 ) Nota: hacer previamente una representaci´on gr´afica. ´ . La representaci´on gr´afica es la siguiente: S OLUCI ON Y

H H H H H HHHHHHHHHH HH HHHHHHHH HHHHHHHH HHHHH HH H Y 0 HH H H H HH HHHH HH HHHH HHHH H H HHHHHH H H H H H

X0

X

Hemos representado en color azul el subconjunto X 0 × Y 0 y su complemento lo hemos pintado en rojo. Es claro que esta regi´on es la uni´on (X 0 × Y ) ∪ (X × Y 0 ). Una demostraci´on por elementos es la siguiente, en la que recordemos, que si (x, y) ∈ X 0 ×Y 0 , entonces (x, y) ∈ X × Y . (x, y) ∈ X 0 × Y 0 ⇔ (x, y) ∈ / X0 × Y 0 ⇔ ¬((x, y) ∈ X 0 × Y 0 ) ⇔ ¬((x ∈ X 0 ) ∧ (y ∈ Y 0 )) ⇔ (¬(x ∈ X 0 )) ∨ (¬(y ∈ Y 0 )) ⇔ (x ∈ / X 0 ) ∨ (y ∈ / Y 0) ⇔ (x ∈ X 0 ) ∨ (y ∈ Y 0 ) ⇔ ((x ∈ X 0 ) ∧ (y ∈ Y )) ∨ ((x ∈ X ) ∧ (y ∈ Y 0 )) ⇔ ((x, y) ∈ X 0 × Y ) ∨ ((x, y) ∈ X × Y 0 ) ⇔ (x, y) ∈ (X 0 × Y ) ∪ (X × Y 0 ) ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

44

 Ejercicio. 7.11. Sea f : X −→ Y una aplicaci´on y sean A, B ⊆ X subconjuntos de X . (1). Probar que f (A ∪ B) = f (A) ∪ f (B). (2). ¿Qu´e relaci´on existe entre f (A ∩ B) y f (A) ∩ f (B)? ´ . Parte 1. Tenemos las siguientes equivalencias: S OLUCI ON y ∈ f (A ∪ B) ⇔ ∃x ∈ A ∪ B, f (x) = y ⇔ (∃x ∈ A, f (x) = y) ∨ (∃x ∈ B, f (x) = y) ⇔ (y ∈ f (A)) ∨ (y ∈ f (B)) ⇔ y ∈ f (A) ∪ f (B). Parte 2. Es claro que se puede probar la inclusi´on f (A ∩ B) ⊆ f (A) ∩ f (B) siguiendo las siguientes implicaciones: y ∈ f (A ∩ B) ⇔ ∃x ∈ A ∩ B, f (x) = y ⇐ (∃x ∈ A, f (x) = y) ∧ (∃x ∈ B, f (x) = y) ⇔ (y ∈ f (A)) ∧ (y ∈ f (B)) ⇔ y ∈ f (A) ∩ f (B). En cambio la otra inclusi´on no es cierta; basta considerar el siguiente ejemplo: X = {a, b}, Y = {1}, f : X −→ Y , f (a) = 1 = f (b) Es claro que si A = {a} y B = {b}, entonces se verifica: f (A ∩ B) = f (∅) = ∅ 6= {1} = f (A) ∩ f (B).  Ejercicio. 7.12. Sea f : X −→ Y una aplicaci´on y sean C, D ⊆ Y subconjuntos de Y . (1). Probar que f −1 (C ∪ D) = f −1 (C) ∪ f −1 (D). (2). ¿Qu´e relaci´on existe entre f −1 (C ∩ D) y f −1 (C) ∩ f −1 (D)? ´ . Parte 1. Tenemos las siguientes equivalencias: S OLUCI ON x ∈ f −1 (C ∪ D) ⇔ f (x) ∈ C ∪ D ⇔ (f (x) ∈ C) ∨ (f (x) ∈ D) ⇔ (x ∈ f −1 (C)) ∨ (x ∈ f −1 (D)) ⇔ x ∈ f −1 (C) ∪ f −1 (D). 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

45

Parte 2. Se puede probar la igualdad tambi´en en este caso: x ∈ f −1 (C ∩ D) ⇔ f (x) ∈ C ∩ D ⇔ (f (x) ∈ C) ∧ (f (x) ∈ D) ⇔ (x ∈ f −1 (C)) ∧ (x ∈ f − (D)) ⇔ x ∈ f −1 (C) ∩ f −1 (D).  Ejercicio. 7.13. Observar que al decir que una aplicaci´on f : X −→ Y tiene una inversa hemos dicho que existe una aplicaci´on g : Y −→ X verificando fg = 1Y y gf = 1X . No basta con solo una de las igualdades, ya que dada la aplicaci´on f : {1, 2} −→ {a} existe una aplicaci´on g : {a} −→ {1, 2} verificando fg = 1{a} , pero no es biyectiva. En efecto, es f´acil ver que no es una aplicaci´on inyectiva. ´ . ¡Estudiar bien el enunciado! S OLUCI ON



Relaciones de equivalencia y de orden Ejercicio. 7.14. Se considera el conjunto N \ {0} y la relaci´on aRb si blog(a)c = blog(b)c. (1) Demuestra que R es una relaci´on de equivalencia en N \ {0}. (2) Describe el conjunto cociente. ´ . Tenemos que blog(a)c es la parte entera del numero ´ S OLUCI ON log(a), utilizando la base decimal. (1) Es claro. ´ (2) Cada clase est´a determinada por un numero natural, as´ı la clase determinada por 0 es: {1, 2, 3, 4, 5, 6, 7, 8, 9}, la determinada por 1 es: {10, 11, . . . , 98, 99}, etc.  Ejercicio. 7.15. Se considera el conjunto N \ {0} y la relaci´on aRb si blog2 (a)c = blog2 (b)c. (1) Demuestra que R es una relaci´on de equivalencia en N \ {0}. ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

46 (2) Describe el conjunto cociente.

´ . Tenemos que blog(a)c es la parte entera del numero ´ S OLUCI ON log(a), utilizando la base decimal. (1) Es claro. ´ (2) Cada clase est´a determinada por un numero natural, as´ı la clase determinada por 0 es: {1}, la determinada por 1 es: {2, 3}, la determinad por 2 es: {4, 5, 6, 7}, etc.  Ejercicio. 7.16. Se considera el conjunto N \ {0} y la relaci´on aRb si blog(a)c ≤ blog(b)c. Demuestra que R no es una relaci´on de orden al no verifica la propiedad antisim´etrica. ´ . Es claro que blog(1)c = blog(2)c, luego 1R2 y 2R1, pero como 1 6= 2, resulta que R S OLUCI ON no verifica la propiedad antisim´etrica.  Ejercicio. 7.17. Dada una relaci´on R en un conjunto X decimos que R verifica la propiedad circular si si aRb y bRc, entonces cRa, para cada a, b, c ∈ X . Demuestra que R es una relaci´on de equivalencia en X si y solo si R verifica las propiedades reflexiva y circular. ´ . Hacer. S OLUCI ON Ejercicio. 7.18. Dado un conjunto X y un subconjunto A ⊆ X , se define una relaci´on en P(X ) mediante:



BRC si B ∩ A = C ∩ A, para cada B, C ∈ P(X ).

(1) Demuestra que R es una relaci´on de equivalencia en P(X ); (2) Demuestra que existe una biyecci´on entre P(X )/R y P(A). ´ . Hacer S OLUCI ON Ejercicio. 7.19. En el conjunto Z se define la relaci´on



aRb si a 2 − b 2 = a − b, para cada a, b ∈ Z.

19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

47

(1) Demuestra que R es una relaci´on de equivalencia, (2) Determina la clase de equivalencia de cada elemento a ∈ Z, (3) Describe el conjunto cociente.

´ . Hacer S OLUCI ON



Ejercicio. 7.20. Dado un conjunto X y dos relaciones R y S en X , se define una nueva relaci´on en X mediante: a(R ◦ S)b si existe x ∈ X tal que aRx y xSb.

(1) Demuestra que una relaci´on R verifica la propiedad transitiva si y solo si R ◦ R ⊆ R, (2) Demuestra que si R verifica la propiedad reflexiva, entonces R ⊆ R ◦ R,

´ . S OLUCI ON

(1) Si R verifica la propiedad transitiva y a(R ◦ R)b, entonces existe x ∈ X tal que aRx y xRb, luego aRb. Rec´ıprocamente, si aRb y bRc, entonces a(R ◦ R)c, y por tanto aRc, luego R verifica la propiedad transitiva. (2) Dados a, b ∈ X tales que aRb, como bRb, entonces a(R ◦ R)b.  Ejercicio. 7.21. Dado un conjunto X y dos relaciones de equivalencia R y S en X , demuestra que R ◦ S es de equivalencia si y solo si R ◦ S = S ◦ R. ´ . Hacer S OLUCI ON



Ejercicio. 7.22. Dado un conjunto X y dos relaciones de equivalencia R y S en X , demuestra que R ∪ S es de equivalencia si y solo si R ◦ S ⊆ R ∪ S y S ◦ R ⊆ R ∪ S. ´ . Hacer S OLUCI ON ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

 P. Jara

C AP. I. C ONJUNTOS , APLICACIONES Y RELACIONES

48

Cuantificadores Ejercicio. 7.23. Sea X = {1, a, z, 2}. Determinar el conjunto de partes de X . ´ . Los subconjuntos de X son: S OLUCI ON ∅, {1}, {2}, {a}, {z}, {1, 2}, {1, a}, {1, z}, {2, a}, {2, z}, {a, z} {1, 2, a}, {1, 2, z}, {1, a, z}, {2, a, z} {1, 2, a, z} Observar que en total hay 16 subconjuntos.



Ejercicio. 7.24. Dado un conjunto X y subconjuntos A, B, C ⊆ X , demuestra que se verifican las siguientes propiedades: (1) Si A M B = C, entonces A M C = B. (2) A ∪ B = B ∪ C si y solo si A M B ⊆ C.  A∪B =A∪C (3) Si , entonces B = C. A∩B =A∩C ´ . Hacer S OLUCI ON



M´etodos de demostraci´ on Ejercicio. 7.25. √ ´ ´ ´ racional. Demuestra que para cada numero primo p el numero real p no es un numero ´ . Es claro. S OLUCI ON



Ejercicio. 7.26. √ ´ ´ Demuestra que para cada par de numeros primos, distintos, p y q, el numero real pq no es ´ un numero racional. ´ . Es claro. S OLUCI ON



19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29

S EC . 7. E JERCICIOS

49

Ejercicio. 7.27. Se tiene una l´amina met´alica cuadrada de 70 cm. de lado y se golpea 50 veces con una martillo. Demuestra que al menos dos de los golpes deben estar a una distancia de 15 cm. ´ . Dibujamos en la l´amina ua trama formada por 49 celdas cuadradas de 10 cm. de S OLUCI ON lados. Como hay 49 celdas y hemos golpeada la l´amina met´alica 50 veces, al menos dos de los golpes se han dado en la misma celda (¡los bordes son parte de la celda!). Tenemos pues dos puntos en un cuadrado de 10 cm. de lado. Vamos a ver que estos puntos distan menos de 15 cm. Dados dos puntos A y B en un cuadrado de 10 cm. de lado, unimos estos por una l´ınea que cortar´ıa al borde en dos puntos A 0 y B 0 . Si A 0 y B 0 est´an en lados contiguos, entonces la distancia A 0 B 0 es menor que la diagonal del cuadrado, y lo mismo ocurre se est´an en lados opuestos. Por lo tanto la mayor distancia entre A 0 B 0 se produce cuando A 0 y B 0 son v´ertices opuestos. Esta distancia m´axima es: √ √ 10+ 102 = 200 = 14, 1cm. 

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

BIBLIOGRAF´IA

51

Bibliograf´ıa ´ [1] L. Merino, E. Santos, Algebra Lineal con m´etodos elementales, Thomson, 2006. [2] Anzola-Caruncho, Problemas de Algebra, Tomos 1 y 3. Alef. [3] J. de Burgos, Curso de Algebra y Geometr´ıa, Alhambra Universidad. [4] de Diego. Problemas de Algebra Lineal, Deimos. ˜ ıa Editorial Continental, 1982. I [5] Paul R. Halmos, Teor´ıa intuitiva de conjuntos, Compan´ [6] Lipschutz, Teor´ıa de Conjuntos y temas afines, McGraw-Hill. Serie Schaum. [7] Sigler, Algebra, Revert´e. [8] Rojo, Mart´ın, Ejercicios y Problemas de Algebra Lineal, McGraw-Hill [9] Strang, Algebra Lineal y sus Aplicaciones, Addison-Wesley Iberoamericana.

´ ALGEBRA Y ESTRUCTURAS DISCRETAS

P. Jara

´INDICE ALFAB ETICO ´

53

´Indice alfab´etico ∀, 30 ◦, 24 ⊆, 4 ⊂, 5 $, 5 *, 5 ∆, 17 ∃, 30 ∈, 3 6∈, 3 f −1 , 19 1X , 24 =, 4 6=, 5 [ ], 27 ¯, 27 ×, 18 P(X ), 9 ∪, 6 ∩, 6 ∅, 7 ∧, 12 ∨, 12 ¬, 12 =⇒, 14–15, 32 ⇐⇒, 12 aplicaci´on, 18 biyectiva, 24 identidad, 24 inversa, 25 inyectiva, 24 sobreyectiva, 24 biyecci´on, 24 ´ ALGEBRA Y ESTRUCTURAS DISCRETAS

cardinal de un conjunto, 10 infinito, 10 clase de equivalencia, 27 composici´on de aplicaciones, 24 conjunto, 3 cociente, 27 de las partes, 9 finito, 10 infinito, 10 parcialmente ordenado, 28 potencia, 9 vac´ıo, 7 cota inferior, 28 superior, 28 cuantificador existencial, 30 universal, 30 definici´on de conjunto por comprensi´on, 3 por extensi´on, 3 diagrama de Venn, 5 diferencia de subconjuntos, 10 sim´etrica, 17 elemento de un conjunto, 3 m´aximo, 28 m´ınimo, 28 maximal, 28 P. Jara

´INDICE ALFAB ETICO ´

54 minimal, 28 Existencia de complemento, 14 de elemento neutro, 13 funciones proposicionales, 30 grafo de aplicaci´on, 21 de una aplicaci´on, 21 de una relaci´on, 26 imagen de un elemento, 18 de un subconjunto, 19 de una aplicaci´on, 19 inversa, 19 ´ınfimo, 28 intersecci´on de subconjuntos, 6

propiedad circular, 46 proposici´on, 11 compuesta, 12 proposiciones equivalentes, 12 relaci´on, 25 de equivalencia, 27 de orden, 28 subconjunto, 4 complemento, 8 impropio, 5 propio, 5 trivial, 7 subconjuntos disjuntos, 7 distintos, 5 iguales, 4 supremo, 28 tautolog´ıa, 13

Ley de de Morgan, 14

uni´on de subconjuntos, 6

no pertenencia, 3 partici´on de un conjunto, 31 pertenencia, 3 primer elemento, 28 producto cartesiano, 18 Propiedad antisim´etrica, 26 asociativa, 13 conmutativa, 13 de absorci´on, 13 de idempotencia, 13 distributiva, 14 reflexiva, 25 sim´etrica, 25 transitiva, 26 19 de octubre de 2008

Curso 2008–2009. NOTAS DE TRABAJO, 29