Unique Readability for Polish Notation

From ProofWiki
Jump to navigation Jump to search


Let $\AA$ be an alphabet.

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


Let $\phi$ be a WFF of Polish 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.



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