11.4: Definiciones inductivas
- Page ID
- 118034
Podemos utilizar la idea de definiciones recursivas de una manera más general.
un método para definir una colección de objetos, donde cada objeto de la colección se puede construir a partir de objetos asumidos o ya conocidos por existir en la colección
una instrucción que especifica algunos objetos iniciales específicos que pertenecen al conjunto definido inductivamente
una declaración que describe un medio para determinar nuevos objetos en el conjunto definido inductivamente a partir de los que ya se sabe que pertenecen
una declaración de que ningún objeto pertenece al conjunto definido inductivamente a menos que se obtenga de un número finito de aplicaciones de las cláusulas base e inductivas
Definamos un conjunto\(\mathscr{L}\) con la siguiente definición inductiva.
Cláusula base.
Por cada variable\(m \in \mathbb{N}\text{,}\) de sentencia\(p_m\) pertenece a\(\mathscr{L}\text{.}\)
Cláusula inductiva.
Dadas declaraciones\(A,B \in \mathscr{L}\text{,}\) las declaraciones
\ begin {equation*}\ neg A,\ quad A\ land B,\ quad A\ lor B,\ quad A\ right tarrow B,\ quad A\ left trightarrow B\ end {equation*}
son también elementos de\(\mathscr{L}\text{.}\)
Cláusula limitante.
El conjunto\(\mathscr{L}\) no contiene ningún elemento excepto aquellos que pueden obtenerse a partir de un número finito de aplicaciones de las cláusulas base e inductivas.
Por ejemplo, la declaración lógica\(\neg p_2 \land (p_1 \rightarrow p_2)\) está en\(\mathscr{L}\) por la siguiente construcción.
\ begin {ecuación*} p_1, p_2\ in\ mathscr {L}\ quad\ Rightarrow\ quad\ neg p_2\ in\ mathscr {L},\;\; p_1\ fila derecha p_2\ in\ mathscr {L}\ quad\ Rightarrow\ quad\ neg p_2\ land (p_1\ fila derecha p_2)\ en\ mathscr {L}\ end {ecuación*}
Suponemos que\(\emptyset\) existe un conjunto vacío. Definamos un conjunto\(N\) inductivamente.
Cláusula base.
El conjunto vacío\(\emptyset\) es un elemento de\(N\text{.}\)
Cláusula inductiva.
Si\(X\) es un elemento de\(N\) y\(X\) en sí mismo es un conjunto, entonces el conjunto también\(X^+ = X \cup \{X\}\) es un elemento de\(N\text{.}\)
Cláusula limitante.
El conjunto\(N\) no contiene ningún otro elemento excepto aquellos que pueden obtenerse a partir de un número finito de aplicaciones de las cláusulas base e inductivas.
Obsérvese que las tres cláusulas en conjunto implican que cada elemento de\(N\) debe ser un conjunto, por lo que la parte “y\(X\) en sí misma es un conjunto” de la cláusula inductiva es superflua.
Dado que la cláusula base involucra un solo elemento inicial de\(N\) y la cláusula inductiva produce un nuevo elemento de\(N\) a partir de un solo elemento antiguo de\(N\text{,}\) podemos llevar a cabo explícitamente la construcción paso a paso. Ahora definimos los números naturales para que sean los elementos en esta construcción:
\ begin {alinear*} 0 & =\ juego vacío,\\ 1 & = 0^+ = 0\ taza\ {0\} =\ juego vacío\ taza\ {0\} =\ {0\}\ ne 0,\\ 2 & = 1^+ = 1\ taza\ {1\} =\ {0\} =\ {0\}\ taza\ {1\} =\ {0, 1\}\ ne 0,1,\\ 3 & = 2^+ = 2\ taza\ {2\} =\ {0, 1\}\ copa\ {2\} =\ {0, 1, 2\}\ ne 0,1,2\\ &\;\;\ vdots\ end {alinear*}
Normalmente escribimos\(\mathbb{N}\) para este conjunto en lugar de\(N\text{.}\)
Tenga en cuenta que el número de elementos en cada número natural (como conjunto) es igual al número definido por ese conjunto, y que cada número natural\(m\) se define como el conjunto que hemos llamado previamente\(\mathbb{N}_{<m}\text{.}\)
Bonificación
En Ejemplo\(\PageIndex{2}\) anterior, construimos el conjunto\(\mathbb{N}\) inductivamente usando solo los axiomas de la teoría de conjuntos. Pero, ¿cómo hacemos aritmética con esta definición? Podemos definir la suma como una colección infinita de funciones definidas inductivamente: para cada una\(m \in \mathbb{N}\text{,}\) define una función de “suma con\(m\)” de la\(s_m: \mathbb{N} \rightarrow \mathbb{N}\) siguiente manera.
Cláusula base.
Set\(s_m(0) = m\text{.}\)
Cláusula inductiva.
Para\(n \in \mathbb{N}\) tal que ya\(s_m(n)\) está definido, establecer
Es decir, si\(s_m(n)\) se define y\(n^+\) es el siguiente número natural después\(n\) en la definición inductiva de\(\mathbb{N}\text{,}\) entonces define\(s_m(n^+)\) para ser el siguiente número natural después\(s_m(n)\text{.}\)
Entonces usamos los símbolos\(m + n\) para significar\(s_m(n)\text{.}\) En esta notación, se puede pensar en la cláusula inductiva anterior como diciendo que una vez que\(m+n\) se define, podemos definir\(m+(n+1)\) como\((m+n)+1\text{.}\)
Si estás aburrido un viernes o sábado por la noche, puedes probar lo siguiente usando la definición anterior de adición en\(\mathbb{N}\text{.}\)
- Demostrar que la adición en\(\mathbb{N}\) es:
- conmutativo:\(m+n = n+m\text{,}\) es decir,\(s_m(n) = s_n(m)\) para todos\(m,n \in \mathbb{N}\text{;}\) y
- asociativo:\((m+n)+\ell = m + (n+\ell)\text{,}\) es decir,\(s_{s_m(n)}(\ell) = s_m(s_n(\ell))\text{,}\) para todos\(m,n,\ell \in \mathbb{N}\text{.}\)
- Usa la idea de que cada entero positivo debe tener un negativo para definir\(\mathbb{Z}\) como un subconjunto del producto cartesiano\(\mathbb{N} \times \mathbb{N}\text{.}\) Luego define suma y resta en\(\mathbb{Z}\text{.}\)
- Pista.
-
Para definir\(\mathbb{Z}\text{,}\) primero elija una función uno a uno apropiada incrustada\(\mathbb{N}\)\(\mathbb{N} \times \mathbb{N}\) en de tal manera que luego le permitirá adjuntar un segundo dato adicional a cada número natural (es decir, un designador del signo del número).