1  Teoría de conjuntos

Ejercicio 1.1 Dado el conjunto universo de los números de un dado Ω={1,2,3,4,5,6} y los subconjuntos correspondientes a sacar par en el lanzamiento de un dado A={2,4,6} y sacar menos de 5 en el lanzamiento de un dado B={1,2,3,4}, calcular e interpretar los siguientes conjuntos:

  1. AB
  2. AB
  3. A y B
  4. AB y BA
  5. AB
  6. (AB)
  7. (AB)
  8. AB
  9. AB

¿Qué conjuntos de números en el lanzamiento de un dado serían disjuntos con A? ¿Y con AB?

  1. AB={1,2,3,4,6}
  2. AB={2,4}
  3. A={1,3,5} y B={5,6}
  4. AB={6} y BA={1,3}
  5. AB={1,3,6}
  6. (AB)={5}
  7. (AB)={1,3,5,6}
  8. AB={2,4,5,6}
  9. AB={2,4,5,6}

Serían disjuntos con A todos los conjuntos que solo tuviesen alguno de los números 1, 3 o 5, por ejemplo el conjunto {1,5}. El único conjunto disjunto con AB, además del vacío es {5}.

Ejercicio 1.2 Expresar con operaciones entre los conjuntos A, B y C, los conjuntos que se corresponden con las regiones sombreadas en los siguientes diagramas.

a.

b.

c.
  1. (BA)(ABC)
  2. (AB)(AC)(BC)(ABC)
  3. (ABC)((AB)(AC)(BC))

Ejercicio 1.3 Demostrar gráficamente las leyes de Morgan AB=AB y AB=AB.

Ejercicio 1.4 Construir por extensión el conjunto potencia del conjunto de los grupos sanguíneos S={0,A,B,AB}. ¿Cuál es su cardinal?

P(S)={,{0},{A},{B},{AB},{0,A},{0,B},{0,AB},{A,B},{A,AB},{B,AB},{0,A,B},{0,A,AB},{0,B,AB},{A,B,AB},{0,A,B,AB}}

Ejercicio 1.5 Construir el producto cartesiano del conjunto d los grupos sanguíneos S={0,A,B,AB} y el conjunto de los factores Rh R={Rh+,Rh}.

S×R={(0,Rh+),(0,Rh),(A,Rh+)),(A,Rh),(B,Rh+),(B,Rh),(AB,Rh+),(AB,Rh)}

Ejercicio 1.6 Demostrar que la relación R={(x,y)Z2:xy es par} es una relación de equivalencia.

Propiedad reflexiva: aZ aa=0 es par, de manera que aRa.
Propiedad simétrica: a,bZ si aRb entonces ab es par, es decir, existe kZ tal que ab=2k. Por tanto, ba=2(k) también es par y bRa.
Propiedad transitiva: a,b,cZ, si aRb y bRc entonces ab y bc son pares, de manera que su suma ab+bc=ac también es par, y aRc.

Ejercicio 1.7 ¿Cuáles de las siguientes relaciones son relaciones de equivalencia? ¿Cuáles don de orden?

  1. R1={(x,y)R2:x=y}
  2. R2={(x,y)R2:xy}
  3. R3={(x,y)R2:x2+y2=1}
  4. R4={(x,y)R2:x2+y21}
  1. R1 es relación de equivalencia.
  2. R2 es relación de orden.
  3. R3 no es relación de equivalencia ni de orden porque no cumple las propiedades reflexiva y transitiva.
  4. R4 es no es relación de equivalencia ni de orden porque tampoco cumple las propiedades reflexiva y transitiva.

Ejercicio 1.8 Para cada uno de los conjuntos siguientes, calcular si existe el supremo, el ínfimo, el máximo y el mínimo.

  1. A={1,2,3,4,5}
  2. B={xN:x es par}
  3. C={xQ:0<x1}
  1. sup(A)=5, inf(A)=1, max(A)=5, min(A)=1.
  2. inf(B)=2 y min(B)=2. No existe el supremo ni el máximo porque B no está acotado superiormente.
  3. sup(C)=1, inf(C)=0 y max(C)=1. No existe el mínimo.

Ejercicio 1.9 Dar ejemplos de funciones f:ZZ que cumplan lo siguiente:

  1. f es inyectiva pero no sobreyectiva.
  2. f es sobreyectiva pero no inyectiva.
  3. f no es inyectiva ni sobreyectiva.
  4. f es biyectiva y distinta de la función identidad.
  1. f(x)=2x
  2. f(x)=x/2.
  3. f(x)=x2
  4. f(x)=x+1

Ejercicio 1.10 Dadas las siguientes funciones de R en R, estudiar cuáles son inyectivas y cuáles sobreyectivas:

  1. f(x)=x2
  2. g(x)=x3
  3. h(x)=x3x22x
  4. i(x)=|x|
  1. f(x)=x2 no es ni inyectiva ni sobreyectiva.
  2. g(x)=x3 es biyectiva.
  3. h(x)=x3x22x es sobreyectiva pero no inyectiva.
  4. i(x)=|x| no es ni inyectiva ni sobreyectiva.

Ejercicio 1.11 Demostrar que la composición de dos funciones inyectivas es también inyectiva.

Sean f y g dos funciones inyectivas tales que Im(f)Dom(g). Veamos que gf es inyectiva. Supongamos ahora que existen a,bDom(f) tales que gf(a)=gf(b), es decir, g(f(a))=g(f(b)). Como g es inyectiva, se tiene que f(a)=f(b), y como f es inyectiva se tiene que a=b, con lo que gf es inyectiva.

Ejercicio 1.12 Dados dos conjuntos finitos A y B, demostrar que |AB|=|A|+|B||AB| y que |A×B|=|A||B|.

  1. AB=(AB)(BA)(AB) con AB, AB y BA disjuntos dos a dos, de manera que |AB|=|AB|+|BA|+|AB|.

    Por otro lado, A=(AB)(AB), y B=(BA)(AB), de modo que

    |A|+|B||AB|=|AB|+|AB|+|BA|+|AB||AB|=|AB|+|BA|+|AB|,

    que coincide con el resultado anterior.

  2. Supongamos que A={a1,,an} y B={b1,,bm}, de manera que |A|=n y |B|=m. Para cada elemento aiA se pueden formar m pares (ai,b1),(ai,bm). Como A tiene n elementos, en total se pueden formar nm pares, así que |A×B|=nm=|A||B|.

Ejercicio 1.13 Dada una función f:AB, demostrar que si f es inyectiva, entonces |A||B|, y si f es sobreyectiva, entonces |A||B|. ¿Cómo es |A| en comparación con |B| cuando f es biyectiva?

Sea f:AB inyectiva. Entonces para cualesquiera a1,a2A con a1a2 se tiene que f(a1)f(a2), por lo que |A||B|.

Sea f:AB sobreyectiva. Entonces para todo bB existe aA tal que f(a)=b. Además dos elementos de B no pueden tener la misma preimagen porque entonces f no sería una función, por lo que |A||B|.

De lo anterior se deduce que si f es biyectiva, entonces |A|=|B|.

Ejercicio 1.14 Dados dos conjuntos finitos A y B con |A|=n y |B|=m. ¿Cuántas funciones distintas se pueden construir de A a B? ¿Cuántas funciones sobreyectivas se pueden construir suponiendo que nm? ¿Y cuántas funciones inyectivas suponiendo que nm?

Se pueden construir mn funciones distintas, mmn funciones sobreyectivas y m!(mn)! funciones inyectivas.

Ejercicio 1.15 Tomando el conjunto de los números naturales N como conjunto universo, dar un ejemplo de un subconjunto infinito cuyo complemento también sea infinito.

A={xN:x es par} es infinito y A={xN:x es impar} también es infinito.

Ejercicio 1.16 Demostrar que todo conjunto infinito tiene un subconjunto infinito numerable.

Sean A un conjunto infinito. Como A no es vacío, existe un elemento a1A. Considérese ahora el conjunto A1=A{a1}. Es evidente que A1 sigue siendo infinito y podemos elegir otro elemento a2A1 de manera que el conjunto A2=A1{a2} sigue siendo infinito. Repitiendo este proceso indefinidamente obtenemos que el conjunto {a1,a2,} es un subconjunto de A que es numerable.

Ejercicio 1.17 Demostrar que un conjunto es infinito si y solo si es equipotente a un subconjunto propio.

Sea A un conjunto. Si A es finito, entonces cualquier subconjunto BA cumple que |B|<|A| por lo que no se puede establecer una biyección entre A y B.

Si A es infinito, por el ejercicio anterior se tiene que existe un subconjunto numerable B={a1,a2,}A. Si tomamos la aplicación f:BB{a1} dada por f(ai)=ai+1, entonces f es biyectiva, y su extensión f^:AA{a1} dada por

f^(x)={xsi xBf(x)si xB

es también biyectiva, por lo que A es equipotente a A{a1} que es un subconjunto propio suyo.

Ejercicio 1.18 Demostrar que el producto cartesiano de dos conjuntos numerables es numerable. ¿Y el producto cartesiano de n conjuntos numerables?

Sean A y B dos conjuntos numerables. Entonces existe una aplicación inyectiva f:AN y otra g:BN. Si se toma ahora la función h:A×BN definida como

f(a,b)=2f(a)3g(b)aA,bB,

se tiene que f es inyectiva y por tanto A×B es numerable.

Por inducción, es fácil probar que el producto cartesiano de n conjuntos numerables es también numerable.

Ejercicio 1.19 Demostrar que el conjunto de los números racionales es numerable.

Si se considera la aplicación f:QZ×N que a cada número racional r le hace corresponder el par (p,q)Z×N donde pq es la fracción irreducible de r con denominador positivo, se tiene que f es inyectiva. Como el producto cartesiano de dos conjuntos numerables es numerable, existe otra aplicación inyectiva de g:Z×NN, con lo que gf:QN es inyectiva y Q es numerable.

Ejercicio 1.20 Demostrar que la unión de dos conjuntos numerables es numerable.

Sean A y B dos conjuntos numerables disjuntos. Entonces existen dos biyecciones f:AN y g:BN. A partir de estas biyecciones se puede definir otra h:ABN dada por

h(x)={2f(x)1si xA2g(x)si xB

Así pues, AB es numerable.

Si A y B no son disjuntos, entonces AB=A(BA). Si BA={b1,,bn} es finito, se puede tomar la biyección g={(b1,1),,(bn,n)} y, a partir de ella, construir la biyección h:ABN dada por

h(x)={f(x)+nsi xAg(x)si xBA

Mientras que si BA es infinito, se puede razonar como al principio pues A y BA son disjuntos.

Ejercicio 1.21 Demostrar que el conjunto de los números irracionales no es numerable.

Ya hemos visto en el ejercicio que Q es numerable, de manera que si RQ fuese numerable, entonces por el QRQ=R sería numerable, lo cual no es cierto.

Ejercicio 1.22 Demostrar la unión de un conjunto numerable de conjuntos numerables es numerable.

Sea A un conjunto numerable de conjuntos numerables. Por ser A numerable existe una biyección f:NA, de manera que podemos enumerar los elementos de A de tal forma que Ai=f(i). Del mismo modo, como cada conjunto Ai es numerable se puede establecer una enumeración de sus elementos Ai={ai1,ai2,}. Así pues, podemos representar los elementos de i=1Ai en una tabla como la siguiente

a11a12a13a21a22a23a31a32a33

Siguiendo el orden de las flechas es posible enumerar todos los elementos de este conjunto, por lo que i=1Ai es numerable.

Ejercicio 1.23 Demostrar que el conjunto de todos los polinomios con coeficientes enteros P={a0+a1x+a2x2++anxn:nN,aiZ} es numerable. ¿Y el de los polinomios con coeficientes racionales?

Para cada nN sea Pn el conjunto de los polinomios de grado n con coeficientes enteros Pn={a0+a1x+a2x2++anxn:aiZ}. Para cada polinomio a0+a1x+a2x2++anxnPn podemos establecer una biyección entre sus coeficientes y la tupla pn=(a0,a1,,an), con aiZ. Por tanto, existe una biyección entre Pn y Zn, y como Zn es numerable, Pn también lo es.

Finalmente, P=i=1Pn que es la unión numerable de conjuntos numerables, que, como ya se vió en el , es numerable.

Del mismo modo, el conjunto de los polinomios de grado n con coeficientes racionales también es numerable, ya que podemos establecer una biyección entre sus coeficientes y la tupla pn=(a0,a1,,an), con aiQ. Por tanto, existe una biyección entre Pn y Qn, que es numerable.

Ejercicio 1.24 ¿Cuáles de los siguientes conjuntos son numerables?

  1. A={3k:kZ}
  2. B={xQ:10<x<10}
  3. C={xR:0x1}
  4. D={(x,y):xZ,yQ}
  5. E={1/n:nN}
  1. A es numerable ya que es un subconjunto de Z y un subconjunto de un conjunto numerable es numerable.

  2. B es numerable ya que es un subconjunto de Q y un subconjunto de un conjunto numerable es numerable.

  3. C no es numerable ya que cualquier intervalo real con más de un número es no numerable. Para probarlo podemos usar el mismo razonamiento que para probar que el conjunto de los números reales es no numerable. El conjunto C está formado por los números decimales de la forma 0.d1d2,. Supongamos que existe la siguiente biyección entre C y N:

    1. 0.d1,1,d1,2,d1,3,
    2. 0.d2,1,d2,2,d2,3,
    3. 0.d3,1,d3,2,d3,3,

    Entonces es posible construir otro número real 0.c1c2c3,ldots tal que ci=di,i+1 o ci=0 si di,i=9. Este número real sería diferente de todos los de la enumeración anterior, ya que se diferenciaría de cada uno de ellos en al menos una cifra decimal. Por tanto, habría al menos un número que no estaría emparejado con un número natural mediante la aplicación, por lo que no podría ser una biyección entre C y N.

  4. D es numerable al ser el producto cartesiano de dos conjuntos numerables.

  5. E es numerable ya que se puede establecer la biyección f(n)=1/n entre N y E.

Ejercicio 1.25 ¿Es el conjunto de todas las secuencias infinitas de ADN numerable?

No es numerable, ya que, al igual que ocurre con los números reales, no es posible hacer una enumeración de sus elementos. Las cadenas de ADN son secuencias de elementos conocidos como bases, que pueden ser A (Adenina), T (Timinia), G (Guanina), C (Citosina). Si existiese una biyección entre el conjunto de estas cadenas infinitas y N, como por ejemplo, la siguiente,

  1. A,T,C,
  2. C,G,A
  3. T,C,G,

podríamos construir una nueva cadena distinta de todas las de esta enumeración, cambiando la base de la posición i por otra distinta de la que tenga en la misma posición la cadena i de la enumeración. De esta manera, la enumeración anterior no sería una biyección, pues habría al menos una cadena que no tendría asociado un número natural.