8.4: Los números naturales están bien ordenados

La inducción es una herramienta muy poderosa, pero a veces es difícil de aplicar (y hay muchas versiones diferentes a las que hacer un seguimiento, como vimos en la sección anterior). En esta sección, demostramos una técnica estrechamente relacionada que a menudo es menos engorrosa de usar.

Definición\(8.4.1\).

Dejar\(S \subset \mathbb{R}\) y\(a \in \mathbb{R}\). Decimos que\(a\) es el elemento más pequeño de\(S\) iff:

• \(a \in S\), y
• \(\forall s \in S\),\(a \leq s\).

Ejemplo\(8.4.2\).

• El elemento más pequeño de\(\{2,4,6,8\}\) es 2.
• El elemento más pequeño de\(\{12,9,18,5,13\}\) es 5.

Es importante darse cuenta de que no todos los conjuntos de números tienen un elemento más pequeño:

Ejercicio\(8.4.3\).

Mostrar que el conjunto dado no tiene un elemento más pequeño.

1. \(\mathbb{Z} [Hint: If \(n \in \mathbb{Z}\), entonces\(n − 1 < n\).]
2. \(\mathbb{R}^{+}=\{x \in \mathbb{R} \mid x>0\}\)[Pista: Si\(x \in \mathbb{R}^{+}\), entonces\(x / 2 \in \mathbb{R}^{+}\).]
3. \(\varnothing\)[Pista: Un conjunto sin elementos no puede tener un elemento más pequeño.]

Este problema no surge para subconjuntos de\(\mathbb{N}\):

Teorema\(8.4.4\) (\(\mathbb{N}\) is Well-Ordered).

Cada subconjunto no vacío de\(\mathbb{N}\) tiene un elemento más pequeño.

Esta observación bastante obvia es tan poderosa como todas las muchas variaciones del Principio de Inducción Matemática. Es decir, si se\(P(n)\) puede probar para todos\(n \in \mathbb{N}^{+}\) usando cualquiera de las muchas formas de Inducción Matemática, entonces también se puede probar aplicando Teorema\(8.4.4\) al conjunto\[S=\left\{n \in \mathbb{N}^{+} \mid \neg P(n)\right\} .\]

Más precisamente, supongamos que no\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\). Entonces el hecho de que\(\mathbb{N}\) esté bien ordenado nos dice que hay uno más pequeño\(n\), tal que no\(P(n)\) es cierto. Esto significa que:

1. \(P(n)\)no es cierto, pero
2. \(P(k)\)es cierto para todos\(k < n\) (tal que\(k \in \mathbb{N}^{+}\)).

Obtener una contradicción a partir de estos dos supuestos completará la prueba que\(P(n)\) es cierta para todos\(n \in \mathbb{N}^{+}\).

Ejemplo\(8.4.5\) (Alternate Proof of Example \(8.3.3\)).

Supongamos que no es cierto eso\(F_{n} < 2^{n}\) para todos\(n \in \mathbb{N}^{+}\). (Esto conducirá a una contradicción.) Entonces, como\(\mathbb{N}\) está bien ordenado, hay una más pequeña\(n\), tal que\(F_{n} \geq 2^{n}\). Esto significa que

1. \(F_{n} \geq 2^{n}\), pero
2. \(F_{k} < 2^{k}\)para todos\(k < n\) (tal que\(k \in \mathbb{N}^{+}\)).

Tenga en cuenta que, desde\[F_{1}=1<2=2^{1} \quad \text { and } \quad F_{2}=1<4=2^{2} ,\]

vemos de (i) eso\(n \notin\{1,2\}\), entonces\(n \geq 3\). Por lo tanto\(n − 1 \in \mathbb{N}^{+}\) y\(n − 2 \in \mathbb{N}^{+}\). Entonces, ya que\(n − 1\) y\(n − 2\) son menores que\(n\), vemos de (ii) que\[(*) \quad F_{n-1}<2^{n-1} \text { and } F_{n-2}<2^{n-2} .\]

Ahora, tenemos\ [\ begin {aligned}
F_ {n} &=F_ {n-1} +F_ {n-2} & &\ text {(definición de la secuencia de Fibonacci)}\\
&<2^ {n-1} +2^ {n-2} & (*):\ text {la minimalidad de} n)\\
&<2^ {n-1} +2^ {n-1} & & (n-2<n-1)\\
&=2 ^ {n} & &.
\ end {alineado}\]

Esto contradice (i).

Ejercicio\(8.4.6\).

1. Demostrar\(F_{n+4} + F_{n} = 3F_{n+2}\) para todos\(n \in \mathbb{N}^{+}\).
2. Demostrar\(2^{n} > n^{2}\) para cada\(n \geq 5\).
3. Demostrar\(3^{n} > 2^{n} + 2n\), para cada\(n \geq 2\).

Ejercicio\(8.4.7\).

1. Demostrar que el Principio de Inducción Matemática (\(8.1.2\)) se desprende del hecho de que\(\mathbb{N}\) está bien ordenado.
2. Utilizar la inducción para probar el Teorema\(8.4.4\). [Pista:\(P(n)\) Definir como la aserción “Si\(S \subset \mathbb{N}\) y\(S\) contiene un elemento\(\leq n\), entonces\(S\) tiene un elemento más pequeño”.]