# Boolean Interpretation is Well-Defined

## Theorem

Let $\mathcal L_0$ be the language of propositional logic.

Let $v: \mathcal L_0 \to \{T, F\}$ be a boolean interpretation.

Then $v$ is well-defined.

## Proof 1

By Language of Propositional Logic has Unique Parsability, $\mathcal L_0$ is uniquely parsable.

Therefore, the Principle of Definition by Structural Induction can be applied to $\mathcal L_0$.

By inspection, we see that the definition of the boolean interpretation $v$ follows the bottom-up specification of propositional logic.

Hence the Principle of Definition by Structural Induction implies that $v$ is well-defined.

$\blacksquare$

## Proof 2

This is to be done by strong induction on the length of WFFs.

By definition of $v$ being a boolean interpretation, $v \left({p}\right)$ is well-defined for all $p \in \mathcal P_0$, the vocabulary of $\mathcal L_0$.

A WFF of length $1$ has (trivially) a unique parsing sequence.

Consequently, only a single defining rule for $v$ as a boolean interpretation applies.

So the result holds for all WFFs of length $1$.

Now, suppose the result is true for all WFFs of length $k$ or less.

Let $\mathbf A$ be a WFF of length $k+1$.

There are two possibilities:

Suppose $\mathbf A = \neg \mathbf B$ for some WFF $\mathbf B$.

Then $\mathbf B$ is of length $k$, so by the induction hypothesis has a unique value $v (\mathbf B)$ no matter what parsing sequence is used.

So as $v (\mathbf A) = f^\neg \left({ v (\mathbf B) }\right)$, it follows that $\mathbf A$ likewise has a unique value.

Hence the result holds for $k+1$ in this situation.

Suppose $\mathbf A = \left({\mathbf B * \mathbf C}\right)$ for some WFFs $\mathbf B$ and $\mathbf C$ and some connective $*$.

By Language of Propositional Logic has Unique Parsability, $*$ must be the unique main connective.

So $\mathbf B$ and $\mathbf C$ are both WFFs shorter than $k+1$ and therefore by the induction hypothesis have unique values $v (\mathbf B)$ and $v (\mathbf C)$.

Since $\mathbf A = \left({\mathbf B * \mathbf C}\right)$ for a unique main connective $*$, it follows that:

- $v (\mathbf A) = f^* \left({ v (\mathbf B), v (\mathbf C) }\right)$

is well-defined.

Hence the result holds for $k+1$ in this situation.

So the result follows by the Second Principle of Mathematical Induction.

$\blacksquare$