TEORÍA DE CONJUNTOS

TEORÍA DE CONJUNTOS 

Clases y conjuntos 1.1. 

Construcción de clases Para empezar aclaremos que una noción “indefinida”no tiene propiedades, excepto aquellas que se le asignen explÍcitamente; por lo tanto, debemos enunciar como axiomas todas las propiedades elementales que esperamos que tengan las nociones indefinidas. En nuestro sistema de teor´ıa axiom´atica de conjuntos elegimos dos nociones indefinidas: la palabra clase y la relaci´on de pertenencia ∈. Todos los objetos de nuestra teor´ıa se llaman clases. Ciertas clases, que se llamar´an conjuntos, ser´an definidas posteriormente. Todo conjunto es una clase, pero no rec´ıprocamente; una clase que no es un conjunto se llama clase propia. Comentemos brevemente sobre el “significado”que le intentamos dar a dichas nociones. En la interpretaci´on pretendida de nuestro sistema axiom´atico, la palabra clase se entiende que refiere a cualquier colecci´on de objetos. No obstante, ciertas colecciones “excesivamente grandes”pueden formarse en teor´ıa ingenua de conjuntos (por ejemplo, la colecci´on de todos los x tales que x 6∈ x), las cuales conllevan a contradicciones tales como la paradoja de Russell. El t´ermino clase propia se entiende que refiere a estas colecciones “excesivamente grandes”; todas las dem´as colecciones son conjuntos. Si x y A son clases, la espresi´on x ∈ A se lee como “x es un elemento de A”, o “x pertenece a A”, o “x est´a en A”. Es conveniente escribir x 6∈ A por ”x no es un elemento de A”. Sea x una clase; si existe una clase A tal que x ∈ A, entonces a x se le llama un elemento. De aqu´ı en adelante usaremos las siguientes convenciones notacionales: 1 las letras min´usculas a, b, c, x, y, . . . s´olo ser´an usadas para designar elementos. As´ı, una letra may´uscula, tal como A, puede denotar tanto a un elemento como a una clase que no es un elemento, pero una letra min´uscula, tal como x, s´olo puede denotar a un elemento. Definici´on 1.1.1 Sean A y B clases; definimos A = B para significar que todo elemento de A es un elemento de B y viceversa. En s´ımbolos, A = B ssi x ∈ A ⇒ x ∈ B ∧ x ∈ B ⇒ x ∈ A. Hemos definido que dos clases son iguales si y s´olo si tienen los mismos elementos. Las clases que son iguales tienen otra propiedad: si x y y son clases iguales y x es un elemento de A, ciertamente esperaremos que y sea un elemento de A. Esta propiedad se enuncia como nuestro primer axioma: Axioma 1 Si x = y y x ∈ A, entonces y ∈ A. A este axioma se le llama axioma de extensi´on. Definici´on 1.1.2 Sean A y B clases; definimos A ⊆ B para significar que todo elemento de A es un elemento de B. En s´ımbolos: A ⊆ B ssi x ∈ A ⇒ x ∈ B. Si A ⊆ B, entonces decimos que A es una subclase de B. Definimos que A ⊂ B para significar que A ⊆ B y A 6= B; en este caso, decimos que A es una subclase estricta de B. Si A es una subclase de B y A es un conjunto, le llamaremos a A un subconjunto de B. Unas propiedades simples de la igualdad y la inclusi´on se dan en el siguiente teorema. Teorema 1.1.1 Para todas las clases A, B y C, lo siguiente se cumple: 1. A = A. 2. A = B ⇒ B = A. 3. A = B y B = C ⇒ A = C. 4. A ⊆ B y B ⊆ A ⇒ A = B. 5. A ⊆ B y B ⊆ C ⇒ A ⊆ C. Prueba: 1. La proposici´on x ∈ A ⇒ x ∈ A ∧ x ∈ A ⇒ x ∈ A es obviamente verdadera; as´ı, por la Definici´on 1.1.1, A = A. 2 2. Suponga que A = B; entonces x ∈ A ⇒ x ∈ B ∧ x ∈ B ⇒ x ∈ A; por la conmutatividad de la conjunci´on tenemos que x ∈ B ⇒ x ∈ A ∧ x ∈ A ⇒ x ∈ B; as´ı, por la Definici´on 1.1.1, B = A. 3. Suponga que A = B y B = C; entonces tenemos lo siguiente: x ∈ A ⇒ x ∈ B, x ∈ B ⇒ x ∈ A, x ∈ B ⇒ x ∈ C, x ∈ C ⇒ x ∈ B. De la primera y la tercera concluimos (dado que (((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)) es una tautolog´ıa) que x ∈ A ⇒ x ∈ C. De la segunda y la cuarta, por la conmutatividad de la conjunci´on y la tautolog´ıa anterior, concluimos que x ∈ C ⇒ x ∈ A. As´ı, por la Definici´on 1.1.1, A = C. 4. Ejercicio para el lector. 5. Ejercicio para el lector. De manera intuitiva sabemos que construimos clases enunciando una propiedad de objetos y formando la clase de los objetos que tengan dicha propiedad. Nuestro segundo axioma nos permite hacer clases de esta manera. Axioma 2 Sea P(x) una propiedad sobre x que puede expresarse enteramente en t´erminos de los s´ımbolos ∈, ∨, ∧, ¬,⇒, ∃, ∀, las variables x, y, z, A, B, C, . . . y par´entesis. Entonces existe una clase C que consiste de todos los elementos x que satisfacen la propiedad P(x). El Axioma 2 se llama axioma de construcci´on de clase. Debemos notar que el Axioma 2 nos permite formar la clase de todos los elementos x que satisfacen P(x), pero no la clase de todas las clases x que satisfacen P(x); esta definici´on es suficiente para eliminar las paradojas l´ogicas. Las paradojas sem´anticas se han evitado al admitir, en el Axioma 2, s´olo las propiedades P(x) que se puedan escribir completamente en t´erminos de los s´ımbolos ∈, ∨, ∧, ¬,⇒, ∃, ∀, par´entesis y variables. La clase C cuya existencia se da por cierta mediante el Axioma 2 se designa simb´olicamente como: C = {x|P(x)}. 3 Note que el uso de la x min´uscula no es accidental en la expresi´on {x|P(x)}, sino que es muy esencial. Recordemos que hemos acordado que las letras min´usculas x, y, . . . se usar´an para designar elementos. As´ı C = {x|P(x)}. asevera que C es la clase de todos los elementos x que satisfacen P(x). Ahora usaremos el axioma de construcci´on de clase para formar nuevas clases a partir de clases dadas. Definici´on 1.1.3 Sean A y B clases; la uni´on de A y B se define como la clase de todos los elementos que pertenecen a A, o a B, o a ambas A y B. En s´ımbolos, A ∪ B = {x|x ∈ A ∨ x ∈ B}. As´ı, x ∈ A ∪ B si y s´olo si x ∈ A ∨ x ∈ B. Definici´on 1.1.4 Sean A y B clases; la intersecci´on de A y B se define como la clase de todos los elementos que pertenecen tanto a A como a B. En s´ımbolos, A ∩ B = {x|x ∈ A ∧ x ∈ B}. As´ı, x ∈ A ∩ B si y s´olo si x ∈ A ∧ x ∈ B. Definici´on 1.1.5 Por la clase universal U nos referimos a la clase de todos los elementos. La existencia de la clase universal es una consecuencia del axioma de construcci´on de clase, ya que si tomamos a P(x) como la propiedad x = x, entonces el Axioma 2 garantiza la existencia de una clase que consiste de todos los elementos que satisfacen x = x; por el Teorema 1.1.1(1), todos los elementos est´an en esta clase. Definici´on 1.1.6 Por la clase vac´ıa ∅ nos referimos a la clase que no tiene elementos. La existencia de la clase vac´ıa es una consecuencia del axioma de construcci´on de clase; ya que el Axioma 2 garantiza la existencia de una clase que consiste de todos los elementos que satisfacen x 6= x; por el Teorema 1.1.1(1), esta clase no tiene elementos. Teorema 1.1.2 Para toda clase A lo siguiente se cumple: 1. ∅ ⊆ A. 2. A ⊆ U. Prueba: 4 1. Que ∅ ⊆ A significa que x ∈ ∅ ⇒ x ∈ A, lo cual siempre es cierto, ya que x ∈ ∅ es falso (la clase vac´ıa no tiene elementos) y falso implica cualquier cosa es siempre verdadero. 2. Si x ∈ A, entonces x es un elemento; as´ı x ∈ U. Definici´on 1.1.7 Si dos clases no tienen elementos en com´un se dice que son disjuntas. En s´ımbolos, A y B son disjuntas ssi A ∩ B = ∅. Definici´on 1.1.8 El complemento de una clase A es la clase de todos los elementos que no pertenecen a A. En s´ımbolos, A 0 = {x|x 6∈ A}. As´ı, x ∈ A0 si y s´olo si x 6∈ A. Ejercicio 1.1.1 Practique con los siguientes problemas. 1. Suponga que A ⊆ B y que C ⊆ D; pruebe que a) (A ∪ C) ⊆ (B ∪ D). b) (A ∩ C) ⊆ (B ∩ D). 2. Suponga que A = B y que C = D; pruebe que a) (A ∪ C) = (B ∪ D). b) (A ∩ C) = (B ∩ D). 3. Pruebe que si A ⊆ B, entonces B0 ⊆ A0 . 4. Pruebe que si A = B, entonces A0 = B0 . 5. Pruebe que si A = B y B ⊆ C, entonces A ⊆ C. 6. Pruebe que si A ⊂ B y B ⊂ C, entonces A ⊂ C. 5 1.2. Algebra de clases ´ Uno de los aspectos m´as interesantes y ´utiles sobre clases es que, bajo las operaciones de uni´on, intersecci´on y complemento, satisfacen ciertas leyes algebr´aicas a partir de las cuales podemos desarrollar un ´algebra de clases. En esta secci´on desarrollaremos las leyes b´asicas del ´algebra de clases. Recordemos que la palabra clase debe entenderse como cualquier colecci´on de objetos; as´ı, debemos entender que las leyes que aqu´ı se presentan se aplican a toda colecci´on de objetos; en particular, se aplican a conjuntos. Teorema 1.2.1 Si A y B son cualesquiera clases, entonces 1. A ⊆ A ∪ B y B ⊆ A ∪ B. 2. A ∩ B ⊆ A y A ∩ B ⊆ B. Prueba: 1. Para probar que A ⊆ A ∪ B debemos probar que x ∈ A ⇒ x ∈ A ∪ B: x ∈ A ⇒ x ∈ A ∨ x ∈ B recuerde que (P ⇒ (P ∨ Q)) es una tautolog´ıa ⇒ x ∈ A ∪ B por la Definici´on 1.1.3. An´alogamente se puede demostrar que B ⊆ A ∪ B. 2. Para probar que A ∩ B ⊆ A debemos probar que x ∈ A ∩ B ⇒ x ∈ A: x ∈ A ∩ B ⇒ x ∈ A ∧ x ∈ B por la Definici´on 1.1.4 ⇒ x ∈ A recuerde que ((P ∧ Q) ⇒ P) es una tautolog´ıa. An´alogamente se puede demostrar que A ∩ B ⊆ B. Teorema 1.2.2 Si A y B son clases entonces 1. A ⊆ B si y s´olo si A ∪ B = B. 2. A ⊆ B si y s´olo si A ∩ B = A. Prueba: 6 1. Asumamos primero que A ⊆ B; esto es, x ∈ A ⇒ x ∈ B. Entonces x ∈ A ∪ B ⇒ x ∈ A ∨ x ∈ B por la Definici´on 1.1.3 ⇒ x ∈ B ∨ x ∈ B ya que si Q ⇒ R entonces ((P ∨ Q) ⇒ (P ∨ R)) es una tautolog´ıa ⇒ x ∈ B ya que ((P ∨ P) ⇔ P) es una tautolog´ıa. As´ı, A ∪ B ⊆ B, pero por el Teorema 1.2.1(1) B ⊆ A ∪ B, consecuentemente A ∪ B = B. Reciprocamente, asumamos que A ∪ B = B. Nuevament 2. (A ∩ B) 0 = A0 ∪ B0 . Prueba: 1. Primero, x ∈ (A ∪ B) 0 ⇒ x 6∈ (A ∪ B) por la Definici´on 1.1.8 ⇒ x 6∈ A ∧ x 6∈ B (si x ∈ A ∨ x ∈ B, entonces x ∈ A ∪ B) ⇒ x ∈ A 0 ∧ x ∈ B 0 por la Definici´on 1.1.8 ⇒ x ∈ (A 0 ∩ B 0 ) por la Definici´on 1.1.4. Luego, x ∈ (A 0 ∩ B 0 ) ⇒ x ∈ A 0 ∧ x ∈ B 0 por la Definici´on 1.1.4 ⇒ x 6∈ A ∧ x 6∈ B por la Definici´on 1.1.8 ⇒ x 6∈ A ∪ B ⇒ x ∈ (A ∪ B) 0 por la Definici´on 1.1.8. 2. Ejercicio para el lector. Teorema 1.2.6 Para todas las clases A, B y C las siguientes se cumplen: 1. A ∪ B = B ∪ A. 2. A ∩ B = B ∩ A. 3. A ∪ A = A. 4. A ∩ A = A. 5. A∪(B ∪C) = (A∪B)∪C. 6. A∩(B ∩C) = (A∩B)∩C. 7. A∩(B ∪C) = (A ∩ B) ∪ (A ∩ C). 8. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Prueba: 1. x ∈ A ∪ B ⇒ x ∈ A ∨ x ∈ B por la Definici´on 1.1.3 ⇒ x ∈ B ∨ x ∈ A por la conmutatividad de la disyunci´on ⇒ x ∈ B ∪ A por la Definici´on 1.1.3. 2. Ejercicio para el lector. 3. Ejercicio para el lector. 4. Ejercicio para el lector. 8 5. x ∈ A ∪ (B ∪ C) ⇒ x ∈ A ∨ x ∈ B ∪ C por la Definici´on 1.1.3 ⇒ x ∈ A ∨ (x ∈ B ∨ x ∈ C) por la Definici´on 1.1.3 ⇒ (x ∈ A ∨ x ∈ B) ∨ x ∈ C por la asociatividad de la disyunci´on ⇒ x ∈ (A ∪ B) ∨ x ∈ C por la Definici´on 1.1.3 ⇒ x ∈ (A ∪ B) ∪ C por la Definici´on 1.1.3. 6. Ejercicio para el lector. 7. x ∈ A ∩ (B ∪ C) ⇒ x ∈ A ∧ x ∈ B ∪ C por la Definici´on 1.1.4 ⇒ x ∈ A ∧ (x ∈ B ∨ x ∈ C) por la Definici´on 1.1.3 ⇒ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) por la distribuci´on de la conjunci´on sobre la disyunci´on ⇒ x ∈ A ∩ B ∨ x ∈ A ∩ C por la Definici´on 1.1.4 ⇒ x ∈ (A ∩ B) ∪ (A ∩ C) por la Definici´on 1.1.3. 8. Ejercicio para el lector. Teorema 1.2.7 Para toda clase A, 1. A∪∅ = A. 2. A∩∅ = ∅. 3. A∪U = U. 4. A ∩ U = A. 5. U 0 = ∅. 6. ∅0 = U. 7. A ∪ A0 = U. 8. A ∩ A0 = ∅. Prueba: 1. Por el Teorema 1.1.2.(1) ∅ ⊆ A y en consecuencia al Teorema 1.2.2.(1) A ∪ ∅ = A. 2. Ejercicio para el lector. 3. Por el Teorema 1.1.2.(2) A ⊆ U y en consecuencia al Teorema 1.2.2.(1) A ∪ U = U. 4. Ejercicio para el lector. 5. Ejercicio para el lector. 9 6. Ejercicio para el lector. 7. Ejercicio para el lector. 8. Ejercicio para el lector. Las leyes del ´algebra de clases que hemos desarrollado nos permiten probar todas las propiedades elementales de clases sin referirnos a las definiciones de los s´ımbolos ∪, ∩, 0 y ⊆. El siguiente es un ejemplo de como se procede. Ejemplo 1.2.1 Pruebe que A ∩ (A0 ∪ B) = A ∩ B. Prueba: A ∩ (A 0 ∪ B) = (A ∩ A 0 ) ∪ (A ∩ B) por el Teorema 1.2.6.(7) = ∅ ∪ (A ∩ B) por el Teorema 1.2.7.(8) = A ∩ B por el Teorema 1.2.7.(1). La siguiente definici´on frecuentemente es ´util: La diferencia de dos clases A y B es la clase de todos los elementos que pertenecen a A pero que no pertenecen a B. En s´ımbolos, A − B = A ∩ B 0 . Ejemplo 1.2.2 Pruebe que A − B = B0 − A0 . Prueba: A − B = A ∩ B 0 por Definici´on de diferencia = B 0 ∩ A por el Teorema 1.2.6.(2) = B 0 ∩ (A 0 ) 0 por el Teorema 1.2.4 = B 0 − A 0 por la definici´on de diferencia. Es ´util notar que las propiedades que involucran inclusi´on (⊆), en lugar de igualdad, se pueden probar usando ´algebra de clases ayud´andose con el Teorema 1.2.2. Ejercicio 1.2.1 Use ´algebra de clases para demostrar lo siguiente: 10 1. (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C). 2. (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C). 3. Si A ∩ C = ∅ entonces A ∩ (B ∪ C) = A ∩ B. 4. Si A ∩ B = ∅ entonces A − B = A. 5. Si A ∩ B = ∅ y A ∪ B = C entonces A = C − B. 6. A ∩ (B − C) = (A ∩ B) − C. 7. (A ∪ B) − C = (A − C) ∪ (B − C). 8. A − (B ∪ C) = (A − B) ∩ (A − C). 9. A − (B ∩ C) = (A − B) ∪ (A − C). Ejercicio 1.2.2 Definimos la operaci´on + sobre clases como sigue: Si A y B son clases entonces: A + B = (A − B) ∪ (B − A). Pruebe lo siguiente: 1. A + B = B + A. 2. A + (B + C) = (A + B) + C. 3. A ∩ (B + C) = (A ∩ B) + (A ∩ C). 4. A + A = ∅. 5. A + ∅ = A Ejercicio 1.2.3 Pruebe lo siguiente: 1. Si A ∪ B = ∅ entonces A = ∅ y B = ∅. 2. A ∩ B0 = ∅ si y s´olo si A ⊆ B. 3. A + B = ∅ si y s´olo si A = B. 4. A ∪ C = B ∪ C si y s´olo si A + B ⊆ C. 5. (A ∪ C) + (B ∪ C) = (A + B) − C. Ejercicio 1.2.4 Use ´algebra de clases para probar que si A ⊆ B y C = B−A entonces A = B − C. 11 1.3. Pares ordenados y productos cartesianos Si a es un elemento podemos usar el axioma de construcci´on de clase para formar la clase {a} = {x|x = a}. Es f´acil ver que {a} contiene s´olo un elemento, llamado elemento a. A una clase que contiene un solo elemento se le llama solitaria. Si a y b son elementos podemos usar el axioma de construcci´on de clase para formar la clase {a, b} = {x|x = a ∨ x = b}. Claramente {a, b} contiene dos elementos, llamados los elementos a y b. Una clase que contiene exactamente dos elementos es llamada par desordenado, o simplemente una pareja. De manera an´aloga podemos formar las clases {a, b, c}, {a, b, c, d} y as´ı sucesivamente. En matem´aticas frecuentemente necesitamos formar las clases cuyos elementos son parejas. Para poder hacer esto leg´ıtimamente, necesitamos un nuevo axioma que garantice que si a y b son elementos entonces la pareja {a, b} es un elemento. Esto motiva nuestro siguiente axioma, al que se le suele llamar Axioma de apareamiento: Axioma 3 Si a y b son elementos entonces {a, b} es un elemento. Est´a claro que {a, a} = {a}; as´ı, al definir a = b en el Axioma 3, inmediatamente obtenemos que si a es un elemento entonces la solitaria {a} es un elemento. Teorema 1.3.1 Si {x, y} = {u, v} entonces o [x = u ∧ y = v] o [x = v ∧ y = u]. Prueba: Ejercicio para el lector. (Sugerencia: Considere separadamente los casos x = y y x 6= y. Luego use el Axioma 1.) Una noci´on importante en matem´aticas es la de un par ordenado de elementos. Intuitivamente, un para ordenado es una clase que consiste de dos elementos en un orden espec´ıfico. En efecto, el orden realmente no es esencial; lo que es esencial es que los pares ordenados tienen la siguiente propiedad. 12 Propiedad 1.3.1 Sean (a, b) y (c, d) pares ordenados. Si (a, b) = (c, d) entonces a = c y b = d. Nos gustar´ıa definir pares ordenados de tal manera que no sea necesario introducir una nueva noci´on indefinida de “orden”. Es un hecho interesante que, realmente, se puede lograr procediendo como sigue. Definici´on 1.3.1 Sean a y b elementos; el par ordenado (a, b) se define como la clase (a, b) = {{a}, {a, b}}. Por el Axioma 3, (a, b) se puede formar leg´ıtimamente y tambi´en es un elemento. Vale la pena notar que (b, a) = {{b}, {b, a}} = {{b}, {a, b}}. As´ı hay una clara distinci´on entre los dos posibles “ordenes”(a, b) y (b, a) ya que son dos clases distintas, resta probar que los pares ordenados, como han sido definidos, tienen la Propiedad 1.3.1. Teorema 1.3.2 Si (a, b) = (c, d) entonces a = c y b = d. Prueba: Suponga que (a, b) = (c, d); esto es, {{a}, {a, b}} = {{c}, {c, d}}. Por el Teorema 1.3.1, o [{a} = {c} ∧ {a, b} = {c, d}] o [{a} = {c, d} ∧ {a, b} = {c}]; consideraremos separadamente los dos casos. Caso 1 {a} = {c} y {a, b} = {c, d}. De {a} = {c} se sigue que a = c. De {a, b} = {c, d} y el Teorema 1.3.1 se sigue que o a = c y b = d, o a = d y b = c; en el primer subcaso hemos terminado; en el segundo subcaso como a = c tenemos entonces que b = c = a = d, con lo que terminamos el Caso 1. 13 Caso 2 {a} = {c, d} y {a, b} = {c}. Aqu´ı, c ∈ {c, d} y {c, d} = {a}, as´ı c ∈ {a}; por lo que c = a; an´alogamente, d = a. Tambi´en, b ∈ {a, b} y {a, b} = {c}, as´ı b ∈ {c}; por lo que b = c. De tal manera que a = b = c = d, terminando la prueba. Definici´on 1.3.2 El producto cartesiano de dos clases A y B es la clase de los pares ordenados (x, y) donde x ∈ A y y ∈ B. En s´ımbolos, A × B = {(x, y)|x ∈ A ∧ y ∈ B}. Las siguientes son propiedades simples del producto cartesiano. Teorema 1.3.3 Para todas las clases A, B, C y D, 1. A × (B ∩ C) = (A × B) ∩ (A × C). 2. A × (B ∪ C) = (A × B) ∪ (A × C). 3. (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D). Prueba: 1. (x, y) ∈ A × (B ∩ C) ⇔ x ∈ A ∧ y ∈ B ∩ C ⇔ x ∈ A ∧ y ∈ B ∧ y ∈ C ⇔ (x, y) ∈ A × B ∧ (x, y) ∈ A × C ⇔ (x, y) ∈ (A × B) ∩ (A × C). 2. Ejercicio para el lector. 3. (x, y) ∈ (A × B) ∩ (C × D) ⇔ (x, y) ∈ A × B ∧ (x, y) ∈ C × D ⇔ x ∈ A ∧ y ∈ B ∧ x ∈ C ∧ y ∈ D ⇔ x ∈ A ∩ C ∧ y ∈ B ∩ D ⇔ (x, y) ∈ (A ∩ C) × (B ∩ D). 14 Ejercicio 1.3.1 Pruebe que: 1. A × (B − D) = (A × B) − (A × D). 2. (A × B) ∩ (C × D) = (A × D) ∩ (C × B). 3. (A × A) ∩ (B × C) = (A ∩ B) × (A ∩ C). 4. (A × B) − (C × C) = [(A − C) × B] ∪ [A × (B − C)]. 5. (A × A) − (B × C) = [(A − B) × A] ∪ [A × (A − C)]. 6. A y B son disjuntas si y s´olo si para cualquier clase no vac´ıa C, A × C y B × C son disjuntas. 7. Si A y C son clases no vac´ıas, A ⊆ B y C ⊆ D si y s´olo si A×C ⊆ B×D. 8. Sean A, B, C y D clases no vac´ıas. A × B = C × D si y s´olo si A = C y B = D. 9. A × B y A0 × C son disjuntas. 10. B × A y C × A0 son disjuntas. 11. A × B = ∅ si y s´olo si A = ∅ o B = ∅. 12. Si a = {b} entonces b ∈ a. 13. x = y si y s´olo si {x} = {y}. 14. x ∈ a si y s´olo si {x} ⊆ a. 15. {a, b} = {a} si y s´olo si a = b. 16. La siguiente es una definici´on alternativa de par ordenado: (x, y) = {{x, ∅}, {y, {∅}}}. Use esta definici´on para probar que si (a, b) = (c, d) entonces a = c y b = d. 15 1.4. Gr´aficas Una clase de pares ordenados se llama una gr´afica. Dicho de otra manera, una gr´afica es una subclase arbitraria de U × U. Definici´on 1.4.1 Si G es una gr´afica entonces G−1 es la gr´afica definida mediante G −1 = {(x, y)|(y, x) ∈ G}. Definici´on 1.4.2 Si G y H son gr´aficas entonces G◦H es la gr´afica definida como sigue G ◦ H = {(x, y)|∃z  (x, z) ∈ H ∧ (z, y) ∈ G}. Las siguientes son propiedades b´asicas de gr´aficas. Teorema 1.4.1 Si G, H y J son gr´aficas entonces las siguientes propiedades se cumplen: 1. G ◦ (H ◦ J) = (G ◦ H) ◦ J. 2. (G−1 ) −1 = G. 3. (G ◦ H) −1 = H−1 ◦ G−1 . Prueba: 1. (x, y) ∈ (G ◦ H) ◦ J ⇔ ∃z  (x, z) ∈ J ∧ (z, y) ∈ G ◦ H ⇔ ∃w ∧ ∃z  (x, z) ∈ J ∧ (z, w) ∈ H ∧ (w, y) ∈ G ⇔ ∃w  (x, w) ∈ H ◦ J ∧ (w, y) ∈ G ⇔ (x, y) ∈ G ◦ (H ◦ J) 2. (x, y) ∈ (G −1 ) −1 ⇔ (y, x) ∈ G −1 ⇔ (x, y) ∈ G 3. (x, y) ∈ (G ◦ H) −1 ⇔ (y, x) ∈ G ◦ H ⇔ ∃z  (y, z) ∈ H ∧ (z, x) ∈ G ⇔ ∃z  (x, z) ∈ G −1 ∧ (z, y) ∈ H −1 ⇔ (x, y) ∈ H −1 ◦ G −1 16 Definici´on 1.4.3 Sea G una gr´afica. Por el dominio de G nos referimos a la clase dom G = {x|∃y  (x, y) ∈ G}, y por el rango de G nos referimos a la clase ran G = {y|∃x  (x, y) ∈ G}. En otras palabras, el dominio de G es la clase de todos los “primeros componenetes”de los elemento de G y el rango de G es la clase de todos los “segundos componentes”de los elementos de G. Teorema 1.4.2 Si G y H son gr´aficas, entonces 1. dom G = ran G−1 . 2. ran G = dom G−1 . 3. dom (G ◦ H) ⊆ dom H. 4. ran (G ◦ H) ⊆ ran G. Prueba: 1. x ∈ dom G ⇔ ∃y  (x, y) ∈ G ⇔ ∃y  (y, x) ∈ G −1 ⇔ x ∈ ran G−1 , 2. Ejercicio para el lector, 3. x ∈ dom (G ◦ H) ⇒ ∃y  (x, y) ∈ (G ◦ H) ⇒ ∃y∃z  (x, z) ∈ H ∧ (z, y) ∈ G ⇒ x ∈ dom H. 4. Ejercicio para el lector. Corolario 1.4.1 Sean G y H gr´aficas. Si ran H ⊆ dom G entonces dom (G◦ H) = dom H. Prueba: Ejercicio para el lector. Ejercicio 1.4.1 Proceda como se indica en cada inciso. 17 1. Sean G = {(b, b),(b, c),(c, c),(c, d)} y H = {(b, a),(c, b),(d, c)}. Encuentre G−1 , H−1 , G ◦ H, H ◦ G,(G ◦ H) −1 ,(G ∪ H) −1 , H−1 ◦ G. 2. Si G, H y J son gr´aficas, pruebe cada uno de los siguientes: a) (H ∪ J) ◦ G = (H ◦ G) ∪ (J ◦ G), b) (G − H) −1 = G−1 − H−1 , c) G ◦ (H ∩ J) ⊆ (G ◦ H) ∩ (G ◦ J), d) (G ◦ H) − (G ◦ J) ⊆ G ◦ (H − J). 3. Si G y H son gr´aficas, pruebe cada uno de los siguientes: a) (G ∩ H) −1 = G−1 ∩ H−1 , b) (G ∪ H) −1 = G−1 ∪ H−1 . 4. Si G, H, J y K son gr´aficas, pruebe: a) Si G ⊆ H y J ⊆ K, entonces G ◦ J ⊆ H ◦ K, b) G ⊆ H si y s´olo si G−1 ⊆ H−1 . 5. Si A, B y C son clases, pruebe cada uno de los siguientes: a) (A × B) −1 = B × A, b) Si A ∩ B 6= ∅, entonces (A × B) ◦ (A × B) = A × B, c) Si A y B son disjuntas, entonces (A × B) ◦ (A × B) = ∅, d) Si B 6= ∅, entonces (B × C) ◦ (A × B) = A × C. 6. Sean G y H gr´aficas, pruebe cada uno de los siguientes: a) Si G ⊆ A × B, entonces G−1 ⊆ B × A, b) Si G ⊆ A × B y H ⊆ B × C, entonces H ◦ G ⊆ A × C. 7. Si G y H son gr´aficas, pruebe cada uno de los siguientes: a) dom (G ∪ H) = (dom G) ∪ (dom H), 18 b) ran (G ∪ H) = (ran G) ∪ (ran H), c) dom G − dom H ⊆ dom (G − H), d) ran G − ran H ⊆ ran (G − H). 8. Sea G una gr´afica y sea B una subclase del dominio de G. Por la restricci´on de G a B nos referimos a la gr´afica G[B] = {(x, y)|(x, y) ∈ G ∧ x ∈ B}. Pruebe cada uno de los siguientes: a) G[B] = G ∩ (B × ran G), b) G[B∪C] = G[B] ∪ G[C] , c) G[B∩C] = G[B] ∩ G[C] , d) (G ◦ H)[B] = G ◦ H[B] . 9. Sea G una gr´afica y sea B una subclase del dominio de G. Usaremos el s´ımbolo G(B) para designar la clase G(B) = {y|∃x ∈ B  (x, y) ∈ G}. Pruebe cada uno de los siguientes: a) G(B) = ran G[B] , b) G(B ∪ C) = G(B) ∪ G(C), c) G(B ∩ C) = G(B) ∩ G(C), d) Si B ⊆ C, entonces G(B) ⊆ G(C). 1.5. Uni´on e intersecci´on generalizadas Considere la clase {A1, A2, . . . , An}; sus elementos est´an indexados por los n´umeros 1, 2, . . . , n. A tal clase frecuentemente se le llama familia indexada de clases; a los n´umeros 1, 2, . . . , n se les llama ´ındices y a la clase {1, 2, . . . , n} se le llama la clase ´ındice. Generalizando, frecuentemente consideramos una clase I cuyos elementos i, j, k, . . . sirven como ´ındices para designar a los elementos de una clase {Ai , Aj , Ak, . . .}. La clase {Ai , Aj , Ak, . . .} es llamada familia indexada de 19 clases, I es llamada su clase ´ındice, y los elementos de I son llamados ´ındices. Una notaci´on compacta que se usa frecuentemente para designar a la clase {Ai , Aj , Ak, . . .} es {Ai}i∈I As´ı, hablando informalmente, {Ai}i∈I es la clase de todas las clases Ai , con i variando en I. Observaci´on 1.5.1 La definici´on de una familia indexada de clases que hemos dado es intuitiva; descansa sobre la noci´on intuititva de indexaci´on. Esta defici´on intuitiva es adecuada en este momento; no obstante, para referencias futuras, damos ahora la definici´on formal del mismo concepto: Por una familia indexada de clases, {Ai}i∈I , nos referimos a una gr´afica G cuyo dominio es I; para cada i ∈ I definimos Ai mediante Ai = {x|(i, x) ∈ G}. Por ejemplo, considere {Ai}i∈I donde I = {1, 2}, A1 = {a, b} y A2 = {c, d}. Entonce, formalmente, {Ai}i∈I es la gr´afica G = {(1, a),(1, b),(2, c),(2, d)}. Si {Ai}i∈I es una familia indexada de clases tal que para cada i ∈ I, Ai es un elemento, entonces {Ai |i ∈ I} designar´a la clase cuyos elementos son todos los Ai , esto es, {Ai |i ∈ I} = {x|x = Ai para alg´un i ∈ I}. No obstante, seguiremos la notaci´on matem´atica usual y emplearemos las dos expresiones {Ai}i∈I y {Ai |i ∈ I} intercambiablemente. Definici´on 1.5.1 Sea {Ai}i∈I una familia indexada de clases. La uni´on de las clases Ai consiste de todos los elementos que pertenecen al menos a una clase Ai de la familia. En s´ımbolos, [ i∈I Ai = {x|∃j ∈ I  x ∈ Aj}. La intersecci´on de las clases Ai consiste de todos los elementos que pertenecen a toda clase Ai de la familia. En s´ımbolos, \ i∈I Ai = {x|∀i ∈ I, x ∈ Ai}. 20 Las siguientes son algunas propiedades b´asicas de las familias indexadas de clases. Teorema 1.5.1 Sea {Ai}i∈I una familia indexada de clases. 1. Si Ai ⊆ B para todo i ∈ I, entonces S i∈I Ai ⊆ B. 2. Si B ⊆ Ai para todo i ∈ I, entonces B ⊆ T i∈I Ai . Prueba: 1. Suponga que Ai ⊆ B para todo i ∈ I; ahora si x ∈ S i∈I Ai , entonces x ∈ Aj para alg´un j ∈ I, pero Aj ⊆ B, as´ı x ∈ B. As´ı S i∈I Ai ⊆ B. 2. Ejercicio para el lector. Teorema 1.5.2 (Leyes generalizadas de De Morgan). Sea {Ai}i∈I una familia indexada de clases. Entonces 1. (S i∈I Ai) 0 = T i∈I A0 i . 2. (T i∈I Ai) 0 = S i∈I A0 i . Prueba: 1. x ∈ ( [ i∈I Ai) 0 ⇔ x 6∈ [ i∈I Ai ⇔ ∀i ∈ I, x 6∈ Ai ⇔ ∀i ∈ I, x ∈ A 0 i ⇔ x ∈ \ i∈I A 0 i . 2. Ejercicio para el lector. Teorema 1.5.3 (Leyes distributivas generalizadas) Sean {Ai}i∈I y {Bj}j∈J familias indexadas de clases. Entonces 1. (S i∈I Ai) ∩ ( S j∈J Bj ) = S (i,j)∈I×J (Ai ∩ Bj ). 2. (T i∈I Ai) ∪ ( T j∈J Bj ) = T (i,j)∈I×J (Ai ∪ Bj ). 21 Prueba: 1. x ∈ ( [ i∈I Ai) ∩ ( [ j∈J Bj ) ⇔ x ∈ [ i∈I Ai ∧ x ∈ [ j∈J Bj ⇔ x ∈ Ah para alg´un h ∈ I ∧ x ∈ Bk para alg´un k ∈ J ⇔ x ∈ Ah ∩ Bk para alg´un (h, k) ∈ I × J ⇔ x ∈ [ (i,j)∈I×J (Ai ∩ Bj ). 2. Ejercicio para el lector. Un teorema concerniente a la uni´on de gr´aficas ser´a ´util en el siguiente cap´ıtulo. Teorema 1.5.4 Sea {Gi}i∈I una familia de gr´aficas. Entonces 1. dom( S i∈I Gi) = S i∈I (dom Gi). 2. ran( S i∈I Gi) = S i∈I (ran Gi). Prueba: 1. x ∈ dom( [ i∈I Gi) ⇔ ∃y  (x, y) ∈ [ i∈I Gi , por 1.4.3 ⇔ ∃y  (x, y) ∈ Gj para alg´un j ∈ I, por 1.5.1 ⇔ x ∈ dom Gj para alg´un j ∈ I, por 1.4.3 ⇔ x ∈ [ i∈I (dom Gi), por 1.5.1. 2. Ejercicio para el lector. Una notaci´on variante para la uni´on e intersecci´on de una familia de clases es ´util a veces. Si A es una clase (sus elementos son necesariamente clases), definimos la uni´on de A, o la uni´on de los elementos de A, como la uni´on de todas las clases que son elementos de A. En s´ımbolos, 22 Definici´on 1.5.2 [ A∈A A = {x|x ∈ A para alg´un A ∈ A} En otras palabras, x ∈ S A∈A A si y s´olo si existe una clase A tal que x ∈ A y A ∈ A. An´alogamente, definimos la intersecci´on de los elementos de A, como la intersecci´on de todas las clases que son elementos de A. En s´ımbolos, Definici´on 1.5.3 \ A∈A A = {x|x ∈ A para todo A ∈ A} Ejemplo 1.5.1 Sea A = {K, L, M}, donde K = {a, b, d}, L = {a, c, d} y M = {d, e}. Entonces [ A∈A A = {a, b, c, d, e} y \ A∈A A = {d} . Observaci´on 1.5.2 Es pr´actica frecuente, en la literatura de teor´ıa de conjuntos, escribir [ A en lugar de [ A∈A A y \ A en lugar de \ A∈A A Ocasionalmente seguiremos esta pr´actica. Ejercicio 1.5.1 Proceda como se indica en cada inciso. 1. Sean {Ai}i∈I y {Bi}i∈I dos familias de clases con la misma clase ´ındice I. Suponga que ∀i ∈ I, Ai ⊆ Bi , pruebe que: a) S i∈I Ai ⊆ S i∈I Bi . b) T i∈I Ai ⊆ T i∈I Bi . 2. Sean {Ai}i∈I y {Bj}j∈J familias indexadas de clases. Pruebe lo siguiente. a) (S i∈I Ai) × ( S j∈J Bj ) = S (i,j)∈I×J (Ai × Bj ). 23 b) (T i∈I Ai) × ( T j∈J Bj ) = T (i,j)∈I×J (Ai × Bj ). 3. Sean {Ai}i∈I y {Bj}j∈J familias indexadas de clases. Suponga que ∀i ∈ I, ∃j ∈ J  Bj ⊆ Ai . Pruebe que \ j∈J Bj ⊆ \ i∈I Ai . 4. Sean a = {u, v, w}, b = {w, x}, c = {w, y}, r = {a, b}, s = {b, c} y p = {r, s}. Encuentre las clases: ∪(∪p), ∩(∩p), ∪(∩p) y ∩(∪p). 5. Pruebe que ∩(A ∪ B) = (∩A) ∩ (∩B). 1.6. Conjuntos Indudablemente, todo lo que hemos dicho en las p´aginas anteriores es muy familiar al lector. Aunque dijimos clase donde el lector est´a m´as acostumbrado a oir conjunto, es obvio que la “uni´on” e “intersecci´on” que hemos definido son precisamente las familiares uni´on e intersecci´on de conjuntos, el “producto Cartesiano” es exactamente el producto Cartesiano usual de conjuntos y similarmente para los otros conceptos introducidos. En este punto, parece como si todo lo que estamos acostumbrados a hacer con conjuntos se puede hacer con clases. As´ı, el lector muy bien prodr´ıa preguntar, “¿por qu´e molestarse en distinguir entre clases y conjuntos? ¿Por qu´e no desarrollar toda la matem´atica en t´erminos de clases?” Ya que, como hemos dicho, una clase significa “cualquier colecci´on de elementos”, ¿por qu´e no simplemente le llamamos a una clase un conjunto, y acabamos de una vez? La respuesta a esta pregunta es de gran importancia; el principal prop´osito de esta secci´on es explicar por qu´e queremos distinguir entre clases y conjuntos. Primero, notemos que el axioma de construcci´on de clases (Axioma A2) nos permite formar la clase de todos los elementos que satisfacen una propiedad dada; pero no nos permite formar la clase de todas las clases que satisfacen una propiedad dada. La razon de esta limitaci´on es obvia: si pudieramos formar la clase de todas las clases que satisfacen cualquier propiedad dada, entonces podriamos formar la “clase de Russell” de todas las clases que no son elementos de si mismas, esto nos dar´ıa la paradoja de Russell. 24 Despu´es, notemos que en matem´atica frecuentemente necesitamos formar conjuntos de conjuntos particulares. Unos pocos ejemplos que vienen a la mente son los siguientes: El conjunto de todos los intervalos cerrados [a, b] de n´umeros reales. El conjunto de todas las secuencias convergentes de n´umeros reales. El conjunto de todas las l´ıneas en el plano (donde cada l´ınea se considera como un conjunto de puntos). Veamos m´as de cerca el primer ejemplo; en una discusi´on en c´alculo elemental, nos sentiriamos perfectamente libres de decir “A consiste de todos los conjuntos que son intervalos cerrados [a, b] de n´umeros reales.” Ahora si los “conjuntos” no fueran diferentes de las “clases” entonces, por el p´arrafo precedente, no podriamos formar A. Esto ser´ıa una restricci´on intolerable a nuestra libertad de operar conjuntos en matem´aticas. Recapitulemos: La noci´on de clase es atractiva por su simplicidad intuitiva y generalidad; no obstante, existe un serio inconveniente al tratar con clases, a saber que no es permisible [para una propiedad arbitraria P(X)] formar la “clase de todas las clases X que satisfacen P(X)”. Esto ser´ıa una restricci´on intolerable a nuestra libertad de acci´on si fueramos a basar la matem´atica en clases. En su lugar, basamos la matem´atica en conjuntos; el concepto de un conjunto es algo m´as estrecho que el de una clase; los conjuntos ser´an definidos de tal manera, no obstante, que para cualquier propiedad P(X) sea leg´ıtimo formar la clase de todos los conjuntos que satisfacen P(X). As´ı, la libertad que requerimos nos es restaurada, siempre y cuando estemos dispuestos a tratar con conjuntos m´as que con la noci´on m´as amplia de clase. Estamos m´as que dispuestos a hacer esto, ya que, como seremos capaces de mostrar, todas las clases con las que tratamos en matem´aticas son conjuntos. Ahora, ¿c´omo deben ser definidos los conjuntos? Para responder esta pregunta, es esencial que recordemos, una vez m´as, que estamos buscando una manera de definir conjuntos que legitime formar la clase de todos los conjuntos X que satisfacen cualquier propiedad P(X). Una respuesta obvia es identificar conjuntos con elementos: sea un conjunto la misma cosa que un elemento. Entonces el Axioma A2 ciertamente nos permitir´a formar la clase de todos los conjuntos X que satisfacen la propiedad P(X). Esta respuesta simple es, en efecto, la ´unica que ha sido adoptada por la mayor´ıa de los matem´aticos. La usaremos aqu´ı, as´ı, 25 Definici´on 1.6.1 Por un conjunto se entiende a cualquier clase que es un elemento de una clase. Esta definici´on se admite por nuestra percepci´on intuitiva de lo que un conjunto debe ser. Por que si A, B, C, . . . son conjuntos, es perfectamente razonable que deberiamos ser capaces de formar la clase {A, B, C, . . .} cuyos elementos son A, B, C, . . .. En otras palabras, muy ciertamente esperariamos que todo conjunto sea un elemento. Lo opuesto es igualmente razonable: porque si A no es un conjunto, entonces A es una clase propia, y anteriormente hemos visto que para evitar contradicciones, las clases propias no deben ser elementos de cosa alguna. As´ı, si A no es un conjunto, entonces A no es un elemento. En el resto de esta secci´on, estableceremos los axiomas b´asicos que tratan con conjuntos. El prop´osito principal de estos axiomas es garantizar que cuando las operaciones usuales de teor´ıa de conjuntos son aplicadas a conjuntos, el resultado, cada vez, es un conjunto. Primero, notemos que el Axioma de Apareamiento, nuestro Axioma 3, puede ser restablecido as´ı: Axioma 4 Si a y b son conjuntos, entonces {a, b} es un conjunto. Ahora, si B es un conjunto y A ⊆ B, uno razonablemente esperar´ıa que A sea un conjunto. Este es el contenido de nuestro siguiente axioma, llamado el Axioma de Subconjuntos. Axioma 5 Toda subclase de un conjunto es un conjunto. Por el Teorema 1.2.1(2), A ∩ B ⊆ A; as´ı, por el Axioma 5, si A es un conjunto, entonces A ∩ B es un conjunto. En particular, la intersecci´on de cualesquiera dos conjuntos es un conjunto. La uni´on de “no demasiados” conjuntos debe ser un conjunto. Esto es garantizado por el siguiente axioma, llamado el Axioma de Uniones: Axioma 6 Si A es un conjunto de conjuntos, entonces S A∈A A es un conjunto. Si A y B son conjuntos, entonces, por el Axioma 4, {A, B} es un conjunto; inmediatamente se sigue de la Definici´on 1.5.2 que S X∈{A,B} X = A ∪ B; as´ı, por el Axioma 6, A ∪ B es un conjunto. Esto muestra que la uni´on de dos conjuntos es un conjunto. 26 Observaci´on 1.6.1 Por el Axioma 4, todo doble es un conjunto. A´un m´as, si hacemos a = b en el Axioma 4, todo soltero es un conjunto. Ya que la uni´on de dos conjuntos es un conjunto, se sigue que toda clase de tres elementos es un conjunto, toda clase de cuatro elementos es un conjunto y as´ı sucesivamente. Por ello, en un sentido intuitivo, toda clase finita es un conjunto. A continuaci´on, estableceremos que si A es un conjunto, entonces la clase de todos los subconjuntos de A es un conjunto. Empezamos con una definici´on. Definici´on 1.6.2 Sea A un conjunto, por el conjunto potencia de A nos referimos a la clase de todos los subconjuntos de A. En s´ımbolos, el conjunto potencia de A es la clase P(A) = {B|B ⊆ A}. Note que por el Axioma 5, P(A) es la clase de todos los conjuntos B que satisfacen B ⊆ A. Por la Definici´on 1.6.1 y el Axioma 2, es leg´ıtimo formar esta clase. El siguiente es llamado el Axioma de Conjuntos Potencia: Axioma 7 Si A es un conjunto, entonces P(A) es un conjunto. Ejemplo 1.6.1 Si A = {a, b}, entonces P(A) = {∅, {a}, {b}, {a, b}}. De todo lo que hemos dicho hasta aqu´ı, a´un no se sigue que existe alg´un conjunto. Para llenar este vac´ıo, establecemos un axioma temporal, el cual ser´a sustituido por el Axioma A9: T La clase vac´ıa es un conjunto. De aqu´ı en adelante nos referiremos a ∅ como el conjunto vac´ıo. A partir del Axioma T, junto con A3 y A5, podemos inferir la existencia de una gran cantidad de conjuntos. Tenemos al conjunto vac´ıo, ∅; tenemos solteros tales como {∅}, {{∅}}, etc.; tenemos dobles tales como {∅, {∅}}, formados por cualesquiera dos de los anteriores. Similarmente, tomando repetidamente uniones de los anteriores, podemos formar conjuntos con cualquier n´umero finito de elementos. 27 Observaci´on 1.6.2 Una consecuencia importante del Axioma A6 es la siguiente. Si A es un conjunto, entonces claramente B = {X|X ⊆ A ∧ P(X)} es la clase de todos los subconjuntos de A los cuales satisfacen la propiedad P; por el Axioma A4, el Axioma A2 puede usarse leg´ıtimamente para forma la clase B. Ahora si X ∈ B, entonces X es un subconjunto de A, as´ı X ∈ P(A); as´ı B ⊆ P(A). Pero por el Axioma A6, P(A) es un conjunto, as´ı por el Axioma A4, B es un conjunto. Podemos resumir como sigue: si A es un conjunto y P(X) es una propiedad de X, entonces la clase de todos los subconjuntos de A que satisfacen P(X) es un conjunto. Teorema 1.6.1 Si A y B son conjuntos, entonces A × B es un conjunto. Prueba: Sean A y B conjuntos. Por el Axioma A5, A∪B es un conjunto; por el Axioma A6, P(A∪B) es un conjunto; finalmente, de nuevo por el Axioma A6, P[P(A ∪ B)] es un conjunto. Probemos que A × B ⊆ P[P(A ∪ B)] y se seguir´a, por el Axioma A4, que A × B es un conjunto. Sea (x, y) ∈ A × B. Por 1.3.1, (x, y) = {{x}, {x, y}}. Ahora x ∈ A ∪ B, as´ı {x} ⊆ A ∪ B, as´ı {x} ∈ P(A ∪ B). Similarmente, x ∈ A ∪ B y y ∈ A ∪ B, as´ı {x, y} ⊆ A ∪ B, luego {x, y} ∈ P(A ∪ B). Hemos demostrado que {x} y {x, y} son elementos de P(A ∪ B), por lo tanto {{x}, {x, y}} ⊆ P(A ∪ B) se sigue que {{x}, {x, y}} ∈ P[P(A ∪ B)] esto es (x, y) ∈ P[P(A ∪ B)]. As´ı A × B ⊆ P[P(A ∪ B)]. Se sigue del Teorema 1.6.1 y el Axioma A4 que si A y B son conjuntos, entonces cualquier gr´afica G ⊆ A × B es un conjunto. Es f´acil mostrar que si G es un conjunto, entonces dom G y ran G son conjuntos. Usando este hecho, uno puede mostrar f´acilmente que si G y H son conjuntos, entonces G ◦ H y G−1 son conjuntos. 28 Cap´ıtulo 2 Funciones 2.1. Introducci´on El concepto de funci´on es una de las ideas m´as b´asicas y se encuentra en casi cualquier discusi´on matem´atica. Generalmente una funci´on se define como sigue: Si A y B son clases, entonces una funci´on de A a B es una regla que le asigna a cada elemento x ∈ A un ´unico elemento y ∈ B; para indicar esta conexi´on entre x y y usualmente escribimos y = f(x). Por ejemplo, considere la funci´on y = sin x; si tomamos a A como el conjunto de los n´umeros reales y a B como el intervalo cerrado [−1, 1], entonces es f´acill ver que y = sin x es uan regla que le asigna a todo n´umero x ∈ A un ´unico n´umero y ∈ B. La gr´afica de una funci´on se define como sigue: Si f es una funci´on de A a B, entonces la gr´afica de f es la clase de todos los pares ordenados (x, y) tal que y = f(x). Por ejemplo, sean A = {a, b, c}, B = {d, e} y f la funci´on definida por la siguiente tabla: x f(x) a d b e c d La gr´afica de f es {(a, d),(b, e),(c, d)}. Claramente, podemos usar la informaci´on contenida en la tabla para construir la gr´afica de f; tambi´en podemos operar de otra manera, esto es, podemos usar la informaci´on contenida en la gr´afica para construir la tabla de 29 f. As´ı, una funci´on f determina completamente a su gr´afica, e inversamente, una gr´afica determina completamente a su funci´on. De tal manera que no hay necesidad de distinguir entre una funci´on y su gr´afica. Dado que una funci´on y su gr´afica son esencialmente una y la misma cosa, podemos, si queremos, definir que una funci´on es una gr´afica. Al hacerlo as´ı ganaremos una importante ventaja, a saber, evitamos tener que introducir la palabra regla como un nuevo concepto indefinido de teor´ıa de conjuntos. Por esta raz´on es costumbre, en tratamientos rigurosos de matem´aticas, introducir la noci´on de funci´on via la de gr´afica. Seguiremos este procedimiento aqu´ı. 2.2. Conceptos y definiciones fundamentales Empecemos dando nuestra definici´on “oficial” de funci´on. Definici´on 2.2.1 Una funci´on de A a B es un triple1 de objetos < f, A, B >, donde A y B son clases y f es una subclase de A × B con las siguientes propiedades: F1 ∀x ∈ A, ∃y ∈ B tal que (x, y) ∈ f. F2 Si (x, y1) ∈ f y (x, y2) ∈ f entonces y1 = y2. Se acostumbra escribir f : A → B en lugar de < f, A, B >. En aplicaciones matem´aticas ordinarias, toda funci´on f : A → B es una funci´on de un conjunto A a un conjunto B. No obstante, el concepto intuitivo de funci´on de A a B se aplica a cualesquiera dos colecciones A y B, sin importar que A y B sean conjuntos o clases propias, es natural dar la definici´on de una funci´on en su forma m´as general, por ello se estableci´o que A y B son cualesquiera clases. Una vez m´as, todo conjunto es una clase, as´ı todo lo que tenemos que decir sobre funciones de una clase A a una clase B se aplica, en particular, a funciones de un conjunto A a un conjunto B. 1Si f, A y B no son todos conjuntos, el triple ordenado < f, A, B > se puede definir, formalmente, as´ı: < f, A, B >= (f × {∅}) ∪ (A × {{∅}}) ∪ (B × {{{∅}}}). 30 Sea f : A → B una funci´on; si (x, y) ∈ f decimos que y es la imagen de x (con respecto a f); tambi´en decimos que x es la preimagen de y (con respecto a f); tambi´en se dice que f mapea x sobre y y lo simbolizamos mediante x f 7→ y. As´ı, F1 enuncia que todo elemento x ∈ A tiene una imagen y ∈ B. F2 enuncia que si x ∈ A, entonces la imagen de x es ´unica; porque si (x, y1) ∈ f y (x, y2) ∈ f, esto es, tanto y1 como y2 son im´agenes de x, entonces F2 dicta que y1 = y2. Se sigue que F1 y F2 combinadas enuncian que: Definici´on 2.2.2 Todo elemento x ∈ A tiene una imagen determinada ´unicamente y ∈ B. Teorema 2.2.1 Sean A y B clases y sea f una gr´afica. Entonces f : A → B es una funci´on si y s´olo si: I) F2 se cumple, II) dom f = A y III) ran f ⊆ B. Prueba: (si) Suponga que f : A → B es una funci´on; por 2.2.1, F2 se cumple. A´un m´as, a) x ∈ dom f ⇒ ∃y  (x, y) ∈ f, por 1.4.3 ⇒ (x, y) ∈ A × B, porque f ⊆ A × B, por 2.2.1 ⇒ x ∈ A, por 1.3.2. b) x ∈ A ⇒ ∃y ∈ B  (x, y) ∈ f por F1 ⇒ x ∈ dom f, por 1.4.3. 31 c) y ∈ ran f ⇒ ∃x  (x, y) ∈ f, por 1.4.3 ⇒ (x, y) ∈ A × B, porque f ⊆ A × B, por 2.2.1 ⇒ y ∈ B, por 1.3.2. Por a) y b), dom f = A; por c), ran f ⊆ B. As´ı 2.2.1.I, 2.2.1.II y 2.2.1.III se cumplen. (s´olo si) Rec´ıprocamente, suponga que 2.2.1.I, 2.2.1.II y 2.2.1.III se cumplen. Tenemos: a) (x, y) ∈ f ⇒ x ∈ dom f y y ∈ ran f, por 1.4.3 ⇒ x ∈ A y y ∈ B, por 2.2.1.II y 2.2.1.III ⇒ (x, y) ∈ A × B, por 1.3.2. b) Sea x un elemento arbitrario de A. Por 2.2.1.II, x ∈ dom f; as´ı ∃y  (x, y) ∈ f; pero y ∈ ran f, as´ı por 2.2.1.III, y ∈ B. Esto prueba que F1 se cumple. Por 2.2.1.I, F2 se cumple; as´ı, por la Definici´on 2.2.1, f : A → B es una funci´on. Corolario 2.2.1 Sea f : A → B una funci´on; si C es cualquier clase tal que ran f ⊆ C entonces f : A → C es una funci´on. Prueba: Si f : A → B es una funci´on, entonces por el Teorema 2.2.1, F2 se cumple y dom f = A; as´ı, si ran f ⊆ C, entonces por el Teorema 2.2.1, f : A → C es una funci´on. Sea f : A → B una funci´on y sea x ∈ A; se acostumbra usar el s´ımbolo f(x) para designar la imagen de x. As´ı, y = f(x) tiene el mismo significado que (x, y) ∈ f. Usando esta convenci´on, las condiciones F1 y F2 toman la forma: F1 ∀x ∈ A, ∃y ∈ B, y = f(x). F2 Si y1 = f(x) y y2 = f(x) entonces y1 = y2. 32 Teorema 2.2.2 Sean f : A → B y g : A → B funciones. Entonces f = g si y s´olo si f(x) = g(x), ∀x ∈ A. Prueba: Primero, asumamos que f = g. Entonces, para un x ∈ A arbitrario, y = f(x) ⇔ (x, y) ∈ f ⇔ (x, y) ∈ g ⇔ y = g(x); as´ı, f(x) = g(x). Rec´ıprocamente, asuma que f(x) = g(x), ∀x ∈ A. Entonces (x, y) ∈ f ⇔ y = f(x) ⇔ y = g(x) ⇔ (x, y) ∈ g; as´ı, f = g. Funciones Inyectivas, Sobreyectivas y Biyectivas Las siguientes definiciones son de gran importancia en el estudio de funciones. Definici´on 2.2.3 Una funci´on f : A → B se dice que es inyectiva si tiene la siguiente propiedad: INJ Si (x1, y) ∈ f y (x2, y) ∈ f, entonces x1 = x2. Note que INJ simplemente enuncia que si y es cualquier elemento de B, entonces y no tiene m´as de una preimagen; porque si (x1, y) ∈ f y (x2, y) ∈ f, esto es, si x1 y x2 son ambos preim´agenes de y, entonces INJ dicta que x1 = x2. Usando nuestra notaci´on para im´agenes podemos escribir INJ como: si f(x1) = f(x2) entonces x1 = x2. Definici´on 2.2.4 Una funci´on f : A → B se dice que es sobreyectiva si tiene la siguiente propiedad: SURJ ∀y ∈ B, ∃x ∈ A  y = f(x). La condici´on SURJ enuncia que todo elemento de B es la imagen de alg´un elemento de A, esto es, B ⊆ ran f, pero por el Teorema 2.2.1-III ran f ⊆ B, as´ı f : A → B es sobreyectiva si y s´olo si ran f = B. 33 Definici´on 2.2.5 Una funci´on f : A → B se dice que es biyectiva si es inyectiva y sobreyectiva. Decir que f : A → B es inyectiva es decir que todo elemento de B es la imagen de no m´as de un elemento de A; decir que f es sobreyectiva es decir que todo elemento de B es la imagen de al menos un elemento de A; as´ı, decir que f es biyectiva es decir que todo elemento de B es la imagen de exactamente un elemento de A. En otras palabras, si f : A → B es una funci´on biyectiva, todo elemento de A tiene exactamente una imagen en B y todo elemento de B tiene exactamente un preimagen en A; as´ı todos los elementos de A y todos los elementos de B est´an asociados en pares; por esta raz´on, si f es biyectiva, a veces se le llama correspondencia uno-a-uno entre A y B. Definici´on 2.2.6 Si existe una funci´on biyectiva f : A → B entonces decimos que A y B est´an en correspondencia uno-a-uno. Ejemplos de funciones Ejemplo 2.2.1 Funci´on Identidad. Sea A una clase, por la funci´on identidad sobre A nos referimos a la funci´on IA : A → A dada por IA(x) = x, ∀x ∈ A. En otras palabras, IA = {(x, x)|x ∈ A}. IA claramente es inyectiva, suponga que IA(x) = IA(y), por definici´on IA(x) = x y IA(y) = y, as´ı x = y; es decir, INJ se cumple. IA es sobreyectiva porque, obviamente, el rango de IA es A. As´ı, IA es biyectiva. Ejemplo 2.2.2 Funci´on constante. Sean A y B clases, y sea b un elemento de B. Por la funci´on constante Kb nos referimos a la funci´on Kb : A → B dada por Kb(x) = b, ∀x ∈ A. En otras palabras, Kb = {(x, b)|x ∈ A}. Note que si A tiene m´as de un elemento, Kb no es inyectiva; si B tiene m´as de un elemento, Kb no es sobreyectiva. 34 Ejemplo 2.2.3 Funci´on inclusi´on Sea A una clase y B una subclase de A. Por la funci´on inclusi´on de B en A nos referimos a la funci´on EB : B → A dada por EB(x) = x, ∀x ∈ B. Note que si B = A, la funci´on inclusi´on coincide con la funci´on identidad IA. Por el argumento usado en el ejemplo 2.2.1, EB es inyectiva; no obstante, si B 6= A, entonces EB no es sobreyectiva. Ejemplo 2.2.4 Funci´on caracter´ıstica. Sea 2 que designa a una clase con dos elementos, digamos que a la clase {0, 1}. si A es una clase y B es una subclase de A, la funci´on caracter´ıstica de B en A es la funci´on CB : A → 2 dada por CB(x) = ( 0 si x ∈ B, 1 si x 6∈ B, ∀x ∈ A. As´ı CB mapea todo elemento de B sobre 0 y todo elemento de A − B sobre 1. Ejemplo 2.2.5 Restricci´on de una funci´on. Sea f : A → B una funci´on y sea C una subclase de A. Por la restricci´on de f a C nos referimos a la funci´on f[C] : C → B dada por f[C](x) = f(x), ∀x ∈ C. Para decirlo de otra manera, f[C] = {(x, y)|(x, y) ∈ f ∧ x ∈ C}. Note que f[C] ⊆ f. Las restricciones de funciones tienen las siguientes propiedades, que nos ser´an ´utiles posteriormente. Teorema 2.2.3 Si f : B ∪ C → A es una funci´on entonces f = f[B] ∪ f[C] . La prueba de este teorema simple se deja al lector. Teorema 2.2.4 Sean f1 : B → A y f2 : C → A funciones donde B ∩C = ∅. Si f = f1 ∪ f2 entonces lo siguiente se cumple: I) f : B ∪ C → A es una funci´on. II) f1 = f[B] y f2 = f[C] . 35 III) Si x ∈ B entonces f(x) = f1(x) y si x ∈ C entonces f(x) = f2(x). Prueba: Empezaremos probando las siguientes dos relaciones. a) (x, y) ∈ f y x ∈ B ⇔ (x, y) ∈ f1. b) (x, y) ∈ f y x ∈ C ⇔ (x, y) ∈ f2, Si (x, y) ∈ f1, entonces x ∈ B ya que dom f1 = B, y (x, y) ∈ f ya que f = f1 ∪ f2. Rec´ıprocamente, suponga (x, y) ∈ f y x ∈ B: (x, y) ∈ f implica que (x, y) ∈ f1 o (x, y) ∈ f2; si (x, y) ∈ f2, entonces x ∈ C (porque dom f2 = C), lo cual es imposible ya que x ∈ B y B ∩C = ∅, as´ı, (x, y) ∈ f1. Esto prueba a), la prueba de b) es an´aloga. Ahora probemos que c) dom f = B ∪ C y ran f ⊆ A. En verdad, por el teorema 1.5.4, dom(f1 ∪ f2) = dom f1 ∪ dom f2 = B ∪ C, y ran(f1 ∪ f2) = ran f1 ∪ ran f2 ⊆ A. Nuestro siguiente paso ser´a probar que d) f satisface la condici´on F2. Suponga que (x, y1) ∈ f y (x, y2) ∈ f; ahora x ∈ dom f, as´ı por c), x ∈ B o x ∈ C. Si x ∈ B, entonces, por a), (x, y1) ∈ f1 y (x, y2) ∈ f1, as´ı por la definici´on 2.2.1, y1 = y2; si x ∈ C, entonces, por b), (x, y1) ∈ f2 y (x, y2) ∈ f2, as´ı por la definici´on 2.2.1, y1 = y2; esto prueba d). De c), d) y el teorema 2.2.1, concluimos que f : B ∪ C → A es una funci´on. De a) y el ejemplo 2.2.5, (x, y) ∈ f1 ⇔ (x, y) ∈ f[B] , esto es, f1 = f[B] ; an´alogamente, f2 = f[C] . Finalmente, a) enuncia que [y = f(x) ∧ x ∈ B] ⇔ y = f1(x) y b) enuncia que [y = f(x) ∧ x ∈ C] ⇔ y = f2(x); as´ı III) se cumple. 36 Ejercicio 2.2.1 Resuelva los siguientes problemas: 1. Pruebe que las funciones identidad, constante, inclusi´on, caracter´ıstica y la restricci´on de una funci´on califican como funciones de acuerdo a la definic´on de funci´on, en otras palabras que cumplen F1 y F2. 2. Si f : A → B es un funci´on inyectiva y C ⊆ A entonces f[C] : C → B es un funci´on inyectiva. 3. Sea A una clase y sea f = {(x,(x, x))|x ∈ A}. Muestre que f es una funci´on biyectiva de A en IA. 4. Sean f : A → B y g : A → B funciones. Pruebe que si f ⊆ g entonces f = g. 5. Sean f : A → B y g : C → D funciones. El producto de f y g es la funci´on definida como sigue: [f · g](x, y) = (f(x), g(y)) para todo (x, y) ∈ A × C. Pruebe que f · g es una funci´on de A×C en B ×D. Pruebe que si f y g son inyectivas entonces f ·g es inyectiva y que si f y g son sobreyectivas entonces f ·g es sobreyectiva. Pruebe que ran [f ·g] = (ran f)×(ran g). 2.3. Propiedades de funciones compuestas y funciones inversas Los siguientes teoremas expresan algunas propiedades b´asicas de funciones. Teorema 2.3.1 Si f : A → B y g : B → C son funciones entonces g ◦ f : A → C es una funci´on. Prueba: I) Por el corolario 1.4.1, dom g ◦ f = dom f = A, por el teorema 1.4.2.4, ran g ◦ f ⊆ ran g ⊆ C. 37 II) Suponga que (x, z1) ∈ g ◦ f y que (x, z2) ∈ g ◦ f; por la definici´on 1.4.2, ∃y1  (x, y1) ∈ f y (y1, z1) ∈ g y ∃y2  (x, y2) ∈ f y (y2, z2) ∈ g. De (x, y1) ∈ f y (x, y2) ∈ f concluimos, por la definici´on 2.2.1, que y1 = y2; as´ı, (y1, z1) ∈ g y (y1, z2) ∈ g. Se sigue por F2 (aplicada a g) que z1 = z2; as´ı, g ◦ f satisface F2. De I), II) y el teorema 2.2.1, concluimos que g ◦ f : A → C es una funci´on. Por la Definici´on 1.4.2, (x, y) ∈ g ◦ f si y s´olo si para alg´un elemento z, (x, z) ∈ f y (z, y) ∈ g. As´ı, x g◦f 7→ y si y s´olo si para alg´un z, x f 7→ z y z g 7→ y. Esto es lo mismo como decir que y = [g ◦ f](x) si y s´olo si para alg´un z, z = f(x) y y = g(z). Por lo cual obtenemos la siguiente: Definici´on 2.3.1 [g ◦ f](x) = g(f(x)). Definici´on 2.3.2 Una funci´on f : A → B se dice que es invertible si f −1 : B → A es una funci´on. Sea f : A → B una funci´on invertible; por la Definici´on 1.4.1, (x, y) ∈ f si y s´olo si (y, x) ∈ f −1 . As´ı, x f 7→ y si y s´olo si y f−1 7→ x. De donde obtenemos: Definici´on 2.3.3 y = f(x) si y s´olo si x = f −1 (y). Los siguientes dos teoremas nos dan una condici´on necesaria y una suficiente para que una funci´on sea invertible. Teorema 2.3.2 Si f : A → B es una funci´on biyectiva entonces f −1 : B → A es una funci´on biyectiva. Prueba: Por el teorema 2.2.1, dom f = A, y por la definici´on 2.2.4, ran f = B; as´ı por el teorema 1.4.2, dom f −1 = B y ran f −1 = A. Ahora probemos que f −1 satisface F2: (y, x1) ∈ f −1 ∧ (y, x2) ∈ f −1 ⇒ (x1, y) ∈ f ∧ (x2, y) ∈ f, por 1.4.1 ⇒ x1 = x2, por 2.2.3. As´ı, por el teorema 2.2.1, f −1 : B → A es una funci´on. 38 Procedemos a probar que f −1 satisface INJ: (y1, x) ∈ f −1 ∧ (y2, x) ∈ f −1 ⇒ (x, y1) ∈ f ∧ (x, y2) ∈ f, por 1.4.1 ⇒ y1 = y2, por 2.2.1. Finalmente, f −1 satisface SURJ ya que ran f −1 = A. Teorema 2.3.3 Si f : A → B es invertible entonces f : A → B es biyectiva. Prueba: Sea f : A → B invertible; esto es, sea f −1 : B → A una funci´on. Por el teorema 2.2.1, dom f −1 = B, as´ı por el teorema 1.4.2.2, ran f = B, as´ı, f : A → B es sobreyectiva. Ahora (x1, y) ∈ f ∧ (x2, y) ∈ f ⇒ (y, x1) ∈ f −1 ∧ (y, x2) ∈ f −1 , por 1.4.1 ⇒ x1 = x2, por F2 aplicada a f −1 . As´ı f : A → B es tambi´en inyectiva, y por tanto biyectiva. Los teoremas 2.3.2 y 2.3.3 se pueden resumir como sigue: f : A → B es invertible si y s´olo si es biyectiva; a´un m´as, si f : A → B es invertible, entonces f −1 : B → A es biyectiva. Los dos teoremas siguientes dan otra caracterizaci´on ´util de funciones invertibles. Teorema 2.3.4 Sea f : A → B una funci´on invertible entonces: I) f −1 ◦ f = IA. II) f ◦ f −1 = IB. Prueba: I) Sea x ∈ A y sea y = f(x); entonces por 2.3.3, x = f −1 (y). As´ı [f −1 ◦ f](x) = f −1 [f(x)] = f −1 (y) = x = IA(x); esto se cumple para todo x ∈ A, as´ı por el teorema 2.2.2, f −1 ◦ f = IA. II) La prueba es an´aloga a la del inciso anterior y se deja como un ejercicio. Teorema 2.3.5 Sean f : A → B y g : B → A funciones. Si g ◦ f = IA y f ◦g = IB entonces f : A → B es biyectiva (y por tanto invertible) y g = f −1 . Prueba: 39 I) Primero, probemos que f : A → B es inyectiva. f(x1) = f(x2) ⇒ g(f(x1)) = g(f(x2)), por F2 (aplicada a g) ⇒ (g ◦ f)(x1) = (g ◦ f)(x2), por 2.3.1 ⇒ x1 = x2, porque g ◦ f = IA. II) Luego, probemos que f : A → B es sobreyectiva. Si y ∈ B entonces y = IB(y) = (f ◦ g)(y) = f(g(y)); en otras palabras, si y es cualquier elemento de B, entonces y = f(x), donde x = g(y) ∈ A. III) Finalmente, probemos que g = f −1 . Para empezar, x = g(y) ⇒ f(x) = f(g(y)) = (f ◦ g)(y) = IB(y) = y ⇒ x = f −1 (y); reciprocamente, x = f −1 (y) ⇒ y = f(x) ⇒ g(y) = g(f(x)) = (g ◦ f)(x) = IA(x)) = x. As´ı, ∀y ∈ B, x = f −1 (y) ssi x = g(y); esto es, f −1 (y) = g(y); se sigue (por el teorema 2.2.2) que f −1 = g. Los teoremas 2.3.4 y 2.3.5 se pueden resumir como sigue: f : A → B es invertible si y s´olo si existe una funci´on g : B → A tal que g ◦ f = IA y f ◦ g = IB. La funci´on g, si existe, es la inversa de f. El siguiente teorema proporciona una caracterizaci´on importante de las funciones inyectivas. Teorema 2.3.6 Sea f : A → B una funci´on; f : A → B es inyectiva si y s´olo si existe una funci´on g : B → A tal que g ◦ f = IA. Prueba: I) Suponga que existe una funci´on g : B → A tal que g ◦ f = IA. Para probar que f : A → B es inyectiva, repetimos la parte I) de la prueba de 2.3.5. 40 II) Rec´ıprocamente, suponga que f : A → B es inyectiva; sea C = ran f. Por el corolario 2.2.1, f : A → C es una funci´on; f : A → C es sobreyectiva (porque C = ran f), as´ı es biyectiva; as´ı f −1 : C → A es una funci´on. Si a es alg´un elemento fijo de A, sea Ka : (B − C) → A la funci´on constante (ver ejemplo 2.2.2) el cual mapea todo elemento de (B − C) sobre a. Si g = f −1 ∪ Ka, entonces, por 2.2.4.I), g : B → A es una funci´on. Finalmente, si x ∈ A, sea y = f(x); entonces (g ◦ f)(x) = g(f(x)) = g(y), porque y = f(x) = f −1 (y), por 2.2.4.III) = x, porque x = f −1 (y) por 2.3.3. As´ı ∀x ∈ A,(g◦f)(x) = IA; se sigue por el teorema 2.2.2 que g◦f = IA. Posteriormente probaremos un teorema compa˜nero del teorema 2.3.6, el cual enuncia lo siguiente: f : A → B es sobreyectiva si y s´olo si existe una funci´on g : B → A tal que f ◦ g = IB. El teorema 2.3.6 y su compa˜nero frecuentemente se parafrasean como sigue. Sea f : A → B una funci´on; f : A → B es inyectiva si y s´olo si tiene una “inversa izquierda” y es sobreyectiva si y s´olo si tiene una “inversa derecha”. Teorema 2.3.7 Si f : A → B, g : B → C y g ◦ f : A → C son funciones, entonces lo siguiente se cumple: I) Si f y g son inyectivas entonces g ◦ f es inyectiva. II) Si f y g son sobreyectivas entonces g ◦ f es sobreyectiva. III) Si f y g son biyectivas entonces g ◦ f es biyectiva. Prueba: I) Suponga que tanto f como g satisfacen INJ, entonces g[f(x1)] = g[f(x2)] ⇒ f(x1) = f(x2) ⇒ x1 = x2; as´ı g ◦ f satisface INJ. 41 II) Suponga que ambas f y g satisfacen SURJ, si z ∈ C, entonces ∃y ∈ B  x = g(y); ya que y ∈ B, ∃x ∈ A  y = f(x); as´ı z = g(f(x)) = (g◦f)(x). Consecuentemente, g ◦ f satisface SURJ. III) Se sigue inmediatamente de I) y II). Se sigue de 2.3.7.III) que la composici´on de dos funciones invertibles es invertible. A´un m´as, por el teorema 1.4.1.3, (g ◦ f) −1 = f −1 ◦ g −1 . Ejercicio 2.3.1 Resuelva los siguientes problemas: 1. Sea f : A → B una funci´on. Pruebe que IB ◦ f = f y que f ◦ IA = f. 2. Suponga que f : A → B y g : B → C son funciones. Pruebe que si g ◦f es inyectiva entonces f es inyectiva; pruebe q Cap´ıtulo 3 Relaciones 3.1. Introducci´on Intuitivamente, una relaci´on binaria en una clase A es un enunciado R(x, y) que es verdadero o falso para cada par ordenado (x, y) de elementos de A. Por ejemplo, la relaci´on “x divide a y”, la cual escribimos como D(x, y), es una relaci´on en la clase Z de los enteros: D(x, y) es verdadera para todo par de enteros (x, y) tal que y es un m´ultiplo de x; es falsa para cualquier otro par de enteros. La gr´afica representante de una relaci´on en A es una gr´afica G ⊆ A × A la cual consiste de todos los pares (x, y) tales que R(x, y) es verdadera. Rec´ıprocamente, si nos dan una gr´afica arbitraria G ⊆ A × A, entonces G define una relaci´on en A, llamada la relaci´on R tal que R(x, y) es verdadera si y s´olo si (x, y) ∈ G. As´ı, como hicimos en el caso de funciones, podemos identificar relaciones con sus gr´aficas representantes. Desde este punto de vista el estudio de relaciones es parte de la teor´ıa de conjuntos elemental. 3.2. Conceptos fundamentales y definiciones Definici´on 3.2.1 Sea A una clase; por una relaci´on en A entendemos una subclase arbitraria de A × A. Definici´on 3.2.2 Sea G una relaci´on en A; entonces a G se le llama reflexiva si ∀x ∈ A,(x, x) ∈ G. 43 sim´etrica si (x, y) ∈ G ⇒ (y, x) ∈ G. antisim´etrica si (x, y) ∈ G ∧ (y, x) ∈ G ⇒ x = y. transitiva si (x, y) ∈ G ∧ (y, z) ∈ G ⇒ (x, z) ∈ G. Definici´on 3.2.3 La gr´afica diagonal IA se define como la clase {(x, x)|x ∈ A}. Es f´acil ver que G es reflexiva si y s´olo si IA ⊆ G. Existe una variedad de maneras alternativas interesantes y ´utiles de definir las nociones anteriores. Algunas se dan en el siguiente teorema. Teorema 3.2.1 Sea G una relaci´on en A. I) G es sim´etrica si y s´olo si G = G−1 . II) G es antisim´etrica si y s´olo si G ∩ G−1 ⊆ IA. III) G es transitiva si y s´olo si G ◦ G ⊆ G. Prueba: I) Suponga que G es sim´etrica. Entonces (x, y) ∈ G ⇔ (y, x) ∈ G ⇔ (x, y) ∈ G −1 ; as´ı G = G−1 . Rec´ıprocamente, suponga que G = G−1 , entonces (x, y) ∈ G ⇒ (x, y) ∈ G −1 ⇒ (y, x) ∈ G. II) Suponga que G es antisim´etrica, entonces (x, y) ∈ G ∩ G −1 ⇒ (x, y) ∈ G ∧ (x, y) ∈ G −1 ⇒ (x, y) ∈ G ∧ (y, x) ∈ G −1 ⇒ x = y ⇒ (x, y) = (x, y) ∈ IA. Rec´ıprocamente, suponga que G ∩ G−1 ⊆ IA, entonces (x, y) ∈ G ∧ (y, x) ∈ G ⇒ (x, y) ∈ G ∧ (x, y) ∈ G −1 ⇒ (x, y) ∈ G ∩ G −1 ⊆ IA ⇒ x = y. 44 III) Suponga que G es transitiva, entonces (x, y) ∈ G ◦ G ⇒ ∃z  (x, z) ∈ G ∧ (z, y) ∈ G ⇒ (x, y) ∈ G. As´ı G ◦ G ⊆ G. Rec´ıprocamete, suponga que G ◦ G ⊆ G, entonces (x, y) ∈ G ∧ (y, z) ∈ G ⇒ (x, z) ∈ G ◦ G ⊆ G. Definici´on 3.2.4 Una relaci´on es llamada una relaci´on de equivalencia si es reflexiva, sim´etrica y transitiva. Una relaci´on es llamada una relaci´on de orden si es reflexiva, antisim´etrica y transitiva. Definici´on 3.2.5 Sea G una relaci´on en A. G es llamada: irreflexiva si ∀x ∈ A,(x, x) 6∈ G. asim´etrica si (x, y) ∈ G ⇒ (y, x) 6∈ G. intransitiva si (x, y) ∈ G ∧ (y, z) ∈ G ⇒ (x, z) 6∈ G . Ejemplo 3.2.1 Sea Z que designa al conjunto de los n´umeros enteros; la relaci´on de igualdad en Z es reflexiva, sim´etrica y transitiva; as´ı, es una relaci´on de equivalencia. Ejemplo 3.2.2 Sea Z que designa al conjunto de los n´umeros enteros; la relaci´on ≤ (“menor o igual a”) es reflexiva, antisim´etrica y transitiva; as´ı, es una relaci´on de orden. Ejemplo 3.2.3 Sea Z que designa al conjunto de los n´umeros enteros; la relaci´on < (“menor estrictamente que”) no es una relaci´on de orden: es irreflexiva, asim´etrica y transitiva; a tal relaci´on se le llama una relaci´on de orden estricto. Ejercicio 3.2.1 Proceda como se indica en cada inciso. 45 1. Cada una de las siguientes gr´aficas describe una relaci´on en el conjunto Z de n´umeros enteros. Enuncie, para cada relaci´on, si tiene cada una de las siguientes propiedades: reflexiva, sim´etrica, antisim´etrica, transitiva, irreflexiva, asim´etrica e intransitiva. Determine cuando es una relaci´on de equivalencia, una relaci´on de orden o ninguna. Pruebe sus respuestas en cada caso. a) G = {(x, y)|x + y < 3}. b) G = {(x, y)|x divide a y}. c) G = {(x, y)|x y y son primos relativos}. d) G = {(x, y)|x + y es un n´umero par}. e) G = {(x, y)|x = y ∨ x = −y}. f) G = {(x, y)|x + y es par y x es un m´ultiplo de y}. g) G = {(x, y)|x = y + 1}. 2. Sea G una relaci´on en A; pruebe cada una de las siguientes: a) G es irreflexiva si y s´olo si G ∩ IA = ∅. b) G es asim´etrica si y s´olo si G ∩ G−1 = ∅. c) G es intransitiva si y s´olo si (G ◦ G) ∩ G = ∅. 3. Muestre que si G es una relaci´on de equivalencia en A, entonces G◦G = G. 4. Sea {Gi}i∈I una familia indexada de relaciones de equivalencia en A. Muestre que T i∈I Gi es una relaci´on de equivalencia en A. 5. Sea {Gi}i∈I una familia indexada de relaciones de orden en A. Muestre que T i∈I Gi es una relaci´on de orden en A. 6. Sea H una relaci´on reflexiva en A. Pruebe que para cualquier relaci´on G en A, G ⊆ H ◦ G y G ⊆ G ◦ H. 7. Sean G y H relaciones en A; suponga que G es reflexiva y H es reflexiva y transitiva. Muestre que G ⊆ H si y s´olo si G◦H = H. (En particular, esto se cumple si G y H son relaciones de equivalencia.) 8. Muestre que la inversa de una relaci´on de orden en A es una relaci´on de orden en A. 46 9. Sea G una relaci´on en A. Muestre que G es una relaci´on de orden si y s´olo si G ∩ G−1 = IA y G ◦ G = G. 10. Sean G y H relaciones de equivalencia en A. Muestre que G◦ H es una relaci´on de equivalencia en A si y s´olo si G ◦ H = H ◦ G. 11. Sean G y H relaciones de equivalencia en A. Pruebe que G ∪ H es una relaci´on de equivalencia si y s´olo si G ◦ H ⊆ G ∪ H y H ◦ G ⊆ G ∪ H. 12. Sea G una relaci´on de equivalencia en A. Pruebe que si H y J son relaciones arbitrarias en A, entonces G ⊆ H ∧ G ⊆ J ⇒ G ⊆ H ◦ J. 3.3. Relaciones de equivalencia y particiones En el resto de este cap´ıtulo nos ocuparemos con relaciones de equivalencia en conjuntos. Los conceptos que estamos por introducir surgen naturalmente en t´erminos de conjuntos, peor no pueden extenderse a clases propias; para entender porque no, el lector debe revisar nuestra discusi´on de la secci´on 1.6. Brevemente, si A es un conjunto y P(X) es una propiedad, entonces por la Observaci´on 1.6.2 es leg´ıtimo formar el conjunto de todos los subconjuntos X ⊆ A que satisfacen P(X). No obstante, si A fuera una clase arbitraria, no ser´ıa permisible formar la “clase de todas las subclases de A que satisfacen P(X)”. Esta restricci´on nos obliga a confinar la siguiente discusi´on a conjuntos. Intuitivamente, esto no debe inquietar demasiado al lector, ya que un conjunto es casi lo mismo que una clase: un conjunto es cualquier clase excepto una “excesivamente grande”. Definici´on 3.3.1 Sea A un conjunto; por una partici´on de A nos referimos a una familia {Ai}i∈I de subconjuntos no vac´ıos de A con las siguientes propiedades: P1. ∀i, j ∈ I, Ai ∩ Aj = ∅ o Ai = Aj . P2. A = S i∈I Ai . Intuitivamente, una partici´on es una familia de subconjuntos de A los cuales son disjuntos uno del otro, y cuya uni´on es todo A. Los subconjuntos son llamados los miembros de la partici´on. Se acostumbra permitir a un 47 miembro dado de la partici´on ser designado por m´as de un ´ındice; esto es, podemos tener Ai = Aj , cuando i 6= j. As´ı la condici´on de que dos miembros distintos son disjuntos est´a expresada correctamente por P1. La propiedad P1 enuncia que cualesquiera dos miembros Ai y Aj o son disjuntos o son iguales; esto es, o no tienen elementos en com´un o tienen todos sus elmentos en com´un; en otras palabras, si ellos tienen tanto como un elemento en com´un, ellos tienen todos sus elementos en com´un. As´ı, P1 tambi´en se puede enunciar como sigue: P1◦ . Si ∃x ∈ Ai ∩ Aj , entonces Ai = Aj . P2 se puede remplazar por la condici´on m´as simple P20 . A ⊆ S i∈I Ai . Ya que, independientemente de la condici´on P2, hemos establecido que cada Ai es un subconjunto de A; as´ı, por el teorema 1.5.1.1 S i∈I Ai ⊆ A. Consecuentemente, es suficiente enunciar P20 para tener que A = S i∈I Ai . Es conveniente escribir P20 en la forma P2◦ . Si x ∈ A, entonces x ∈ Ai para alg´un i ∈ I. Brevemente, entonces, una partici´on de A es una familia {Ai}i∈I de subconjuntos no vac´ıos de A tal que P1◦ . Si ∃x ∈ Ai ∩ Aj , entonces Ai = Aj y P2◦ . Si x ∈ A, entonces x ∈ Ai para alg´un i ∈ I. En los ejercicios al final de esta secci´on se dan ejemplos de particiones. Los siguientes resultados enuncian la conexi´on entre relaciones de equivalencia en A y particiones de A. Ellos son de gran importancia en muchas ramas de la matem´atica. Sea G una relaci´on de equivalencia en A; algunas veces escribimos x ∼ G y en vez de (x, y) ∈ G, y decimos que “x es equivalente a y m´odulo G”; cuando no existe peligro de ambig¨uedad, escribimos simplemente x ∼ y y decimos que “x es equivalente a y”. Note que como G es una relaci´on de equivalencia en A, tenemos i) x ∼ x, ∀x ∈ A. 48 ii) x ∼ y ⇒ y ∼ x. iii) x ∼ y ∧ y ∼ z ⇒ x ∼ z. Definici´on 3.3.2 Sea A un conjunto y sea G una relaci´on de equivalencia en A. Si x ∈ A, entonces la clase de equivalencia de x m´odulo G es el conjunto Gx definido como sigue: Gx = {y ∈ A|(y, x) ∈ G} = {y ∈ A|y ∼ G x}. En otras palabras, Gx es el conjunto de todos los elementos de A que son equivalentes a x. En la literatura matem´atica, Gx se denota tambi´en por los s´ımbolos Ax, [x] y x/G. Lema 3.3.1 Sea G una relaci´on de equivalencia en A. Entonces x ∼ y si y s´olo si Gx = Gy. Prueba: i) Suponga que x ∼ y; tenemos z ∈ Gx ⇒ z ∼ x ⇒ z ∼ y porque asumimos que x ∼ y ⇒ z ∈ Gy. Hemos mostrado que Gx ⊆ Gy; an´alogamente, Gy ⊆ Gx; as´ı Gx = Gy. ii) Suponga Gx = Gy; por la propiedad reflexiva, x ∼ x, as´ı x ∈ Gx; pero Gx = Gy; as´ı x ∈ Gy, esto es x ∼ y. Teorema 3.3.1 Sea A un conjunto, sea G una relaci´on de equivalencia en A, y sea {Gx}x∈A la familia de todas las clases de equivalencia m´odulo G. Entonces {Gx}x∈A es una partici´on de A. Prueba: Por definici´on, cada Gx es un subconjunto de A; es no vac´ıo ya que x ∼ x, por lo tanto x ∈ Gx. Resta probar que P1◦ y P2◦ se cumplen. 49 P1◦ z ∈ Gx ∩ Gy ⇒ z ∈ Gx y z ∈ Gy ⇒ z ∼ x y z ∼ y ⇒ x ∼ z y z ∼ y ⇒ x ∼ y ⇒ Gx = Gy (la ´ultima implicaci´on se sigue del lema 3.3.1). P2◦ Si x ∈ A, entonces por la propiedad reflexiva x ∼ x, as´ı x ∈ Gx. Si G es una relaci´on de equivalencia en A y {Gx}x∈A es la familia de todas las clases de equivalencia m´odulo G, entonces {Gx}x∈A es referida como la partici´on inducida por G, o la partici´on correspondiente a G. Teorema 3.3.2 Sea A un conjunto, sea {Ai}i∈I una partici´on de A, y sea G el conjunto de pares (x, y) de elementos de A tales que x y y est´an en el mismo miembro de la partici´on; esto es, G = {(x, y)|x ∈ Ai ∧ y ∈ Ai para alg´un i ∈ I}. Entonces G es una relaci´on en A y {Ai}i∈I es la partici´on inducida por G. A G se le llama la relaci´on de equivalencia correspondiente a {Ai}i∈I . Prueba: G es reflexiva: x ∈ A ⇒ x ∈ Ai para alg´un i ∈ I lo cual implica que x ∈ Ai ∧ x ∈ Ai ⇒ (x, x) ∈ G. G es sim´etrica: (x, y) ∈ G ⇒ x ∈ Ai ∧ y ∈ Ai lo cual implica que y ∈ Ai ∧ x ∈ Ai ⇒ (y, x) ∈ G. G es transitiva: (x, y) ∈ G y (y, z) ∈ G implican que x ∈ Ai ∧ y ∈ Ai y y ∈ Aj ∧ z ∈ Aj lo cual implica que Ai = Aj (porque y ∈ Ai ∩ Aj ) lo cual implica que x ∈ Ai ∧ z ∈ Ai lo cual implica que (x, z) ∈ G. Finalmente, cada Ai es una clase de equivalencia m´odulo G; ya que si x ∈ Ai , entonces y ∈ Ai ⇔ (y, x) ∈ G ⇔ y ∈ Gx; as´ı Ai = Gx. Los dos teoremas aclaran que toda relaci´on de equivalencia en A corresponde ´unicamente a una partici´on de A, y rec´ıprocamente. Una vez m´as: si damos una partici´on de A, la relaci´on de equivalencia correspondiente es la relaci´on que le llama a los elementos x y y “equivalentes” si ellos est´an en el mismo miembro de la partici´on. Viendo el otro lado de la moneda, si damos una relaci´on de equivalencia en A, la partici´on correspondiente es aquella que pone a los elementos x y 50 y en el mismo miembro de la partici´on si y s´olo si ellos son equivalentes. El lector debe notar que G es la relaci´on de equivalencia correspondiente a {Ai}i∈I si y s´olo si {Ai}i∈I es la partici´on correspondiente a G. Ejemplo 3.3.1 Sea A = {a, b, c, d, e}; sea A1 = {a, b}, A2 = {c, d} y A3 = {e}. Sea G = {(a, a),(b, b),(c, c),(d, d),(e, e),(a, b),(b, a),(c, d),(d, c)}. Es f´acil ver que {A1, A2, A3} es una partici´on de A; G es la relaci´on de equivalencia correspondiente a {A1, A2, A3} y {A1, A2, A3} es la partici´on correspondiente a G. Se debe notar que A1 = Ga = Gb, A2 = Gc = Gd y A3 = Ge. Si G es una relaci´on de equivalencia en el conjunto A, entonces al conjunto de clases de equivalencia m´odulo G se le llama el conjunto cociente de A entre G, se acostumbra denotarlo mediante A/G. As´ı, en el ejemplo anterior, A/G es el conjunto de tres elementos {Ga, Gc, Ge}. El concepto de conjunto cociente juega un rol vital en muchas partes de la matem´atica avanzada. Ejercicio 3.3.1 Proceda como se pide. 1. Sea Z el conjunto de los enteros. Para cada entero n, sea Bn = {m ∈ Z|∃q  m = n + 5q}. Pruebe que {Bn}n∈Z es una partici´on de Z. 2. Sea R el conjunto de los n´umeros reales. En cada uno de los siguientes, pruebe que {Br}r∈R es una partici´on de R × R. Describa geom´etricamente a los miembros de cada partici´on. Encuentre la relaci´on de equivalencia correspondiente a cada partici´on. a) Br = {(x, y)|y = x + r} para cada r ∈ R. b) Br = {(x, y)|x 2 + y 2 = r} para cada r ∈ R. 3. Sea R el conjunto de los n´umeros reales. Pruebe que cada una de las siguientes es una relaci´on de equivalencia en R × R: a) G = {[(a, b),(c, d)]|a 2 + b 2 = c 2 + d 2}. b) H = {[(a, b),(c, d)]|b − a = d − c}. c) J = {[(a, b),(c, d)]|a + b = c + d}. Encuentre la partici´on correspondiente a cada una de las relaciones de equivalencia y describa geom´etricamente a los miembros de estas particiones. [Consejo para b): si b−a = d−c = k, note que [(a, b),(c, d)] ∈ H 51 si y s´olo si tanto (a, b) como (c, d) satisfacen la ecuaci´on y = x+k. Consejo para c): si a + b = c + d = k, note que [(a, b),(c, d)] ∈ J si y s´olo si tanto (a, b) como (c, d) satisfacen la ecuaci´on y = −x + k.] 4. Si H y J son las relaciones de equivalencia del ejercicio 3, describa la relaci´on de equivalencia H ∩ J. Describa las clases de equivalencia m´odulo H ∩ J. 5. Sean H y J las relaciones de equivalencia del ejercicio 3. Pruebe que H ◦ J = J ◦ H; concluya que H ◦ J es una relaci´on de equivalencia, y describa las clases de equivalencia m´odulo H ◦ J. [Consejo: Vea el ejercicio 10 del conjunto de ejercicios 3.2.1.]

BIOGRAFÍA.
file:///D:/Downloads/Teor%C3%ADa%20Axiom%C3%A1tica%20de%20Conjuntos%20FCC%20BUAP.%20Jos%C3%A9%20de%20Jes%C3%BAs%20Lavalle%20Mart%C3%ADnez.pdf