Countable Sets

dmuthuk

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 not have 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 to itself?

matt grime

Isn't this just a version of the fact that every infinite set has a countable subset?

Pick a subset X that does not have a least element. Pick x_1 in it. The subsubset of things less than x_1 cannot be non-empty, or X has a least element. So pick something in it, and repeat, voila a countable subset with no least element is constructed.

dmuthuk

Does this need the axiom of choice? I think the recursion theorem states something like this: Let [tex]X[/tex] be a set and consider a map [tex]f:X\to X[/tex]. If [tex]a\in X[/tex], then there is a unique function [tex]U:\mathbb{N}\to X[/tex] such that [tex]U(0)=a[/tex] and [tex]U(n+1)=f(U(n))[/tex] for every [tex]n\in\mathbb{N}[/tex]. The problem is my choice function [tex]f[/tex] doesn't look like this since it goes from [tex]\mathcal{P}(X)\to X[/tex]. Is there a way to adjust it?

Well, perhaps we can do it by composing two functions. For instance, let [tex]g:\mathcal{P}(E)-\{\emptyset\}\to E[/tex] be a choice function for [tex]E[/tex]. And, define [tex]h:E\to\mathcal{P}(E)-\{\emptyset\}[/tex] by [tex]h(x)=s(x)\cap E[/tex]. Finally, we can define [tex]f:E\to E[/tex] by [tex]f(x)=g(h(x))[/tex]. Note that for each [tex]x\in E[/tex], the set [tex]s(x)\cap E[/tex] is nonempty (since E has no least member) and so [tex]g(h(x))[/tex] is always defined.

matt grime

Why are you making it so complicated? Why invoke any choice functions?

dmuthuk

You are arbitrarily choosing elements from an infinite collection of sets, so how can you do it without the axiom of choice??

matt grime

Warning: I do not understand the intricacies of the axiom of choice.

I am not choosing arbitrary elements of unrelated _sets_. I have _one_ set X. It is not empty, and has no least element. Pick x_1 in it. Since X doesn't have a least element, by definition there is an x_2 less thn x_1. That isn't least, so there is x_3 less than it, and by induction I can create an uncountable set with no minimal element. I don't see that I need to invoke anything deep here. This is a perfectly sound proof, with or without needing to invoke any big theorems explicitly. But I could very easily be wrong. And even if such a choice does require the axiom of choice, by some equivalency, there is still no need to write such an argument as you have done above.

dmuthuk

I totally agree with the argument of course. The thing is I have just been learning the basic concepts of set theory (Halmos' book) for the first time and so I guess I am a little pedantic about the rigour of such proofs. For instance, I have always thought of a function as just a function or a number as just a number. It's comforting to know that we can break everything down to just sets and the axioms that govern them:)

matt grime

Edit: I of course meant a _countable_ set, and not an uncountable one.

My impression is that you're making far too much out of the axiom of choice, which is just a statement of something that is obviously true, in some cases, and obviously not important (perhaps even false) in others.

I see nothing wrong (i.e. that needs any direct appeal to, or help from) any complicated theorem in my (and your) argument. It might need something equivalent to the axiom of choice, but that does not mean that it is at all helpful to invoke the axiom of choice in the form that you have learnt it.

mathwonk

how can there b e any further discussion AFTER POST 2?

SiddharthM

I couldn't disagree more. He/she is STUDYING SET THEORY - knowing when and if the AC is needed in ANY proof of a set-theoretic theorem IS important. Knowing what machinery is needed to prove something is a huge part of the the the study of foundational mathematics.

That being said I think the recursion theorem justifies matt grime's proof.
Your f's domain is not the powerset of X but X. Define it appropriately.