Inducción sobre una fórmula bien formada (wff)

Question

Sea una fórmula bien formada (wff); sea c el número de lugares en los que los símbolos conectivos binarios (, , , ) aparecen en ; sea s el número de lugares en los que los símbolos de la oración aparecen en . (Por ejemplo, si es (A (¬A)) entonces c = 1 y s = 2). Demuestre mediante el principio de inducción que s = c + 1.

No estoy seguro de cómo aplicar la inducción en este caso. ¿El caso base sería c = 1 y s = 2? ¿A partir de ahí, a dónde iría?

Answer 1

Procedemos por inducción en $c \in \{0,1,2,...\}$ .

Caso base: Supongamos que $c=0$ . Entonces, como no hay conectivos binarios, $\alpha$ debe ser un literal (es un átomo o su negación). Por lo tanto, tenemos $s = 1 = 0 + 1 = c + 1$ , según se desee.

Hipótesis de inducción: Supongamos que la afirmación es válida para todos los $c \in \{0,1,...,k\}$ .

Queda por demostrar que la afirmación es cierta para $c=k+1$ . Supongamos que $\alpha$ tiene $k+1$ símbolos conectivos binarios. Entonces podemos escribir $\alpha = \beta \circ \gamma$ , donde:

• El símbolo $\circ$ es un marcador de posición para una conectiva binaria (es decir, $\circ\in \{\land, \lor, \to, \leftrightarrow\}$ ).
• $\beta$ es un wff que contiene $x$ conectivos binarios, donde $x \in \{0,1,...,k\}$ .
• $\gamma$ es un wff que contiene $y$ conectivos binarios, donde $y \in \{0,1,...,k\}$ .
• $x+y=k$

Así, por la hipótesis de inducción, hay $x+1$ lugares en los que aparecen los símbolos de la frase en $\beta$ y $y+1$ lugares en los que aparecen los símbolos de la frase en $\gamma$ . Pero entonces debe haber: $$ s=(x+1)+(y+1) = (x+y)+2=k+2 = (k+1)+1=c+1 $$ lugares en los que aparecen los símbolos de la frase en $\alpha$ como se desee. Esto completa la inducción.