unique readability of wellformed formulas
Suppose $V$ is an alphabet. Two words ${w}_{1}$ and ${w}_{2}$ over $V$ are the same if they have the same length and same symbol for every position of the word. In other words, if ${w}_{1}={a}_{1}\mathrm{\cdots}{a}_{n}$ and ${w}_{2}={b}_{1}\mathrm{\cdots}{b}_{m}$, where each ${a}_{i}$ and ${b}_{i}$ are symbols in $V$, then $n=m$ and ${a}_{i}={b}_{i}$. In other words, every word over $V$ has a unique representation as product^{} (concatenation^{}) of symbols in $V$. This is called the unique readability of words over an alphabet.
Unique readability remains true if $V$ is infinite^{}. Now, suppose $V$ is a set of propositional variables, and suppose we have two wellformed formulas (wffs) $p:=\alpha {p}_{1}\mathrm{\cdots}{p}_{n}$ and $q:=\beta {q}_{1}\mathrm{\cdots}{q}_{m}$ over $V$, where $\alpha ,\beta $ are logical connectives from a fixed set $F$ of connectives (for example, $F$ could be the set $\{\mathrm{\neg},\vee ,\wedge ,\to ,\leftrightarrow \}$), and ${p}_{i},{q}_{j}$ are wffs. Does $p=q$ mean $\alpha =\beta $, $m=n$, and ${p}_{i}={q}_{i}$? This is the notion of unique readability of wellformed formulas. It is slightly different from the unique readability of words over an alphabet, for ${p}_{i}$ and ${q}_{j}$ are no longer symbols in an alphabet, but words themselves.
Theorem 1.
Given any countable set $V$ of propositional variables and a set $F$ of logical connectives, wellformed formulas over $V$ constructed via $F$ are uniquely readable
Proof.
Every $p\in \overline{V}$ has a representation $\alpha {p}_{1}\mathrm{\cdots}{p}_{n}$ for some $n$ary connective $\alpha $ and wffs ${p}_{i}$. The rest of the proof we show that this representation is unique, establishing unique readability.
Define a function $\varphi :V\cup F\to \mathbb{Z}$ such that $\varphi (v)=1$ for any $v\in V$, and $\varphi (f)=1n$ for any $n$ary connective $f\in F$. Defined inductively on the length of words over $V\cup F$, $\varphi $ can be extended to an integervalued function ${\varphi}^{*}$ on the set of all words on $V\cup F$ so that ${\varphi}^{*}({w}_{1}{w}_{2})={\varphi}^{*}({w}_{1})+{\varphi}^{*}({w}_{2})$, for any words ${w}_{1},{w}_{2}$ over $V\cup F$. We have

1.
${\varphi}^{*}$ is constant (whose value is $1$) when restricted to $\overline{V}$.
This can be proved by induction^{} on ${V}_{i}$ (for the definition of ${V}_{i}$, see the parent entry). By definition, this is true for any atoms. Assume this is true for ${V}_{i}$. Pick any $p\in {V}_{i+1}$. Then $p=\alpha {p}_{1}\mathrm{\cdots}{p}_{n}$ for some $n$ary $\alpha \in F$, and ${p}_{j}\in {V}_{i}$ for all $j=1,\mathrm{\dots},n$ Then ${\varphi}^{*}(p)={\varphi}^{*}(\alpha )+{\varphi}^{*}({p}_{1})+\mathrm{\cdots}+{\varphi}^{*}({p}_{n})=1n+n\times 1=1$. Therefore, ${\varphi}^{*}(p)=1$ for all $p\in \overline{V}$.

2.
for any nontrivial suffix $s$ of a wff $p$, ${\varphi}^{*}(s)>0$. (A suffix of a word $w$ is a word $s$ such that $w=ts$ for some word $t$; $s$ is nontrivial if $s$ is not the empty word^{})
This is also proved by induction. If $p\in {V}_{0}$, then $p$ itself is its only nontrivial final segment, so the assertion is true. Suppose now this is true for any proposition^{} in ${V}_{i}$. If $p\in {V}_{i+1}$, then $p=\alpha {p}_{1}\mathrm{\cdots}{p}_{n}$, where each ${p}_{k}\in {V}_{i}$. A nontrivial final segment $s$ of $p$ is either $p$, a final segment of ${p}_{n}$, or has the form $t{p}_{j}\mathrm{\cdots}{p}_{n}$, where $t$ is a nontrivial final segment of ${p}_{j1}$. In the first case, ${\varphi}^{*}(s)={\varphi}^{*}(p)=1$. In the second case, ${\varphi}^{*}(s)>0$ from assumption^{}. In the last case, ${\varphi}^{*}(s)={\varphi}^{*}(t)+(nj+1)>0$.
Now, back to the main proof. Suppose $p=q$. If $p$ is an atom, so must $q$, and we are done. Otherwise, assume $p=\alpha {p}_{1}\mathrm{\cdots}{p}_{m}=\beta {q}_{1}\mathrm{\cdots}{q}_{n}=q$. Then $\alpha =\beta $ since the expressions are words over $V\cup F$, and $\alpha ,\beta \in F$. Since the two connectives are the same, they have the same arity: $m=n$, and we have $\alpha {p}_{1}\mathrm{\cdots}{p}_{n}=\alpha {q}_{1}\mathrm{\cdots}{q}_{n}$. If $n=0$, then we are done. So assume $n>0$. Then ${p}_{1}\mathrm{\cdots}{p}_{n}={q}_{1}\mathrm{\cdots}{q}_{n}$. We want to show that ${p}_{n}={q}_{n}$, and therefore ${p}_{1}\mathrm{\cdots}{p}_{n1}={q}_{1}\mathrm{\cdots}{q}_{n1}$, and by induction ${p}_{i}={q}_{i}$ for all $$ as well, proving the theorem.
First, notice that ${p}_{n}$ is a nontrivial suffix of ${q}_{1}\mathrm{\cdots}{q}_{n}$. So ${p}_{n}$ is either a suffix of ${q}_{n}$ or has the form $t{q}_{j}\mathrm{\cdots}{q}_{n}$, where $j\le n$, and $t$ is a nontrivial suffix of ${q}_{j1}$. In the latter case, $1={\varphi}^{*}({p}_{n})={\varphi}^{*}(t{q}_{j}\mathrm{\cdots}{q}_{n})={\varphi}^{*}(t)+nj+1$. Then ${\varphi}^{*}(t)=jn\le 0$, contradicting 2 above. Therefore ${p}_{n}$ is a suffix of ${q}_{n}$. By symmetry^{}, ${q}_{n}$ is also a suffix of ${p}_{n}$, hence ${p}_{n}={q}_{n}$. ∎
As a corollary, we see that the wellformed formulas of the classical propositional logic, written in Polish notation, are uniquely readable. The unique readability of wffs using parentheses and infix notation requires a different proof.
Remark. Unique readability will fail if the ${p}_{i}$ and ${q}_{j}$ above are not wffs, even if $V$ is finite. For example, suppose $v\in V$ and $\mathrm{\#}$ is binary, then $\mathrm{\#}v\mathrm{\#}vv$ can be read in three nontrivial ways: combining $v$ and $\mathrm{\#}vv$, combining $v\mathrm{\#}$ and $vv$, or combining $v\mathrm{\#}v$ and $v$. Notice that only the first combination^{} do we get wffs.
Title  unique readability of wellformed formulas 

Canonical name  UniqueReadabilityOfWellformedFormulas 
Date of creation  20130322 18:52:32 
Last modified on  20130322 18:52:32 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03B05 
Defines  unique readability 