If $F$ is a function symbol with arity $2$, then is $F(x,F(x,F(x,x)))$ a term?

Question

Here $F$ is a function symbol with arity $2$.

The solutions say it is but I am not sure.

If $F$ has arity $2$, but the first $F$ on the outside contains three arguments: $x$, $F(x)$ and $F(x,x)$.

Answer 1

It can be useful to use lower-case letters : $f, g,\ldots$ for function symbols and upper-case letters : $P, R,\ldots$ for predicate symbols.

---

The first one is the recursive Defintion of term :

i) every (individual) variable : $x_1, x_2,\ldots$ is a term

ii) every constant : $c_1, c_2,\ldots$ is a term

iii) if $f_i^n$ is a function symbol with arity $n$ (i.e. an $n$-ary function symbol) and $t_1,\ldots,t_n$ are terms, then :

$f_i^n(t_1, \ldots, t_n)$ is a term.

In the last case, we have to take care of arity (the "exponent" $n$ of $f_i^n$); often it is left unspecified, because we can "read it" form the context.

In the language of arithmetic, $+$ (the "sum") and $\times$ (the "product") are both binary function symbols. In this cases, we usually "switch" form the "formal" way of writing : $+(x,y)$ (the "prefix" notation) to the "informal" one : $x+y$ (the "infix" notation).

A term denotes an "object" of the domain of discourse; thus, a function symbol allows us to build "complex" terms from already defined ones.

For example, $0+1$ (i.e. the "infomal" way of writing : $+(0,1)$) is a term built form the function symbol $+$ and the two individual constants $0,1$. The individual constants denote the corersponding nutural numbers : zero and one, and the "complex" term will denote the number one.

---

Having defined terms, we need the recursive Defintion of formula :

Note : in first-order logic, we usually use the binary symbol $=$ (identity) as a logical symbol.

i) if $t_1, t_2$ are terms, then $t_1=t_2$ is an atomic formula;

ii) if $R_i^n$ is a predicate symbol with arity $n$ and $t_1,\ldots,t_n$ are terms, then :

$R_i^n(t_1, \ldots, t_n)$ is an atomic formula.

Also in this case we have to take care of arity (the "exponent" $n$ of $R_i^n$); often it is left unspecified, because we can "read it" form the context.

iii) If $\varphi, \varphi_1, \varphi_2$ are formulae, then :

$\lnot \varphi, \varphi_1 \lor \varphi_2, \varphi_1 \land \varphi_2, \varphi_1 \rightarrow \varphi_2, \varphi_1 \leftrightarrow \varphi_2$ are formulae

iv) If $\varphi$ is a formula and $x$ is a variable, then :

$\exists x \varphi, \forall x \varphi$ are formulae.

Consider again the first-order language (with : $=$) of arithmetic, with individual constants : $0,1$, function symbols : $+, \times$ and (binary) predicate symbol : $<$ .

The following are examples of atomic formulae :

$x=x, 0=1, 0 < 1$.

The following are examples of formulae :

$\forall x (x=x), \lnot (0=1), \exists x (x < 1), \forall x (0 < x \lor 0 = x)$.

---

Consider now your examples :

a) $f(x,f(x,f(x,x)))$

and use the binary function symbol $+$ in place of $f$. We get :

$+(x,+(x,+(x,x)))$, i.e. $(x + (x + (x + x)))$.

It is a term, because it satisfy the definition of term above : $x+x$ is a term (built up from the binary function symbol $+$ and two terms, two occurrences of the variable $x$; thus also $x + (x + x)$ is a term, and so on..

Consider now :

b) $f(x,y)=x$ where $f$ is a function symbol with arity $2$,

and use again the the binary function symbol $<$ in place of $f$. We get :

$+(x,y)=x$, i.e. $(x+y)=x$.

$x$ is a term, and also $x+y$ is; thus, according to the above definition of formula, it is an atomic formula, because it is built up with the binary symbol $=$ for identity and two terms.

Finally :

c) If $P$ is a predicate symbol with arity $1$, according to the above definition of formula, $P(x)$ is an atomic formula ($x$ is a term).

In the language of arithmetic, we can define a (unary) predicate $Even$ such that $Even(n)$ holds if $n$ is an even number (but in this case, the predicate $Even$ is "formally" an abbreviation for a "complex" formula like : $\exists z (x=z \times (1+1))$, and thus $Even(x)$ is a formula, but it is not an atomic one).

---

Next we have the Definition of the set $Sub(\varphi)$ of subformulae of a formula $\varphi$ :

i) if $\varphi$ is atomic, then the set of subformuale of $\varphi$ is $Sub(\varphi) = \{ \varphi \}$;

ii) $Sub(\varphi_1 \lor \varphi_2) = Sub(\varphi_1) \cup Sub(\varphi_2) \cup \{ \varphi_1 \lor \varphi_2 \}$, and the same for the other binary connectives;

iii) $Sub(\lnot \varphi) = Sub(\varphi) \cup \{ \lnot \varphi \}$;

iv) $Sub(\forall x \varphi) = Sub(\varphi) \cup \{ \forall x \varphi \}$, and the same for $\exists$.

We say that $\psi$ is a subformula of $\varphi$ if $\psi \in Sub(\varphi)$.

An example in the language of arithmetic can be :

$\forall x (0 = x \lor 0 < x)$;

its subformulae are $\forall x (0 = x \lor 0 < x)$ itself, $(0 = x \lor 0 < x), 0 = x$ and $0 < x$.

Answer 2

(This should be a comment, but I can't still comment)

The first F on the outside contains TWO arguments: x and F(x,F(x,x)).

The first F of F(x,F(x),F(x,x)) would contain three arguments, but you would not be allowed to write that because, the second F would have one argument, and the third, two arguments. But either F has one, two or three arguments. F(x,G(x),H(x,x)) would work.

Answer 3

It is a term. The first argument of the outermost $F$ contains the two arguments $x$ and $F(x,F(x,x))$.