Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I don't think Jech is using "naturally" as in "natural choice"; he's just using it as a synonym for "obviously". If X is non-empty set then there exists an x in X, because that's what it means for X to be non-empty. The choice is arbitrary: if X is the set of all functions from R to R then you could take the exponential function, the x^2 function, etc., whatever you like; the point is that it is certainly possible to make some choice.

Doubting the axiom of choice means thinking that when you have infinitely many sets to choose from, it is possible that not only is there is no natural choice function, but there is no choice function at all.



But why do we need the axiom of choice at all? By this logic I have any family of non-empty sets then I’m good? But surely there’s a distinction here


I'm late replying to this, but---you need the axiom of choice once you have a family of non-empty sets rather than a single non-empty set.

At some point you have to go into the formalism to really understand it. It's really about an interchange of quantifiers. If you have a non-empty set X that it is true that

[a] (exists x)(x in X)

If you have a family F of non-empty sets X then it is true that

[b] (forall X in F)(exists x)(x in X)

But to say that you have a choice function f for F is to say that

[c] (exists f)(forall X in F)(f(X) in X)

It turns out that the laws of first-order predicate logic and the axioms of ZF set theory do not allow you to come up with a formal proof that [b] implies [c]. You can try to find one, and you will fail. It's like the parallel postulate in Euclidean geometry. There is actually a proof that the axiom of choice is not provable from the other axioms, but it's a pretty deep result. Historically, there was quite a long time between when the set-theoretical foundations for mathematics were developed at the start of the 20th century, which is when mathematicians realized that the axiom of choice was a principle that needed justification, and when Paul Cohen proved that the axiom of choice wasn't provable from the other axioms, in the 1960s.

So if you believe that the implication from [b] to [c] is self-evident, you have to assume

[d] (forall X in F)(exists x)(x in X) => (exists f)(forall X in F)(f(X) in X)

as an axiom, which is the axiom of choice.

I think most people are inclined to agree that [d] is self-evident---that's why it's generally accepted as an axiom, with only a minority of people objecting. However, in the larger context of set theory it makes a lot of sense to minimize the amount of existential assumptions we are making. Historically, set theorists assumed that any set given by a definable formula would exist, but this lead to contradictions (Russell's paradox). So there's some reasonable paranoia about using additional axioms when we don't need to, in case it somehow leads to another inconsistency.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: