Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $ \{ A,B \} $ be a partition of $ \mathbb{N} $ into two infinite subsets. For every $ r \in \mathbb{R}_{> 0} $, can we find an increasing sequence $ (a_{n})_{n \in \mathbb{N}} $ in $ A $ and an increasing sequence $ (b_{n})_{n \in \mathbb{N}} $ in $ B $ such that $ \displaystyle \lim_{n \rightarrow \infty} \frac{a_{n}}{b_{n}} = r $?

share|improve this question
1  
You could try to look at the first-quadrant grid points, and colour the ponts of the form $(b, a), a\in A, b\in B$. Then see if you can guarantee coloured points in an arbitrarily thin cone around any line through the origin with positive finite slope. If it is possible, this would lead to sequences, which would be increasing, although not necessarily strictly. This is just a rephrasing of the question, but it might yield some geometric intuition. –  Arthur Oct 13 '12 at 10:14

3 Answers 3

up vote 5 down vote accepted

For $r=1$, note that there are infinitely many pairs of adjacent elements of $A$ and $B$, whose ratio tends to $1$.

For $r\ne1$, without loss of generality let $r\gt1$. Form sequences $a_n$, $b_n$ such that $|a_n/b_n-r|\lt\frac rn$, and for the sake of contradiction assume that at some point this is no longer possible. That is, for some $k,n\in\mathbb N$ there is no pair $a_n\in A$ and $b_n\in B$ such that $a_n,b_n\ge k$ and $|a_n/b_n-r|\lt\frac rn$.

Pick some $b\in B$ with $b\ge k$. If necessary, increase $n$ to ensure $r(1-\frac1n)\gt1$. Then none of the natural numbers between $br(1-\frac1n)$ and $br(1+\frac1n)$ is in $A$. Therefore they are in $B$, and we can apply the same argument to them. Thus for all $m\in\mathbb N$ none of the numbers between $br^m(1-\frac1n)^m$ and $br^m(1+\frac1n)^m$ is in $A$. But at some point $r^{m+1}(1+\frac1n)^{m+1}\gt r^m(1-\frac1n)^m$, so the intervals overlap and cover the rest of $\mathbb N$ from that point on, contradicting the fact that $A$ is infinite.

The contradiction shows that contrary to the assumption the sequence can be extended indefinitely.

(I glossed over some rounding issues, but I think it's clear enough that by going to sufficiently high numbers we can ensure that the intervals grow by a constant factor even when restricted to the natural numbers they contain.)

share|improve this answer

Answer: yes.

Choose an element $a_1$ of $A$, and then look for the element $b_i$ in $B$ that is closest to $r\cdot a_1$. Let $r_1=\frac{a_1}{b_1}$.

Then, repeat this procedure:

Choose an element $a_{i+1}$ in $A$ that satisfies $a_i< a_{i+1}$, and look for a $b_{i+1}\in B$, which satisfies $b_i<b_{i+1}$ and $\left\vert r-\frac{a_{i+1}}{b_{i+1}}\right\vert<\frac{1}{2}\cdot\left\vert r-r_i\right\vert$. If you have found a $b_{i+1}$, then let $r_{i+1}=\frac{a_{i+1}}{b_{i+1}}$, and you can go on with repeating the procedure.

If you can not find any $b_{i+1}$, take the next element of $A$, and look again for a $b_{i+1}$. [end procedure]

If we can proove that it will always take finitely many steps to find an $a_{i+1}$ for wich there exists such a $b_{i+1}$, the proof is complete. (Because the distance between $r_i$ and $r$ is smaller than $\frac{1}{2^{i-1}\cdot|r-r_1|}$, which converges to $0$.)

Thus, we look for $a$ and $b$ such that for every $r,r_i$ we have $\left\vert r-\frac{a}{b}\right\vert<\frac{1}{2}\cdot\left\vert r-r_i\right\vert$. One possibility is that $r-\frac{a}{b}<\frac{1}{2}(r-r_i)$, supposing that $r_i<r$ for all $i$. Rewrite it like $a>\frac{b}{2}(r+r_i)$. It is obvious that for $a$ large enough we can find such a $b$, since both partitions are infinite.

Only thing we have to do is that for $i=1$ we can find such $a$ and $b$. But any $a_1>r\cdot b_1$ satisfies the condition.

Am i right ?

share|improve this answer

Many thanks go to Barto and Joriki for their valuable insights. What follows is simply a reorganization of the solutions of these two gentlemen. All credit, therefore, goes to them and to them only.

Let $ r \in \mathbb{R}_{>1} $, and choose an $ \epsilon \in (0,r - 1) $.

Claim For every $ N \in \mathbb{N} $, there exists $ (a,b) \in (A \cap \mathbb{N}_{>N}) \times (B \cap \mathbb{N}_{>N}) $ such that $ \displaystyle \left| r - \frac{a}{b} \right| < \epsilon $.

Proof of claim By way of contradiction, assume that the claim is false. Then there exists an $ N \in \mathbb{N} $ such that the inequality $ \displaystyle \left| r - \frac{a}{b} \right| < \epsilon $ has no solution for $ (a,b) \in (A \cap \mathbb{N}_{>N}) \times (B \cap \mathbb{N}_{>N}) $. As the inequality $ \displaystyle \left| r - \frac{a}{b} \right| < \epsilon $ is equivalent to $ b(r - \epsilon) < a < b(r + \epsilon) $, it follows that $ (b(r - \epsilon),b(r + \epsilon)) \cap \mathbb{N} \subseteq B $ for all $ b \in B \cap \mathbb{N}_{>N} $.

Now, the gist of Barto's and Joriki's observation is that for a fixed $ b \in B \cap \mathbb{N}_{>N} $, the following proposition is true: \begin{equation} \forall k \in \mathbb{N}: \quad (b(r - \epsilon)^{k},b(r + \epsilon)^{k}) \cap \mathbb{N} \subseteq B. \end{equation} We prove this by induction. When $ k = 1 $, the proposition is true by the previous paragraph. Next, suppose that the proposition is true for $ k = l $. Pick any $ n \in (b(r - \epsilon)^{l},b(r + \epsilon)^{l}) \cap \mathbb{N} $. As $ n \in B $ by the induction hypothesis, and as $ n > b(r - \epsilon)^{l} > N \cdot 1 = N $, we see that $ n \in B \cap \mathbb{N}_{>N} $. We may thus apply the argument in the previous paragraph to deduce that $ (n(r - \epsilon),n(r + \epsilon)) \cap \mathbb{N} \subseteq B $. However, this is true for all $ n \in (b(r - \epsilon)^{l},b(r + \epsilon)^{l}) \cap \mathbb{N} $, so we can conclude that $ (b(r - \epsilon)^{l+1},b(r + \epsilon)^{l+1}) \cap \mathbb{N} \subseteq B $. The proposition is therefore true for $ k = l + 1 $, and by induction, it is true for all $ k \in \mathbb{N} $.

Finally, observe that the collection of intervals $ \{ (b(r - \epsilon)^{k},b(r + \epsilon)^{k}) \}_{k \in \mathbb{N}} $ must cover $ \mathbb{R} $ from some point on. To prove this, it suffices to show that the left-endpoint of the interval $ (b(r - \epsilon)^{k+1},b(r + \epsilon)^{k+1}) $ is less than the right-endpoint of the interval $ (b(r - \epsilon)^{k},b(r + \epsilon)^{k}) $ for all $ k \in \mathbb{N} $ large enough. However, this is true because \begin{equation} \lim_{k \rightarrow \infty} \frac{b(r - \epsilon)^{k+1}}{b(r + \epsilon)^{k}} = \lim_{k \rightarrow \infty} \left( \frac{r - \epsilon}{r + \epsilon} \right)^{k} (r - \epsilon) = 0. \end{equation} We thus see that $ (b(r - \epsilon)^{k},\infty) \cap \mathbb{N} \subseteq B $ for all $ k \in \mathbb{N} $ large enough, which contradicts the hypothesis that $ A $ is infinite. The assumption is therefore false, and the claim is proven. Q.E.D.

The claim is now sufficient to prove the case when $ r > 1 $ or $ 0 < r < 1 $. The case $ r = 1 $ is settled by taking pairs of adjacent numbers in $ A $ and $ B $, as Joriki has mentioned.

share|improve this answer
    
I don't understand this version. How does it help that the intervals for $b$ and $b+1$ overlap? We don't know whether there are any adjacent numbers in $B$. For all we know without an iterated argument, $B$ could be increasingly sparse and the intervals $(b(r-\epsilon),b(r+\epsilon))$ could remain disjoint for all $b\in B$. –  joriki Oct 14 '12 at 6:56
    
@Joriki: The interval $ (b(r - \epsilon),b(r + \epsilon)) $ may not contain a natural number, but if it does, then that natural number must belong to $ B $. However, we know that $ \{ (b(r - \epsilon),b(r + \epsilon)) \,|\, b \in \mathbb{N}_{>N} \text{ large enough} \} $ covers $ \mathbb{R} $ from some point on (I am not referring to a cover of $ \mathbb{N} $ from some point on but to a cover of $ \mathbb{R} $), so any natural numbers in that region must belong to $ B $, making no room for $ A $ to make an appearance. Contradiction. –  Haskell Curry Oct 14 '12 at 16:48
    
Sorry, I still don't understand. I wasn't making a distinction between real and natural numbers. I agree that $\{(b(r-\epsilon),b(r+\epsilon))\,|\,b\in\mathbb{N}_{>N}\text{ large enough}\}$ covers $\mathbb R$. But I don't understand how you conclude that any natural numbers in that region must belong to $B$. Your use of the variable $b$ appears to suggest that you intend all the $b$'s to be in $B$ (and then what you want to conclude would indeed follow), but I don't see where you're getting that from -- other than the letter $b$, nothing you're written tells me that those $b$'s are in $B$. –  joriki Oct 14 '12 at 17:17
    
Hi Joriki. Yes, I finally got your point. Well, I've made some changes, so the argument should be correct this time. It turns out to be very similar to your argument, so I'm half-thinking of deleting this post anyway. Thanks! –  Haskell Curry Oct 14 '12 at 20:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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