B.6: Relaciones y Funciones

Última actualización
Guardar como PDF

Page ID: 103550

$ \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}}$

Cuando hemos definido un conjunto de objetos (como los números naturales o los términos agradables) inductivamente, también podemos definir relaciones sobre estos objetos por inducción. Por ejemplo, considere la siguiente idea: un término agradable$t_1$ es un subtérmino de un término agradable$t_2$ si ocurre como parte de él. Usemos un símbolo para ello:$t_1 \sqsubseteq t_2$. Cada término agradable es un subtérmino en sí mismo, por supuesto:$t \sqsubseteq t$. Podemos dar una definición inductiva de esta relación de la siguiente manera:

Definición$\PageIndex{1}$

La relación de un término agradable$t_1$ siendo un subtérmino de$t_2$,$t_1 \sqsubseteq t_2$, se define por inducción de la$t_2$ siguiente manera:

Si$t_2$ es una letra, entonces$t_1 \sqsubseteq t_2$ iff$t_1 = t_2$.
Si$t_2$ es$[s_1 \circ s_2]$, entonces$t_1 \sqsubseteq t_2$ iff$t = t_2$,$t_1 \sqsubseteq s_1$, o$t_1 \sqsubseteq s_2$.

Esta definición, por ejemplo, nos lo dirá$\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]$. Para (2) dice que$\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]$ iff$\mathrm{a} = [\mathrm{b} \circ \mathrm{a}]$, o$\mathrm{a} \sqsubseteq b$, o$\mathrm{a} \sqsubseteq \mathrm{a}$. Los dos primeros son falsos:$\mathrm{a}$ claramente no es idéntico a$[\mathrm{b} \circ \mathrm{a}]$, y por (1),$\mathrm{a} \sqsubseteq \mathrm{b}$ iff$\mathrm{a} = \mathrm{b}$, que también es falso. Sin embargo, también por (1),$\mathrm{a} \sqsubseteq \mathrm{a}$ iff$\mathrm{a} = \mathrm{a}$, lo cual es cierto.

Es importante señalar que el éxito de esta definición depende de un hecho que aún no hemos probado: cada término agradable$t$ es o una letra por sí mismo, o hay términos agradables determinados de manera única$s_1$ y$s_2$ tal que $t = [s_1 \circ s_2]$. “Singularmente determinado” aquí significa$t = [s_1 \circ s_2]$ que si no es también$= [r_1 \circ r_2]$ con$s_1 \neq r_1$ o$s_2 \neq r_2$. Si este fuera el caso, entonces la cláusula (2) puede entrar en conflicto consigo misma: leyendo$t_2$ como$[s_1 \circ s_2]$ podríamos conseguir$t_1 \sqsubseteq t_2$, pero si$[r_1 \circ r_2]$ leemos$t_2$ como podríamos llegar no$t_1 \sqsubseteq t_2$. Antes de demostrar que esto no puede suceder, veamos un ejemplo donde puede suceder.

Definición$\PageIndex{2}$

Definir términos sin corchete inductivamente por

Cada letra es un término sin corchete.
Si$s_1$ y$s_2$ son términos sin corchete, entonces$s_1 \circ s_2$ es un término sin corchete.
Nada más es un término sin corchete.

Los términos sin corchete son, por ejemplo$\mathrm{a}$,,$\mathrm{b} \circ \mathrm{d}$,$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$. Ahora bien, si definimos “subtérmino” para términos sin corchete de la manera que lo hicimos anteriormente, la segunda cláusula diría

Si$t_2 = s_1 \circ s_2$, entonces$t_1 \sqsubseteq t_2$ iff$t_1 = t_2$,$t_1 \sqsubseteq s_1$, o$t_1 \sqsubseteq s_2$.

Ahora$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$ es de la forma$s_1 \circ s_2$ con

\[s_1 = \mathrm{b} \quad\text{ and }\quad s_2 = \mathrm{a} \circ \mathrm{b}.\nonumber\]

También es de la forma$r_1 \circ r_2$ con

\[r_1 = \mathrm{b} \circ \mathrm{a} \quad\text{ and }\quad r_2 = \mathrm{b}.\nonumber\]

Ahora es$\mathrm{a} \circ \mathrm{b}$ un subtérmino de$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$? La respuesta es sí si vamos por la primera lectura, y no si vamos por la segunda.

La propiedad de que la forma en que se construye un término agradable a partir de otros términos agradables es única se llama legibilidad única. Dado que las definiciones inductivas de relaciones para tales objetos definidos inductivamente son importantes, tenemos que demostrar que se mantiene.

Proposición$\PageIndex{1}$

Supongamos que$t$ es un término agradable. Entonces o$t$ es una letra por sí misma, o hay términos agradables singularmente determinados$s_1$,$s_2$ tales que$t = [s_1 \circ s_2]$.

Comprobante. Si$t$ es una carta por sí misma, se cumple la condición. Entonces$t$ asumamos que no es una carta por sí misma. Podemos decir por la definición inductiva que entonces$t$ debe ser de la forma$[s_1 \circ s_2]$ para algunos términos agradables$s_1$ y$s_2$. Queda por demostrar que estos están determinados de manera única, es decir, si$t = [r_1 \circ r_2]$, entonces$s_1 = r_1$ y$s_2 = r_2$.

Así que supongamos$t = [s_1 \circ s_2]$ y también$t = [r_1 \circ r_2]$ para buenos términos$s_1$,$s_2$,$r_1$,$r_2$. Tenemos que demostrar eso$s_1 = r_1$ y$s_2 = r_2$. Primero,$s_1$ y$r_1$ debe ser idéntico, pues de lo contrario uno es un segmento inicial propio del otro. Pero por la Proposición B.5.2, eso es imposible si$s_1$ y$r_1$ son ambos términos agradables. Pero si$s_1 = r_1$, entonces claramente también$s_2 = r_2$. ◻

También podemos definir funciones inductivamente: por ejemplo, podemos definir la función$f$ que mapea cualquier término agradable a la profundidad máxima de anidado$[\dots]$ en él de la siguiente manera:

Definición$\PageIndex{3}$

La profundidad de un término agradable,$f(t)$, se define inductivamente de la siguiente manera:\[f(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(f(s), f(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

Por ejemplo\[\begin{aligned} f([\mathrm{a} \circ \mathrm{b}]) & = \max(f(\mathrm{a}),f(\mathrm{b})) + 1 = \\ &= \max(0, 0) + 1 = 1, \text{ and}\\ f([[\mathrm{a} \circ \mathrm{b}] \circ \mathrm{c}]) & = \max(f([\mathrm{a} \circ \mathrm{b}]), f(\mathrm{c})) + 1 = \\ & = \max(1,0) + 1 = 2.\end{aligned}\]

Aquí, por supuesto, asumimos que$s_1$$s_2$ son términos agradables, y hacemos uso del hecho de que cada término agradable es una letra o de la forma$[s_1 \circ s_2]$. Nuevamente es importante que pueda ser de esta forma de una sola manera. Para ver por qué, consideremos de nuevo los términos sin corchete que definimos anteriormente. La “definición” correspondiente sería:

\[g(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(g(s), g(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

Consideremos ahora el término sin corchete$\mathrm{a} \circ \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}$. Se puede leer de más de una manera, por ejemplo, como$s_1 \circ s_2$ con

\[s_1 = \mathrm{a} \quad\text{ and }\quad s_2 = \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}, \nonumber\]

o como$r_1 \circ r_2$ con

\[r_1 = \mathrm{a} \circ b \quad\text{ and }\quad r_2 = \mathrm{c} \circ \mathrm{d}.\nonumber\]

Calcular de$g$ acuerdo a la primera forma de lectura que daría

\ [\ begin {alineado} g (s_1\ circ s_2) & =\ max (g (\ mathrm {a}), g (\ mathrm {b}\ circ\ mathrm {c}\ circ\ mathrm {d})) + 1 =\\
& =\ max (0,2) + 1 = 3\ end {alineado}\]

mientras que según la otra lectura obtenemos

\ [\ begin {alineado} g (r_1\ circ r_2) & =\ max (g (\ mathrm {a}\ circ\ mathrm {b}), g (\ mathrm {c}\ circ\ mathrm {d})) + 1=\\
& =\ max (1,1) + 1 = 2\ end {alineado}\]

Pero una función siempre debe producir un valor único; así que nuestra “definición” de$g$ no define una función en absoluto.

Problema$\PageIndex{1}$

Dar una definición inductiva de la función$l$, donde$l(t)$ está el número de símbolos en el término agradable$t$.

Problema$\PageIndex{2}$

Demostrar por inducción estructural en términos agradables$t$ que$f(t) < l(t)$ (donde$l(t)$ está el número de símbolos en$t$ y$f(t)$ es la profundidad de$t$ como se define en Definición$\PageIndex{3}$).