Combinatorics and quantifiers
Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996) no. 3, pp. 433-443
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
Let $\binom{I}{m}$ be the set of subsets of $I$ of cardinality $m$. Let $f$ be a coloring of $\binom{I}{m}$ and $g$ a coloring of $\binom{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:\binom{I}{m}\rightarrow k$ is called the {\sl $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.
Let $\binom{I}{m}$ be the set of subsets of $I$ of cardinality $m$. Let $f$ be a coloring of $\binom{I}{m}$ and $g$ a coloring of $\binom{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:\binom{I}{m}\rightarrow k$ is called the {\sl $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.
@article{CMUC_1996_37_3_a0,
author = {Ne\v{s}et\v{r}il, Jaroslav},
title = {Combinatorics and quantifiers},
journal = {Commentationes Mathematicae Universitatis Carolinae},
pages = {433--443},
year = {1996},
volume = {37},
number = {3},
mrnumber = {1426908},
zbl = {0881.05096},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMUC_1996_37_3_a0/}
}
Nešetřil, Jaroslav. Combinatorics and quantifiers. Commentationes Mathematicae Universitatis Carolinae, Tome 37 (1996) no. 3, pp. 433-443. http://geodesic.mathdoc.fr/item/CMUC_1996_37_3_a0/