Undefinable classes?

405 Views Asked by At

Note: this question has been changed substantially from its original form.

Originally I had asked whether or not it is possible to prove that all classes whose elements are 'truly arbitrary' are finite. After a bit more searching, I've figured out that what I intended to refer to are exactly those classes which cannot be defined by a formula in a given language.


In analogy with definable numbers, it would seem that there are definable classes, which can be expressed as a formula, and undefinable classes, which cannot.

I haven't been able to find much literature on the definability of classes, so where can I find more information on undefinable classes?


I would ask how to determine whether or not a class is undefinable given a universe $\mathbb{U}$ and a language $(\mathbb{U};U_{op},U_{rel})$ - but I'm pretty sure that 'undefinable' implicitly means this can't be done.

2

There are 2 best solutions below

1
On BEST ANSWER

In the standard set theoretic formulation, i.e. $\sf ZFC$, classes are not even objects in the universe. So the only way we can even talk about them is by formulas. So in this context, classes are always definable.

We can move to second-order theories where classes are also objects of the universe. There we can talk about classes which are definable using a formula that has no class variables appearing in it (i.e. a first-order formula), and a class which isn't definable like that.

But then we are moving from syntax to semantics. So the choice of model, and more importantly, the choice of classes in the model becomes important. Here's two examples:

  1. If $M$ is any model of $\sf ZFC$, then $(M,\in,\operatorname{Def}(M))$ is a model of von Neumann–Gödel–Bernays set theory (omitting global choice, anyway). Here $\operatorname{Def}$ denotes the collection of all definable classes.

  2. If $\kappa$ is an inaccessible cardinal, then $(V_\kappa,\in,V_{\kappa+1})$ is a model of Morse–Kelley set theory.

The theory of $\sf MK$ is much stronger than $\sf NBG$. It proves the consistency of $\sf ZFC$, for starts, whereas the first example show that $\sf NBG$ cannot prove the consistency of $\sf ZFC$ (since in that case you'd have a definable way in $\sf ZFC$ to do it).

Things can get even weirder. If $M$ is a countable model of any set theory, then it cannot compute the power set of $\omega$ correctly, so there are subsets of $\omega$ which are not in $M$. These are not definable classes, of course, since definable classes which are bounded are sets. And these "missing subsets" can be quite destructive to the set theory, if one adds them as a subset.

For example, it could be that a subset of $\omega$ codes a bijection of $\omega$ with $M$, or some well-ordering of $\omega$ which is much longer than the order type of the ordinals of $M$. On the other hand, if we add a subset of $\omega$ by forcing, then we didn't do a lot of damage to the model, but the new subset, from an external point of view was a collection of elements of $M$, so an "undefinable class" in the broadest interpretation.

For this reason there's a lot more difficulties when treating "arbitrary classes", and you normally want to somehow restrict your classes to be definable, or at least amenable (i.e. their intersection with any set is a set, thus excluding generic sets, etc.). We do get some benefit from using these undefinable classes, sometimes, in very technical situations (sharps in set theory are an excellent example), but those are all very technical, and it's better to first build a strong basis of knowledge before flying this high on poorly-glued feather wings, as they tend to melt and break down.

1
On

"No computation can be performed" is some very infomal expression, except if it is said in the context of computability. The questions "is this theorem provable, does there exist some algorithm that will prove it in a finite amount of time ?" are the kind of questions which make sens in this context. You can't hope to find a rigorous meaning to that if you don't go into the details of this theory. Here is the Wikipedia page of computability.