Cap´ıtulo 2 Conjuntos, Aplicaciones Y Relaciones

Transcript

Cap´ıtulo 2 Conjuntos, Aplicaciones y Relaciones 2.1. Conjuntos Se partir´a, en esta introducci´on, de la existencia intuitiva de unos entes matem´aticos que se denominar´an conjuntos. Definici´ on 3. Un conjunto es una colecci´ on de objetos bien definidos y diferenciables entre s´ı. A los objetos que constituyen un conjunto se les denomina elementos del mismo. Los conjuntos se designan, habitualmente, por letras latinas may´ usculas: A, B, . . . y los elementos por letras latinas min´ usculas: a, b, . . .; si a es un elemento del conjunto A, se dir´a que a pertenece al conjunto A, y se escribir´a a ∈ A. En caso contrario, se dir´a que el elemento no pertenece al conjunto y se denotar´a a 6∈ A.1 Al conjunto que carece de elementos se le denomina conjunto vac´ıo, y se denota por ∅ o por { }. Ejemplos 1. La proposici´on “Todos los alumnos que aprobar´ an Matem´ aticas en junio” no define adecuadamente un conjunto puesto que, dado un alumno, no se puede afirmar de antemano si aprobar´ a o no en junio. Un conjunto puede ser definido por extensi´ on, enumerando todos y cada uno de sus elementos, o por comprensi´ on, diciendo cu´al es la propiedad que los caracteriza. 1 Un conjunto A est´a bien definido cuando, dado un elemento cualquiera x, es cierta una y s´olo una, de las proposiciones x ∈ A y x 6∈ A. 23 CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 24 B A Figura 2.1: Inclusi´on de Conjuntos, A ⊂ B. Ejemplos 2. Algunos conjuntos definidos por comprensi´on: A = {x ∈ Z ; x2 ≤ 16} B = {x ∈ N ; x divide a 20} ∅={} Ejemplos 3. Los mismos conjuntos definidos por extensi´on: A = {0, 1, 2, 3, 4, −1, −2, −3, −4} B = {1, 2, 4, 5, 10, 20} Como se aprecia en este ejemplo, se utilizan las llaves “{” y “}” para delimitar los elementos que componen un conjunto. 2.1.1. Inclusi´ on Definici´ on 4. Dados dos conjuntos A y B, se dice que A es un subconjunto de B, y se expresa A ⊆ B, cuando todos los elementos de A son tambi´en elementos de B, es decir: ∀x [x ∈ A =⇒ x ∈ B] se dir´a que A est´a inclu´ıdo o contenido en B. Cuando A no est´a contenido en B, se escribir´a A * B (lo cual quiere decir que existe a ∈ A tal que a 6∈ B). Cualquier conjunto A, siempre admite como subconjuntos al conjunto vac´ıo ∅ y a A. Estos se denominan subconjuntos impropios o triviales. En otro caso, se dice que B es un subconjunto propio de A. Si B ⊆ A y B 6= A, se dice que B est´a contenido estrictamente en A y se denota B ⊂ A. 2.1. CONJUNTOS 25 En la figura 2.1 se muestra, mediante Diagramas de Venn,2 un conjunto A subconjunto de otro B. Definici´ on 5. El conjunto formado por todos los subconjuntos de uno dado A se denomina partes de A o conjunto potencia, y se denota P(A) o 2A . Ejemplos 4. Se exponen a continuaci´ on dos conjuntos sencillos, y sus partes:  Si A = {a, b} ⇒ P(A) = ∅, {a}, {b}, A .  Si A = {a, b, c} ⇒ P(A) = ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c , A}. Debe quedar claro que si A y B son dos conjuntos cualesquiera, se verifica que B ∈ P(A) ⇔ B ⊆ A Ejemplo 17. Las afirmaciones I), III), IV ), V ), V III), IX) y XI) son verdaderas. i) ∅ ⊆ ∅. ii) ∅ ∈ ∅ iii) ∅ ⊆ {∅} iv) ∅ ∈ {∅} v) {a, b} ⊆ {a, b, c, {a, b, c}} vi) {a, b} ∈ {a, b, c, {a, b, c}} vii) {a, ∅} ⊆ {a, {a, ∅}} viii) {a, ∅} ∈ {a, {a, ∅}} ix) N ⊆ Z x) N ∈ Z xi) {2} ∈ P(Z) xii) {2} ⊆ P(Z) 2 Los Diagramas de Venn fueron introducidos en 1880 por John Venn (1834–1923). B´asicamente, se trata de una colecci´on de curvas simples y cerradas, dibujadas en el plano. Son muy u ´ tiles para visualizar relaciones entre conjuntos. CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 26 U A Figura 2.2: Complementario de A respecto a U. Definici´ on 6. Un conjunto A es finito si tiene un n´ umero finito de elementos; este n´ umero se llama cardinal y se denota |A| o #A. En caso contrario, se dice que A es no finito. Es f´acil comprobar que si A es un conjunto finito, tambien lo es P(A)3 y, adem´as, |P(A)| = 2|A| . Definici´ on 7. Dos conjuntos A y B son iguales si, simult´ aneamente, se verifica A ⊆ B y B ⊆ A, es decir: A=B ⇔ A⊆B ∧ B⊆A 2.2. 2.2.1. Operaciones entre conjuntos Complementaci´ on Definici´ on 8. Dado un conjunto U 4 y un subconjunto A ⊆ U se llama com¯ al subconjunto de U formado plementario del conjunto A, y se denota5 A, por todos los elementos que no pertenecen a A, es decir: A¯ = {x ∈ U ; x 6∈ A} Obs´ervese que la propiedad que determina al complementario de A es la negaci´on de la propiedad que determina a los elementos de A. 3 Si A = {a1 , a2 , . . . , an } tiene n elementos, a cada uno de sus subconjuntos B le asociamos una cadena cB de 0′ s y 1′ s de longitud n. Cada cadena binaria tendr´a un 1 en la posici´on i-´esima (i = 1, . . . , n) si, y s´olo si, el elemento ai ∈ B, con lo que el cardinal de P(A) es el n´ umero de cadenas binarias de longitud n, es decir 2n . 4 Cuando, en un contexto determinado, se consideran siempre conjuntos que son subconjuntos de uno dado U , a dicho conjunto de referencia U se le denomina conjunto universal o universo 5 Puede usarse tambien la notaci´on A′ o CU (A) 27 2.2. OPERACIONES ENTRE CONJUNTOS A A B Figura 2.3: Uni´on de conjuntos: A ∪ B. B Figura 2.4: Intersecci´on de conjuntos: A ∩ B. En la figura 2.2 en la p´agina anterior se muestra, en la zona rayada, el conjunto complementario de A respecto a U. Propiedades 1. Dado un conjunto U y dos subconjuntos suyos A y B, se verifican las siguientes propiedades: i) ∅¯ = U. ii) U¯ = ∅. iii) A¯ = A. ¯ ⊆ A. ¯ iv) A ⊆ B ⇔ B 2.2.2. Uni´ on Definici´ on 9. Dados dos conjuntos A y B se llama uni´ on de A y B, y se representa A ∪ B, al conjunto formado por los elementos que pertenecen a A o a B: A ∪ B = {x ; x ∈ A ∨ x ∈ B} En la figura 2.3, la zona rayada reprsenta el conjunto A ∪ B. Propiedades 2. Dados los conjuntos A, B y C, subconjuntos de U, la uni´ on de conjuntos verifica las siguientes propiedades: i) A ⊆ (A ∪ B) , B ⊆ (A ∪ B). ii) A ⊆ B ⇔ A ∪ B = B. iii) A ⊆ C ∧ B ⊆ C ⇔ (A ∪ B) ⊆ C. iv) A ∪ A = A (Propiedad Idempotente). CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 28 v) A ∪ B = B ∪ A (Propiedad Conmutativa). vi) A ∪ (B ∪ C) = (A ∪ B) ∪ C (Propiedad Asociativa). vii) A ∪ U = U viii) A ∪ ∅ = A. 2.2.3. Intersecci´ on Definici´ on 10. Dados dos conjuntos A y B se llama intersecci´ on de A y B, y se representa A ∩ B, al conjunto formado por los elementos que pertenecen a A y a B, es decir: A ∩ B = {x ; x ∈ A ∧ x ∈ B} De la definici´on se sigue que un elemento pertenece a la intersecci´on si pertenece a los dos conjuntos. En la figura 2.4 en la p´agina anterior la zona rayada indica el conjunto intersecci´on A ∩ B. Propiedades 3. Dados tres conjuntos A,B y C, subconjuntos de U, la intersecci´on verifica las siguientes propiedades: i) (A ∩ B) ⊆ A, (A ∩ B) ⊆ B. ii) A ⊆ B ⇔ A ∩ B = A. iii) A ⊆ C ∧ B ⊆ C ⇒ (A ∩ B) ⊆ C.6 iv) C ⊆ A ∧ C ⊆ B ⇔ C ⊆ (A ∩ B). v) A ∩ A = A (Propiedad Idempotente). vi) A ∩ B = B ∩ A (Propiedad Conmutativa). vii) A ∩ (B ∩ C) = (A ∩ B) ∩ C (Propiedad Asociativa). viii) A ∩ U = A (U es el conjunto universal). ix) A ∩ ∅ = ∅. Propiedades 4. Con la notaci´ on anterior, la uni´ on y la intersecci´ on verifican adem´as las siguientes propiedades conjuntas: 6 N´otese que puede suceder que A ∩ B ⊆ C y, sin embargo, A * C y B * C. Es el caso de A = {a, x}, B = {b, x} y C = {x, y}. 29 2.2. OPERACIONES ENTRE CONJUNTOS A B A C B Figura 2.5: A ∪ (B ∩ C). C Figura 2.6: A ∩ (B ∪ C). i) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (Ver figura 2.5). ii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (Ver figura 2.6). iii) A ∪ A¯ = U. iv) A ∩ A¯ = ∅. ¯ (Primera Ley de De Morgan). v) (A ∪ B) = A¯ ∩ B ¯ (Segunda Ley de De Morgan). vi) (A ∩ B) = A¯ ∪ B Como consecuencia, si A, B ⊆ U son dos subconjuntos de U, se verifica que ¯ = (A ∩ B) ∪ (A ∩ B) ¯ A = A ∩ U = A ∩ (B ∪ B) Definici´ on 11. Si dos conjuntos no tienen ning´ un elemento en com´ un, se dice que son disjuntos, es decir: A y B son disjuntos ⇔ A ∩ B = ∅ 2.2.4. Diferencia Definici´ on 12. Dados dos conjuntos A y B se llama diferencia entre A y B, y se representa A\B o A − B , al conjunto formado por los elementos de A que no pertenecen a B: A\B = {x ∈ A ; x 6∈ B} En la figura 2.7(a) en la p´agina siguiente se muestran dos conjuntos A y B y, representado por el ´area rayada, el conjunto A − B. Se aprecia con CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 30 A B (a) Diferencia: A\B. A B (b) Diferencia sim´etrica: A ⊕ B. Figura 2.7: Diferencia de conjuntos facilidad que A\B y B\A son, en general, distintos. Por otro lado, es claro ¯ que A\B = A ∩ B Adem´as, se verifica que ¯ ⇔ A ∩ B = ∅ ⇔ B ⊆ A¯ ⇔ B\A = B A\B = A ⇔ A ⊆ B Definici´ on 13. Dados dos conjuntos A y B se llama diferencia sim´ etrica entre A y B, y se representa A ⊕ B, al conjunto de los elementos que est´an en uno y, s´olo uno de los conjuntos A o B. A ⊕ B = (A ∪ B) \ (A ∩ B) En la figura 2.7(b) se muestran dos conjuntos A y B, y en el ´area rayada, el conjunto diferencia sim´etrica A ⊕ B. Es f´acil ver que A ⊕ B = B ⊕ A y, adem´as: A ⊕ B = (A ∪ B) \ (A ∩ B) = (A\B) ∪ (B\A) Tambien se puede comprobar que A ⊕ ∅ = A, A ⊕ A = ∅, A ⊕ A¯ = U y ¯ A ⊕ U = A. 2.2.5. Producto Cartesiano Definici´ on 14. Dados dos conjuntos A y B, se llama producto cartesiano de A por B, y se denota A × B, al conjunto constituido por pares ordenados de elementos, el primero perteneciente al conjunto A y el segundo al B. Esto es: A × B = {(a, b) ; a ∈ A ∧ b ∈ B} Ejemplos 5. El producto cartesiano A × B de los conjuntos A = {1, 2, 3} y B = {a, b} es el conjunto: A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)} 31 2.3. APLICACIONES B b b a b (1, b) (1, a) 1 b b 2 (2, b) (2, a) b b 3 (3, b) (3, a) A Figura 2.8: Representaci´on gr´afica de A × B Cuando sea posible, es u ´til representar gr´aficamente el producto cartesiano por medio de diagramas de coordenadas cartesianas. Para ello se toman dos rectas OX y OY , perpendiculares u oblicuas, de forma que el punto O es la intersecci´on de ambas. Este punto recibe el nombre de origen, la recta OX es el eje de abscisas y la OY es el eje de ordenadas. El conjunto A se representa linealmente en OX, y el B en OY . Los elementos (a, b) de A×B se representan por puntos resultantes de la intersecci´on de la paralela a OY por a con la paralela a OX por b. En la figura 2.8 se muestra la representaci´on en coordenadas cartesianas del ejemplo anterior. Dos pares ordenados (a, b) y (c, d), elementos del producto cartesiano A×B, son iguales si a = c y b = d. Es claro que, en general, A×B 6= B ×A. Se puede extender la definici´on de producto cartesiano a n conjuntos. Definici´ on 15. Dados n conjuntos A1 , A2 , . . . , An se define su producto cartesiano como: A1 × A2 × · · · × An = {(a1 , a2 , . . . , an ) ; ai ∈ Ai , ∀ i = 1, 2, . . . , n} Finalmente, si A y B son conjuntos finitos, tambien lo es A × B y se tiene que: |A × B| = |A|.|B| 2.3. Aplicaciones El concepto de aplicaci´on (funci´on) es de gran importancia en Inform´atica. Una funci´on es el modo m´as natural de implementar la correspondencia entre los datos y el resultado de un proceso de c´alculo en un ordenador. Los llamados lenguajes funcionales como OCAML, HASKELL, etc., se fundamentan en este concepto y suelen identificar programa y funci´on. CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 32 Definici´ on 16. Sean A y B dos conjuntos no vac´ıos. Una aplicaci´ on f de A en B es una regla que asocia a cada elemento a de A un u ´nico elemento de B que se denomina imagen de a y se denota f (a). El conjunto A se llama conjunto inicial, y el B conjunto final. La relaci´on entre a y b debida a f se suele representar de la forma: f : A −→ B a f (a) = b Se suele denominar funci´ on 7 a la correspondencia f : A → B si A y B son conjuntos num´ericos. Con frecuencia, se utiliza la letra x para denotar los elementos del conjunto inicial de f , y la letra y para los elementos del conjunto final. rojo 4, 28 naranja verde amarillo 4, 63 5, 17 5, 35 azul 6, 12 violeta 6, 97 7, 49 Hz·1014 Figura 2.9: Aplicaci´on del espectro visible Ejemplos 6. i) Se puede considerar que el arco iris define una aplicaci´on que asocia a cada rango de frecuencias del espectro electromagn´etico, un color de los que percibimos tal como se muestra en la figura 2.9. ii) El horario de un ferrocarril define una aplicaci´ on que asocia a cada estaci´on a, b, c, . . . un n´ umero que sirve para expresar la medida del tiempo (8h, 8h30m, 8h57m,. . .) que invertir´ a el tren en llegar a cada estaci´on. Puesto que a cada estaci´ on s´ olo le puede corresponder una hora de llegada del tren, esta correspondencia entre estaciones y horarios sea efectivamente una aplicaci´ on. iii) Una tabla de seguros de vida es una funci´ on que asocia cada edad del solicitante (1 a˜ no, 2 a˜ nos, 3 a˜ nos, etc.) el importe de las primas que ha de pagar para suscribir tal seguro. 7 En el contexto del An´alisis Matem´atico es frecuente utilizar la palabra funci´on para referirse a una correspondencia f : A → B, es decir una regla que asocia a algunos elementos de A un elemento en B. Esos elementos de A que tienen imagen en B forman un subconjunto de A llamado dominio de f y que coincide con A cuando f es una aplicaci´ on. 33 2.3. APLICACIONES iv) La regla que permite calcular el per´ımetro p de una circunferencia multiplicando su di´ametro 2r (siendo r el radio) por la constante π, es una funci´on real de variable real, ya que el conjunto inicial es el de los n´ umeros reales, R, y coincide con el de llegada. Se representa: p = f (r) = 2πr Dos aplicaciones f : A → B y g : C → D son iguales si A = C, B = D y f (a) = g(a), para cualquier elemento a de A. Si A y B son dos conjuntos cualesquiera, se denota por B A al conjunto: B A = {f : A → B ; f es una aplicaci´on}. Cuando A y B son conjuntos son finitos, tambi´en lo es B A y se verifica que |B A | = |B||A|. Definici´ on 17. Sea f : A → B una aplicaci´ on y sean A1 ⊆ A y B1 ⊆ B dos subconjuntos de A y B respectivamente. Definimos la imagen por f del conjunto A1 como: f (A1 ) := {f (a) ; a ∈ A1 } ⊆ B y la imagen rec´ıproca por f del conjunto B1 como: f −1 (B1 ) := {a ∈ A ; f (a) ∈ B1 } ⊆ A Si tomamos como A1 = A, al conjunto f (A) = Imf le denominamos conjunto imagen. Ejemplos 7. Sea f : A = {1, 2, 3} → B = {x, y, z, t} la aplicaci´ on dada por f (1) = x, f (2) = z, f (3) = z. Es claro que f ({1}) = {x}, f ({2}) = {z}, f ({3}) = {z} y, por otro lado, f −1 ({x, y}) = {1} y f −1 ({y, t}) = ∅. Propiedades 5. Sea f : A → B una aplicaci´ on y sean A1 , A2 ⊆ A y B1 , B2 ⊆ B subconjuntos de A y B respectivamente. Se verifica: i) f (∅) = ∅, f −1 (∅) = ∅ y f −1 (B) = A ii) Si A1 ⊆ A2 , entonces f (A1 ) ⊆ f (A2 ) 34 CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES iii) Si B1 ⊆ B2 , entonces f −1 (B1 ) ⊆ f −1 (B2 ) iv) f (A1 ∩ A2 ) ⊆ f (A1 ) ∩ f (A2 ) La igualdad no es cierta, en general. Basta tomar A1 = {2} y A2 = {3} en el el ejemplo 7. v) f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 ) vi) f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 ) vii) f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ) viii) A1 ⊆ f −1 (f (A1 )) Si tomamos A1 = {2} en el ejemplo 7 comprobamos que {2} ⊂ f −1 (f ({2}) = f −1 ({z}) = {2, 3} ix) f (f −1 (B1 )) ⊆ B1 Si tomamos B1 = B = {x, y, z, t} en el ejemplo 7 comprobamos que f (f −1({x, y, z, t}) = f ({1, 2, 3}) = {x, z} ⊂ {x, y, z, t}. Definici´ on 18. Sea f : A → B una aplicaci´ on y sea A1 ⊆ A un subconjunto de A. Llamamos restricci´ on de f a A1 y denotamos f/A1 a la aplicaci´on f restringida al conjunto A1 , es decir, f definida s´ olo para los elementos de A1 . Definici´ on 19. Se dice que una aplicaci´ on f : A → B entre A y B es: i) inyectiva si dos elementos distintos de A tienen diferente imagen en B, esto es: ∀ a1 , a2 ∈ A [f (a1 ) = f (a2 ) ⇐⇒ a1 = a2 ] ii) sobreyectiva, suprayectiva o exhaustiva si todo elemento de B es imagen, al menos, de un elemento de A, es decir: ∀b ∈ B, ∃ a ∈ A [f (a) = b] iii) biyectiva o biun´ıvoca si es a la vez inyectiva y sobreyectiva. Es interesante destacar que si los conjuntos A y B son finitos y f : A → B es una aplicaci´on entre ellos, se verifica que: 2.3. APLICACIONES 35 Si f es inyectiva8 , entonces |A| ≤ |B| Si f es sobreyectiva, entonces |A| ≥ |B| Si f es biyectiva9 , entonces |A| = |B| Ejemplos 8. Una empresa proporciona a sus 513 empleados un c´ odigo que consta de nueve cifras entre 0 y 9, por ejemplo 23/130/0467. Dos c´ odigos son “coincidentes en ceros”, si, en cada posici´ on uno tiene un cero si, y s´ olo si, lo tiene el otro. As´ı, los c´odigos 20/560/0503 y 10/730/0804 son coincidentes en ceros. Demuestra que al menos dos empleados tendr´ an c´ odigos de usuario coincidentes en ceros.10 Adem´as, se verifica tambi´en el siguiente resultado que ser´a de utilidad en la pr´actica: Proposici´ on 1. Si A y B son dos conjuntos finitos con el mismo cardinal y f : A → B es una aplicaci´on entre ellos, son equivalentes: f es inyectiva f es sobreyectiva f es biyectiva Demostraci´on. Si A = {a1 , . . . , an }, entonces f (A) = {f (a1 ), . . . , f (an )} y, al ser f inyectiva, |f (A)| = |A| = |B|. Puesto que f (A) ⊆ B y tienen el mismo cardinal, es obvio que f (A) = B, es decir f es sobreyectiva. Rec´ıprocamente, si f es sobreyectiva y f (a1 ) = f (a2 ) con a1 6= a2 , entonces |f (A)| < |A| = |B|, lo que contradice la sobreyectividad de f . Definici´ on 20. Dados tres conjuntos A, B y C, y dos aplicaciones f y g tales que f : A −→ B g : B −→ C a −→ f (a) = b b −→ g (b) = c 8 Este principio se conoce como Principio de Palomar. Es claro que si tenemos un conjunto de n palomas y otro conjunto de m nidos, con n > m, y definimos una aplicaci´on entre ellos que consiste en enviar cada paloma a su nido, al menos dos palomas comparten un nido, es decir la aplicaci´on no es inyectiva. 9 Conviene destacar que, si bien no todas las aplicaciones que se pueden definir entre conjuntos con el mismo cardinal son biyectivas, siempre es posible encontrar una aplicaci´on biyectiva entre ellos. 10 A cada empleado (paloma) le hacemos corresponder el subconjunto de {1, 2, . . . , 9} (nido) correspondiente a las posiciones en las que su c´odigo tiene un cero. Como hay m´as palomas que nidos (el n´ umero de subconjuntos posibles es 29 = 512), dos palomas al menos comparten el nido. 36 CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES se llama composici´ on de f con g a la aplicaci´ on g ◦ f : A −→ C a −→ (g ◦ f ) (a) = g [f (a)] = g (b) = c Ejemplos 9. Sea A = {1, 2, 3, 4, 5} y sean f, g : A → A las aplicaciones definidas por f (1) = f (2) = f (3) = f (4) = f (5) = 1 y g(1) = 5, g(2) = 4, g(3) = 3, g(4) = 2 y g(5) = 1. Es evidente que (g◦f )(a) = 5 y (f ◦g)(a) = 1, para todo a ∈ A. Por lo tanto, g ◦ f 6= f ◦ g. La composici´on de aplicaciones tiene la propiedad asociativa, es decir, dadas tres aplicaciones f : A −→ B, g : B −→ C y h : C −→ D : h ◦ (g ◦ f ) = (h ◦ g) ◦ f Proposici´ on 2. Sean f : A → B y g : B → C dos aplicaciones cualesquiera. Se verifica que: Si f y g son inyectivas, tambi´en lo es g ◦ f Si f y g son sobreyectivas, tambi´en lo es g ◦ f Si f y g son biyectivas, tambi´en lo es g ◦ f Demostraci´on. Si f y g son inyectivas y a1 , a2 son dos elementos de A tales que (g ◦ f )(a1 ) = (g ◦ f )(a2 ), entonces g(f (a1)) = g(f (a2 )) (por definici´on de composici´on). Puesto que g es inyectiva, se verifica que f (a1 ) = f (a2 ) y, la inyectividad de f permite concluir que a1 = a2 . La demostraci´on de las otras dos afirmaciones es un sencillo ejercicio. Definici´ on 21. Se llama aplicaci´ on identidad a una aplicaci´ on IA entre A y A de la forma: IA : A −→ A a −→ IA (a) = a Definici´ on 22. Sea f : A → B una aplicaci´ on. Se llama aplicaci´ on inversa de f , y se denota por f −1 a una aplicaci´ on f −1 : B → A tal que, si b es un elemento de B f −1 (b) = a ⇐⇒ b = f (a) Se puede comprobar que f ◦f −1 = IB , f −1 ◦f = IA , f ◦IA = f y IB ◦f = f . En consecuencia, si existe la inversa de f , ´esta es u ´nica. Proposici´ on 3. Dada una aplicaci´ on f : A → B, f admite inversa si, y s´olo si, f es biyectiva. Adem´as, Si f es inversible, su inversa f −1 tambi´en lo es y (f −1 )−1 = f Si f : A → B y g : B → C son dos aplicaciones inversibles, entonces (g ◦ f )−1 = f −1 ◦ g −1 37 2.4. RELACIONES Z 3 b 2 b 1 b 0 b −1 b −2 b −3 b b b b b b b b 1 2 3 4 5 6 7 N Figura 2.10: Representaci´on gr´afica de la aplicaci´on γ : N → Z 2.3.1. Conjuntos numerables Decimos que un conjunto A es numerable si es finito o existe una biyecci´on entre A y N. Se comprende f´acilmente que si A es finito y n = |A|, existe una biyecci´on entre el conjunto A y {1, . . . , n}. Son numerables los conjuntos N y Z ya que la aplicaci´on γ : N −→ Z n −→ γ (n) =  n/2 , − (n − 1) /2 , si n es par si n es impar es biyectiva. En la siguiente figura se muestra un diagrama en el que se aprecia el funcionamiento de esta aplicaci´on. Los naturales pares son asignados a los enteros positivos, y los naturales impares a los enteros negativos. Es evidente, a la vista de la figura, que esta aplicaci´on no tiene por qu´e ser u ´nica. Tambien es cierto que el conjunto de los n´ umeros racionales Q es numerable. No son numerables ni R ni C. 2.4. Relaciones Definici´ on 23. Dados dos conjuntos A y B, una relaci´ on binaria11 de A en B es un subconjunto cualquiera R del producto cartesiano A × B. Si el par ordenado (a, b) pertenece a R, se dir´ a que a est´ a relacionado con b, y se denotar´a aRb. 11 En general si tenemos n conjuntos, Ai con i = 1, . . . , n, se dice que un subconjunto R ⊆ A1 × · · · × An es una relacion n-aria sobre A1 , A2 , . . . , An . CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES 38 B R b b b b a b b b 1 2 3 r R A Figura 2.11: Representaci´on gr´afica de R ⊂ A × B Ejemplos 10. Figura 2.12: Representaci´on gr´afica de C ⊂ R × R i) Para los conjuntos A y B del ejemplo 5, se tiene que A × B = {(1, a) , (1, b) , (2, a) , (2, b) , (3, a) , (3, b)}. Una posible relaci´on ser´ıa R = {(1, a) , (2, b) , (3, a)}. En la figura 2.11 se muestran, mediante puntos, los elementos de A×B, y mediante c´ırculos los de R. ii) Para el producto cartesiano R × R, ser´ an A = B = R. Una posible relaci´on podr´ıa ser C = {(x, y) ∈ R × R ; x2 + y 2 = r 2 }, siendo r un n´ umero real positivo. En la figura 2.12 se muestran los conjuntos A y B (los ejes cartesianos), y toda la superficie del papel, en la que se encuentran los ejes, que constituye el producto cartesiano A × B = R × R = R2 . Los elementos de la relaci´on C ser´an los puntos de ese plano que verifiquen la ecuaci´on que la caracteriza. En la figura, esos puntos se encuentran sobre la l´ınea fina que, como se aprecia, forma una circunferencia de radio r. iii) El estado de una partida de un juego de barcos se determina, habitualmente, en un tablero cuadrado de 100 casillas, ordenadas en 10 filas y 10 columnas numeradas respectivamente del 1 al 10 y de la A a la J, tal como se muestra en la figura 2.13 en la p´ agina siguiente. Si llamamos X al conjunto de las filas del tablero e Y al de las columnas, las casillas del tablero ser´ an pares ordenados de la forma (x, y) ∈ X × Y . La situaci´on de la flota de barcos en el tablero bien puede considerarse una relaci´on F ⊂ X × Y . En concreto, los barcos que se muestran en el tablero de la figura 2.14 en la p´ agina siguiente constituyen la relaci´on: F = {(B, 2) , (B, 3) , (B, 4) , (E, 8) , (F, 8) , (G, 8) , (H, 3) , (H, 4) , (H, 5)} 39 2.4. RELACIONES 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 A B C D E F G H I J A B C D E F G H I J Figura 2.13: Tablero de una partida de barcos: X × Y . Figura 2.14: Flota de barcos (F ) y torpedos disparados (T ) en un tablero de barcos (X × Y ). Por otra parte, los sucesivos intentos de hundir la flota, indicados en la figura 2.14 mediante torpedos, constituyen otra relaci´ on T de la forma: T = {(D, 6) , (E, 2) , (F, 8) , (H, 5) , (I, 9)} Los impactos que los torpedos han producido en los barcos, ser´ an la relaci´on intersecci´on entre ambas: I = F ∩ T = {(F, 8), (H, 5)}. Definici´ on 24. Dado un conjunto A, se llama relaci´ on binaria en A a 12 cualquier subconjunto R de A × A. La relaci´on binaria es, por tanto, un caso particular de relaci´on en el que coinciden el conjunto inicial y el final. Si el conjunto A es finito, se puede representar una relaci´on binaria en A con un grafo dirigido. Para ello, se dibujan tantos puntos como elementos tenga A y una flecha de a a b si (a, b) ∈ R o, lo que es lo mismo, si aRb. 2.4.1. Propiedades de una relaci´ on binaria Sea A un conjunto y R una relaci´on binaria en A, Se dice que R es i) Reflexiva si ∀a ∈ A aRa ii) Sim´ etrica si ∀a1 , a2 ∈ A [a1 Ra2 ⇐⇒ a2 Ra1 ] 12 2 Si A es finito, el n´ umero de relaciones binarias en A es 2|A| . 40 CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES iii) Antisim´ etrica si ∀a1 , a2 ∈ A [(a1 Ra2 ) ∧ (a2 Ra1 ) =⇒ a1 = a2 ] iv) Transitiva si ∀a1 , a2 , a3 ∈ A [(a1 Ra2 ) ∧ (a2 Ra3 ) =⇒ a1 Ra3 ] Ejemplos 11. i) Dado cualquier conjunto A, la relaci´ on (⊆)“estar contenido en” definida en P(A) es reflexiva, antisim´etrica y transitiva. ii) Si A = N, Z, Q o R, la relaci´ on (≤) “ser menor o igual que” es tambien reflexiva, antisim´etrica y transitiva. iii) Dados dos n´ umeros enteros a y b, se dice que a divide a b y se denota a|b, si existe un n´ umero entero m tal que b = am. Es f´ acil comprobar que es reflexiva y transitiva. Cuando la restringimos a un subconjunto A de n´ umeros enteros del mismo signo (es decir A ⊆ Z+ o A ⊆ Z− ), verifica, adem´as la propiedad antisim´etrica. 2.4.2. Relaci´ on de Equivalencia Definici´ on 25. Una relaci´ on de equivalencia en un conjunto A es una relaci´on binaria R que satisface las propiedades reflexiva, sim´etrica y transitiva. En adelante, utilizaremos el s´ımbolo ∼ para referirnos a una relaci´on de equivalencia. Ejemplos 12. En Z, la relaci´ on: a ≡2 b ⇐⇒ a − b es un m´ ultiplo de 2 es una relaci´on de equivalencia. Esta relaci´ on se puede extender, considerando cualquier entero positivo m y definiendo: a ≡m b ⇐⇒ a − b es un m´ ultiplo de m Las relaciones de equivalencia permiten agrupar elementos relacionados entre s´ı en subconjuntos llamados clases de equivalencia: Definici´ on 26. Dado un conjunto A dotado de una relaci´ on de equivalencia ∼, se llama clase de equivalencia del elemento a ∈ A, y se denota por [a] al conjunto de los elementos de A que est´ an relacionados con a mediante ∼, es decir: [a] = {x ∈ A ; x ∼ a} 2.4. RELACIONES 41 La relaci´on de equivalencia del ejemplo que hemos visto antes divide a los elementos del conjunto Z en dos clases de equivalencia, una formada por los n´ umeros pares, y la otra por los impares. Cuando la relaci´on es ≡m , tenemos m clases de equivalencia 13 [0], [1], . . . , [m − 1]. Propiedades 6. Las clases de equivalencia verifican las siguientes propiedades: i) Dos elementos a1 y a2 est´an relacionados entre s´ı (a1 ∼ a2 ) si, y s´ olo si, determinan la misma clase de equivalencia ([a1 ] = [a2 ])14 . Demostraci´on. Si a1 ∼ a2 y a ∈ [a1 ], entonces a ∼ a1 y a1 ∼ a2 , nos permiten deducir que a ∼ a2 , es decir a ∈ [a2 ]. Rec´ıprocamente, si las clases coinciden, entonces a1 ∈ [a1 ] = [a2 ], es decir a1 ∼ a2 . ii) Dos elementos a1 y a2 no est´an relacionados si, y s´ olo si, [a1 ]∩[a2 ] = ∅. Demostraci´on. Si a1 6∼ a2 y a ∈ [a1 ] ∩ [a2 ], entonces a1 ∼ a y a ∼ a2 , as´ı que a1 ∼ a2 , lo que contradice la hip´otesis de partida. El rec´ıproco es an´alogo. Definici´ on 27. A una familia {Ai }i∈I de subconjuntos no vac´ıos de A que verifica: [ A= Ai i∈I Ai ∩ Aj = ∅, para todo i 6= j se le llama partici´ on de A. Es f´acil comprobar que una partici´on define una relaci´on de equivalencia15 y viceversa. Definici´ on 28. Dada una relaci´on de equivalencia ∼ definida en un conjunto A, se llama conjunto cociente de A respecto a ∼, y se denota A/ ∼, al conjunto cuyos elementos son las clases de equivalencia determinadas en A por ∼. En el ejemplo que estamos manejando, el conjunto cociente Z/ ≡m tiene m elementos. Este conjunto se denota Zm y se llama conjunto de restos m´odulo m. 13 Un n´ umero entero x pertenece a la clase de equivalencia [r], con 0 ≤ r ≤ m − 1, si r es el resto de la divisi´on de x entre m. 14 Teniendo esto en cuenta, una clase de equivalencia puede representarse por cualquiera de sus elementos. 15 Si {Ai }i∈I es una partici´on de A y a, b ∈ A, se dice que a ∼ b si, y s´olo si, existe i ∈ I tal que a, b ∈ Ai . 42 2.4.3. CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES Relaci´ on de orden Definici´ on 29. Si 4 es una relaci´ on binaria en A reflexiva, antisim´etrica y transitiva, se dice que es una relaci´ on de orden. Si a 4 b se dice que a es anterior a b o menor o igual que16 b. Una relaci´on de orden 4 en un conjunto A es de orden total si dados dos elementos cualesquiera a, b de A, siempre se pueden comparar, es decir a 4 b o b 4 a. Un ejemplo de relaci´on de orden total es la relaci´on ≤ en N, Z, Q o R, mientras que las relaciones “ ⊆ ” y “divide a” definidas anteriormente no son de orden total. Definici´ on 30. Un poset (A, 4) es un conjunto A y una relaci´ on de orden 4 definida en ´el. Ejemplos 13. i) Son ejemplos de posets (P(A), ⊆) y (N, |). ii) Sea (L, ≤) un alfabeto, es decir un conjunto finito totalmente ordenado y sea L∗ el conjunto de palabras que se pueden formar con los elementos de L. El orden de L se puede extender a L∗ siendo la relaci´ on de orden resultante de orden total y llamada orden lexicogr´afico por ser el orden del diccionario. As´ı, las palabras l1 l2 . . . lp y l1′ l2′ . . . lq′ est´ an relacionadas ′ ′ ′ y verifican que l1 l2 . . . lp ≤ l1 l2 . . . lq , si ocurre: ′ para alg´ un k < p, se tiene que li = li′ (con i = 1, . . . k), lk+1 ≤ lk+1 ′ y lk+1 6= lk+1 (por ejemplo casa y caso) p ≤ q y li = li′ , para i = 1 . . . p (por ejemplo casa y casas). Cuando (A, 4) es un poset finito, se puede representar con un diagrama de Hasse que consiste en un conjunto de v´ertices (denotando los elementos de A) y una serie de aristas (sin flecha). Dibujaremos una arista ascendente de x a y si y cubre a x, es decir, x ≤ y y no hay “elementos intermedios” entre ambos, es decir, si z ∈ A es tal que x ≤ z ≤ y, entonces z = x o z = y. Definici´ on 31. Dos posets (A, 4) y (B, ≤) son isomorfos si existe una aplicaci´on biyectiva f : A → B, de modo que: a 4 a′ ⇐⇒ f (a) ≤ f (a′ ). Ejemplos 14. Los posets (P({a, b, c}), ⊆), (D30 = {1, 2, 3, 5, 6, 10, 15, 30}, |)17 y ({0, 1}3, R) son isomorfos 18 . 16 De la relaci´on de orden nace, por ejemplo, el ordenamiento de los n´ umeros reales. No es de extra˜ nar el parecido entre el s´ımbolo “4” y el s´ımbolo “≤” (o, a veces, “6”) utilizado para ordenar de menor a mayor los n´ umeros reales. 17 Dm denota el conjunto de divisores positivos de m. 18 R es la relaci´on dada por (a, b, c) ≤ (a′ , b′ , c′ ) ⇔ (a ≤ a′ ) ∧ (b ≤ b′ ) ∧ (c ≤ c′ ) 43 2.4. RELACIONES 30 15 10 D30 5 6 3 2 1 2.4.4. Elementos distinguidos en un poset Sea (P, ≤) un poset. Definici´ on 32. Un elemento m ∈ P es un maximal si19 ¬∃p ∈ P [(m ≤ p) ∧ (m 6= p)], es decir, no hay elementos en P “estrictamente mayores” que m. Definici´ on 33. Un elemento n ∈ P es un minimal si20 ¬∃p ∈ P [(p ≤ n) ∧ (n 6= p)], es decir, no hay elementos en P “estrictamente menores” que n. Un poset puede tener varios maximales y varios minimales y, si es finito, tiene al menos un maximal y al menos un minimal. Definici´ on 34. Un elemento M ∈ P es m´ aximo de P si p ≤ M, para todo p ∈ P. Definici´ on 35. Un elemento m ∈ P es m´ınimo de P si m ≤ p, para todo p ∈ P. Proposici´ on 4. Se verifican los siguientes enunciados: i) El m´aximo, si existe, es u ´nico. ii) El m´ınimo, si existe, es u ´nico. iii) Si P es finito, P tiene m´aximo, si y, s´ olo si, tiene un un u ´nico maximal. iv) Si P es finito, P tiene m´ınimo, si y, s´ olo si, tiene un un u ´nico minimal. 19 20 Equivalentemente, ∀p ∈ P Equivalentemente, ∀p ∈ P [(m ≤ p) → (m = p)]. [(p ≤ n) → (n = p)]. 44 CAP´ITULO 2. CONJUNTOS, APLICACIONES Y RELACIONES Sea ahora Q ⊆ P un subconjunto de P . Definici´ on 36. Un elemento a ∈ P es una cota superior de Q en P si q ≤ a, para cualquier q ∈ Q. Definici´ on 37. Un elemento b ∈ P es una cota inferior de Q en P si b ≤ q, para cualquier q ∈ Q. Definici´ on 38. Un elemento a ∈ P es supremo de Q si a es una cota superior de Q en P , es decir, q ≤ a, para todo q ∈ Q. Si b es otra cota superior de Q en P , necesariamente a ≤ b. Queda claro que, si el conjunto de cotas superiores de Q en P es no vac´ıo, entonces el supremo es el m´ınimo de dicho conjunto. Definici´ on 39. Un elemento c ∈ P es ´ınfimo de Q si c es una cota inferior de Q en P , es decir, c ≤ q, para todo q ∈ Q. Si d es otra cota inferior de Q en P , necesariamente d ≤ c. Igual que ocurre con el supremo, si el conjunto de cotas inferiores de Q en P es no vac´ıo, entonces el ´ınfimo es el m´aximo de dicho conjunto. Proposici´ on 5. Se verifican los siguientes enunciados: i) El supremo de Q, si existe, es u ´nico. ii) El ´ınfimo de Q, si existe, es u ´nico. iii) Existe el m´aximo de Q si, y s´ olo si, existe el supremo y ´este es un elemento de Q. iv) Existe el m´ınimo de Q si, y s´ olo si, existe el ´ınfimo y ´este es un elemento de Q. Ejemplos 15. En el conjunto P = {1, 2, 3, 4, 5, 6, 8, 10, 12, 20}, se considera la relaci´on de orden parcial de divisibilidad y el subconjunto Q = {1, 2, 4, 10}. Es f´acil ver que Q no tiene m´ aximo porque tiene dos maximales (4 y 10). El supremo de Q en P es 20. Por otro lado, el u ´nico minimal 1 es m´ınimo e ´ınfimo. Por su parte, P tiene tres maximales (8, 12 y 20), no tiene m´ aximo y su m´ınimo es 1. 45 2.4. RELACIONES 8 20 12 6 10 4 2 3 1 5 P