3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What exactly do you mean by "class"? Are they different from "sets"? Which version of set theory are you asking about? ZFC? VNB? NF? Or your own version? Are you asking about semantics? About constructability? More background would help here. $\endgroup$ – Somos May 4 at 5:21
  • $\begingroup$ @Somos I was thinking mostly in terms of naive set theory (a la Cantor) and universal algebra - with the the understanding that every 'set' is an instance of a 'class' but not the other way around. If I had to choose a formal theory, I would go with VNB (or VNBU, if that's a thing). I'm asking more about syntax than semantics, though I should probably understand a bit more about model theory first. $\endgroup$ – R. Burton May 4 at 21:52
  • $\begingroup$ There is no precise definition of "naive set theory". We still don't know exactly what you mean by "class". Cantor didn't use classes. Naive set theory is plagued with paradoxes. Some is due to infinite sets. Some with what it means exactly to define a "set". $\endgroup$ – Somos May 4 at 21:59
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Classes are always definable" with parameters. The question is vague enough to leave open the possibility that parameter-free definability is meant. $\endgroup$ – Andreas Blass May 7 at 23:04
4
$\begingroup$

"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.

$\endgroup$
  • $\begingroup$ Thank you for your answer, I will try and keep this in mind. However, the focus of the question was less on the definition of computability and more on the problems incurred by placing too-few restrictions on what can go into an infinite class. $\endgroup$ – R. Burton Apr 25 at 16:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.