So far, we’ve been talking mainly about the ZFC axiomatization of set theory, but in fact, when I’ve talked about classes, I’ve really been talking about the von Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other day that the ordinals are a proper class is an NBG proof.) NBG is an alternate formulation of set theory which has the same proof power as ZFC, but does it with a finite set of axioms. (If you recall, several of the axioms of ZFC are actually axiom schemas, which need to be distinctly instantiated for all possible predicates.) NBG uses one axiom scheme, but it’s possible to show that that schema only expands into a finite number of distinct axioms.
In ZFC, the sets are the things you can construct using the axioms; classes are things that are sets in naive set theory, but which you can’t define properly using the ZFC axioms. ZFC doesn’t talk about classes. NBG actually defines and uses classes as its basis, and it’s where the set/proper class distinction comes from: a class is a collection of sets; and a set is a class that’s a member of some other class.
Since NBG has both sets and classes, it’s effectively a typed theory, where there are two types: sets, and classes. We’ll use lowercase letters for sets, and uppercase for classes – and we’ll use that for axioms as well as variables (there’s an “Axiom of Extensionality” for classes, and an “axiom of extensionality” for sets).
For NBG, we define the correspondence betweens sets and classes with the same members using an onto function Rep, where Rep(A)=a if ∀x: x∈a⇔x∈A.
The axioms of NBG are:
- The axiom of class extensionality: (∀x: x;∈A ⇔ x∈B ⇒ A=B): classes are equal if and only if they have the same members.
- The axiom of set extensionality: (∀x: x;∈a ⇔ x∈x ⇒ a=b): sets are equal if and only if they have the same members.
- The axiom of Class Comprehension: For any formula
which does not quantify over classes, there is a class
such that
if and only if
is true. (This is actually a schema parametric in
- The Axiom of Pairing:
: for any two sets
and
, there’s a set with exactly
- The Axiom of size: For any class
such that
if and only if there is no total one-to-one function between
- The Axiom of union:
for any set
- the Axiom of powerset:
: For any set x, there is a set which contains all of the subsets of x.
- The Axiom of infinity: There exists a set
where:
- The empty set ∅ is a member of N; and;
- for each member x∈N, (x∪{x})∈N
Which is a fancy way of saying that there’s at least one infinitely large set, which is exactly Cantor’s construction of the natural numbers.
- The Axiom of Foundation: All non-empty classes are disjoint from at least one of their elements.
- The Axiom of regularity: All non-empty sets are disjoint from at least one of their elements.
Personally, I like NBG better that ZFC, precisely because it provides ways of talking about classes; ZFC pretty much throws up its hands and says “Outside my realm” when you get classes. I think that capturing proper classes in your set theory is both cool and useful. I also find proofs based an the axiom of size to be clearer than most other ways of proving things to be proper classes. Unfortunately for me, ZFC is pretty dominant in mathematical circles. Personally, I don’t really see why, but that’s the way it is.
Er, your casing rules for class and set axioms looks mixed up at the moment…
Misspelled von Neumann there.
I also like the fact that NBG talks about classes, but I wonder if it says the right things about them. At least ZFC is a good model of common intuitions about mathematics. E.g. intuitively we can talk about a pair of classes (I’ve mentioned that before, in comments here, and my most recent post is about Cantor’s paradox; it’s my favourite philosophical fact!), about them having the same number of members (e.g. the bijection between the standard ordinals and the standard cardinals). So it seems that classes ought to be able to be members of sets. Cantor’s paradox indicates (as far as I can see) that classes are a lot like potential infinities (which raises further philosophical questions…:).
You write: Unfortunately for me, ZFC is pretty dominant in mathematical circles.
Is that really true? I would instead say that most mathematical discourse uses “ordinary” naive set theory, retreating to ZFC when necessary to show that one hasn’t done anything illegitimate. Set theorists, of course, are more likely to explicitly show what axioms they are using — but they frequently adjust their axiom sets by leaving out choice, or adding large cardinal axioms.
In any event, NBG is a conservative extension of ZFC — it proves exactly the same statements about sets as ZFC does. ZFC does not have class variables, but mathematicians can still talk about classes while using the language of ZFC — a “class” in ZFC is a formula with a single free parameter; “classes” are “equal” if they have the same extension. NBG proves a few additional things about classes (for example the axiom of of size proves that the class of all sets can be well-ordered!), but I suspect that most of the time we wish to talk about proper classes we really just wish to talk about some formula of ZFC whose extension is not a set.
If I understand the axiom of size correctly, it asserts that the only properties which are non-collectivising (i.e. can’t be made into sets) are those in 1-1 correspondence with the class of all sets.
I’m not an expert on set theory, but this seems somewhat restrictive to me. I can see how the axiom of size rules out paradoxes such as Russell’s but why should there not be other classes or properties that are not sets but which are not as large as V – even if we don’t know what they might be.
Are there alternative, less restrictive approaches to this axiom?
Charles Tye: I am not entirely sure, but I think the axiom of size is more or less a replacement for ZFC’s axiom of replacement, and can be derived from it, foundation and global choice.
Basically, the axiom of foundation allows you to assign to every set a rank ordinal, and the sets below a given rank themselves form a set. This means that any class whose elements have bounded rank is a set.
On the other hand, any class whose elements do not have bounded rank must be at least as large as the class of all ordinals (replacement, plus any unbounded subclass of the ordinals is in one-to-one correspondence with the whole by a transfinite recursion argument.) Using global choice and foundation, you can well-order the class of all sets by rank first, and then get a one-to-one correspondence with the ordinals, so there is no intermediate size possible for non-set classes.
Well, you can at least speak metamathematically about classes, as formulas with parameters under an equivalence relation. A lot of theorems about classes become theorem schema. You’re right that ZFC itself doesn’t address these objects directly, but I think that’s a good thing; see below.
I can’t speak for all mathematicians, but when I see a legitimate type of mathematical object, the first thing I want to do is take collections of them, and collections of those, etc. Before long, if classes are legitimate, then so is an entire hierarchy of objects above the “classes”, and I’m dealing with not an NBG universe, but a ZFC universe with a large cardinal.
To me, it’s NBG that puts an artificial bound on the objects available. ZFC plus large cardinal axioms does a better job of capturing the idea of an unbounded universe. Of course, given that NBG is a conservative extension of ZFC, this is entirely a matter of opinion.
It seems to me, Chad, that proper classes of standard sets ought to behave a lot like sets, for pretty much the reasons that standard sets do, so that given the standard domain it makes sense to extend it by adjoining a large cardinal. But then I’m led by similar reasoning to consider the new proper class of all those new sets, and so on, adjoining large cardinals in some principled way (e.g. via a Reflection Principle). And if that endless process of adding more and more axioms to set theory was getting us closer and closer to a perfect description of objective collections (and allowing large cardinals does seem to tell us more about the sets that we already had) then we would want to consider the proper class of all of those sets, the sets described by aleph-null axioms. And we could not then simply adjoin another large cardinal (which would just be aleph-null axioms again), so that finally we would be looking at something less intuitive, such as NBG, anyway. In short, proper classes seem to be a way of pushing the counter-intuitiveness of standard sets out to infinity, out beyond the transfinite where it can be ignored by mathematicians (if not philosophers), which is worth bearing in mind (I think) when intuitive arguments for standard sets are given. (Incidentally, it seems that Logic Matters is soon to discuss Absolute Generality.)
First off, Enigman, thanks for pointing me to the Logic Matters blog.
I agree, the reasoning that leads us to postulate a single inaccessible cardinal should lead us to postulate lots of them. Where you go awry is here:
You don’t need |α| axioms to get a sequence of inaccessible cardinals with length α (assuming you have a definition of α). All you need is a single axiom which says “There exists a sequence of inaccessibles with length α”. For that matter, you could also say “There is no set which contains all the inaccessible cardinals”, which guarantees that they form a proper class; in fact, this is usually done.
It’s actually possible to push it much farther, but I won’t do that now. The point is, you don’t need NBG to reach these cardinals.
Also, I’m not sure I understand your point about “pushing the counter-intuitiveness of standard sets … out beyond the transfinite where it can be ignored by mathematicians”, since the standard sets aren’t being pushed out in the first place. I assume you’re talking about dealing with things like the Russell Paradox (“the collection of all objects x where x is not an element of x”). As I see it, there are only three ways of resolving the paradox:
the New Foundations approach, where you can’t make a set out of the phrase “x is not an element of x”, because it’s somehow malformed;
the NBG approach, which says that only certain objects (“sets”) can be members of other objects, and that the Russell collection is therefore not a “set”;
the ZF approach, where the Russell collection does not exist as a mathematical object because one does not have “access” to the entire mathematical universe when attempting to construct a set. In essence, the mathematical universe is a “potential infinity” which can never be completed.
Useful fact: if you hit C-x C-s, the Post button activates.
To complete the above comment, I think 1 is absurd; there’s nothing wrong with the question “Is x an element of x?”, so there shouldn’t be a problem forming a collection based on it. 2 and 3 both seem reasonable a priori, but! If you think about it, you still need potential infinites in NBG, to talk about collections of proper classes (they can’t be members of actual objects, remember). So you’re stuck with 3 anyway, and there’s no sense bringing in 2 as well.
That’s why I would pick ZFC as foundational. (At least over NBG or NF, not sure about the topos-theoretic foundations yet.)
Pingback: The Basics of ST Type Theory (plus Administrivia) | Good Math/Bad Math