# What are the subsets of an infinite set?

In the ZFC set theory the "Axiom schema of specification" states that given an infinite set z, for any formula $\phi$ the subset $\{x\in z:\phi (x)\}$ always exists. My question is: Are there any other means for assuring the existence of subsets not specified this way? (See the Wikipedia article) https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory#3._Axiom_schema_of_specification_.28also_called_the_axiom_schema_of_separation_or_of_restricted_comprehension.29

• Not really a problem with the question, but I would like to point out that the axiom schema does not require $z$ to be infinite, nor is the produced set necessarily a subset of $z$. – Paul Sinclair Feb 10 '17 at 0:00
• @Paul: the produced set is necessarily a subset of z . – Zoltán Csereháti Feb 10 '17 at 14:24
• Sorry, you are right. I was thinking of the existence of $\{\phi(x) : x \in z\}$, which is a different schema. At least I was right about $z$ not needing to be infinite. – Paul Sinclair Feb 10 '17 at 17:10

The well-ordering theorem or its equivalent the axiom of choice can do so. A classic is a Vitali set You define an equivalence relation on the reals in $[0,1]$ by $x \sim y \iff |x-y| \in \Bbb Q.$ This gives you uncountably many equivalence classes, each countable. Now the axiom of choice says there is a set having one member of each equivalence class. We can't write a formula $\phi$ to separate out that set.

• That is not quite correct. Separation allows parameters to be used. So in fact, every set can be obtained using separation by allowing a parameter to be used as the set itself. – Asaf Karagila Feb 9 '17 at 19:43
• Not to mention that obtaining a specific set happens in a model. And certainly there are models where there is a parameter free definition of a Vitali set (e.g. in $L$ there is one). – Asaf Karagila Feb 9 '17 at 19:47
• @Zoltan: That is not true. You are working inside a given model. The set already exists. – Asaf Karagila Feb 9 '17 at 19:50
• @Zoltan: Exists where? In what model? – Asaf Karagila Feb 9 '17 at 20:18
• @Zoltan: And there are countable models of set theory. In those only countably many sets exist. – Asaf Karagila Feb 9 '17 at 20:42

The separation schema is not just for a single-variable formulas. Parameters are allowed. So given any subset $A\subseteq X$, it is an eligible parameter for defining a subset. Namely, $\phi(x,A)$ defined as $x\in A$ is a valid formula for a separation axiom. And of course that $\{x\in X\mid x\in A\}=A$.

You might want to ask whether or not every set can be obtained using a parameter free-formula, and now we can prove that it is consistent that there are sets which cannot be obtained that way. Of course, things are even worse, since the same set can have different definitions which depend on the ambient universe of sets in which we work. So it is possible that some sets (e.g. a Vitali set mentioned by Ross) does have a parameter free-definition in some universe of set theory, but not in another.

The question, ultimately, is what are we trying to do. If we want a definition which provably does something, then the answer is most likely negative; whereas given a set in a universe, we want to know whether or not its subsets are all definable without parameters (from a meta-theoretic point of view, at least), then this becomes a somewhat more concrete question, but now there are additional constraints as to whether or not the answer is positive or negative.

• You are not allowed to define the subset A using itself. – Zoltán Csereháti Feb 9 '17 at 20:08