Why is the unique readability of wff's important?

Question

I am reading Classical Mathematical Logic by Epstein. The author defines:

$L(\neg, \rightarrow, \vee, \wedge, p_0, p_1, ...)$

i. For each $i=0, 1, 2, ..., (p_i)$ is an atomic wff, to which we assign the number $1$.

ii. If $A$ and $B$ are wffs and the maximum of the numbers assigned to $A$ and to $B$ is $n$, then each of $(\neg A), (A \rightarrow B), (A \vee B), (A \wedge B)$ is a compound wff to which we assign the number $n+1$. These are compound wffs.

iii. A concatenation of symbols is a wff if and only if it is assigned some number $n \ge 1$ according to (i) or (ii) above.

Then the author then proves the "Unique Readability of wffs", which he only defines as "no wff can be read as, for example, both $A \rightarrow B$ and $C \wedge D$"

I don't really see the benefits of proving this. The only benefits I can think of are:

$1)$ Each wff can only be assigned one number according to (ii).

I've looked over the next pages, and the book seems to only make use of this fact in the definition of the length of a wff. It doesn't seem important, because a proposition can only be assigned a number if it is using the maximum number of parenthesis (which we almost never do). There are plenty of equivalent propositions which are assigned different numbers. Similarly, there are plenty of equivalent such that $A \rightarrow B \equiv C \wedge D$ and at the end of the day, we mostly just care about equivalence; the number being assigned to a proposition seems like just an artifact we had to use in order to make our language formal.

$2)$ If the unique readability theorem was false, then parenthesis don't behave in the intuitive way we want them to (that is, we intuitively believe that with enough parenthesis we can specify one and only one order of operations/connectives)

While this seems more important, proving that a proposition is uniquely readable does not prove that our intuition of parenthesis is necessarily right.

Am I missing something?

Answer 1

What is actually important is the local property that every wff arises in exactly one of the ways

• $(\neg A)$
• $(A\to B)$
• $(A\lor B)$
• $(A\land B)$
• atomic formula, of such-and-such particular shapes themselves

and within each group from only one combination of $A$ and $B$.

This local property is crucial for being sure that we can define properties of formulas by induction on their structure (and depend on the thing we define actually satisfying the recursion equations we define it with, in all cases).

The global property that every wff has exactly one full parse tree is just icing on the cake, and a convenient early example of how to prove things by induction on the structure of formulas.

Answer 2

If we didn't have unique readability, then the language would be useless - we wouldn't be able to say that a sentence is "true" or "false". We could have a sentence that was true under one reading, but not under the other.

A formal language is to natural language what arithmetic is to counting - an abstraction that's supposed to make things clearer. Imagine if we could read "$(7 + 3)\cdot 5$" in several different ways, each one evaluating to a different number - that would render this way of writing arithmetic utterly useless, wouldn't it?

To take an example, $\cos 3 + x$ could be read $\cos(3 + x)$ or $\cos(3) + x$; these are extremely different functions, and they behave completely differently. If I don't know which one I'm talking about, there's next to nothing I can say with certainty. So I would want a mathematical language to exclude strings like $\cos 3 + x$ from being sentences.

Answer 3

The bottom line is that a statement cannot have unambiguous meaning unless you have a precise unambiguous way of interpreting (reading) it. Even in natural language almost all sentences have unambiguous grammatical structure and more or less clear semantic interpretation, which is not an accident, because otherwise it would fail to be a viable means of communication! Language is nevertheless much more ambiguous than formal systems, because we can rely quite a lot on the receiving party to understand the unspoken context and to draw from a common world view to disambiguate between possible meanings by choosing the one that fits them best.

Formal systems, on the other hand, are purposely designed to be completely precise, so that they have absolutely no ambiguity. Why? Because it then means that once someone accepts all the assumptions and inference rules of a given formal system, that one has no choice but to accept every argument that we can express in the formal system as well, since it can be mechanically checked that it follows the rules.

If you want a crystal-clear grasp of the importance of this, as well as an intuition to answer all your questions, the best way is for you to learn programming in a proper language such as Python or Javascript. You will quickly realize that formal systems for mathematical logic are miniscule in complexity compared to programming languages, but you will also see clearly the reason for the exacting precision in defining a formal system.

For a concrete example from logic consider the following expression:

$A \lor B \land C$

If a formal system allows such an expression, for some propositions $A,B,C$, it must also tell us what it is supposed to mean? Even simple things like reading from left to right are not taken for granted! In most formal systems that allow this, it would be parsed as a short-form for:

$( A \lor ( B \land C ) )$

where this new sentence is interpreted according to your book's convention.

Note that this has a different meaning from:

$( ( A \lor B ) \land C )$.

So allowing expressions with 'freer form' end up requiring more rules to tell us exactly how to evaluate them. This leads to an advantage of a more rigid system like the one in your book, in that it is easier to prove things about it than about a more complicated system. For instance, proving unique readability is easier!

Anyway here are the answers to your two questions.

(1) ... the number being assigned to a proposition seems like just an artifact we had to use in order to make our language formal.

We don't need the formula numbering for the formalization itself, though the ability to number them uniquely may be useful for proving things about the formal system.

(2) If the unique readability theorem was false, then parenthesis don't behave in the intuitive way we want them to ... While this seems more important, proving that a proposition is uniquely readable does not prove that our intuition of parenthesis is necessarily right.

You're right that this is more useful. We need rules for evaluating expressions; brackets are just arbitrary symbols and meaningless until we use them in evaluation. It is actually non-trivial to define the value of an expression, even for propositional logic. Your book ought to do just that in a subsequent section. There are two main flavours, top-down and bottom-up.

The top-down algorithm is based on the recursive definition of propositional sentences, recursively splitting according to the final boolean connective and evaluating the two subexpressions and then combining and returning the result. [The main issue here is to prove that one can uniquely identify the final boolean connective. The easiest way is by counting open/close-brackets; prove that at any point other than the ends of a propositional sentence the number of open-brackets before that point is greater than the number of close-brackets before that point.]

The bottom-up algorithm captures the intention of using brackets to denote order of evaluation, by repeatedly evaluating the leftmost 'innermost bracketed expression' (a subexpression starting with an open-bracket and ending with a close-bracket and having no brackets in-between) and replaces that expression with a symbol denoting the evaluated value. [The main issue here is to prove that there is such an innermost bracketed expression in the first place. You might ask "Why leftmost?". Well prove that it does not matter!]

The bottom-up algorithm can be implemented by reading from left to right, and at every ")", it backtracks to the last seen "(", and evaluates those symbols in-between, and replaces the bracketed expression with the result. If you think of this in terms of pushing and popping off a stack, it is not much different from how the top-down algorithm would be executed.