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.

  • $\begingroup$ 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". $\endgroup$ Nov 1, 2022 at 17:18

1 Answer 1


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).

  • $\begingroup$ Just to clarify but I thought the set of Infinitesimals don't exist in the standard real number system? $\endgroup$ Nov 1, 2022 at 23:05
  • $\begingroup$ 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. $\endgroup$ Nov 1, 2022 at 23:47
  • $\begingroup$ 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? $\endgroup$ Nov 2, 2022 at 0:18
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2022 at 0:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .