Saltar al contenido principal
Library homepage
 
LibreTexts Español

B.4: Definiciones inductivas

  • Page ID
    103536
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    En la lógica muy a menudo definimos tipos de objetos inductivamente, es decir, especificando reglas para lo que cuenta como un objeto del tipo a definir que explican cómo obtener nuevos objetos de ese tipo a partir de objetos antiguos de ese tipo. Por ejemplo, a menudo definimos clases especiales de secuencias de símbolos, como los términos y fórmulas de un lenguaje, por inducción. Para un ejemplo simple, considere cadenas consistentes en letras\(\mathrm{a}\),,\(\mathrm{b}\),\(\mathrm{c}\)\(\mathrm{d}\), el símbolo\(\circ\) y corchetes\([\) y\(]\), como “\([[\mathrm{c} \circ \mathrm{d}][\)”,” \([\mathrm{a}[]\circ]\)”, “\(\mathrm{a}\)” o “\([[\mathrm{a} \circ \mathrm{b}]\circ \mathrm{d}]\)”. Probablemente sientas que hay algo “mal” con las dos primeras cadenas: los corchetes no “equilibran” en absoluto en la primera, y podrías sentir que el “\(\circ\)” debería “conectar” expresiones que a su vez tienen sentido. La tercera y cuarta cuerda se ven mejor: por cada “\([\)” hay un cierre “\(]\)” (si hay alguna), y para cualquiera\(\circ\) podemos encontrar expresiones “bonitas” a cada lado, rodeadas de un par de paréntesis.

    Nos gustaría especificar con precisión lo que cuenta como un “término agradable”. En primer lugar, cada letra por sí misma es agradable. Cualquier cosa que no sea solo una carta por sí misma debe ser de la forma “\([t \circ s]\)” donde\(s\) y\(t\) son ellos mismos agradables. Por el contrario, si\(t\) y\(s\) son agradables, entonces podemos formar un nuevo término agradable poniendo un\(\circ\) entre ellos y rodearlos por un par de corchetes. Podríamos usar estas operaciones para definir el conjunto de términos agradables. Esta es una definición inductiva.

    Definición\(\PageIndex{1}\): Nice terms

    El conjunto de términos agradables se define inductivamente de la siguiente manera:

    1. Cualquier letra\(\mathrm{a}\),\(\mathrm{b}\),\(\mathrm{c}\),\(\mathrm{d}\) es un término agradable.

    2. Si\(s_1\) y\(s_2\) son términos agradables, entonces también lo es\([s_1 \circ s_2]\).

    3. Nada más es un término agradable.

    Esta definición nos dice que algo cuenta como un término agradable si se puede construir de acuerdo con las dos condiciones (1) y (2) en algún número finito de pasos. En el primer paso, construimos todos los términos agradables simplemente consistentes en letras por sí mismos, es decir,\[\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\nonumber\] En el segundo paso, aplicamos (2) a los términos que hemos construido. Obtendremos\[[\mathrm{a} \circ \mathrm{a}], [\mathrm{a} \circ \mathrm{b}], [\mathrm{b} \circ \mathrm{a}], \dots, [\mathrm{d} \circ \mathrm{d}]\nonumber\] para todas las combinaciones de dos letras. En el tercer paso, aplicamos (2) de nuevo, a cualesquiera dos términos agradables que hayamos construido hasta ahora. Obtenemos un nuevo término agradable como\([\mathrm{a} \circ [\mathrm{a} \circ \mathrm{a}]]\) —donde\(t\) es\(\mathrm{a}\) del paso 1 y\(s\) es\([\mathrm{a} \circ \mathrm{a}]\) del paso 2— y\([[\mathrm{b} \circ \mathrm{c}] \circ [\mathrm{d} \circ \mathrm{b}]]\) construido a partir de los dos términos\([\mathrm{b} \circ \mathrm{c}]\) y\([\mathrm{d} \circ \mathrm{b}]\) del paso 2. Y así sucesivamente. La cláusula (3) descarta que cualquier cosa que no se construya de esta manera se cuela en el conjunto de términos agradables.

    Tenga en cuenta que aún no hemos demostrado que cada secuencia de símbolos que “se siente” bien sea agradable de acuerdo con esta definición. No obstante, debe quedar claro que todo lo que podemos construir hace de hecho “sentirse bien”: los brackets están equilibrados, y\(\circ\) conecta partes que son bonitas en sí mismas.

    La característica clave de las definiciones inductivas es que si quieres probar algo sobre todos los términos agradables, la definición te dice qué casos debes considerar. Por ejemplo, si te dicen que\(t\) es un término agradable, la definición inductiva te dice cómo\(t\) puede verse:\(t\) puede ser una letra, o puede ser\([s_1 \circ s_2]\) para algún par de términos agradables\(s_1\) y\(s_2\) . Por la cláusula (3), esas son las únicas posibilidades.

    Al probar afirmaciones sobre todo un conjunto definido inductivamente, la fuerte forma de inducción se vuelve particularmente importante. Por ejemplo, supongamos que queremos demostrar que por cada buen término de duración\(n\), el número de\([\) en él es\(< n/2\). Esto puede verse como una afirmación sobre todos\(n\): para cada\(n\), el número de\([\) en cualquier buen término de duración\(n\) es\(< n/2\).

    Proposición\(\PageIndex{1}\)

    Para cualquiera\(n\), el número de\([\) en un buen término de duración\(n\) es\(< n/2\).

    Comprobante. Para probar este resultado por inducción (fuerte), tenemos que demostrar que la siguiente afirmación condicional es cierta:

    Si por cada\(l < k\), cualquier buen término de duración\(l\) tiene\(l/2\)\([\)'s, entonces cualquier buen término de duración\(k\) tiene\(k/2\)\([\)'s.

    Para mostrar este condicional, supongamos que su antecedente es verdadero, es decir, asumir que para cualquier\(l<k\), términos agradables de longitud\(l\)\(< l/2\)\([\) contiene's. Llamamos a esta suposición la hipótesis inductiva. Queremos mostrar lo mismo es cierto para buenos términos de longitud\(k\).

    Entonces supongamos que\(t\) es un buen término de duración\(k\). Debido a que los términos agradables se definen inductivamente, tenemos dos casos: (1)\(t\) es una letra por sí misma, o (2)\(t\) es\([s_1 \circ s_2]\) para algunos términos agradables\(s_1\) y\(s_2\).

    1. \(t\)es una letra. Entonces\(k = 1\), y el número de\([\) in\(t\) es\(0\). Ya que\(0 < 1/2\), el reclamo se sostiene.

    2. \(t\)es\([s_1 \circ s_2]\) para algunos términos agradables\(s_1\) y\(s_2\). Vamos a\(l_1\) ser la longitud de\(s_1\) y\(l_2\) ser la longitud de\(s_2\). Entonces la longitud\(k\) de\(t\) es\(l_1+l_2+3\) (las longitudes de\(s_1\) y\(s_2\) más tres símbolos\([\),\(\circ\),\(]\)). Ya que siempre\(l_1+l_2+3\) es mayor que\(l_1\),\(l_1 < k\). De igual manera,\(l_2 < n\). Eso significa que la hipótesis de inducción se aplica a los términos\(s_1\) y\(s_2\): el número\(m_1\) de\([\) in\(s_1\) es\(< l_1/2\), y el número\(m_2\) de\([\) en\(s_2\) es\(< l_2/2\).

      El número de\([\) in\(t\) es el número de\([\) in\(s_1\), más el número de\([\) in\(s_2\), más\(1\), es decir, es\(m_1 + m_2 + 1\). Desde\(m_1 < l_1/2\) y\(m_2 < l_2/2\) tenemos:\[m_1 + m_2 + 1 < \frac{l_1}{2} + \frac{l_2}{2} + 1 = \frac{l_1+l_2+2}{2} < \frac{l_1+l-2+3}{2} = k/2.\nonumber\]

    En cada caso, hemos demostrado que el número de\([\) in\(t\) es\(< k/2\) (sobre la base de la hipótesis inductiva). Por fuerte inducción, la proposición sigue. ◻

    Problema\(\PageIndex{1}\)

    Definir el conjunto de términos de supernice

    1. Cualquier letra\(\mathrm{a}\),\(\mathrm{b}\),\(\mathrm{c}\),\(\mathrm{d}\) es un término superagradable.

    2. Si\(s\) es un término superagradable, entonces también lo es\([s]\).

    3. Si\(s_1\) y\(s_2\) son términos superagradables, entonces también lo es\([s_1 \circ s_2]\).

    4. Nada más es un término superagradable.

    Demostrar que el número de\([\) en un término superagradable\(t\) de duración\(n\) es\(\le n/2 +1\).


    This page titled B.4: Definiciones inductivas is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .