Proper classes and their consequences

I have two main questions:

1. What is a proper class? I've read that it's collection of objects that's "too big" to be a set, but in what sense is such a collection "too big"? Since I'd like this post to be accessible to people who aren't necessarily with the intricacies of symbolic logic, it'd be much appreciated if any symbolic logic expression be accompanied by an explanation of what it means and maybe a quick example of how it works (e.g. "One consequence of this axiom is that objects such as x={x}, which isn't disjoint from any of its elements, can't be a set. However, it [is/is not] a class because...").

2. Beyond the implications for philosophy of mathematics, would most mathematicians ever need to worry about proper classes vs. sets? If so, when and why? If not, what types of mathematicians would need to worry about this distinction?

-
There is a reasonably good explanation at the Wikipedia article. What's lacking about it? –  Qiaochu Yuan Dec 4 '10 at 21:38
I think the questioner is seeking in (1) a list of reasons why a collection might not be a set, and "is too big" isn't the complete list of reasons. –  Adam Dec 4 '10 at 21:53

A fairly general "definition" of "proper class" is that it means a collection of sets that is not itself a set.

In the usual picture of sets as constituting a transfinite cumulative hierarchy (in which each level contains all those sets whose elements are in earlier levels), proper classes are those collections that contain sets from arbitrarily high levels (e.g., the collection of all sets), so there is no level at which such a collection could live as a set. This picture corresponds to the Zermelo-Fraenkel axioms of set theory and related theories that allow you to explicitly talk about classes (the von-Neumann-Bernays-G"odel and Kelley-Morse class theories are of this sort).

Vopenka and his co-workers have developed a rather different intuition in which proper classes can be subcollections of sets. These proper classes are not too big but too imprecisely specified to be sets. This intuition is formalized in what Vopenka calls alternative set theory. Subclasses of sets are called semisets, and there's a book "Theory of Semisets" by Vopenka and Hajek. This set-up accommodates the "too complicated" examples mentioned in Adam's answer.

Quine also introduced, along with his set theory "New Foundations", a theory called "Mathematical Logic" that allows for proper classes. Here, these fail to be sets because they cannot be defined by stratified formulas (as in the set-existence axiom of New Foundations). The original formulation of "Mathematical Logic" was inconsistent, but a tamer version is not known (to me) to be inconsistent.

The reason I started this answer with the weak-sounding "fairly general" is that there's at least one theory of sets and classes in which classes can have other proper classes as members. This is a theory introduced by Ackermann. The motivating idea here is that a collection forms a set if all its members are sets and it is defined without reference to the general concept of set.

-
The "too complicated" examples that Vopenka dealt with also exist in positive set theories, where moreover there is an operation of closure such that the closure of every class is a set. I must say that upon reading the Vopenka-Hajek book the idea of their fuzzy proper classes seemed a bit unintuitive to me, perhaps due to their only examples being non-mathematical, such as the "semiset of one's ancestors that were humans and not apes". There is no such problem with positive set theories; see my answer here: mathoverflow.net/questions/55981 –  Sergey Melikhov Feb 19 '11 at 15:30

(Answer for 2.) One reason most mathematicians can avoid the theory of proper classes is through the use of Grothendieck universes. In brief, one chooses a strongly inaccessible cardinal $\kappa$, which is the cardinality of a set so big that it cannot be constructed through basic operations involving strictly smaller sets. Here, basic operations are:

• Products of sets
• Intersections of sets
• Unions of sets
• Functions between sets
• Subsets of sets

Then, you consider only the set of sets strictly smaller than $\kappa$, called a Grothendieck universe. Since virtually all set-theoretic constructions that occur in regular math can be boiled down to combinations of the basic operations, one never leaves this set. Having chosen a Grothendieck universe, one can then only consider categories whose objects are constructed in that Grothendieck universe. This means you get small categories, where you can genuinely talk about the set of objects and the set of morphisms.

The appeal of Grothendieck universes is that it makes the terminology simpler. The collection of all $R$-modules is a proper class, but only to preclude the existence of such pathological modules as 'the free $R$-module generated by the set of all sets which are not elements of themselves'. If you are actually working with $R$-modules, you will never accidentally try to create such a module; its just too ridiculously big. Therefore, it is sensible to consider some cut-off cardinality, past which all sets are 'too ridiculously big to matter'. Having made this cut-off, the majority of set-theoretic concerns disappear.

I should mention that this approach can be on shaky axiomatic foundations. The problem is that only one strongly inaccessible cardinal can be constructed in ZFC; the countable cardinal $\aleph_0$. This gives the Grothendieck universe of hereditary finite sets, and so this Grothendieck universe rules out the existence of any infinite set. Therefore, if you choose a bigger Grothendieck universe, you are implicitly including an assumption that a bigger strongly inaccessible cardinal exists. Personally, I am ok with this.

-
*The problem is that only one strongly inaccessible cardinal can be constructed in ZFC; the countable cardinal $\aleph_0$* -- but note that it's only in ZFC because we explicitly assume so via the Axiom of Infinity. Any and every strongly inaccessible cardinal ($\aleph_0$ included) in our set theory winds up there because we assume so (relative to Peano Arithmetic/$\text{ZFC}^{\text{fin}}$). –  Adam Dec 4 '10 at 22:09
@Adam: I was wondering: How do ZFC and ZFCU compare in consistency strength relative to $ZFC^{fin}$ (I actually asked this question earlier on MO, but decided to delete it)? –  Harry Gindi Dec 5 '10 at 18:40
@Harry: if by ZFCU you mean ZFC+"there exists a set which is a universe" then they are strictly linearly ordered by consistency strength: $Con(ZFCU)\Rightarrow Con(ZFC)\Rightarrow Con(ZFC^{\text{fin}})$. The requirement "must contain $\omega$" is usually part of the definition "is a universe", although @Greg didn't list it above; this accounts for the first implication. The second is because $V_\omega$ is a model of $ZFC^{\text{fin}}$ and $V_\omega$ is a set of ZFC. –  Adam Dec 6 '10 at 0:00
(some people use ZFCU for ZFC with a weak extensionality axiom which allows for "urelemente"; others use ZFCA (ZFC with Atoms) for this) –  Adam Dec 6 '10 at 0:02
By the way, as defined on the Wikipedia page a "universe" is NOT a model of ZFC -- it fails the Axiom of Infinity. I believe the standard definition is the one given by Bergman in definition 6.4.1 of his book (avaliable online here: math.berkeley.edu/~gbergman/245/Ch.6.ps ). In that definition, "$\omega\in U$" is part of the definition, ensuring that every universe is a transitive model of ZFC. –  Adam Dec 6 '10 at 0:08

Here's a basic answer to question 1: what makes a collection of sets a proper class? The answer has to do with models, so let's look at those for a moment.

A model of set theory, also called a "universe", is a collection $M$ of things we'll call "sets", but for now they don't have any extra structure, they're just points or objects. But a model also has some extra information in its definition, a relation $E\subset M\times M$. And I'll write the relation as an infix, so that $xEy$ is short for $(x,y)\in E$. This relation is how the model describes when one set is supposed to be an element of another: $xEy$ is supposed to satisfy all the axioms of set theory. That means $M$ and $E$ only make a model of set theory if statements like

For all $x,y\in M$, if $zEx$ holds whenever $zEy$ holds, then $x=y$. (Extensionality)

are true about $M$ and $E$.

Now, models of set theory don't have to "feel" like a universe of sets. For example, you can construct the "set" of real numbers in any model of set theory, and prove that the set of real numbers is uncountable. Well then, the model had better be uncountable for the real numbers to fit inside, right? No, in fact the Löwenheim-Skolem theorem implies that there's a model of set theory where $M$, the collection of all "sets", is countable. (Assuming there's any model at all, of course.)

Isn't that a contradiction? If $M$ is countable, then $r$ has a countable number of elements, so we can put them in one-to-one correspondence with the elements of $n$ (the "set" of natural numbers), and use Cantor's diagonal argument to find an element not on the list, etc.

Let's see why there actually isn't a contradiction: If $r\in M$ is the "set" of real numbers and $n\in M$ is the set of natural numbers, we can consider the collection of all "elements" of $r$, namely $R=\{x\in M: xEr\}$, and the collection of "elements" of $n$, namely $N=\{x\in M: xEn\}$ Then if $M$ is a countable model, $R$ and $N$ are both countable, so we can find a bijection $N\to R$... But there the reasoning stops. In order to get a contradiction with Cantor's diagonal argument, what we actually need there to be is a "set" $f\in M$ such that $f$ satisfies the conditions to be a "function" from $n$ to $r$, but that isn't what we have.

That leads us to the notion of "class" and "proper class". If we're working with a model $M$, then sets are elements of $M$ and "classes" of sets are subsets of $M$. Now some classes correspond to sets: any set $x\in M$ gives us a class of its elements: `X=$\{y\in M:yE x\}$. Since the axiom of extensionality means that a set is determined by its class of elements, it's natural to identify a set with its class of elements. In this way, we can ask whether a class $C\subset M$ corresponds to some set $c\in M$. If it does, i.e. $x\in C$ iff $x E c$, we can abuse terminology and call $C$ a set, but if there's no such $c$, we call $C$ a proper class.

As the other answers have pointed out, there are many reasons $C$ can fail to be a set and so be a proper class. $C$ could be too "big", like $M$ itself: $M$ never corresponds to a set $m\in M$ by Russel's paradox: we'd have $xE m$ iff $x\in M$ which is true, so $m$ would be a "set" of all "sets". Or $C$ could be a set that would give you something impossible if it existed, like a bijection between the set $r\in M$ of real numbers and $n\in M$ of natural numbers. Or $C$ could just be a subset of $M$ that's outside the scope of $M$ for no good reason, in which case there are standard ways of building a new model $M'\supset M$ in which $C\subset M\subset M'$ actually does correspond to an "set" $c\in M'$.

This is one way to look at how independence results are shown: you start with a model $M$ of set theory, and then build a new model $M'$ that is not only a model of set theory but also has other properties, such as every "subset" of "the real numbers" being "in bijection" either with "the real numbers" or with "the natural numbers", so that $M'$ satisfies the continuum hypothesis. Then you can rephrase that result as "If ZFC is consistent (has a model $M$), then so is ZFC+CH (there's a model $M'$ of both)."

-

Let me restrict and better formalize this question to ask, "If we have some first-order formula $\varphi(x)$ expressible (with parameters) in the language of set theory, when will $\lnot \exists x \varphi(x)$ be true?" In other words, when will we have an object that cannot exist as a set when sufficiently described? For example, the question of whether the class of all sets is proper is equivalent to the question of whether $\lnot \exists x \varphi(x)$ where $\varphi(x) \equiv \forall y(y \in x)$. Since this statement is easily provable in ZFC, we say that the class of all sets is indeed proper. As another example, we can consider the existence of a generic filter for some partial order as mentioned by Adam. In this case, we could fix a partial order $\mathbb{P}$ and have $\varphi(x)$ be the statement "$x$ is a filter on $\mathbb{P}$ intersecting all dense subsets of $\mathbb{P}$.'' There may be many such $x$ external to the universe that satisfy these criteria, but if $\mathbb{P}$ is a nontrivial forcing notion such as the forcing to add a Cohen Real, we will be able to prove $\lnot \exists x \varphi(x)$ so that any such filter $x$ cannot be a set in the universe. Thus any such generic object must be a proper class.

In this sense, I would characterize a class as being proper when its existence as an object in the universe would cause set theory to be inconsistent. Since we consider a wide variety of models in set theory today (some which may even be sets themselves), I would argue that "too big" is a somewhat outdated intuition for characterizing all proper classes that can arise. For example, if we consider a countable model $M$ of ZFC, we can force to add a wide variety of sets to it that are proper classes of $M$. Also, if $0^{\sharp}$ (a Real number encoding truth in $L$) exists, then this will be a proper class of the constructible universe $L$ containing all ordinals. I therefore claim that a proper class is merely an object that reveals too much about the universe in question to be a set in this universe.

In light of these considerations, I would always consider proper classes in terms of specific models of a theory. In this sense, proper classes are ubiquitous. For example, the set of all primes in any model of Peano arithmetic would be a proper class in the context of this model. Pure mathematicians may need to consider questions about proper classes of models in proofs. For example, when Andrew Wiles proved Fermat's Last Theorem, he appealed to the existence of a Grothendieck universe, which is a proper class of any set-theoretic universe without an inaccessible cardinal. Since we cannot even prove the consistency of the existence of such a cardinal in ZFC, a mathematician should be aware that he/she may be appealing to a stronger theory than set theory alone when assuming that Fermat's Last Theorem is true (although the discussion on Inaccessible cardinals and Andrew Wiles's proof seems to suggest this large cardinal assumption was inessential). As Greg pointed out, it may be sufficient to only consider universes with an inaccessible cardinal for most mathematics thereby eliminating the need to consider proper classes. However, one never knows when a new theorem may rely on the use of large cardinals with even greater consistency strength. For example, there is a result in category theory appealing to the existence of a cardinal with very large consistency strength (Vopěnka's Principle). There are also proper class considerations to be made in determining whether it even makes sense to talk about a conjecture. (i.e., is it formalizable in the language?)

Finally, as a point of clarification to Greg's post, $\aleph_0$ is technically not an inaccessible cardinal under the standard definition I'm accustomed to, which requires the cardinal to be uncountable. The reason for this is because inaccessibility is considered a large cardinal notion, whose consistency should always be independent of ZFC. Since the (consistency of the) existence of $\aleph_0$ is provable from ZFC, it should not be characterized as a large cardinal. However, as noted, it could be considered a large cardinal in the absence of the axiom of infinity.

-

Off-hand, I can think of at least two reasons why a collection whose elements are all sets might fail to be a set:

1. The collection is too big (which you've mentioned)

2. The collection is too complicated. This is the case, for example, with:

1. Generic filters -- for $M$ a model of ZFC, an $M$-generic filter is not an $M$-set even though every element of the filter is an $M$-set and the filter itself has the same cardinality as an $M$-set (and is therefore not "too big").

2. Sets which code information that the set theory "ought not know" -- for example, zero sharp is a subset of the constructible universe, yet not a set of $L$ (nor adjoinable to $L$ by forcing) because it contains information $L$ cannot know.

3. Sets introduced by compactness or ultraproduct arguments. For example, an ultrapower of a model of ZFC taken with a nonprincipal ultrafilter will satisfy the axiom of regularity, yet will contain ill-founded sets. This is possible because the order type of any infinite descending $\in$-chain is not a set (a phenomenon which was first explained to me here).

Aside from that, there is also the case you mention of "obviously" ill-founded sets (that is, ill-founded sets whose $\epsilon$-chain is also a set), which are simply excluded by fiat.

-