Subtérminos

Definamos a modo de ejemplo $ST(M)$ que dado un término $M$ calcula todos los subtérminos. Podemos pensarlo como todos los subárboles de $M$.

A continuación asumimos que $M$ y $N$ representan términos y $x$ un identificador.

$$\begin{aligned} \ST(x) &:= \{ x \}\\ \ST(\app{M}{N}) &:= \{ \app{M}{N} \} \cup \ST(M) \cup \ST(N)\\ \ST(\lam{x}{N}) &:= \{ \lam{x}{N} \} \cup \ST(N) \end{aligned}$$

Veamos algunos ejemplos:

$\ST(y) = \ldots$ $y$ El resultado debe ser un conjunto. $\{y\}$ $\{x\}$ $x$ no aparece en $y$. $\ST(\app{f}{x}) = \ldots$ $\{f, x\}$ $\{x, f\}$