Teoria de conjuntos

MATEMÁTICA DISCRETA
TEMA 1: TEORÍA DE CONJUNTOS

CONJUNTOS: Intuitivamente un conjunto (cjto) es una colección bien definida de objetos a los que llamaremos elementos (eltos). Los conjuntos siempre se escriben en mayúsculas A,B,C,… mientras que los elementos se escriben en minúsculas a,b,c,… Para indicar que un elemento a pertenece a un conjunto A escribiremos a ∈ A, si no pertenece seescribe a ∉ A.
Si los eltos que usamos pertenecen a un cjto fijo U, a este se le llama universo o conjunto universal.
Los conjuntos se pueden describir por:
* Extensión: citando todos y cada uno de sus eltos separados por comas y todos ellos encerrados entre llaves. P:= { 0,2,4,6,8 }.
* Comprensión: especificamos el universo de donde elegimos los eltos que lo forman y cuál es la propiedadque los determina. P:= {a ≤Z │o ≤a ≤8 y a es par}.
ℤ = nº entero (-2,-1,0,1,2)
ℕ = nº natural (1,2,3,4,5)
Si el número de elementos de A es finito A es un cjto finito y este nº se representa por A = cardinalidad o tamaño de A , en otro caso se dice q A es infinito.
Ejemplo: Sea U:={1,2,3,…} (los enteros positivos).
A:={1,4,9,…,64,81} = { x2 │ x Є U y x2<100 } A = 9.
B:={2,4,6,…}=a ЄN a ≥1 y a es par=2kk Є U B=∞
En lo que sigue asumiremos fijado un universo U.
Dados los conjuntos C y D decimos que C es un subconjunto de D y se denota por C ᶜ D ó D ᵓ C. Si todos y cada uno de los eltos de C pertenecen también a D, es decir, x ∈ C ⇨ x ∈ D; también se dice que C está contenida en D y D contiene a C. Si esto ocurre que C ᶜ D y C ᵓ D, ambas son iguales C=D. Para denotar queno son iguales C ≠ D, C ᶜ D pero D ≠ C, D es más grande que C y C es un subconjunto propio de D, cuando esto ocurre se puede decir C ᶜ D ó D ᵓ C. Si C y D son finitos C ≤ D.
Si C y D son finitos, C ᶜ D y C ≠ D C < D.
Ejemplo: Sea U:={1,2,3,4,5,6,x,y,{1,2},{1,2,3},{1,2,3,4}} Donde x e yson letras minúsculas del abecedario.U= 11Sea A:= {1,2,3,4} , |A|=4 ¿Está A contenida en U? Sí. ¿A pertenece a U? Sí. Sea B:= {{1,2,3,4}} ¿Esta B contenida en U? Si está contenida.¿Pertenece B a U? No.
TEOREMA: Sean A,B,C ᶜ U se tiene que: Si A ᶜ B y B ᶜ C, por lo tanto A ᶜ C.
El conjunto vacio es el único conjunto que no tiene elementos, se denota por Ø ó por {}. El conjunto vacio lo contiene cualquier otro conjunto.
Dado un cjto A ᶜ U se dice conjunto de todos los subconjuntos de A a P(A):= { B ᶜ U | B ᶜ A }.
Ejemplo: A:= {1,2,3,4} P(A):= {Ø,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}, {1,2,3,4}} ⇨⇨ |P(A)|= 16 = 24
TEOREMA: Siendo n= número de elementos de A, |A|=n |P(A)|= 2n
* A contiene exactamente ( kn )= n!k!(n-k)
Hay tantos subconjuntos de A con k elementos como formas de elegir k elementos de entre n, como indica la fórmula.Factorial de 4! = 4x3x2x1 = 24.
Demostración: Sea A:={a1,a2,a3,…,an}.
Un subconjunto B queda determinado escribiendo debajo de cada elemento de A un 0 ó un 1, dependiendo si forma parte de B o no.
{1,2,3,4,5} 1 1 0 0 0 ⇨ {1,2} 1 0 0 0 1 ⇨ {1,5}0 1 1 0 0 ⇨ {2,3}
Por lo tanto hay tantos subconjuntos como expresiones binarias de longitud n, es decir 2n.
Ejercicio: ¿Cuántos subconjuntos de A:={1,2,3,4} hay con 1 elto?
( 14 )= 4!1!3! = 4x3x2x11x3x2x1 = 4 elementos.
¿Y con 2 eltos?
( 24 )= 4x3x2x12x1x2x1) = 6 elementos.
OPERACIONES CON CONJUNTOS:
Sean A y B ᶜ U, se...