Combinatorics and quantifiers. (English) Zbl 0881.05096

Summary: Let \(\tbinom {I}{m}\) be the set of subsets of \(I\) of cardinality \(m\). Let \(f\) be a coloring of \(\tbinom {I}{m}\) and \(g\) a coloring of \(\tbinom {I}{m}\). We write \(f \rightarrow g\) if every \(f\)-homogeneous \(H\subseteq I\) is also \(g\)-homogeneous. The least \(m\) such that \(f \rightarrow g\) for some \(f : \tbinom {I}{m} \rightarrow k\) is called the \(k\)-width of \(g\) and denoted by \(w_k(g)\). In the first part of the paper we prove the existence of colorings with high \(k\)-width. In particular, we show that for each \(k>0\) and \(m>0\) there is a coloring \(g\) with \(w_k(g) = m\). In the second part of the paper we give applications of wide colorings in the theory of generalized quantifiers. In particular, we show that for every monadic similarity type \(t = (1,\ldots ,1)\) there is a generalized quantifier of type \(t\) which is not definable in terms of a finite number of generalized quantifiers of a smaller type.


05C55 Generalized Ramsey theory
03C80 Logic with extra quantifiers and operators
Full Text: EuDML