Does any non-maximal element of a well-ordered set have a unique successor?

111 Views Asked by At

$\newcommand{\setcomplement}[2]{#1 \setminus #2}$ $\newcommand{\singleton}[1]{\left\{#1\right\}}$ $\newcommand{\segment}[2]{\operatorname{Seg}_{#1}\left(#2\right)}$

I wanted to find the smallest element of $\mathbb{Q}$ larger than $0$, where $\mathbb{Q}$ is well-ordered as a result of the bijection between $\mathbb{Q}$ and $\mathbb{N}$. Thanks to comments provided below, I realized that I need to prove the following theorem: Let $\left(X,R\right)$ be a well-ordered set where $R$ is a strict total order on $X$. Then for any $x \in X$, if $x$ is not the maximal element of $X$, then there exists a unique $y \in X$ such that (1) $x R y$; (2) there is no $s \in X$ such that $x R s$ and $s R y$.

My proof is presented below.

First of all, if $X = \emptyset$, then the theorem trivially holds. Next, assume that $X \neq \emptyset$ and $X$ is a singleton. Then the theorem also trivially holds.

Further, assume that $X \neq \emptyset$ and $X$ is not a singleton. Let $A$ be the following set: $A \subseteq X$ and for any $x$, $x \in A$ if and only if if $x$ is not the maximal element of $X$, then there exists a unique $y \in X$ such that $y$ is the successor of $x$ under $R$, or, more precisely, (1) $x R y$; (2) there is no $s \in A$ such that $x R s$ and $s R y$. It is our desire to prove $A = X$, and we prove $A = X$ using the theorem of finite induction on well-ordered sets.

First of all, we prove that the least element of $X$ is in $A$. As $X \neq \emptyset$, there exists $x_{0} \in X$ which is the least element of $X$. Let $B$ be the following set: \begin{equation} B = \left\{x \in X \vert x_{0} R x\right\}. \end{equation} As $X$ is not a singleton and $x_{0}$ is the least element of $X$, it is clear that $B \neq \emptyset$. Then there exists a least element $y_{0}$ of $B$. It is obvious that $x_{0} R y_{0}$. Assume that there exists some $z_{0} \in X$ such that $x_{0} R z_{0}$ and $z_{0} R y_{0}$. Then $z_{0} \in B$ and $z_{0} R y_{0}$, contradicting the fact that $y_{0}$ is the least element of $B$. Thus $y_{0}$ is a successor of $x_{0}$. Next assume that there exists $y_{1} \in X$ such that $y_{0} \neq y_{1}$ and $y_{1}$ is a successor of $x_{0}$. Then it is obvious that $y_{1} \in B$, and as $y_{0}$ is the least element of $B$, $y_{0} R y_{1}$. Thus we have $x_{0} R y_{0}$ and $y_{0} R y_{1}$, contradicting the assumption on $y_{1}$. Thus, there doesn't exist a second successor of $x_{0}$ in $X$. Up to now, We conclude that there exists some unique $y \in X$ such that $y$ is the unique successor of $x_{0}$, and so, $x_{0} \in A$.

Next, we prove that if for any $x \in X$, if $\segment{X}{x} \subseteq A$, then $x \in A$. Let $x_{0} \in X$. First assume that $x_{0}$ is the least element of $X$. As we have proved that $x_{0} \in A$, it is obvious that if $\segment{X}{x_{0}} \subseteq A$, then $x_{0} \in A$. Then assume that $x_{0}$ is not the least element of $X$. It is obvious that $x_{0} \in A$ if $x_{0}$ is the maximal element of $X$. So under the condition that $x_{0}$ is the maximal element of $X$, $\segment{X}{x_{0}} \subseteq A$ leads to $x_{0} \in A$.

Next assume that $x_{0}$ is not the maximal element of $X$ either. Under this assumption, let $\segment{X}{x_{0}} \subseteq A$. It is our desire to prove that $x_{0}$ is of a unique successor in $X$. Obviously $\segment{X}{x_{0}} \neq \emptyset$ and $X \setminus \segment{X}{x_{0}} \neq \emptyset$. As $x_{0}$ is not a maximal element of $X$, there exists some $x_{1} \in X$ such that $x_{0} R x_{1}$. Then $X \setminus \segment{X}{x_{0}}$ is not a singleton, or it is to say, $\setcomplement{\left(\setcomplement{X}{\segment{X}{x_{0}}}\right)}{\singleton{x_{0}}} \neq \emptyset$. Then there exists some $y_{0}$ as the least element of $\setcomplement{\left(\setcomplement{X}{\segment{X}{x_{0}}}\right)}{\singleton{x_{0}}} \neq \emptyset$. We argue that $y_{0}$ is the successor of $x_{0}$. First all, it is clear that $x_{0} R y_{0}$. Next, suppose there exists some $y_{1}$ between $x_{0}$ and $y_{0}$. Then $y_{1} \in \setcomplement{\left(\setcomplement{X}{\segment{X}{x_{0}}}\right)}{\singleton{x_{0}}}$ and $y_{1} R y_{0}$, contradicting the condition that $y_{0}$ is the least element of $\setcomplement{\left(\setcomplement{X}{\segment{X}{x_{0}}}\right)}{\singleton{x_{0}}}$. Thus, $y_{0}$ is indeed a successor of $x_{0}$. Further, assume there exists some other $y_{1}$ which is also a successor of $x_{0}$. Then using the similar argument for uniqueness above, we have $x_{0} R y_{0}$ and $y_{0} R y_{1}$, which contradicts the definition of $y_{1}$. As a result, $y_{0}$ is indeed the unique successor of $x_{0}$, and the unique existence is established, and $x_{0} \in A$. Thus, we conclude that when $x_{0}$ is not the maximal element of $X$ nor the least element of $X$, if $\segment{X}{x_{0}} \subseteq A$, $x_{0} \in A$.

Combining all of the above argument, we conclude that for any $x \in X$, if $$\segment{X}{x} \subseteq A,$$ then $x \in A$. Thus, $A = X$.

Up to now, we can locate the successor of $0 \in \mathbb{Q}$, and we may use this element to construct intervals for Heine-Borel theorem which cover a closed and bounded real set.