*Definición *recurrente* vs. *inductiva

Question

Una vez tuve una discusión con un profesor mío, si la siguiente definición era una recursivo o inductivo definición:

Suponga que tiene una secuencia de números reales. Defina $a_0:=2$ y $a_{i+1}:=\frac{a_i a_{i-1}}{5}$ . (Por supuesto, esto es sólo un ejemplo y, como tal, sólo tiene carácter ilustrativo - también podría haber tomado como ejemplo una definición de alguna familia de conjuntos)

Afirmé que esta definición era recursivo ya que tenemos un $a_{i+1}$ y definirlo yendo "hacia abajo" y utilizar la palabra " inductivo " sólo como un adjetivo para la palabra "prueba", pero mi profesor insistió en que distinguiéramos entre estos tipos de definición y que esto era un definición inductiva ya que empezamos con $a_0$ y trabajar "hacia arriba".

Ahora, ¿hay alguien que pueda tener razón? Ya que a mí me parece que matemáticamente cada recursivo definición es también inductivo (sea cual sea el significado final de estas dos expresiones), ya que los métodos matemáticos utilizados para definirlas (es decir, las ecuaciones) son los mismos. (La Wikipedia también parece pensar que son lo mismo - pero confío más en una comunidad matemática sólida, es decir, en ustedes, que en la Wikipedia)

Y si hay una diferencia, quién tiene razón y qué es, si lo anterior es una recursivo definición, un inductivo definición (y viceversa)?

(Por favor, no me pidan que le pregunte de nuevo a mi profesor - o algo similar, ya que a menudo obtengo esta respuesta aquí, después de mencionar que esta pregunta fue el resultado de una discusión con algún miembro de la facultad - ya que nuestra discusión terminó con él diciendo que " definitivamente es inductivo, pero no puedo explicarlo ")

Answer 1

Tanto los términos "definición recursiva" como "definición inductiva" son comunes, y las diferencias entre los términos suelen ser tan insignificantes que cualquiera de ellos funcionará (por lo que no merece la pena perder el sueño). Algunas personas son muy quisquillosas a la hora de llamar a cada definición "inductiva" o "recursiva", lo cual es respetable. Pero no puedo pensar inmediatamente en un ejemplo en el que el cambio de una palabra a la otra cambie lo que ocurre en una definición concreta.

Mi mejor descripción es que la "definición inductiva" es más común cuando estamos definiendo un conjunto de objetos "de la nada", mientras que la "definición recursiva" es más común cuando estamos definiendo una función sobre una colección de objetos ya existente.

Una definición inductiva prototípica es la siguiente definición del conjunto de los números naturales:

1. El 0 es un número natural

2. Si $n$ es un número natural, también lo es $n$ + 1

3. Sólo los números obtenidos a partir de las reglas 1 y 2 son números naturales.

Aquí no tenemos ya un conjunto de números naturales, sino que estamos describiendo una determinada forma de caracterizar qué números son "números naturales".

Por otro lado, la siguiente definición de la función factorial suele llamarse "definición recursiva" $$ n! = \begin{cases} 1 & n = 0 \\ n \cdot (n-1)! & n > 0 \end{cases} $$

La definición inductiva de $\mathbb{N}$ que ya tenemos, es lo que justifica el uso de una definición recursiva para $n!$ . Toda definición inductiva conduce a un principio de inducción y a un método de definición de funciones por recursión.

Sí importa que, al definir $\mathbb{N}$ Hay que empezar por 0 y "trabajar". No funciona intentar definir el conjunto $\mathbb{N}$ diciendo que $n$ es un número natural si $n-1$ es un número natural. Pero una vez que tenemos una definición inductiva de $\mathbb{N}$ podemos aprovechar eso para otros fines.

Otras cosas que se pueden definir inductivamente son el conjunto de polinomios sobre un anillo, la colección de árboles finitos enraizados y la colección de conjuntos de Borel. Las definiciones inductivas son especialmente importantes en la informática, la lógica matemática y otras áreas relacionadas. Un aspecto adicional de las mismas es que suelen dar un conjunto de "términos" para los objetos que se describen. Por ejemplo, sabemos por la definición inductiva de $\mathbb{N}$ que todo número natural puede expresarse como una cadena finita de la forma $0 + 1 + 1 + \cdots 1$ (de cierta longitud).

Answer 2

Las definiciones recursivas son técnicamente irrestrictas, mientras que las inductivas deben tener normalmente un "principio de inducción" bien fundado que te permita realmente hacer inducción (en el sentido de prueba) sobre el objeto. Las definiciones recursivas no dan a priori definiciones inductivas, pero una definición inductiva es recursiva.

Answer 3

En realidad, la Wikipedia parece distinguir entre estas definiciones. La verdad es que nunca he oído hablar de "definición inductiva", pero intentaré hacerme a la idea:

Sin embargo, en tu ejemplo, básicamente parece que se piensa en la misma cosa de dos maneras diferentes:

Recursivo:

Para calcular $a_n$ , primero calcula $a_{n-1}$ y que entonces $a_n = 2a_{n-1}$ . Terminar cuando se llega a $a_0=1$ .

Inductivo:

Comience con $a_0=1$ . Ahora bien, si usted sabe $a_n$ se puede calcular $a_{n+1}$ por $a_{n+1}=2a_n$ .

Es más o menos lo mismo. Sin embargo, se puede pensar en casos en los que la definición recursiva es obvia pero la inductiva resulta extraña, concretamente cuando se producen elecciones: Consideremos los tiempos de parada del Secuencia de Collatz

Para calcular $s_n$ para $n\neq 1$ , computa $$ s_n = 1+s_{f(n)} \text{ where } f(n) = \begin{cases} \frac n 2&,n \text{ even} \\ 3n+1&, n \text{ odd} \end{cases} $$ Terminar con $s_1=1$ .

Ahora intenta dar una bonita definición inductiva ;)

En otros contextos, el enfoque inductivo se siente más natural

Si A es un término válido b es una variable, entonces $\lambda b . T$ es un término válido.

Sin embargo, no me molestaría en distinguirlo, ya que se entenderá de todos modos. En el caso de la secuencia, lo que queremos decir en realidad es

Dejemos que $a_n$ sea la única secuencia que satisface la ecuación recursiva $$a_n = 2a_{n-1}, a_0=1 $$

Nadie llamaría a esto un ecuación inductiva ¿verdad?

Answer 4

Tenga en cuenta que en la programación informática estos términos tienen un significado estricto relacionado con la terminación de los programas.

Es posible definir inductivamente la suma de una lista:

 sum([]) = 0
 sum([H|T]) = H + sum(T)

En este caso, la lista disminuye constantemente su longitud, por lo que sabemos que terminará. Sin embargo, para una lista infinita como:

 helper(N) = [N | helper(N + 1)]
 nats = helper(0)
 nats = [0, 1, 2, 3, 4, 5...

tal definición inductiva no terminará.

Se podría definir una lista como:

 List(a) = unit ∨ (a ∧ List(a))

Leído como caso base de un unit tipo que tiene un habitante o un par del tipo a y el resto de la lista.

Una forma de abordar esto es distinguir entre datos finitos y posiblemente infinitos con las funciones de ayuda:

μ(f) = ∀a. (f(a) → a) → a
ν(f) = ∃a. a ∧ (a → f a)

Sin embargo, este tipo de codificaciones no ofrecen una recursión dependiente, pero son más sencillas que la historia completa de los endofunctores polinómicos.

Y una lista finita se definiría como List(a) = μ(λrest. unit ∨ (a ∧ rest)) .

La lista finita se convierte entonces en un programa que permite aplicarle funciones para reducirla a un valor menor.

La lista infinita se convierte entonces en un programa que comienza con una semilla y una función para pasar al siguiente paso que puede utilizarse para generar un flujo infinito de valores.

Así que tu ejemplo es inherentemente una definición inductiva porque no funciona con un tipo de datos infinito.

Consideremos los números naturales definidos como:

 nat = zero or succ(nat)

Entonces, ¿qué pasa con el siguiente número?

 omega = succ(omega)

Su algoritmo hará un bucle eterno.

La mayoría de las veces en matemáticas la gente utiliza definiciones inductivas. Pero se diferencian específicamente de otros algoritmos recursivos en que sólo pueden funcionar con datos finitos.

Ahora te preguntarás qué tipo de algoritmos "coinductivos" pueden funcionar en una lista infinita.

Bien, por ejemplo, es posible incrementar cada miembro individual de una lista. Recuerda que la definición coinductiva define la lista infinita como un par así:

 inc((seed, succ)) = ((n, succ, seed), helper)
 helper((n, succ, seed)) = (n + 1, ((succ(seed), succ, seed), helper))

Dicho esto, yo no diría que estas son las definiciones de los términos inductivo y coinductivo en todos los casos. Se trata de una jerga propia de los algoritmos.

Ver también https://en.wikipedia.org/wiki/Coinduction

Answer 5

Aquí está mi inductivo definición de la cardinalidad de un conjunto finito (ya que en mi opinión, los conjuntos finitos se construyen añadiendo elementos empezando por el conjunto vacío):

$|\emptyset| = 0 $ .

$|A \cup {x}| = \begin{cases} x \in A &\implies |A|\\ x \not\in A &\implies |A|+1\\ \end{cases} $