Inducción y Recursión. ¿Qué hace $C_n$ y cómo medir la longitud de una construcción?

Question

Hay algo que no entiendo, ¿puedes decirme, en la imagen, por qué el "árbol" es $C_5$ ? ¿Y cuál es su longitud? He estado leyendo mucho y no lo entiendo y tengo que resolver un problema del Enderton: "Supongamos que $C$ se genera a partir de un conjunto $B= \{a, b\}$ mediante la operación binaria $f$ y la operación unaria $g$ . Enumerar todos los miembros de $C_2$ . ¿Cuántos miembros podrían $C_3$ ¿tiene? $C_4$ ?"

¡Ayúdame con tu luz por favor! Muchas gracias de antemano

Tomado de Enderton's Mathematical introduction to Logic.

introduzca aquí la descripción de la imagen

Answer 1

Considere la secuencia $x_1 = b$ , $x_2 = f(x_1, x_1)$ , $x_3 = a$ , $x_4 = f(x_3, x_2)$ , $x_5 = g(x_4)$ . Refleja el cómputo descrito por el árbol y muestra que el término $g(f(a,f(b,b)))$ está en $C_5$ .

Para los términos en $C_2$ Su secuencia comienza por $x_1 = a$ o $x_1 = b$ y $x_2$ es uno de $x_2 = f(x_1, x_1)$ o $x_2 = g(x_1)$ . Esto le da el término $f(a,a)$ , $f(b,b)$ , $g(a)$ y $g(b)$ .

Sugerencia . Para los términos en $C_3$ En este caso, tienes el mismo primer paso, pero tienes otros dos posibles segundos pasos: $x_2 = a$ y $x_2 = b$ . Los posibles terceros pasos son $x_3 = f(x_1, x_1)$ , $x_3 = f(x_1, x_2)$ , $x_3 = f(x_2, x_1)$ , $x_3 = f(x_2, x_2)$ , $x_3 = g(x_1)$ y $x_3 = g(x_2)$ .