How to prove a totally ordered set is not Dedekind complete?

Take $$\mathbb{Z}^{\mathbb{N}}$$ to be the set of all sequences of integers. Where every element $$x$$ is of the following form: $$x=(x_{1},x_{2},...)$$ with $$\forall n\in \mathbb N^*, x_{n}\in\mathbb{Z}$$.

We order the set as follows: $$x\lneq y\Leftrightarrow$$ the first non-zero entry of $$y-z$$ is positive. Where we denote subtractions as term by term such that: $$y-z$$ corresponds to the sequence $$(y_{1}-x_{1},y_{2}-x_{2},...,)$$

I'm trying to prove that this totally ordered set is indeed not Dedekind complete (every non-empty subset that is bounded above has a supremum). I've checked previously that this ordering does form a totally ordered set.

I'm a bit stuck on where to begin this proof. Any advice is appreciated.

• The order you describe is better known as the lexicographic order: $(a_1,a_2,\ldots)\lt (b_1,b_2,\ldots)$ if and only if there is a $k$ such that $a_i=b_i$ for $1\leq i\lt k$, and $a_k\lt b_k$. It is the "dictionary order". Nov 1, 2022 at 17:18

1 Answer

It's easier to see what's going on if we rearrange things a bit. I am going to start $$\mathbb{N}$$ at $$0$$ and also rename your sequences to $$a_0, a_1, a_2, \dots$$, and furthermore I am going to think about a sequence as a formal power series

$$A(x) = \sum_{i=0}^{\infty} a_i x^i.$$

The reason I want to do this is that we get a conceptual interpretation of the lexicographic order in terms of formal power series. Two formal power series $$A(x), B(x)$$ satisfy $$A < B$$ iff $$B - A$$ is positive in the sense that its first nonzero term is positive. What this tells us is that $$x$$ behaves like a positive infinitesimal; it is smaller than all of the positive "ordinary numbers" $$a_0$$ but larger than $$0$$, and also larger than $$x^2$$, which is larger than $$x^3$$, which is larger than $$x^4$$, and so on. So the lexicographic order can be thought of as describing "formal power series in a positive infinitesimal."

So, how do we use this interpretation to produce a non-empty set bounded from above without a supremum? Consider the set

$$x, 2x, 3x, \dots$$

which consists of infinitesimals so is bounded from above by $$1$$. In fact it's not hard to see that the set of upper bounds is exactly the set of power series $$g(x)$$ such that $$g(0) \ge 1$$. What this means is that if $$g(x)$$ is any upper bound then so is the infinitesimally smaller upper bound $$g(x) - x$$, so there is no least upper bound. (Obviously you could run this entire argument in terms of sequences but personally I think it's less intuitive, whereas thinking about $$x$$ as infinitesimal immediately suggests this argument, to me anyway.)

Note that we only need a single infinitesimal to run this argument, not the extravagantly larger infinite stack of infinitesimals we actually have available. The general lesson here is that Dedekind-completeness is not compatible with the existence of infinitesimals (say, when you are trying to figure out what properties you should require $$\mathbb{R}$$ to have).

• Just to clarify but I thought the set of Infinitesimals don't exist in the standard real number system? Nov 1, 2022 at 23:05
• Right, and they can't if you want $\mathbb{R}$ to be Dedekind-complete. The point is that when setting up foundations there is a choice that can be made here whether to allow $\mathbb{R}$ to have infinitesimals; this was a real choice that mathematicians faced historically and eventually they chose not to do it. You can add infinitesimals using e.g. nonstandard analysis but then you give up Dedekind-completeness. Nov 1, 2022 at 23:47
• Ah, that makes sense. So, the only way for the set of all integer sequences with the above ordering to not be Dedekind complete is to choose $\mathbb{R}$ to allow infinitesimals? Nov 2, 2022 at 0:18
• No, the above order has nothing to do with $\mathbb{R}$ explicitly, I am just making a general comment. You can ignore it if it's confusing. Nov 2, 2022 at 0:29