Me gustaría saber cómo aplicar inducción bien fundamentada . He encontrado dos definiciones que enumero a continuación, seguidas de la pregunta.
(1) Una relación binaria $\prec$ es fundado si no hay cadenas descendentes infinitas. Un cadena descendente infinita es una secuencia infinita $a_0, a_1, \dotsc$ tal que $a_{i + 1} \prec a_i$ (va en orden inverso) para todos $i \geq 0$ .
(2) La inducción fundamentada dice que, para demostrar una propiedad $P$ se mantiene en un conjunto $A$ que tiene una relación binaria bien fundada $\prec$ es suficiente para demostrar que $P$ es válida para cualquier $a \in A$ siempre que $P$ se mantiene para $b \prec a$ .
El último párrafo no lo entiendo bien. Y estoy teniendo problemas para analizar el anidado múltiple $\Rightarrow$ bloques en la definición formal:
$$\forall a \in A.(\forall b \in A.b \prec a \Rightarrow P(b)) \Rightarrow P(a) \Rightarrow \forall a \in A.P(a)$$
Una alternativa de Wikipedia es igual de difícil de analizar:
(3) Si $x$ es un elemento de $X$ y $P(y)$ es cierto para todos los $y$ tal que $y R x$ entonces $P(x)$ también debe ser cierto.
$$\forall x\in X\,[(\forall y\in X\,(y\,R\,x\to P(y)))\to P(x)]\to \forall x\in X\,P(x)$$
Las preguntas son:
- Si se pudiera desglosar/analizar esa ecuación formal para explicar su significado.
- Y de la misma manera para ese párrafo (2), lo que significa que "es suficiente para probar que $P$ es válida para cualquier $a \in A$ siempre que $P$ se mantiene para $b \prec a$ "
Mi intento de entender la versión wiki es, para todos $x \in X$ entonces si [el primer gran bloque] es verdadero, entonces podemos decir para todos $x \in X$ , $P(x)$ es cierto. Así que eso es esencialmente decir que si esa gran parte es verdadera, entonces hemos demostrado nuestra propiedad $P(x)$ es verdadera para todo x. No estoy seguro de cómo es el caso, pero continuando...
Entonces el "primer gran bloque" está diciendo, si para todos $y \in X$ [el segundo gran bloque] es verdadero, entonces $P(x)$ es verdadero, para el $x$ estamos centrados en atm. Así que para todos $y \in X$ , $P(x)$ va a ser cierto si ese "segundo gran bloque" es cierto.
Por último, el "segundo gran bloque" dice que si $y$ precede a $x$ entonces $P(y)$ es cierto. Así que si $y$ viene antes que $x$ Entonces, por lo menos sabemos $P(y)$ es cierto. No estoy muy seguro de lo que esto significa (cómo sabemos $P(y)$ es verdadera).
Así que para resumir, si para todos $x$ que para todos los $y$ , si $y$ precede a $x$ entonces $P(y)$ es cierto, que si eso es cierto, entonces $P(x)$ es cierto, y si eso es cierto, entonces $P(x)$ es cierto para todos los $x$ .
No tengo ni idea de lo que estoy diciendo ahora mismo lol, me está costando entender esto y busco alguna orientación. Muchas gracias.
1 votos
La mejor medicina para ello es jugar con un pequeño ejemplo no trivial: Tomemos $\{a,b,c,d,e\}$ con la orden $a<c$ , $b<c$ , $c<e$ y $d<e$ . La orden es un pequeño árbol. La condición dentro del [] dice que si $P$ se mantiene para $a$ y $b$ , entonces debería ser válida para $c$ . Si, además, también es válido para $d$ entonces también debería valer para $e$ .