Cofinal set is uncountable

Consider sequences of natural numbers. We say that a sequence $a$ majorizes $b$, notation $a\succ b$, if $$\lim_{n\to \infty}\frac{b_n}{a_n}=0.$$
We call a set of sequences $C$ cofinal if for any sequence $v$ there is $u\in C$ such that $u$ majorizes $v$.


$\textbf{Statement}.$ Every cofinal set is uncountable.

$\textbf{Proof}.$ The proof is utilization of Cantor's diagonal argument.
Assume $C$ is a cofinal countable set, denote its elements as $a^k$ for $k=1,2,3,\ldots$. First of all observe that $\succ$ is a transitive relation and for any finite set of sequences, there is a sequence $u$ which majorizes all of them (consider $n$ times the pointwise maximum).
Construct a sequence of sequences $b^k$ as follows -
take $b^1_n=\max\{a^1_1,\ldots,a^1_n\}$. Suppose we have constructed $b^j$ for $j=1,\ldots,k$. Construct $b^{k+1}$ as an nondecreasing sequence which majorizes all of $a^i$ for $i=1,\ldots,k+1$ and $b^j$ for $j=1,\ldots,k$.
Thus $b^j\succ a^j$ and $b^{j+1}\succ b^j$ and each $b^j$ is nondecreasing sequence.
Let $n_1$ be such that $\displaystyle \frac{b^1_{j}}{b^{2}_j}<\frac{1}{2}$ for $j\ge n_1$. Now for $i>1$ take $n_i \ge\max\{i, \ n_{i-1}\}$ and such that $\displaystyle \frac{b^i_{j}}{b^{i+1}_j}<\frac{1}{2}$ for $j\ge n_i$ . Now define $c_k=b_{n_k}^k$. Take some $a^j$ ($j$ fixed) and we know $b^j\succ a^j$. Now take $k>j$. We have $$\frac{b^j_{n_k}}{c_k}=\frac{b^j_{n_k}}{b_{n_k}^k}=\frac{b^{k-1}_{n_{k}}}{b_{n_k}^k}\cdot \frac{b^{k-2}_{n_{k}}}{b_{n_{k}}^{k-1}}\cdots \frac{b_{n_k}^{j}}{b_{n_k}^{j+1}}.$$ Since $n_k\ge n_i$ when $k>i$ we have that $$\frac{b^{i+1}_{n_{k}}}{b^i_{n_k}}< \frac{1}{2}$$ for $i\in\{j,\cdots k-1\}$. Thus using the above form we have $$\frac{b^j_{n_k}}{c_k}<\frac{1}{2^{k-j}}$$ Since $b^j$ is noncreasing and $n_k\ge k$ we have $$\frac{b^j_{k}}{c_k}\le \frac{b^j_{n_k}}{c_k}<\frac{1}{2^{k-j}}.$$ This means that $c\succ b^j$ for all $j$. Since $b^j\succ a^j$ we see that $c\succ a_j$ for all $j$ which contradicts the fact that $C$ is cofinal.

Comments

Post a Comment

Popular posts from this blog

Basel problem type sum, proposed by prof. Skordev

Evaluate $$\sum_{n=1}^{\infty}\frac{1}{2^n n^2}.$$ Proof. The function $$S(x):=\sum_{n=1}^{\infty}\frac{x^n}{ n^2}$$ is well defined for $x\in[-1,1]$ and thus we need to find $S(1/2)$. Using differentiation, we observe that $$S(x)=-\int_0^x\frac{\log(1-t)}{t}\text{d}t.$$ If we make change of variables in the latter integral $t\to 1-t$ we obtain $$S(x)=-\int_{1-x}^1\frac{\log t}{1-t}\text{d}t. \ \ \ \ \ (1)$$ On the other hand, using integration by parts, we obtain $$S(x)=-\int_0^x\log(1-t)\text{d}\log t=-\log t\log(1-t)\Big|_{t=0}^x-\int_0^x\frac{\log t}{1-t}\text{d}t.$$ Notice that $\displaystyle \lim_{t\to 0}\log t \log(1-t)=0$ ($\log (1-t)\sim t$ and then L'Hopital), hence $$S(x)=-\int_0^x\log(1-t)\text{d}\log t=-\log x\log(1-x)-\int_0^x\frac{\log t}{1-t}\text{d}t. \ \ \ \ \ (2)$$ Plugging $x=1/2$ and equating $(1)$ to $(2)$ we obtain $$\int_{1/2}^1\frac{\log(1-t)}{t}\text{d} t-\int_{0}^{1/2}\frac{\log(1-t)}{t}\text{d} t= \log\left(\frac{1}{2}\right)^2.$$ On the ot...
Read more

A problem proposed by prof. Babev

Consider the sequence $$a_n=\int_{n}^{n+1}\frac{\sin^2(\pi t)}{t}\text{d}t.$$ It could be proven that $$\lim_{n\to \infty}n a_n=\frac{1}{2}$$  Now we are going to prove that $$\lim_{n\to\infty}n\left(na_n-\frac{1}{2}\right)=-\frac{1}{4} $$ and show how to derive all such limits. $\textbf{Proof.}$ Since $\displaystyle\int_{n}^{n+1}\sin^2(\pi t)\text{d}{t}=\frac{1}{2}$ (for any $n\in \mathbb{N}$) we can rewrite the limit in question as $$\lim_{n\to \infty}n\left(n\left(\int_{n}^{n+1}\frac{\sin^2(\pi t)}{t}\text{d}t-\int_{n}^{n+1}\frac{\sin^2(\pi t)}{n}\text{d}t\right)\right)=\lim_{n\to \infty}n^2\left(\int_{n}^{n+1}\sin^2(\pi t)\left(\frac{1}{t}-\frac{1}{n}\right)\text{d}t\right)$$ $$=\lim_{n\to \infty}n\left(\int_{n}^{n+1}\sin^2(\pi t)\frac{n-t}{t}\text{d}t\right)$$ Changing the variables $t\to n+s$ and using periodicity of sine, the last simplifies to $$ \lim_{n\to \infty}n\int_{0}^{1}\sin^2(\pi s)\frac{-s}{n+s}\text{d}s$$ Since for $s\in[0,1]$, $\displaystyle \...
Read more

Modification on a sequence from VJIMC

The first two limits of the following problem were proposed at VJIMC, 2005, Category I. The exact value of the last limit was proposed by a user at https://artofproblemsolving.com , where you can also see his solution along other lines.  Let $(x_n)_{n\ge 2}$ be a sequence of real numbers, such that $x_2>0$ and for every $n\ge 2$ holds  $$x_{n+1}=-1+\sqrt[n]{1+nx_n}.$$ Prove consecutively that  $$1)\ \lim_{n\to\infty}x_n=0,\  \ \ 2)\ \lim_{n\to\infty}nx_n=0,\  \ \ 3)\ \lim_{n\to\infty}n^2x_n=4.$$ $\textbf{Proof.}$  $\textbf{1)}$ Clearly all the elements of the sequence are positive. The inequality $-1+\sqrt[n]{1+nx_n}<x_n$ is equivalent to $(1+nx_n)<(1+x_n)^n$, which is seen to be true after expanding, since all the summands on the right are positive. This shows that the sequence is strictly decreasing. Hence $$0<x_{n+1}=-1+\sqrt[n]{1+nx_n}\le -1+\sqrt[n]{1+nx_2},$$ and since the right hand side clearly tends to $0$ we obtain $\displaystyle\lim_...
Read more