6
$\begingroup$

In Mendelson's book ("Introduction to mathematical logic") he defines truth values for sentences in the propositional calculus using truth tables. However, it seems to me he assumes implicitly that every well-formed sentence (what he calls "statement form") has a unique parsing; i.e. it is impossible for the same statement form to arise in two different ways.

This is of course correct, but it requires a proof. The omission of such proof (or even mentioning it is needed) is somewhat surprising for me as Mendelson's book is otherwise very explicit about everything. Am I missing something?

Improve this question
$\endgroup$
  • $\begingroup$ Disclaimer: not expert on formal logic, but I find this question interesting. So you're saying that given a set of deductive rules defining well-formed formulas, prove that any WFF has a unique parsing? How would one define parsing, and unique parsing? By mapping to parse trees? or by defining a confluent mapping to, say, a canonical WFFs (e.g. infex)? $\endgroup$ – user2468 Mar 13 '12 at 18:21
  • 3
    $\begingroup$ @J.D.: one example of a book that does do this rigorously is Enderton's book A Mathematical Introduction to Logic. He does this by defining an algorithm to perform the parsing and examining the algorithm in detail. A key step is that no proper initial segment of a well formed formula (as Enderton has defined them) can be a well formed formula. $\endgroup$ – Carl Mummert Mar 13 '12 at 18:54
  • 2
    $\begingroup$ @J.D.: Another example of a text that proves "unique readability" is Shoenfield's "Mathematical Logic." In that case it is quite important because he introduces a syntax without parentheses in prefix (Polish) notation (so what is usually written "$(\exists x ) (\neg ( x = x ) \vee ( \exists y ) ( x = y ) )$" is rendered "$\exists v \vee \neg = x x \exists y = x y$") and so you cannot take advantage of a quick "unique pairing of parentheses" fact to get unique parsing. $\endgroup$ – user642796 Mar 13 '12 at 19:35
  • $\begingroup$ @J.D.: Yes, you prove that every WFF has a unique parse tree, or generating sequence, or whatever; the important thing is it will have a unique "something you define the truth value by". $\endgroup$ – Gadi A Mar 14 '12 at 5:46
10
$\begingroup$

No, you're not missing anything. Mendelson does define a "statement form" to be a kind of expression, and does not go out of his way to prove unique readability or to prove that if you had unique readability then this would lead to his claim that each statement form determines a unique function of its variables.

But, to be charitable, the entire section is somewhat conversational, and it's right at the beginning, so the author might view these things as particularly simple and not want to spend time proving them if he thinks that would delay getting into more interesting material. It is not uncommon in textbooks for authors to make various claims that have to be verified by the reader, without dwelling on how the claims would be proved.

Improve this answer
$\endgroup$
  • $\begingroup$ Do you mean "not uncommon"? $\endgroup$ – Robert Israel Mar 13 '12 at 19:16
  • $\begingroup$ @Robert Israel: thanks, I did. $\endgroup$ – Carl Mummert Mar 13 '12 at 19:24
  • 1
    $\begingroup$ Thank you. As I've said, my surprise comes from Mandelson not even mentioning the need for such a proof; he really hides some very nontrivial work that the beginning student won't even know he needs to do. $\endgroup$ – Gadi A Mar 14 '12 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.