unique readability of well-formed formulas

Suppose V is an alphabet. Two words w1 and w2 over V are the same if they have the same length and same symbol for every position of the word. In other words, if w1=a1an and w2=b1bm, where each ai and bi are symbols in V, then n=m and ai=bi. In other words, every word over V has a unique representation as productPlanetmathPlanetmath (concatenationMathworldPlanetmath) of symbols in V. This is called the unique readability of words over an alphabet.

Unique readability remains true if V is infiniteMathworldPlanetmath. Now, suppose V is a set of propositional variables, and suppose we have two well-formed formulas (wffs) p:=αp1pn and q:=βq1qm over V, where α,β are logical connectives from a fixed set F of connectives (for example, F could be the set {¬,,,,}), and pi,qj are wffs. Does p=q mean α=β, m=n, and pi=qi? 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 pi and qj 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


Every pV¯ has a representation αp1pn for some n-ary connective α and wffs pi. The rest of the proof we show that this representation is unique, establishing unique readability.

Define a function ϕ:VF such that ϕ(v)=1 for any vV, and ϕ(f)=1-n for any n-ary connective fF. Defined inductively on the length of words over VF, ϕ can be extended to an integer-valued function ϕ* on the set of all words on VF so that ϕ*(w1w2)=ϕ*(w1)+ϕ*(w2), for any words w1,w2 over VF. We have

  1. 1.

    ϕ* is constant (whose value is 1) when restricted to V¯.

    This can be proved by inductionMathworldPlanetmath on Vi (for the definition of Vi, see the parent entry). By definition, this is true for any atoms. Assume this is true for Vi. Pick any pVi+1. Then p=αp1pn for some n-ary αF, and pjVi for all j=1,,n Then ϕ*(p)=ϕ*(α)+ϕ*(p1)++ϕ*(pn)=1-n+n×1=1. Therefore, ϕ*(p)=1 for all pV¯.

  2. 2.

    for any non-trivial suffix s of a wff p, ϕ*(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 wordPlanetmathPlanetmath)

    This is also proved by induction. If pV0, then p itself is its only non-trivial final segment, so the assertion is true. Suppose now this is true for any propositionPlanetmathPlanetmathPlanetmath in Vi. If pVi+1, then p=αp1pn, where each pkVi. A non-trivial final segment s of p is either p, a final segment of pn, or has the form tpjpn, where t is a non-trivial final segment of pj-1. In the first case, ϕ*(s)=ϕ*(p)=1. In the second case, ϕ*(s)>0 from assumptionPlanetmathPlanetmath. In the last case, ϕ*(s)=ϕ*(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=αp1pm=βq1qn=q. Then α=β since the expressions are words over VF, and α,βF. Since the two connectives are the same, they have the same arity: m=n, and we have αp1pn=αq1qn. If n=0, then we are done. So assume n>0. Then p1pn=q1qn. We want to show that pn=qn, and therefore p1pn-1=q1qn-1, and by induction pi=qi for all i<n as well, proving the theorem.

First, notice that pn is a non-trivial suffix of q1qn. So pn is either a suffix of qn or has the form tqjqn, where jn, and t is a non-trivial suffix of qj-1. In the latter case, 1=ϕ*(pn)=ϕ*(tqjqn)=ϕ*(t)+n-j+1. Then ϕ*(t)=j-n0, contradicting 2 above. Therefore pn is a suffix of qn. By symmetryPlanetmathPlanetmath, qn is also a suffix of pn, hence pn=qn. ∎

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 pi and qj above are not wffs, even if V is finite. For example, suppose vV 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 combinationMathworldPlanetmathPlanetmath do we get wffs.

Title unique readability of well-formed formulas
Canonical name UniqueReadabilityOfWellformedFormulas
Date of creation 2013-03-22 18:52:32
Last modified on 2013-03-22 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