Does the Axiom of Choice Expand or Limit the Set-Theoretic Universe?

[Fredrik]

Does the axiom of choice make the class of all sets bigger or smaller? Does it perhaps bring new sets into the universe and kick others out of it at the same time? (Maybe in a way that ensures that the first question doesn't make sense?)

The AC gives us permission to construct certain sets from other sets. This suggests that it makes the set-theoretic "universe" bigger.

On the other hand, it's equivalent to Zorn's lemma, which implies things like "every vector space has a basis", so it seems that the AC is what ensures that certain annoying sets (like vector spaces that don't have a basis) are not included in the set-theoretic universe. This seems to suggest that the AC makes the set-theoretic universe smaller, not bigger.

 

[g_edgar]

Neither.
Inside any model of ZF is a model of ZFC: result of Goedel.
Inside any model of ZFC is a countable model of ZF: Löwenheim-Skolem

 

[g_edgar]

Take your example, a vector space without a basis. We can fix that problem in two ways: Making the universe smaller, throwing out that vector space. Making the universe bigger, adding a basis of the space.

Now, for example: is there a basis of R over Q? Unfortunately, we cannot throw out R from ZF... But (in Goedel's method) we can throw out some elements of R, leaving us with something (still called R) that has a basis. Or we can leave the elements of R alone and add extra subsets of R, including one which is our basis.

 

[Fredrik]

Thanks. I can't say I understood all of that, because still haven't studied the Löwenheim-Skolem theorem for example, but your answer still makes things clearer. I intend to make an effort to learn more set theory and logic in a few months, and this gives me some additional motivation.

 

[disregardthat]

I would say it makes it bigger. Bigger doesn't mean "more freedom", indeed if we have a vector space for which no basis could be found without choice we certainly could not prove that in ZF. So how could you say that ZF is bigger in this sense? ZF allows vector spaces with no basis (their existence is not provably false), but doesn't allow any such constructions. Choice only broadens the universe of discourse. To put it succinctly, the class of provably existent sets of ZF is a subclass of those of ZFC.

 

[Fredrik]

Take your example, a vector space without a basis. We can fix that problem in two ways: Making the universe smaller, throwing out that vector space. Making the universe bigger, adding a basis of the space.

It seems to me that the AC can't possibly do the latter, because if X is a vector space in the ZF universe, its power set P(X) either contains a basis or it doesn't. P(X) isn't going to be a different set just because we add AC to our list of axioms, because ZF already tells us what a subset is, and what a power set is. But I suppose AC can kick X out of the universe. (I don't see how. It looks like a rule that should give us more sets without removing any).

If AC just adds more sets to the universe, and the ZFC universe doesn't contain a vector space without a basis, then this seems to imply that the ZF universe doesn't either. Did I just use an axiom that's not a part of ZF to prove something about ZF. Is that even possible? I'm still pretty confused (and really tired...need to get some sleep).

 

[Preno]

Does the axiom of choice make the class of all sets bigger or smaller? Does it perhaps bring new sets into the universe and kick others out of it at the same time? (Maybe in a way that ensures that the first question doesn't make sense?)

Trivially, if the existence (or non-existence) of a set satisfying some property can be proven in ZF, it can also be proven in ZFC. There are sets whose existence can be proven in ZFC but not in ZF. There are would-be sets whose existence can be disproven in ZFC but not ZF (the set X such that Y belongs to X iff there is a vector space with no basis, for example). This should exhaust your question.

If AC just adds more sets to the universe, and the ZFC universe doesn't contain a vector space without a basis, then this seems to imply that the ZF universe doesn't either.

What's "the" ZFC universe and "the" ZF universe? One can take the position that there is no such thing as the ZFC universe or the ZF universe (only various models of ZF and ZFC), or one can take the position that the universe of sets satisfies ZFC, or one can take the position that the universe of sets satisfies ZF but not AC, but the position that there's the ZFC universe and there's the ZF universe make little sense to me (actually the formalist position that there are only various models of ZF also makes little sense to me, but at least that's accepted by quite a few people).

If you take the view that you're describing a pre-existing universe of sets, it makes no sense to say that "AC adds more sets to the universe", while if you take the view that you're defining sets into existence through a bunch of first-order axioms, it makes no sense to talk about "the ZF(C) universe".

 

[Fredrik]

Trivially, if the existence (or non-existence) of a set satisfying some property can be proven in ZF, it can also be proven in ZFC. There are sets whose existence can be proven in ZFC but not in ZF.

Doesn't the second sentence contradict the first?

There are would-be sets whose existence can be disproven in ZFC but not ZF (the set X such that Y belongs to X iff there is a vector space with no basis, for example). This should exhaust your question.

I don't understand. If it isn't possible to prove the existence of a vector space without a basis in ZF, then "X=∅ if there's a vector space without a basis and X={Y} otherwise" is just a sentence that fails to assign a set to the symbol "X". In ZFC on the other hand, the sentence just says that X={Y}, and this doesn't give us any new sets, because we could have used the axioms to find out that {Y} is a set.

What's "the" ZFC universe and "the" ZF universe? One can take the position that there is no such thing as the ZFC universe or the ZF universe (only various models of ZF and ZFC), or one can take the position that the universe of sets satisfies ZFC, or one can take the position that the universe of sets satisfies ZF but not AC, but the position that there's the ZFC universe and there's the ZF universe make little sense to me (actually the formalist position that there are only various models of ZF also makes little sense to me, but at least that's accepted by quite a few people).

Some of the axioms are there to prevent certain things from being called "sets", like S={x|x∉S}. Such axioms are necessary to prevent logical inconsistencies (and I'm sure they have other purposes as well, even though I don't fully understand them yet). Other axioms are there to ensure that there are enough sets for the set theory to be useful. There's for example an axiom that ensures that there's an empty set, and another that ensures that there's an inductive set (i.e. a set with the properties we want the natural numbers to have). What I mean by "the universe" is the class of all sets that are permitted by the full list of axioms.

I have also read that in ZFC (maybe ZF too?), all sets can be built up from the empty set alone. Doesn't this paint a pretty clear picture of what the ZFC "universe" of sets is? The empty set is clearly in there, and so is the set we call the natural numbers, but no vector space without a basis is.

If you take the view that you're describing a pre-existing universe of sets, it makes no sense to say that "AC adds more sets to the universe", while if you take the view that you're defining sets into existence through a bunch of first-order axioms, it makes no sense to talk about "the ZF(C) universe".

I agree with the first part*, and I don't understand the second part. It looks wrong to me, but I'm a novice at this, so I don't know.

*) I'm definitely not imagining a universe of sets that somehow "really" exists, independent of any axioms. As a physics nerd, I think it would be preposterous to make obviously unfalsifiable claims about reality, like e.g. that there's an "actual" universe of sets.

 

[Preno]

Trivially, if the existence (or non-existence) of a set satisfying some property can be proven in ZF, it can also be proven in ZFC. There are sets whose existence can be proven in ZFC but not in ZF.

Doesn't the second sentence contradict the first?

No. It's kind of the point of AC that it allows us to prove the existence of sets we couldn't prove before, and it's trivial that any theorem of ZF is also a theorem of ZFC.

I don't understand. If it isn't possible to prove the existence of a vector space without a basis in ZF, then "X=∅ if there's a vector space without a basis and X={Y} otherwise" is just a sentence that fails to assign a set to the symbol "X". In ZFC on the other hand, the sentence just says that X={Y}, and this doesn't give us any new sets, because we could have used the axioms to find out that {Y} is a set.

The Y was implicitly meant to be universally quantified. Every set belongs to X if there is a vector space with no basis, no set belongs to X otherwise.

Some of the axioms are there to prevent certain things from being called "sets", like S={x|x∉S}. Such axioms are necessary to prevent logical inconsistencies (and I'm sure they have other purposes as well, even though I don't fully understand them yet). Other axioms are there to ensure that there are enough sets for the set theory to be useful. There's for example an axiom that ensures that there's an empty set, and another that ensures that there's an inductive set (i.e. a set with the properties we want the natural numbers to have). What I mean by "the universe" is the class of all sets that are permitted by the full list of axioms.

You still haven't justified your usage of the definite article, though. There are many models of ZF(C). In some, for example, 2^aleph_4 is equal to aleph_5, in others, to aleph_37. Which of these are you talking about when you talk about "the ZF(C) universe"?

I have also read that in ZFC (maybe ZF too?), all sets can be built up from the empty set alone. Doesn't this paint a pretty clear picture of what the ZFC "universe" of sets is? The empty set is clearly in there, and so is the set we call the natural numbers, but no vector space without a basis is.

I think you're confusing the formal theory called ZF(C) on the one hand, and the intuitive "iterative conception of set" on the other. The former is just one possible formalization of the latter. One can claim that the latter completely describes the set universe, but you cannot claim that the former does (because it leaves many questions undecided).

If you take the view that you're describing a pre-existing universe of sets, it makes no sense to say that "AC adds more sets to the universe", while if you take the view that you're defining sets into existence through a bunch of first-order axioms, it makes no sense to talk about "the ZF(C) universe".

I agree with the first part*, and I don't understand the second part. It looks wrong to me, but I'm a novice at this, so I don't know.

The ZF(C) axioms give you plenty of leeway in deciding many questions (the general continuum hypothesis, large cardinal axioms). If you think the formal theory called ZF(C) completely describes the universe of sets, then you have to put a universe in which 2^aleph_4 = aleph_5 and one in which 2^aleph_4 = aleph_37 on equal footing. There is no way of deciding, in ZF(C), which of these holds in "the" ZF(C) universe.

*) I'm definitely not imagining a universe of sets that somehow "really" exists, independent of any axioms. As a physics nerd, I think it would be preposterous to make obviously unfalsifiable claims about reality, like e.g. that there's an "actual" universe of sets.

What would it mean for there to be an "actual" universe of sets, as opposed to there being a "non-actual" universe of sets?

 

[Fredrik]

No. It's kind of the point of AC that it allows us to prove the existence of sets we couldn't prove before, and it's trivial that any theorem of ZF is also a theorem of ZFC.

I don't know what I was thinking when I wrote that. I must have misread one of those sentences. Now that I read them again, I don't see anything contradictory about them.

You still haven't justified your usage of the definite article, though. There are many models of ZF(C). In some, for example, 2^aleph_4 is equal to aleph_5, in others, to aleph_37. Which of these are you talking about when you talk about "the ZF(C) universe"?

This is news to me. Assuming that this is accurate, I would agree that it doesn't really make sense to talk about "the" ZFC universe.

 

[Preno]

See here and here.