Prove every finite set of real numbers is well ordered.

Question

so as the title says how do we prove it? I mean it is obvious but i have no idea how to do it. Without referring to general principle of mathematical induction, as that would be circular logic i presume.

Answer 1

Induction is in fact the way to do this; we induct on the number of elements in the set. The empty set is trivially well-ordered; any set containing exactly one real is well-ordered (if the set is $\{x\}$, the order is $x \leq x$, and that's a well-order).

Now, suppose we have a set $\{ r_1, r_2, \dots, r_n \}$, which are in ascending order. What is it for this set to be well-ordered? We need every subset to have a least element. But every subset is finite, so is (by inductive hypothesis) well-ordered unless it's the entire set, so in particular it has a least element unless it's the entire set. Together with the fact that the entire set has a least element (again by induction, since min is associative), that's all we need.

By the way, it is always possible to find a well-order on any finite set (even one which doesn't come with an order, like $\mathbb{R}$'s subsets do). This is also proved by induction on the length of the set.

Answer 2

Every non-empty subset of the naturals is well ordered with respect to the standard ordering on the naturals. If $A$ is any non-empty finite set, then there is a bijection $f:A\to\{1,\dots,n\}$ for some $n\in\mathbb{N}$. Given two elements $a,b\in A$, say $a\leq_Ab$ if and only if $f(a)\leq f(b)$. Then $\leq_A$ defines a well ordering on $A$.

To see why this is the case, it is a total ordering on $A$:

Reflexive: We have $a\leq_A a$ for all $a\in A$ since $f(a)\leq f(a)$ for all $a\in A$.

Transitive: If $a,b,c\in A$ and $a\leq_A b$ and $b\leq_A c$, then $f(a)\leq f(b)\leq f(c)$ so $a\leq_Ac$.

Anti-Symmetric: If $a\leq_A b$ and $b\leq_A a$, then $f(a)\leq f(b)$ and $f(b)\leq f(a)$ so $f(a) = f(b)$. $f$ being bijective implies $a=b$.

Strongly connected (or total): If $a,b\in A$, then $f(a)\leq f(b)$ or $f(b)\leq f(a)$ so $a\leq_Ab$ or $b\leq_A a$.

Now, given any non-empty subset $B\subseteq A$, $f(B)\subseteq\{1,\dots,n\}$ is a non-empty subset of $\mathbb{N}$ and has a minimal element, say $m\in f(B)$. Then $m\leq x$ for all $x\in f(B)$. Given $b\in B$, we have $m\leq f(b)$ hence $f^{-1}(m)\leq_A b$ for all $b\in B$ so $f^{-1}(m)$ is the minimal element of $B$. This shows that $\leq_A$ is a well ordering on $A$.

Answer 3

This is overkill, but just for fun, a set is well-ordered iff it contains no infinite sequence $x_0, x_1, ...$ such that if $i > j$ then $x_i < x_j$. A finite set of real numbers contains no such infinite sequence and, as such, it is well-ordered.

Answer 4

I hope this is not seen as a redundant to Patrick Steven's answer...it just provides a little extra detail on how the induction argument takes place.

We want to show that for any for any $n \in \mathbb N$, if $S_n$ is a set with $n$ elements (all belonging to $\mathbb R)$, then $S_n$ has a least element (i.e. $S_n$ satisfies the well-ordering principle). A similar argument can be used to show that $S_n$ must have a greatest element. Formally, we will show through induction that $\forall n \in \mathbb N:\left[ \forall S: \big( |S|=n \rightarrow \exists x^* \in S: \forall x \in S: x^* \leq x \big) \right]$

Base Case

Consider any arbitrary singleton $S_1=\{x\}$. Clearly, $x$ is the least element of $S_1$.

Inductive Assumption

For an arbitrary $n$, suppose we know that for any $n$-sized set $S_n$, there is a least element $x_{\ell} \in S_n$.

Induction Proof

Consider any arbitrary $S_{n+1}$. Choose any $t \in S_{n+1}$. Then there exists an $S_n: \{t\} \cup S_n=S_{n+1}$. By our inductive assumption, we know that there is an $x_{\ell} \in S_n$ such that for any $x \in S_n: x_{\ell} \leq x$. There are two cases to consider: $t \geq x_{\ell}$ or $t \lt x_{\ell}$. In the former case, we have that for any $x \in S_{n+1}: x_{\ell} \leq x$, so $x_{\ell}$ is the least element of $S_{n+1}$. In the latter case, we have that for any $x \in S_{n+1}: t \leq x$, which means that $t$ is the least element of $S_{n+1}$. In either case, we therefore have that there exists a least element for $S_{n+1}$. $S_{n+1}$ was arbitrary, so we can generalize to any $(n+1)$-sized set $S_{n+1}$. The induction is now closed.

We can now generalize across the natural numbers and claim that for any $n$-sized set $S_n$, there is a least element $x_{\ell}$.