What are the subsets of an infinite set?

Question

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

Answer 1

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.

Answer 2

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.