Lecture Notes in Computer Science, 1999, Volume 1754/1999, 124-139, DOI: 10.1007/3-540-46583-9_6

Ramsey Theory Is Needed for Solving Definability Problems of Generalized Quantifiers

Kerkko Luosto

View Related Documents

Abstract

In recent years, generalized quantifiers (see [H3]) have received quite a lot of novel interest because of their applications to computer science and linguistics. Their definability theory has made considerable progress during the last decade, which will be the subject of the next section. The proofs of many of these results often use results of Ramsey theory, such as theorems of van derWaerden and Folkman, and yet, the answers to some of the definability problems seem obvious from the outset. This raises the natural question whether Ramsey theory is really needed in the proofs (cf. [vBW]) or whether easier ways of proof might be discovered. The purpose of this paper is to argue in favour of the former and to convince the reader of the cruciality of Ramsey theory for quantifier definability theory.
1991 Mathematics Subject Classification: 03C80, 05D10.

Fulltext Preview

Image of the first page of the fulltext document