Pigeonhole Principle for infinite case - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:33:32Z http://mathoverflow.net/feeds/question/14431 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14431/pigeonhole-principle-for-infinite-case Pigeonhole Principle for infinite case unknown (google) 2010-02-06T21:35:46Z 2010-02-10T11:22:36Z <p>Suppose $X_n$ are finite sets for any natural integer $n$. let $Y$ be an infinite subset of $\prod_n X_n$. Do there exist $y$ and $y'$ in $Y$ and an infinite subset $S$ of $\mathbb N$ such that $y_n=y'_n$ for all $n$ in $S$?</p> http://mathoverflow.net/questions/14431/pigeonhole-principle-for-infinite-case/14433#14433 Answer by darij grinberg for Pigeonhole Principle for infinite case darij grinberg 2010-02-06T21:40:30Z 2010-02-06T21:40:30Z <p>What about $X_n=\left\lbrace 1,2,3,...,n\right\rbrace$, and $Y$ consisting of the sequences $\left(1,1,1,...,1,2,3,4,5,6,...\right)$ with $n$ ones for all $n\in\mathbb N$?</p> <p>The first true thing that comes into my mind when I hear "Pigeonhole Principle for infinite case" are some theorems in infinite Ramsey theory, such as <a href="http://en.wikipedia.org/wiki/Ramsey%27s%5Ftheorem#Infinite%5FRamsey%5Ftheorem" rel="nofollow">this one</a>.</p> http://mathoverflow.net/questions/14431/pigeonhole-principle-for-infinite-case/14434#14434 Answer by Inna for Pigeonhole Principle for infinite case Inna 2010-02-06T22:11:16Z 2010-02-07T05:18:23Z <p>I think that what you are asking for is impossible. Given any element of $\prod_n X_n$ the element is uniquely determined by its image in each of the individual $X_n$'s. So if two elements of $Y$ agree on each $X_n$ then they must be the same element.</p> <p>In language similar to yours, what you probably want for the finite case is "If $X$ and $Y$ are finite sets such that $|X| &lt; |Y|$ and $f:Y\rightarrow X$ is any map then there exists an element $x\in X$ such that $|f^{-1}(x)| > x$." More generally, given any finite sequence $X_1,\ldots,X_n$ of finite sets and any set $Y$ such that $|Y| > |X_1|\cdot|X_2|\cdots|X_n|$ and any sequence of maps $f_i:Y\rightarrow X_i$ then there exists a sequence of elements $x_1,\ldots,x_n$ and two elements $y,y'\in Y$ such that $f_i(y) = f_i(y')$ for any $i$.</p> <p>The problem with the infinite case is that there are injective but not surjective maps between infinite sets with the same cardinality. However, it is true that given a sequence of finite sets $X_1,X_2,\ldots$ and a set $Y$ with cardinality greater than that of $\prod X_n$, if you have any sequence of maps $f_i:Y\rightarrow X_i$ then there exists an uncountable subset $Z\subseteq Y$ such that for any two elements $z,z'$ of $Z$ you have $f_i(z) = f_i(z')$ for all $i$.</p> <p>In even more generality, I believe that if you have any set of sets ${X_\alpha}$ and any set $Y$ such that the cardinality of $Y$ is larger than the cardinality of $\prod_\alpha X_\alpha$ then you have a similar statement.</p> http://mathoverflow.net/questions/14431/pigeonhole-principle-for-infinite-case/14466#14466 Answer by Joel David Hamkins for Pigeonhole Principle for infinite case Joel David Hamkins 2010-02-07T05:04:01Z 2010-02-07T05:34:05Z <p>First, let me improve upon the countable counterexample of Darij Grinberg by giving an <em>uncountable</em> counterexample Y. Indeed, I shall give finite sets X<sub>n</sub> and a subset Y of the product &Pi;X<sub>n</sub> having size continuum (that is, as large as possible), such that any two distinct y, y' in Y have only finitely many common values.</p> <p>Let X<sub>n</sub> have 2<sup>n</sup> elements, consisting of the binary sequences of length n. Now, for each infinite binary sequence s, let y<sub>s</sub> be sequence in the product &Pi;X<sub>n</sub> whose n<sup>th</sup> value is s|n, the length n initial segment of s. Let Y consist of all these y<sub>s</sub>. Since there are continuum many s, it follows that Y has size continuum.</p> <p>Note that if s and t are distinct binary sequences, then eventually the initial segments of s and t disagree. Thus, eventually, the values of y<sub>s</sub> and y<sub>t</sub> are different. Thus, y<sub>s</sub> and y<sub>t</sub> have only finitely many common values. So Y is very large counterexample, as desired.</p> <p>A similar argument works still if the X<sub>n</sub> grow more slowly in size, as long as liminf|X<sub>n</sub>| = infinity. One simply spreads the construction out a bit further, until the size of the X<sub>i</sub> is large enough to accommodate the same idea. That is, if the liminf of the sizes of the X<sub>n</sub>'s is infinite, then one can again make a counterexample set Y of size continuum.</p> <p>In contrast, in the remaining case, there are no infinite counterexamples. I claim that if infinitely many X<sub>n</sub> have size at most k and Y is a subset of &Pi;X<sub>n</sub> having k+1 many elements, then there are distinct y,y' in Y having infinitely many common values. To see this, suppose that Y has the property that distinct y, y' in Y have only finitely many common values. In this case, any two y, y' must eventually have different values. So if Y has k+1 many elements, then eventually for sufficiently large n, these k+1 many sequences in Y must be taking on different values in every X<sub>n</sub>. But since unboundedly often there are only k possible values in X<sub>n</sub>, this is impossible.</p> <p>In summary, the situation is as follows:</p> <p><b>Theorem.</b> Suppose that X<sub>n</sub> is finite and nonempty.</p> <ul> <li>If liminf |X<sub>n</sub>| is infinite, then there is Y subset &Pi;X<sub>n</sub> of size continuum, such that distinct y, y' in Y have only finitely many values in common.</li> <li>Otherwise, infinitely many X<sub>n</sub> have size at most k for some k, and in this case, every Y subset &Pi;X<sub>n</sub> of size k+1 has distinct y,y' in Y with infinitely many common values.</li> </ul> <p>In particular, if the X<sub>n</sub> become increasingly large in size, then there are very bad counterexamples to the question, and if the X<sub>n</sub> are infinitely often bounded in size, then there is a very strong positive answer to the question.</p>