This is perhaps a stupid question, but I ask it anyway. It seems to me that the semantic comes after and it cannot change the complexity of the language. I ask the question, because Herbert B. Enderton in https://plato.stanford.edu/archives/spr2008/entries/logic-higher-order/ wrote:

We have seen that, although the set V¹ of valid formulas of first-order logic is computably enumerable, the corresponding set V² for second-order logic (with the standard semantics) is vastly more complex. This phenomenon does not continue into the higher orders.

Why did he had to specify "with the standard semantics"? I am learning and checking my understanding, perhaps on a detail. The context is that, with the Henkin semantic, this language is equivalent to many-sorted first order logic with the comprehension axioms. Is it correct to say that, nevertheless, the language itself remains non recursively enumerable, even if it is equivalent (in terms of interpretations) to a language that is recursively enumerable? I am checking if I have missed something.


Usually "valid" means "true in every interpretation", and the semantics determines what it is we consider to be an "interpretation" at all.

So depending on which semantics we use, the description "the set of all valid second-order formulas" will mean two different sets of formulas, and it should not be mysterious that one of those sets can be r.e. while the other isn't.

Standard semantics considers fewer possible interpretations than Henkin semantics -- specifically, a Henkin interpretation where the set variables range over only some subsets of the universe is not a standard interpretation. Having fewer interpretations makes is easier for a formula to be valid: the set of standardly valid formulas is larger than the set of Henkin valid formulas.

Note that speaking of "the language" here makes your question a bit confusing to understand, because it is not clear whether you mean the definition of which strings of symbols are formulas at all (as "language" is often used in logic), or the particular set of formulas that you're trying to decide or enumerate (as "language" is often used in computability theory).

  • $\begingroup$ Yes, it was confusing, because I was confused between these two notions myself. Well, I suppose it was a stupid question, only showing that I was ignorant on something basic, but now I am less ignorant. I'll comeback and accept the answer after I learned more and reached a status where I feel I have some authority to do so. $\endgroup$ – Dominic108 May 30 '18 at 2:03
  • $\begingroup$ I also learned the expression "the set variables" reading your answer. $\endgroup$ – Dominic108 May 30 '18 at 2:40
  • $\begingroup$ @Dominic108: Some presentations would say "predicate variables" instead of "set variables". $\endgroup$ – Henning Makholm May 30 '18 at 10:50

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.