I am trying to show that "if every countable subset of a totally ordered set [tex]X[/tex] is well ordered, then [tex]X[/tex] itself is well ordered". My argument is by contradiction. Informally, if we have a nonempty subset [tex]E[/tex] of [tex]X[/tex] which does(adsbygoogle = window.adsbygoogle || []).push({}); nothave a smallest element, then we can produce an infinite decreasing sequence in [tex]E[/tex] whose image is a countable subset of [tex]X[/tex] that doesn't have a smallest element and is therefore not well ordered.

I am having some doubts about how to make this argument more precise. I was thinking of something as follows: Let [tex]f:\mathcal{P}(X)\to X[/tex] be a choice function for [tex]X[/tex] and let [tex]x_0\in E[/tex]. Then, define a sequence recursively by letting [tex]x_{n+1}=f(s(x_n)\cap E)[/tex]. (Note: [tex]s(x_n)=\{x\in X: x<x_n\}[/tex].) Clearly, the image of this sequence has no smallest element. But, the question is can we really define a sequence in this way? For the Recursion Theorem to work, doesn't the function [tex]f[/tex] have to be a map from a set toitself?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Countable Sets

**Physics Forums | Science Articles, Homework Help, Discussion**