11
$\begingroup$

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$
  • $\begingroup$ Wow, you really got everything covered. Definability with parameters, without parameters, and external definability. :-) $\endgroup$ – Asaf Karagila Nov 10 '15 at 5:44
  • $\begingroup$ IMHO, for all but a few very narrow specialties, Separation and Choice are the about the only axioms of set theory that the "working mathematician" need concern him/herself with when writing informal proofs. (Only a few maniacs like me actually write machine-verified, formal proofs.) For Separation, you only need to know that you cannot define a subset in terms of itself. You may get into trouble otherwise. For Choice, you only need to know that if you have a family of non-empty sets, you are entitled assume the existence of a function mapping each one of these sets to an element of itself. $\endgroup$ – Dan Christensen Nov 10 '15 at 16:14
  • $\begingroup$ ... the family of sets itself being the domain of this so-called choice function. $\endgroup$ – Dan Christensen Nov 10 '15 at 16:52
  • $\begingroup$ BTW, I think you might be missing some kind of restriction on parameter $p$. If you had $p=y$, as Asaf suggests, you would be defining the subset $y$ in terms of itself -- something I have suggested you avoid. You could have any number of other parameters in your selection criteria, just no reference the subset being defined. $\endgroup$ – Dan Christensen Nov 10 '15 at 17:41
  • $\begingroup$ @Dan: There are no restrictions on the parameters in the subset (or replacement) schema. The trick in my answer works when you are given a set and you need to supply a definition with parameters. Of course it doesn't work to define every set without parameters. $\endgroup$ – Asaf Karagila Nov 10 '15 at 22:13
8
$\begingroup$

It's certainly possible! There are models of set theory where every set is definable, without parameters! http://arxiv.org/abs/1105.4597 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$
8
$\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$
  • $\begingroup$ That's circular. In ZFC the only things that exist are sets. You can't pass $y$ as a parameter until after you prove it is a set, which is what you're trying to do. $\endgroup$ – Kevin Nov 10 '15 at 13:35
  • $\begingroup$ No, you already have a model. And you have $y$. Now you want to find it a definition. And if you allow parameters, which the subset schema allows, then you can in fact use $y$ as a parameter for its own definition. $\endgroup$ – Asaf Karagila Nov 10 '15 at 13:41
  • $\begingroup$ But your definition is in terms of $y$. That seems very slippery to me. $\endgroup$ – Kevin Nov 10 '15 at 13:42
  • $\begingroup$ But you're not proving the existence of $y$ in terms of $y$. This set already exists. There is no circularity. $\endgroup$ – Asaf Karagila Nov 10 '15 at 13:43
  • 1
    $\begingroup$ I have said all that I can say. You can sit down and read through a book in set theory, and see what's this is about, or downvote. But I really can't tell you much more than I have. Have a nice day. $\endgroup$ – Asaf Karagila Nov 10 '15 at 14:06
6
$\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
    $\begingroup$ I like the reverse Skolem paradox: model of ZFC which has an uncountably many finite ordinals. :-) $\endgroup$ – Asaf Karagila Nov 10 '15 at 5:45
  • $\begingroup$ Even though I don't know what Skolem's paradox is, I found your final paragraph very useful. It tells me that this pathology is possible, but that a beginner in set theory shouldn't spend too much time worrying about it! $\endgroup$ – user940 Nov 11 '15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy