Unique Readability for Polish Notation
Let $\AA$ be an alphabet.
- $(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$.
- $\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.