I am trying to solve the following problem, please help me to complete the proof:

I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of f functional symbols and the number $p_g$ of g functional symbols in term $t$ .

$f$ is an unary func symbol, $g$ is ternary one.

My induction assumption is that this relation is $p_c(t) = 2p_g(t) +0p_f(t) $, where $p_g$ and $p_c$ show num of corresponding symbols in the term $t $ respectively.

Having this, base:

$p_c(x)=0$, where $x$ is some variable. Assumption holds


let $k_i \in \{k_a, k_b, k_c\}$ are some terms. $p_c(k_i) = 2p_g(k_i)$

Then $p_c(k_{i+1}) = p_c(f(k_i)) = 0 + 2 p_g(k_i)$ or

$p_c(k_{i+1}) = p_c(g(k_a, k_b, k_c)) = 2 + p_c(k_a)+ p_c(k_b)+ p_c(k_c) = 2 + 2p_g(k_a)+ 2p_g(k_b)+ 2p_g(k_c)$

what should I write next?

  • $\begingroup$ Better late than never ... $\endgroup$ – Bram28 Nov 8 '16 at 18:34

Beforehand, I would state the claim that you are trying to prove simply as $p_c(t) = 2p_g(t)$

In the Step:

First say that you need to show $p_c(k_{i+1}) = 2p_g(k_{i+1})$

In the case where $k_{i+1} = f(k_i)$, the number of g functional symbols in $k_{i+1}$ equals the number of g functional symbols in $k_i$, and so $p_c(k_{i+1}) = p_c(k_i) = 2p_g(k_i) = 2p_g(k_{i+1})$

In the case where $k_{i+1} = g(k_a, k_b, k_c)$, the number of g functional symbols in $k_{i+1}$ is 1 + all the g functional symbols in the other terms, i.e. $p_g(k_{i+1}) = p_g(k_a) + p_g(k_b) + p_g(k_c) + 1$. So then: $p_c(k_{i+1}) = p_c(k_a) + p_c(k_b) + p_c(k_c) + 2 =$ (by inductive hypothesis) $= 2p_g(k_a) + 2p_g(k_b) + 2p_g(k_c) + 2 = 2(p_g(k_a) + p_g(k_b) + p_g(k_c) + 1) = 2p_g(k_{i+1})$

So yes, in both cases $p_c(k_{i+1}) = 2p_g(k_{i+1})$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.