Matemática Discreta (1925) PDF - Universidad Nacional de Río Cuarto

UNIVERSIDAD NACIONAL DE RIO CUARTO Facultad de Ciencias Exactas Fı́sico-Quı́mica y Naturales Profesorado y Licenciatura en Matemática Licenciatura en Fı́sica NOTAS DE CLASE MATEMÁTICA DISCRETA (1925)...

UNIVERSIDAD NACIONAL DE RIO CUARTO Facultad de Ciencias Exactas Fı́sico-Quı́mica y Naturales Profesorado y Licenciatura en Matemática Licenciatura en Fı́sica NOTAS DE CLASE MATEMÁTICA DISCRETA (1925) ÁLGEBRA I (2260) EQUIPO DOCENTE TEÓRICO PRÁCTICO ⋆ Mg. Carolina Bollo ⋆ Lic. Carmina Alturria Año 2024 2 Índice general 1. Proposiciones matemáticas y su demostración 7 1.1. Proposición Conjuntiva.............................. 8 1.2. Proposición Disyuntiva.............................. 9 1.3. Proposición Condicional............................. 9 1.4. Generalizador y Particularizador......................... 11 1.5. Demostraciones Directas e Indirectas...................... 14 2. Teorı́a de Conjuntos 19 2.1. Conjuntos y subconjuntos, pertenencia e inclusión............... 19 2.2. Diagramas de Venn................................ 23 2.3. Operaciones entre Conjuntos........................... 25 2.4. Propiedades de las Operaciones de Conjuntos................. 29 2.5. Tablas de Verdad de la Lógica proposicional.................. 33 2.6. Partición de un Conjunto............................. 37 2.7. Producto Cartesiano de Conjuntos....................... 37 3. Relaciones 39 3.1. Relación Binaria................................. 39 3.2. Representaciones de una Relación........................ 40 3.3. Relación de un conjunto en si mismo...................... 42 3.4. Funciones..................................... 44 3.5. Relación Inversa.................................. 46 3.6. Operaciones entre Relaciones........................... 47 3.7. Generalización................................... 48 3.8. Propiedades de las Relaciones.......................... 49 3 4 3.8.1. Reflexividad................................ 49 3.8.2. Arreflexiva................................. 50 3.8.3. Simetrı́a.................................. 51 3.8.4. Asimetrı́a................................. 52 3.8.5. Antisimetrı́a................................ 53 3.8.6. Transitividad............................... 54 3.9. Ejemplos...................................... 56 4. Relaciones de Orden y de Equivalencia 59 4.1. Relación de Orden................................ 59 4.1.1. Relación divide.............................. 60 4.1.2. Representación Gráfica.......................... 61 4.1.3. Orden Estricto.............................. 64 4.1.4. Orden Parcial y Total.......................... 65 4.1.5. Elementos Caracterı́sticos de un Conjunto Ordenado......... 67 4.1.6. Subconjuntos de un Conjunto Ordenado................ 70 4.2. Relación de Equivalencia............................. 74 5. Números Naturales e Inducción 85 5.1. La Suma de Gauss y la Serie Geométrica.................... 86 5.1.1. La suma de Gauss............................ 86 5.1.2. La serie Geométrica............................ 86 5.2. Sistema Axiomático de Peano.......................... 87 5.2.1. Principio de Inducción Matemática................... 89 5.3. El Principio de Buena Ordenación y el Principio de Inducción Matemática. 92 5.4. Sucesiones..................................... 93 5.4.1. Aplicaciones del PIM........................... 94 5.5. La Sucesión de Fibonacci y el Principio de Inducción Generalizada...... 95 5.6. Conjuntos coordinables, finitos, numerables................... 98 6. Números Enteros 101 6.1. Suma y Producto en Z.............................. 101 6.2. Relación ≤ en Z.................................. 103  5 6.3. Relación de Divisibilidad en Z.......................... 104 6.4. Algoritmo de la División Entera......................... 107 6.5. Máximo Común Divisor............................. 111 6.5.1. Algoritmo de Euclides.......................... 113 6.6. Mı́nimo Común Múltiplo............................. 116 6.7. Primos y Factorización.............................. 118 6.7.1. Teorema Fundamental de la Aritmética................. 120 6.8. Congruencia.................................... 122 7. Otros Conjuntos Numéricos 127 7.1. Números Racionales............................... 127 7.1.1. Suma y Producto en Q.......................... 128 7.1.2. Relación ≤ en Q............................. 129 7.1.3. Densidad en Q.............................. 130 7.2. Números Reales.................................. 131 7.3. Números Complejos................................ 133 8. Ejercitación 139 8.1. Ejercitación Capı́tulo 1.............................. 139 8.2. Ejercitación Capı́tulo 2.............................. 140 8.3. Ejercitación Capı́tulo 3.............................. 143 8.4. Ejercitación Capı́tulo 4.............................. 146 8.5. Ejercitación Capı́tulo 5.............................. 149 8.6. Ejercitación Capı́tulo 6.............................. 151 Bibliografı́a 152 6 Titulo importante / texto importante Ejemplos Texto importante Conclusiones Capı́tulo 1 Proposiciones matemáticas y su demostración En el intento por resolver problemas en matemática, se plantean y se utilizan afirmaciones o proposiciones que necesitan ser justificadas. Estas proposiciones pueden tener diferentes grados de complejidad: desde proposiciones muy sencillas, como por ejemplo: “6 es múltiplo de 2”, hasta proposiciones más complejas, como por ejemplo: “Dados dos números enteros cualesquiera x e y: Si x + y ≥ 2 entonces x ≥ 1 o y ≥ 1” ¿Cómo justificamos la verdad de afirmaciones de este tipo? Para poder comenzar a dar respuesta a esta cuestión, vamos a empezar por analizar algunos tipos de proposiciones muy sencillas. Ejemplo 1.0.1 Consideremos la siguiente proposición: “6 es múltiplo de 2” Esta proposición es verdadera. Pero, ¿cómo lo justificamos? En este caso, simplemente debemos utilizar la siguiente definición: Definición 1.0.2 Múltiplo Un número natural x es múltiplo de otro número natural y si x = y · k para algún número natural k. Luego, como 6 = 2 · 3 donde 3 es un número natural, entonces 6 es múltiplo de 2 por la Definición 1.0.2. 7 8 1.1. Proposición Conjuntiva Ejemplo 1.1.1 Consideremos la siguiente proposición: “12 es par y 3 es primo” Como se trata de una conjunción entre dos proposiciones, para probar que es verdadera tenemos que ver que ambas proposiciones son verdaderas. ¿El 12 es un número par?. Recordemos la definición de número par: Definición 1.1.2 Número par Un número natural x es par si x = 2 · k para algún k natural. Dado que 12 = 2 · 6 donde 6 es un número natural, entonces 12 es par. ¿El 3 es un número primo?. Recordemos la definición de número primo: Definición 1.1.3 Número primo Un número primo es un número natural mayor que 1 que tiene únicamente dos divisores positivos distintos: él mismo y el 1. Puesto que los únicos divisores naturales de 3 son el 1 y el 3, entonces 3 es primo. Ası́, las proposiciones p: 12 es par y q: 3 es primo son ambas verdaderas. Por lo tanto, desde la lógica, podemos afirmar que la conjunción de ambas proposiciones será también verdadera. Luego, 12 es par y 3 es primo es una proposición verdadera. La “forma de razonar” utilizada en el Ejemplo 1.1.1 se basa en una regla lógica llamada producto lógico, la cual nos indica que si sabemos que vale una proposición p y también una proposición q, podemos concluir que vale la proposición p ∧ q. Se puede indicar del siguiente modo: Producto lógico (P rod) p q p∧q Este forma de razonar se emplea siempre que tengamos una proposición conjuntiva.  9 1.2. Proposición Disyuntiva Ejemplo 1.2.1 Supongamos que nuestra proposición es una disyunción como la siguiente: “6 es múltiplo de 2 o 6 es múltiplo de 4” Por tratarse de una disyunción, bastarı́a mostrar que una de las dos proposiciones es verda- dera para justificar la verdad de toda la proposición. En este caso, como 6 = 2 · 3 donde 3 es un natural entonces 6 es múltiplo de 2. Ası́, dadas las proposiciones p: 6 es múltiplo de 2 y q: 6 es múltiplo de 4 al menos una resulta verdadera. Por lo tanto, desde la lógica, podemos afirmar que la dis- yunción entre ambas proposiciones será también verdadera. Luego, 6 es múltiplo de 2 o 6 es múltiplo de 4 es una proposición verdadera. La “forma de razonar” utilizada en el Ejemplo 1.2.1 se basa en una regla lógica denominada Adición, la cual nos indica que si sabemos que una proposición p es verdadera, claramente la proposición p ∨ q también lo será (independientemente de si q es verdadera o falsa). Se puede indicar del siguiente modo: Adición (Ad) p p∨q Este forma de razonar se emplea siempre que tengamos una proposición disyuntiva. 1.3. Proposición Condicional Ejemplo 1.3.1 Consideremos la siguiente proposición, donde n es un número natural ar- bitrario: “Si n es par entonces n + 1 es impar” Claramente se trata del una proposición condicional de la forma p → q, donde p : n es par y q: n + 1 es impar. Si observamos la tabla de verdad del condicional 10 p q p→q V V V V F F F V V F F V podemos ver que: Si el antecedente p fuese falso, el condicional resultarı́a verdadero sin importar el valor de verdad de q. Si p fuese verdadero se requiere que q también sea verdadera para que el condicional resulte verdadero. Entonces no nos quedan dudas de que, para garantizar la verdad del condicional p → q necesitamos probar que si p es verdadero, q también debe resultar verdadero. Es por ello que, una estrategia válida para demostrar que vale un condicional p → q es suponer que p es verdadera (p es usualmente llamada hipótesis) y, utilizando tanto p como definiciones y propiedades establecidas con anterioridad, probar que q es verdadera (q es la tesis). En nuestro ejemplo procedemos tal como se muestra a continuación: Supongamos que n es un número par (Hipótesis) ⇒ n = 2 · k, con k natural (por definición de número par) ⇒ n + 1 = 2 · k + 1 (por propiedad matemática) ⇒ n + 1 es impar (por definición de número impar) (Tesis) Por lo tanto, la proposición “Si n es par entonces n + 1 es impar” es verdadera. La “forma de razonar” utilizada en el Ejemplo 1.3.1 está justificada por una regla lógica, basada en los valores de verdad de la implicación, que básicamente dice que si suponemos p y llegamos a q, podemos concluir que vale p → q. Esta regla lógica se la conoce como Teorema de la Deducción: Teorema de la Deducción (T D) Suponemos p · · · y llegamos a q p→q Este forma de razonar se emplea cuando tenemos una proposición condicional.  11 1.4. Generalizador y Particularizador Ejemplo 1.4.1 ¿Qué podrı́amos afirmar acerca de la suma de un número natural cualquiera y su consecutivo? Para responder a esta pregunta podrı́amos comenzar observando algunos ejemplos: 1+2=3 2+3=5 3+4=7 ··· 7 + 8 = 15 ··· 1230 + 1231 = 2461 ··· Una regularidad que podemos observar en estos ejemplos es que siempre el resultado de la suma da un número impar, con lo cual podrı́amos inferir la siguiente afirmación: “La suma de un número natural cualquiera y su consecutivo es un número impar” Sin embargo, esta proposición es, por el momento, una conjetura, es decir una proposición que suponemos, creemos que es verdadera, pero cuya verdad se basa en la sola observación de “algunos” casos particulares. Para estar seguros que nuestra conjetura es verdadera, deberı́amos recorrer “todos” los núme- ros naturales y probar que para cada uno de ellos se cumple que la suma del mismo más su consecutivo da un número impar, y eso es imposible dado que hay infinitos números natu- rales. Es por esto que debemos buscar otro tipo de justificación. Observemos que nuestra conjetura se puede reescribir de la siguiente manera: ∀x natural : x + (x + 1) es impar. Esta proposición es una generalización, es decir, el sı́mbolo principal es el generalizador “∀”. Para poder demostrar la proposición anterior lo que podemos hacer es considerar un número natural “a” arbitrario (pero fijo) y tratar de probar para dicho número que se cumple que a + (a + 1) es impar. En efecto, a + (a + 1) = (a + a) + 1 (por propiedad asociativa de la suma) =2·a+1 (por definición de suma de términos semejantes) Ası́, a + (a + 1) = 2 · a + 1 y por lo tanto a + (a + 1) es un número impar (por definición de número impar). Como hemos demostrado que a + (a + 1) es impar para un número natural “a” cualquiera y 12 el razonamiento usado es independiente del número natural considerado, podemos asegurar que la propiedad se cumple “para todos los naturales”, es decir que: ∀x natural : x + (x + 1) es impar ¿Cuál es la regla lógica que justifica lo realizado? Si llamamos “P (x)” a la propiedad “x+(x+1) es impar”, observemos que hemos demostrado que la propiedad P vale para un natural “a” arbitrario, es decir P (a). Luego, podemos concluir que la propiedad P vale para todo x natural, es decir: ∀xP (x). Esta regla tiene el nombre de Introducción del generalizador, y dice lo siguiente: Introducción del Generalizador (IG) P(a) ∀x P(x) Siempre y cuando “a” sea un elemento arbitario Lo que dice esta regla es que si sabemos que un elemento a “cualquiera” tiene una propiedad P , entonces podemos concluir que “todos” los elementos tienen la propiedad P. Hay otras proposiciones matemáticas que no comienzan con un generalizador, es decir, no son del tipo “Para todo...”, sino que comienzan con un particularizador, es decir con un “Existe...”. Ejemplo 1.4.2 Consideremos la siguiente proposición: “Existen naturales que son mayores que 5” En sı́mbolos: ∃x natural : x > 5 Observemos que en este caso no pedimos que “todos” los números naturales cumplan una propiedad, sino que haya al menos uno que cumple la propiedad, con lo cual esta proposición se puede demostrar simplemente “mostrando” un número natural que sea mayor que 5, por ejemplo el 6. Como 6 > 5, entonces ∃x natural : x > 5 es una proposición verdadera. En este ejemplo, el hecho de haber hallado un natural “a” (el 6) que cumpla la propiedad P (ser mayor que 5), nos autoriza a decir que “existen” naturales que verifican la propiedad. Esto es lo que expresa la siguiente regla lógica:  13 Introducción del Particularizador (IP ) P(a) ∃x P(x) Lo que afirma esta regla es que si sabemos que un elemento “a” tiene una propiedad P , podemos concluir que existe un x que tienen la propiedad P. Veamos algunas proposiciones más: Ejemplo 1.4.3 “No todos los números naturales son primos” Observando la “forma” de esta proposición vemos que en este caso se trata de la negación de un “para todo”. En sı́mbolos, serı́a ¬∀x P (x) (donde P designa a la propiedad de “ser primo”). Es claro que, para poder afirmar que “no todos los números naturales tienen la propiedad P ” bastarı́a mostrar que “hay al menos un número natural que no tiene la propiedad P ”. Esto es expresado por la siguiente regla lógica que nos indica cómo se niega un “para todo”. Negación del Generalizador (N G) ¬∀xP (x) ≡ ∃x¬P (x) Probar nuestra proposición, serı́a equivalente a probar que : “Existen números naturales que no son primos” La cual, como es un “existe”, se puede demostrar “mostrando” un número natural que no sea primo, por ejemplo el 4. Ejemplo 1.4.4 “No existe un número natural que sea menor que 1” Observando su “forma” vemos que en este caso se trata de la negación de un “existe”. Decir que “no existen individuos que cumplan la propiedad P ” es equivalente a decir que “todos los individuos no cumplen la propiedad P ”. Esto es lo que indica la siguiente regla lógica: 14 Negación del Particularizador (N P ) ¬∃xP (x) ≡ ∀x¬P (x) Teniendo en cuenta esta equivalencia lógica, podrı́amos demostrar nuestra proposición pro- bando que: “Todo número natural cumple que no es menor que 1” 1.5. Demostraciones Directas e Indirectas Tipos de razonamientos como los vistos en las secciones anteriores, que nos permiten ga- rantizar la verdad de las proposiciones es lo que los matemáticos comúnmente llaman demostración. Los ejemplos analizados nos permiten aproximarnos a lo que significa de- mostrar dentro de la comunidad de los matemáticos. Definición 1.5.1 Una demostración es una secuencia de pasos donde cada uno de ellos se justifica utilizando definiciones y propiedades ya establecidas con anterioridad, y que se ajusta a ciertas reglas de la lógica deductiva (esto es, a ciertas formas de razonar que la lógica considera válidas). Ejemplo 1.5.2 Consideremos ahora la siguiente proposición: “Para cualquier natural x se cumple que: si x es par entonces x2 también es par” En sı́mbolos: ∀x natural: x es par → x2 es par Demostración. Como la proposición tiene un generalizador, podemos considerar un número natural “a” arbitrario pero fijo y probar que para ese “a” cualquiera se cumple la propiedad: “Si a es par entonces a2 es par”. Como se trata de una implicación, comenzamos suponiendo el antecedente y tratamos de deducir el consecuente: Supongamos que a es un número par (Hipótesis) ⇒ a = 2 · k, con k natural (por definición de número par) ⇒ a2 = (2 · k)2 (por propiedad matemática) 2 ⇒ a = (2 · k)(2 · k) (por definición de potencia) 2 ⇒ a = 2 · (k · 2 · k) (por propiedad matematica) ⇒ a2 = 2 · m, con m = k · 2 · k natural (por propiedad matemática) 2 ⇒ a es par (por definición de némero par) (Tesis)  15 Por lo tanto, la proposición Si a es par entonces a2 es par es verdadera por regla lógica TD. Como hemos justificado la proposición para un número natural “a” fijo pero arbitrario, po- demos asegurar que la propiedad se cumple “para todos los naturales”, es decir: ∀x natural : si x es par entonces x2 es par (por regla lógica IG). Una demostración como la relizada en el Ejemplo 1.5.2 es lo que usualmente se denomina una prueba directa, donde partimos del antecedente y mediante una cadena de implicaciones llegamos al consecuente. Pero esto no siempre es posible de realizar, por lo que a veces se recurre a lo que se denominan pruebas indirectas. Hay dos tipos de pruebas indirectas: Demostración por contrarrecı́proca. Demostración por el absurdo. En lo que sigue veremos un ejemplo de una prueba por contrarrecı́proca. Ejemplo 1.5.3 Si quisiéramos probar que: ∀x natural: si x2 es par entonces x es par Consideramos “a” natural fijo pero arbitrario (podemos llamarlo “x” también). Deberı́amos demostrar que para ese “a” es verdadera la implicación: Si a2 es par entonces a es par. Esta es una expresión de tipo condicional p → q donde p : a2 es par y q : a es par. Como sabemos que una proposición condicional es lógicamente equivalente a su contra- rrecı́proca: p → q ≡ ¬q → ¬p en lugar de demostrar p → q, podrı́amos demostrar ¬q → ¬p, es decir: Si ¬(a es par) entonces ¬ (a2 es par). 16 O, lo que es lo mismo, Si a no es par entonces a2 no es par. Suponemos que a no es par ⇒ a es impar (por propiedad matemática) ⇒ a = 2 · k + 1 para algún k natural (por definición de número impar) 2 2 ⇒ a = (2k + 1) (elevando ambos miembros al cuadrado - propiedad matemática) ⇒ a2 = 4 · k 2 + 4 · k + 1 (por cuadrado de un binomio) 2 2
⇒ a = 4 · k + 4k + 1 (por propiedad asociativa de la suma) ⇒ a2 = 2 2 · k 2 + 2 · k + 1
(por propiedad matemática: factor común 2) 2 ⇒a =2·j+1 (donde j = 2 · k 2 + 2 · k y j es un natural por ser producto y suma de naturales) 2 ⇒ a es impar (por definición de número impar) 2 ⇒ a no es par (por propiedad matemática) De este modo, por regla lógica TD, hemos demostrado la verdad de la implicación: Si a no es par entonces a2 no es par. Y, por ende, de su equivalente: Si a2 es par entonces a es par (por Contrarrecı́poroca). Como además, hemos demostrado esto para un a arbitrario, por regla lógica IG podemos afirmar que: ∀x natural: x2 es par → x es par. En otras ocasiones, conviene abordar la prueba de una proposición matemática mediante una prueba por el absurdo, que consiste básicamente en suponer que no es cierto lo que queremos demostrar y, a partir de ello llegar a una contradicción. Eso nos garantizarı́a que nuestra suposición no es cierta y que, por lo tanto es verdadera la proposición que queremos demostrar. Ejemplo 1.5.4 Si quisiéramos demostrar que: 1 “ ∀x racional: Si x > 0 entonces x > 0” Podrı́amos tomar un número x racional arbitrario y suponer que no es cierto que: 1 si x > 0 entonces > 0, x  17 es decir,   1 ¬ x>0→ >0 (1.1) x Aquı́ nos queda la negación de una implicación, es decir: ¬(p → q), que es equivalente a: p ∧ ¬q: ¬(p → q) ≡ p ∧ ¬q Negación del condicional (NC) Con lo cual, (1.1) se puede escribir como   1 x>0∧¬ >0 x 1 ⇒x>0∧ ≤0 x 1 ⇒x· ≤0 x ⇒1≤0 con lo cual, llegamos a una contradicción, ya que sabemos que 1 > 0. Por lo tanto, nuestra suposición es falsa, luego la proposición original que querı́amos demostrar es verdadera. Esta demostración se basa en la regla lógica del Absurdo: Absurdo (Abs) Suponemos ¬p · · · y llegamos a q ∧¬ q p Nota 1.5.5 De todo lo visto destacamos que, para abordar la demostración de una proposi- ción matemática debemos tener en cuenta la forma lógica de la misma (es decir, ver si se trata de una conjunción, de una disyunción, de una generalización, de un existencial, etc.) y de acuerdo con ello ver qué estrategia conviene utilizar. Y recalcar cuáles son todos los pasos que hago en una demostración, cada uno de los cuales debe estar justificado mediante una definición o propiedad establecida con anterioridad, o por una regla de la lógica deductiva. 18 Capı́tulo 2 Teorı́a de Conjuntos El concepto de conjunto es de fundamental importancia en las matemáticas modernas. La mayorı́a de los matemáticos creen que es posible expresar todas las matemáticas en el len- guaje de la teorı́a de conjuntos. Nuestro interés en los conjuntos se debe tanto al papel que representan en las matemáticas como a su utilidad en la modelización e investigación de di- ferentes problemas. Los conjuntos fueron estudiados formalmente por primera vez por Georg Cantor (1845 − 1918). 2.1. Conjuntos y subconjuntos, pertenencia e inclusión Definición 2.1.1 Definición informal de conjuntos y elementos. Un conjunto es una colección de objetos, llamados elementos, que tiene la propiedad que dado un objeto cualquiera, se puede decidir si ese objeto es un elemento del conjunto o no. Observación 2.1.2 La definición de un conjunto no debe ser ambigua en el sentido de que pueda decidirse cuando un objeto particular pertenece, o no, a un conjunto. Los objetos pueden ser números, letras, rı́os, lugares, etc. Para denotar conjuntos se utilizan, en general, letras mayúsculas como A, B, C, X, Z, etc. Entonces, vamos a convenir denotar a los conjuntos con letras mayúsculas y a sus elementos con letras minúsculas. La afirmación “el elemento a pertenece al conjunto A” se escribe a∈A La negación de este hecho, ¬(a ∈ A) se escribe 19 20 a∈ /A y se lee “a no pertenece al conjunto A”. Ejemplo: Sea A = {1, 2, 3}, entonces 1 ∈ A, 2 ∈ A, 4∈ / A. Definición 2.1.3 Cardinalidad de un Conjunto Si A es un conjunto finito, se llama cardinal de A, a la cantidad de elementos de A y se denota #A o |A|. Ejemplo: Si A = {2, 4, 6, 8} entonces |A| = 4. Las definiciones comunes de un conjunto son por extensión y por comprensión. Definición 2.1.4 Un conjunto está definido por extensión cuando se especifican todos los elementos que forman el mismo. Se enumeran todos sus elementos colocándolos entre llaves y separándolos por comas. Ejemplos: El conjunto de las vocales del alfabeto: A = {a, e, i, o, u}. El conjunto formado por los números enteros, pares, no negativos, menores que 10: B = {0, 2, 4, 6, 8}. Nota 2.1.5 El orden de los elementos no importa en un conjunto, y en un conjunto no se tiene en cuenta repeticiones de elementos. A veces resulta inconveniente o imposible nombrar todos los elementos de un conjunto (por ejemplo en el caso de conjuntos que tienen infinitos elementos). En tales casos el conjunto se puede definir por comprensión. Definición 2.1.6 Un conjunto está definido por comprensión cuando se especifica una pro- piedad que caracteriza a todos los elementos del mismo. Ejemplos:  21 A = {x : x es una vocal del abecedario} B = {x : x ∈ Z, x es par y 0 ≤ x < 10} En general, A = {x : P (x)} donde P (x) es una propiedad que cumplen sus elementos. Los siguientes conjuntos numéricos se denotan por sı́mbolos especiales: N = {x : x es un número natural} = {1, 2, 3, 4,...} Z = {x : x es un número entero} = {..., −3, −2, −1, 0, 1, 2, 3, 4,...} nm o Q = {x : x es un número racional} = : m ∈ Z y n ∈ Z y n ̸= 0 n R = {x : x es un número real} Definición 2.1.7 Conjunto Universal y Conjunto Vacı́o Los elementos de todos los conjuntos en consideración pertenecen a un gran conjunto fijo llamado conjunto universal, que generalmente se denota U. El conjunto que no tiene elementos se llama conjunto vacı́o y se denota ∅. Definición 2.1.8 Subconjuntos e Inclusión. Sean A y B dos conjuntos. Diremos que A está contenido en B, y lo notaremos A ⊆ B, si cada elemento de A es un elemento de B. En este caso decimos también que A está incluido en B, o que A es un subconjunto de B. En sı́mbolos: A ⊆ B ⇔ ∀x (x ∈ A → x ∈ B) Si A no es un subconjunto de B se nota A ⊈ B. En sı́mbolos: A ⊈ B ⇔ ∃x (x ∈ A ∧ x ∈ / B) Ejemplo 2.1.9 Sea A = {1, 2, 3} entonces {1} ⊆ A, {2, 3} ⊆ A, ∅ ⊆ A, A ⊆ A, {3, 4} ⊈ A. N⊆Z⊆Q⊆R Si A ⊆ B y además B tiene al menos un elemento que no está en A, diremos que A está estrictamente contenido en B y lo denotaremos por A ⊂ B. En sı́mbolos: 22 A ⊂ B ⇔ A ⊆ B ∧ ∃x (x ∈ B ∧ x ∈ / A) Nota 2.1.10 El sı́mbolo ∀ significa “para todo” y el sı́mbolo ∃ significa “existe”. Definición 2.1.11 Igualdad de Conjuntos. Dos conjuntos A y B son iguales si tienen los mismos elementos. A = B ⇔ A ⊆ B ∧ B ⊆ A, o bien A = B ⇔ ∀x (x ∈ A ↔ x ∈ B). Es decir, A = B si tienen exactamente los mismos elementos (sin importar el orden y sin tener en cuenta las repeticiones). Ejemplo: Los conjuntos A = {Rojo, Amarillo, Azul} y B = {Azul, Rojo, Amarillo} son iguales. Proposición 2.1.12 Propiedades de la inclusión. 1) Todo conjunto A es subconjunto de sı́ mismo. 2) El conjunto vacı́o ∅ es subconjunto de cualquier conjunto. 3) Si A es un subconjunto de B y B es un subconjunto de C, entonces A es un subconjunto de C. Demostración 1) ∀A : A ⊆ A ya que se cumple ∀x (x ∈ A → x ∈ A). Esta última afirmación es verdadera ya que para cualquier x, siempre que el antecedente de la implicación sea verdadero, el consecuente también lo será. Ası́ la implicación resulta verdadera. 2) ∀A : ∅ ⊆ A ya que se cumple ∀x (x ∈ ∅ → x ∈ A). Esta última afirmación es verdadera ya que para cualquier x, el antecedente de la implicación es falso, luego la implicación resulta verdadera.  23 3) Suponemos el antecedente de la implicación que debemos demostrar, es decir, se supone que: A ⊆ B ⇔ ∀x (x ∈ A → x ∈ B) (Hipótesis 1) B ⊆ C ⇔ ∀x (x ∈ B → x ∈ C) (Hipótesis 2) Se quiere demostrar que A⊆C (Tesis), es decir, se debe probar que ∀x (x ∈ A → x ∈ C). (2.1) Sea x∈A ⇒x∈B (por hipótesis 1) ⇒x∈C (por hipótesis 2) Luego, por regla lógica vale x ∈ A → x ∈ C, y dado que x es arbitrario queda demostrado (2.1). Definición 2.1.13 Conjunto Partes. Sea A un conjunto. El conjunto de partes de A, que se nota P(A), es el conjunto formado por todos los subconjuntos de A, o sea el conjunto cuyos elementos son los subconjuntos de A. Es decir, P(A) = {X : X ⊆ A} o bien X ∈ P(A) ⇔ X ⊆ A. Ejemplo 2.1.14 a) Sea A = {a, b}, entonces P(A) = {∅, {a}, {b}, A}. b) Cualquiera sea el conjunto A, ∅ ∈ P(A) y A ∈ P(A). c) P (∅) = {∅}, o sea el conjunto que tiene como único elemento al conjunto vacı́o. Para pensar: Si A tiene n elementos, ¿cuántos elementos tendrá P(A)? 2.2. Diagramas de Venn Una representación gráfica para los conjuntos son los diagramas de Venn. El conjunto univer- sal se representa por el interior de un rectángulo y todos los demás conjuntos se representan por cı́rculos incluidos en el mismo. Sean A y B dos conjuntos, se tienen las siguientes posibilidades: 24 Si A ⊆ B B U A Si A y B no tienen elementos en común, en este caso se dice que los conjuntos son disjuntos. A B U Si A y B tienen elementos en común, pero no ocurre que uno de los conjuntos esté contenido en el otro. A B U Ejemplo 2.2.1 En el Ejemplo 2.1.9 hemos observado que N ⊆ Z ⊆ Q ⊆ R. Esta relación entre los conjuntos numéricos se representa en el siguiente diagrama de Venn.  25 R Q Z N 2.3. Operaciones entre Conjuntos Introduciremos las operaciones con conjuntos que nos van a permitir obtener nuevos con- juntos, partiendo de conjuntos ya conocidos. En lo que sigue A y B serán dos conjuntos cualesquiera de un universal arbitrario U. A continuación definiremos las principales operaciones entre conjuntos. Definición 2.3.1 Unión de Conjuntos. La unión de dos conjuntos A y B es el conjunto que tiene por elementos a los objetos que están en A o en B. A ∪ B = {x ∈ U : x ∈ A ∨ x ∈ B} La disyunción, ∨, se utiliza en el sentido inclusivo. Es decir si un elemento está en A y en B, está en la unión por estar en al menos alguno de ellos. Ası́, x ∈ A ∪ B ≡ x ∈ A ∨ x ∈ B. Diagrama de Venn de la unión: U A B 26 ¿Qué significa que x ∈ / A ∪ B? x∈/ A∪B ≡ ¬(x ∈ A ∪ B) (Def. de ∈) / ≡ ¬(x ∈ A ∨ x ∈ B) (Def.de Unión) ≡ ¬(x ∈ A) ∧ ¬(x ∈ B) (De Morgan- Regla lógica) ≡x∈ / A∧x∈ /B (Def. de ∈) / Ası́, se tiene que x ∈ / A∪B ≡x∈ / A∧x∈ / B. Ejemplos: Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10}, entonces A ∪ B = {1, 2, 3, 4, 5, 8, 10}. Sea U = R. Si I = {x ∈ R : x ≤ 2} = (−∞, 2] y J = {x ∈ R : −10 ≤ x < 10} = [−10, 10), entonces I ∪ J = {x ∈ R : x < 10} = (−∞, 10). Para pensar: ¿Será cierto en general, que |A ∪ B| = |A| + |B|? Definición 2.3.2 Intersección de Conjuntos. La intersección de dos conjuntos A y B es el conjunto que tiene por elementos a aquellos que están en A y en B simultáneamente. A ∩ B = {x ∈ U : x ∈ A ∧ x ∈ B} Ası́, x ∈ A ∩ B ≡ x ∈ A ∧ x ∈ B. Diagrama de Venn de la intersección: U A B Si A y B no tienen elementos en común, es decir A ∩ B = ∅, entonces diremos que A y B son conjuntos disjuntos.  27 ¿Qué significa que x ∈ / A ∩ B? x∈/ A∩B ≡ ¬(x ∈ A ∩ B) (Def. de ∈) / ≡ ¬(x ∈ A ∧ x ∈ B) (Def. de Intersección) ≡ ¬(x ∈ A) ∨ ¬(x ∈ B) (De Morgan) ≡x∈ / A∨x∈ /B (Def. de ∈) / Ası́, se tiene que x ∈ / A∩B ≡x∈ / A∨x∈ / B. Ejemplos: Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10}, entonces A ∩ B = {3, 5}. Sea U = R. Si I = {x ∈ R : x ≤ 2} = (−∞, 2] y J = {x ∈ R : −10 ≤ x < 10} = [−10, 10), entonces I ∩ J = {x ∈ R : −10 ≤ x ≤ 2} = [−10, 2]. Definición 2.3.3 Diferencia de Conjuntos. La diferencia de A con B es el conjunto que tiene por elementos a aquellos que están en A pero que no pertenecen a B. A − B = {x ∈ U : x ∈ A ∧ x ∈ / B} Ası́, x ∈ A − B ≡ x ∈ A ∧ x ∈ / B. Diagrama de Venn de la diferencia: A B U Ejemplos: Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10}, entonces A − B = {1, 2, 8} y B − A = {4, 10}. 28 Sea U = R. Si I = {x ∈ R : x ≤ 2} = (−∞, 2] y J = {x ∈ R : −10 ≤ x < 10} = [−10, 10), entonces I − J = (−∞, −10). Definición 2.3.4 Complemento de un Conjunto. El complemento de un conjunto A es el conjunto de todos los elementos de U que no están en A. Ac = {x ∈ U : x ∈ / A} = U − A Diagrama de Venn del complemento de un conjunto: U A Ejemplos: Sea U = {1, 2, 3}. Si A = {2}, entonces Ac = {1, 3}. Sea U = N. Si A = {2}, entonces Ac = {n ∈ N : n ̸= 2}. Definición 2.3.5 Diferencia Simétrica. La diferencia simétrica de A con B es el con- junto que tiene por elementos a aquellos que pertenecen a A o a B, pero no a ambos si- multáneamente. A △ B = {x ∈ U : x ∈ A ∪ B ∧ x ∈ / A ∩ B} = (A ∪ B) − (A ∩ B) Diagrama de Venn de la diferencia simétrica: U A B  29 Ejemplos: Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10}, entonces A △ B = {1, 2, 4, 8, 10}. Sea U = R. Si I = (−∞, 2] y J = [−10, 10), entonces I △ J = (−∞, −10) ∪ (2, 10). Teoremas 2.4. Propiedades de las Operaciones de Conjuntos Ejemplo 2.4.1 Para todo conjunto A y B se cumple A ⊆ A ∪ B. Si bien esta afirmación se puede visualizar mediante un diagrama de Venn, para demostrar que esta propiedad se cumple para cualquier conjunto A y B, debemos ver que se cumple la inclusión, es decir debemos probar que ∀x (x ∈ A → x ∈ A ∪ B). En efecto, sea x arbitrario y veamos que se cumple el condicional. x∈A ⇒x∈A∨x∈B (Regla lógica) ⇒x∈A∪B (Def. de Unión) Luego, vale x ∈ A → x ∈ A ∪ B, y puesto que x es arbitrario se logra ∀x (x ∈ A → x ∈ A ∪ B). Las operaciones de unión, intersección y complemento cumplen las siguientes propiedades. Sólo demostraremos algunas de ellas. Proposición 2.4.2 Leyes Conmutativas Dados dos conjuntos A y B de un universal arbitrario U, se verifica: 1) A ∪ B = B ∪ A 2) A ∩ B = B ∩ A Demostración 1) Para demostrar que A ∪ B = B ∪ A, por definición de igualdad de conjuntos, debemos ver que se cumplen las siguientes inclusiones: A ∪ B ⊆ B ∪ A y B ∪ A ⊆ A ∪ B. 30 En primer lugar probemos A ∪ B ⊆ B ∪ A, que por definición de inclusión equivale a ver: ∀x (x ∈ A ∪ B → x ∈ B ∪ A) Supongo x∈A∪B ⇒x∈A∨x∈B (Def. de Unión) (2.2) ⇒x∈B∨x∈A (Conmutativa de ∨ − Regla lógica) ⇒x∈B∪A (Def. de Unión) Luego, vale x ∈ A ∪ B → x ∈ B ∪ A. En segundo lugar se debe probar que B ∪ A ⊆ A ∪ B, es decir: ∀x (x ∈ B ∪ A → x ∈ A ∪ B) Supongo x∈B∪A ⇒x∈B∨x∈A (Def. de Unión) ⇒x∈A∨x∈B (Conmutativa de ∨) ⇒x∈A∪B (Def. de Unión) Luego, vale x ∈ B ∪ A → x ∈ A ∪ B. Al haber demostrado las dos inclusiones queda demostrada la igualdad de conjuntos. Como en (2.2) sólo se utilizan definiciones y reglas lógicas de equivalencia, en lugar de probar las dos inclusiones por separado, podrı́amos haber escrito la demostración como sigue: x∈A∪B ≡x∈A∨x∈B (Def. de Unión) ≡x∈B∨x∈A (Conmutativa de ∨ − Regla lógica) ≡x∈B∪A (Def. de Unión) Lo cual muestra que vale ∀x (x ∈ A ∪ B ↔ x ∈ B ∪ A). La demostración de 2) es análoga. Proposición 2.4.3 Leyes Asociativas Dados tres conjuntos A, B y C de un universal arbitrario U, se verifica: 1) (A ∪ B) ∪ C = A ∪ (B ∪ C) 2) (A ∩ B) ∩ C = A ∩ (B ∩ C) Proposición 2.4.4 Leyes Distributivas Dados tres conjuntos A, B y C de un universal arbitrario U, se verifica: 1) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)  31 2) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Proposición 2.4.5 Leyes Idempotentes Dado cualquier conjunto A en un universal arbitrario U, se verifica: 1) A ∪ A = A 2) A ∩ A = A Proposición 2.4.6 Leyes de Identidad Dado cualquier conjunto A en un universal arbitrario U, se verifica: 1) A ∪ ∅ = A 2) A ∪ U = U 3) A ∩ ∅ = ∅ 4) A ∩ U = A Demostración Veamos 1) A ∪ ∅ = A, es decir debemos probar: ∀x (x ∈ A ∪ ∅ ↔ x ∈ A). En efecto x∈A∪∅ ≡ x ∈ A ∨ x ∈ ∅ (Def. de Unión) ≡ x ∈ A ∨ F alse (Def. Conjunto vacı́o) ≡x∈A (Regla Lógica) Veamos 4) A ∩ U = A, es decir debemos probar: ∀x (x ∈ A ∩ U ↔ x ∈ A). En efecto x∈A∩U ≡ x ∈ A ∧ x ∈ U (Def. de Intersección) ≡ x ∈ A ∧ T rue (Def. Conjunto universal) ≡x∈A (Regla Lógica) Proposición 2.4.7 Ley Involutiva Dado un conjunto A cualquiera de un universal U, se verifica: (Ac )c = A 32 Proposición 2.4.8 Leyes del Complemento Dado cualquier conjunto A en un universal arbitrario U, se verifica: 1) A ∪ Ac = U 2) A ∩ Ac = ∅ 3) U c = ∅ 4) ∅c = U Ejemplo 2.4.9 ¿Será cierto que (A ∪ B)c = Ac ∪ Bc ? La respuesta es NO. Para justificarlo daremos un contraejemplo. Sean U = {1, 2, 3, 4, 5}, A = {1, 2, 3} y B = {3, 5}. Observar que: A ∪ B = {1, 2, 3, 5}, y por lo tanto (A ∪ B)c = {4} Ac = {4, 5} y B c = {1, 2, 4}, y por lo tanto Ac ∪ B c = {1, 2, 4, 5}. Ası́ se tiene que (A ∪ B)c ̸= Ac ∪ B c. Proposición 2.4.10 Leyes de De Morgan Dados dos conjuntos A y B de un universal U, se verifica: 1) (A ∪ B)c = Ac ∩ B c 2) (A ∩ B)c = Ac ∪ B c Demostración Veamos 1) (A ∪ B)c = Ac ∩ B c. En efecto, x ∈ (A ∪ B)c ≡x∈ / A∪B (Def. de Complemento) ≡ ¬(x ∈ A ∪ B) (Def. de ∈) / ≡ ¬(x ∈ A ∨ x ∈ B) (Def. de Unión) ≡ ¬(x ∈ A) ∧ ¬(x ∈ B) (De Morgan- Regla lógica) ≡x∈ / A∧x∈ /B (Def. de ∈) / ≡ x ∈ Ac ∧ x ∈ B c (Def. de Complemento) c c ≡x∈A ∩B (Def. de Intersección)  33 Ejemplo 2.4.11 Demostrar que la siguiente afirmación A⊆B ⇒A∪B =B es cierta para cualquier par de conjuntos A y B. En efecto, suponemos el antecedente A⊆B Hipótesis la cual equivale a ∀x(x ∈ A → x ∈ B). Queremos demostrar el consecuente A∪B =B Tesis En este caso para demostrar la igualdad debemos probar dos inclusiones: Veamos A ∪ B ⊆ B Sea x ∈ A ∪ B ⇒x∈A∨x∈B (Def. de Unión) Si x ∈ A ⇒ x ∈ B (Hipótesis) Si x ∈ B ⇒ x ∈ B (Regla lógica) ⇒x∈B (Regla Lógica) Veamos B ⊆ A ∪ B Sea x∈B ⇒x∈A∨x∈B (Regla lógica) ⇒x∈A∪B (Def. de Unión) Luego, se deduce la tesis A ∪ B = B, quedando demostrada la propiedad. 2.5. Tablas de Verdad de la Lógica proposicional Otra forma de visualizar las operaciones entre conjuntos es por medio de las tablas de verdad de la lógica proposicional. Como vimos anteriormente, las operaciones básicas y las relaciones entre conjuntos están definidas por medio de conectores lógicos (∧, ∨, ¬, →, ↔). Tablas de verdad de los conectores lógicos Sean p, q proposiciones, es decir afirmaciones que son o bien verdaderas o bien falsas. Las tablas de verdad de los conectores lógicos son las siguientes: 34 p ¬p V F F V p q p∨q V V V V F V F V V F F F p q p∧q V V V V F F F V F F F F p q p→q V V V V F F F V V F F V p q p↔q V V V V F F F V F F F V Veamos cómo las tablas de verdad de los conectores lógicos se relacionan con las tablas de las operaciones de conjuntos. Dados A y B conjuntos incluidos en un conjunto universal U, y sea un elemento x ∈ U, se puede definir las siguientes proposiciones p y q: p : “x ∈ A” y q : “x ∈ B” Notemos que la proposición p es verdadera si sólo si el elemento x de U pertenece al subcon- junto A. Esto describe dos posibilidades para cualquier elemento genérico x de U, que p sea verdadera (si x pertenece a A) o que p sea falsa (si x no pertenece a A). Del mismo modo, tenemos dos posibilidades para la proposición q. Las tablas de verdad de las operaciones de conjuntos se corresponden con las tablas de verdad de los conectores lógicos de la siguiente manera: Complemento: El complemento de A en U, Ac , se corresponde con ¬p. Unión: A ∪ B se corresponde con p ∨ q.  35 Intersección: A ∩ B se corresponde con p ∧ q. Inclusión: A ⊆ B se corresponde con p → q. Igualdad: A = B se corresponde con p ↔ q. Usando los valores de verdad de cada proposición, las tablas de verdad de las operaciones y relaciones entre conjuntos quedarı́an como sigue: A Ac V F F V A B A∪B V V V V F V F V V F F F A B A∩B V V V V F F F V F F F F A B A△B V V F V F V F V V F F F A B A⊆B V V V V F F F V V F F V A B A=B V V V V F F F V F F F V 36 De la definición de diferencia, se puede demostrar que A − B = A ∩ Bc. (Ejercicio) Luego, la tabla de verdad de la diferencia es A B Bc A − B = A ∩ Bc V V F F V F V V F V F F F F V F Ejemplo 2.5.1 Ley de De Morgan (A ∪ B)c = Ac ∩ B c A B A∪B (A ∪ B)c Ac Bc Ac ∩ B c (A ∪ B)c = Ac ∩ B c V V V F F F F V V F V F F V F V F V V F V F F V F F F V V V V V Se observa que las columnas correspondientes a (A ∪ B)c y Ac ∩ B c son iguales, o sea los elementos pertenecen a (A ∪ B)c si y solo si pertenecen a Ac ∩ B c. Luego los dos conjuntos son iguales. A ∩ B ⊆ (B − C) ∪ (A ∩ C) : A B C A∩B B−C A∩C (B − C) ∪ (A ∩ C) A ∩ B ⊆ (B − C) ∪ (A ∩ C) V V V V F V V V V V F V V F V V V F V F F V V V V F F F F F F V F V V F F F F V F V F F V F V V F F V F F F F V F F F F F F F V La columna correspondiente a la inclusión es verdadera siempre, lo que significa que la afirmación A ∩ B ⊆ (B − C) ∪ (A ∩ C) es verdadera. Ejemplo 2.5.2 Las tablas de verdad sirven para decidir si una afirmación sobre conjuntos es verdadera o falsa. Retomando el Ejemplo 2.4.9, si se realiza la tabla de verdad para (A ∪ B)c = Ac ∪ B c se tiene:  37 A B A∪B (A ∪ B)c Ac Bc Ac ∪ B c V V V F F F F V F V F F V V F V V F V F V F F F V V V V En la tabla se observa que las columnas correspondientes a (A∪B)c y Ac ∪B c no son iguales, y esto implica que la igualdad (A ∪ B)c = Ac ∪ B c no se cumple para cualquier conjunto A y B. 2.6. Partición de un Conjunto Definición 2.6.1 Una familia de conjuntos A1 , A2 , A3 ,..., An se dice partición de un conjunto A si se verifica: 1) Ai ∩ Aj = ∅ ∀i, j tal que i ̸= j (son disjuntos dos a dos) n S 2) Ai = A i=1 Ejemplo 2.6.2 Sea A = {a, b, c, d, e, f } Si tomamos A1 = {a, b, d}, A2 = {c, f } y A3 = {e} forman una partición de A ya que se cumple: 1) A1 ∩ A2 = ∅ A1 ∩ A3 = ∅ A2 ∩ A3 = ∅ 2) A1 ∪ A2 ∪ A3 = A Si tomamos A1 = {a, d, f } y A2 = {b, c, e} forman otra partición de A ya que: 1) A1 ∩ A2 = ∅ 2) A1 ∪ A2 = A En cambio si se considera A1 = {a, b, d}, A2 = {e, f } y A3 = {b, c, e} no forman una partición de A ya que si bien se cumple A1 ∪A2 ∪A3 = A, no se cumple que A2 ∩A3 = ∅. 2.7. Producto Cartesiano de Conjuntos Definición 2.7.1 (Producto cartesiano) Sean A y B conjuntos. El producto cartesiano de A con B, que se denota A × B, es el conjunto de pares ordenados A × B = {(x, y) : x ∈ A ∧ y ∈ B} 38 Para pensar: Si A tiene n elementos y B tiene m elementos, ¿cuántos elementos tendrá A × B? Elementos Ejemplo 2.7.2 a) Sean A = {1, 2, 3}, B = {a, b}. Entonces, A × B = {(1, a), (1, b), (2, a) (2, b), (3, a) (3, b)} B × A = {(a, 1), (a, 2), (a, 3) (b, 1), (b, 2) (b, 3)} B × B = {(a, a), (a, b), (b, a), (b, b)}. b) Si A = B = R, entonces R × R es el plano real R2. c) A × ∅ = ∅ y ∅ × B = ∅. Observación 2.7.3 Si A ̸= B son ambos no vacı́os, entonces A × B ̸= B × A. De manera análoga se puede definir el producto cartesiano de n conjuntos A1 , A2 ,..., An como el conjunto de n-uplas ordenadas: A1 × A2 × · · · × An = {(x1 , x2 ,..., xn ) : x1 ∈ A1 , x2 ∈ A2 ,..., xn ∈ An } Proposición 2.7.4 El producto cartesiano es distributivo respecto de la intersección y la unión de conjuntos, es decir, si A, B y C son tres conjuntos cualesquiera, se verifica: a) A × (B ∩ C) = (A × B) ∩ (A × C) b) A × (B ∪ C) = (A × B) ∪ (A × C) c) (A ∩ B) × C = (A × C) ∩ (B × C) d) (A ∪ B) × C = (A × C) ∪ (B × C) Demostración a) Veamos que A × (B ∩ C) = (A × B) ∩ (A × C). En efecto, sea (x, y) un elemento arbitrario de A × (B ∩ C), entonces: (x, y) ∈ A × (B ∩ C) ≡ x ∈ A ∧ y ∈ (B ∩ C) (Def. de producto cartesiano) ≡ x ∈ A ∧ (y ∈ B ∧ y ∈ C) (Def. de intersección) ≡ (x ∈ A ∧ x ∈ A) ∧ (y ∈ B ∧ y ∈ C) (Regla lógica) ≡ (x ∈ A ∧ y ∈ B) ∧ (x ∈ A ∧ y ∈ C) (Asoc. y Conm. de ∧) ≡ (x, y) ∈ A × B ∧ (x, y) ∈ A × C (Def. de producto cartesiano) ≡ (x, y) ∈ (A × B) ∩ (A × C) (Def. de intersección) Luego, ∀(x, y) ((x, y) ∈ A × (B ∩ C) ↔ (x, y) ∈ (A × B) ∩ (A × C)) es decir, A × (B ∩ C) = (A × B) ∩ (A × C). Los demás incisos se prueban de forma similar. Capı́tulo 3 Relaciones En este capı́tulo estudiaremos algunas estructuras básicas que pueden representarse a través de la relación entre elementos de conjuntos. Hasta el momento han trabajado con distintas relaciones, por ejemplo la equivalencia entre proposiciones, y también vimos la relaciones de inclusión e igualdad para conjuntos. 3.1. Relación Binaria Dados dos conjuntos (no necesariamente distintos) es posible vincular o relacionar los ele- mentos de ambos. Esta viculación se llama relación binaria. Por ejemplo, si tenemos un conjunto A formado por diferentes unidades de medida y un conjunto B formado magnitudes fı́sicas: A = {Metro, Segundo, Fahrenheit, Kilogramo, Milı́metro, Kelvin} B = {Longintud, Tiempo, Masa, Temperatura} Podemos relacionar cada unidad de medida del conjunto A con la magnitud fı́sica que permite medir, de la siguiente manera: Unidad (A) Magnitud Fı́sica (B) Metro Longitud Segundo Tiempo Fahrenheit Temperatura Kilogramo Masa Milı́metro Longitud Kelvin Temperatura Definición 3.1.1 (Relación Binaria) Sean A y B conjuntos. Una relación R de A en B es un subconjunto del producto cartesiano A × B. Es decir, R ⊆ A × B. 39 40 Ejemplo 3.1.2 Sean A = {3, 4, 5} y B = {a, b}. Entonces R1 = {(4, a), (4, b), (5, b)}, R2 = A × B y R3 = ∅ son ejemplos de relaciones de A en B. Por otro lado R4 = {(a, 4), (b, 3), (a, 5)} y R5 = {(a, 3)} son ejemplos de relaciones de B en A. Notación: Dados x ∈ A, y ∈ B y una relación R de A en B, se dice que x está relacionado con y (por la relación R) si (x, y) ∈ R y se escribe xRy. Cuando (x, y) ∈/ R, se dice x no está relacionado con y y se escribe xRy. Ası́, continuando con el Ejemplo 3.1.2 se tiene que 4R1 a 5R1 b R1 b 3 bR4 3 R4 5. b Definición 3.1.3 (Dominio e Imagen) Llamaremos dominio de una relación R al conjunto formado por todos los primeros ele- mentos de los pares ordenados que pertenecen a R, e imagen al conjunto formado por los segundos elementos. Es decir, si R es una relación de A a B, entonces Dom(R) = {a ∈ A, ∃b : b ∈ B ∧ (a, b) ∈ R} Img(R) = {b ∈ B, ∃a : a ∈ A ∧ (a, b) ∈ R} Ası́, en el ejemplo anterior, el dominio de R1 es Dom(R1 ) = {4, 5} y la imagen es Img(R1 ) = {a, b}. 3.2. Representaciones de una Relación Dados dos conjuntos A y B, finitos y no vacı́os, A = {a1 , a2 ,..., am }, B = {b1 , b2 ,..., bn }, y una relación R cualquiera de A a B, se pueden utilizar distintas representaciones de R. Ilustraremos las distintas formas de representación mediante un ejemplo: Sean A = {2, 4, 6}, B = {1, 3, 5, 6} y la relación de A en B R = {(2, 3), (2, 5), (2, 6), (4, 5), (4, 6)}.  41 1) Mediante Tablas A B 2 3 2 5 2 6 4 5 4 6 2) Mediante Diagrama de Venn A B 2 1 3 4 5 6 6 3) Mediante una Matriz Booleana de ceros y unos Sea R una relación de A en B. Llamaremos matriz de la relación R a la siguiente matriz booleana:   1 si (ai , bj ) ∈ R MR = (rij ) : rij = 0 si (ai , bj ) ∈ /R  donde i = 1, 2,..., m; j = 1, 2,..., n y rij representa el elemento de la matriz que está en la fila i columna j. En el caso del ejemplo la matriz de la relación es:   0 1 1 1 MR = 0 0 1 1 0 0 0 0 Observación 3.2.1 ˆ La matriz de una relación caracteriza a la misma, o sea, si se conoce la relación se conoce la matriz, y si se conoce la matriz sabemos de qué relación se trata. 42 ˆ Cada fila de la matriz se corresponde con un elemento del conjunto A y cada columna con un elemento de B. Para calcular el dominio de R bastará ver en qué filas hay, al menos, un uno y para calcular la imagen bastará con ver en qué columnas hay, al menos, un uno. 4) Mediante Gráfico Cartesiano Sólo se puede representar una relación R ⊆ A × B mediante un gráfico cartesiano si A y B son conjuntos numéricos. En el ejemplo, se tiene y 6 5 4 3 2 1 x 1 2 3 4 5 6 3.3. Relación de un conjunto en si mismo Supongamos ahora, que tenemos una relación binaria R de un conjunto A en sı́ mismo. En este caso se dice que R está definida sobre A. Esto es, R está definida sobre A si R ⊆ A × A. Ejemplo 3.3.1 Sea A = {a, b, c, d}, entonces R = {(a, a), (a, b), (a, d), (b, b), (c, d), (d, a)} es una relación sobre A.  43 ≤ es una relación en R. En el caso de conjuntos finitos, a estas relaciones se las puede representar mediante un grafo dirigido o digrafo. Definición 3.3.2 (Grafo dirigido) Un Grafo Dirigido o Digrafo es un par ordenado D = (A, R), donde A es un conjunto finito y R es una relación binaria definida sobre A. Al conjunto A lo llamaremos conjunto de nodos o vértices de D. A los elementos de R los llamaremos arcos o aristas del digrafo D. Observación 3.3.3 Un grafo dirigido caracteriza a una relación, es decir, si se conoce la relación se conoce el digrafo, y si se conoce el digrafo puede establecerse la relación. El dominio y la imagen de R están formados por los puntos que son, respectivamente, extremo inicial y final de algún arco. Representación gráfica de un grafo dirigido Tomaremos los elementos de A como puntos del plano y cuando dos elementos x e y de A estén relacionados, es decir xRy, trazaremos un arco dirigido desde x hasta y. A x lo llamaremos vértice inicial y al y, vértice final de la arista (x, y). A una arista que una un punto consigo mismo la llamaremos bucle o lazo. A un vértice que no sea inicial ni final de ninguna arista, lo llamaremos aislado. Ejemplo 3.3.4 En la siguiente figura mostramos la representación gráfica de un digrafo D = (A, R), siendo A = {a, b, c, d} y R = {(a, a), (a, c), (b, c)}. a b Aislado c d 44 Las aristas son (a, a), (a, c) y (b, c). d es un vértice aislado. Ejemplo 3.3.5 Sea A = {1, 2, 3, 4}. Consideramos la siguiente relación R definida sobre A: (x, y) ∈ R ⇔ x + y es par. Ası́, la relación R descripta por extensión es: R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}. Su representación mediante un digrafo es: 1 2 3 4 3.4. Funciones Una función es un tipo particular de relación. Definición 3.4.1 (Función) Sean A y B conjuntos, y sea R una relación de A en B. Se dice que R es una función cuando todo elemento x ∈ A está relacionado con algún elemento y ∈ B, y este elemento y es único. Es decir: ∀x ∈ A, ∃!y ∈ B : xRy. Aquı́ el sı́mbolo “∃!” significa “existe un único”, es decir ∀x ∈ A, ∃y ∈ B tal que xRy y si y, z ∈ B son tales que xRy y xRz, entonces y = z.  45 Como a cada x ∈ A le corresponde y ∈ B y este y es único, se le puede dar un nombre para notar que y depende de x. Se dice que y es la imagen de x por f , y suele denotarse “y = f (x)”, que es la notación usual que usamos para las funciones. Se nota f : A → B a una función del conjunto A en el conjunto B. Ejemplo 3.4.2 Sean A = {2, 4, 6} y B = {1, 3, 5, 6}. Si R = {(2, 3), (4, 5)} R A B 2 1 3 4 5 6 6 La relación R no es función ya que el elemento 6 ∈ A no está relacionado con ningún elemento de B. Si S = {(2, 3), (4, 5), (6, 5)} S A B 2 1 3 4 5 6 6 La relación S es función ya que cada elemento de A está relacionado con un único elemento de B. Si T = {(2, 1), (2, 3), (4, 5), (6, 5)} 46 T A B 2 1 3 4 5 6 6 La relación T no es función ya que el elemento 2 ∈ A está relacionado con dos ele- mentos distintos de B. La relación R ⊆ R × R dada por R = {(x, x2 ) : x ∈ R} es la función f : R → R, f (x) = x2. y y = x2 x 3.5. Relación Inversa Definición 3.5.1 (Relación Inversa) Dada la relación binaria R de A en B, definimos la relación binaria R−1 , de la siguiente manera: R−1 = {(y, x) ∈ B × A : (x, y) ∈ R} Es decir, y R−1 x ⇔ xRy Observemos que R−1 ⊆ B × A.  47 Ejemplo 3.5.2 Sean A = {2, 4, 6} y B = {1, 3, 5, 6}. Considerar R ⊆ A × B definida por: (x, y) ∈ R ⇔ x < y. O sea, R = {(2, 3), (2, 5), (2, 6), (4, 5), (4, 6)}. Entonces R−1 = {(3, 2), (5, 2), (6, 2), (5, 4), (6, 4)}, es decir (x, y) ∈ R−1 ⇔ x > y. Para pensar... ¿Quién será Dom(R−1 ) y Img(R−1 )? Ejemplo 3.5.3 Veamos un ejemplo de una relación binaria con infinitos elementos. Sea R ⊆ N × N definida por (x, y) ∈ R ⇔ y > x + 1. Es claro que esta relación tiene infinitos elementos. ¿Quién será R−1 ? R−1 = {(y, x) ∈ N × N : (x, y) ∈ R} = {(y, x) ∈ N × N : y > x + 1} = {(x, y) ∈ N × N : x > y + 1} (cambiando las variables) = {(x, y) ∈ N × N : y < x − 1} 3.6. Operaciones entre Relaciones Las relaciones son conjuntos, y como tales, podemos someterlas a operaciones como la unión, intersección, etc. Ejemplo 3.6.1 Sean A = {2, 4, 6} y B = {1, 3, 5, 6}. Si R = {(2, 3), (2, 5), (2, 6), (4, 5), (4, 6)} ⊆ A × B y S = {(2, 1), (4, 5)} ⊆ A × B, entonces R ∪ S = {(2, 3), (2, 5), (2, 6), (4, 5), (4, 6), (2, 1)} R ∩ S = {(4, 5)}. También podemos definir la composición de relaciones 48 Definición 3.6.2 (Composición de Relaciones) Sean las relaciones R ⊆ A×B y S ⊆ B ×C, se llama composición entre R y S a la siguiente relación: S ◦ R = {(x, z) ∈ A × C/ ∃y ∈ B : (x, y) ∈ R ∧ (y, z) ∈ S}. Gráficamente R S A B C x y z Ejemplo 3.6.3 Sean A = {2, 4, 6}, B = {1, 3, 5, 6} y C = {3, 5, 7, 9}. Si R ⊆ A × B, R = {(2, 3), (2, 5), (2, 6), (4, 5), (4, 6)}, y S ⊆ B × C, S = {(1, 3), (3, 5), (5, 7)}. R S A B C 2 1 3 3 5 4 5 7 6 6 9 Ası́, por ejemplo (2, 5) ∈ S ◦ R ya que ∃ 3 ∈ B : (2, 3) ∈ R ∧ (3, 5) ∈ S. Se tiene S ◦ R = {(2, 5), (2, 7), (4, 7)}. 3.7. Generalización Muchas veces es útil relacionar elementos de varios conjuntos, por tal motivo introducimos la siguiente definición.  49 Definición 3.7.1 (Generalización de Relación) Sean los conjuntos A1 , A2 ,..., An. Una relación R sobre A1 × A2 ×... × An es cualquier subconjunto de este producto cartesiano, es decir, R ⊆ A1 × A2 ×... × An. Observación 3.7.2 Si R = ∅ la llamaremos la relación vacı́a. Si R = A1 × A2 ×... × An la llamaremos la relación universal. Si n = 2 diremos que es una relación binaria, y si n = 3 una ternaria. 3.8. Propiedades de las Relaciones A continuación analizaremos algunas propiedades que tienen las relaciones definidas sobre un conjunto. 3.8.1. Reflexividad Una relación binaria R sobre un conjunto A se dice reflexiva, cuando cada elemento de A está relacionado consigo mismo. Es decir R es reflexiva ⇔ ∀a ∈ A : aRa O equivalentemente, R es reflexiva ⇔ ∀a ∈ A : (a, a) ∈ R. Ejemplo 3.8.1 Sea A = {1, 2, 3, 4} y R = {(1, 1), (1, 2), (2, 2), (3, 3), (3, 2), (4, 4)} una relación definida en A. R es reflexiva ya que para cada a ∈ A, el par (a, a) está en la relación. Más precisamente, se tiene: 1R1 2R2 3R3 4R4 El digrafo de la relación es: 50 1 2 3 4 Si una relación es reflexiva, el digrafo correspondiente debe tener un lazo en cada vértice. La matriz de la relación es:   1 1 0 0 0 1 0 0 MR =  0 1  1 0 0 0 0 1 Si una relación es reflexiva, la matriz debe tener todos 1 en su diagonal principal. Observación 3.8.2 Diremos que una relación no es reflexiva si: ∃a ∈ A : (a, a) ∈ / R. 3.8.2. Arreflexiva Una relación R sobre un conjunto A es arreflexiva si cumple: ∀a ∈ A : (a, a) ∈ /R Ejemplo 3.8.3 Sea A = {1, 2, 3, 4} y R = {(1, 2), (3, 2)} una relación definida en A. R es arreflexiva ya que para cada a ∈ A, el par (a, a) no está en la relación. Más precisamente, se tiene: 1R1 2R2 3R3 4R4 Observación 3.8.4 Si una relación es arreflexiva, ningún vértice del digrafo tiene un lazo. Si una relación es arreflexiva, la matriz debe tener todos 0 en su diagonal principal.  51 3.8.3. Simetrı́a Una relación binaria R sobre un conjunto A se dice simétrica, si cada vez que un elemento a está relacionado con otro elemento b, entonces b está relacionado con a, es decir: R es simétrica ⇔ ∀a, b ∈ A : (aRb ⇒ bRa) Ejemplo 3.8.5 Sea A = {1, 2, 3, 4} y R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)} una relación definida en A. R es simétrica ya que las siguientes implicaciones son verdaderas Si (1, 1) ∈ R ⇒ (1, 1) ∈ R Si (1, 2) ∈ R ⇒ (2, 1) ∈ R Si (2, 1) ∈ R ⇒ (1, 2) ∈ R Si (2, 3) ∈ R ⇒ (3, 2) ∈ R Si (3, 2) ∈ R ⇒ (2, 3) ∈ R y los demás casos son verdaderos ya que el antecedente es falso. Ası́, se ha verificado que la implicación es verdadera para todo par de elementos a, b ∈ A. El digrafo de la relación es: 1 2 3 4 Si una relación es simétrica, el grafo correspondiente tiene la propiedad de que si existe una arista dirigida de a a b, debe existir otra arista dirigida de b en a. O dicho de otro modo, entre los vértices distintos no puede haber sólo una arista. La matriz de la relación es:   1 1 0 0 1 0 1 0 MR =  0  1 0 0 0 0 0 0 52 La matriz de una relación simétrica debe ser simétrica respecto de su diagonal principal, es decir rij = rji ∀i, j. Observación 3.8.6 Cuidado!!! La propiedad de simetrı́a no dice que ∀a, b ∈ A : (aRb ∧ bRa) Diremos que una relación R no es simétrica si: ∃a, b ∈ A : (a, b) ∈ R ∧ (b, a) ∈ / R. 3.8.4. Asimetrı́a Una relación binaria R sobre un conjunto A se dice que es asimétrica si cada vez que aRb se sigue que bRa. Es decir, ∀a, b ∈ A : ((a, b) ∈ R ⇒ (b, a) ∈ / R). Ejemplo 3.8.7 Sea A = {1, 2, 3, 4} y R = {(1, 2), (1, 4), (2, 3)} una relación definida en A. R es asimétrica ya que las siguientes implicaciones son verdaderas Si (1, 2) ∈ R ⇒ (2, 1) ∈ /R Si (1, 4) ∈ R ⇒ (4, 1) ∈ /R Si (2, 3) ∈ R ⇒ (3, 2) ∈ /R y los demás casos son verdaderos ya que el antecedente es falso. Ası́, se ha verificado que la implicación es verdadera para todo par de elementos a, b ∈ A. Observación 3.8.8 Si una relación es asimétrica, el grafo correspondiente tiene la propiedad de que entre dos vértices distintos existe a lo sumo una arista. Además no puede tener lazos. La matriz de una relación asimétrica satisface la propiedad ∀i, j rij = 0 ó rji = 0.  53 3.8.5. Antisimetrı́a Una relación binaria R sobre un conjunto A se dice antisimétrica, si la única manera de que a esté relacionado con b y b esté relacionado con a, es que a y b sean iguales. Es decir: R es antisimétrica ⇔ ∀a, b ∈ A : (aRb ∧ bRa ⇒ a = b). Ejemplo 3.8.9 Sea A = {1, 2, 3, 4} y R = {(1, 1), (1, 2), (2, 3), (3, 4)} una relación definida en A. R es antisimétrica ya que la siguiente implicación es verdadera Si (1, 1) ∈ R ∧ (1, 1) ∈ R ⇒ 1 = 1 y los demás casos son verdaderos ya que el antecedente es falso. Ası́, se ha verificado que la implicación es verdadera para todo par de elementos a, b ∈ A. El digrafo de la relación es: 1 2 3 4 Si una relación es antisimétrica, el grafo correspondiente tiene la propiedad de que entre cualquier par de vértices a y b distintos, debe existir a lo sumo una arista dirigida. La matriz de la relación es:   1 1 0 0 0 0 1 0 MR =  0  0 0 1 0 0 0 0 54 La matriz de una relación antisimétrica cumple que ∀i ̸= j rij = 0 ó rji = 0. Observación 3.8.10 Diremos que una relación R no es antisimétrica si: ∃a, b ∈ A : a ̸= b ∧ (a, b) ∈ R ∧ (b, a) ∈ R 3.8.6. Transitividad Una relación binaria R sobre un conjunto A se dice transitiva, si cuando a se relaciona con b y b se relaciona con c, resulta que a se relaciona con c. Es decir: R es transitiva ⇔ ∀a, b, c ∈ A : (aRb ∧ bRc ⇒ aRc) Ejemplo 3.8.11 Sea A = {1, 2, 3, 4} y R = {(1, 2), (1, 3), (1, 4), (2, 3)} una relación definida en A. R es transitiva ya que la siguiente implicación es verdadera Si (1, 2) ∈ R ∧ (2, 3) ∈ R ⇒ (1, 3) ∈ R y los demás casos son verdaderos ya que el antecedente es falso. Ası́, se ha verificado que la implicación es verdadera para toda terna de elementos a, b, c ∈ A. La matriz de la relación es:   0 1 1 1 0 0 1 0 MR =  0  0 0 0 0 0 0 0 La matriz de una relación transitiva cumple que si rij = 1 y rjk = 1 entonces rik = 1. El digrafo de la relación es:  55 1 2 3 4 Si una relación es transitiva, el grafo correspondiente tiene la propiedad de que cada vez que haya una arista dirigida de a en b y una de b en c, debe existir arista de a en c. Observación 3.8.12 Diremos que una relación R no es transitiva si: ∃a, b, c ∈ A : (a, b) ∈ R ∧ (b, c) ∈ R ∧ (a, c) ∈ / R. Para pensar... Sea R una relación definida en un conjunto A, ¿puede tener las propiedades simétrica y antisimétrica?. 56 3.9. Ejemplos Ejemplo 3.9.1 Sea R la relación definida sobre A = {a, b, c, d} por el siguiente digrafo: a b c d Entonces R = {(a, b), (b, d), (a, d), (c, a), (a, c)}. No es reflexiva ya que ∃b ∈ A : (b, b) ∈ / R. Es arreflexiva ya que ∀x ∈ A : (x, x) ∈ / R. Más precisamente, (a, a) ∈ / R, (b, b) ∈ / R, (c, c) ∈ / R, (d, d) ∈ / R. No es simétrica ya que ∃ b, d ∈ A : (b, d) ∈ R pero (d, b) ∈ / R. No es asimétrica ya que ∃ a, c ∈ A : (a, c) ∈ R ∧ (c, a) ∈ R. No es transitiva ya que ∃ c, a, b ∈ A : (c, a) ∈ R ∧ (a, b) ∈ R pero (c, b) ∈ / R. No es antisimétrica ya que ∃ a, c ∈ A : (a, c) ∈ R ∧ (c, a) ∈ R pero a ̸= c. Ejemplo 3.9.2 Consideremos la siguiente relación R definida sobre N:  57 xRy ⇔ x + y es múltiplo de 4 o equivalentemente xRy ⇔ ∃k ∈ Z : x + y = 4k Analicemos que propiedades tiene R. ¿Es reflexiva?. Deberı́amos ver que ∀x ∈ N : xRx La relación no es reflexiva ya que ∃ 1 ∈ N : 1R1. ¿Es simétrica? Deberı́amos ver que ∀x, y ∈ N : xRy → yRx Sean x, y ∈ N cualesquiera. Supongo xRy ⇒ x + y es múltiplo de 4 (Def. de R) ⇒ ∃k ∈ Z : x + y = 4k (Def. de múltiplo) ⇒ ∃k ∈ Z : y + x = 4k (Conmutativa de la suma) ⇒ y + x es múltiplo de 4 (Def. de múltiplo) ⇒ yRx (Def. de R) Luego, R es simétrica. ¿Es antisimétrica? Deberı́amos ver que ∀x, y ∈ N : xRy ∧ yRx → x = y No es antisimétrica ya que existen 4, 8 ∈ N : 4R8 ∧ 8R4 pero 4 ̸= 8. ¿Es transitiva? Deberı́amos ver que ∀x, y, z ∈ N : xRy ∧ yRz → xRz No es transitiva, ya que existen 7, 1, 3 ∈ N : 7R1 ∧ 1R3 pero 7R3. Ejemplo 3.9.3 Si consideramos la relación R definida sobre N: xRy ⇔ 2x + 2y es múltiplo de 4 58 ¿Es reflexiva?. Deberı́amos ver que ∀x ∈ N : xRx Dado x ∈ N cualquiera, se verifica que 2x + 2x = 4x ⇒ 2x + 2x es múltiplo de 4 (Def. de múltiplo) ⇒ (x, x) ∈ R (Def. de R) Luego, R es reflexiva. ¿Es transitiva? Deberı́amos ver que ∀x, y, z ∈ N : xRy ∧ yRz → xRz Sean x, y, z ∈ N cualesquiera. Supongo xRy ∧ yRz ⇒ 2x + 2y es múltiplo de 4 ∧ 2y + 2z es múltiplo de 4 (Def. de R) ′ ′ ⇒ ∃k, k ∈ Z : 2x + 2y = 4k ∧ 2y + 2z = 4k (Def. de múltiplo) ′ ′ ⇒ ∃k, k ∈ Z : 2x = 4k − 2y ∧ 2z = 4k − 2y (Despejando) ′ ′ ⇒ ∃k, k ∈ Z : 2x + 2z = 4k + 4k − 4y (Sumando) ′ ′ ⇒ ∃k, k ∈ Z : 2x + 2z = 4(k + k − y) (Factor común) ′′ ′′ ⇒ ∃k ∈ Z : 2x + 2z = 4k (k = k + k ′ − y) ′′ ⇒ 2x + 2z es múltiplo de 4 (Def. de múltiplo) ⇒ xRz (Def. de R) Luego, R es transitiva. Capı́tulo 4 Relaciones de Orden y de Equivalencia 4.1. Relación de Orden Definición 4.1.1 Una relación binaria R sobre un conjunto A se dice que es de orden, si es reflexiva, antisimétrica y transitiva. Observación 4.1.2 Los “órdenes” más comunes son las relaciones ≤ y ≥ en Z y en R, definidas como: a ≤ b ⇔ b − a ∈ Z+ 0 y a ≥ b ⇔ a − b ∈ Z+ 0 en Z, y de manera análoga en R. Por esta razón cuando nos refiramos en general a una relación de orden en un conjunto A, usaremos los sı́mbolos ⪯ y ⪰. Ası́, en una relación de orden, para indicar que (x, y) ∈ R escribiremos x ⪯ y, que se lee “x precede a y” o “y sucede a x”. Una relación de orden sobre A verifica: Reflexividad: ∀x ∈ A : x ⪯ x Antisimetrı́a: ∀x, y ∈ A : x ⪯ y ∧ y ⪯ x ⇒ x = y Transitividad: ∀x, y, z ∈ A : x ⪯ y ∧ y ⪯ z ⇒ x ⪯ z Ejemplo 4.1.3 Dado el conjunto A = {1, 2, 3}, consideremos la relación de inclusión R definida sobre P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 59 60 Es decir, se tiene la relación XRY ⇔ X ⊆ Y R es una relación de orden ya que posee las propiedades reflexiva, antisimétrica y transitiva. Podemos ordenar al conjunto P(A): ∅ ⊆ {1} ⊆ {1, 2} ⊆ {1, 2, 3} ∅ ⊆ {2} ⊆ {1, 2} ⊆ {1, 2, 3} y ası́ sucesivamente. Observar que la relación de inclusión no sirve para ordenar todos los elementos de P(A), ya que por ejemplo {1} no está incluido en {2} y {2} no está incluido en {1}. Es por eso que decimos que el conjunto está parcialmente ordenado. 4.1.1. Relación divide Definición 4.1.4 Definimos la relación “ |” sobre el conjunto N de la siguiente manera: m|n ⇔ ∃k ∈ N : n = m · k Se lee “m divide a n” o “m es divisor de n” o “n es múltiplo de m” o “n es divisible por m”. Ejemplo 4.1.5 Consideremos la siguiente relación R definida sobre A = N : xRy ⇔ x|y ¿Será R una relación de orden sobre N? Deberı́amos ver que esta relación es reflexiva, antisimétrica y transitiva. ¿Es reflexiva? Deberı́amos ver que ∀x ∈ N : x|x. En efecto, sea x ∈ N se tiene: ∃1 ∈ N : x = x · 1 ⇒ x|x (Def. de relación | ) ¿Es antisimétrica? Deberı́amos ver que ∀x, y ∈ N : x|y ∧ y|x → x = y.  61 En efecto, sean x, y ∈ N cualesquiera. Suponemos x|y ∧ y|x ⇒ ∃k ∈ N : y = x · k ∧ ∃k ′ ∈ N : x = y · k ′ (Def. de relación | ) ⇒ ∃k, k ′ ∈ N : y = (y · k ′ ) · k (Sustitución) ′ ′ ⇒ ∃k, k ∈ N : y = y · (k · k) (Asociativa en N) ′ ′ ⇒ ∃k, k ∈ N : k · k = 1 (Neutro en N) ⇒ k = 1 ∧ k′ = 1 (Única forma que el producto de 1 en N) ⇒y =x·1 (Reemplazando en la segunda lı́nea de la prueba) ⇒x=y ¿Es transitiva? Deberı́amos ver que ∀x, y, z ∈ N : x|y ∧ y|z → x|z. En efecto, sean x, y, z ∈ N cualesquiera. Suponemos x|y ∧ y|z ⇒ ∃k ∈ N : y = x · k ∧ ∃k ′ ∈ N : z = y · k ′ (Def. de relación | ) ⇒ ∃k, k ′ ∈ N : z = (x · k) · k ′ (Sustitución) ′ ′ ⇒ ∃k, k ∈ N : z = x · (k · k) (Asociativa en N) ′′ ′′ ⇒ ∃k ∈ N : z = x · k (k = k ′ · k con k ′′ ∈ N) ′′ ⇒ x|z (Def. de relación | ) Luego, R es una relación de orden sobre N. En este caso ⪯ es la relación |. Observemos que puede haber pares de elementos que no sean comparables: por ejemplo (2, 3) ∈ / R y (3, 2) ∈ / R (ya que 2
|
3 y 3
|
2), en este caso se dice que 2 y 3 son elementos incomparables. 4.1.2. Representación Gráfica Observación 4.1.6 Las caracterı́sticas de los grafos dirigidos correspondientes a las rela- ciones de orden son las siguientes: Tiene un lazo en cada vértice (propiedad reflexiva). A lo sumo una arista dirigida entre dos vértices distintos (propiedad antisimétri- ca). Cada vez que hay una arista de un vértice a otro, y de éste a un tercero, la hay también del primero al tercero (propiedad transitiva). 62 Ejemplo 4.1.7 Sea A = {2, 3, 4, 12} y la relación R definida por xRy ⇔ x|y Por extensión R = {(2, 2), (2, 4), (2, 12), (3, 3), (3, 12),