Unique Readability of Well-Formed Formulas
We need two more lemmas before we can move onto the theorem that we want to prove. The first is fairly easy.
Lemma 3.1. For every well-formed formula $\varphi$, the first symbol of $\varphi$ is either $($ or a propositional variable.
Proof. Recall that, by definition, a well-formed formula is either a propositional variable or a formula of the form $(\neg \alpha), (\alpha \wedge \beta), (\alpha \vee \beta), (\alpha \rightarrow \beta)$. If $\varphi = p$ where $p$ is a propositional variable, it is clear that the first symbol of $\varphi$ is $p$, a propositional variable. Otherwise, in all other cases it is clear that the first symbol of $\varphi$ must be $($.
$$\tag*{$\Box$}$$
The second of the two lemmas we need to prove today before moving on involves the proper prefix of an expression or string.
Definition 3.2. A proper prefix of an expression $\varphi$ is a non-empty expression $\alpha$ such that $\varphi = \alpha \beta$ for some non-empty expression $\beta$. For example,
- the proper prefixes of the expression $(\neg p)$ are: $(, (\neg, (\neg p$,
- the proper prefixes of the expression $))( \vee q$ are: $), )), ))(, ))( \vee, ))(\vee$.
We will make use of the following property of proper prefixes of well-formed formulas.
Lemma 3.3. Let $\varphi$ be a well-formed formula. Then every proper prefix of $\varphi$ has more opening parentheses than closing parentheses.
Proof. We will prove this by structural induction. Let $op(\varphi)$ and $cl(\varphi)$ denote the number of opening and closing parentheses in $\varphi$, respectively. Let $P(\varphi)$ denote the property that for every proper prefix $\psi$ of $\varphi$, $op(\psi) > cl(\psi)$.
Base case: $\varphi = p$ for some propositional variable $p$. Such an expression has no proper prefixes. Therefore, $P(\varphi)$ holds vacuously.
Induction step: Let $\varphi'$ denote a proper prefix of $\varphi$. There are two cases to consider.
- $\varphi = (\neg \alpha)$ for some well-formed formula $\alpha$. Assume that $P(\alpha)$ holds. There are four cases to consider.
- $\varphi' = ($. Then $op(\varphi') = op(() = 1 > 0 = cl(() = cl(\varphi')$.
- $\varphi' = (\neg$. Then $op(\varphi') = op((\neg) = 1 > 0 = cl((\neg) = cl(\varphi')$.
- $\varphi' = (\neg\alpha'$ for some proper prefix $\alpha'$ of $\alpha$. Then,
\begin{align*}
op((\neg\alpha') &= 1+op(\alpha') \\
& > 1 + cl(\alpha') & \text{(induction hypothesis)} \\
& > cl(\alpha') \\
&= cl((\neg\alpha')
\end{align*}
- $\varphi' = (\neg\alpha$. Then,
\begin{align*}
op((\neg\alpha) &= 1+op(\alpha) \\
& = 1 + cl(\alpha) & \text{(Lemma 2.4)} \\
& > cl(\alpha) \\
& = cl((\neg\alpha)
\end{align*}
Thus, $P(\varphi)$ holds.
- $\varphi = (\alpha * \beta)$ for well-formed formulas $\alpha$ and $\beta$. Assume that $P(\alpha)$ and $P(\beta)$ hold. There are six cases to consider.
- $\varphi' = ($. Then $op(\varphi') = op(() = 1 > 0 = cl(() = cl(\varphi')$.
- $\varphi' = (\alpha'$ for some proper prefix $\alpha'$ of $\alpha$. Then,
\begin{align*}
op((\alpha') &= 1 + op(\alpha') \\
& > 1 + cl(\alpha') & \text{(induction hypothesis)} \\
& > cl(\alpha') \\
& = cl((\alpha')
\end{align*}
- $\varphi' = (\alpha$. Then,
\begin{align*}
op((\alpha) &= 1 + op(\alpha) \\
& = 1 + cl(\alpha) & \text{(Lemma 2.4)} \\
& > cl(\alpha) \\
& = cl((\alpha)
\end{align*}
- $\varphi' = (\alpha *$. Then,
\begin{align*}
op((\alpha *) &= 1 + op(\alpha) \\
& = 1 + cl(\alpha) & \text{(Lemma 2.4)} \\
& > cl(\alpha) \\
& = cl((\alpha *)
\end{align*}
- $\varphi' = (\alpha * \beta'$. Then,
\begin{align*}
op((\alpha * \beta') &= 1 + op(\alpha) + op(\beta') \\
& = 1 + cl(\alpha) + op(\beta') & \text{(Lemma 2.4)} \\
& > 1 + cl(\alpha) + cl(\beta') & \text{(induction hypothesis)} \\
& > cl(\alpha) + cl(\beta') \\
& = cl((\alpha * \beta')
\end{align*}
- $\varphi' = (\alpha * \beta$. Then,
\begin{align*}
op((\alpha * \beta) &= 1 + op(\alpha) + op(\beta) \\
& = 1 + cl(\alpha) + cl(\beta) & \text{(Lemma 2.4)} \\
& > cl(\alpha) + cl(\beta) \\
& = cl((\alpha * \beta)
\end{align*}
Thus, $P(\varphi)$ holds.
By the principle of structural induction, $P(\varphi)$ holds for every well-formed formula $\varphi$.
$$\tag*{$\Box$}$$
The Main Result
Now, we have all the properties of well-formed formulas we need to prove that all well-formed formulas are uniquely readable. That is, there's exactly one way to construct or interpret each well-formed formula.
How exactly do we do this? Well, suppose we know one way to construct a formula. We just have to show that there's no other way to come up with the same formula. Luckily, there are a limited number of ways to do this, so we just have to check them all at each step to make sure. In essence, this is what our proof, via structural induction, will do: for every well-formed formula, we check that the last step is the only one that we can possibly apply.
Theorem 3.4. (Unique Readability) There is a unique way to construct every well-formed formula.
Proof. We will prove this by structural induction. Let $\varphi$ be a well-formed formula.
Base case: $\varphi = p$, for some propositional variable $p$. Let $\alpha$ and $\beta$ be well-formed formulas.
- Suppose that $\varphi$ can be written as $(\neg \alpha)$. This cannot be the case, since $(\neg \alpha)$ has length at least 4, while $\varphi$ has length exactly 1.
- Similarly, $\varphi$ cannot be written as $(\alpha * \beta)$ for any binary connective *, since such a formula has length at least 5. Thus, $\varphi$ must be written as a propositional variable.
Induction step: There are two cases to consider.
Case 1: We have $\varphi = (\neg \alpha)$ where $\alpha$ is a well-formed formula. For our induction hypothesis, we assume $\alpha$ has a unique construction.
Then $\varphi$ has the following obvious construction: construct $\alpha$, then apply negation to obtain $(\neg \alpha)$. We will show that there are no other possible constructions.
- Suppose that we can construct $(\neg \alpha)$ as a propositional variable. A propositional variable has length exactly 1, while $(\neg \alpha)$ must be of length at least 4. Therefore, this cannot be the case.
- Suppose that we can construct $(\neg \alpha)$ as a formula $(\neg \gamma)$ for some well-formed formula $\gamma \neq \alpha$. However, by our inductive hypothesis, $\alpha$ is uniquely constructible so we must have $\gamma = \alpha$.
- Suppose that we can construct $(\neg \alpha)$ as a formula $(\gamma * \eta)$, where $\gamma$ and $\eta$ are well-formed formulas and $*$ is a binary connective. In this case, observe that the first symbol of $\gamma$ must be $\neg$. However, this would mean $\gamma$ is not well-formed by Lemma 3.1. This contradicts our assumption that $\gamma$ is well-formed. Therefore, we cannot construct $\varphi$ by applying a binary connective.
Thus, formulas of the form $(\neg \alpha)$ have a unique construction.
Case 2: We have $\varphi = (\alpha * \beta)$ where $\alpha$ and $\beta$ are well-formed formulas and $*$ is a binary connective $\wedge, \vee, \rightarrow)$. For our induction hypothesis, we assume that $\alpha$ and $\beta$ each have unique constructions. We will show that there is a unique way to construct $(\alpha * \beta)$.
Then $\varphi$ has the following obvious construction: construct $\alpha$, construct $\beta$, then join the two with the binary connective $*$. We will show that there are no other possible constructions.
- Suppose that we can construct $\varphi$ as a propositional variable. As before, this cannot be the case since propositional variables have length 1 while $(\alpha * \beta)$ has length at least 5.
- Suppose that we can construct $\varphi$ as a formula $(\neg \gamma)$ for some well-formed formula $\gamma$. Observe that in this case, the first symbol of $\alpha$ would be $\neg$. Since $\alpha$ is well-formed, by Lemma 3.1, this cannot be the case and this construction does not hold.
- Suppose that we can construct $\varphi$ as a formula $(\gamma * \eta)$ where $\gamma$ and $\eta$ are well-formed formulas. However, by our inductive hypothesis, $\alpha$ and $\beta$ have unique constructions, so we must have $\gamma = \alpha$ and $\eta = \beta$.
- Suppose that we can construct $\varphi$ as a formula $(\gamma \odot \eta)$ where $\gamma$ and $\eta$ are well-formed formulas, and $\odot$ is a binary connective that is not $*$. In this case, the binary connective $\odot$ must occur in either $\alpha$ or $\beta$.
- If $\odot$ occurs in $\alpha$, then $\gamma$ is a proper prefix of $\alpha$. By Lemma 3.3, $\gamma$ has more opening parentheses than closing parentheses. But we assumed that $\gamma$ is a well-formed formula, which has an equal number of opening and closing parentheses, by Lemma 2.4. Thus, this contradicts our assumption and $\odot$ does not occur in $\alpha$. Thus, this construction is not valid.
- If $\odot$ occurs in $\beta$, then we can write $\beta = \mu \odot \sigma$. In other words, $\gamma = \alpha * \mu$ and $\eta = \sigma$. Let $op(\psi)$ and $cl(\psi)$ denote the number of opening and closing parentheses in $\psi$. Since $\alpha$ is well-formed, by Lemma 2.4, we have $op(\alpha) = cl(\alpha)$. Note that $\mu$ is a proper prefix of $\beta$, and therefore by Lemma 3.3, $op(\mu) > cl(\mu)$. Then we have
\begin{align*}
op(\gamma) & = op(\alpha) + op(\mu) \\
& = cl(\alpha) + op(\mu) & \text{(Lemma 2.4)} \\
& > cl(\alpha) + cl(\mu) & \text{(Lemma 3.3)} \\
& = cl(\gamma)
\end{align*}
Therefore, $op(\gamma) > cl(\gamma)$ and by Lemma 2.4, $\gamma$ is not well-formed as originally assumed. Thus, this construction cannot work.
Thus, formulas of the form $(\alpha * \beta)$ have a unique construction.
By the principle of structural induction, we have shown that each well-formed formula $\varphi$ has a unique construction.
$$\tag*{$\Box$}$$