Ejercicios Resueltos de Teoría de Números y Conjuntos: Fundamentos Matemáticos

1. Divisibilidad y Máximo Común Divisor

Dados a, b, d ∈ ℤ, si sabemos que mcd(a, b) = 1, entonces:

• Si además d|b, entonces mcd(a,d) = 1.
• Si además d | b, entonces mcd(a, d) = d.
• Si además d|(a × b), entonces mcd(a,d) = d.
• Si además d | a, entonces mcd(a, d) = 1.

X Si además d|b, entonces mcd(a,d) = 1.

Solución (a)

Supongamos mcd(a, d) = d′ &implies; d′ | a y d′ | d. Como d′ | d y d | b &implies; d′ | b.

d′ | a ????

d′ &implies; d′ | mcd(a,b) = 1 &implies; d′ = 1.

d|b

(b) es falso.

Si mcd(a, d) = d &implies; d | a.

d|a ???? d|b

(c) es falso.

Contraejemplo. Sea d = 6, a = 3, b = 2. mcd(a,b) = 1.

6 = d | (a × b) = 3 × 2 pero mcd(a, d) = mcd(3, 6) = 3 = 6 = d.

(d) es falso.

Si d | a &implies; mcd(a, d) = d.

2. Propiedades de los Conjuntos Potencia

Dadas las dos siguientes afirmaciones:

P(A) ∩ P(B) = P(A ∩ B)

P(A) ∪ P(B) = P(A ∪ B)

• Ambas son siempre ciertas.
• Ambas son siempre falsas.
• X Solamente es cierta siempre la primera.
• Solamente es cierta siempre la segunda.

Solución (c)

P(D) = {X | X ⊆ D}

P(A) ∩ P(B) = P(A ∩ B) es cierta.

⊆)

Sea X ∈ P(A) ∩ P(B) &implies; X ⊆ A y X ⊆ B &implies; X ⊆ A ∩ B. Por tanto X ∈ P(A ∩ B).

⊇)

???? X ⊆ A &implies; X ∈ P(A)

Sea X ∈ P(A ∩ B) &implies; X ⊆ A ∩ B &implies; X ⊆ A y X ⊆ B.

X ⊆ A &implies; X ∈ P(A)

X ⊆ B &implies; X ∈ P(B)

&implies; X ∈ P(A) ∩ P(B)

P(A) ∪ P(B) = P(A ∪ B). Es falsa.

Contraejemplo. A = {1}, B = {2}.

A ∪ B = {1,2}. {1,2} ∈ P(A ∪ B) pero {1,2} ∉ A = {1} y {1,2} ∉ B = {2}. Por tanto {1,2} ∉ P(A) ∪ P(B).

3. Elementos y Subconjuntos

Consideremos el conjunto A = {{1}, {1, 2, {}}, 1}. Entonces:

• A tiene 5 elementos.
• 2 ∈ A.
• X 2 ∉ A, pero existe X ∈ A tal que 2 ∈ X.
• {1} ⊆ A y {{1},1} ∈ A.

Solución (c)

A = {{1}, {1, 2, {}}, 1}

Tomamos X = {1,2,{}}. 2 ∈ X y 2 ∉ A. Es distinto de los tres elementos de A. (Luego (b) es falso).

2 = {1}, 2 = {1,2,{}}, 2 = 1 (a) es falso porque |A| = 3.

(d) es falso porque aunque {1} ⊆ A ya que 1 ∈ A = {{1},{1,2,{}},1} sin embargo {{1},1} ∉ A. Es distinto de los tres elementos de A.

{{1}, 1} ≠ {1}, {{1}, 1} ≠ {1, 2, {}}, {{1}, 1} ≠ 1.

4. Relaciones Binarias sobre Conjuntos Potencia

Sea R la relación binaria sobre P(ℕ) definida por:

X R Y ⇔ X \ Y = X

• R es reflexiva.
• X R es simétrica.
• R es antirreflexiva.
• R es transitiva.

Solución (b)

X R Y ⇔ X \ Y = X ⇔ X ∩ Y = X ⇔ X ⊆ Y ⇔ Y ⊆ X ⇔ Y ∩ X = Y ⇔ Y R X

(a) es falso porque no es reflexiva (∀X X R X). X R X ⇔ X \ X = X ⇔ X ∩ X = ∅ = X. Solo se cumple si X = ∅. Por lo tanto tampoco es antirreflexiva. (∀X X R X) ∅R∅.

No es transitiva (∀ X, Y, Z X R Y, Y R Z &implies; X R Z). {1}R{2}, {2}R{1} pero {1} ¬R {1}.

???? {1}\{2}={1} pero {1}\{1}=∅ {2} \ {1} = {2}

5. Funciones y Cardinalidad de Conjuntos

Sea f : {(X,Y)|X ∈ P(ℕ),Y ∈ P(ℕ),X = Y} → ℕ∪{ℵ₀} definida por f(X,Y) = |X ∩Y| (donde recordemos que ℵ₀ es el cardinal de los conjuntos numerables infinitos, o sea el de ℕ):

• f es inyectiva, pero no suprayectiva.
• X f es suprayectiva, pero no inyectiva.
• f es biyectiva.
• f no es ni inyectiva, ni suprayectiva.

Solución (b)

f no es inyectiva.

f({1},{1,2}) = |{1} ∩ {1,2}| = |{1}| = 1

f({1},{1,3}) = |{1} ∩ {1,3}| = |{1}| = 1

f es suprayectiva.

Sea n ∈ ℕ. Sea n = {0, 1, . . . , n − 1} y n + 1 = {0, 1, . . . , n − 1, n}.

f (n, n + 1) = |{0, 1, . . . , n − 1} ∩ {0, 1, . . . , n − 1, n}| = |{0, 1, . . . , n − 1}| = n.

Sea ℵ₀. Como ℤ y ℕ son numerables, |ℤ|=|ℕ|=ℵ₀.

f (ℤ, ℕ) = |ℤ ∩ ℕ| = |ℕ| = ℵ₀.

6. Cardinalidad de Conjuntos: Propiedades Avanzadas

Considera los dos asertos siguientes:

1. Si A es no numerable y B numerable, entonces A \ B es no numerable.
2. Toda familia (sea o no numerable) de conjuntos numerables tiene una unión numerable.

• Ambos son ciertos.
• Ambos son falsos.
• X El primero es cierto y el segundo es falso.
• El primero es falso y el segundo es cierto.

Solución (c)

Si A es no numerable y B es numerable entonces A \ B es no numerable.

Supongamos que A \ B fuese numerable. (A\B)∪(A∩B)=(A∩B)∪(A∩B)=A∩(B∪B)=A∩U =A

Contradicción.

La segunda es falsa.

Contraejemplo. F = {{r}|r ∈ ℝ} entonces ⋃ F = ℝ que es no numerable. Cada {r} es finito y por tanto numerable.

numerable.

7. Sucesiones Definidas Recursivamente y Demostración por Inducción

Considerando la sucesión (a_n | n ∈ ℕ) , definida recursivamente mediante: a₁ = 20, a_n = 5 × 4ⁿ − a_n−1, para n ≥ 2.

1. a) Demostración por Inducción de la Divisibilidad por 10

   Razonando por inducción, demuestra que para todo n ≥ 1, se tiene 10 | a_n.

2. b) Demostración por Inducción de la Fórmula Explícita

   Razonando por inducción, demuestra que a_n = 4ⁿ⁺¹ + 4 × (−1)ⁿ⁻¹, para todo n ≥ 1.

   Indicación: Tened cuidado con el valor de (−1)ⁿ⁻¹, según el valor de n.

3. c) Conclusión sobre la Divisibilidad

   Concluye de lo anterior que para todo n ≥ 1, 4ⁿ⁺¹ + 4 × (−1)ⁿ⁻¹ es múltiplo de 10.

Solución

a) Lo demostramos por inducción simple:

Caso Base:

n=1. S(1) ≡ 10 | a₁. Se cumple ya que a₁ = 20.

Hipótesis Inductiva (HI):

S(k) ≡ 10 | a_k. Es decir, a_k = 10t para algún t ∈ ℤ.

Paso Inductivo: S(k) &implies; S(k + 1)

S(k + 1) ≡ 10 | a_k+1

a_k+1 = 5 · 4^k+1 − a_k = 5 · 4 · 4^k − a_k = 20 · 4^k − 10t = 10(2 · 4^k − t)

(A∩B)⊆B ???? B numerable

&implies; (A ∩ B) es numerable.

(A \ B) ∪ (A ∩ B) = A sería unión de dos conjuntos numerables y por tanto, también numerable.

H.I. a_k = 10t

b) Lo demostramos por inducción simple:

Caso Base:

n=1. S(1) ≡ a₁ = 4¹⁺¹ + 4(−1)¹⁻¹ = 16 + 4 · 1 = 20.

Hipótesis Inductiva (HI):

S(k) ≡ a_k = 4^k+1 + 4(−1)^k−1.

Paso Inductivo: S(k) &implies; S(k + 1)

S(k+1) ≡ a_k+1 = 4^k+2 + 4(−1)^k.

a_k+1 = 5 · 4^k+1 − a_k

= 5 · 4^k+1 − (4^k+1 + 4(−1)^k−1)

= 4^k+1(5 − 1) − 4(−1)^k−1

= 4^k+1 · 4 + 4(−1) · (−1)^k−1

= 4^k+2 + 4(−1)^k

Luego se cumple.

c) Conclusión

Por (a) sabemos que 10 | a_n. Por (b) sabemos que a_n = 4ⁿ⁺¹ + 4(−1)ⁿ⁻¹. Por lo tanto, 10 | (4ⁿ⁺¹ + 4(−1)ⁿ⁻¹).

8. Propiedades de Divisibilidad y MCD

Sean a, b, c ∈ ℕ₁:

a) Demostración de la Propiedad

Demuestra que a|c ∧ b|c ∧ mcd(a,b)=1 &implies; (a×b)|c.

b) Contraejemplo

Prueba que la conclusión no tendría por qué darse, si no se tuviera la hipótesis mcd(a, b) = 1.

a) Solución

mcd(a,b)=1 &implies; m·a+n·b=1 (Teorema de Bezout)

a | c &implies; c = a · t₁

b | c &implies; c = b · t₂

1 = m·a+n·b. Multiplicamos por c.

c = m·a·c + n·b·c = m·a·(b·t₂) + n·b·(a·t₁) = ab(m·t₂ + n·t₁). Por tanto, ab|c.

b) Solución

Sean a=3, b=6, c=12. mcd(3,6)=3=1

a·b = 3·6 = 18, pero 18 no divide a 12.