Zorn's lemma without the axiom of choice

[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?

 

[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.

 

[Hurkyl]

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.

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, the trick is to take just the sets before it as your chain, and not that element itself!

 

[StatusX]

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

 

[Hurkyl]

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)

 

[Hurkyl]

Oh, I did a quick search, and here's the neat trick:

http://www.math.niu.edu/~rusin/known-math/00_incoming/ordinals

 

[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.

 

[Hurkyl]

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!

 

[Hurkyl]

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?

 

[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?

 

[Hurkyl]

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

 

[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.

 

[Hurkyl]

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)

 

[matt grime]

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.

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

 

[StatusX]

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.

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.

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)

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.

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

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

 

[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.

 

[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.

 

[Hurkyl]

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

 

[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?

 

[Hurkyl]

How do you plan on passing from:

I can find sequences of any finite length​

to

I can find an infinite sequence​

?

 

[StatusX]

The point is I can define an x_n for any n. There's an infinite sequence.

 

[Hurkyl]

I misread what you said.

The point is I can define an x_n for any n. There's an infinite sequence.

No it's not. You've just told me that you are capable of choosing one element from the n-th set, no matter what n is. You haven't yet told me how you are going to pick an infinite number of elements out of infinitely many sets. (one from each)

 

[Hurkyl]

Oh, I can put it another way.

You've just told me that you are capable of picking one element from one set. But no matter how many times you repeat that process, all you've done is pick one element from each of finitely many sets.

To pass to the "limit" of an infinite sequence, you need to have picked one element from each of infinitely many sets -- so you need to invoke something else. In the most generic case, that something else is the AoC. (Special cases might not need the AoC. In fact, the AoC is never required to find a choice function for a "constructible" collection of sets)

 

[StatusX]

Damn, this is frustrating. I never used to have to worry about "practical" concerns like actually constructing an infinite sequence. I just said "for each n,..", and I was done for all n. I guess I'll have to be more careful from now on.

Do you mind explaining what you mean by "constuctible" sets? I'm guessing this applies to the situation in post 17.

 

[Hurkyl]

Something is "constructible" if you can explicitly construct it. I don't actually know what the right technical definition of constructible would be, though. I didn't mean it in relation to #17, but it does give me an idea. What sort of X and function f are you thinking about? If X is, say, a compact subset of Euclidean n-space, and f a continuous function, then I think you canconstruct of the sequence {x} that you want without invoking the AoC.

The key point is that I think you can prove that any nonempty compact subset of Euclidean n-space has a lexicographically smallest point. (lexicographic meaning, for example, that (1, 1) < (1, 2) < (2, 1)) Then, you can define:

x_n = the lexicographically smallest point in $f^{-1}\left( \left\{ \, a - \frac{1}{2n} \, \right\} \right)$.

 

[StatusX]

Something is "constructible" if you can explicitly construct it. I don't actually know what the right technical definition of constructible would be, though. I didn't mean it in relation to #17, but it does give me an idea. What sort of X and function f are you thinking about? If X is, say, a compact subset of Euclidean n-space, and f a continuous function, then I think you canconstruct of the sequence {x} that you want without invoking the AoC.

The key point is that I think you can prove that any nonempty compact subset of Euclidean n-space has a lexicographically smallest point. (lexicographic meaning, for example, that (1, 1) < (1, 2) < (2, 1)) Then, you can define:

x_n = the lexicographically smallest point in $f^{-1}\left( \left\{ \, a - \frac{1}{2n} \, \right\} \right)$.

The function is from the collection of measurable sets to the positive real numbers, given by taking the measure. It should be ok to pick a single member from, say, f^-1(a-1/n) for a fixed n, right? The problem is I need to do this for all n and take the union of all these sets. Still, I feel like I've done this kind of thing many times before without ever thinking about the axiom of choice.

 

[Hurkyl]

I feel like I've done this kind of thing many times before without ever thinking about the axiom of choice.

That's why we usually assume the axiom of choice.