2
$\begingroup$

Well, I know that I'm going to have some vote-down, because this should be a very simple property but the real story is that... I am not able to prove it!

For any fixed $n\in\mathbb N$, I have a finite partition of the natural numbers

$$ \mathbb N=A_1^n\cup...\cup A_{k(n)}^n $$

(every set of the partition is infinite). Suppose that the sequence $k(n)$ is bounded. I want to make a choice of a set $A_{i_n}^n$ for each partition such that $A=\bigcap_{n=1}^\infty A_{i_n}^n$ is infinite.

Intuitively this should be possible, and I have a sketch of the proof making use of the upper density on natural numbers, but I don't think it is completely right and anyway it sounds a bit too complicated.

Motivation: I am basically extracting infinite subsequences from a sequence and I want to be sure to find, at the end of the story, a subsequence.

$\endgroup$
4
  • 7
    $\begingroup$ What if the $n$th partition splits the naturals into ten pieces based on the $n$th digit of the decimal expansion? $\endgroup$ Dec 5, 2011 at 18:27
  • $\begingroup$ To sharpen Clinton Conley's remark: take $k(n)=2$ for each $n$, and look at the binary expansion of each natural number... $\endgroup$
    – Yemon Choi
    Dec 5, 2011 at 18:55
  • 2
    $\begingroup$ @Clinton Conley - why not post that as an answer, so the question can be put to bed? $\endgroup$
    – Yemon Choi
    Dec 5, 2011 at 18:56
  • 1
    $\begingroup$ On the other hand, judging from your motivation, what you probably what to do is take a free ultrafilter $U$ on $\mathbb{N}$ and choose your $i_n$ such that $A_{i_n}\in U$. The $A_{i_n}$ can then be diagonalized to choose your subsequence. $\endgroup$ Dec 5, 2011 at 21:11

2 Answers 2

12
$\begingroup$

As requested, here's the comment posted as an answer:

What if the $n$th partition splits the naturals into ten pieces based on the $n$th digit of the decimal expansion?

(Of course ten is chosen for familiarity and not for optimality.)


Apologies for such an extensive edit, but I couldn't visualize this either, and this doesn't fit into a comment. Using binary (and indexing from 0) instead of base 10 gives: $$A_0^0 = evens, A_1^0 = odds$$ $$A_0^1 = (0\bmod 4)\cup(1\bmod 4), A_2^1 = (2\bmod 4)\cup(3\bmod 4)$$ $$A_0^n = \{ n \in {\mathbb N} \colon 0\leq n\bmod 2^{n+1} <2^n\}, A_1^n = \{ n \in {\mathbb N} \colon 2^n\leq n\bmod 2^{n+1} <2^{n+1}\},$$ But now $$\bigcap_{i=0}^n A_{i_n}^n$$ is a single congruence class modulo $2^{n+1}$ for any choice of $i_n$, and the second positive element of a congruence class must be at least as large as the modulus, and the modulus goes to infinity, so the infinite intersection cannot have two elements.

$\endgroup$
3
  • 1
    $\begingroup$ Sorry, but maybe I don't understand what you have in mind. It seems to me that the set $A_{10}^n$, for $n\geq2$, contains all the natural numbers having less then $n$ digits plus the natural numbers having more than $n$ digits but having $0$ at the $n$-th place. So, $A_{10}^n$, for $n\geq2$ contains $1,10,100,1000,...$. Now this set is also contained in $A_1^1$, and the here is the choice with infinite intersection. $\endgroup$ Dec 5, 2011 at 19:38
  • 1
    $\begingroup$ I am counting the digits from the right. So (switching the index sets slightly) $A^n_i$ consists of those natural numbers with the digit $i$ in the $10^n$ place of the decimal expansion. $\endgroup$ Dec 5, 2011 at 20:01
  • 4
    $\begingroup$ This last edit seems a bit extreme to me. Wouldn't it make more sense to supply your own answer if you found mine confusing? $\endgroup$ Dec 5, 2011 at 20:22
0
$\begingroup$

I think Clinton Conley intended for the $n$th digit to be read from the right (one's digit is the first, ten's digit is the second, etc.).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.