Zorn's lemma without the axiom of choice

1. Nov 19, 2006

StatusX

I'm wondering if there is a version of Zorn's lemma that applies to collections that are "small" in a sense I'll describe below, and which true independent of the axiom of choice.

Specifically, say I have a collection of sets such that each set in it is countable, but the collection as a whole may be uncountable. I order this collection by inclusion, and show that every chain has an upper bound. I can apply Zorn's lemma and get that there's a maximal element. But what I'm wondering is if I can do this without the usual version Zorn's lemma, which requires the axiom of choice. Every chain must be countable, since otherwise its bound would be uncountable. Is there a way to do this?

2. Nov 19, 2006

StatusX

This isn't directly about my question, but it just got me thinking, and I can't figure this out. If you look at the collection of countable subsets of R, ordered by inclusion, there is clearly no maximal element, since you can always add a single element to a countable set and get another countable set. So it must be that not every chain has an upper bound.

But clearly every countable chain has an upper bound, namely the union of the elements in the chain, which must itself be countable. Thus there must be uncountable chains. But how can you have an uncountable chain of countable sets? Each set in the chain must have at least one more element than the one before it, so if a set has uncountably many sets before it, it must be uncountable. So what we must have is an uncountable chain such that any given element still has only countably many predecessors. This seems wierd.

3. Nov 19, 2006

Hurkyl

Staff Emeritus
It is possible to have an uncountable chain of countable sets. For example, consider the chain of all countable ordinal numbers.

Every countable ordinal is, of course, a countable set.

The set of all countable ordinals must itself be an ordinal... and since it cannot be a countable ordinal, it must be the smallest uncountable ordinal.

Therefore, the chain of countable ordinals is uncountably long, but consists only of countable sets.

So, the trick is to take just the sets before it as your chain, and not that element itself!

Last edited: Nov 19, 2006
4. Nov 19, 2006

StatusX

But how do you know there is a smallest uncountable ordinal number?

5. Nov 19, 2006

Hurkyl

Staff Emeritus
The class of ordinals is well-ordered. (You don't need to assume the axiom of choice for that!) So if there exists any uncountable ordinal, then there exists a smallest one.

Alternatively, we can actually construct it:

the smallest uncountable ordinal = {a | a is a countable ordinal}

I'll have to ponder a bit to prove the required assumption above. (Or to prove the set-builder notation I gave actually gives a set). (it follows easily from the AoC, though)

6. Nov 19, 2006

Hurkyl

Staff Emeritus
7. Nov 19, 2006

StatusX

Thanks, that makes some sense now. So the set of ordinals up to (but not including) the first uncountable one is uncountable, but any element has only countably many predecessors (and so uncountably many successors). That's a strange set. No matter how high you go, you're nowhere near the top. I guess you can draw an analogy between this situation and the distinction between finite and infinite sets. I'll keep thinking about this, but I'm still lost on my original question.

8. Nov 19, 2006

Hurkyl

Staff Emeritus
I was thinking more of an analogy like

countable ordinals : the first uncountable ordinal :: [0, 1) : 1,

but I suppose there are lots of analogies you can write. Oh, I guess you're thinking of

countable ordinals : the first uncountable ordinal :: natural numbers : $\omega$

which is a closer analogy!

Last edited: Nov 19, 2006
9. Nov 19, 2006

Hurkyl

Staff Emeritus
Allow me to define the small axiom of choice:

a choice function exists for any countable collection of nonempty sets.

I think that your small Zorn's lemma implies the small AoC by exactly the same argument the usual Zorn's lemma implies the usual AoC.

I don't remember off hand how the argument for the reverse implication goes... but maybe this direction answers your original question?

Last edited: Nov 19, 2006
10. Nov 19, 2006

StatusX

Actually I think I'm looking for the other direction. I want to show that if every chain has an upper bound, then there is a maximal element, but I don't want to use the (big) axiom of choice. I think I can do this using your small axiom of choice when the collection is countable, but what about when the collection is uncountable, but every chain is countable?

11. Nov 19, 2006

Hurkyl

Staff Emeritus
Why not take small Zorn's lemma as an axiom?

12. Nov 19, 2006

StatusX

Ok, let me go back. I'm trying to prove the Lebesgue decomposition theorem directly, since the proof in my book (Rudin) is indirect, using Hilbert space theory, and isn't very intuitive. I'm pretty sure my proof is correct, but it uses Zorn's lemma, and I don't think the axiom of choice is necessary for the LDT. Maybe I'm wrong about that though.

13. Nov 19, 2006

Hurkyl

Staff Emeritus
Eep! I dread the thought of trying to work out which theorems of analysis depend on the AoC and which do not!

The small axiom of choice is still not a theorem of ZF; it's just a weaker assumption than the full axiom of choice. So you're still assuming something beyond ZF if you want to invoke it.

If you're okay with that, and are just trying to minimize the cardinality with which you're assuming the AoC... then it might be worth trying to reorganize your proof to use the AoC directly, or maybe transfinite induction.

Incidentally, the proof in Royden starts by invoking the Radon-Nikodym theorem, and from there is constructive and fairly short. I can copy it if oyu want to see it.

(Of course, I don't know if the Radon-Nikodym theorem relies on a variant of the AoC or not)

14. Nov 19, 2006

matt grime

So if you invoke a stronger axiom it becomes easier to prove. That shouldn't be at all surprising.

15. Nov 19, 2006

StatusX

Oh, I thought a choice function did exist independently of AC for countable sets, but looking back, it seems this is only true for finite sets. I don't want to assume anything I don't have to, so I'll try to go back and fix up my proof.

The proof in Rudin gives the LDT and the Radon-Nikodym theorem at the same time, so it might be pretty similar to the one in your book. But the LDT seems pretty basic, and I'd like to find a direct proof of it.

Right, but is it possible to prove it without invoking that axiom?

Last edited: Nov 19, 2006
16. Nov 19, 2006

StatusX

Actually I just realized I never used the assumption that the base measure (that the other one is decomposed wrt) is sigma finite, which is assumed in the ordinary version of the theorem. I guess my proof strengthens the theorem, albeit under the extra assumption of AC. I'll try to go back and use the sigma finite condition.

17. Nov 20, 2006

StatusX

Ok, I think I found a way around it, but I'm not sure if I'm still using the axiom of choice. Basically, say I have a bounded function f from some set X to the real numbers, and say its sup is a. Can I form a sequence x_n in X with f(x_n)>a-1/n without using the axiom of choice? I've seen this kind of technique used a lot, and I've never heard AC explicitly mentioned, but it seems like it would be necessary.

18. Nov 20, 2006

Hurkyl

Staff Emeritus
Is it enough to consider the set of finite sequences that satisfy your criterion?

19. Nov 21, 2006

StatusX

Now I'm confused again. You can always choose a single element from a single set. Having done this, do it again, and by induction, you can choose an element from each of the sets in any finite collection. So if I have a countable collection of sets A_n, I can pick an x_n from each A_n up to any n. Thus I can get a sequence of x_n for all natural numbers n, all without the axiom of choice, right?. So what's the difference between this the "small" axiom of choice you defined in post 9?

20. Nov 21, 2006

Hurkyl

Staff Emeritus
How do you plan on passing from:

I can find sequences of any finite length​

to

I can find an infinite sequence​

?