Problemas de matemática discreta

1. Pruebe la validez del principio de induccion bidimensional, esto es:
a) P (i, 0) ∀i ∈ N0
b) P (0, j) ∀j ∈ N0
c) P (i − 1, j) ∧ P (i, j − 1) ⇒ P (i, j)
Entonces K = {(i, j) ∈ N0 × N0 /P (i, j)}= N0 × N0
Demostraci´n. Aceptemos las hip´tesis de la inducci´n bidimensional
o
o
o
(a,b,c), luego sean:
Xn = {m ∈ N0 /P (m, n)} y Y = {n ∈ N0 /Xn = N0 }
afirmaci´n 1: 0 ∈ Y
o
Para que estosuceda se necesita que X0 = N0 , lo que equivale a:
X0 = {m ∈ N/P (m, 0)}
debido a la hip´tesis (a), esto se cumple.
o
Luego, sea k ∈ Y (Hip. Inductiva 1), veamos que k + 1 ∈ Y . Tenemos que Xk =N0 y queremos mostrar que Xk+1 = N0 . Procederemos
nuevamente por inducci´n, veamos que 0 ∈ Xk+1 :
o
0 ∈ Xk+1 ⇐⇒ P (0, k + 1)
debido a la hip´tesis (b), se cumple P (0, k + 1), por lo tanto 0 ∈Xk+1 .
o
Luego si p ∈ Xk+1 (Hip. Inductiva 2) veamos que p + 1 ∈ Xk+1 . Debido
a la hip´tesis inductiva 1 tenemos P (p + 1, k) y la nueva hip´tesis
o
o
inductiva 2: P (p, k + 1), luego debido a lahip´tesis (c) se tiene
o
P (p + 1, k + 1), lo cual implica Xk+1 = N0 . De ah´ obtenemos k + 1 ∈ Y
ı
y por consiguiente Y = N0 .
Finalmente, tenemos que para todo n ∈ N0 se cumple Xn = N0 (debidoa que Y = N0 ), por lo que para todo m, n ∈ N0 se cumple P (m, n).
2. Usando el principio del buen orden, demuestre que

√
2 es irracional.

√
Demostraci´n. Procederemos por contradicci´n, sea2 ∈ Q, esto imo
o
plica que existen m, n ∈ N (descartamos el caso de m ≤ 0 debido a que
√
√
2 > 0) tales que 2 = m . Luego sean los conjuntos:
n
Xm = {n ∈ N/ m2 = 2n2 }
1

Y = {m ∈ N/Xm =∅}
afirmaci´n 1: Y = ∅
o
Por el P.B.O. existe un primer elemento m0 ∈ Y , luego Xm0 = ∅ y
Xm0 ∈ N. Nuevamente por el P.B.O. existe un primer elemento
n0 ∈ Xm0 tal que m0 2 = 2n0 2 .
afirmaci´n 2:
om = ˚ n = ˚+ 1
2
2
Si m = n = ˚ entonces existen k, p ∈ N tales que:
2
m0
2k
k √
=
= = 2
n0
2p
p
Luego k < m0 , p < n0 y k 2 = 2p2 , lo que contradice la minimalidad de
m0 y n0 ....