Pigeonhole Principle for infinite case - MathOverflow

Pigeonhole Principle for infinite case

2010-02-06T21:35:46Z

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

Answer by darij grinberg for Pigeonhole Principle for infinite case

2010-02-06T21:40:30Z

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.

Answer by Inna for Pigeonhole Principle for infinite case

2010-02-06T22:11:16Z

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.

Answer by Joel David Hamkins for Pigeonhole Principle for infinite case

2010-02-07T05:04:01Z

First, let me improve upon the countable counterexample of Darij Grinberg by giving an uncountable counterexample Y. Indeed, I shall give finite sets X_n and a subset Y of the product ΠX_n 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 X_n have 2ⁿ elements, consisting of the binary sequences of length n. Now, for each infinite binary sequence s, let y_s be sequence in the product ΠX_n whose n^th value is s|n, the length n initial segment of s. Let Y consist of all these y_s. 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 y_s and y_t are different. Thus, y_s and y_t have only finitely many common values. So Y is very large counterexample, as desired.

A similar argument works still if the X_n grow more slowly in size, as long as liminf|X_n| = infinity. One simply spreads the construction out a bit further, until the size of the X_i is large enough to accommodate the same idea. That is, if the liminf of the sizes of the X_n'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 X_n have size at most k and Y is a subset of ΠX_n 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_n. But since unboundedly often there are only k possible values in X_n, this is impossible.

In summary, the situation is as follows:

Theorem. Suppose that X_n is finite and nonempty.

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

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