En el conjunto ℤ × ℤ×, donde ℤ× = ℤ − {0}, decimos que (a, b) y (c, d) están relacionados si ad = bc. Probar que esta relación es de equivalencia.
(Nota: Los números racionales se definen como las clases de equivalencia de esta relación).
11. Sea n > 0 un entero. Definimos la siguiente relación en ℤ. Decimos que a, b ∈ ℤ están relacionados si n divide a a − b. Probar que esta relación es de equivalencia y que la clase de equivalencia de a es
a + nℤ = {a + nz | z ∈ ℤ}.
12. Probar que las siguientes aplicaciones son biyectivas:
(i) f : ℕ× → P = {2, 4, 6, …} y g : ℕ× → I = {1, 3, 5, …} dadas por f(n) = 2n y g(n) = 2n − 1. Concluir que el conjunto de números pares e impares positivos son numerables.
(ii) Si m ∈ ℕ×, la aplicación f : ℕ× → {n ∈ ℕ× | n > m} dada por f(n) = n + m.
(iii) f : ℕ× → ℤ dada por f(n) = n/2 si n es par, y f(n) = (1 − n)/2 si n es impar. Concluir que ℤ es numerable.
(iv) f : ℕ× × ℕ× → ℕ× dada por f(n, m) = 2n−1(2m − 1).
13. Si f : A → B es suprayectiva y A es numerable, entonces B es finito o numerable.
(Nota: Se pueden aplicar el problema 1.5 y el corolario 1.11. También podemos construir g : B → A inyectiva utilizando el teorema del buen orden en ℕ. Como A es numerable, entonces A está bien ordenado. Si b ∈ B, sea a el menor elemento de f−1({b}) y podemos definir g(b) = a).
14. Sea A un conjunto numerable y sea B un conjunto. Probar las siguientes propiedades.
(i) Si B es finito, entonces A − B es numerable.
(ii) Si B es finito, entonces A ∪ B es numerable.
(iii) Si B es numerable, entonces A ∪ B es numerable. Concluir por inducción que la unión de un número finito de conjuntos numerables es numerable.
(iv) Si B es numerable, entonces A × B es numerable. Concluir por inducción que el producto cartesiano de un número finito de conjuntos numerables es numerable.
(Ayuda: Para (i), utilizar el teorema 1.10. Para (ii), podemos suponer por (i) que A ∩ B = ∅. Si B tiene m elementos, sabemos por el problema 1.12 (ii) que existe f : {n ∈ ℕ× | n > m} → A biyectiva. Para (iii), por el mismo problema existen f : P → A y g : I → B biyectivas. Aplicar el problema 1.13. Para (iv), aplicar el problema 1.12 (iv)).
15. Probar que ℚ es numerable, utilizando que f : ℤ × ℤ× → ℚ, definida por f(n, m) = n/m, es suprayectiva.
16. Si An es finito o numerable para todo n ∈ ℕ×, probar que
es finito o numerable.
(Ayuda: Por hipótesis, existe fn : ℕ× → An suprayectiva. Definimos
dada por f(n, m) = fn(m). Probar que f es suprayectiva).
17. Sea ℚ[x] el conjunto de los polinomios con coeficientes en ℚ.
(i) Probar que ℚ[x] es numerable.
(ii) Un número complejo α es algebraico sobre ℚ si existe un polinomio 0 ≠ f con coeficientes en ℚ, tal que f(α) = 0. Utilizando que todo polinomio f de grado n tiene (como mucho) n ráıces complejas, probar que el conjunto de los números algebraicos es numerable.
(Ayuda: Para (i), agrupar los polinomios según grado y aplicar los problemas 1.16 y 1.14 (iv). Para (ii), volver a aplicar el problema 1.16).
18. Comprobar el siguiente argumento de D. Keyt para probar que ℝ no es numerable. Definimos una aplicación inyectiva f : P (ℕ) → [0, 1/9] de la manera siguiente. Si S ⊆ ℕ, entonces f(S) es el número real 0.a0a1a2 … an …, donde an = 0 si n ∉ S, y an = 1 si n ∈ S. Por ejemplo, f(∅) = 0, f(N) = 0.11111 … = 1/9, f({0, 1, 3, 5}) = 0.110101, etc.
Utilizando los teoremas 1.8 y el problema 1.10, probar que [0, 1/9] no es numerable. Deducir que ℝ no es numerable.
19. Probar por inducción que
1 + 3 + 5 + … + (2n − 1) = n2.
20. Definimos 0! = 1 y n! = 1 · 2 … (n − 1) · n para n > 0. Si 0 ≤ a ≤ n, definimos
Si 1 ≤ a < n, probar que
Deducir que
21. Probar que el producto de k naturales consecutivos es divisible por k!
22. (Binomio de Newton) Si a, b ∈ ℤ y n > 0, entonces
23. Sea p un primo, y sea 1 ≤ k < p. Probar que p divide a
(Ayuda: Sabemos que p divide a
24. Probar las siguientes afirmaciones:
(i) Si n es impar,
