Alright, so I am reading "Computability and Logic" by Boolos and Jeffrey, specifically I'm on chapter 9 "A Precis of First-Order Logic: Syntax. There has been more than a handful of definitions in this chapter, and I believe I've come to be able to understand what each of them are except one in particular which begins on pg. 110. Namely, the following:

"We officially define a string of consecutive symbols within a given formula to be a ${subformula}$ of the given formula if it is itself a formula."

So, I've tried to break this down and see where I am getting confused. I followed entirely what is being said until "...if it is itself a formula." The reason I am getting confused is why is this last part added? I was given a formula shouldn't "it" be a formula if that is what we are given?

Any help would be much appreciated!

  • 1
    $\begingroup$ You were indeed given a formula, but, now you are looking at a substring. That substring may, or, may not be a formula. If it is, it is a subformula of the original formula. $\endgroup$ – James Jan 29 '15 at 3:46
  • $\begingroup$ Awesome! Thanks James! $\endgroup$ – Valentino Jan 29 '15 at 13:29

I don't know what notation B&J use, but the point will be something like this. If you have a formula $$\forall x (P(x)\to(\neg Q(x)))$$ then for example $$x(P$$ is a string of consecutive symbols from this formula. However $x(P$ is not a grammatically (syntactically) correct formula, therefore it is not a subformula.

On the other hand, $P(x)$ is a string of consecutive symbols from the above formula, and $P(x)$ is itself a grammatically correct formula, so $P(x)$ is a subformula of the above.

  • $\begingroup$ Once again David, you are amazing, your explanations are lucid, and you are very kind to help me out! $\endgroup$ – Valentino Jan 29 '15 at 13:29
  • $\begingroup$ David, my class is currently using Computability and Logic for a class named Intermediate Logic. I enjoy the book, but I was wondering if you had any suggestions for a possible supplement? $\endgroup$ – Valentino Feb 3 '15 at 15:04
  • 1
    $\begingroup$ See if these notes help. The notes are copyright so please do not make multiple copies, but you are welcome to keep a (hard or soft) copy for yourself. $\endgroup$ – David Feb 3 '15 at 19:55
  • $\begingroup$ Wow, okay I'll check them out sometime today. Thanks a million David! $\endgroup$ – Valentino Feb 3 '15 at 19:57

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.