Unique Readability for Prefix Notation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\AA$ be an alphabet.

Then prefix notation for $\AA$ has the unique readability property.


Proof

Let $\phi$ be a WFF of prefix notation for $\AA$.

Apply the Principle of Mathematical Induction on the length of $\phi$ to prove:

$(1): \quad$ No prefix of $\phi$ is a WFF, except $\phi$ itself;
$(2): \quad$ If the first symbol of $\phi$ has arity $n$, then there exist unique WFFs $\phi_1, \ldots, \phi_n$ such that $\phi = s \phi_1 \cdots \phi_n$.

Let $\phi'$ be a WFF that is a prefix of $\phi$.

Because all WFFs have at least length $1$, it follows that:

$\phi' = s \phi'_1 \cdots \phi'_n$

Now it must be that either $\phi_1$ is a prefix of $\phi'_1$ or vice versa.

By the induction hypothesis on $(1)$, it must be that $\phi_1 = \phi'_1$ because $\phi_1$ and $\phi'_1$ are both strictly shorter than $\phi$.

Now if, given $1 < j \le n$:

$\phi_i = \phi'_i$ for all $i < j$

it follows that $\phi_j$ and $\phi'_j$ start at the same position in $\phi$.

Hence again, inductively, it follows that $\phi_j = \phi'_j$.

Thus $\phi_i = \phi'_i$ for all $1 \le i \le n$; that is:

$\phi = \phi'$


The result follows by the Principle of Mathematical Induction.

$\blacksquare$


Remark

It is not possible to use the Principle of Structural Induction, because we still need to establish that the constituent WFFs are uniquely determined.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Unique_Readability_for_Prefix_Notation&oldid=721305"