show/hide this revision's text 3 added 71 characters in body

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 set 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.
show/hide this revision's text 2 improved formatting

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 set Y of size continuum, 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|Xliminf |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 sufficiently large finite Y subset ΠXn of size k+1 has distinct y,y' in Y with infinitely many common values.

In particular, if the Xn becomes 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.
show/hide this revision's text 1

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 set Y of size continuum, 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, every sufficiently large finite Y subset ΠXn has distinct y,y' in Y with infinitely many common values.

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