Is every complete, dense, linearly-ordered set uncountable, without arithmetic? I am studying Introduction to Set Theory by Hrbacek & Jech.  In section 4.5, they introduce complete linear orderings and demonstrate that $\mathbf{Q}$ is not complete, then introduce $\mathbf{R}$ as the completion of $\mathbf{Q}.$  In section 4.6, they prove that $\mathbf{R}$ is uncountable by noting that, by completeness, $\mathbf{R}$ cannot be isomorphic to $\mathbf{Q}$, and since it is not isomorphic to $\mathbf{Q}$ it is not a countable dense linearly ordered set without endpoints.  Since $\mathbf{R}$ is dense, linearly ordered, and without endpoints, it follows that $\mathbf{R}$ must not be countable.  So far so good, I think.
However, this hinges on the fact that some subsets of $\mathbf{Q}$ do not have least upper bounds, and this is proven with field properties of $\mathbf{Q},$ specifically that $\{x \in \mathbf{Q} \mid x^2 < 2\}$ has no least upper bound.
Is it possible to prove that any complete, dense, linearly-ordered set without endpoints is uncountable, while working strictly in terms of basic ordering properties?  In particular, without reference to $\mathbf{Q}$ and $\mathbf{R}$ and arithmetic on those sets?
 A: Assuming you add "nonempty", the answer is "yes".
Consider such an order $P$. To begin with, pick $a < b$.
Let $FinSeq(2)$ be the set of finite sequences of 0s and 1s. Write the empty sequence as $nil$ and, given a sequence $s$ and a value $b \in \{0, 1\}$, write $b :: s$ to be the sequence which begins with $b$ and continues with $s$. We define a function $f : FinSeq(2) \to P^2$ as follows (using the axiom of choice rather liberally, or at least some version of dependent choice):
$f(nil) = (a, b)$
Given that we know $f(s) = (c, d)$, pick some $x, y$ such that $c < x < y < d$. Then define $f(0 :: s) = (c, x)$ and $f(1 :: s) = (y, d)$.
Now, let us consider an infinite sequence $s \in 2^\mathbb{N}$. Consider the set $K_s = \{p \in P \mid$ for all finite initial segments $b$ of $s$, if $f(b) = (c, d)$ then $p < d\}$.
Note that for each $s$, $K_s$ is non-empty, since we can prove by induction on the initial segment $b$ that $a \in K_s$.
Furthermore, note that $b$ is an upper bound for $K_s$. So $K_s$ is nonempty and has an upper bound.
Then define $g(s) = \sup K_s$. Then $g : 2^\mathbb{N} \to P$. I claim that $g$ is injective.
For let us suppose that we have two infinite $a, b$ which are distinguishable. WLOG, suppose that $a < b$ according to lexicographic order. Then take some $c \in FinSeq(2)$ such that $0 :: c$ is an initial segment of $a$ and $1 :: c$ is an initial segment of $b$.
Now write $f(c) = (i, j)$, $f(0 :: c) = (i, x)$, and $f(1 :: c) = (y, j)$. Then I claim that $x$ is an upper bound of $K_a$. This follows from the very definition of $K_a$.
But I claim that $x$ is not an upper bound of $K_b$. The reason is that $y \in K_b$, and $x < y$. We can prove that $y \in K_b$ by induction.
Therefore, $\sup K_a \leq x < \sup K_b$. That is, $g(a) < g(b)$.
Since $g : 2^\mathbb{N} \to P$ is injective, this shows that $|\mathbb{N}| < |2^\mathbb{N}| \leq |P|$. So $P$ is uncountable.
A: A basic theorem of logic is that any countable dense linear ordering without endpoint is isomorphic to $\mathbb{Q}$. This is an application of back and forth method. I think its called Fraisse's theorem. Dont know if this answers your question but one thing you will learn studying logic and set theory that the structures $\mathbb{Q}$ and $\mathbb{R}$ are universal.
To give a proof as you envision, you must construct a tree in the linear ordering.
Let $I_0$ and $I_1$ be two disjoint intervals.
Then $I_{00}, I_{01}$ two further disjoint intervals inside $I_0$, and $I_{10}, I_{11}$ disjoint intervals inside $I_1$, and continue, building a binary tree. Then take the intersections of the nested intervals along each branch, which will be non empty by completeness. This gives uncountably many elements.
