Prove that every $L$-term has an odd number of symbols

241 Views Asked by At

We're talking about first-order logic.

Assume that we have $3$ symbols in a language $L$:

$o$ which is a constant symbol, $f$ which is a function which takes $2$ variables as input and $g$ which is another function which takes $4$ variables as its input.

By induction on the complexity of $L$-terms, Prove that every $L$-term has an odd number of symbols.

Note : I don't understand the part that talks about odd number of symbols. I also don't know what does "complexity of $L$-terms" mean. Actually, its been a while since i had "logic class" and i don't remember how we proved such these things. Now, I'm facing this question and i don't know how to solve it.

1

There are 1 best solutions below

2
On BEST ANSWER

Hint

You have to use the inductive definition of term :

every variable is a term;

every constant is a term;

if $t_1$ and $t_2$ are terms and $f$ is a binary function symbol, then $f(t_1,t_2)$ is a term.

The first two clauses of the definition are the base case and the third clause is the inductive step.