Demostrando que no existe una secuencia descendente infinita de productos naturales mediante el contraejemplo mínimo

Question

Esta podría ser una de largo aliento manera de probar algo tan obvio, pero quiero verificar si se mantiene.

Reclamo: no existe una secuencia $\{{a}_{n \in \mathbb{N}}\}$ de los números naturales tal que $a_{n+1} < a_{n}$ por cada $n$.

Prueba: Esto equivale a mostrar que el conjunto de $M = \{ m \in \mathbb{N} : m \leq a_{0}\}$ donde $a_{0}$ es el primer miembro de cualquier secuencia infinita de descenso, es finito. Supongamos que por el bien de la contradicción que existe una $a_{0}$ de manera tal que el conjunto $M$ es infinito. Suponemos, además, que el $a_{0}$ es mínima. Claramente $a_{0} \neq 0$, pues si lo fuera, el conjunto $M = \{ m \in \mathbb{N} : m \leq 0\}$ = $\{0\}$ es finito.

Consideremos el conjunto a $N = M - \{n \in \mathbb{N}: a_{1} < n \leq a_{0}\}$, que es el conjunto de $M$, con un número finito de productos naturales eliminado. De elementrary la teoría de conjuntos, $N$ debe ser infinito.

Pero $N = \{ n \in \mathbb{N} : n \leq a_{1}\}$, y podemos suponer que $a_{1}$ es el primer término de un número natural de la secuencia infinita de descenso. Así que hemos encontrado otro conjunto infinito con la propiedad deseada, pero con $a_{1} < a_{0}$. Esto contradice la minimality de $a_{0}$.

Answer 1

Yo lo habría hecho hace por inducción sobre secuencias cuyo primer término $a_0\le n$ lugar y la propiedad de que son stationnary a partir de un cierto punto.

$n=0$ sólo una secuencia, la nula secuencia, es stationnary.

Para $a_0\le n+1$ si $a_0\le n$, entonces podemos aplicar la hipótesis de inducción, más desde $a_1<a_0$ $a_1\le n$ y podemos aplicar la hipótesis de inducción en el truncado de la secuencia.

Nota histórica :

Sin embargo, podemos preguntarnos si el principio de la inducción en sí no uso el infinito descenso a probarse ? De hecho Frege demostrado que es una consecuencia de la lógica de segundo orden dada la definición del cero, de un número y el sucesor de operación definido por Peano.

He encontrado esto en este artículo de $§6.4$ (aunque en francés, lo siento) : le raisonnement par de recurrencia, quel fondement ?.

Así que en la anterior prueba de toda cosa tiene efectivamente en estas cosas :

• la definición de las $0$ se utiliza cuando decimos que si $a_0\le0$, a continuación, toda la secuencia es el null-secuencia. (es decir, no es natural <0).

• el bien de pedidos de $\mathbb N$ se utiliza cuando decimos que $(a_0\le n+1)\land (a_1<a_0)\Rightarrow a_1\le n+1-1=n$, haciendo pleno uso del sucesor de definición.

En vuestra prueba, si queremos ser escrupuloso, cuando dices un número finito natural eliminado, entonces, es un poco molesto, ya que se muerde la cola : para probar que no hay infinito descendente de la secuencia de los naturales, sino que se invoca tecleando un argumento de finitness...

Anexo : (a partir de los comentarios)

En todas estas pruebas que están muy cerca de la axiomática del material, en teoría comprobar todo lo que escribimos para evitar la morderse la cola del problema (es decir, con un resultado demostró por medio del teorema queremos demostrar).

Sin embargo, aquí, se puede establecer el punto de partida como axiomas de Peano y el principio de la inducción y demostrar que infinito descenso así como así-principio de orden (es decir, cada conjunto de los naturales tiene un mínimo) son el sonido. Y, de hecho, estos eventualmente pueden convertirse en nuevas formas de inducción en sus el propios.

Este hecho son los principios usados en la de otros autores de las pruebas.

Answer 2

Esto equivale a mostrar que el conjunto de $M = \{ m \in \mathbb{N} : m \leq a_{0}\}$ donde $a_{0}$ es el primer miembro de cualquier secuencia infinita de descenso, es finito. $ \def\nn{\mathbb{N}} $

Esta primera línea de su 'prueba' no es válida. Usted está utilizando solamente tu intuición a la afirmación de que la no-existencia de un infinito descendente de la cadena de números naturales siguientes a partir de la finitud de un conjunto especificado. Esta es la circular , en este caso; demostrando la equivalencia asciende a probar algo de aproximadamente la misma fuerza que el original deseada teorema.

En lugar de lo que realmente necesitan es:

Deje $S = \{ n : n \in \nn \land \text{there is a strictly decreasing sequence from $\nn$ starting with $n$ } \}$.

Si $S$ es no vacío, entonces vamos a $m = \min(S)$ e (usar tus otras ideas) para demostrar que no es estrictamente una disminución de la secuencia de $\nn$ empezando con algo menos de $m$, lo que contradice la definición de $m$.

Por lo tanto, $S$ está vacía y ya está.

Answer 3

La prueba se ve bien para mí. Como @user21820 y otros señalan, que en realidad no lo es, y el otro contesta hacer un mejor trabajo de explicar esto. De hecho, incluso la prueba a continuación es inexacta como la $\dotsb$ implica la inducción, pero yo no he afirmado que, debido a que se trata de una "intuición" de la prueba. Suponiendo que la inducción y el 'sentido común' de las propiedades de los números naturales no es una cosa trivial para un muy axiomático pregunta como esta. (Gracias @user21820!)

---

He aquí otro pensé: desde la $a$s son números naturales, $a_{n + 1} < a_n$ es equivalente a $a_{n + 1} \leq a_n - 1$ debido a que no existen números naturales entre el$a_n$$a_n - 1$. A continuación, vamos a $n = a_1$ y tiene $$a_{n+1} \leq a_{n} - 1 \leq a_{n-1} - 2 \leq \dotsb \leq a_1 - n = 0$$ pero $a_{n+1} \geq 0$ como es un número natural, por lo $a_{n+1} = 0$. Más allá de que no puede haber números más pequeños.

(Yo uso 'natural' para significar 'entero positivo', sino que trabaja para 'entero no negativo" o incluso "conjunto de números enteros con un límite inferior'.)

Answer 4

Además de los comentarios en las respuestas por zwim y user21820, quiero subrayar que la prueba utiliza de manera esencial el hecho (necesario para ser probado en las presentaciones más comunes de los productos naturales) que cada grupo de productos naturales tiene un elemento menos.

Answer 5

(Creo que esta respuesta no reproducir de una ya existente, aunque las ideas son muy similares.)

Supongamos que por el bien de la contradicción que existe una secuencia, $\{a_n\}_{n \in \mathbb{N}}$. Consideremos el conjunto que contiene todos sus elementos. Dado que este es un conjunto no vacío de números naturales, contiene -- por el Principio de orden -- por lo menos un elemento, $a_k \in \mathbb{N}$. Puesto que la sucesión es estrictamente decreciente, $a_{k+1} < a_k$, lo que contradice la minimality de $a_k$.

Por lo tanto, nuestra suposición era incorrecta, y no hay tal secuencia existe.