# Where am I wrong in this "proof" that the collection of sets is countable?

Looking at sets (in ZF, Set Theory of Kunen) I could not escape from looking at logic as well.

A formal language is presented containing basic symbols ($\wedge,\neg,\exists,(,),\in,=,$ and $v_{i}$ for $i=0,1,\dots$).

Also things are said about free variables and bound variables.

Formulas are defined inductively ($v_{i}=v_{j}$ and $v_{i}\in v_{j}$ for any $i,j\in\left\{ 0,1,\dots\right\}$ and if $\phi,\psi$ are formulas then so are $\left(\phi\right)\wedge\left(\psi\right),\neg\left(\phi\right),\exists v_{i}\left(\phi\right)$for every $i\in\left\{ 0,1,\dots\right\}$).

Now my question: where am I wrong in the following statements/reasoning?

1. For every class $K$ there is a formula $\phi$ containing a free variable $v_{0}$ such that $K=\left\{ v_{0}\mid\phi\left(v_{0}\right)\right\}$

2. The collection of formulas is countable.

3. Based on 1) and 2) I conclude: there are only a countable number of classes.

4. Every set is a class.

5. Based on 3) and 4) I conclude: there are only a countable number of sets.

• See Skolem's Paradox . Dec 14, 2015 at 10:55
• In 1) you have to say : for any formula $\phi$ there is a class $K$ ... This means that the "number" of "specifiable" classes is countable, but it is possible that in the "universe" there are others. Dec 14, 2015 at 10:57
• This means that, in this case (ZFC and "similar") we have to take care about "there is"; i.e. we have to separate : "there is the (a) model of the theory and this model has a specified cardinality" from "the theory can prove the existence of some set with a specified cardinality". Dec 14, 2015 at 11:00
• Bracketing some metamathematical issues alluded to above: If classes are all definable by a formula with one free variable, then it won't in general be true that every set will correspond to a class. If you allow classes definable by formulas with set parameters, then every set will correspond to a class but there won't in general be countably many -- there will be as many as there are sets.
– user104955
Dec 14, 2015 at 11:07
• @MauroALLEGRANZA If I understand your second comment then existence of classes that do not correspond with a formula depends on the universe we are working in? And working in the universe of sets such classes indeed exist? Dec 14, 2015 at 11:10

There are two points here:

1. The enumeration of the formulas don't live "inside the model", it lives "in the meta-theory". It is something that the model has access to. And indeed, a model where every set is definable without parameters is necessarily countable in the meta-universe.

2. You are forgetting parameters. Every set is a class, that is true. But it is possible that there are sets that only have "nearly trivial definition", in the sense that you can't really defined them in terms of "simpler" sets. So such set is ostensibly defined by the formula $$x\in p$$, where $$p$$ is a parameter and you place the set itself as the parameter.

That is not a "true" definition in the sense that we think of, but it is legal in the sense that when a model is given you want to define a class and you are allowed to use parameters from the model, in particular you can use the set itself as a parameter when you define a class. So you define a class and it happens to be exactly the set from the parameter.

You are correct, however, that at most countably many sets are definable without parameters over any model of $$\sf ZFC$$. But they are definable externally to the model. And the enumeration is also external to the model.

• In Set Theory of Kunen I read: "Informally, we call any collection of the form $\left\{ x:\phi\left(x\right)\right\}$ a class. We allow $\phi$ to have free variables other than $x$, which are thought of as parameters upon which the class depends." So (if I understand you well) these parameters must be looked at as members of the model we are working in? I thought that here $\phi\left(x\right)$ had to be interpreted as a formula containing free variables $v_{0},v_{1},\dots v_{n}$ and that $x$ was some abbreviation of e.g. $v_{0}$. Dec 14, 2015 at 12:37
• Yes, that is correct. We often like to omit the parameters as they clutter things, but they are important (especially in points like these). The free variables $v_1,\ldots,v_n$ are our parameters but in fact it suffices to consider just $v_0\in v_1$ as our formula (so we only have one parameter). We fix it in each "instance" of the class, but we are allowed to change it from one instance to another, and that's how you can define every set using that formula just by changing the parameter. Dec 14, 2015 at 13:07
• Thank you! This explains a lot to me. Dec 14, 2015 at 13:23
• Thanks @AsafKaragila. I had the same question to myself as drhab, and that last comment clears a lot of things. Dec 21, 2021 at 7:45