Problems with recursive definitions

Question

I'm having a bit of trouble understanding how to go about formulating recursive definitions. This has caused trouble on the following:

$(1)$ Give a recursive definition of the set of subsentences of a sentence $\phi$ of $L_1$ — i.e. give a recursive specification of the function $\phi \mapsto$ {$ \psi \ | \ \psi$ is a subsentence of $\psi$}.

Answer 1

In order to define the function $\text{Sub}(ϕ) = \text { the set of subformulas of } ϕ$, we have to follow the recursive (or inductive) definition of formula :

(i) $\phi \text { is an atomic formula, i.e. }$ :

$\top, \bot, t_1=t_2 \text { and } P_n(t_1,\ldots, t_n), \text { for terms } t_i \text { and predicate symbol } P_n.$

In this case $\text {Sub}(\phi) = \{ \phi \}$.

(ii) $\phi \text { is a formula } \psi_1 \circ \psi_2, \text { where } \circ \in \{ \land, \lor, \to, \leftrightarrow \}.$

In this case $\text {Sub}(\phi) = \text {Sub}( \psi_1) \cup \text {Sub}( \psi_2) \cup \{ \psi_1 \circ \psi_2 \}.$

(iii) $\phi \text { is a formula } \lnot \psi$.

In this case $\text {Sub}(\phi) = \text {Sub}( \psi) \cup \{ \lnot \psi \}.$

And similar for quantifiers.

---

We have to use them in the general schema of Definition by Recursion :

Let mappings $H_{\circ} : A^2 → A$ and $H_¬ : A → A$ be given and let $H_{at}$ be a mapping from the set of atoms into $A$. Then there is exactly one mapping $F : \text {FORM} → A$ such that :

$F(ϕ) = H_{at}(ϕ)$ for $ϕ$ atomic,

$F((ϕ\circ ψ)) = H_{\circ}(F (ϕ),F(ψ)$),

$F((¬ϕ)) = H_¬(F (ϕ))$.

Above we have defined the specific functions to be used with $A=\text{FORM}$ to get $F=\text{Sub}$.