Matemática Discreta Past Paper PDF

Matemática Discreta Facultad de Informática. 1. Demuestra que si A ∼c B y A ∩ B = ∅, entonces A ∪ B ∼c A × {0, 1}. 2. Demuestra que si f : A → A es una función inyectiva pero no suprayectiva entonces A es un conjunto infinito. (Indicación: Considera lo...

Matemática Discreta Facultad de Informática. 1. Demuestra que si A ∼c B y A ∩ B = ∅, entonces A ∪ B ∼c A × {0, 1}. 2. Demuestra que si f : A → A es una función inyectiva pero no suprayectiva entonces A es un conjunto infinito. (Indicación: Considera los elementos a, f (a), f (f (a)), etc., donde a ∈ A − ran(f )). 3. Sea A ⊆ B ⊆ C. Demuestra que si A ∼c C, entonces A ∼c B y B ∼c C. (Indicación: Aplica el teorema de Schröeder - Bernstein: A ≤c B, B ≤c A =⇒ A ∼c B). 4. Demuestra que los siguientes conjuntos son numerables. Son finitos?. Fn = {X ∈ P(N) | | X | = n} (donde n ∈ N es un número fijo) F = {X ∈ P(N) | X es finito} CF = {X ∈ P(N) | N − X es finito} 5. Usa la técnica de diagonalización de Cantor para demostrar que: a) (N → N) es un conjunto no numerable. b) (N → A) es un conjunto no numerable siempre que A tenga al menos dos elementos. 6. ¿Existe un conjunto X tal que P(X) sea un conjunto infinito numerable?. Justifica tu respuesta. 7. Estudia si A ≤c B , B ≤c A, o ambas en los siguientes casos: a ) A = N, B = Z b ) A = N, B finito c ) A = Q, B = P(N) d ) A = N × N, B = Q × Q e ) A = [0, 1], B = [0, 2] f ) A = N × Q, B = N × R 8. Dados los siguientes conjuntos P(N), N ∩ [0, 4], N × Q. Señala la respuesta correcta. Los tres conjuntos son numerables. Ninguno de los tres conjuntos es numerable. El tercero es el único conjunto numerable. El segundo y el tercero son numerables. 9. Given the following sets A = {n ∈ N/n ≥ 15}, B = {n ∈ N/2n2 + 5n < 50} y P(N), mark the correct answer: Los tres conjuntos son infinito numerables. A y B son infinito numerables. A y B son numerables. B y P(N) son numerables. 10. Sea f : {p ∈ N/pprimo} × {2n/n ∈ N} −→ N × Q, señala la respuesta correcta. f puede ser suprayectiva pero no biyectiva. f puede ser sinyectiva pero no biyectiva. f puede ser biyectiva. Ninguna de las anteriores. 11. Sea f : N → P(N), podemos afirmar que: f no puede ser suprayectiva. f no puede ser inyectiva. f no puede ser total. No tenemos información suficiente para conocer la respuesta correcta. 12. Sea C la familia de conjuntos definida como: C = {{n ∈ N | n ≥ m} | m ∈ N, m ≤ 5} Indica la respuesta correcta: S C es un conjunto finito y C = N. S C es un conjunto infinito numerable y C = N. S C es un conjunto finito y C = P(N). S C es un conjunto infinito numerable y C = P(N). 13. Sean A un conjunto infinito numerable y f : P(A) −→ A una función total. Indica la respuesta correcta: f puede ser una funcion inyectiva. f es necesariamente una funcion suprayectiva. f puede ser una función suprayectiva. Ninguna de las anteriores. 14. Dados los conjuntos P(N), Q, (N → N), Indica la respuesta correcta: Los tres conjuntos son no numerables. Los tres conjuntos son numerables. El segundo es el único numerable. El primero es no numerable, pero el segundo y el tercero son numerables. CONJUNTOS Y CARDINALES INFINITOS Def. Un conjunto A decimos que es finito y de cardinal n (n = |A|) si existe una biyección f : n −→ A donde n = {0, 1,... , n − 1} ⊆ N Es una definición correcta pues si n 6= m no existen f1 , f2 , biyecciones f1 6= f2 tales que f1 : n −→ A f2 : m −→ A si n 6= m. Esta propiedad se conoce como el Principio del Palomar que enunciamos a continuación: Sean A, B conjuntos finitos. Si f : A −→ B y |A| > |B| entonces f no es inyectiva. (Si hay más palomas que huecos en el palomar, al menos dos palomas tendrán que compartir hueco.) Teorema Sean A, B conjuntos finitos. Entonces 1. S ⊆ A =⇒ S también es finito y |S| ≤ |A| 2. A ∪ B es finito y |A ∪ B| = |A| + |B| − |A ∩ B| A ∩ B = ∅ =⇒ |A ∪ B| = |A| + |B|. 3. A − B es finito y |A − B| = |A| − |A ∩ B| B ⊆ A (A ∩ B = B) =⇒ |A − B| = |A| − |B| 4. A × B es finito y |A × B| = |A| · |B|. 5. El conjunto de todas las funciones de A en B (denotado por A −→ B) es finito y |A −→ B| = |B||A| 6. P(A) es finito y |P(A)| = 2|A| Dem. 1. Si S ⊆ A podemos definir la función de inclusión f : S ,→ A dada por f (x) = x pues x ∈ A, que es trivialmente inyectiva. Aplicando el Principio del Palomar |S| ≤ |A| y, por tanto, S es finito. 2. |A ∪ B| = |A| + |B| − |A ∩ B| pues los elementos de la intersección se cuentan dos veces, una al contar los de A y otra al contar los de B. Trivialmente si A ∩ B = ∅ =⇒ |A ∪ B| = |A| + |B|. 3. A\B es finito y |A\B| = |A|−|A∩B| pues los elementos de la intersección, que son elementos de B, se cuentan en A. Si B ⊆ A, (A ∩ B = B) =⇒ |A \ B| = |A| − |B| 1  4. A × B es finito y |A × B| = |A| · |B|. Como A×B = {(a, b)|a ∈ A, b ∈ B}, por cada elemento a de A hay tantos pares en A × B como elementos hay en B, luego |A × B| = |A| · |B|. 5. El conjunto de todas las funciones de A en B (denotado por A −→ B) es finito y |A −→ B| = |B||A| Identificamos cada función f de A en B con la n-tupla (f (a1 ), f (a2 ),... , f (an )) donde A = {a1 , a2 ,... , an }. Por tanto, el número de funciones de A en B coincide con el número de tuplas distintas que podamos construir. Si |B| = m hay m posibles valores para f (a1 ), para f (a2 ) y para f (an ), luego hay m · m · · · · · m = mn = |B||A| tuplas distintas. 6. Sea A un conjunto y sea B ⊆ A, la función caracterı́stica de B es: fB : A −→ {0, 1} definida por  1 si x ∈ B fB (x) = 0 si x 6∈ B Luego, existe una biyección h de P(A) en el conjunto de todas las fun- ciones de A en 2,A −→ 2 y, por tanto, |P(A)| = 2|A|. h : P(A) −→ (A −→ 2) h(B) = fB Es inyectiva. h(B1 ) = h(B2 ) =⇒ fB1 = fB2 =⇒ B1 = B2 Es suprayectiva. ∀g : A −→ 2 existe B ∈ P(A) tal que h(B) = g. Dado g : A −→ 2 construimos B de la siguiente forma: x ∈ B ⇐⇒ g(x) = 1. Se verifica g = fB y h(B) = fB = g Comparando Conjuntos Sean A, B conjuntos (finitos o infinitos). 1. A ∼c B sii ∃f : A −→ B biyectiva. Decimos que A y B son conjuntos equipotentes. 2. A ≤c B sii ∃f : A −→ B inyectiva. Decimos que A está dominado por B 3. A 0} es numerable. Q− = {x ∈ Q|x < 0} es numerable. Podemos definir f : Q+ −→ N inyectiva. f(mn ) = 2m 3n (m, n primos entre sı́.) Luego Q+ es numerable. CONJUNTOS NO NUMERABLES Teorema P(N) es un conjunto infinito, no numerable. Dem P(N) no es finito ya que N ≤c P(N) Basta definir f : N −→ P(N) inyectiva. f (n) = {n}. f es inyectiva. Si f (n) = f (m) =⇒ {n} = {m} =⇒ n = m. P(N) es no numerable. Vamos a demostrar que no existe g : N −→ P(N) suprayectiva. Supongamos que existe g0 : N −→ P(N) suprayectiva. Sean A0 = g0 (0) A1 = g0 (1) A2 = g0 (2)... Definimos D = {i ∈ N|i 6∈ Ai } ∈ P(N). Vamos a demostrar que aunque D ∈ P(N), D 6= g0 (n) ∀n ∈ N, es decir, g0 no es suprayectiva.. Supongamos D = g0 (n0 ) para algún n0 ∈ N : n0 ∈ D ⇐⇒ n0 6∈ An0 = g0 (n0 ) = D n0 ∈ D ⇐⇒ n0 6∈ D Contradicción. (Este método de demostración se conoce como método de Diagonalización de Cantor.) Teorema Sea A un conjunto. A