Logica

Conjuntos, relaciones y funciones
Susana Puddu

1. Repaso sobre la teor´ de conjuntos. ıa Denotaremos por IN al conjunto de los n´meros naturales y por Z al de los enteros. u Z Dados dos conjuntos A y B decimos que A est´ contenido en B o tambi´n que A es a e un subconjunto de B si cada elemento de A es tambi´n un elemento de B, es decir, si e x ∈ A =⇒ x ∈ B. En tal caso escribimos A ⊆ B.Decimos que los conjuntos A y B son iguales si A ⊆ B y B ⊆ A. En tal caso escribimos A = B. Decimos que A est´ contenido estrictamente en B si A ⊆ B y B ⊆ A, es decir, si a A ⊆ B y A = B. En ese caso escribimos A ⊂ B. Ejemplos. i) A = {1, 2, 3, 5, 7}, B = {1, 2, 3, 4, 5, 6, 7, 8} En este caso A ⊆ B pero no vale que B ⊆ A pues 4 ∈ B y 4 ∈ A. Luego, A est´ contenido / a estrictamente en B. ii) A = {a,b, {3}, 2}, B = {a, b, 3, 2} En este caso A ⊆ B pues {3} ∈ A y {3} ∈ B. Adem´s, B ⊆ A pues 3 ∈ B y 3 ∈ A. / a / iii) ∅ ⊆ A cualquiera sea el conjunto A, donde ∅ denota el conjunto vac´ ıo. iv) A = {a, b, c, d}, B = {b, d, c, a}. En este caso A = B. Operaciones con conjuntos. Sean A y B dos subconjuntos de un conjunto dado V , al que llamaremos conjunto referencial. Definimos la uni´n, intersecci´n,complemento, o o diferencia y diferencia sim´trica de la siguiente manera: e A ∪ B = {x ∈ V / x ∈ A o x ∈ B} A ∩ B = {x ∈ V / x ∈ A y x ∈ B} A = {x ∈ V / x ∈ A} / A − B = {x ∈ V / x ∈ A y x ∈ B} / A B = (A ∪ B) − (A ∩ B) (uni´n) o (intersecci´n) o (complemento respecto del conjunto referencial V ) (diferencia) (diferencia sim´trica) e

Grafiquemos estos conjuntos en un diagrama de Venn:
V A B
VA B

A∪B

A∩B

1

ALGEBRA I

Conjuntos, relaciones y funciones
V

V A

A

B

A
V A B

A−B

A B Observemos que, de estos conjuntos, el unico que realmente depende del conjunto refe´ rencial V es A . En general, cuando trabajemos con conjuntos, siempre supondremos que todos los conjuntos considerados son subconjuntos de un conjunto referencial y s´lo o aclararemos cu´l esese conjunto referencial cuando sea necesario. a Ejercicio. Probar que A − B = A ∩ B = {x ∈ A / x ∈ B}. / Diremos que los conjuntos A y B son disjuntos si A ∩ B = ∅. Ejemplo. Dado el conjunto referencial V = {a, b, c, d, 2, {2}, 3, {3}, 7} sean A, B y C los subconjuntos de V definidos por: A = {a, b, 2, {3}} se tiene que A ∪ B = {a, b, 2, 3, {3}}, A C = {a, b, {3}, 3, 7}, B = {a, b, 2, 3} A ∩ B ={a, b, 2}, C = {2, 3, 7} B − C = {a, b}

(A ∩ B) − (A C) = {2},

(A ∩ B) = {c, d, {2}, {3}, 3, 7}

Adem´s, B − C y (A ∩ B) son disjuntos. a Ejercicio. Sean A, B y C los conjuntos del ejemplo anterior. Hallar todos los subconjuntos de B ∪ C que sean disjuntos con A. Ejercicio. Sean A = {1, ∅, a, 7} y B = {{1}, a, b, 4}, C = {3, 6, b, a}. ¿Cu´les de las a siguientes afirmaciones son verdaderas?i) ∅ ∈ A ∪ B ii) ∅ ∈ A ∩ B iii) ∅ ⊆ A iv) ∅ ⊆ C v) 7 ∈ (A ∪ C) ∩ (A B)

2

ALGEBRA I

Conjuntos, relaciones y funciones

Propiedades de las operaciones. Sean A, B y C subconjuntos de un conjunto referencial V . Entonces valen: i) A ∪ B = B ∪ A, A ∩ B = B ∩ A y A B = B A ii) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C y A (B C) = (A B) C iii) A ⊆ B y B ⊆ C =⇒ A ⊆ C iv) A ⊆ B y A ⊆C =⇒ A ⊆ B ∩ C v) A ∩ B ⊆ A y A ∩ B ⊆ B vi) A ⊆ C y B ⊆ C =⇒ A ∪ B ⊆ C vii) A ⊆ A ∪ B y B ⊆ A ∪ B viii) (A ) = A, A ∩ A = ∅ y A ∪ A = V ix) A B = (A − B) ∪ (B − A) x) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) xi) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) xii) (A ∪ B) = A ∩ B xiii) (A ∩ B) = A ∪ B Demostraci´n: S´lo demostraremos iv), vi), viii) y xi) y dejamos como ejercicio la deo o mostraci´n de las restantespropiedades. o Demostraci´n de iv): Sabemos que A ⊆ B y que A ⊆ C. Debemos probar que A ⊆ B ∩ C: o Sea x ∈ A. Como A ⊆ B y x ∈ A entonces x ∈ B y como A ⊆ C y x ∈ A entonces x ∈ C. Luego resulta que x ∈ B y x ∈ C, es decir, x ∈ B ∩ C. Demostraci´n de vi): Sabemos que A ⊆ C y que B ⊆ C. Debemos probar que A ∪ B ⊆ C: o Sea x ∈ A ∪ B. Entonces x ∈ A o x ∈ B. Si x ∈ A entonces, como A ⊆ C resulta que x ∈...