Dense linear order on any infinite set

Question

The problem:

Prove that there is a dense linear order on any infinite set X: that is, a linear order such that whenever $x < y$, there is a $z \in X$ such that $x < z < y$. [Hint: consider $\mathbb{Q}\times X$].

I've tried proving this using Zorn's lemma, but it doesn't get me anywhere. I don't see how the tip could be used, maybe something with the property that between two rationals there always is an irrational..?

Answer 1

The axiom of choice is needed here, of course. So going through Zorn's lemma is somehow necessary. But applying it "directly" is not the best course of action.

Here are two options:

1. Use these two facts in conjunction:

   • Every set can be linearly ordered (that is a consequence of Zorn's lemma),
   • and $|\Bbb Q\times X|=|X|$ for any infinite set $X$ (that is another consequence of Zorn's lemma).

   Now use the lexicographic ordering on $\Bbb Q\times X$ (using the first fact), and the bijection you have to $X$ (using the second fact) to define a linear ordering on $X$ which is dense.

2. Use the Löwenheim–Skolem theorem to prove that every theory with an infinite model has an infinite model of any cardinality. Since $\Bbb Q$ is a model of "dense linear ordering" which is infinite, there is one of any cardinality. In particular, $|X|$.