# Pigeonhole Principle for infinite case

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$?

• You should insist that y, y' are distinct, since otherwise y=y' means the answer is trivially yes. Feb 7, 2010 at 3:26

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$?

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 this one.

First, let me improve upon the countable counterexample of Darij Grinberg by giving an uncountable counterexample Y. Indeed, I shall give finite sets Xn and a subset Y of the product ΠXn having size continuum (that is, as large as possible), such that any two distinct y, y' in Y have only finitely many common values.

Let Xn have 2n elements, consisting of the binary sequences of length n. Now, for each infinite binary sequence s, let ys be sequence in the product ΠXn whose nth value is s|n, the length n initial segment of s. Let Y consist of all these ys. Since there are continuum many s, it follows that Y has size continuum.

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 ys and yt are different. Thus, ys and yt have only finitely many common values. So Y is very large counterexample, as desired.

A similar argument works still if the Xn grow more slowly in size, as long as liminf|Xn| = infinity. One simply spreads the construction out a bit further, until the size of the Xi is large enough to accommodate the same idea. That is, if the liminf of the sizes of the Xn's is infinite, then one can again make a counterexample set Y of size continuum.

In contrast, in the remaining case, there are no infinite counterexamples. I claim that if infinitely many Xn have size at most k and Y is a subset of ΠXn 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 Xn. But since unboundedly often there are only k possible values in Xn, this is impossible.

In summary, the situation is as follows:

Theorem. Suppose that Xn is finite and nonempty.

• If liminf |Xn| is infinite, then there is Y subset ΠXn of size continuum, such that distinct y, y' in Y have only finitely many values in common.
• Otherwise, infinitely many Xn have size at most k for some k, and in this case, every Y subset ΠXn of size k+1 has distinct y,y' in Y with infinitely many common values.

In particular, if the Xn become increasingly large in size, then there are very bad counterexamples to the question, and if the Xn are infinitely often bounded in size, then there is a very strong positive answer to the question.

• Actually, you don't even need the X_n's to grow. If you have X_n = {0,1} and you let Y be the interval [0,1], and let f:Y -> X_n be the nth digit of Y in base 2 you get the same phenomenon. (This also points out a problem with what I had previously said.) What you in fact need is you need a larger set mapping to a smaller set. Since the product of a countable number of finite sets can be uncountable you don't necessarily have this.
– Inna
Feb 7, 2010 at 5:21
• @Inna: What you are saying is not correct. If X_n has only two elements, then my argument shows that in any subset Y of the product, with at least three sequences in it, there will be two with infinitely many common values. After all, if y and y' have only finitely many binary digits in common, then any y'' with have to agree with one of them infinitely often, since there are no other digits available. Feb 7, 2010 at 5:26

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.

In language similar to yours, what you probably want for the finite case is "If $X$ and $Y$ are finite sets such that $|X| < |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$.

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$.

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.