# Unique Readability for Polish Notation

## Theorem

Let $\AA$ be an alphabet.

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

## Proof

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.

$\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

- 2009: Kenneth Kunen:
*The Foundations of Mathematics*... (previous) ... (next): $\text {II}.4$ Polish Notation: Lemma $\text {II}.4.3$