Ezra's Research

For a bit of light bedtime reading, I'm going through Raymond Smullyan's book First-Order Logic. It's a proper math book, not one of his popular fantasias like The Lady or the Tiger, and it was first published in 1968.

One of the things that strikes me is how mired in mechanics it is. He defines propositional formulae, as you might expect, as formed from variables, negations, and parenthesized binary connectives, and then he is at pains to point out that every proposition uniquely decomposes as either a variable, a negation, or a parenthesized binary connective. He cites proofs from Church and Kleene.

I spent ages going back and forth trying to decide what the difference between the definition and the lemma was, or to see what the supposed proof obligation was here.

Finally it dawned on me that he sees his formulae as essentially strings of symbols, rather than terms per se, and so the "uniqueness of decomposition" was essentially saying that there is a unique way to parse these symbol-strings as terms. To my modern eyes, it never occurred to me that the definition itself would be interpreted as anything but a definition about terms, or trees.

He goes on to note that, whereas his definition provided for connectives formed as, for example, (X /\ Y), they could have been defined as (X) /\ (Y). Three pages are spent on all this fuss over parentheses, and the equivalence between their different placements! When I didn't even see the parentheses as objects in the first place—they were just notation. How times have changed, for the better.