¿Por qué hacemos la inducción matemática sólo para los números enteros positivos?

Question

Después de leer una pregunta hecha aquí, Quería preguntar: "¿Por qué hacemos la inducción matemática sólo para los números enteros positivos?".

Sé que solemos empezar nuestra inducción matemática demostrando que funciona para $0,1$ porque suele ser lo más fácil, pero ¿por qué sólo probamos que funciona para $k+1$ ?

¿Por qué no probar que funciona para $k+\frac12$ Suponiendo que funcione para $k=0$ .

Aplicando algunos límites en esto, por qué no probamos que funciona para $\lim_{n\to0}k+n$ ?

Quiero hacer esto porque me di cuenta de que la inducción matemática sólo demostrará que funciona para $x=0,1,2,3,\dots$ . suponiendo que empecemos en $x=0$ lo que significa que no se sabe si funcionará para $0<x<1$ para todos $x$ .

Y por qué no hacer $k-1$ ? De esta manera podemos demostrarlo también para los números negativos, ¿no?

¿Qué tienen de especial nuestros números enteros positivos a la hora de hacer una inducción matemática?

Y entonces esto sólo funcionará para los números reales porque definitivamente no podemos hacerlo para los números complejos, ¿verdad?

¿Y qué pasa con la asignación de valores para que se convierta en uno de los anteriores? Es decir, cambiarlo para que tengamos $x\to x/2$ ? Entonces, demostrando para $x+1$ se convierte en una prueba para todos $x$ que es un múltiplo de $\frac12$ !?

Answer 1

Olvidémonos de los números naturales por un momento y echemos un vistazo a lo que la inducción matemática está demostrando. En el paso base, se demuestra que una propiedad, digamos $P$ es válida para algún objeto especial, por ejemplo $a$ . En el paso de inducción, se demuestra que si $P$ se mantiene para algún objeto fijo, digamos $x$ entonces es válido para algún otro objeto relacionado con $x$ de alguna manera, lo que puede traducirse matemáticamente en: para alguna función $S$ , $P$ se mantiene para $S(x)$ . Ahora bien, como sabemos que $P$ se mantiene para $a$ concluimos que $P$ se mantiene para $S(a)$ y luego para $S(S(a))$ y así sucesivamente: $$a\quad\to\quad S(a)\quad\to\quad S(S(a))\quad\to\quad S(S(S(a)))\quad\to\quad\dots$$ esto lleva a una secuencia de objetos definidos así: $$a_0=0$$ $$a_{n+1}=S(a_n)$$ $$a_0\quad\to\quad a_1\quad\to\quad a_2\quad\to\quad a_3\quad\to\quad\dots$$ y $P$ se mantiene para cada elemento de esta secuencia. Si miramos los índices, encontramos números naturales. Así que los números naturales aparecen de forma natural en las pruebas inductivas. Puede ser útil notar que teniendo sólo la base y el paso inductivo, los objetos mencionados anteriormente son los únicos objetos que hemos probado que tienen la propiedad $P$ .

Ahora, el objeto de partida estándar es $0$ y la función sucesora estándar es $S(x)=x+1$ . Pero poniendo cualquier otro objeto en una secuencia, puedes usar la inducción para dar una prueba. Nótese que incluso en ese caso, se puede definir una secuencia como lo hicimos antes, ¡y utilizar la inducción estándar! Así que no hay ninguna diferencia real entre ellas. Por ejemplo, dejando que $a=0$ y $S(x)=x-1$ se puede demostrar una propiedad para cada número entero no positivo. En este caso tenemos $a_n=-n$ . Así que se puede utilizar la inducción matemática dos veces para demostrar una propiedad para todos los enteros; una vez con $a=0$ y $S(x)=x+1$ y una vez con $a=0$ y $S(x)=x-1$ .

Por último, puede ser útil observar que no todos los conjuntos de objetos pueden representarse como una secuencia. Por ejemplo, los números reales no se pueden enumerar en una secuencia y, por tanto, no se puede utilizar este tipo de inducción para ellos.

Answer 2

La inducción realmente sólo requiere que siempre podamos hacer algún tipo de camino entre nuestro caso base y los casos que queremos probar. La forma normal de la inducción hace un camino que se parece: $$\rightarrow 0\rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow \ldots$$ donde cada flecha representa una implicación - que el caso de $n$ implica el de $n+1$ . Incluyo una flecha para $0$ para recordarnos que ese caso debe ser probado. Es perfectamente posible reemplazar este camino por cualquier otro - así que $$\rightarrow 0\rightarrow \frac{1}2\rightarrow 1\rightarrow \frac{3}2\rightarrow 2\rightarrow \ldots$$ funciona igual de bien o partiendo de un negativo $$\rightarrow-1\rightarrow 2\rightarrow 3 \rightarrow 4\rightarrow 5\rightarrow\ldots$$ o ir en ambas direcciones $$\begin{align*} & \downarrow & \\\ldots\leftarrow-3\leftarrow -2\leftarrow -1 \leftarrow &\,\,0\rightarrow1\rightarrow 2 \rightarrow 3\rightarrow\ldots\end{align*}$$ siempre y cuando podamos proporcionar una prueba correspondiente a cada una de las flechas.

Una cosa notable de esto es que podemos usar algo llamado "inducción estructural" donde pensamos en estructuras matemáticas discretas (como gráficos o grupos) y probamos alguna propiedad de ellas reduciendo el problema a un caso más pequeño (de manera que, suficientes reducciones de este tipo nos llevan a algún caso base), y estos podrían tener diagramas bastante complejos si se grafican como he estado haciendo. El punto principal de estos cuadros es que la inducción requiere hacer algún tipo de enlace.

En sentido abstracto, lo que la inducción requiere es que ordenemos todos los casos sobre los que queremos demostrarla de una manera especial llamada "orden de pozo", lo que significa que cada conjunto no vacío tiene un mínimo (es decir, un elemento $x$ para que no haya $y<x$ en el conjunto). Entonces, tenemos que demostrar, para cualquier elemento $x$ una prueba de que, si nuestra proposición deseada es válida para todos $y<x$ es válida para $x$ también. Lo que encontramos entonces es que, si hubiera un contraejemplo, habría un contraejemplo mínimo - algún $x$ tal que para todo $y<x$ , sostuvo el comunicado. Pero esto es imposible ya que la afirmación se mantiene para todos $y<x$ es suficiente para demostrar la proposición.

La inducción ordinaria utiliza el orden ordinario sobre los números naturales -y observamos que se requiere demostrar que el caso de $0$ se mantiene asumiendo que se mantiene para todos $x<0$ - por supuesto, no hay tales $x$ en nuestro dominio, lo que explica por qué el caso base necesita una prueba separada. Del mismo modo, podemos inducir sobre el conjunto $\frac{1}2\mathbb N$ utilizando el orden normal. Y, la inducción sobre $\mathbb Z$ I representado proviene del orden (parcial) definido como normal en los positivos y definido como $-n<-m$ en los negativos exactamente cuando $n<m$ para $n,m\in\mathbb N$ (donde no decimos que $1<-1$ o $-1<1$ - nunca necesitamos compararlas, ya que ninguna se utiliza en la prueba de la otra).

La orden ordinaria sobre $\mathbb R>0$ no satisface esto. Sin embargo, si se puede demostrar que si la afirmación se cumple para $x$ entonces es válido para $x+k$ para todos $k\in (0,\varepsilon]$ para un fijo $\varepsilon$ entonces se puede ordenar el conjunto diciendo que $x<y$ siempre que $x+\varepsilon$ es menor que $y$ en el orden habitual, y este es un orden bien, por lo que podemos utilizar la inducción. Sin embargo, esto nos obliga a demostrar infinitas implicaciones, y realmente no se ve tanto.

Answer 3

La inducción funciona en un conjunto $A$ que está dotado de una relación $R\subset A\times A$ tal que todo subconjunto no vacío $B$ de $A$ contiene un elemento $b\in B$ con $\{x\in A\mid x \mathrel{R} b\}\cap B=\varnothing$ . Una relación que satisface esto es por definición " bien fundado ".

Dejemos que $\mathcal P$ sea alguna propiedad de los elementos de $A$ que se "hereda" de $R$ -Predecesores. Esto en el sentido de que: si $\mathcal P(b)$ para todos $b\in A$ con $b \mathrel{R} a$ entonces también $\mathcal P(a)$ . Entonces se puede demostrar que $\mathcal P(a)$ es verdadera para cada $a\in A$ .

Para demostrarlo, supongamos que la afirmación no es cierta. Entonces el conjunto $B:=\{a\in A\mid\neg\mathcal P(a)\}$ no está vacío. Sea $b\in B$ con $\{x\in A\mid x \mathrel{R} b \}\cap B=\varnothing$ . Entonces $\mathcal P(c)$ para $c\in A$ con $c \mathrel{R} b$ y en consecuencia $\mathcal P(b)$ . Se encuentra una contradicción, y estamos listos.

Así que el esencial La pregunta aquí es:

¿se trata de una relación bien fundada sobre un conjunto?

La respuesta es "sí" si se trabaja, por ejemplo, con $\langle\mathbb N,<\rangle$ o $\langle\{\frac12n\mid n\in\mathbb N\},<\rangle$ o $\langle-\mathbb N,>\rangle$ pero es "no" si se trabaja, por ejemplo, con $\langle\mathbb R,<\rangle$ , $\langle\mathbb Z,<\rangle$ o $\langle\mathbb N,>\rangle$ .

Answer 4

De todos modos, todos los contextos en los que propones aplicar la inducción utilizan implícitamente los enteros positivos.

Por ejemplo, supongamos que tenemos una propiedad $P$ y demostramos que $P(x)\implies P(x+\frac 1 2)$ . Entonces, si sabemos $P(0)$ podemos demostrar $P(0.5)$ , $P(1)$ , $P(1.5)$ etc. Pero aquí estás usando implícitamente los números naturales. Estás demostrando que si $P(n\frac 1 2)$ se mantiene, entonces $P((n+1)\frac 1 2)$ se mantiene, y por lo tanto se concluye que $P(n\frac 1 2)$ es válida para todos los $n$ .

O supongamos que probamos que $P(x)\implies P(x-1)$ . Entonces, desde $P(0)$ podríamos deducir $P(n)$ para cualquier $n$ . Pero aquí estás demostrando implícitamente que si $P(-n)$ se mantiene entonces $P(-(n+1))$ se mantiene y así se demuestra que $P(-n)$ es válida para todo lo que es positivo $n$ .

Answer 5

Prueba por inducción "funciona" porque el paso inductivo es :

para cualquier $n$ , si $P(n)$ se mantiene, entonces $P(n+1)$ se mantiene.

La característica clave aquí es que para cualquier $n$ tenemos un sucesor : $n+1$ .

Si nos trasladamos, por ejemplo, a racional números con la ordenación "habitual", no tenemos sucesor; lo que nosotros el sucesor de $k + \frac 1 2$ ? ¿Es así? $k+1$ ? ¿Por qué no? $k + \frac 3 4$ ?

---

Ver Inducción matemática :

La inducción matemática es una técnica de demostración matemática, más comúnmente utilizada para establecer un enunciado dado para todos los números naturales, aunque puede utilizarse para demostrar enunciados sobre cualquier conjunto bien ordenado.

Así, para aplicar, por ejemplo, a racionales tiene que confiar en el ordenación de $\mathbb Q$ y esto no es $\le$ .