# Existence of sets, power set, & axiom of choice

What does it mean for a set to exist?

I have seen the axiom of choice stated that: for any collection of sets $\{S_\alpha\}_{\alpha\in A}$ there exists a set $B=\{b_\alpha \mid b_\alpha\in S_\alpha \text{ for all } \alpha\in A\}$. So in effect we are "choosing" an element from each $A_\alpha$ and forming the set $B$ out of those elements.

My main question is:
1. What does it mean for this set $B$ to exist? Generally, what does it mean for a set to exist?

Of course this may really be about the concept of existence in mathematics. I don't want to get all metaphysical or philosophical here (which is ironic, because I usually do want to get all nonsensical-philosophical). I'm looking for a direct mathematical answer/explanation.

Here is my intuition: in mathematics, we are always working with a collection (set?) of mathematical objects and their properties/relations (e.g. numbers, or sets of certain symbols, etc.). So for a set to exist, it just means that it is a member of the universe of sets that we are working in (or be in whatever model of whatever set theory we are working with).

E.g. if $\{\emptyset, \{a,b\}\}$ is our universe, then the set $\{a\}$ does not exist.

As a related side question, if we allow the power set of real numbers to exist, does that imply the axiom of choice? It seems like it should because for whatever collection of sets of real numbers we have, any arbitrary set with one element taken form each will be an element in the power set.

These probably have answers already here on MathSE, but this is far out of my expertise, so I have trouble understanding many of the more technical set-theoretic threads. I'd appreciate as simple an answer as possible, but do also appreciate any technical details, even if I don't understand them right away.

• "As a related side question, if we allow the power set of real numbers to exist, does that imply the axiom of choice?" At least according to one interpretation of this question, the answer is "no:" the theory ZF contains the powerset axiom, so proves that the powerset of the reals exists, but is known to not prove that the reals are well-orderable. (Also, even if it did that wouldn't imply full choice: choice says much more than just that the reals are well-orderable.) – Noah Schweber Jun 23 '18 at 16:06
• @Mauro I don't think that is quite correct. That a set exists should simply mean that it is a member of the set-theoretic universe, regardless of whether we can justify its existence via specific axioms. – Andrés E. Caicedo Jun 23 '18 at 17:42

Your intuition is generally right: To say that something "exists" in set theory (which is the same as saying that is "is a set") means just that it is an individual in whatever model or interpretation of the language of set theory we're considering.

When we're looking at the model from the outside, it may be possible that we can identify certain of its individuals by a particular property, and then we can ask whether all those individuals make up a set in the model -- which is nothing more or less than asking whether there is some individual in the model whose elements are exactly the ones we were pointing at before. This may or not be the case.

In particular, Russell's paradox points out that if we're looking at all the individuals in the model that are not elements of themselves (for all we know, that could be all of them!), then those individuals are not the elements of any set in the model.

Note well that in this model-theoretic view all the sets in the model have already existed all the time. Thus the axiom of choice does not actively create the choice set -- it just asserts that there is one somewhere in the model. And if it is right about asserting that, then the choice set has always been part of that model.

E.g. if $\{\emptyset, \{a,b\}\}$ is our universe, then the set $\{a\}$ does not exist.

Right. Though if that is the case, and neither of $a$ or $b$ happens to be $\emptyset$, then it is a strange set-theoretic universe because neither of its two individuals is an element of the other. So as far as the language of set theory is concerned, both $\emptyset$ and $\{a,b\}$ qualify as empty sets in your model, and the Axiom of Extensionality fails for this universe. That is, as long as $\in$ of your model is interpreted to mean the $\in$ relation we use outside it.

As a related side question, if we allow the power set of real numbers to exist, does that imply the axiom of choice? It seems like it should because for whatever collection of sets of real numbers we have, any arbitrary set with one element taken form each will be an element in the power set.

No, that is a misunderstanding of what the power set axiom says. What it says is that whenever $X$ is a set in our model, then there is another set $Y$ in the model, such that the elements of $Y$ is exactly all of those individuals in the model that happen to be subsets of $X$.

It may be that from the outside we can point to certain of the elements of $X$, such that there is no set in the model that contains just the elements we point to. That is not a problem for the power set, because the power set is not obliged to contain things unless they are in the model in the first place!

Another way of looking at it is if we stand outside the model and point to certain of the elements of $X$, and if it so happens that there is a $Z$ in the model whose elements are exactly the ones we point to then this $\mathcal P(X)$ has to contain $Z$ as an element. But if the second of these conditions are not met, then the power set axiom demands nothing.

• Thanks! This clears up much of my confusion. Regarding the power set: if by power set we mean all subsets in the grandest sense (the naive set of ALL subsets, can be denoted $2^\mathbb R$, yes? Is there a term for this kind of power set as opposed to others?). Without choice, such a "full" power set does not exist, yes? So by assuming the existence of this "full" power set, I was already assuming the axiom of choice, it appears. Or is it much more complicated than this, and I will have to study much more to understand the answer to this particular question? – jdods Jun 23 '18 at 18:34
• @jdods: Even with choice such a "full" power set will not necessarily exist in any given model. For example, if ZFC is consistent, then it has a countable model (by Löwenheim-Skolem), and such a model does not have enough elements to have one for each of the subsets of its $\mathbb N$ that we know at the metalevel. – hmakholm left over Monica Jun 23 '18 at 18:51
• The claim that your "full" power set exists cannot be formalized in first-order logic. You can state it in second order logic, but what you get from it there is somewhat disappointing. In model-theoretic terms what it actually gives you depends on what holds at the metalevel, so if you do your metamathematics in a world without choice, a second-order "full power set" axiom wouldn't give it in models either. On the other hands, second order logic does not have a complete proof system, so a full power set axiom would not allow you to prove anything that Separation doesn't already. – hmakholm left over Monica Jun 23 '18 at 18:54
• The philosophical outcome of this, I think, is that speaking about "full power sets" manages only to punt uncertainty about which subcollections of sets exist from the model to the metalevel. Not very satisfying if our goal was to achieve clarity about which assumptions out mathematical reasoning rests on. – hmakholm left over Monica Jun 23 '18 at 18:58
• Thanks for the info on that. It is more complicated than I had initially thought, which doesn't surprise me. I still don't know much about second and first order logic. That's probably something I need to study. Thanks again for the insight! – jdods Jun 23 '18 at 23:59