1

I am looking for a good introductory text to the theory of quantifier complexity. It can be a chapter in a larger text on logic. I have an understanding of logic already.

Everything I could find online was either advanced, or only a few slides in a powerpoint presentation.

This question is motivated by this answer to an earlier question. I am interested in simplifying formulae, specifically in getting rid of quantifiers over functions $A\to B$, but also more generally in understanding when formulae can and cannot be reduced to simpler ones (e.g. see this question). e.g. I am interested in the arithmetic hierarchy (though I'm not sure how well it captures the specific case where there are quantifiers like $f:A\to A$, which I think would require a multi-sorted theory?)

user56834
  • 12,925
  • What exactly do you mean by "the theory of quantifier complexity?" Do you have a specific context in mind (e.g. the arithmetical hierarchy)? – Noah Schweber Oct 03 '18 at 15:30
  • @NoahSchweber, I am interested in the arithmetical hierarchy yes, and would be interested in something that addresses that. (but the question is motivated by something specific, namely what I referenced in the other question). – user56834 Oct 03 '18 at 15:42
  • @NoahSchweber, I'm not sure where I should look if I want to learn about the arithmetical hierarchy (beyond what's on the wikipedia page) do you have a suggestion? – user56834 Oct 04 '18 at 15:17

0 Answers0