Let $S$ be an arbitrary set of symbols, $x$ variable and $\Phi$ $S$-formula. Assume that $x$ occurs as bound variable in $\Phi$.

I want to show:

There exist strings $\zeta_1, \zeta_2$ and $S$-formulas $\Psi_1, \Psi_2$ so that:

  1. x does not occur in $\zeta_1$.

  2. $\Phi = \zeta_1 \Psi_1 \zeta_2$.

  3. $\Psi_1$ is either of the form $\exists x \Psi_2$ or of the form $\forall x \Psi_2$.

Intuitively this seems evident, but how can one prove that? Thanks in advance!


I assume you are referring to a first-order language $L_\Sigma=<\Sigma,V,\rightarrow,\bot,\forall,\exists>$, where

  • $\Sigma$ is a triple $<R,F,C>$ the signature of $L$, where $R=\{R_n\}_{n \in \mathbb{N}}$ and $F=\{F_n\}_{n \in \mathbb{N}}$ are family of sets and $C$ is a set. The elements of $R$ are called $n$-ary relation symbols, the elements of $F$ are called $n$-ary function symbols, the elements of $C$ are called constant symbols. We say that $\Sigma$ is the signature of $L$.
  • $V$ is a set, called the variable symbols of $L_\Sigma$.

Now let $L_\Sigma^*$ denote the set of all strings of $L_\Sigma$.

  1. Trival. Just take '$\bot$' or '$\rightarrow$' (Note that those are strings)

  2. Let $x$ occurs bound in $Φ$. We want to show that $Φ \equiv ζ_1Ψ_1ζ_2$ for some strings $ζ_1,ζ_2$ and a well-formed formula $Ψ_1$. By the definition of a $L_\Sigma$-bound variable (define it!), we have that part of $Φ$ consists of either $\forall x \Psi_2$ $\exists x \Psi_2$, where $x$ occurs free in $\Psi_2$. We set $Ψ_1$ as any one of those two. Now we proceed by cases. Case 1: $Φ$ is atomic. Then $ζ_1=ζ_2=\emptyset$ and we are done. Case 2: $Φ$ is molecular. Then, by the definition of the wff of $L_\Sigma$ (define it), $Φ \equiv \alpha \rightarrow \beta$, where $\alpha$ and $\beta$ are $L_\Sigma$-wff. Now $x$ is bound in $\alpha$ or $\beta$. If it is in $\alpha$, and it is atomic, then $\alpha \equiv \psi_1$ and set $ζ_1 = \emptyset$ and $ζ_2 \equiv \rightarrow \beta$. If it is in $\beta$, and it is atomic, then $\beta \equiv \psi_1$ and set $ζ_1 = \alpha \rightarrow$ and $ζ_2 \equiv \emptyset$. If $x$ is bound in $\alpha$ and it is molecular, then $\Phi\equiv (\alpha' \rightarrow \beta') \rightarrow \beta$ and the argument continues for $\alpha'$ and $\beta'$ (the same holds for $\beta$).

  3. Take the definition of bound variable you defined in (2).

Note that there is a lot of missing information in the OP's question though.


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.