Languages and Formulas — Foundations of Mathematics

Definition 2.1.1. A language $\mathcal{L}$ is given by the following data:

a set of function symbols $\mathcal{F}$ and positive integer $$n_f$$ for each $f\in {\mathcal{F}};$
a set of relation symbols $\mathcal{R}$ and positive integer $$n_R$$ for each $R\in {\mathcal{R}};$
a set of constant symbols $\mathcal{C}.$

Definition 2.1.2. The set of $$\mathcal L$-$ terms is the smallest set $\mathcal T$ such that

for each constant symbol $c\in \mathcal C,$ we have $$c\in \mathcal T$;$
each variable symbol $v_i\in \mathcal T$ for $i=1,2,\dots;$ and
if $t_1,\dots,t_{n_f}\in \mathcal T$ and $f\in \mathcal F,$ then $f(t_1,\dots,t_{n_f})\in \mathcal T.$

Example 2.1.3. Let $\mathcal L_r=\lbrace +,-,\cdot,0,1\rbrace$ be the language of rings, where $+,-,\cdot$ are binary function symbols and $$0,1$$ are constant symbols. Then $\cdot(v_1, -(v_3,1))$ and $$+(1, +(1, 1))$$ are $$\mathcal L_r$-$ terms.

Definition 2.1.4. We say that $\phi$ is an atomic $$\mathcal L$-$ formula if $\phi$ is either

$$t_1=t_2,$$ where $$t_1$$ and $$t_2$$ are terms, or
$R(t_1,\dots,t_{n_R}),$ where $R\in \mathcal R$ and $t_1,\dots,t_{n_R}$ are terms.

Definition 2.1.5. The set of $$\mathcal L$-$ formulas is the smallest set $\mathcal W$ containing the atomic formulas such that

if $\phi$ is in $\mathcal W,$ then $\neg\phi$ is in $\mathcal W;$
if $\phi$ and $\psi$ are in $\mathcal W,$ then $(\phi\rightarrow\psi)$ is in $\mathcal W;$ and
if $\phi$ is in $\mathcal W,$ then $(\forall v_i)\phi$ is in $\mathcal W$ for each variable $$v_i.$$

The remaining connectives and the existential quantifier are abbreviations:

$$\phi\wedge\psi = \neg(\phi\rightarrow\neg\psi)$;$
$$\phi\lor\psi = (\neg\phi\rightarrow\psi)$;$
$$\phi\leftrightarrow\psi = (\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi)$;$
$$(\exists x)\phi = \neg(\forall x)\neg\phi$.$

Definition 2.1.6. An occurrence of a variable $$x$$ in a formula is bound if it lies in the scope of a quantifier binding $$x$;$ otherwise, it is free. For a term $$t,$$ let $\operatorname{FV}(t)$ be the set of variables occurring in $$t.$$ For formulas, the set of free variables is defined recursively by

\[\begin{aligned} \operatorname{FV}(t=u) &= \operatorname{FV}(t)\cup\operatorname{FV}(u),\\ \operatorname{FV}(R(t_1,\dots,t_{n_R})) &= \bigcup_{i=1}^{n_R}\operatorname{FV}(t_i),\\ \operatorname{FV}(\neg\phi) &= \operatorname{FV}(\phi),\\ \operatorname{FV}(\phi\rightarrow\psi) &= \operatorname{FV}(\phi)\cup\operatorname{FV}(\psi),\\ \operatorname{FV}((\forall x)\phi) &= \operatorname{FV}(\phi)\setminus\{x\}. \end{aligned}\]

A formula is a sentence if it has no free variables.

Definition 2.1.7. Let $$x$$ be a variable and let $$t$$ be a term. For a term $$u,$$ the term $$u[t/x]$$ is obtained by replacing every occurrence of $$x$$ in $$u$$ by $$t.$$ A term $$t$$ is free for $$x$$ in a formula $\phi$ if no free occurrence of $$x$$ in $\phi$ lies in the scope of a quantifier binding a variable occurring in $$t.$$ When $$t$$ is free for $$x$$ in $\phi,$ the formula $\phi[t/x]$ is obtained by simultaneously replacing the free occurrences of $$x$$ in $\phi$ by $$t.$$

Definition 2.1.8. An $$\mathcal L$-$ theory $$T$$ is a set of $$\mathcal L$-$ sentences.