MATEMATICAS DISCRETAS ( CONJUNTOS Y RELACIONES)

Matemática Discreta Conjuntos y Relaciones

Capítulo 4 - Pág. 1

UNIVERSIDAD TECNOLÓGICA NACIONAL FACULTAD REGIONAL CÓRDOBA

Carrera de Ingeniería en Sistemas de Información

CONJUNTOS Y RELACIONES

Los temas del presente capítulo, corresponden a la segunda y última parte de la Unidad Temática 3, asignatura de Matemática Discreta, Área de Programación, correspondiente al primer cuatrimestre del primer año de la carrera.

Período Lectivo 1996 - Prof. Ing. Juan C.Vázquez



_____________________________________________________________

Capítulo 4 CONJUNTOS Y RELACIONES

_____________________________________________________________ 4.0. Introducción. 4.1. Notación. 4.2. Subconjuntos. 4.3. Operaciones con conjuntos. 4.4. Relaciones.

_____________________________________________________________ Casi todos los objetos con que trabaja la matemática, son conjuntos u operadores que de alguna manera relacionan o modifican conjuntos, por lo cual puede afirmarse que el estudio de los mismos constituye el basamento de esta disciplina. Tempranamente ya, desde la escuela primaria (mi hijo, que actualmente cursa el sexto grado de la escuela, interviene en mis conversaciones sobre conjuntos para "discutirme" algún tema), hemos tenido contacto con el concepto de conjuntos, su conformación y las operaciones que sobre ellos podemos efectuar. Tal vez por esto, las ideas matemáticas sobre conjuntos nos resultan tan familiares e intuitivas, al punto de asumirlas en muchos casos como triviales. Sin embargo, siendo el cimiento de la llamada matemática moderna merece nuestra más esmerada atención, siendo por supuesto la exposición presentada en este capítulo y a nuestros fines, una "cuidada" revisión de los temas ya estudiados en anteriores etapas. Términos como conjuntos y elementos, son considerados en el contexto de la teoría de conjuntos como primitivos, en el sentido que no pueden ser definidos estrictamente sin caer en circularidades, sino más bien, descriptos en forma intuitiva.

Diremos pues que, "un conjunto, es cualquier colección bien definida de objetos", los cuales reciben el nombre de miembros o elementos del conjunto.

La expresión "bien definida" es fundamental en la definición intuitiva de conjunto, ya que podrá decirse que un conjunto está definido, si dado cualquier objeto x, puede determinarse la pertenencia del mismo o no, al conjunto. Además, hay que señalar que la palabra "objetos", se refiere en este contexto no sólo a objetos materiales, sino también a objetos abstractos o entes, que es "de lo que la matemática se alimenta".



_____________________________________________________________

Tema 4.0 INTRODUCCIÓN

_____________________________________________________________ 4.0.1. Breve reseña histórica. 4.0.2. Comentario a la definición intuitiva. 4.0.3. Objetivos. 4.0.4. Conocimientos previos.

_____________________________________________________________ 4.0.1. Breve reseña histórica. Si bien las clases ya eran conocidas como entes abstractos desde la antigüedad, fue George Boole (del cual ya hablamos en el capítulo anterior), quien desarrolló el álgebra de clases, a mediados del siglo XIX. Luego de él, otros muchos continuaron puliendo la idea de una lógica aritmetizada, extrayendo nuevas conclusiones, ampliando los conceptos y sus relaciones, y en definitiva, desarrollando en poco tiempo lo que durante más de dos mil años se mantuvo en un profundo letargo . Se atribuye al matemático ruso1 Georg Cantor (1845-1918), la sistematización de la teoría de conjuntos como tal, con las ideas publicadas en seis memorias, entre 1878 y 1884 en los Anales Matemáticos alemanes. Además, este científico con sus estudios sobre el concepto de infinito y de los llamados ordenes de infinitud, llevaron a reconsiderar aspectos centrales como continuidad, límites, densidad, etc., de fundamental importancia en toda la matemática y en particular en el análisis matemático moderno2. Cantor, murió en 1918 internado en un manicomio, loco y torturado por las críticas despiadadas que de sus estudios le infirieron sus contemporáneos, en particular, su ex-profesor Leopold Kronecker (1823-1891) quien al parecer lo combatió intensamente. 4.0.2. Comentario a la definición intuitiva. En el concepto de conjunto presentado, hicimos incapié en la expresión "bien definida" y en el sentido del vocablo "objeto" utilizado. Analicemos un poco más estos aspectos. Por ejemplo, las letras vocales a, e, i, o, u del alfabeto español, conforman un conjunto, ya que dada cualquier letra x, podemos decidir inequívocamente si es miembro o no del conjunto aludido. Sin embargo, si nos referimos a las letras del alfabeto a, b, ..., z, estrictamente hablando no

1 En muchos libros se nombra a Cantor como matemático alemán. Según el Ing. A.R.López, persona de mi absoluta confianza en cuanto a la seriedad con que encara los temas de estudio, Georg Cantor nació en San Petesburgo (hoy Leningrado) por lo cual lo ubicaremos como matemático de nacionalidad rusa, aunque su actividad profesional fue desarrollada casi íntegramente en Alemania. (Nota extraída de Matemática Moderna I, A.R.Lopez, Stella, 1971, página 17) 2 Véase El Romance de los Números, G.Masini, C. Internazionale del Libro, 1980, páginas 155 a 160, para un comentario sobre la obra de Cantor y su influencia en la matemática actual.



conforman un conjunto, ya que debe especificarse del alfabeto de qué lengua estamos hablando, debido al hecho que letras como la ñ (eñe), por ejemplo, pertenecen al alfabeto español y no al inglés, la ç (c con cedilla) pertenece al alfabeto francés y no al japonés, etcétera; en definitiva, no conforman un conjunto porque la colección no está bien definida. Otro punto importante en la definición intuitiva de conjuntos, es la idea de colección de objetos. Cuando hablamos de colección, aún en el lenguaje cotidiano, no hacemos referencia a un orden específico en el cual deban encontrarse los objetos coleccionados ni a si tenemos repeticiones de los mismos ya que, si bien no es lo mismo tener dos canicas azules que cuatrocientas canicas azules, en el concepto abstracto de colección sólo nos interesará si tenemos o no canicas de color azul. 4.0.3. Objetivos. Por otra parte, la teoría de conjuntos desde el punto de vista de la lógica matemática (teoría de clases), estudia las propiedades de la agrupación de objetos de cualquier tipo, lo que permite extender sus conclusiones a los más variados campos del saber. En matemática, interesarán principalmente conjuntos de entes abstractos (objetos matemáticos como números, vectores, espacios, funciones, etc.) y en informática, agregaremos a los anteriores en particular, los conjuntos de símbolos que representen letras, lenguajes, instrucciones, estados de una máquina, etc., lo que nos permitirá utilizar el poderoso formalismo matemático en estos temas y teorizar sobre la información y la computación con rigor científico. Repasaremos en lo que sigue, distintos conceptos sobre los conjuntos y las operaciones que se pueden realizar con ellos, ideas ya conocidas desde la enseñanza preuniversitaria, poniendo especial énfasis en su conexión con la lógica matemática y presentando la mayoría de los temas, como conclusiones o aplicaciones derivadas de ella. Además, recordaremos los importantes conceptos de relación y función, que utilizaremos ampliamente en los más variados estudios. 4.0.4. Conocimientos previos. Por lo antedicho, es prerequisito para el estudio de los temas a desarrollar en lo que sigue, estar familiarizado con los conceptos de la lógica matemática del capítulo anterior y haber ejercitado los mismos, lo que asegurará la fluidez en su manejo.



_____________________________________________________________

Tema 4.1 NOTACIÓN

_____________________________________________________________ 4.1.1. Pertenencia. 4.1.2. Determinación de un conjunto. 4.1.3. Conjuntos especiales. 4.1.4. Igualdad de conjuntos.

_____________________________________________________________ 4.1.1. Pertenencia. Un conjunto puede tener un número finito de elementos (como el conjunto de las letras vocales del alfabeto español indicado en la introducción), o un número infinito de elementos (como el conjunto formado por las concatenaciones o yuxtaposiciones de longitud arbitraria, de los elementos del anterior conjunto finito aludido). Como con las clases (tema 3.4), denotaremos en general con letras mayúsculas A, B, C, ..., a los conjuntos y con letras minúsculas a, b, c, ..., a los elementos de los mismos, y escribiremos:

a ∈ A para denotar la proposición "el objeto a es miembro del conjunto A", y lo leeremos "el elemento a pertenece al conjunto A". De forma similar, escribiremos la negación de la anterior proposición (~(a ∈ A)), como:

a ∉ A denotando que "el objeto a no es miembro del conjunto A", y lo leeremos "el elemento a no pertenece al conjunto A". 4.1.2. Determinación de un conjunto. Si el conjunto está formado por un número finito de elementos, puede determinarse o definirse inequívocamente al mismo, nombrando todos los elementos que lo componen. Esto suele hacerse, colocando primero el nombre del conjunto, luego un sígno de igualdad y a continuación todos los elementos que lo conforman, encerrados entre llaves e individualizados separándolos con coma o con punto y coma. Por ejemplo:

V = {a, e, i, o, u}



(que se lee "conjunto V formado por los elementos a, e, i, o, u"), describe claramente el conjunto V de las letras vocales hispanas. En este caso, se dice que el conjunto está determinado o definido por extensión o por enumeración. Asumiendo el contexto de las letras del alfabeto español, pueden escribirse por ejemplo, las siguientes proposiciones:

a ∈ V b ∉ V e ∈ V n ∉ V o ∈ V k ∉ V

que resultan verdaderas en virtud de la anterior definición del conjunto V. Otras veces, y en particular cuando tratamos con conjuntos de una cantidad infinita de elementos, la enumeración de miembros no aparece como una notación adecuada3, y se conviene definir entonces al conjunto, con una propiedad o característica que es común a todos los elementos del conjunto, y sólo a ellos. Por ejemplo:

V = {x / x es una vocal del alfabeto español} (que se lee "el conjunto V está formado por los elementos x tales que x es una vocal del alfabeto español), también define al conjunto de las letras vocales españolas sin lugar a dudas. Se dice en este caso, que el conjunto está determinado o definido por comprensión o por propiedad. En términos lógicos, esto se expresará como una función proposicional cuantificada:

V = {∀ x: P(x)} (el conjunto V está formado por todo x que verifique P), o resumidamente:

V = {x/ P(x)}

(el conjunto V está formado por todo x, tal que P(x) es verdadera), siendo P(x) la función proposicional x es una vocal española. Cabe reiterar que, ni en la noción de conjunto, ni en las dos formas en las que puede definirse un determinado conjunto, se hace referencia al orden o a la repetición de elementos. Esto no es un descuido sino, la esencia misma de la idea de conjunto como colección de objetos. Así:

A = (a, e, i, i, i, i, o, u} B = {i, i, e, a, a, o, u, i}

representan al mismo conjunto V definido anteriormente. A veces, abusando de la intuición y de las analogías, suele también definirse un conjunto infinito de elementos por extensión, indicando con puntos suspensivos que existen más elementos que los efectivamente indicados como en:

3 Un conjunto finito como el de "todos los habitantes de la ciudad de Córdoba, Argentina, que son abonados al servicio telefónico por cable", puede definirse por extensión, como lo demuestra la existencia de una guía telefónica; sin embargo, aunque finito, en otros contextos como el de esta nota, resulta claramente más conveniente una definición por propiedad.



V* = {a, aa, aaa, aaaa, aaaaa, ... }4

pero de ser posible, no caeremos en tales arrebatos en este texto.

Ejemplo: Determine por extensión y comprensión el conjunto de las provincias cuya-nas de la República Argentina.

Solución: C = {Mendoza, San Juan, San Luis} (por extensión) C = {x/ x es una provincia argentina de Cuyo} (por comprensión)♦

En el primer caso, enumeramos o enlistamos todos los elementos que componen el conjunto; en el segundo, determinamos el conjunto diciendo que formarán parte de él, sólo aquellos objetos que satisfagan una cierta propiedad. 4.1.3. Conjuntos especiales. Al igual que en clases, se extiende el concepto de conjunto definiendo el conjunto vacío (denotado por ∅ ), como aquel que no contiene elemento alguno y considerando como conjunto (y nombrándolo como conjunto unitario), a aquel que posea un sólo elemento5. Además, al hablar de conjuntos, normalmente se supone un determinado universo de discurso al cual pertenecen naturalmente todos los objetos a los que se hace referencia en el estudio. En los ejemplos anteriores, está implícito en el término vocales que estamos hablando de letras y no de frutas cítricas o de extraterrestres. Denotaremos con "U", al conjunto universal del cual son miembros todos los elementos de los conjuntos bajo estudio6. Por su importancia en matemáticas, y por que los utilizaremos para ejemplificar variados conceptos, daremos una notación especial a los siguientes conjuntos:

N = {x/ x es un número natural} Z = {x/ x es un número entero} Q = {x/ x es un número racional} R = {x/ x es un número real} N0 = {x/ x es un número natural o x es el número cero} Z+ = {x/ x es un número entero positivo}

y supondremos conocido desde la escuela, qué se entiende por natural, entero, etcétera.

Ejemplo: Exprese en símbolos el conjunto de los números naturales pares mayores a diez y menores a cien.

4 La notación V* para el conjunto de las combinaciones de símbolos, provienen de la operación llamada estrella de Kleene, la cual en realidad define la cadena vacía λ como parte del conjunto. (Referencia de Teoría de la Computación, J.G.Brookshear, Addison-Wesley, página 60) 5 Se hacen estas consideraciones aquí, ya que los conceptos de conjunto vacío y conjunto unitario, no se corresponden con la noción de conjunto presentada. Aún así, serán tratados como conjuntos. 6 Tal vez un nombre más apropiado sería conjunto referencial, pero utilizaremos el de universal para no crear confunsión con la bibliografía de consulta sugerida. (Nota debida a la Prof. L.Constable)



Solución: La definición de paridad de números naturales, dice que un número natural a es par, si existe algún natural x tal que a pueda escribirse como 2.x. Así:

P = {a/ a∈ N ∧ ∃ (x∈ N)/ a=2x ∧ a>10 ∧ a<100}♦

Aquí, hemos impuesto una propiedad que los números a deberán cumplir, para que sean considerados miembros del conjunto P en cuestión.

Ejemplo: Defina por comprensión, el conjunto vacío (sin elementos). Solución: Por el concepto de conjunto vacío, cualquier propiedad que un objeto x nunca

pueda satisfacer, nos servirá para definirlo por comprensión. Tomaremos la más sencilla: ∅ = {x/ x ≠ x}♦

También podríamos haber dado otras expresiones para el conjunto vacío, como por ejemplo, el conjunto de todos los hombres que son inmortales, el conjunto de todas las proposiciones lógicas que son verdaderas y falsas al mismo tiempo, etc., o sea, propiedades que contradicen la escencia de los objetos a los que se les atribuye. 4.1.4. Igualdad de conjuntos. Como ya se indicó, la repetición de elementos y el orden de presentación de los mismos en la definición de un conjunto en particular, no tienen efectos sobre la determinación efectiva del mismo. Teniendo esto en cuenta:

Definición: Dados dos conjuntos A y B, se dice que son iguales, (y lo denotamos por A=B), sii están formados por exactamente los mismos elementos.

En símbolos:

A = B ↔ ∀ x: x∈ A → x∈ B ∧ ∀ y: y∈ B → y∈ A

Se suele llamar también a la anterior definición, Principio de extensión7.

Ejemplo: Dado el conjunto A={1, 2, 3}, defina otros tres iguales al mismo. Solución: B = {2, 3, 1, 1} C = {x/ x∈ N ∧ x < 4} D = {x/ (x=1) ∨ (x=2) ∨ (x=3)}♦

7 Véase Matemáticas para Computación, S.Lipschutz, McGraw-Hill, 1992, página 132, donde se encuentra tal denominación. Además, el autor presenta el Principio de Abstracción diciendo: "dado cualquier conjunto U y cualquier propiedad P, hay un conjunto A tal, que los elementos de A son exactamente aquellos miembros de U que tienen la propiedad P". Creo que estos principios concuerdan con nuestra noción de determinación por extensión y por comprensión.



Aquí, se han utilizado los conocidos conectivos lógicos (en C y D), para conformar la proposición que caracteriza a los elementos del conjunto y se han separado con paréntesis "innecesarios" las funciones proposicionales de pertenencia, para destacarlas como tal. Estrictamente hablando, cuando decimos que dos conjuntos son iguales, en realidad nos estamos refiriendo a dos representaciones o caracterizaciones del mismo conjunto; establecemos una relación entre dos nombres de una misma entidad.

_____________________________________________________________ EJERCICIOS 4.1

4.1.1. Diga si las siguientes expresiones definen algún conjunto. En caso afirmativo, defina el

conjunto en símbolos y diga si es finito o infinito; en caso negativo, indique porqué no lo hacen y ejemplifique.

a) Los hombres altos. b) Los actuales habitantes de la Luna. c) Los algoritmos de exactamente cuatro instrucciones. d) Las proposiciones lógicas de la lógica tradicional. e) Las estrellas brillantes del cielo austral.

4.1.2. Sea U={1,2,3,4,5,6,7,8,9,10}, el conjunto universal de referencia y sean A ={1,2} y

B={2,4,6,8,10}. Indique la verdad o falsedad de las siguientes proposiciones:

a) 1 ∈ A f) 1∈ A ∨ 1∈ B b) 9 ∈ A g) 4∈ A ∧ 4∈ U c) 9 ∈ B h) 3∈ A → 8∈ U d) 9 ∉ B i) 3∉ A → 8∈ U e) 2 ∉ A j) 4∈ A ∨ 5∉ U

4.1.3. Defina por comprensión los conjuntos A y B del anterior ejercicio. 4.1.4. Indique cuáles de los siguientes conjuntos son iguales:

A = {x/ (x∈ N) ∧ (x es primo) ∧ (x<10)} B = {x/ (x∈ Z) ∧ (x<8)} C = {1, 2, 3, 4, 5, 6, 7} D = {1, 7, 7, 3, 1} E = {2, 3, 4, 5, 6, 1, 7}

4.1.5. Defina por comprensión y extensión los siguientes conjuntos:

a) Los naturales pares menores que diez. b) Los cuadrados menores que diez, de los primeros nueve naturales. c) Los números enteros negativos mayores que menos cuatro. d) Los temas del capítulo de lógica matemática de este texto. e) El conjunto de todas las letras "m" de esta página.

4.1.6. Diga cuándo dos conjuntos son distintos y estudie todos los casos posibles.



_____________________________________________________________

Tema 4.2 SUBCONJUNTOS

_____________________________________________________________ 4.2.1. Inclusión. 4.2.2. Cardinalidad de un conjunto. 4.2.3. Propiedades de la inclusión. 4.2.4. Familias de conjuntos.

_____________________________________________________________ Utilizaremos en lo que sigue, los diagramas de Venn ya presentados en el punto (3.4.4), con la misma significación y modo de construcción indicados allí, pero aplicados al concepto de conjunto. 4.2.1. Inclusión.

Definición: Dados dos conjuntos A y B, diremos que A está incluido en B (y lo denotaremos A⊆ B ó B⊇ A), si todo elemento de A es también elemento de B.

En símbolos:

A ⊆ B ↔ ∀ x: x∈ A → x∈ B

Según la variada bibliografía existente sobre el tema, las siguientes expresiones son consideradas equivalentes: • A está incluido en B. • A está contenido en B. • A es un subconjunto de B. • B incluye a A. • B contiene a A. • B es un superconjunto de A.

U

B

A.a.b

.c

Fig. 4.1: Diagrama de Venn de la inclusión A ⊆ B.



Ejemplo: Sean A y B, los conjuntos de la figura 4.1. Defina los conjuntos por exten-sión y establezca la relación de inclusión entre ellos.

Solución: a) La definición por extensión de los conjuntos es:

A = {a, b} B = {a, b, c} b) Ya que a∈ A, b∈ A y a∈ B, b∈ B, por definición de inclusión:

A ⊆ B

Sin embargo, como c∈ B y c∉ A, no puede decirse que B esté incluido en A.♦ El símbolo "⊆ " utilizado para representar la inclusión, recuerda el uso del símbolo menor o igual (≤) utilizado usualmente como relación entre números, y en cierta forma, indica que si A es un subconjunto de B, tiene menor o igual cantidad de elementos.

Definición: Dados dos conjuntos A y B, diremos que A está estrictamente incluido en B (y lo denotaremos A⊂ B ó B⊃ A), si todo elemento de A es también elemento de B, pero existe al menos un elemento en B que no es elemento de A.

En símbolos:

A ⊂ B ↔ (∀ x: x∈ A → x∈ B) ∧ (∃ y/ y∈ B ∧ y∉ A)

Si un conjunto A está estrictamente incluido en un conjunto B, se dice que el primero es un subconjunto propio del segundo. Por otra parte, la inclusión amplia engloba al concepto de inclusión estricta, ya que si A ⊆ B, puede suceder que A ⊂ B o que A = B. En el anterior ejemplo, A resulta ser un subconjunto propio de B. Nuevamente, el símbolo "⊂ " utilizado para representar la inclusión estricta, recuerda el uso del símbolo menor (<) utilizado entre números, y en cierta forma, indica que si A es un subconjunto propio de B, tiene menor cantidad de elementos. 4.2.2. Cardinalidad de un conjunto. Si llamamos conjunto finito a aquel que posee un número finito de elementos (esto es, n elementos con n∈ N), expresamos que:

Definición: Dado un conjunto finito A, llamaremos cardinalidad de A, (y lo denotaremos con A), al número n de elementos que pertenecen a él.

En símbolos: A = n



Por convención, se asigna el número cero como cardinalidad del conjunto vacío, si bien el cero no es un número natural, y el conjunto vacío no es en rigor, finito.

∅ = 0 También nos referiremos a la cardinalidad de un conjunto A, como el número cardinal de A. Ejemplo: Sean A={1,2,3} y B={a,b}. Entonces:

A = 3 B = 2♦ 4.2.3. Propiedades de la inclusión. Así, pueden ahora demostrarse algunas propiedades de la inclusión (con carácter de teoremas), y algunas relaciones entre las cardinalidades de conjuntos. 1) PROPIEDAD REFLEXIVA: Todo conjunto es parte de sí mismo. Hipótesis: Sea A, un conjunto cualquiera. Tesis: A ⊆ A Demostración: Por definición de inclusión:

A ⊆ A ↔ ∀ x: x∈ A → x∈ A

implicación que es verdadera para cualquier elemento de A.♦ 2) PROPIEDAD TRANSITIVA: Si un conjunto es subconjunto de otro y éste subconjunto de un

tercero, entonces el primero es subconjunto del tercero. Hipótesis: Sean A, B y C, tres conjuntos tales que A⊆ B y B⊆ C. Tesis: A ⊆ C Demostración: Sea x un elemento cualquiera de A. Entonces se tiene

simultáneamente: x∈ A → x∈ B, por hipótesis A⊆ B y la definición de inclusión, y (i) x∈ B → x∈ C, por hipótesis B⊆ C y la definición de inclusión. (ii) y por la ley del silogismo hipotético de la lógica, de (i) e (ii) se obtiene: x∈ A → x∈ C, que por definición de inclusión demuestra la tesis.♦ 3) PROPIEDAD ANTISIMÉTRICA: Si un conjunto es subconjunto de otro y éste subconjunto del

primero, entonces los conjuntos son iguales. Hipótesis: Sean A y B, dos conjuntos tales que A⊆ B y B⊆ A. Tesis: A = B Demostración: Por definición de igualdad de conjuntos:

A = B ↔ ∀ x: x∈ A → x∈ B ∧ ∀ y: y∈ B → y∈ A,



pero por definición de inclusión, esto puede escribirse:

A = B ↔ (A ⊆ B) ∧ (B ⊆ A), lo cual, al ser las premisas verdaderas, demuestra trivialmente la tesis.♦ 4) VACÍO SIEMPRE PRESENTE: El conjunto vacío está incluído en cualquier conjunto. Hipótesis: Sea A cualquier conjunto. Tesis: ∅ ⊆ A Demostración: Por definición de inclusión, la tesis puede escribirse como:

∀ x: x∈∅ → x∈ A lo cual es verdadero, ya que un antecedente falso (como x∈∅ ) siempre hace verdadero el condicional, con lo cual queda demostrada la tesis.♦ 5) UNICIDAD DEL VACÍO: El conjunto vacío es único. Hipótesis: Sea ∅ el conjunto vacío. Tesis: ∅ es único. Demostración: Supongamos que existe otro conjunto vacío ∅ '; entoces por la

propiedad (4) debe cumplirse:

(∅ ⊆ ∅ ') ∧ (∅ ' ⊆ ∅ ) lo que por la propiedad antisimétrica significa que ∅ = ∅ '.♦ 6) Si un conjunto finito. está incluído en otro, también finito, entonces la cardinalidad del primero es menor o igual a la del segundo. Hipótesis: Sean A y B dos conjuntos finitos tales que A ⊆ B. Tesis: A ≤ B Demostración: Supongamos que A= n y que B= m, o sea que el conjunto A tiene

exactamente n elementos y el B, exactamente m elementos. Por definición de inclusión, se tiene por hipótesis que:

∀ x: x∈ A → x∈ B lo que dice que, siempre que un elemento esté en A, el mismo debe pertenecer a B para

que la implicación sea verdadera, por lo cual, B contiene al menos tantos elementos como A, o sea que n es por lo menos igual a m. (i)

Además, la misma definición permite que existan elementos de B que no pertenezcan al conjunto A, con lo cual la implicación de antecedente falso y conclusión verdadera, resultará también verdadera. Si éste fuera el caso, B tendría entonces además de todos los elementos de A, algunos más, por lo cual m resultaría mayor que n. (ii)

De (i) e (ii), queda demostrada la tesis.♦ Algunas otras propiedades respecto de la inclusión de conjuntos, serán enunciadas luego y su demostración será dejada como ejercicio.



4.2.4. Familias de conjuntos. Existen algunos conjuntos que tienen como elementos a otros conjuntos, y se les denomina usualmente, conjunto de conjuntos, clase de conjuntos o familia de conjuntos; más aún, un conjunto puede contener como miembros, otros conjuntos y algunos elementos que no son conjuntos. Ejemplo: Sea A = {{a}, b} un conjunto. Entonces puede escribirse:

{a} ∈ A b ∈ A {b} ⊆ A {{a}} ⊆ A Sin embargo, a como elemento, no pertenece al conjunto A y el conjunto {a} no está incluído en A sino que es un elemento del mismo; en símbolos:

a ∉ A {a} ⊄ A♦ Un familia de conjuntos cuya aplicación es importante, es el denominado conjunto potencia de un conjunto A, denotado por P(A), la cual se define como aquella que tiene por elementos a todos los posibles subconjuntos de A. En símbolos:

P(A) = {X/ X⊆ A} Así, el problema de determinar P(A), o sea conocer la pertenencia o no de un conjunto X al conjunto potencia de A, se reduce al problema de establecer si X está efectivamente incluído en A. Por las propiedades que enunciamos sobre la inclusión de conjuntos y de la definición de conjunto potencia, se desprende fácilmente que el conjunto vacío pertenece a P(A) y que el mismo conjunto A, pertenece a su conjunto potencia. Ejemplo: Sea A={a,b,c}. Determine su conjunto potencia. Solución: En el siguiente diagrama de Venn, se representan las distintas asociaciones que se pueden formar con los elementos de A:

.a

.b

.cA

U quedando entonces el conjunto potencia definido por:

P(A) = {∅ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} ♦



Se puede demostrar (aunque no lo haremos aquí8) que: si A es un conjunto finito, en-tonces su conjunto potencia P(A) tendrá 2A elementos.

_____________________________________________________________ EJERCICIOS 4.2

4.2.1. Sean U={a,b,c,d,e,f,g,h,i}, A={a,c,e,g,i} y B={b,d,f,h}. Confeccione el diagrama de Venn

suponiendo que U es el conjunto universal, y determine la validez de las siguientes proposiciones, justificando su respuesta:

a) a ∈ A f) a ⊆ A b) {a} ∈ A g) {a} ⊆ A c) B ⊆ A h) c ∉ A → B ∈ U d) B ∈ U i) {a,g,c,i,e} ⊆ A e) B ⊆ U j) {a,g,c,i,e} ⊂ A

4.2.2. Demuestre las propiedades reflexiva, simétrica y transitiva de la igualdad de conjuntos.

Esto es, verificar respectivamente que se cumplen:

a) A = A b) A = B ↔ B = A c) (A=B ∧ B=C) → A=C 4.2.3. Dado el conjunto A={x / x∈ N ∧ x2 < 16}, indique si son verdaderas:

a) {0, 1, 2, 3} ⊆ A f) 0 ∉ A b) ∅ ⊆ A g) {0} ⊆ A c) 4 ∈ A h) {1,2,3} ⊆ A d) {4} ∈ A i) {1,2,3} ⊂ A e) {4} ⊂ A j) 2 ∈ A

4.2.4. Determine el conjunto potencia de A={1,2} y la cardinalidad del mismo. 4.2.5. Si A={b, i, t}, indique la verdad o falsedad de:

a) A ∈ P(A) f) {{t},{i}} ⊆ P(A) b) A ⊂ P(A) g) {{t},{i}} ⊂ P(A) c) {t,i} ∈ P(A) h) {t,i} ∉ P(A) d) {t,b} ⊆ P(A) i) {∅ } ⊆ P(A) e) {{t},{i}} ∈ P(A) j) ∅ ∈ P(A)

4.2.6. Indique todos los subconjuntos que se pueden formar con las letras de la palabra

"autómata", la cardinalidad de cada uno y cuáles de ellos son subconjuntos propios de {a, u, t, o, m}.

8 Puede encontrarse una demostración en Teoría de la Computación, J.G.Brookshear, Addison-Wesley, páginas 4-6, donde el autor procede por inducción matemática.



_____________________________________________________________

Tema 4.3 OPERACIONES CON CONJUNTOS

_____________________________________________________________ 4.3.1. Complementación. 4.3.2. Intersección. 4.3.3. Unión. 4.3.4. Producto cartesiano. 4.3.5. Propiedades de las operaciones con conjuntos. 4.3.6. Conjuntos finitos.

_____________________________________________________________ Tanto la igualdad de conjuntos como la inclusión, han sido definidas básicamente sobre la noción de pertenencia de elementos a conjuntos; de la relación de pertenencia, vimos que se puede afirmar que es verdadera (a∈ A) o que es falsa (a∉ A). Por esto, y con la misma argumentación utilizada para los conectivos lógicos (tema 3.2), pueden definirse cuatro operadores unitarios y dieciséis binarios, que accionen sobre conjuntos, para obtener otros conjuntos (o lo que es lo mismo, que operen sobre proposiciones lógicas del tipo "a pertenece al conjunto A"). Al igual que en esa oportunidad, sólo nos interesarán algunas operaciones de todas las posiblemente definibles, siendo las demás sólo combinaciones de ellas. A continuación, se definirán tres operaciones y se estudiarán sus propiedades, correspondientes a la aplicación de los conectivos no, y, o, de la lógica, a las proposiciones categóricas que definen conjuntos. Además, introduciremos el concepto de par ordenado y basado en él, el de producto cartesiano de dos conjuntos. 4.3.1. Complementación. Hemos destacado ya el hecho que, cuando hablamos de elementos de un determinado conjunto A, estamos presuponiendo la existencia de un universo de discurso, el conjunto universal U, al cual pertenecen naturalmente todos los objetos de los conjuntos bajo estudio (y posiblemente otros que no pertenecen a ninguno de ellos), compartiendo alguna característica común.

Definición: Dado un conjunto A, y el conjunto universal U, llamaremos complemento de A al conjunto ~A, (que leeremos complemento de A o A complemento), formado por todos los elementos del conjunto universal, que no pertenecen al conjunto A.

En símbolos:

~A = {x/ x∈ U ∧ x∉ A}

El símbolo "~" utilizado para denotar el complemento, refuerza la idea de negación de la proposición que establece la pertenencia al conjunto (~(x∈ A) o no es el caso que el elemento x



pertenezca al conjunto A); en la bibliografía, suele también utilizarse el símbolo " " como sombrero del conjunto a complementar o las notaciones A' o Ac.

U

A

~A

Fig. 4.2: Complemento de un conjunto A (área sombreada).

También se define en forma análoga, el complemento de un conjunto A respecto de otro cualquiera B, llamado a veces diferencia entre los conjuntos A y B.

Definición: Dados dos conjuntos A y B, llamaremos complemento de A respecto de B, al conjunto B-A, (que leeremos B menos A, o complemento de A con respecto a B), formado por todos los elementos de B que no pertenecen al conjunto A.

En símbolos:

B - A = {x/ x∈ B ∧ x∉ A}

Suele también denotarse al complemento de A respecto de B como AB

c o AB'.

A B

B-AU

Fig. 4.3: Complemento de un conjunto A respecto de otro B (área sombreada).

Ejemplo: Dados A={a, b, c} y B={c, x}, determine B - A y A - B. Solución: Del diagrama de Venn y de la definición de complementación respecto de un

conjunto, se sigue que:

B - A = {x} (todo elemento de B que no esté en A) A - B = {a, b} (todo elemento de A que no esté en B)



A B.a.b

U

.c .x

A B

U

.x.c.a

.b

A-B B-A ♦

Esta operación, "hereda" de la negación la propiedad de involución y otras, que serán luego enunciadas formalmente y se presentarán como ejercicio para su demostración. Además, el anterior ejemplo demuestra por contraejemplo que la complementación de conjuntos no es conmutativa. 4.3.2. Intersección. La idea intuitiva de intersección en el lenguaje ordinario, se refiere a puntos comunes de dos líneas que se cortan, a la esquina de dos calles, etcétera. Esta misma idea es la que el término expresa, referida a conjuntos. Formalmente:

Definición: Dados dos conjuntos A y B, llamaremos intersección de A y B, al conjunto A∩B, (que leeremos A intersección B), formado por todos los elementos comunes de A y de B.

En símbolos:

A∩B = {x/ x∈ A ∧ x∈ B}

La operación así definida, resulta ser binaria ya que aplicándola a dos conjuntos se obtiene otro conjunto.

U

A B

AnB

Fig. 4.4: Intersección de dos conjuntos (área sombreada). El símbolo "∩" utilizado para denotar la intersección de conjuntos, tiene la forma suavizada del símbolo de conjunción de la lógica matemática, y efectivamente este conectivo tiene acción decisiva en la definición precedente.

Ejemplo: Dados A={1, 2, 3, 4, 6, 7, 8, 9} y B={5, 6, 7, 8, 10}, determine A∩B.



Solución: Estando los conjuntos definidos por extensión pueden verse claramente los elementos comunes a ambos conjuntos, por lo cual A∩B={6, 7, 8}♦

La operación de intersección heredará de la conjunción, las propiedades que la misma cumple en el ámbito de las proposiciones lógicas.

Ejemplo: Demuestre que la intersección de conjuntos cumple la propiedad asociativa. Solución: Hipótesis: Sean A, B y C tres conjuntos cualesquiera. Tesis: (A∩B)∩C = A∩(B∩C) Demostración: La demostración surge naturalmente de la definición de intersec- ción y de

las propiedades de la conjunción de proposiciones lógicas. Definamos las siguientes proposiciones lógicas:

p: x∈ A q: x∈ B r: x∈ C entonces:

(A∩B)∩C = {x/ (x∈ A ∧ x∈ B) ∧ x∈ C} por definición de intersección.

= {x/ (p ∧ q) ∧ r} reemplazando las proposiciones. = {x/ p ∧ (q ∧ r)} propiedad asociativa de conjunción. = {x/ x∈ A ∧ (x∈ B ∧ x∈ C)} reemplazando las proposiciones. = A∩(B∩C) por definición de intersección.♦

Que la intersección goce de la propiedad asociativa, nos permite generalizar la operación de intersección a n conjuntos Ai, en cuyo caso se suele escribir:

A A ... A = A1 2 n ii=1

n

∩ ∩ ∩ I

Dados dos conjuntos A y B, pueden darse con respecto a la intersección, cuatro situa-ciones diferentes a saber:

U

U

U

A

A

AB

B

B

(a) Conjuntos disjuntos (b)

(c) Conjuntos iguales

AB

U(d) A C B

C

Fig. 4.5: Posibilidades en la intersección de dos conjuntos.



a) Si los conjuntos no tienen elementos en común, se dice que los mismos son disjuntos y su intersección es, por lo tanto, el conjunto vacío:

A∩B = ∅

b) Si los conjuntos tienen algunos elementos en común y otros no, entonces su inter-sección

estará compuesta por los elementos ubicados en el área común a ambos en la fig. 4.5(b). A∩B = C

c) Si los conjuntos son iguales, entonces la intersección es el mismo conjunto A.

A∩B = A

d) Si se trata del caso que (como en la fig. 4.5(d)), uno de los conjuntos es subconjunto propio

del otro, entonces la intersección de ellos es el subconjunto (el de menor cardinalidad). A∩B = A

En realidad, si hablamos de inclusión y no de inclusión estricta, los casos (c) y (d) se funden en uno sólo. 4.3.3. Unión. La operación de unión de conjuntos, aplica la idea de disyunción lógica al ámbito de los conjuntos, en el sentido que relaciona las proposiciones de pertenencia de elementos utilizando el conectivo "o". Formalmente:

Definición: Dados dos conjuntos cualesquiera A y B, llamaremos unión de A y B al conjunto A∪ B, (que leeremos A unión B), formado por todos los elementos de A y todos los de B.

En símbolos:

A∪ B = {x/ x∈ A ∨ x∈ B}

La operación así definida, resulta ser también binaria ya que genera un nuevo conjunto a partir de dos conjuntos dados.

U

A B

AUB

Fig. 4.6: Unión de dos conjuntos (área sombreada).



El símbolo "∪ " utilizado para denotar la unión de conjuntos, tiene la forma suavizada del símbolo "∨ " de la disyunción lógica y, como puede verse claramente en la definición presentada de la operación, es coherente la semejanza.

Ejemplo: Dados A={1, 2, 3, 4, 6, 7, 8, 9} y B={5, 6, 7, 8, 10}, determine A∪ B. Solución: La respuesta es sencilla; para determinar el conjunto unión de A y B, sólo tenemos

que listar primero los elementos de A y a continuación los de B. Así:

A∪ B = {1, 2, 3, 4, 6, 7, 8, 9, 5, 6, 7, 8, 10} Pero por definición de conjunto, suelen no listarse los elementos repetidos (ya que no

aportan nada a la determinación del conjunto), con lo cual obtenemos:

A∪ B = {1, 2, 3, 4, 6, 7, 8, 9, 5, 10}♦ La operación de unión heredará naturalmente de la disyunción, las propiedades que la misma cumple para el cálculo proposicional.

Ejemplo: Demuestre que la unión de conjuntos cumple la propiedad asociativa. Solución: Hipótesis: Sean A, B y C tres conjuntos cualesquiera. Tesis: (A∪ B)∪ C = A∪ (B∪ C) Demostración: La demostración surge de la definición de uniión y de las propie-dades de

la disyunción de proposiciones lógicas. Definamos como antes, las siguientes proposiciones lógicas:

p: x∈ A q: x∈ B r: x∈ C

entonces:

(A∪ B)∪ C = {x/ (x∈ A ∨ x∈ B) ∨ x∈ C} por definición de unión.

= {x/ (p ∨ q) ∨ r} reemplazando las proposiciones. = {x/ p ∨ (q ∨ r)} propiedad asociativa de disyunción. = {x/ x∈ A ∨ (x∈ B ∨ x∈ C)} reemplazando las proposiciones. = A∪ (B∪ C) por definición de unión.♦

La propiedad asociativa de la unión, nos permite generalizarla a una familia de n conjuntos Ai, en cuyo caso se suele escribir:

A A ... A = A1 2 n ii=1

n

∪ ∪ ∪ U Con las operaciones ya establecidas de intersección y unión de conjuntos, definiremos el importante concepto de partición de un conjunto como sigue:



Definición: Dados los conjuntos no vacíos A1, A2, ..., An, y el conjunto B, llamaremos partición de B (o recubrimiento de B, o conjunto cociente de B), a la familia L={A1, A2, ..., An} si se verifica que los conjuntos Ai son disjuntos de a pares y si para cada elemento x de B, x pertenece a algún Ai con i=1, 2, ...,n.

En símbolos:

La familia L={A1, A2, ..., An} es una partición de B sii:

a) Ai ∩ Aj = ∅ , con i ≠ j e i, j=1, 2, ..., n b) B = A1∪ A2∪ ...∪ An

La anterior definición puede ser extendida a una familia infinita de conjuntos, extendiendo la unión generalizada a infinitos conjuntos Ai.

A

AA

A

B

U

1

23

4

Fig. 4.7: Una partición L = {A1, A2, A3, A4} del conjunto B.

Ejemplo: Diga si L = {{1, 2}, {2, 3}, {4}}, es una partición de A = {1, 2, 3, 4}. Solución: Hay que verificar si las condiciones de la definición se cumplen: a) {1, 2} ∩ {2, 3} = {2} , no son disjuntos! {1, 2} ∩ {4} = ∅ {2, 3} ∩ {4} = ∅ b) {1, 2} ∪ {2, 3} ∪ {4} = {1, 2, 3, 4} Como puede verse, la intersección de algunos conjuntos de L no es vacía, por lo cual L

resulta no ser una partición de A.♦ Para no ser pesimistas en nuestros ejemplos, veamos ahora que realmente se pueden establecer particiones en algún conjunto.

Ejemplo: Determine dos particiones distintas de V = {a, e, i, o, u}. Solución: a) L1 = {{a, e, i, o}, {u}} es una partición de V, ya que se cumple: {a, e, i, o} ∩ {u} = ∅



y V = {a, e, i, o} ∪ {u}. b) L2 = {{a, i}, {u,o}, {e}} es también una partición de V, pues se cumplen: {a, i} ∩ {u, o} = ∅ {a, i} ∩ {e} = ∅ {u, o} ∩ {e} = ∅ y V = {a, i} ∪ {u, o} ∪ {e}.♦

4.3.4. Producto cartesiano. En la idea de conjunto, el orden de los elementos que al mismo pertenecen, no tiene ninguna significación en cuanto a su determinación. Así, hemos expresado que:

{a, b} = {b, a} ya que ambos miembros de la igualdad son en realidad, el mismo conjunto. Definiremos ahora, un ente matemático en el cual el orden en que aparecen sus componentes sí tiene importancia:

Definición: Dados dos objetos a y b, llamaremos par ordenado, y lo denotaremos con (a, b), al arreglo ordenado de los mismos, y diremos que a es la primer componente y que b es la segunda componente del par ordenado.

Una definición más estricta9 de par ordenado, lo define como la familia de conjuntos:

(a, b) = {{a}, {a, b}}

permitiendo aplicar las operaciones de conjuntos y las propiedades de las mismas, a este nuevo concepto. De la definición precedente se desprende que, en general, (a, b) ≠ (b, a), a menos que se verifique a = b y, basado en este hecho, se dice que un par ordenado es igual a otro, si y sólo si, sus componentes correspondientes son iguales. En símbolos:

(a, b) = (c, d) ↔ a = c ∧ b = d.

Utilizando este ente, definiremos una nueva operación de conjuntos que recibe el nombre de producto cartesiano en honor al matemático y filósofo francés René Descartes (1596-1650), quien es considerado el fundador de la geometría analítica10.

9 Una definición tal se encuentra en Algebra I, A.O.Rojo, El Ateneo, 1972, página 53 y una explicación más detallada del concepto puede verse en Calculus, M.Spivak, Reverté, 1970, páginas 67 y 68. 10 Algunos autores opinan que la historia fue en este caso injusta con otro francés, el matemático Piere Fermat (1601-1665), quien fue el primero en explisitar la representación gráfica de los pares ordenados.



Definición: Dados dos conjuntos no vacíos A y B, llamaremos conjunto producto de A y B o producto cartesiano de A y B, al conjunto A x B (que leeremos A por B) cuyos elementos son los pares ordenados que tienen como primer componente, un elemento de A y como segunda componente, un elemento de B.

En símbolos:

A x B = {(a, b) / a∈ A ∧ b∈ B}

En particular utilizaremos la notación A2 para referirnos al producto cartesiano de un conjunto por sí mismo, A x A.

Ejemplo: Determine el producto cartesiano de {1, 2, 3} y {a, b}, en ese orden. Solución: El producto de A = {1, 2, 3} y B = {a, b}, será por definición:

A x B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}♦ Si extendemos el concepto de par ordenado a n objetos diciendo que, una n-tupla es un arreglo ordenado de objetos (a1, a2, ..., an), podemos extender el producto cartesiano a una familia de n conjuntos no vacíos, expresando:

A1 x A2 x ... x An = {(a1, a2, ..., an) / a1∈ A1 ∧ a2∈ A2 ∧ ... ∧ an∈ An} lo que también suele escribirse como:

A A ... A = A1 2 n i

i=1

n

× × × C

y como es usual, denotaremos con An al producto cartesiano de A por sí mismo n veces. Por definición de par ordenado, evidentemente el producto cartesiano no es conmutativo; además, pueden demostrarse varias propiedades como por ejemplo, que es distributivo a derecha o a izquierda respecto de la unión. 4.3.5. Propiedades de las operaciones con conjuntos. De las infinitas igualdades de conjuntos que podemos construir utilizando las operaciones que hemos definido, como en el caso de los conectivos lógicos y por su utilidad en matemáticas, se listarán a continuación, sólo algunas de ellas (y algunas otras en la ejercitación del presente capítulo). La demostración de estas propiedades (tratadas así como teoremas), puede ser efectuada algebráicamente apelando a las propiedades que satisfacen los conectivos lógicos y gráficamente, construyendo y analizando los diagramas de Venn de las distintas situaciones a las que ellas hacen referencia. Sean A, B y C tres conjuntos cualesquiera y sean ∼ , ∩ y ∪ los símbolos de las operaciones de complementación, intersección y unión de conjuntos respectivamente. Entonces, se cumplen las siguientes propiedades:



1. Involución: ~(~A) = A 2. Idempotencia: a) De la intersección: A ∩ A = A b) De la unión: A ∪ A = A 3. Conmutatividad: a) De la intersección: A ∩ B = B ∩ A b) De la unión: A ∪ B = B ∪ A 4. Asociatividad: a) De la intersección: A ∩ B ∩ C = A ∩ (B ∩ C) = (A ∩ B) ∩ C b) De la unión: A ∪ B ∪ C = A ∪ (B ∪ C) = (A ∪ B) ∪ C 5. Distributividad: a) De la intersección respecto de la unión: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) b) De la unión respecto de la intersección: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 6. Leyes de DeMorgan: a) ~(A ∪ B) = ~A ∩ ~B b) ~(A ∩ B) = ~A ∪ ~B

Fig. 4.8: Algunas propiedades de las operaciones de conjuntos.

Nótese la similitud entre la anterior tabla de propiedades y la tabla de leyes lógicas de la figura 3.10. Con los comentarios que hemos ido haciendo sobre la relación entre los operadores de conjuntos y los operadores lógicos involucrados en sus definiciones, claramente esta semejanza no es una casualidad, sino que emana de la estructura del sistema formal construído. Estamos diciendo más o menos lo mismo, con otras palabras. Además, pueden establecerse otras relaciones útiles entre cualquier conjunto A y los conjuntos universal U y vacío ∅ , como las que siguen:

i) A ∪ ~A = U v) A ∩ ~A = ∅ ii) A ∪ ∅ = A vi) A ∩ ∅ = ∅ iii) A ∪ U = U vii) A ∩ U = A iv) ~U = ∅ viii) ~∅ = U

Por último, estableceremos el siguiente principio, el cual es también válido para la lógica proposicional (con los arreglos de notación correspondientes):



Principio de Dualidad: Si T es un teorema del álgebra de conjuntos, entonces el dual de T, denotado por T*, construido reemplazando los símbolos U, ∅ , ∩ , ∪ de T por los símbolos ∅ , U, ∪ , ∩ , respectivamente, es también un teorema.

Ejemplo: Demostrar que A ∪ U = U, para cualquier conjunto A. Solución: Hipótesis: Sean A cualquier conjunto y U el conjunto universal. Tesis: A∪ U = U. Demostración: El teorema, enunciado como una proposición lógica, establece que si A⊆ U,

entonces A∪ U es igual a U. En símbolos:

(A⊆ U) → (A∪ U=U) (iii) Por definición de inclusión y de igualdad de conjuntos, podemos escribir:

∀ x: (x∈ A → x∈ U) → ((x∈ A ∨ x∈ U) → (x∈ U)) ∧ ((x∈ U) → (x∈ A ∨ x∈ U)) Si para abreviar, establecemos p:x∈ A y q:x∈ U (omitiendo la variable x por comodidad

pero sin perder de vista el cuantificador universal), reescribimos lo anterior como:

∀ x: (p→q) → ((p∨ q) → q) ∧ (q → (p ∨ q)) En esta expresión, la proposición q siempre es verdadera, por definición de conjunto

universal (toda x debe pertenecer a él), por lo cual: (p∨ V) → V ≡ V→V, es verdadero por el cálculo de proposiciones. V → (p∨ V) ≡ V→V, es verdadero por el cálculo de proposiciones. (V→V) ∧ (V→V), es verdadero por el cálculo de proposiciones. (p→q), es verdadero por la definición de universal (A⊆ U, cualquiera que sea A) entonces, queda la anterior expresión como:

∀ x: V → V que es una tautología, y siendo equivalente a (iii), queda demostrada la tesis.♦

Si aplicamos el principio de dualidad al anterior teorema, la expresión A∪ U=U se transforma en A∩∅ =∅ el cual también es un teorema del álgebra de conjuntos. (Nótese que todas las propiedades en las cuales intervienen los símbolos ∩ , ∪ , ∅ , U enunciadas anteriormente, bienen de "a pares") 4.3.6. Conjuntos finitos.



Como ya se indicó, se dice que un conjunto es finito si tiene exactamente n elementos con n∈ N, e infinito si lo conforman un número infinito de elementos. Son de especial interés para las ciencias informáticas el primer tipo de conjuntos mencionado, ya que los algoritmos son conjuntos finitos de instrucciones, la memoria de una computadora es un conjunto finito de celdas donde alojar símbolos, los lenguajes de programación son un conjunto finito de sentencias y reglas para manejarlas, etc.. Diremos que un conjunto es numerable (o contable) si se puede establecer una corres-pondencia uno a uno con los números naturales. Esto es, a cada elemento del conjunto lo podremos nombrar como primero, segundo, tercero, ..., o sea enumerarlos. En caso contrario, se dice que el conjunto es no numerable (o no contable o incontable). Claramente, por nuestra definición de conjunto finito, todo conjunto finito resulta ser numerable ya que teniendo n elementos, los podremos enumerar como primero, segunto, ..., i-ésimo, ..., n-ésimo.

Ejemplo: Sea A un conjunto finito de símbolos y sea además, A* (leído como A es-trella) el conjunto de todas las combinaciones finitas de elementos de A. Diga si A* es numerable y si es finito11.

Solución: Claramente, A* no es finito, ya que aunque finitas, las cadenas de símbolos

formadas por cualquier cantidad de elementos de A (con repeticiones) resultan ser infinitas. Sin embargo, A* es contable.

Para demostrar esto último, ordenaremos las cadenas formadas con símbolos de A, de la siguiente manera:

a) Primero se colocarán todas las posibles cadenas de un sólo símbolo, ordenados en forma alfabética (o si son numerales, según un orden ascendente de los valores que ellos representan). b) Luego, todas las cadenas formadas por dos símbolos de A, ordenados alfabé- ticamente entre ellas, y así sucesivamente. Ordenando de esta forma, y suponiendo A={a, b}, podremos escribir: Primera: a Segunda: b Tercera: aa Cuarta: ab Quinta: ba Sexta: bb Séptima: aaa

. . . . . .

con lo cual se ha conseguido una forma de enumerar el conjunto infinito A*.♦

11 Véase referencia (4) en la página seis del presente capítulo, un comentario sobre esta notación.



En el anterior ejemplo, el conjunto A puede no estar formado de números (como {a,b}) y en estos casos suelen denominarse alfabeto al conjunto A y palabras a los elementos del conjunto A* (o también cadenas, secuencias o el familiar vocablo del idioma inglés "strings"). Por otro lado, se definió ya la cardinalidad de un conjunto finito, como la cantidad de elementos (distintos por definición de conjunto) que el mismo posee. Resulta importante en muchos problemas, conocer la cantidad de elementos que contiene un conjunto, obtenido combinando otros mediante las operaciones de complementación, intersección, unión y producto cartesiano. Por esto, se enunciarán los siguientes teoremas, cuya demostración puede ser efectuada mediante un análisis de los respectivos diagramas de Venn y/o de las definiciones de los operadores.

a) TEOREMA: Dados dos conjuntos finitos A y B, la cardinalidad del complemento de A

respecto de B, es igual a la cardinalidad de A menos la cardinalidad de la intersección de los conjuntos.

En símbolos:

A - B = A - A ∩ B

b) TEOREMA: Dados dos conjuntos finitos A y B, la cardinalidad de la unión de ellos, es igual a la suma de las cardinalidades de cada uno de ellos menos la cardinalidad de la intersección de los mismos.

En símbolos:

A ∪ B = A + B - A ∩ B

c) TEOREMA: Dados dos conjuntos finitos A y B, la cardinalidad del producto cartesiano de A y B, es igual al producto de las cardinalidades de cada uno de ellos.

En símbolos:

A x B = A . B

El teorema (b), recibe usualmente el nombre de Principio de conteo o de Principio de Adición. A través de estos teoremas, pueden establecerse como corolarios, otros que permitan calcular la cardinalidad de cualquier combinación de operaciones de conjuntos, como por ejemplo:

d.1) COROLARIO: Del teorema (a), se sigue que:

A ∩ B = A - A - B

d.2) COROLARIO: Del principio de adición, se sigue que:

A ∩ B = A + B - A ∪ B d.3) COROLARIO: De los colorarios d.1 y d.2, se sigue inmediatamente que:



A - A - B = A + B - A ∪ B

y: A - B = A ∪ B - B

y muchos otros. Por último, la siguiente fórmula (un poco más complicada) enuncia el principio de adición aplicado a tres conjuntos A, B y C, cualesquiera:

A∪ B∪ C = A + B + C - A∩B - A∩C - B∩C + A∩B∩C

_____________________________________________________________ EJERCICIOS 4.3

4.3.1. Demostrar todas las propiedades de las operaciones con conjuntos de la figura 4.8. (Nota: recuerde que la distributividad debe demostrarse a derecha y a izquierda) 4.3.2. Sea A cualquier conjunto y U el conjunto universal. Demuestre que:

i) A ∪ ~A = U v) A ∩ ~A = ∅ ii) A ∪ ∅ = A vi) A ∩ ∅ = ∅ iii) A ∪ U = U vii) A ∩ U = A iv) ~U = ∅ viii) ~∅ = U

4.3.3. Sean los conjuntos U={0,1,2,3,4,5,6,7,8,9}, A={2,4,6,8}, B={1,2}, C={1,2,3,5,7}. a) Defina por comprensión los conjuntos A, B y C. (respecto de U) b) Determine utilizando diagramas de Venn y exprese por extensión:

1) A ∪ B 5) ~A ∩ C 9) A x B 2) A ∪ C 6) A ∩ ~C 10) B x A 3) A ∩ U 7) ~(A ∩ C) 11) ~A x B 4) (A ∪ B) ∩ C 8) B - C 12) (A ∩ C) ∩ ~B

c) Defina dos particiones de A, dos de B y dos de C. d) Determine el conjunto potencia de B. e) La familia de conjuntos L={A-B, C} ¿es una partición del conjunto U-{9}? Justifique su respuesta utilizando diagramas de Venn. 4.3.4. Siendo A, B y C, los conjuntos del ejercicio anterior, determine para los conjuntos

definidos en los puntos (b.1) a (b.12), sus cardinalidades. 4.3.5. Una encuesta editorial realizada en la U.T.N.-F.R.C., determinó en 1995 que12: 64 estudiantes leen la revista BYTE

12 Véase Estructuras de Matemáticas Discretas para la Computación, B.Kolman / R.C. Busby, 1984, Prentice-Hall, página 22, de donde fue extraído este ejercicio, para otros sobre el tema conteo.



94 estudiantes leen la revista COMPUMAGAZINE 58 estudiantes leen la revista PC-MAGAZINE 28 estudiantes leen las revistas BYTE y PC-MAGAZINE 26 estudiantes leen las revistas BYTE y COMPUMAGAZINE 22 estudiantes leen las revistas PC-MAGAZINE y COMPUMAGAZINE 14 estudiantes leen las tres revistas Siendo 260 la cantidad total de estudiantes encuestados, determine: a) ¿Cuántos de los estudiantes de la encuesta no leen ninguna de las revistas indicadas? b) ¿Cuántos de los estudiantes encuestados, leen sólo la revista Compumagazine? c) ¿Cuántos de los estudiantes encuestados, leen sólo la revista Byte? d) ¿Cuántos de los estudiantes encuestados, leen sólo la revista PC-Magazine? (Nota: Este tipo de problemas, recibe el nombre de problemas de conteo) (Sugerencia: Utilice el principio de adición para tres conjuntos) 4.3.6. Se define como diferencia simétrica de conjuntos (simbolizada por ∆ o por ⊕ ), a la

operación que aplicada a dos conjuntos A y B, genera el conjunto de todos los elementos que pertenecen a A y a B, pero no a ambos. Defina estrictamente la operación, dibuje su diagrama de Venn y demuestre que cumple la propiedad conmutativa.

4.3.7. Utilizando el diagrama de Venn construido en el ejercicio anterior, exprese la diferencia

simétrica como una combinación de operaciones de complemento relativo y uniones e intersecciones entre los conjuntos. (hay varias formas)

4.4.8. La diferencia simétrica de conjuntos, ¿es asociativa?. Justifique su respuesta. 4.3.9. Dados los conjuntos A={1,2} y B={a,b,c}, determine por extensión:

a) A x B e) A x A x A b) B x A f) A x A x B c) A x A g) A x B x A d) B x B h) B x B x B

4.3.10. Determine el conjunto potencia P(A), siendo A={a,b}, e indique cuáles de sus elementos

son subconjuntos propios de A. 4.3.11. Demuestre las propiedades de los números cardinales de conjuntos, indicadas en los

teoremas (a) y (b) del punto 4.3.6. (Utilice diagramas de Venn) 4.3.12. Sea A un conjunto finito y P(A) su conjunto potencia. ¿Es P(A) una partición del

conjunto A?. Explique. 4.3.13. Demuestre que el producto cartesiano es distributivo a derecha y a izquierda respecto de

la unión de conjuntos, pero que en general no es distributivo respecto de esta operación,o sea, que se verifican:



a) A x (B ∪ C) = (A x B) ∪ (A x C). b) (B ∪ C) x A = (B x A) ∪ (C x A).

pero que en general:

c) A x (B ∪ C) ≠ (B x A) ∪ (C x A). d) (B ∪ C) x A ≠ (A x B) ∪ (A x C).

4.3.14. Demuestre que al producto cartesiano es distributivo respecto de la intersección de

conjuntos, en el mismo sentido que el indicado en el ejercicio 4.3.13 para la unión. ¿Qué hecho hace que no se cumpla la distributividad completa entre estas operaciones?.

4.3.15. Sea A un conjunto finito {a1,a2, ..., an} y P(A) su conjunto potencia. Determine:

a) A ∪ P(A) d) P(A) A b) A ∩ P(A) e) {A} ∪ P(A) c) A P(A) f) {A} ∩ P(A)

4.3.16. Represente en diagramas de Venn, las situaciones indicadas en los distintos pun-tos del

ejercicio 4.3.15. 4.3.17. Tomando la definición de par ordenado (a,b) = {{a}, {a,b}}, demuestre que: a) Si K=((a,b) ∩ (c,d)) y K=0, entonces a≠c ∧ b≠d. b) Si K=((a,b) ∩ (c,d)) y K=1, entonces a=c. c) Si K=((a,b) ∩ (c,d)) y K=2, entonces a=c ∧ b=d. d) Si K=((a,b) ∪ (c,d)) y K=2, entonces a=c ∧ b=d. e) Si K=((a,b) ∪ (c,d)) y K=1, entonces a=c=b=d. 4.3.18. ¿Existe algún conjunto X que verifique X≤A para todo A?. Justifique. 4.3.19. ¿Existe algún conjunto X que verifique X≥A para todo A?. Justifique. 4.3.20. Dados los conjuntos A y B, determine: a) (A ∩ B) ∩ (A ∆ B) b) U ∆ ∅ c) P(A) ∩ B, siendo B⊂ A d) P(A) ∩ P(B), siendo B⊂ A



__________________________________________________________

Tema 4.4 Relaciones

__________________________________________________________

4.4.1. Definición. 4.4.2. Representación. 4.4.3. Relación inversa. 4.4.4. Clasificación de relaciones según sus propiedades. 4.4.5. Clases de equivalencia y particiones. 4.4.6. Concepto de función.

__________________________________________________________ El concepto de relación es fundamental en toda la matemática y su uso se extiende a muchas otras disciplinas, desde la programación de computadoras hasta la sociología, siendo una herramienta de inestimable valor al momento de efectuar estudios estadísticos, de estructura, etcétera. La idea de relación es sencilla y muy intuitiva, ya que coincide con el uso cotidiano del vocablo. Así, sabemos que existe una relación entre padres e hijos, entre los alumnos y sus notas en una planilla de calificación, entre los números naturales y sus cuadrados, etcétera. Si bien estas relaciones son todas muy diferentes, en general comparten ciertas propiedades que resultan difíciles de establecer claramente mediante el uso del lenguaje natural. Por esto, se formalizará el concepto como relacion entre conjuntos, prescindiendo del tipo de objetos que el conjunto posea (hombres, notas, alumnos, números naturales, etc.); de hecho, esto mismo hicimos con las proposiciones al estudiar las leyes lógicas y con los conjuntos al tratar sus operaciones. 4.4.1. Definición. Si bien las relaciones entre objetos pueden ser n-arias, trataremos aquí las relaciones binarias que establecen cierta correspondencia entre los objetos de sólo dos conjuntos, sin perder generalidad, pues el concepto podrá luego extenderse a más conjuntos.

Definición: Dados dos conjuntos no vacíos A y B, llamaremos relación binaria de A en B, a todo subconjunto R del producto cartesiano A x B.

En símbolos, R es una relación de A en B sii:

R ⊆ A x B

Si bien la relación binaria como concepto abstracto de correspondencia entre objetos, difiere del conjunto que la misma define, serán tratados en lo sucesivo como sinónimos. Además, usaremos simplemente el término relación toda vez que hagamos referencia a una relación binaria, salvo que se especifique lo contrario.



Si (a, b) ∈ R, se dice que "a está relacionado con b" por medio de R o que "b es la imagen de a" a través de R. En este sentido, las expresiones anteriores representan una proposición lógica, que de ser verdadera se denota aRb y en caso contrario aRb. Además, si la relación se establece entre elementos de un mismo conjunto A, diremos que R ⊆ AxA es "una relación en A" o "una relación sobre A", en vez de una relación de A en A.

Ejemplo: Sea C={1,2,3,4,5,6,7,8,9,10} el conjunto de notas posibles de los alumnos de Matemática Discreta y sea A={Juan, Pedro, Lucía} un conjunto de alumnos que rindieron esa asignatura. Entonces, la siguiente planilla de notas:

Notas de MAD

Alumnos Calificaciones Juan 8

Pedro 3 Lucía 7

establece una relación R de A en C {(Juan, 8), (Pedro, 3), (Lucía, 7)}, un subconjunto de

A x C.♦

Definición: Sea R una relación de A en B; entonces se denominan: • Alcance de la relación o conjunto de partida, al conjunto formado por todas las posibles

primeras componentes de los pares ordenados de la relación (o sea, al conjunto A). (R) = A

• Rango de la relación o conjunto de llegada, al conjunto formado por todas las posibles

segundas componentes de los pares ordenados de la relación (o sea, al conjunto B). (R) = B

• Dominio de la relación, al conjunto formado por todas las primeras componentes de los pares

ordenados que efectivamente pertenecen a la relación.

(R) = {x/ x∈ A ∧ (x, y) ∈ R para algún y∈ B} • Imagen de la relación o contradominio o codominio, al conjunto formado por todas las

segundas componentes de los pares ordenados que pertenecen efectivamente a la relación.

(R) = {y/ y∈ B ∧ (x, y) ∈ R para algún x∈ A}

4.4.2. Representación.



Existen muchas formas de definir y/o representar una relación entre conjuntos pero, cualquiera que sea, debe asegurar que la relación esté bien definida, esto es, claramente establecidos su alcance y rango, e inequívocamente determinados los pares ordenados que la conforman. Destacaremos las siguientes por su amplia utilización y facilidad de comprensión (en particular para conjuntos finitos):

a) Coloquialmente: La relación se define mediante expresiones del lenguaje cotidiano, que determinen sin ambigüedades el alcance, el rango y cuáles de los elementos del primero están relacionados con cuáles del segundo. Por ejemplo:

• Entre los hombres y mujeres de la ciudad de Córdoba, Argentina, se sabe que : - Juan Vvv es amigo de Carlos Ddd, - Leticia Ccc es amiga de Gabriela Aaa, y - Juan Vvv es amigo de Marcelo Mmm. • Sea Z el conjunto de los números enteros y x,y∈ Z. Decimos que "x" está relacionado con "y" si y sólo si x divide a y en Z. b) Por fórmulas: Se especifica un alcance y un rango claramente, y se indica una función

proposicional en dos variables (una perteneciente al alcance y otra al rango), la cual se transformará en proposición verdadera para valores (a, b) relacionados y en proposición falsa para valores (u, v) no relacionados. Por ejemplo:

R = {(x,y)/ x,y∈ N ∧ x > y}

c) Diagramas de Venn: Se dibujan según las normas ya estudiadas para la construcción de

estos diagramas, los conjuntos alcance y rango de la relación (con la posible omisión del recuadro correspondiente al conjunto universal), y mediante flechas, se muestran las relaciones entre elementos, siendo la primer componente de cada par ordenado de R el origen de una flecha y la segunda componente, la punta de la flecha. Así, si (a, b)∈ R existirá en la representación una flecha de a hacia b.

1. 2. 3.4.5.

6.

7.8.9.

10.

. Juan

. Pedro

. Lucía

C A

Si la relación se establece entre elementos de un mismo conjunto, este gráfico suele ser dibujado omitiendo el círculo que representa al conjunto en cuestión, y toma el nombre de grafo dirigido o digrafo. En este contexto, los puntos que representan los elementos del conjunto (o normalmente diminutos círculos etiquetados con el nombre del elemento), reciben el nombre de vértices o nodos y las flechas que los relacionan el nombre de arcos dirigidos o aristas con sentido.

Por ejemplo, sea C el conjunto de calificaciones posibles del ejemplo anterior; el siguiente digrafo, representa la relación sobre C, a es potencia entera de b.



.2

.3.4

.5

.6

.7

.8 .9

.10.1

d) Tablas: Es la representación utilizada en la planilla de calificaciones del ejemplo anterior. Se

confecciona una tabla de dos columnas, indicando en la cabecera de la misma la relación a representar y el nombre del alcance, en la primera columna y el del rango, en la segunda columna; luego se anotan para cada par (x, y) en R, el valor de x en la primer columna y el valor de y en la segunda columna de la una misma fila.

e) Matriz: Esto es, un arreglo rectangular de números (o tabla de doble entrada), en la cual se

etiqueta cada fila con los elementos del primer conjunto del producto cartesiano, y cada columna con los elementos del segundo conjunto. Así, en la intersección de la fila x con la columna y, se colocará cero si (x, y)∉ R, y uno, en el caso que (x, y)∈ R como se ejemplifica a a continuación:

R 1 2 3 4 5 6 7 8 9 10

Juan 0 0 0 0 0 0 0 1 0 0 Pedro 0 0 1 0 0 0 0 0 0 0 Lucía 0 0 0 0 0 0 1 0 0 0

También pueden utilizarse V o F en lugar de unos y ceros para indicar la pertenecia o no

del par ordenado a la relación. f) Gráfico cartesiano: Por último, la conocida representación en un sistema de coordenadas

cartesianas ortogonales, ubicando los elementos del alcance en el eje de abscisas (horizontal) y los del rango en el eje de ordenadas (vertical), y marcando un punto en la intersección de las rectas paralelas a los ejes que pasen por la abscisa a y la ordenada b, si el par (a, b) pertenece a R.

C

123456789

10

Juan Pedro Lucía ε

εy

x A

4.4.3. Relación inversa.



Siempre que una relación R esté definida, esto es, se conozcan su alcance, su rango, y todos los pares ordenados que la verifican, podrán intercambiarse las primeras y segun-das componentes de éstos, estableciéndose una nueva relación. Formalmente:

Definición: Dados dos conjuntos no vacíos A y B, llamaremos relación inversa de una relación R de A en B, y la denotaremos por R-1, al subconjunto de pares ordenados (b, a) del producto cartesiano BxA, tales que (a, b)∈ R.

En símbolos:

R-1 = { (b, a)/ (a,b)∈ R }

Ejemplo: Tomando la relación de los alumnos y sus calificaciones antes definida por tabla,

diremos que su relación inversa es:

R-1 = { ( 8,Juan), (3,Pedro), (7,Lucía) }♦ 4.4.4. Clasificación de relaciones según sus propiedades. Las relaciones pueden ser clasificadas según las propiedades que cumplen. Por su importancia en posteriores estudios y por la claridad que aportan al tema, destacaremos siempre que podamos, cómo influyen estas propiedades en las gráficas que las representan. A este fin, llamaremos diagonal de un producto cartesiano, al subconjunto formado por todos los pares ordenados que tienen iguales sus componentes primera y segunda; este nombre está inspirado en la ubicación que los mismos ocupan en una representación cartesiana del conjunto producto. Si la relación es sobre un conjunto, los elementos de la diagonal antes definida, se presentan en su digrafo como arcos que salen de y llegan a, un mismo nodo. Los llamaremos lazos.

Definición: Dado un conjunto A y una relación R sobre A, diremos que R es reflexiva si para cualquier elemento x de A, el par ordenado (x, x) es un elemento de R.

En símbolos, R⊆ A2 es reflexiva sii:

∀ x: x∈ A → (x, x) ∈ R

Si la relación está representada en un sistema de ejes coordenados, diremos que es reflexiva, si le pertenecen los puntos de la diagonal. En un digrafo, la reflexividad se observará como un lazo existente en cada nodo. Ejemplo: Dado el conjunto A={a,b} y la relación R de A en B definida por:

R = { (a,a), (a,b), (b,a), (b,b) }

la misma resulta reflexiva y algunas de sus representaciones son:



A

A

a b

ab

diagonal a

b

lazo

lazo

ε

εx

y

Fig. 4.9: Gráficas características de una relación reflexiva.♦ Ejemplo: Sea R = { (x,y)/ x,y∈ N ∧ y=x2 } una relación sobre los naturales.

Entonces, (1,1)∈ R pero (2,2)∉ R, por lo cual la relación no es reflexiva.♦ Si a la relación le pertenecen sólo algunos elementos de la diagonal y otros no, se la denomina no reflexiva y en el caso que ningún elemento de la diagonal pertenece a la relación, la misma recibe el nombre de irreflexiva o arreflexiva.

Definición: Dado un conjunto A y una relación R sobre A, diremos que R es simétrica si y sólo si, para cualquier par ordenado de R, el par obtenido permutando sus componentes, también pertenece a R.

En símbolos, R⊆ A2 es simétrica sii:

∀ (x,y∈ A) : (x, y)∈ R → (y, x) ∈ R

Gráficamente, los puntos que representan a los pares ordenados de una relación simétrica, se encuentran espejados respecto de la diagonal del primer y tercer cuadrante de un sistema de coordenadas. En los digrafos esto significa que, siempre que exista un arco desde un nodo a hacia un nodo b, también existirá uno de b hacia a.

Ejemplo: Dada sobre los números reales R la relación y=x+2, determine si es reflexi-va y si es simétrica.

Solución: a) Un elemento de la diagonal de R es el par ordenado (1,1). Probando la

relación dada con el mismo, se obtiene 1=2, proposición evidentemente falsa, por lo cual (1,1) no pertenece a la relación y la misma es al menos no reflexiva.

Además, por las propiedades de los números reales y sus operaciones, podemos escribir: y = x + 2 ↔ y - x = 2

lo que muestra que ningún par (x, x) con x∈ R, verificará la relación pues en tal caso se

llegaría a la contradicción 0=2. Así, la relación definida resulta ser en irreflexiva. b) Por otro lado, siendo (1,2) un elemento de la relación (verifica y=x+1), proba-remos la

relación con el par ordenado de componentes conmutadas (2,1). Operan-do con estos valores, obtenemos 1=3, la cual siendo falso nos dice que la relación no es simétrica.♦



Ejemplo: La relación representada en la figura 4.9, es simétrica ya que para todo par ordenado se verifica que si (x, y)∈ R, entonces (y, x) ∈ R.♦

Si R es una relación en la cual, existe algún (x, y)∈ R tal que (y, x)∉ R, la relación se dice que es no simétrica. Si además, para todo (x, y)∈ R se verifica que (y, x)∉ R, la denominaremos asimétrica. Es de especial interés, el caso de relaciones no simétricas que, sin embargo, contienen a la diagonal (pares de la forma (x,x)).

Definición: Dado un conjunto A y una relación R sobre A, diremos que R es antisimétrica si y sólo si, para cualquier par ordenado (x, y) de R, el par obtenido permutando sus componentes, o no pertenece a R o x = y.

En símbolos, R⊆ A2 es antisimétrica sii:

∀ (x,y∈ A) : (x, y)∈ R ∧ (y, x) ∈ R → x = y

El digrafo de una relación antisimétrica, tendrá un lazo en cada nodo y a lo sumo un arco dirigido entre dos nodos distintos. En un sistema de coordenadas cartesianas, los puntos de la diagonal pertenecerán a la relación, pero no se distinguirá simetría "espeja-da" respecto de la diagonal en los otros puntos.

Ejemplo: La relación sobre A={a,b,c} definida por {(a,a), (b,b), (c,c)} es trivialmen-te antisimétrica, ya que sólo posee elementos de la diagonal de AxA y ningún otro.

a b c ♦

Ejemplo: La relación representada en la figura 4.9, no es antisimétrica ya que si bien incluye

a la diagonal de {a,b} x {a,b}, se tiene que (a,b)∈ R y también que (b,a)∈ R. Obsérvese que su digrafo, tiene más de un arco dirigido entre a y b.♦

Definición: Dado un conjunto A y una relación R sobre A, diremos que R es transitiva, si y sólo si, para todo par de elementos (x,y), (y,z) de la relación, se verifica que (x,z) también pertenece a la relación.

En símbolos, R⊆ A2 es transitiva sii:

∀ (x,y,z∈ A) : ((x, y)∈ R ∧ (y, z) ∈ R) → (x,z)∈ R

El digrafo de una relación transitiva, tiene la siguiente propiedad: cada vez que exista un arco dirigido de x hacia y, y otro de y hacia z, existirá un arco dirigido de x a z.



x

y

z

Ejemplo: Dado un conjunto universal U, podemos pensar la inclusión (⊆ ) de conjuntos como una relación binaria de UxU, siendo los elementos de la misma, pares ordenados de conjuntos (A, B) sii A⊆ B. De esta manera, la inclusión entre conjuntos es una relación transitiva, ya que (por las propiedades ya vistas de esta operación), si A, B y C son subconjuntos de U tales que A⊆ B y B⊆ C, se cumple que A⊆ C.♦

La transitividad de una relación, la hace funcionar como una relación después de otra, en el sentido que, si xRy, yRz, xRz son verdaderas, podría pensarse en algún tipo de equivalencia entre, aplicar una relación R1 que verifique xR1y y seguidamente una R2 que verifique yR2z, y aplicar directamente R que verifica xRz. En un digrafo, estas serian dos formas distintas de llegar de un nodo x a un nodo z. Formalmente:

Definición: Dados tres conjuntos no vacíos A, B y C, y dos relaciones R1 de A en B y R2 de B en C, llamaremos composición de R1 y R2 (y la denotaremos por R2°R1), a la relación de A en C, resultante de aplicar primero R1 y luego R2. En símbolos:

R2°R1 = {(x,z) / (x,y)∈ R1 ∧ (y,z)∈ R2, para algún y∈ B}

En el sentido que una relación establece una proposición lógica de pertenencia de un par ordenado a un conjunto R, suele escribirse también la expresión aRb como b=R(a). Con esta notación, podemos escribir más intuitivamente R2°R1(a) = R2((R1(a)), lo que justifica el orden en que se presentan las relaciones originales, en la notación dada para la composición de relaciones.

Ejemplo: Sean A={-2,-1,0,1,2}, B={1,2,3,4,5}, C={0, 1, 2} y U={x/ x∈ R}. Si definimos las relaciones: R1={(x,y)/ x∈ A ∧ y∈ B ∧ y=x2} y R2={(y,z)/ y∈ B ∧ z∈ C ∧ z=y/2}, determine R2°R1. Solución: En fórmulas, se tiene que:

R2°R1={(x,z)/ x∈ A ∧ z∈ C ∧ ∃ y∈ B/ z = y/2 ∧ y=x2} y su diagrama de Venn es:



.-2

.-1

. 0

. 1

. 2

A B .1.2.3.4.5

C.0.1.2

R R1 2

R2 R

1

1

donde se han dibujado separados los conjuntos A, B y C, para hacer más legible el gráfico (en realidad tienen elementos en común por lo que habría que dibujarlos intersecándose). Identificando los pares verifican a R (líneas punteadas), obtene-mos :

R2°R1={(-2,2), (2,2)}.♦

Debe notarse en el gráfico del ejemplo anterior, que sólo pertenecen a la relación compuesta R2°R1, aquellos pares ordenados (x, z) con x∈ A y z∈ C, que están conectados mediante la dos arcos, uno directamente desde al conjunto A hacia el C, y otro formado por la concatenación de arcos dirigidos de A a B y de B a C. Así, si bien existe un arco de -1∈ A a 1∈ B, el par (-1,1)∉ R2°R1 ya que no existe un arco de 1∈ B hacia algún elemento de C. Por último, daremos un nombre especial a las relaciones que cumplen simultáneamente algunas de las propiedades definidas hasta el momento.

Definición: Una relación sobre un conjunto A, se llama relación de orden parcial, si y sólo si, es reflexiva, antisimétrica y transitiva.

En símbolos, R⊆ AxA es de orden parcial si: i) ∀ x∈ A : (x,x)∈ R ii) ∀ x,y∈ A : (x,y)∈ R ∧ (y,x)∈ R → y=x iii) ∀ x,y,z∈ A : (x,y)∈ R ∧ (y,z)∈ R →(x,z)∈ R

Definición: Una relación sobre un conjunto A, se llama relación de equivalencia, si y sólo si es reflexiva, simétrica y transitiva.

En símbolos, R⊆ AxA es una relación de equivalencia si: i) ∀ x∈ A : (x,x)∈ R ii) ∀ x,y∈ A : (x,y)∈ R → (y,x)∈ R iii) ∀ x,y,z∈ A : (x,y)∈ R ∧ (y,z)∈ R →(x,z)∈ R

La primera, reviste gran importancia ya que permite definir un criterio de ordenación para los elementos de un conjunto a través de R. La segunda, dice que aquellos elementos relacionados por medio de una relación de equivalencia, son de alguna forma semejantes o equivalentes bajo R.

Ejemplo: Tomemos nuevamente nuestra conocida inclusión de conjuntos, como una relación sobre algún U2; entonces y según las anteriores definiciones, la inclusión es una relación de orden parcial ya que por el álgebra de conjuntos estudiada, se cumplen:



a) A⊆ A, para cualquier conjunto A. b) A⊆ B ∧ B⊆ A → A=B, para cualquier par de conjuntos A y B. c) A⊆ B ∧ B⊆ C → A⊆ C, para cualquier terna de conjuntos A, B y C. Sin embargo, al no ser la inclusión conmutativa en general (de A⊆ B no puede deducirse

que B⊆ A, a menos que A=B), la misma no es una relación simétrica, y por lo tanto, no constituye una relación de equivalencia.♦

Ejemplo: Estudiemos la siguiente relación sobre los números reales:

R = {(x,y)/ x,y∈ R ∧ y=x} Por las propiedades de los números reales, se verifican: a) ∀ x∈ R : x = x. b) ∀ x,y∈ R : x=y → y=x. c) ∀ x,y,z∈ R : x=y ∧ y=z → x=z. por lo tanto, R (la igualdad de números reales) resulta ser una relación de equiva-lencia.♦

4.4.5. Clases de equivalencia y particiones. Dada una relación de equivalencia R sobre un conjunto, se dice de las componentes de los pares ordenados que pertenecen a ella, que son equivalentes a través de R. Nos interesará en particular, determinar todos los elementos del conjunto que son equivalentes a uno dado y sus propiedades. Definimos para ello lo siguiente:

Definición: Sea R una relación de equivalencia sobre el conjunto no vacío A y sea "a" un elemento de A; se llama clase de equivalencia del elemento "a", (y se la denota por [a]), al subconjunto de todos los elementos de A equivalentes con el elemento "a" a través de R.

En símbolos, siendo R ⊆ A2:

[a] = {x∈ A/ (x,a)∈ R}

Deben recalcarse dos consecuencias importantes de esta definición: a) La clase de equivalencia de un elemento a∈ A, es siempre un subconjunto de A. b) [a] resulta ser siempre no vacía, ya que por ser R una relación de equivalencia, por lo menos a∈ [a] (propiedad reflexiva de la relación). Se establecerá ahora un importante resultado, que conecta los conceptos de clases de equivalencia recién definido y el de partición de un conjunto definido la sección 4.3.3.

TEOREMA: El conjunto de todas las clases de equivalencia de elementos de un conjunto A, a través de una relación de equivalencia R⊆ AxA, es una partición de A.



Hipótesis: Sea A un conjunto no vacío y R una relación de equivalencia en A; sean además a,b∈ A.

Tesis: L={[a]/ a∈ A} es una partición de A. Demostración: Para demostrar que la familia L es una partición de A, se deberá

probar primero que A puede escribirse como la unión de todas sus clases de equivalencia a través de R, y luego, que las distintas clases de equivalencia de elementos de A son disjuntas por pares.

a) Por definición de clase de equivalencia, sabemos que toda clase [x] es un

subconjunto de A, por lo cual no existen elementos en [x] que no estén en A; además se tiene que para cada clase de equivalencia [u] de elementos de A, por lo menos u∈ [u]. Así, la unión de todas las clases de equivalencia de elementos de A a través de R, resulta igual a A.

b) Supongamos primero que (a,b)∈ R; entonces tenemos que: 1) [a] = {x∈ A/ (x,a)∈ R}, por definición de clase de equivalencia. 2) (x,a)∈ R ∧ (a,b)∈ R → (x,b)∈ R, por la transitividad de R. 3) [b] = {x∈ A/ xRb}, por definición de clase de equivalencia. lo que dice que si (a,b)∈ R entonces [a]⊆ [b] (i), ya que para cualquier elemento

x∈ [a], resulta de (1), (2) y (3), que x∈ [b]. Además, la simetría de R asegura que si (a,b)∈ R debe cumplirse que (b,a)∈

R, por lo cual, con un razonamiento similar al anterior, se prueba que [b]⊆ [a] (ii). De (i) e (ii), se sigue que, si (a,b)∈ R entonces [a]=[b] (iii).

Supóngase ahora que [a] y [b] son dos elementos cualesquiera de la familia L con [a]≠[b] y que existe algún u∈ A tal que u∈ [a]∩[b]. Luego:

(u,a)∈ [a] y (u,b)∈ [b], por definición de clases y de intersección.

pero por (iii), esto implica que [u]=[a] ∧ [u]=[b] lo cual es un absurdo ya que

se supuso que [a]≠[b]. Entonces, no existe un tal u∈ A, por lo cual [a]∩[b]=∅ lo que concluye la demostración de la tesis.♦

Ejemplo: Sea A={a,b,c} y la relación sobre AxA definida por:

R={(a,a), (a,b), (b,a), (b,b), (c,c)} Se pide: a) Indique la clasificación de la relación según sus propiedades. b) ¿Es R una relación de equivalencia? c) De ser cierto, muestre las clases de equivalencia de A a través de R.



a

b

c

Solución: a) 1) (a,a)∈ R ∧ (b,b)∈ R ∧ (c,c)∈ R, por lo que la relación es reflexiva. 2) (a,b)∈ R ∧ (b,a)∈ R, y (1), indican que la relación es simétrica. 3) (a,b)∈ R ∧ (b,a)∈ R → (a,a)∈ R, y siendo los únicos pares fuera de la diagonal, la relación resulta transitiva. b) De a)1), a)2) y a)3), la relación R es de equivalencia en A. c) [a] = {a, b} [b] = {a, b} [c] = {c}♦

Como [a]=[b], resulta que la familia L={[a],[c]} es una partición de A, donde se ha omitido la clase de equivalencia [b] por la definición de conjunto que obvia los elementos repetidos para su determinación. 4.4.6. Concepto de función. Por último, introduciremos el concepto de función, como un tipo muy importante de relación y de la más amplia utilización en ciencias.

Definición: Sean A y B conjuntos no vacíos y f una relación de A en B. Entonces "f" recibe el nombre de función, si y sólo si, el alcance coincide con el dominio de la relación y además, dados dos pares ordenados cualesquiera de f con sus primeras componentes iguales, resultan iguales sus segundas componentes.

En símbolos, f ⊆ AxB es una función sii: a) ∀ a∈ A: ∃ b∈ B/ (a,b)∈ f (o (f) = A ∧ (f) = A) b) ∀ (a∈ A), (b,c∈ B): ((a,b)∈ f ∧ (a,c)∈ f) → b=c

La primera condición establece que todo elemento del conjunto de partida, es una primer componente de algún par ordenado de la relación; la segunda, indica que para cada elemento del conjunto de partida, existe un sólo elemento en el conjunto de llegada. Gráficamente, en un sistema de coordenadas cartesianos, la segunda condición estable-ce que una recta vertical (perpendicular al eje de abscisas), tendrá a lo sumo un punto en común con la gráfica de la función. En un digrafo, de todo nodo deberá partir uno y sólo un arco (condición (a)) y sólo podrá llegar al mismo un arco (condición (b)).



Utilizaremos normalmente letras minúsculas f, g, h, etc., para denotar aquellas relaciones que sean funciones. Se estila además, denotar que f es una función de A en B de la siguiente forma:

f: A → B y si (a,b)∈ f, se representa al elemento b∈ B como f(a):

b=f(a)

El elemento a recibe también, el nombre de argumento de la función, el b el de imagen de a bajo f o el de valor de f en a, y la función misma es a veces nombrada como aplicación (f aplica A en B)13, o como transformación de A en B, haciendo referencia a las propiedades gráficas involucradas. En general, si una función se establece mediante fórmula, como en y=f(x), x recibe el nombre de variable independiente y en un gráfico cartesiano se anotan sus valores sobre el eje de abscisas; por otro lado, y recibe el nombre de variable dependiente y sus valores se ubican sobre el eje de ordenadas. La gráfica de la función queda así formada por los puntos (x,f(x)) del plano cartesiano. De igual forma que las relaciones, el concepto de función puede ser extendido a más de dos conjuntos, obteniendo así funciones de varias variables.

Ejemplo: Sean A={1,2,3,4} y B={a,b,c} el alcance y rango de la relación:

f = {(1,a), (2,b), (3,a), (4,a)} Entonces f es función, ya que cada elemento de A tiene una única imagen en B:

f(1) = a f(2) = b f(3) = a f(4) = a resultando, el alcance de f igual al dominio de f y la imagen de A a través de f igual a {a,b}

⊂ B.♦ Si en el ejemplo anterior, quitamos de la relación cualquiera de los pares ordenados que la componen, la misma deja de ser función ya que el alcance no sería igual al dominio; por otro lado, si agregamos cualquier otro par ordenado distinto de los enlistados, con su primer componente perteneciente al conjunto A, también dejaría de ser función, ya que algún elemento de A tendría por f más de una imagen. Todos los conceptos que estudiamos (relación inversa, composición de relaciones, clasificaciones de las relaciones, etc.) son también aplicables a funciones ya que las mismas son en primera instancia, relaciones. En particular, interesan en muchas aplica-ciones prácticas, dos propiedades que una función puede cumplir, a saber:

13 Algunos autores omiten en la definición de función, la condición de coincidencia entre alcance y dominio. Así, distinguen función de aplicación asignando a ésta última dicha condición.



Definición: Sea f:A→B una función de A en B. Entonces "f" recibe el nombre de inyectiva si y sólo si, a elementos distintos del dominio corresponden elementos distintos de la imagen.

En símbolos, f:A→B es inyectiva sii:

∀ a,b∈ A: a ≠ b → f(a) ≠ f(b)

También se dice que f es una función uno a uno de A en B. En el ejemplo de función citado precedentemente, claramente f resulta ser no inyectiva, ya que f(1)=a y f(3)=a. Por otro lado:

Definición: Sea f:A→B una función de A en B. Entonces "f" recibe el nombre de suprayectiva si y sólo si, todo elemento de B es imagen de algún elemento de A. En símbolos, f:A→B es suprayectiva sii:

∀ b∈ B: ∃ a∈ A/ b=f(a)

También se dice que f es sobreyectiva o suryectiva si cumple la propiedad enunciada en la anterior definición, la que suele escribirse f(A)=B, abusando de la notación establecida (pero intuitivamente clara). La definición de suryectividad establece en pocas palabras, que el rango de la relación debe coincidir con la imagen de la misma.

Ejemplo: Sean como antes A={1,2,3,4} y B={a,b,c}, el alcance y rango de la rela-ción: f = {(1,a), (2,b), (3,a), (4,a)}

la misma no es suprayectiva, ya que existe un elemento c∈ B que no es imagen por f de

ningún elemento del dominio. Sin embargo, si cambiamos el tercer par orde-nado, como en:

g = {(1,a), (2,b), (3,c), (4,a)} resulta ahora g, ser una función suprayectiva. Además, puede verse que por el primer y último par, g no es inyectiva ya que aplica el

elemento 1∈ A y el 4∈ A en la misma imagen a∈ B.♦ Si se recuerda el razonamiento seguido para demostrar que el conjunto {a, b}* es contable (sección 4.3.6, página 26), se reconocerá a la aplicación concebida en aquella oportunidad, como una función f:N→{a, b}* inyectiva y suprayectiva, al mismo tiempo. De hecho, esta es la forma de enunciar correctamente la numerabilidad de un conjunto.

Definición: Sea f:A→B una función de A en B. Entonces "f" recibe el nombre de biyectiva (y se dice que es una biyección), si y sólo si, es a la vez inyectiva y suprayectiva.

En símbolos, f:A→B es biyectiva sii:

(∀ a,b∈ A: a ≠ b → f(a) ≠ f(b)) ∧ (∀ b∈ B: ∃ a∈ A/ b=f(a))



El tema de funciones es extremadamente extenso y sus aplicaciones muy variadas, pero una discusión detallada de las propiedades de las funciones y sus consecuencias matemáticas, exceden el ámbito de este texto, correspondiendo su estudio formal al Análisis Matemático y al Álgebra. Por esto, finalizaremos aquí nuestro estudio de funciones, figurando algunas otras pro-piedades de las mismas, en la ejercitación que sigue.

_____________________________________________________________ EJERCICIOS 4.4

4.4.1. Dada la siguiente relación sobre el conjunto de los números enteros Z:

R = {(-2,-8), (-1,1), (0,0), (1,1), (2,8), (3,27)} indique:

a) ¿Cuál es el alcance de la relación? b) ¿Cuál es el rango de la relación? c) ¿Cuál es el dominio de la relación? d) ¿Cuál es el codominio de la relación? e) Represente la relación por fórmula, tabla y matriz. f) Grafique la relación en un diagrama de ejes coordenados y muestre su

digrafo. g) Clasifique la relación según su reflexividad, su simetría y su transitividad. h) Establezca si R es una función. En caso afirmativo, analice si la misma es una

biyección. 4.4.2. Sea R la relación que se establece entre un país de América del Sur integrante del Mercosur

a la fecha, y su ciudad capital. Indique:

a) ¿Cuál es el alcance de la relación? b) ¿Cuál es el rango de la relación? c) ¿Cuál es el dominio de la relación? d) ¿Cuál es el codominio de la relación? e) Represente la relación por tabla y matriz. Enumere sus pares ordenados. f) Grafique la relación en un diagrama de Venn. g) Establezca si R es una función. En caso afirmativo, analice si la misma es una

biyección. 4.4.3. Defina por extensión, la relación inversa del ejercicio 4.4.1. e indique: a) ¿Cuál es el alcance de la relación? b) ¿Cuál es el rango de la relación? c) ¿Cuál es el dominio de la relación? d) ¿Cuál es el codominio de la relación? e) ¿Es esta relación una función? 4.4.4. En los números naturales, ¿es la relación "≥" una relación de orden parcial?. ¿Es además esta relación de equivalencia?. Justifique sus respuestas.



4.4.5. Diga si las siguientes relaciones en el conjunto de los números enteros, son re-flexivas, simétricas, antisimétricas, transitivas, de orden parcial y/o de equivalencia.

a) R = {(x,y) / y = x2} b) R = {(x,y) / y = x} c) R = {(x,y) / y < x} d) R = {(x,y) / y = 4x} e) R = {(x,y) / y = x(1/2)} 4.4.6. Las relaciones del ejercicio anterior, ¿son funciones?. En caso afirmativo, analice además si

son una biyección. 4.4.7. Utilizando el concepto de relación inversa, demuestre que f-1 (la relación inversa de f) es

función si y sólo si, f es una función biyectiva. 4.4.8. Demuestre que, si f es una función biyectiva, su función inversa también es una biyección. 4.4.9. Cite al menos dos ejemplos de relaciones:

a) Reflexivas e) Irreflexivas b) Simétricas f) Antisimétricas c) Transitivas g) No transitivas d) De orden parcial h) De equivalencia

4.4.10. Dé al menos de dos ejemplos de funciones que: a) Sean inyectivas pero no suprayectivas. b) Sean suprayectivas pero no inyectivas. c) Sean biyectivas. 4.4.11. Determine la verdad o falsedad de las siguientes proposiciones. En el caso de que la

proposición sea verdadera, proporcione una demostración; en caso contrario, indique un contraejemplo.

a) Si R y S son relaciones transitivas, entonces R ∪ S es una relación transitiva. b) Si R y S son relaciones simétricas, entonces R ∪ S es una relación simétrica. c) Si R y S son relaciones reflexivas, entonces R ∪ S es una relación reflexiva. d) Si R y S son relaciones transitivas, entonces R ∩ S es una relación transitiva. e) Si R y S son relaciones simétricas, entonces R ∩ S es una relación simétrica. f) Si R y S son relaciones reflexivas, entonces R ∩ S es una relación reflexiva. g) Si R y S son relaciones transitivas, entonces R ° S es una relación transitiva. h) Si R y S son relaciones simétricas, entonces R ° S es una relación simétrica. i) Si R y S son relaciones reflexivas, entonces R ° S es una relación reflexiva. j) Si R es una relación transitiva, entonces R-1 es una relación transitiva. k) Si R es una relación simétrica, entonces R-1 es una relación simétrica. l) Si R es una relación reflexiva, entonces R-1 es una relación reflexiva. m) Si R es una relación antisimétrica, entonces R-1 es una relación antisimétrica.



4.4.12. Sea R una relación de equivalencia sobre un conjunto finito A. ¿Cuántas clases de equivalencia pueden definirse en A?

4.4.13. Si R y S son relaciones de equivalencia. ¿Es R ° S una relación de equivalencia? 4.4.14. Sea P el conjunto de todas las proposiciones lógicas y sea v:P→{0,1} la función de

veracidad proposicional definida por: v(p) = 1, si la proposición p es verdadera, y v(p) = 0, si la proposición p es falsa. a) ¿Es efectivamente v una función? b) ¿Es esta función inyectiva? c) ¿Es suprayectiva? 4.4.15. Sea A un conjunto y sea U el conjunto universal. Si pensamos en la pertenencia de un

elemento a un conjunto, como una proposición lógica p:x∈ A, la función de veracidad proposicional del ejercicio anterior recibe el nombre de función característica de A en U, y se define como:

cA(x) = 1, si x es un elemento de A, y cA(x) = 0, si x no es un elemento de A. Para esta función, así definida: a) Determine alcance, rango, dominio e imagen de c. b) Demuestre que si C=∼ A, entonces cC(x) = 1 - cA(x), ∀ x∈ U. c) Demuestre que si C=A∪ B, entonces cC(x)=cA(x) + cB(x), ∀ x∈ U. d) Demuestre que si C=A∩B, entonces cC(x)=cA(x) . cB(x), ∀ x∈ U. 4.4.16. Demuestre que la equivalencia lógica es una relación de equivalencia.

4.4.17. ¿Es la implicación simple una relación de orden en el conjunto de las proposiciones lógicas?. ¿Y la doble implicación?

4.4.18. Sea A={1,2,3,4,5} y B={1,2}. Sea además la relación R de A en B definida por a es

múltiplo entero de b. a) Determine alcance, rango, dominio e imagen de R. b) Clasifique a R según sus propiedades. c) ¿Es R una relación de equivalencia?. d) ¿Es R una función?. 4.4.19. Sean a,b∈ Z y sea m∈ Z+. Se dice que a es congruente con b módulo m, sii m divide a (a-

b) en Z, y se lo denota por:

a ≡ b (mod m) Demuestre que la congruencia módulo m en Z es una relación de equivalencia.



Documents

MATEMATICAS DISCRETAS ( CONJUNTOS Y RELACIONES)