I posted a similar question on math stack exchange with the same title, but I didn't get a helpful response. I am trying to develop a logical language where one can express variable numerical quantifiers. In first order logic, one can express statements like "there exist at most 10 x such that Px" and "there exist exactly 25 x such that Px". But I am trying to develop a language where one can express statements like "there exist at least 3n+1 x such that Px", where the n is itself a variable that can be quantified over. Everytime I come up with a definition, or develop a theory, I look on the Internet and find that someone else has already worked it out better. So, my question is, is there a paper or book where someone develops this kind of logical language?
-
2$\begingroup$ arxiv.org/abs/cs/0211022 $\endgroup$– Emil JeřábekCommented Dec 12, 2013 at 22:33
-
1$\begingroup$ You should wait more than a day before cross-posting. $\endgroup$– Andy PutmanCommented Dec 12, 2013 at 22:33
-
8$\begingroup$ I am kind of surprised by the close votes. Ignoring the cross-posting issue, this is a sensible reference request, and the existence of research on logics with counting may not be obvious to someone not familiar with finite model theory. I’d be inclined to post an answer, if it were not past midnight. $\endgroup$– Emil JeřábekCommented Dec 12, 2013 at 23:08
-
1$\begingroup$ I agree with Emil, both as to the reasonableness of the question and as to the heading, "finite model theory," under which you can find information about such logics. $\endgroup$– Andreas BlassCommented Dec 12, 2013 at 23:37
-
$\begingroup$ If you enumerate the values of x (for instance when they are natural numbers), you don't need an extension of the language, to my opinion. $\endgroup$– Lucas K.Commented Dec 13, 2013 at 22:11
1 Answer
There is an old notion of a generalized quantifier introduced by Andrzej Mostowski in late '50s:
A. Mostowski, "On a generalization of quantifiers", Fundamenta Mathematicae 44, 1957.
The paper is actually well-written, but you may also enjoy reading the following introduction:
J. A. Väänänen, "Generalized Quantifiers, an Introduction", European Summer School in Logic, Language and Information, 1997.
As pointed out by Emil and Andreas in the comments, logics extended by some classes of non-standard quantifiers are interesting from the perspective of finite model theory and descriptive complexity --- here are, for example, some results on second-order generalized quantifiers (however, take into account, that I do not follow recent work on the subject):
A. Andersson, "On second-order generalized quantifiers and finite structures", Annals of Pure and Applied Logic, Volume 115, Issues 1–3, 2002.
Another context where you can find the notion of a generalized quantifier is the study of semantics for natural languages:
S. Peters, D. Westerståhl, "Quantifiers in Language and Logic", Clarendon Press, 2006.
