Conjuntos demostraciones

1. Apuntes de Matematica Discreta
2. Operaciones con Conjuntos
Francisco Jose Gonzalez Gutierrez
Cadiz, Octubre de 2004

2. Universidad de Cadiz Departamento de Matematicasii

3. Leccion 2
Operaciones con Conjuntos
Contenido
2.1 Deniciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.1.1 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.1.2 Interseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.1.3 Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.4 Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.5 Diferencia Simetrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2 Algebra de conjuntos. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.2.1 Leyes Idempotentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.2.2 Leyes Conmutativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.2.3 Leyes Asociativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.2.4 Leyes Distributivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.2.5 Leyes de Identidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.2.6 Ley Involutiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.2.7 Leyes del Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.2.8 Leyes de De Morgan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.3 Conjunto de las Partes de un Conjunto . . . . . . . . . . . . . . . . . . . . .
28
2.3.1 Denicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.4 Producto cartesiano de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.4.1n-tupla ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.4.2 Igualdad den-tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.4.3 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.4.4 Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
Introduciremos las operaciones con conjuntos que nos van a permitir obtener nuevos conjuntos, partiendo
de conjuntos ya conocidos.AyBseran dos conjuntos cualesquiera de un universal arbitrarioU.
2.1 Deniciones
Deniremos las principales operaciones entre conjuntos.
15

4. Universidad de Cadiz Departamento de Matematicas
2.1.1 Union
La union de dos conjuntosAyBes el conjunto formado por todos los elementos que pertenecen aA
o aB. Se notaA[B.
A[B=fx:x2A_x2Bg:
La disyuncion,_, se utiliza en el sentido inclusivo, es decir, signica \y/o".
2.1.2 Interseccion
La interseccion de dos conjuntosAyBes el conjunto formado por todos los elementos que pertenecen
aAy aB. Se notaA\B.
A\B=fx:x2A^x2Bg
SiAyBno tienen elementos en comun, es decir, siA\B=;, entonces diremos queAyBson
conjuntos disjuntos.
Ejemplo 2.1SeanA; ByCtres conjuntos.
(a)Demostrar que siCAyCB, entoncesC(A\B), es decir,A\Bes el mayor conjunto que
contiene aAy aB.
(b)Demostrar que siCAyCB, entoncesC(A[B), es decir,A[Bes el conjunto mas
peque~no que contiene aAy aB.
Solucion
(a)Supongamos queCAyCB, entonces la proposicion
8x(x2C=)x2A)^ 8x(x2C=)x2B)
es verdad. Esta proposicion es equivalente a
8x[(x2C=)x2A)^(x2C=)x2B)]
la cual, a su vez, equivale a
8x;[x2C=)(x2A^x2B)]
de aqu que
8x; x2C=)x2[(A\B)]
y, por lo tanto,
CA\B
(b)Supongamos queCAy queCB, y seaxun elemento arbitrario deA[Bentonces,
x2(A[B)()x2A_x2BfDenicion de uniong
=)x2C_x2CfPor hipotesisg
()x2C fIdempotencia de_g
luego,
8x;(x2A[B=)x2C)
de aqu que
C(A[B)
16

5. Matematica Discreta Francisco Jose Gonzalez Gutierrez
2.1.3 Diferencia
La diferencia entre dos conjuntosAyBes el conjunto formado por todos los elementos que pertenecen
aAy no pertenecen aB. Se nota porAnB.
AnB=fx:x2A^x2= Bg
El conjuntoAnBse lee \AmenosB" y recibe tambien el nombre de complementario relativo del
conjuntoBrespecto del conjuntoA.
2.1.4 Complementario
El complementario de un conjuntoAes el conjunto formado por todos los elementos del conjunto
universal que no pertenecen aA. Se notaA
c
.
A
c
=fx:x2U^x2= Ag
Observese que el complementario deAes igual a la diferencia entreUyA, es decir,A
c
=UnA.
2.1.5 Diferencia Simetrica
La diferencia simetrica entre dos conjuntosAyBes el conjunto formado por todos los elementos que
pertenecen aAo aBpero no a ambos. Se nota porA4B.
A4B= (AnB)[(BnA)
A[B
A
AnB A\B BnA
B
Operaciones con conjuntos
17

6. Universidad de Cadiz Departamento de Matematicas
Ejemplo 2.2Sean los conjuntos
A=fn2Z
+
:n613g
B=fn2Z
+
:nes par yn620g
C=fn2Z
+
:nes parg
HallarA[B; A\B; A
c
; B
c
; AnB; BnA; A4B; B\CyBnC.
Solucion
18

7. Matematica Discreta Francisco Jose Gonzalez Gutierrez
A[B=fn2Z
+
:n613g [ fn2Z
+
:nes par yn620g
=f1;2;3;4;5;6;7;8;9;10;11;12;13g [ f2;4;6;8;10;12;14;16;18;20g
=f1;2;3;4;5;6;7;8;9;10;11;12;13;14;16;18;20g
A\B=fn2Z
+
:n613g \ fn2Z
+
:nes par yn620g
=f1;2;3;4;5;6;7;8;9;10;11;12;13g \ f2;4;6;8;10;12;14;16;18;20g
=f2;4;6;8;10;12g
A
c
=fn2Z
+
:n =2Ag
=fn2Z
+
:n >13g
B
c
=fn2Z
+
:n =2Bg
=fn2Z
+
::(n2B)g
=fn2Z
+
::[nes par^(n620)]g
=fn2Z
+
::(nes par)_ :(n620)g
=fn2Z
+
: (nes impar)_(n >20)g
=f1;3;5;7;9;11; : : :g [ f21;22;23;24; : : :g
=f1;3;5;7;9;11;13;15;17;19;21;22;23;24; : : :g
AnB=fn2Z
+
:n2A^n =2Bg
=fn2Z
+
:n2A^n2B
c
g
=fn2Z
+
:n613^n2B
c
g
=f1;3;5;7;9;11;13g
BnA=fn2Z
+
:n2B^n =2Ag
=fn2Z
+
:n2B^n2A
c
g
=fn2Z
+
:nes par yn620 yn >13g
=fn2Z
+
:nes par y 146n620g
=f14;16;18;20g
A4B= (AnB)[(BnA)
=f1;3;5;7;9;11;13g [ f14;16;18;20g
=f1;3;5;7;9;11;13;14;16;18;20g
B\C=fn2Z
+
:nes par yn620g \ fn2Z
+
:nes parg
=fn2Z
+
:nes par yn620 ynes parg
=f2;4;6;8;10;12;14;16;18;20g
BnC=fn2Z
+
:n2Byn =2Cg
=fn2Z
+
:nes par yn620 ynes imparg
=;
19

8. Universidad de Cadiz Departamento de Matematicas
2.2 Algebra de conjuntos. Dualidad
Bajo las operaciones definidas en los apartados anteriores, los conjuntos satisfacen varias leyes o identi-
dades. Observaremos que existe una dualidad entre las leyes que utilizan la interseccion y las que utilizan
la union.
2.2.1 Leyes Idempotentes
Dado cualquier conjuntoAen un universal arbitrarioU, se verica:1.A[A=A2.A\A=A
Demostracion
En efecto, seaxun elemento arbitrario del universalU. Entonces,
1.
x2(A[A)()x2A_x2AfDefinicion de uniong
()x2A fIdempotencia de_g
De la arbitrariedad dexse sigue que
8x[x2(A[A)()x2A]
de aqu que
A[A=A
2.Analogamente se prueba queA\A=A.
2.2.2 Leyes Conmutativas
Dados dos conjuntosAyBde un universal arbitrarioU, se verica:1.A[B=B[A2.A\B=B\A
Demostracion
En efecto,
1.Seaxcualquier elemento deU. Entonces,
x2(A[B)()x2A_x2BfDefinicion de uniong
()x2B_x2AfCommutatividad de_g
()x2(B[A) fDenicion de uniong
Comoxes cualquiera deU, se sigue que
8x[x2A[B()x2B[A]
por lo tanto,
A[B=B[A
2.De una forma similar se demuestra queA\B=B\A. 20

9. Matematica Discreta Francisco Jose Gonzalez Gutierrez
2.2.3 Leyes Asociativas
Dados tres conjuntosA; ByCde un universal arbitrario,U, se verica:1.A[(B[C) = (A[B)[C2.A\(B\C) = (A\B)\C
Demostracion
En efecto, seaxes un elemento arbitrario deU. Entonces,
1.
x2A[(B[C)()x2A_[x2(B[C)] fDefinicion de uniong
()x2A_(x2B_x2C)fDefinicion de uniong
()(x2A_x2B)_x2CfAsociatividad de_g
()(x2A[B)_x2C fDefinicion de uniong
()x2(A[B)[C fDefinicion de uniong
De la arbitrariedad dexse sigue que
8x[x2A[(B[C)()x2(A[B)[C]
de aqu que
A[(B[C) = (A[B)[C
2.Analogamente se demuestra que
A\(B\C) = (A\B)\C

2.2.4 Leyes Distributivas
Dados tres conjuntosA; ByCde un conjunto universal arbitrario,U, se verica:1.A[(B\C) = (A[B)\(A[C)2.A\(B[C) = (A\B)[(A\C)
Demostracion
En efecto,
1.En efecto, seaxcualquier elemento del conjunto universalU, entonces
x2A[(B\C)()x2A_[x2(B\C)] fDefinicion de uniong
()x2A_(x2B^x2C) fDefinicion de intersecciong
()(x2A_x2B)^(x2A_x2C)fDistributividadg
()x2(A[B)^x2(A[C) fDefinicion de uniong
()x2(A[B)\(A[C) fDefinicion de intersecciong
Al serxcualquier elemento deU, se sigue que
8x[x2A[(B\C)()x2(A[B)\(A[C)]
21

10. Universidad de Cadiz Departamento de Matematicas
consecuentemente,
A[(B\C) = (A[B)\(A[C)
2.De una forma similar se prueba que
A\(B[C) = (A\B)[(A\C)

2.2.5 Leyes de Identidad
Dado un conjunto cualquiera de un universal arbitrario,U, se verica:1.A[ ;=A2.A[U=U3.A\ ;=;4.A\U=A
Demostracion
1.A[ ;=A. En efecto, seaxes un elemento arbitrario deU. Entonces,
x2(A[ ;)()x2A_x2 ; fDenicion de uniong
()x2A fx2 ;es falso siempreg
luego,
8x[x2(A[ ;)()x2A]
de aqu que
A[ ;=A
2.A[U=U. Seaxun elemento cualquiera deU. Entonces,
x2(A[U)()x2A_x2UfDenicion de uniong
()x2U fx2Ues verdad siempreg
luego,
8x[x2(A[U)()x2U]
es decir,
A[U=U
3.A\ ;=;. Sixes cualquiera deU, entonces
x2(A\ ;)()x2A^x2 ; fDenicion de uniong
()x2 ; f x2 ;es falso siempreg
luego,
A\ ;=;
4.A\U=A. Seaxun elemento arbitrario deU. Entonces,
x2A\U()x2A^x2UfDefinicion de intersecciong
()x2A fx2Ues verdad siempreg
luego,
A\U=A
22

11. Matematica Discreta Francisco Jose Gonzalez Gutierrez
2.2.6 Ley Involutiva
Dado un conjunto cualquieraAde un universalU, se verica:
(A
c
)
c
=A
Demostracion
Seaxcualquiera deU. Entonces,
x2(A
c
)
c
()x =2A
c
fDefinicion de complementariog
() :(x2A
c
)fNegaciong
() :(x =2A)fDefinicion de complementariog
() ::(x2A)fNegaciong
()x2A fDoble negaciong
luego,
8x[x2(A
c
)
c
()x2A]
es decir,
(A
c
)
c
=A

2.2.7 Leyes del Complementario
Dado un conjunto cualquieraAde un universal arbitrarioU, se verica:1.A[A
c
=U2.U
c
=;3.A\A
c
=;4.;
c
=U
Demostracion
1.A[A
c
=U. En efecto, seaxcualquier elemento deU. Entonces,
x2(A[A
c
)()x2A_x2A
c
fDefinicion de uniong
()x2A_x =2A fComplementariog
()x2A_ :(x2A)fNegaciong
()x2U fTautologag
luego,
8x[x2(A[A
c
)()x2U]
por lo tanto,
A[A
c
=U
2.U
c
=;. En efecto,
U
c
=fx2U:x2U
c
g=fx2U^x =2Ug=;
23

12. Universidad de Cadiz Departamento de Matematicas3.A\A
c
=;. En efecto,
A\A
c
=fx2U:x2A^x2A
c
g=fx2U:x2A^x =2Ag=;
4.;
c
=U. En efecto,
;
c
=fx2U:x2 ;
c
g=fx2U:x =2 ;g=fx2Ug=U

2.2.8 Leyes de De Morgan
Dados dos conjuntosAyBen un universalU, se verica:1.(A[B)
c
=A
c
\B
c
2.(A\B)
c
=A
c
[B
c
Demostracion
1.(A[B)
c
=A
c
\B
c
En efecto, seaxun elemento arbitrario del conjunto universalU. Entonces,
x2(A[B)
c
()x =2(A[B) fDefinicion de complementariog
() :[x2(A[B)] fNegaciong
() :[(x2A)_(x2B)]fDefinicion de uniong
() :(x2A)^ :(x2B)fDe Morgan para_g
()(x =2A)^(x =2B) fNegaciong
()(x2A
c
)^(x2B
c
)fDefinicion de complementariog
()x2(A
c
\B
c
) fDefinicion de intersecciong
y al serxun elemento arbitrario deU, se sigue que
8x[x2(A[B)
c
()x2(A
c
\B
c
)]
luego,
(A[B)
c
=A
c
\B
c
2.Analogamente se prueba que
(A\B)
c
=A
c
[B
c

Ejemplo 2.3SeanA; B; CyDsubconjuntos arbitrarios de un conjunto universal arbitrario,U.
Entonces,
(a)AnBA(b)SiAByCD, entonces (A[C)(B[D)(c)SiAByCD, entonces (A\C)(B\D)(d)A(A[B)(e)A\BA 24

13. Matematica Discreta Francisco Jose Gonzalez Gutierrez(f)SiAB, entoncesA[B=B(g)SiAB, entoncesA\B=A(h)An ;=A(i)A\(BnA) =;(j)A[(BnA) =A[B(k)An(B[C) = (AnB)\(AnC)(l)An(B\C) = (AnB)[(AnC)
Solucion
(a)AnBA
En efecto, seaxun elemento arbitrario deU,
x2AnB()x2A^x =2BfDenicion de diferenciag
=)x2A fSimplificaciong
luego,
8x[x2AnB=)x2A]
consecuentemente,
AnBA
(b)SiAByCD, entonces (A[C)(B[D)
En efecto, supongamos queAByCDy seaxun elemento arbitrario deU, entonces
x2A[C()x2A_x2CfDefinicion de uniong
=)x2B_x2DfHipotesisg
()x2(B[D) fDefinicion de uniong
luego,
8x[x2(A[C) =)x2(B[D)]
por lo tanto,
A[CB[D
(c)SiAByCD, entonces (A\C)(B\D)
Se prueba de forma analoga a la anterior.
(d)A(A[B)
En efecto, sixes cualquiera deU, entonces
x2A=)x2A_x2BfAdiciong
()x2A[B fDefinicion de uniong
luego,
8x[x2A=)x2(A[B)]
de aqu que
A(A[B)
25

14. Universidad de Cadiz Departamento de Matematicas(e)A\BA
En efecto, seaxun elemento cualquiera deA\B. Entonces,
x2A\B()x2A^x2BfDefinicion de intersecciong
=)x2A fSimplificaciong
luego,
8x[x2(A\B) =)x2A]
de donde se sigue
A\BA
(f)SiAB, entoncesA[B=B
En efecto, seaxcualquiera deUy supongamos queAB.
x2(A[B)()x2A_x2BfDefinicion de uniong
=)x2B_x2BfHipotesisg
()x2B fIdempotencia de_g
luego,
8x[x2(A[B) =)x2B]
por lo tanto,
A[BB
y por (d)
B(A[B)
De la doble inclusion se sigue la igualdad que buscamos.
(g)SiAB, entoncesA\B=A
Por el apartado (e), tenemos que
A\BA
Veamos la inclusion contraria.
Supongamos queABy seaxun elemento arbitrario deU, entonces
x2A=)x2A^x2BfHipotesisg
()x2(A\B) fDefinicion de intersecciong
luego,
8x[x2A=)x2(A\B)]
de aqu que
A(A\B)
Tenemos, pues, que
A(A\B) y (A\B)A
por lo tanto,
A=A\B
(h)An ;=A
Seaxcualquiera deU. Entonces,
x2An ; () x2A^x =2 ; fDenicion de diferenciag
()x2A fPor serx =2 ;verdad, siempreg
luego,
An ;=fx:x2Ag=A
26

15. Matematica Discreta Francisco Jose Gonzalez Gutierrez(i)A\(BnA) =;
En efecto,
A\(BnA) =A\(B\A
c
)fDiferencia de conjuntosg
=A\(A
c
\B)fConmutatividad de la uniong
= (A\A
c
)\BfAsociatividad de la intersecciong
=; \B fLeyes del complementariog
=; f Leyes de identidadg
(j)A[(BnA) =A[B
En efecto,
A[(BnA) =A[(B\A
c
) fDiferencia de conjuntosg
= (A[B)\(A[A
c
)fDistributividadg
= (A[B)\U fLeyes del complementariog
=A[B fLeyes de identidadg
(k)An(B[C) = (AnB)\(AnC)
An(B[C) =A\(B[C)
c
fDiferencia de conjuntosg
=A\(B
c
\C
c
) fDe Morgang
= (A\A)\(B
c
\C
c
)fIdempotencia de la intersecciong
= (A\B
c
)\(A\C
c
)fCommutatividad y asociatividadg
= (AnB)\(AnC) fDiferencia de conjuntosg
(l)An(B\C) = (AnB)[(AnC)
La demostracion es similar a la del apartado anterior.

Ejemplo 2.4Probar las identidades siguientes:
(a)A[(A\B) =A(b)A\(A[B) =A(c)AnB=A\B
c
(d)A[(A
c
\B) =A[B(e)A\(A
c
[B) =A\B
Solucion
(a)A[(A\B) =A
Seaxun elemento cualquiera del universalU, entonces
x2A[(A\B)()x2A_x2(A\B)fDenicion de uniong
=)x2A
luego8x; x2A[(A\B) =)x2Aes decir,
A[(A\B)A
27

16. Universidad de Cadiz Departamento de Matematicas
Por otro lado, siempre se verifica que
AA[X;8X2U
en particular,
AA[(A\B)
De la doble inclusion se sigue el resultado,
A=A[(A\B)
(b)A\(A[B) =A
En efecto,
A\(A[B) = (A\A)[(A\B)fDistributividadg
=A[(A\B) fIdempotencia de la intersecciong
=A fApartado (a)g
(c)AnB=A\B
c
En efecto, seaxcualquiera del conjunto universalU, entonces
x2AnB()x2A^x =2BfDefinicion de diferenciag
()x2A^x2B
c
fDefinicion de complementariog
()x2(A\B
c
) fDefinicion de intersecciong
luego,
8x; x2AnB()x2(A\B
c
)
por lo tanto,
AnB=A\B
c
(d)A[(A
c
\B) =A[BEn efecto,
A[(A
c
\B) = (A[A
c
)\(A[B)fDistributividadg
=U\(A[B) fLeyes del complementariog
=A[B fLeyes de identidadg
(e)A\(A
c
[B) =A\B
A\(A
c
[B) = (A\A
c
)[(A\B)fDistributividadg
=; [(A\B) fLeyes del complementariog
=A\B fLeyes de identidadg

2.3 Conjunto de las Partes de un Conjunto
Dado un conjuntoA, si nos referimos a algunos de sus subconjuntos estaramos considerando un conjunto
de conjuntos. En tales casos hablaremos de una clase de conjuntos o coleccion de conjuntos en vez de
un conjunto de conjuntos. Si quisieramos considerar algunos de los conjuntos de una clase dada de
conjuntos, entonces hablaremos de una subclase o de una subcoleccion.
28

17. Matematica Discreta Francisco Jose Gonzalez Gutierrez
Ejemplo 2.5SeaA=fa; b; c; d; egy seaAla clase de subconjuntos deAque contienen exactamente
tres elementos deA. Entonces,
A=ffa; b; cg;fa; b; dg;fa; b; eg;fa; c; dg;fa; c; eg;fa; d; eg;fb; c; dg;fb; c; eg;fc; d; egg
siendo los elementos deAlos conjuntos:
fa; b; cg;fa; b; dg;fa; b; eg;fa; c; dg;fa; c; eg;fa; d; eg;fb; c; dg;fb; c; egyfc; d; eg

2.3.1 Denicion
Dado un conjuntoA, llamaremos conjunto de las partes deAa la clase o coleccion de todos los
subconjuntos deAy se nota porP(A).
Observese que de acuerdo con esta definicion, siXes un conjunto cualquiera deU, entonces
X2P(A)()XA
Ejemplo 2.6SeaA=f1;2;3g. Entonces,
P(A) =f;;f1g;f2g;f3g;f1;2g;f1;3g;f2;3g;f1;2;3gg

Nota 2.1Si el conjuntoAes finito y tienenelementos, entoncesP(A) tambien es un conjunto finito
y tiene 2
n
elementos.
En efecto, seaXun elemento arbitrario deP(A). Para cadaa2A, hay dos opcionesa2Xoa =2X;
como haynelementos enA, habra
nveces
z
}|{
222 2 = 2
n
diferentes conjuntosX. Es decir,P(A) tiene 2
n
elementos.
Veremos otra demostracion en una leccion posterior.

Ejemplo 2.7Especificar el conjunto de las partes para cada uno de los conjuntos siguientes:
(a)fa; b; cg(b)ffa; bg;fcgg(c)ffa; bg;fb; ag;fa; b; bgg
Solucion
(a)fa; b; cg
P(fa; b; cg) =f;;fag;fbg;fcg;fa; bg;fa; cg;fb; cg;fa; b; cgg
(b)ffa; bg;fcgg
P(ffa; bg;fcgg) =f;;ffa; bgg;ffcgg ffa; bg;fcggg
(c)ffa; bg;fb; ag;fa; b; bgg
P(ffa; bg;fb; ag;fa; b; bgg) =P(fa; bg) =f;;fa; bg ffa; bggg
29

18. Universidad de Cadiz Departamento de Matematicas
2.4 Producto cartesiano de conjuntos
El concepto matematico de relacion esta basado en la nocion de relacion entre objetos. Algunas relaciones
describen comparaciones entre elementos de un conjunto: Una caja es mas pesada que otra, un hombre
es mas rico que otro, etc. Otras relaciones involucran elementos de conjuntos diferentes, tal como \x
vive eny", dondexes una persona eyes una ciudad, \xes propiedad dey" dondexes un edicio ey
es una empresa, o \xnacio en el pasyen el a~noz".
Todos los ejemplos anteriores son de relaciones entre dos o tres objetos, sin embargo, en principio,
podemos describir relaciones que abarquennobjetos, dondenes cualquier entero positivo. Cuando
hagamos una armacion que relacionenobjetos, sera necesario no solamente especicar los objetos en s
mismos sino tambien una ordenacion de los mismos. Por ejemplo, la posicion relativa de 3 y 5 da lugar
unicamente a dos armaciones \5<3" y \3<5", siendo una de ellas falsa y la otra verdadera.
Usaremos lasn-tuplas ordenadas de elementospara especificar una sucesion finita de objetos no nece-
sariamente distintos; la posicion relativa de los objetos en la sucesion nos dara la ordenacion necesaria
de los mismos.
2.4.1n-tupla ordenada
Llamaremosn-tupla ordenada a una sucesion denobjetosa1; a2; : : : ; andados en un cierto orden y
la notaremos por(a1; a2; : : : ; an).
Observese que es fundamental el orden en que escribamos los elementos de lan-tupla, as
(a1; a2; : : : ; an)6= (a2; a1; : : : ; an)
Sin= 2, unan-tupla ordenada se llama \par ordenado" y sin= 3, erna ordenada".

2.4.2 Igualdad den-tuplas
Diremos que dosn-tuplas ordenadas son iguales si, y solo si, susi-esimas componentes son iguales
para todoi;16i6n, es decir,
(a1; a2; : : : ; an) = (b1; b2; : : : ; bn)()ai=bi;8i;16i6n
Muchas veces trataremos con colecciones den-tuplas donde la componentei-esima de cadan-tupla es
un elemento de un conjuntoAi. Denimos el conjunto de todas lasn-tuplas ordenadas.

2.4.3 Producto cartesiano
Dada una coleccion arbitraria de conjuntosA1; A2; : : : ; An, llamaremos producto cartesiano de los
mismos y lo notaremos porA1A2 An, al conjunto formado por todas lasn-tuplas ordenadas,
(a1; a2; : : : ; an), dondeai2Ai;16i6n, es decir,
A1A2 An=f(a1; a2; : : : ; an) :ai2Ai16i6ng
En el caso de dos conjuntosAyB, tendremos
AB=f(a; b) :a2A^b2Bg
y este producto se llama binario siA=B, o sea,
AA=f(a; b) :a2A^b2Ag
30

19. Matematica Discreta Francisco Jose Gonzalez Gutierrez
y suele notarse porA
2
.
Su extension anconjuntos se dene como
AA
(n
A=f(a1; a2; : : : ; an) :ai2A;16i6ng
y lo notaremos porA
n
.
Nota 2.2Observese queA ;=;. En efecto, siA ;no fuese vaco, entonces existira, al menos, un
par (a; b)2A ;de aqu quea2Ayb2 ;, lo cual es imposible.
Ejemplo 2.8Considerando el conjuntoRde los numeros reales, el producto cartesianoR
2
=RR
es el conjunto de todos los pares ordenados de numeros reales.
RR=R
2
=f(x; y) :x; y2Rg
Cada puntoPrepresenta un par ordenado (x; y) de numeros reales y viceversa. AR
2
se le llama
normalmenteplano cartesiano.

Ejemplo 2.9SeanA=fx2R: 16x62gyB=fy2R: 06y61g. HallarAByBA.
Solucion
AB=f(x; y) : 16x62^06y61g
BA=f(y; x) : 06y61^16x62g

0

1

2

3
1
2
3
AB

0

1

2

3
1
2
3
BA
Ejemplo 2.9
CuandoAyBson, como en este caso, conjuntos de numeros reales, su producto cartesiano puede
representarse como un conjunto de puntos en el plano cartesiano.

Ejemplo 2.10SeaA=f1;2gyB=fa; b; cg. Entonces
AB=f(1; a);(1; b);(1; c);(2; a);(2; b);(2; c)g
BA=f(a;1);(a;2);(b;1);(b;2);(c;1);(c;2)g
31

20. Universidad de Cadiz Departamento de Matematicas
tambien,
AA=f(1;1);(1;2);(2;1);(2;2)g
BB=f(a; a);(a; b);(a; c);(b; a);(b; b);(b; c);(c; a);(c; b);(c; c)g

Nota 2.3En los ejemplos anteriores se observa que el producto cartesiano de dos conjuntos no es
conmutativo. Es decir, en general,AB6=BA
Ejemplo 2.11SeanA1=f1;2g,A2=fa; bgyA3=fx; yg. CalcularA1A2A3; A2A1A3y
A
2
3.
Solucion
A1A2A3=f(1; a; x);(1; a; y);(1; b; x);(1; b; y);(2; a; x);(2; a; y);(2; b; x);(2; b; y)g
A2A1A3=f(a;1; x);(a;1; y);(a;2; x);(a;2; y);(b;1; x);(b;1; y);(b;2; x);(b;2; y)g
A
2
3=A3A3=f(x; x);(x; y);(y; x);(y; y)g
2.4.4 Propiedades
El producto cartesiano es distributivo respecto de la union y la interseccion de conjuntos, es decir, si
A; ByCson tres conjuntos cualesquiera, se verica:
(a)A(B[C) = (AB)[(AC)(b)A(B\C) = (AB)\(AC)(c)(A[B)C= (AC)[(BC)(d)(A\B)C= (AC)\(BC)
Demostracion
(a)A(B[C) = (AB)[(AC)
En efecto, sea (x; y) un elemento arbitrario deA(B[C), entonces,
(x; y)2A(B[C)()x2A^y2(B[C) fDef. producto cartesianog
()x2A^(y2B_y2C) fDef. de uniong
()(x2A^y2B)_(x2A^y2C)fDist. de^respecto de_g
()(x; y)2(AB)_(x; y)2(AC)fDef. producto cartesianog
()(x; y)2(AB)[(AC) fDefinicion de uniong
luego,
8(x; y) ((x; y)2A(B[C)()(x; y)2(AB)[(AC))
es decir,
A(B[C) = (AB)[(AC)
Los apartados (b), (c) y (d) se demuestran de una forma similar.

Ejemplo 2.12SiU=Z
+
,A=f1;2;3;4g,B=f2;5gyC=f3;4;7g, determnense los conjuntos
siguientes:
(a)AB 32

21. Matematica Discreta Francisco Jose Gonzalez Gutierrez(b)BA(c)A[(BC)(d)(A[B)C(e)(AC)[(BC)
Solucion
(a)AB=f(a; b) :a2A^b2Bg
luego,
AB=f(1;2);(1;5);(2;2);(2;5);(3;2);(3;5);(4;2);(4;5)g
(b)BA=f(b; a) :b2B^a2Ag
luego,
BA=f(2;1);(2;2);(2;3);(2;4);(5;1);(5;2);(5;3);(5;4)g
(c)
A[(BC) =f1;2;3;4;(2;3);(2;4);(2;7);(5;3);(5;4);(5;7)g
(d)
(A[B)C=f(1;3);(1;4);(1;7);(2;3);(2;4);(2;7);(3;3);
(3;4);(3;7);(4;3);(4;4);(4;7);(5;3);(5;4);(5;7)g
(e)
(AC)[(BC) =f(1;3);(1;4);(1;7);(2;3);(2;4);(2;7);(3;3);
(3;4);(3;7);(4;3);(4;4);(4;7);(5;3);(5;4);(5;7)g

Ejemplo 2.13SeanA=fa; b; cg,B=fb; c; dgyC=fa; dg. EncontrarABCutilizando un
diagrama en arbol.
Solucion

a
b

d

a
c
a

d

a
d

d

a
b

d

a
c
b

d

a
d

d

a
b

d

a
c
c

d

a
d

d
Ejemplo 2.13
33

22. Universidad de Cadiz Departamento de Matematicas
La figura muestra el diagrama en arbol. Recorriendo cada una de las ramas obtenemos las distintas
ternas que integran el producto cartesiano de los tres conjuntos, es decir,
ABC=f(a; b; a);(a; b; d);(a; c; a);(a; c; d);(a; d; a);(a; d; d);(b; b; a);(b; b; d);(b; c; a)
(b; c; d);(b; d; a);(b; d; d);(c; b; a);(c; b; d);(c; c; a);(c; c; d);(c; d; a);(c; d; d)g

Ejemplo 2.14Dados tres conjuntos arbitrariosA; B; CU, probarA(B\C) = (AB)\(AC)
Solucion
A(B\C) = (AB)\(AC) En efecto,
8(a; b)2A(B\C)()a2A^b2(B\C)
()a2A^(b2B^b2C)
()(a2A^b2B)^(a2A^b2C)
()(a; b)2AB^(a; b)2AC
()(a; b)2(AB)\(AC)
luego,
8(a; b) ((a; b)2A(B\C)()(a; b)2(AB)\(AC))
es decir,
A(B\C) = (AB)\(AC)

Ejemplo 2.15Se consideran los conjuntosA=fx2Z: 36x68gyB=fx2Z:6< x64g.
HallarAB
Solucion
A=fx2Z: 36x68g=f3;4;5;6;7;8g
B=fx2Z:6< x64g=f5;4g
luego,
AB=
f(3;5);(4;5);(5;5);(6;5);(7;5);(8;5);(3;4);(4;4);(5;4);(6;4);(7;4);(8;4)g

Ejemplo 2.16Demostrar que
(A1B1)\(A2B2) = (A1\A2)(B1\B2)
Solucion
En efecto, sea (a; b) un elemento arbitrario de (A1B1)\(A2B2). Entonces,
(a; b)2(A1B1)\(A2B2)()(a; b)2(A1B1))^(a; b)2(A2B2)fDef. de\g
()(a2A1^b2B1)^(a2A2^b2B2)fDef. deg
()(a2A1^a2A2)^(b2B1^b2B2)fAsoc. y conm.g
()a2(A1\A2)^b2(B1\B2)
()(a; b)2(A1\A2)(B1\B2)
34

23. Matematica Discreta Francisco Jose Gonzalez Gutierrez
luego,
8(a; b) ((a; b)2(A1B1)\(A2B2)()(a; b)2(A1\A2)(B1\B2))
es decir,
(A1B1)\(A2B2) = (A1\A2)(B1\B2)

Ejemplo 2.17Dados los conjuntosA=fa; b; c; dg; B=f1;2;3gyC=f; ; g, hallar
(a)ABC(b)A(B\C)(c)A(B[C)
Solucion
(a)
ABC=f(a;1; );(a;1; );(a;1; );(a;2; );(a;2; );(a;2; );(a;3; );(a;3; );
(a;3; );(b;1; );(b;1; );(b;1; );(b;2; );(b;2; );(b;2; );(b;3; );
(b;3; );(b;3; );(c;1; );(c;1; );(c;1; );(c;2; );(c;2; );(c;2; );
(c;3; );(c;3; );(c;3; );(d;1; );(d;1; );(d;1; );(d;2; );(d;2; );
(d;2; );(d;3; );(d;3; );(d;3; )g
(b)A(B\C) =A ;=;(c)A(B[C)
Segun hemos visto en la leccion,
A(B[C) = (AB)[(AC)
luego,
A(B[C) =f(a;1);(a;2);(a;3);(b;1);(b;2);(b;3);(c;1);(c;2);(c;3);(d;1);(d;2);(d;3)
(a; );(a; );(a; );(b; );(b; );(b; );(c; );(c; );(c; );(d; );(d; );(d; )g

Ejemplo 2.18ParaA; B; CU, probar queA(BnC) = (AB)n(AC).
Solucion
En efecto,
8(a; b)2A(BnC)()a2A^b2BnC
()a2A^(b2B^b =2C)
()(a2A^b2B)^(a2A^b =2C)
()(a; b)2AB^(a; b)=2(AC)
()(a; b)2(AB)n(AC)
luego,
8(a; b) ((a; b)2A(BnC)()(a; b)2(AB)n(AC))
es decir,
A(BnC) = (AB)n(AC)
35