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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - Countable Sets | Date |
---|---|

I Countability of ℚ | Feb 12, 2018 |

Proof that if the alphabet set is at most countable, then strings cnt | Feb 9, 2014 |

How can the set of the rational numbers be countable if there is no | Jan 29, 2013 |

Cantor set end points are and are not countable! | Nov 29, 2012 |

Countable union of countable sets, proof without AC? | Nov 6, 2012 |

**Physics Forums - The Fusion of Science and Community**