A naive question about axiomatic set theory
I'm trying to teach myself some basic set theory by reading Set Theory for the Working Mathematician by Krzysztof Ciesielski, and I'm only in Chapter 1 but I'm already a bit puzzled.
To be concrete, let's work in ZFC.
The axiom of separation says that if $x$ is a set, $p$ a parameter, and $\varphi$ is a formula, then $y=\{u\in x: \varphi(u,p)\}$ is also a set. We can call this $y$ a subset of $x$.
Naively, I read this as saying that any formula-delimited collection of elements of $x$ is a subset. What I'm wondering is whether this axiom gives all the "subsets" (in the naive sense). That is, could there exist a collection of elements of $x$ that cannot be so delimited and is not a set? Or possibly whose status is unknown?
Great care (via new axioms) is taken to show that singletons $\{u\}$ are subsets, and also that the union or intersection of sets is a set. The complement of a subset should also work via $y^c=\{u\in x: u\notin y\}$. But the general question seems to be a non-issue in set theory. Is that because the proposition that all "subsets" are subsets follows from the ZFC axioms, or that the question is uninteresting? I suspect that I am just overthinking this...
I also own Set Theory by Kenneth Kunen and Set Theory (3rd edition) by Thomas Jech if you want to point me somewhere particular.
Comprehension scheme (or schema of separation) For every formula $\varphi(s,t)$ with free variables $s$ and $t$, set $x$, and parameter $p$ there exists a set $y=\{u\in x: \varphi(u,p)\}$ that contains all those $u\in x$ that have the property $\varphi$.
$\endgroup$ 63 Answers
$\begingroup$It's certainly possible! There are models of set theory where every set is definable, without parameters! In such a model, any "subset" (of some set in the model) which is not definable is not a set.
Meanwhile, it's "usually" the case that there exist nondefinable subsets, although this is of course hard to say precisely. For instance, if $M$ is a model of set theory of size at least $\aleph_2$, then we can find $a, b\in M$ with
$a$ is a subset of $b$, but
$a$ is not definable in $M$ in the language of set theory with $b$ as a parameter.
This is a good exercise. (HINT: given that $M$ has size at least $\aleph_2$, find some $b\in M$ such that $(\mathcal{P}(b))^V$ is uncountable.)
It's also possible for a model to "miss" subsets of a given set, because they are undefinable: forcing is a particularly spectacular way to build instances of a model $M$, an element $b\in M$, and a larger model $N\supseteq M$ such that $N$ "sees" more subsets of $b$ than $M$ does.
$\endgroup$ $\begingroup$Since we allow parameters, everything is definable in the silliest way possible. If you want to define the set $y$, just look at the formula $\varphi(x,p):=x\in y$ with $p=y$.
Now if $A$ is a set, and $y$ is a subset of $A$, then $y$ is defined by that formula, with the suitable parameter.
Of course, if you want to talk about definability without parameters, Noah gave a good answer.
$\endgroup$ 8 $\begingroup$Yes, it is possible that there may be subcollections of a set that are not sets.
However, by the comprehension axiom, such a situation can only arise if you have some external notion of "subcollection". So as long as you stay "inside" of a set-theoretic universe, all subcollections of sets must actually be sets themselves.
In typical applications, we presume that we are either staying inside of such a universe, or that the model of ZFC is big enough so that all subcollections are actually sets; working with models that are missing some subcollections is something mainly limited to technical set-theoretic or epistemological arguments.
If you're not at the point where you can wrap your head around Skolem's paradox, ignore the following.
If you have a countable model of ZFC, then its set of natural numbers must have only countably many subsets; consequently, "most" of the subcollections of its set of natural numbers are not actually sets of the countable model.
$\endgroup$ 2
