unique readability of parenthesized formulas
Given a set $V$ of propositional variables, and a set $F$ of logical connectives, one may form the set $\overline{V}$ of wellformed formulas, or wffs. The appearance of a wff depends on the formation rule of a wellformed formula. Auxiliary symbols may or may not be used in the construction of a wff. In the parent entry, we proved that every wellformed formula constructed without the aid of auxiliary symbols has a unique appearance. In this entry, we show that, with the aid of auxiliary symbols such as parentheses, specifically, unique readability is achieved as well. The specific formation rule we have in mind is the following: if ${p}_{1},\mathrm{\dots},{p}_{n}$ are existing wffs, and $\alpha $ is $n$ary, then so is $(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$ a wff.
Theorem 1.
Wffs constructed using the formation rule above have unique readability.
We will only give a partial proof here, since the portion not proved can be easily produced by closely following the proof from the parent entry.
Sketch of Proof.
A wff has one of the following three forms: $v$, $(\mathrm{\#})$, or $(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$, where $v$ is atomic (propositional variable), $\mathrm{\#}$ and $\alpha $ are nullary and $n$ary connectives respectively, with $n>0$, and all ${p}_{i}$ are existing wffs.
First, it is easy to see that every wff has the same number of left parentheses as right parentheses, and every proper nontrivial initial segment of a wff has more left than right parentheses.
Now, suppose $p$ and $q$ are wffs and $p=q$. We look at the following cases:

•
If $p$ is atomic, then so must be $q$, and vice versa.

•
If $p=(\mathrm{\#})$, then $q$ is either $(\mathrm{@})$ where $\mathrm{@}$ is nullary, or $q=(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$, where $\alpha $ is $n$ary with $n>0$. However, the second choice is not possible, as the length of the word $(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$ is longer than $(\mathrm{\#})$. So we are left with $(\mathrm{@})$. Canceling the parentheses in the equation $(\mathrm{\#})=(\mathrm{@})$, we have $\mathrm{\#}=\mathrm{@}$.

•
If $p=(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$, then $q$ must have the form $(\beta {q}_{1}\mathrm{\cdots}{q}_{m})$. Equating the two expressions and canceling the parentheses, we get $\alpha =\beta $ and thus $m=n$. By an argument similar to the one given in the parent entry, we see that ${p}_{n}={q}_{n}$, utilizing the function ${\varphi}^{*}$ modified so that $\varphi (()=\varphi ())=0$. Continuing this, we see that ${p}_{i}={q}_{i}$ for all $i=1,\mathrm{\dots},n$.
In all three cases, we have unique readability, the proof is complete^{}. ∎
Commas are also often used as auxiliary symbols in forming wffs to improve comprehensibility without violating unique readability.
Theorem 2.
Wffs constructed using the following formula^{} formation rule have unique readability: if ${p}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{p}_{n}$ are existing wffs, and $\alpha $ is $n$ary, then so is $\alpha \mathit{}\mathrm{(}{p}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{p}_{n}\mathrm{)}$ a wff.
Sketch of Proof.
Like the last proof, a wff also has one of the three forms: $v$, $(\mathrm{\#})$, or $\alpha ({p}_{1},\mathrm{\cdots},{p}_{n})$, where $v$ is atomic (propositional variable), $\mathrm{\#}$ and $\alpha $ are nullary and $n$ary connectives respectively, with $n>0$, and all ${p}_{i}$ are existing wffs.
The rest of the proof goes pretty much the same as the last one. The last case deserves a little more attention:
If $p=\alpha ({p}_{1},\mathrm{\dots},{p}_{n})$, and $q$ has the form $\beta ({q}_{1},\mathrm{\dots},{q}_{m})$. We again have $\alpha =\beta $ and $m=n$, after equating $p$ and $q$. Eliminating the parentheses, we get ${p}_{1},\mathrm{\dots},{p}_{n}={q}_{1},\mathrm{\dots},{q}_{n}$. So ${p}_{n}$ is a suffix of ${q}_{1},\mathrm{\dots},{q}_{n}$, which means that it is either a suffix of ${q}_{n}$, or has the form $r,{q}_{k},\mathrm{\dots},{q}_{n}$, where $r$ is a suffix of ${q}_{k1}$, and $k\le n$. In the latter case, if $r$ is the empty word^{}, then ${p}_{n}=,{q}_{k},\mathrm{\dots},{q}_{n}$, which is impossible because no wffs begins with a comma. So $r$ is a nontrivial suffix of ${q}_{k1}$. Using ${\varphi}^{*}$ (see the parent entry) modified so that $\varphi (()=\varphi ())=\varphi (,)=0$, we again show that ${p}_{n}$ can not be $r,{q}_{k},\mathrm{\dots},{q}_{n}$. Therefore, ${p}_{n}$ is a suffix of ${q}_{n}$. We will let the reader finish the rest. ∎
Finally, another common practice is to infix a connective when it is binary. We again have unique readability:
Theorem 3.
Wffs constructed using the following formula formation rule have unique readability: if ${p}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{p}_{n}$ are existing wffs, and $\alpha $ is $n$ary, then so is $\mathrm{(}\alpha \mathit{}{p}_{\mathrm{1}}\mathit{}\mathrm{\dots}\mathit{}{p}_{n}\mathrm{)}$ a wff if $n\mathrm{\ne}\mathrm{2}$, and so is $\mathrm{(}{p}_{\mathrm{1}}\mathit{}\alpha \mathit{}{p}_{\mathrm{2}}\mathrm{)}$ a wff if $n\mathrm{=}\mathrm{2}$.
Sketch of Proof.
The proof is very much the same as before. A wff in this case has four forms: $v$, $(\mathrm{\#})$, $(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$, or $({q}_{1}\beta {q}_{2})$. We only need to observe the following:

•
if $p$ has the form $(\alpha {p}_{1}\mathrm{\cdots}{p}_{n})$, and $p=q$, then $q$ can not have the form $({q}_{1}\beta {q}_{2})$, for otherwise ${q}_{1}$ begins with $\alpha $, which is impossible, because a wff never begins with a connective symbol, as it either begins with a left parenthesis $($, or is an atom.

•
so $p$ has the form $({p}_{1}\alpha {p}_{2})$ and $q$ has the form $({q}_{1}\beta {q}_{2})$, which means that ${p}_{1}$ is a prefix of ${q}_{1}\beta {q}_{2})$. Then ${p}_{1}$ is either a prefix of ${q}_{1}$, or has the form ${q}_{1}\beta r$, where $r$ is a prefix of ${q}_{2})$. Let us look at the latter case. $r$ can not be the empty word, for otherwise ${p}_{1}={q}_{1}\beta $, and no wffs end with a connective symbol. $r$ can not be ${q}_{2}$ or ${q}_{2})$, for otherwise ${p}_{1}\alpha {p}_{2}$ is longer (in length) than ${q}_{1}\beta {q}_{2}$. So $r$ is a proper nontrivial prefix of ${q}_{2}$, but this is also impossible, for then $r$ has more left than right parentheses, which means ${q}_{1}\beta r$, or ${p}_{1}$, a wff, has more left than right parentheses. This shows that ${p}_{1}$ is a prefix of ${q}_{1}$.
The rest of the proof is now easy. ∎
Title  unique readability of parenthesized formulas 

Canonical name  UniqueReadabilityOfParenthesizedFormulas 
Date of creation  20130322 18:52:44 
Last modified on  20130322 18:52:44 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  5 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03B05 