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}\cdots a_{n}$ and $w_{2}=b_{1}\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 well-formed formulas (wffs) $p:=\alpha p_{1}\cdots p_{n}$ and $q:=\beta q_{1}\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 $\{\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 well-formed 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, well-formed formulas over $V$ constructed via $F$ are uniquely readable

Proof.

Every $p\in\overline{V}$ has a representation $\alpha p_{1}\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 $\phi:V\cup F\to\mathbb{Z}$ such that $\phi(v)=1$ for any $v\in V$, and $\phi(f)=1-n$ for any $n$-ary connective $f\in F$. Defined inductively on the length of words over $V\cup F$, $\phi$ can be extended to an integer-valued function $\phi^{*}$ on the set of all words on $V\cup F$ so that $\phi^{*}(w_{1}w_{2})=\phi^{*}(w_{1})+\phi^{*}(w_{2})$, for any words $w_{1},w_{2}$ over $V\cup F$. We have

1. 1.

$\phi^{*}$ 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}\cdots p_{n}$ for some $n$-ary $\alpha\in F$, and $p_{j}\in V_{i}$ for all $j=1,\ldots,n$ Then $\phi^{*}(p)=\phi^{*}(\alpha)+\phi^{*}(p_{1})+\cdots+\phi^{*}(p_{n})=1-n+n% \times 1=1$. Therefore, $\phi^{*}(p)=1$ for all $p\in\overline{V}$.

2. 2.

for any non-trivial suffix $s$ of a wff $p$, $\phi^{*}(s)>0$. (A suffix of a word $w$ is a word $s$ such that $w=ts$ for some word $t$; $s$ is non-trivial if $s$ is not the empty word)

This is also proved by induction. If $p\in V_{0}$, then $p$ itself is its only non-trivial 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}\cdots p_{n}$, where each $p_{k}\in V_{i}$. A non-trivial final segment $s$ of $p$ is either $p$, a final segment of $p_{n}$, or has the form $tp_{j}\cdots p_{n}$, where $t$ is a non-trivial final segment of $p_{j-1}$. In the first case, $\phi^{*}(s)=\phi^{*}(p)=1$. In the second case, $\phi^{*}(s)>0$ from assumption. In the last case, $\phi^{*}(s)=\phi^{*}(t)+(n-j+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}\cdots p_{m}=\beta q_{1}\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}\cdots p_{n}=\alpha q_{1}\cdots q_{n}$. If $n=0$, then we are done. So assume $n>0$. Then $p_{1}\cdots p_{n}=q_{1}\cdots q_{n}$. We want to show that $p_{n}=q_{n}$, and therefore $p_{1}\cdots p_{n-1}=q_{1}\cdots q_{n-1}$, and by induction $p_{i}=q_{i}$ for all $i as well, proving the theorem.

First, notice that $p_{n}$ is a non-trivial suffix of $q_{1}\cdots q_{n}$. So $p_{n}$ is either a suffix of $q_{n}$ or has the form $tq_{j}\cdots q_{n}$, where $j\leq n$, and $t$ is a non-trivial suffix of $q_{j-1}$. In the latter case, $1=\phi^{*}(p_{n})=\phi^{*}(tq_{j}\cdots q_{n})=\phi^{*}(t)+n-j+1$. Then $\phi^{*}(t)=j-n\leq 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 well-formed 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 $\#$ is binary, then $\#v\#vv$ can be read in three non-trivial ways: combining $v$ and $\#vv$, combining $v\#$ and $vv$, or combining $v\#v$ and $v$. Notice that only the first combination do we get wffs.

Title unique readability of well-formed formulas UniqueReadabilityOfWellformedFormulas 2013-03-22 18:52:32 2013-03-22 18:52:32 CWoo (3771) CWoo (3771) 9 CWoo (3771) Theorem msc 03B05 unique readability