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 well-formed formulas, or wffs. The appearance of a wff depends on the formation rule of a well-formed formula. Auxiliary symbols may or may not be used in the construction of a wff. In the parent entry, we proved that every well-formed 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},\ldots,p_{n}$ are existing wffs, and $\alpha$ is $n$ -ary, then so is $(\alpha p_{1}\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$ , $(\#)$ , or $(\alpha p_{1}\cdots p_{n})$ , where $v$ is atomic (propositional variable), $\#$ 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 non-trivial 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=(\#)$ , then $q$ is either $(@)$ where $@$ is nullary, or $q=(\alpha p_{1}\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}\cdots p_{n})$ is longer than $(\#)$ . So we are left with $(@)$ . Canceling the parentheses in the equation $(\#)=(@)$ , we have $\#=@$ .
•

If $p=(\alpha p_{1}\cdots p_{n})$ , then $q$ must have the form $(\beta q_{1}\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 $\phi^{*}$ modified so that $\phi(()=\phi())=0$ . Continuing this, we see that $p_{i}=q_{i}$ for all $i=1,\ldots,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_{1},\ldots,p_{n}$ are existing wffs, and $\alpha$ is $n$ -ary, then so is $\alpha(p_{1},\ldots,p_{n})$ a wff.

Sketch of Proof.

Like the last proof, a wff also has one of the three forms: $v$ , $(\#)$ , or $\alpha(p_{1},\cdots,p_{n})$ , where $v$ is atomic (propositional variable), $\#$ 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},\ldots,p_{n})$ , and $q$ has the form $\beta(q_{1},\ldots,q_{m})$ . We again have $\alpha=\beta$ and $m=n$ , after equating $p$ and $q$ . Eliminating the parentheses, we get $p_{1},\ldots,p_{n}=q_{1},\ldots,q_{n}$ . So $p_{n}$ is a suffix of $q_{1},\ldots,q_{n}$ , which means that it is either a suffix of $q_{n}$ , or has the form $r,q_{k},\ldots,q_{n}$ , where $r$ is a suffix of $q_{k-1}$ , and $k\leq n$ . In the latter case, if $r$ is the empty word, then $p_{n}=,q_{k},\ldots,q_{n}$ , which is impossible because no wffs begins with a comma. So $r$ is a non-trivial suffix of $q_{k-1}$ . Using $\phi^{*}$ (see the parent entry) modified so that $\phi(()=\phi())=\phi(,)=0$ , we again show that $p_{n}$ can not be $r,q_{k},\ldots,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_{1},\ldots,p_{n}$ are existing wffs, and $\alpha$ is $n$ -ary, then so is $(\alpha p_{1}\ldots p_{n})$ a wff if $n\neq 2$ , and so is $(p_{1}\alpha p_{2})$ a wff if $n=2$ .

Sketch of Proof.

The proof is very much the same as before. A wff in this case has four forms: $v$ , $(\#)$ , $(\alpha p_{1}\cdots p_{n})$ , or $(q_{1}\beta q_{2})$ . We only need to observe the following:

•

if $p$ has the form $(\alpha p_{1}\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 non-trivial 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	2013-03-22 18:52:44
Last modified on	2013-03-22 18:52:44
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 03B05