Inducc

N´
umeros naturales, principio de inducci´
on

1. Conjuntos inductivos.
Denotaremos por IN al conjunto de n´
umeros naturales, IN = {1, 2, 3, 4, 5, 6, . . .}, cuyos
elementos son suma de un n´
umero finito de unos. Recordemos que IN es cerrado para la
suma y el producto (la suma y el producto de n´
umeros naturales son n´
umeros naturales),
7
pero no lo es para la resta o la divisi´on (4 − 9 ∈
/IN y 5 ∈
/ IN).
Diremos que un subconjunto S de IR es inductivo si se satisfacen:
i) 1 ∈ S
ii) k ∈ S =⇒ k + 1 ∈ S
Ejemplos.
i) IR, IR>0 y IR≥1 son inductivos.
ii) IR<5 no es inductivo pues satisface i) pero no satisface ii)
iii) ∅ no es inductivo pues satisface ii) pero no satisface i)
iv) S = {x ∈ IR / x2 ≤ 3} no es inductivo pues no satisface ii):

√

2 ∈ S pero

√

2+1∈
/S

v) IN es inductivo.Ejercicio. ¿Cu´ales de los siguientes conjuntos son inductivos?
a) S1 = {x ∈ IR / x <

3
2

o x ≥ 27 }

b) S2 = {x ∈ IR / 6x2 − 2x + 2 ≥ 4}
c) S3 = {x ∈ IR / − x ∈ S2 }
d) S4 = IN − {11}
e) S6 = {a ∈ ZZ / a > −3}
Notemos que si S ⊆ IR es un conjunto inductivo entonces 1 ∈ S por i). Pero esto implica
que 2 ∈ S por ii) y luego 3 ∈ S nuevamente por ii), etc. Luego, IN ⊆ S. Por lo tanto,
IN es unconjunto inductivo que est´a contenido en todos los conjuntos inductivos. Si
consideramos el orden en los conjuntos dado por ⊆, esto puede resumirse en la forma: IN
es un conjunto inductivo que es menor que todo otro conjunto inductivo.
Supongamos ahora que H es un subconjunto de IR que tiene esta propiedad, es decir, H es
inductivo y H est´
a contenido en todos los conjuntos inductivos. Entonces debeser H = IN
(¿porque?) y esto significa que IN es el u
´ nico conjunto inductivo que est´a contenido en
todos los conjuntos inductivos. Si quisi´eramos dar una definici´on rigurosa del conjunto de
n´
umeros naturales podr´ıamos definirlo como el u
´nico conjunto inductivo que est´a contenido
en todos los conjuntos inductivos, es decir, la intersecci´on de todos los subconjuntos de IR
que soninductivos.

1

ALGEBRA I

N´
umeros naturales

Observaci´
on. De lo anterior se deduce que si H es un subconjunto de IN que satisface
i) 1 ∈ H
ii) k ∈ H =⇒ k + 1 ∈ H
entonces H = IN.
2. Principio de inducci´
on.
Sea P (n) una funci´on proposicional predicable sobre IN. Si valen
1) P (1) es verdadera
2) P (k) =⇒ P (k + 1), para todo k ∈ IN
entonces P (n) es verdadera para todo n ∈ IN.
Demostraci´
on:Sea H = {h ∈ IN / P (h) es verdadera}. Entonces H es un subconjunto de
IN que satisface
i) 1 ∈ H
ii) k ∈ H =⇒ k + 1 ∈ H
Luego, por la observaci´
on anterior, H = IN y por lo tanto P (n) es verdadera para todo
n ∈ IN.
Resumiendo, el principio de inducci´on dice que para probar que P (n) es verdadera para
todo n ∈ IN alcanza con probar que valen 1) y 2).
Ejemplos.
a) P (n) : n + 3 ≥ n + 7 satisface2) pues k + 3 ≥ k + 7 =⇒ k + 1 + 3 ≥ k + 1 + 7 pero sin
embargo P (n) no es verdadera para todo n ∈ IN. Lo que sucede en este caso es que P (1)
es falsa. Esto muestra que es necesario probar que P (1) es verdadera.
b) P (n) : n ≤ 7 satisface 1) pero sin embargo P (n) no es verdadera para todo n ∈ IN. Lo
que sucede es que no se satisface 2) pues P (7) no implica P (8) ya que P (7) es verdadera
y P(8) es falsa. Esto muestra que es necesario probar que P (k) =⇒ P (k + 1).
c) P (n) : 5n ≥ 2n + 3n . Veamos que en este caso valen 1) y 2) y por lo tanto P (n) es
verdadera ∀ n ∈ IN. Es claro que P (1) : 5 ≥ 2 + 3 es verdadera. Sea k ∈ IN. Veamos ahora
que P (k) =⇒ P (k + 1), es decir, 5k ≥ 2k + 3k =⇒ 5k+1 ≥ 2k+1 + 3k+1
Supongamos que 5k ≥ 2k + 3k (esta es la hip´
otesis inductiva a la queabreviaremos con
k+1
k+1
k+1
HI). Debemos probar que 5
≥2
+3
5k+1 = 5.5k

≥

5.(2k + 3k ) = 5.2k + 5.3k

por HI

≥
5≥2

2.2k + 5.3k

≥

2.2k + 3.3k = 2k+1 + 3k+1

5≥3

Luego, 5n ≥ 2n + 3n ∀ n ∈ IN.
d) P (n) : n5 ≥ n4 . Si bien puede demostrarse que P (n) es verdadera ∀ n ∈ IN utilizando
el principio de inducci´on, notemos que la siguiente demostraci´on es mucho m´as corta y
sencilla: dado n ∈ IN

2...