2

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!

Community
  • 1
xxx
  • 645

1 Answers1

2

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.

Bruno Bentzen
  • 3,362