Honestly, I figured out the idea to prove this theorem without much difficulty. But I found very hard to formalize it into a rigorous proof and it takes me three days to do it.

Could you please have a check on my attempt? Thank you so much!

A sequence $\langle a_n \rangle_{n=0}^{\infty}$ of rational numbers is a Cauchy sequence if for every rational $\epsilon>0$ there exists an integer $N$ such that $|a_m - a_n| < \epsilon$ for all $m,n > N$. Let $\mathfrak{C}$ be the set of all Cauchy sequences of rational numbers. We define a relation $\preccurlyeq$ on $\mathfrak{C}$ by $\langle a_n \rangle_{n=0}^{\infty} \preccurlyeq \langle b_n \rangle_{n=0}^{\infty}$ if and only if for every rational $\epsilon>0$ there exists an integer $N$ such that $a_n - b_n < \epsilon$ for all $n > N$.

Theorem: Any two elements of $\mathfrak{C}$ are comparable w.r.t $\preccurlyeq$.

My attempt:

Assume the contrary that there exist $\langle a_n \rangle_{n=0}^{\infty}$, $\langle b_n \rangle_{n=0}^{\infty} \in \mathfrak{C}$ that are incomparable. Then $\langle a_n \rangle_{n=0}^{\infty} \not \preccurlyeq \langle b_n \rangle_{n=0}^{\infty}$ and $\langle b_n \rangle_{n=0}^{\infty} \not \preccurlyeq \langle a_n \rangle_{n=0}^{\infty}$. As a result, $\exists \epsilon >0,\forall N,\exists n>N:a_n - b_n \ge \epsilon$ and $\exists \epsilon >0,\forall N,\exists m>N:b_m - a_m \ge \epsilon$.

Then $\exists \epsilon >0,\forall N,\exists (n>N \wedge m>N):a_n - b_n \ge \epsilon \wedge b_m - a_m \ge \epsilon$. By Axiom of Choice, there exist functions $f:\Bbb N \to \Bbb N$ and $h:\Bbb N \to \Bbb N$ such that $f(N)>N$, $h(N)>N$, $a_{f(N)} - b_{f(N)} \ge \epsilon$, and $b_{h(N)} - a_{h(N)} \ge \epsilon$.

Moreover, $\langle b_n \rangle_{n=0}^{\infty}$ is a Cauchy sequence $\implies$ $\exists N_0,\forall m,n > N_0:|b_m - b_n| < \epsilon$.

We define functions $f':\Bbb N \to \Bbb N$ and $h':\Bbb N \to \Bbb N$ by $f'(N)=f(N_0)$, $h'(N)=h(N_0)$ for all $N<N_0$ and $f'(N)=f(N)$, $h'(N)=h(N)$ for all $N \ge N_0$.

It follows that $f'(N)>N$, $h'(N)>N$, $a_{f'(N)} - b_{f'(N)} \ge \epsilon$, $b_{h'(N)} - a_{h'(N)} \ge \epsilon$, and $|b_{h'(N)} - b_{f'(N)}| < \epsilon$ for all $N \in \Bbb N$. As a result,

$\begin{align}|a_{f’(N)} - a_{h’(N)}| &= |(a_{f’(N)} - b_{f’(N)}) + (b_{h’(N)} - a_{h’(N)} ) + (b_{f’(N)} - b_{h’(N)})|\\ &\ge |(a_{f’(N)} - b_{f’(N)}) + (b_{h’(N)} - a_{h’(N)} )| - |b_{f’(N)} - b_{h’(N)}|\\ &= |a_{f’(N)} - b_{f’(N)}| + |b_{h’(N)} - a_{h’(N)} | - |b_{f’(N)} - b_{h’(N)}|\\ &> \epsilon + \epsilon - \epsilon =\epsilon\end{align}$

Hence $\exists \epsilon>0, \forall N, \exists(f’(N)>N \wedge h’(N)>N):a_{f’(N)} - a_{h’(N)}>\epsilon$. This contradicts the fact that $\langle a_n \rangle_{n=0}^{\infty}$ is a Cauchy sequence.


I see only a (minor) problem with your attempt: at the first paragraph, those $\varepsilon$'s should be two distinct numbers a priori. But that's not a serious problem.

On the other hand, the axiom of choice is not needed for the proof, but using it is not an error.

  • $\begingroup$ Thank you so much for your verification! Please confirm if my understanding is correct. 1. Although @Did edited my title into ... a total order, I think $\preccurlyeq$ is NOT an order relation. This is because $\preccurlyeq$ is NOT antisymmetric, i.e there exist $\langle a_n \rangle_{n=0}^{\infty} \neq \langle b_n \rangle_{n=0}^{\infty}$ such that $\langle a_n \rangle_{n=0}^{\infty} \preccurlyeq \langle b_n \rangle_{n=0}^{\infty}$ and $\langle b_n \rangle_{n=0}^{\infty} \preccurlyeq \langle a_n \rangle_{n=0}^{\infty}$.[...] $\endgroup$ – Le Anh Dung Jan 30 at 11:03
  • $\begingroup$ [...] 2. To avoid the use of Axiom of Choice, we can define $f:\Bbb N \to \Bbb N$ by $f(N)=\min \{n\in\Bbb N \mid n>N \wedge a_n - b_n \ge \epsilon \}$ for all $N\in\Bbb N$. $\endgroup$ – Le Anh Dung Jan 30 at 11:03
  • $\begingroup$ Right: it is not an order relation. While thinking about your attempt, I only cared about the specific claim that you were trying to prove. $\endgroup$ – José Carlos Santos Jan 30 at 11:04
  • $\begingroup$ Please have a check on my Claim 2. too! $\endgroup$ – Le Anh Dung Jan 30 at 11:05
  • $\begingroup$ It looks correct to me. $\endgroup$ – José Carlos Santos Jan 30 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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