Prueba por doble inducción sobre cadenas

Question

Esta era una pregunta de un trabajo presentado en mi curso de Lógica y Matemáticas para informática, y estoy realmente desconcertado como para llegar a demostrar esto por doble inducción:

Consideremos una cadena formada por uno o dígitos decimales (0-9). Suponga que inserta repetidamente un 0 a la derecha del el dígito situado más a la izquierda y, a continuación, sustituye esa cadena por otra de la misma longitud que representa el resultado de de restar uno a esa cadena.

es decir: empezando por la cadena 11 obtendrá lo siguiente: 11, 101, 100, 1000, 0999, 00999, 00998, etc.

Demostrar por doble inducción, que no no importa con qué cadena empieces al final obtendrás una cadena que contiene sólo 0's.

Esta cuestión parece bastante trivial a primera vista, sin embargo intentar demostrarla mediante doble inducción es otra cosa para mí. Tengo problemas para decidir cuáles serán las variables sobre las que aplicaré la inducción . Obviamente una de las dos variables será la cadena de entrada, pero ¿qué pasa con la otra? He pensado en usar longitud pero no veo en que puede ayudar eso. ¿Qué opináis vosotros?

Asumiendo que he encapsulado las variables, planeo proceder a probar esto de la siguiente manera dado para todo x e y en N. p(x,y):

Sea Q(x) = para todo y en N, p(x,y) Sea x sea arbitraria y supongamos que para todo i en N, i < x IMPLICA Q(i). Dejamos entonces que y en N sea arbitraria y supongamos que para todo j en N, j < y implica p(x,j).

A continuación utilizaré la hipótesis que para todo i y j, p(i,j) es cierto tal que (i < x) o (i = x y j < y).Luego procederé a la prueba.

¿Tiene sentido lógico esa estructura esquelética de la prueba? La doble inducción todavía es nueva para mí y no se ha tratado mucho en las clases, así que todavía me siento inseguro.

Supongo que tendría más sentido si usáramos inducción estructural en cada variable, sin embargo estamos restringidos a usar sólo inducción doble.

Lo siento por la larga pregunta, agradecería cualquier entrada y la ayuda y la perspicacia con respecto a esta cuestión o en la doble inducción en general como mi Google-fu parece estar quedando corto en la información de este último :(.

Answer 1

Sea $a$ sea el primer dígito de la cadena, y que $b$ sea el valor de los dígitos restantes. Demostremos que la es reductora con respecto al orden léxico de $\langle a,b\rangle$ que es una versión de interpretar tu frase "doble inducción".

En primer lugar, tenga en cuenta que la operación de insertar el $0$ a la derecha del dígito inicial no afecta al valor de $a$ ni $b$ .

A continuación, observe que si $b$ es todo cero menos $a$ no es $0$ entonces la operación terminará con $a$ reduciéndose, porque cuando restes uno, tendrás que pedir prestado a $a$ , reduciéndose así. Así, la operación resultará con una cadena con menor $\langle a,b\rangle$ en el léxico léxico.

Si $b$ no es todo cero, entonces la operación terminará con el $b$ valor siendo valor $1$ menos (a pesar de la extra $0$ ), por lo que se reducirá $\langle a,b\rangle$ en el orden léxico.

Dado que el orden léxico en $\mathbb{N}\times\mathbb{N}$ es un bien ordenado, se deduce que la operación debe llegar a todos $0$ s.

El argumento muestra que se puede insertar cualquier número de $0$ s, en lugar de uno solo $0$ en cada paso, aunque si inserta más, entonces tardará más en llegar al todo $0$ cadena, ya que cuando pidas prestado, obtendrás más $9$ s.