This is something that came up in some of the comments on the recent “nimbers” post, and I thought it was worth promoting to the front, and getting up under an easy-to-find title in the “basics” series.
In a lot of discussions in all different areas of math, you encounter talk about sets and classes, and you’ll find people worried about whether they’re talking about sets or classes. What’s the difference? I mentioned this once before, but it’s buried in a discussion of the concept of “meta”, which is why I thought it was worth moving it to its own top-level post: if you don’t know the difference, you’re not going to look in the body of a discussion about the concept of going meta to find the explanation!
I’ll start with just the definitions, and then I’ll dive into the discussion of why we make the distinction.
- A class is any collection of things which have some common property that defines them: the class of logical statements, the class of numbers.
- A set is a class which is a member of a class.
- A proper class is a class which is not a set.
Back in the early days of set theory, people looked at what we now call “naive set theory”. Naive set theory is useful and interesting – but when you try to do complicated things in it, you encounter a problem which makes things fall apart. Naive set theory fails to distinguish between different kinds of things, and that makes it all to easy to use it create paradoxical statements and structures.
For example – take that old classic, the liar’s paradox. “This statement is not true.” Everyone who’s ever watched Star Trek has encountered that, right? If it’s true, then that means it must not be true. But if it’s not true, then it’s true.
The structural problem of that statement can be translated into set theory. It’s a statement that’s really talking about the set of truth-bindings of statements: the statement operates as a function from statements to true or false. So it’s saying is that it is a statement whose meaning is a function which maps some set of statements to either true or false, and that in its mapping of statements to true and false, it maps itself to false.
In terms of set theory, what’s a function F that maps from a value v to true or false? It’s a set, SF, where F(v) is true if and only if v∈SF. So a statement like the Liars paradox is really a set of true statement – and what it’s doing is asserting that it is not in its set.
To see the problem with that, we need to look at the complement of SF, SF-1. SF-1 is the set of values that are not members of SF: SF-1 = {x : x∉SF}. So when F says that a statement M is not true, what it’s saying is M¬it;SF, and therefore M∈SF-1!
Now, finally, here’s the problem. If M is the liars paradox statement, and F is the functional-meaning of M, then SF is the set of values v where F(v)=true. Is M a member of SF? No – because it says that it’s not true, so it necessarily map F(M) to false. . So then SF-1 must include M. But if SF-1 includes M, then that means that M was true, since what M said was that M would be found in SF-1.
If you keep pushing through the semantics, it comes down to a simple paradoxical construct: the liars set: the set of sets that do not include themselves as members, L = { s : s∉s }. The paradox is that if L∈L, then L∉L, but in L∉L then L∈L.
Since a big part of the point of set theory is to provide a simple, general toolkit for building well-founded mathematical structures, the ability to break it so easily was a serious problem. But no one wanted to give up set theory: it’s too powerful, and too easy to use, to just give up on it because of this problem. So people set out to find a solution. The easiest one which avoids the problem was proposed by Alan Turing, and refined by Kurt Gödel. The idea is that instead of just having one kind of collection of things called a set, we’ll create two different kinds of collections. Any collection of things is called a class. A collection of things which is also a member of some class is called a set. A class which is not a set is called a proper class.
This makes the liar’s paradox disappear. The reason it’s gone is that in this new formulation, the Liar’s set isn’t a set. It’s a proper class. So the class of sets that don’t include themselves as members is well-defined, and it doesn’t include itself – in fact, can’t include itself – because it’s not a set.
The way that this connects back to the surreal numbers and nimbers is that the nimbers form a proper class, not a set. And the traditional formulation of a field requires that it be defined in terms of a set of values. But the nimbers don’t form a set – they’re a proper class
As it happens, we don’t actually worry about that. In his book on the surreals, Conway handwaves his way past it by pointing out that for fields of numbers, there’s no particular reason to not allow the definition of class-fields, so long as we’re clear that they are class-fields and not set-fields. So – the nimbers are a class-field, and for most things that we want to do with them, the fact that they’re a class-field and not a set-field just doesn’t actually make a difference.
Maybe I’m beating a dead horse, but are there statements about the nimbers which are only true (or false) because they are are proper class rather than a set?
Jesse:
The main issue when it comes to the nimbers is the same one that comes up with the surreals: there are too many of them. One of the implications of the distinction between sets and classes is that sets always have a countable number of members. The surreals, and by extension the nimbers, include all of the numbers, *plus* more stuff – uncountably much more stuff.
That’s really why the field axioms don’t fall apart for classes like the surreals: because the reason that they’re proper classes is size, and the field axioms don’t really talk about size.
Well, ok, but there are still properties of other fields (e.g., the reals) which are very interesting and nevertheless require second-order logic. And once you get into second-order logic the distinction between sets and proper classes does become important.
Are there any such “interesting” properties of the nimbers? Or are all those properties confined to the world of first-order logic?
Ahem.
Don’t tell it to the reals.
It’s worse than that, even. “Uncountable” still has the connotation of infinite cardinals beyond that of the natural numbers. Proper classes are so large that they don’t even have cardinalities.
Are there any such “interesting” properties of the nimbers?
I confess I haven’t been following the nimbers posts, but one result for fields is that every field is contained in an algebraically closed field, but that result very much uses the fact that the fields are sets. So this might not necessarily hold for Nimbers.
Hmm, indeed. Can the properties of field extensions be expressed without second-order logic? If not, what is the Galois theory of the nimbers like?
This is straying far afield from where Mark wanted to go, I think, so I’ll just stop there. Haha.
It smells like a trick: class is something to which Whitehead’s paradox doesn’t apply – seems it is all that it says. And the paradox doesn’t apply since we have no words and no logic and no concepts to define it except by saying that is not that which can lead to the paradox.
Proper class is sooo huuge (lots of hand waving) that it has no elements, like non-empty set does. But it is some collection so it has something and even lots of it. But they are not really elements like the elements of the set since it would result in paradox and we don’t want that.
“A collection of things which is also a member of some class is called a set. A class which is not a set is called a proper class.”
This seems to imply that a proper class is not a member of any class. But surely it is a member of the class of all classes?
This seems to imply that a proper class is not a member of any class. But surely it is a member of the class of all classes?
There is no such class, just as there is no set of all sets. Not all objects we can describe actually exist, else we arrive at a paradox.
Confused:
The rules of the class/set distinction were formulated specifically to prohibit that. You can say “The class of all classes” in English – but there’s no way to define a class that way in the math. A class isn’t just a collection of objects – it’s a collection of objects which is defined by a common property posessed by all of the objects in it. There’s no way to formulate a statement defining the class of all classes.
As John Armstrong (among others) pointed out, I blew it.
The “size” distinction between classes and sets isn’t countability. It’s a notion that I’ve always thought of as a sort of higher-order countability.
You can define the “size of infinity” of one sort of infinite set by using a mapping between the natural numbers and the members of the infinite set. Infinite sets whose size can be defined that way are countable.
Then there are sets that are bigger than that – for example, the set of the real numbers. Because of the irrationals, the set of real numbers is infinitely larger than the set of integers. That’s an uncountable set.
Then there’s what I think of as the higher order notion of countable. There’s a notion of an infinite set whose can can, in some sense, be meaningfully measured. The real numbers have a cardinality – there’s a meaningful way of talking about how large the set is.
And then there’s the real disaster – immeasurable infinities. Infinites so large that talking about measuring them is just meaningless.
With the surreal numbers, you can easily show that any possible mapping between the entire set of reals, and the set of surreals between 0 and ω-1 will fail – because the surreals are so much larger. They’re so much larger that there’s no possibility of a meaningful way of talking about how large they are. It’s uncountability carried to an almost obscene extreme – not just uncountably large, but so large that talking about how large it is isn’t even meaningful.
It’s sort of like that great quote from the Hitchhikers God about how big space is: “Space is big. Really big. You just won’t believe how vastly hugely mind-bogglingly big it is . I mean, you may think it’s a long way down the road to the chemist, but that’s just peanuts to space. Listen…”
Proper classes are that big. Bigger than that even.
My favorite description of the problem has always been the Grelling-Nelson paradox (although I only just discovered it was called that when I searched for it just now…)
I’ll add this to the Basics series when I get my Mac back, but a comment:
The distinction between a class and a set is the distinction in philosophical logic between an intensional set and an extensional set. That is, all classes are sets, but not all sets are classes (in the sense of being defined by a shared set of properties).
This matters, because (i) historically the usage is not consistent with what you assert here (I know, this is a basics post), and (ii) modern usage is slightly different in philosophy – a set is just some group of things, while a class is a universal. A set can thus be an individual or a particular, while a class can’t. So it pays to be careful about these terms to avoid ambiguity.
I’m not sure that captures it, John (Wilkins). There are perfectly valid variants of set theory — honest ZF set theory, not Gödel-Bernays set theory with classes and such — that don’t incorporate extensionality.
For instance, the internal logics of many topoi which arise naturally as categories of sheaves on certain sites don’t have it. That is, if you properly define “elements of” sheaves, then there are different sheaves having the same elements, but all the other axioms of ZF hold. I’m pretty sure that these models can be constructed inside regular ZF set theory without referring to classes at all.
John WIlkins:”That is, all classes are sets”.
So you are saying forget about the concept of the proper class which is not a set. Stick to shared properties and for sets which are not classes don’t count their elements shared property that they are in the same set?
Mark: Great description. The part I like, though, is what comes right after this. You have some collection V whose elements you accept as legitimate mathematical objects — but it doesn’t contain arbitrary subcollections of itself, thanks to Russell’s paradox. Well, why shouldn’t those subcollections be legitimate objects, and collections of those, and so forth? Just like that, you’re looking at large cardinals — those collections that are just too huge to think about sensibly are probably just the beginning of the universe.
John Armstrong: That example of topoi sounds interesting. I’ve always meant to get into topos theory, but never had the time. I’m not sure that last statement about constructing the model in ZF holds, though. I would think that, if you could do that, you could take the Mostowski collapse of the model and get a model of ZF proper, violating Gödel II. Probably ZFC + “there is an inaccessible cardinal” would do it.
I
MarkCC: A class isn’t just a collection of objects – it’s a collection of objects which is defined by a common property posessed by all of the objects in it. There’s no way to formulate a statement defining the class of all classes.
Can’t we define the class of all classes as the collection of all objects which have the common property of “being a class”?
John A: You can construct models of class theories, such as Goedel-Bernays inside ZFC.
Shaker, the key idea is that classes are collections of sets. The only thing that can be a member of another thing is a set.
shaker:
First, a quick correction… I said that the set theory that introduces the class/set distinction was proposed by Turing. It was von Neumann. I unfortunately, constantly get their contributions mixed up. The set theory with the class/set distinction is called NBG set theory for von Neumann/Bernays/Gödel, for the three people who worked it out.
Anyway – in NBG theory, you can’t define “being a class” as a property that defines a class. In English, it may make sense to talk about “being a class” as a property. But in formalism of NBG set theory where the class/set distinction is defined, you *can’t* say that.
The fundamental point of creating the class/set distinction in NBG set theory was to create a distinction that made some statements inexpressible. You can’t talk about being a class as a property that can be used to define a class. In terms of the theory, it’s a meaningless statement.
One thing that you’ve got to remember when you’re dealing with abstract theoretical math is that natural languages like English are tricky: when you try to formulate something in the syntax of formal math, there are some things that just can’t be expressed because they have no meaning in the formal math – but we can say them in English quite easily.
My wife, who does research in natural language processing, has a favorite example of this: “Colorless green ideas sleep furiously.” That’s a perfectly valid sentence in English. But you can’t render it into a meaningful statement in any kind of mathematical logic – it’s meaningless.
“The class of all classes” is more subtle than the “colorless green ideas” statement – but when you try to reduce it to the pure mathematical logic of its semantics, you find that it’s the same kind of thing – it just *can’t* be rendered, because a statement about the class of classes is simply not meaningful in NBG set theory.
On the other hand, what’s sort of cool about NBG is that when you come across things like Russel’s paradox (which is the rendering of the Liar’s paradox into set theory), the old proof of its being a paradoxical statement actually becomes a *meaningful* proof that shows that it’s a proper class. Literally – the exactly same set of statements and inferences that lead to the contradiction in naive set theory are the proof that class defined by the “paradoxical” statement is a proper class. It’s a pretty nifty trick.
John:
The mathematical definition of class and set per NBG set theory is *different* from the philosophical definitions of classes and sets – in fact, it’s almost opposite.
The philosophical version defines a class as a special kind of set; the NBG version defines a set as a special kind of class. They’re using the same terms to talk about something different. The concepts are related on a deep level – the distinction is there for basically the same purpose – but the meaning that you end up with is quite different.
If a proper class is big (and atomic) then it has a cardinality (?)
I finished up my series of seminar talks for this term today, and got into the position of introducing Morita equivalence for rings, and thus introducing categories, functors and the category of modules over a ring to the newbies in the seminar series.
And my evil, evil professors just had to niggle me with set/class distinctions. I had more gaffes/minute during that section than in seminars during the complete last year.
My normal stance is to ignore the issue completely, and just assume that things work out.
Mikael:
I sympathize completely 🙂 As you can see from this thread, it’s the kind of thing that I find all too easy to mess up as well. So if I don’t need to explicitly worry about it for some reason, I also tend to try to ignore it until it comes back and bites me – because if I don’t ignore it, I’ll screw it up, and then it’ll come back and bite me anyway. But a fair bit of the time, it never really comes up – you don’t get bitten by ignoring it, because for a lot of things, it just doesn’t really matter. Even Conway just hand-waves his way past the class-field/set-field distinction, because it just isn’t important for the things he’s interested in doing with the surreals.
“First, a quick correction… I said that the set theory that introduces the class/set distinction was proposed by Turing. It was von Neumann. I unfortunately, constantly get their contributions mixed up. The set theory with the class/set distinction is called NBG set theory for von Neumann/Bernays/Gödel, for the three people who worked it out.”
In a strict sense Mark your correction is also wrong. The concept of distinguishing between different types of aggregates, manifolds or classes inorder to avoid Russell’s Pardox was naturally first introduced by Russell himself, it is his Theory of Types. von Neumann/Bernays and Gödel were all good Russellians at this point in their development.
With some assumptions (a universal choice operator, I think) it makes sense to say that the cardinality of a proper class is the class of all set ordinals, which is itself the unique ordinal which is a proper class. (This uses the convention that a cardinal number is the smallest ordinal number of its size.) All proper classes then share this cardinality, and you can construct a class bijection function to this class ordinal, by first dividing the elements of a class into ranks (birthdays).
Last week I went to a special memorial lecture at Caltech by William Hugh Woodin, recent surprising results in axiomatization of transfinite numbers. He had been a professor at Caltech, where’ my degree in Math included advanced infinitary set theory. Since computers did not help at all in that field, I shofted to CS and Mathematical Biology and other things.
As Wikipedia reports: “William Hugh Woodin (b. 1955, Tucson, Arizona) is a set theorist at University of California, Berkeley. He has made many notable contributions to the theory of inner models and determinacy. His recent work on Ω-logic suggests an argument that the continuum hypothesis is false.”
“He earned his Ph.D. from UC Berkeley in 1984 under Robert M. Solovay. His dissertation title was Discontinuous Homomorphisms of C(Omega) and Set Theory.”
“He served as chair of the UC Berkeley mathematics department for the 2002-2003 academic year.”
“He is the great-grandson of William Hartman Woodin, former Secretary of the Treasury.”
I asked him about unproven hunches by the recently deceased great Mathematician Paul Cohen, who proved the independence of the Cintinuum Hypothesis, and who’d gone to my high school (Stuyvesant, New York).
Hugh Woodin was pleased that I brought this up, and explained that he’d had many conversations with Cohen about this, including in this past year, Cohen’s last.
The new axioms used weird combinatorics and infinite games, and seemed tantalizingly close to making large ordinals and cardinals as unambiguous and the integers.
Without this lecture, I’d have been able to make little sense of Wikipedi’a short article on “Woodin cardinals.”
“… Woodin cardinals are important in descriptive set theory. Existence of infinitely many Woodin cardinals implies projective determinacy, which in turn implies that every projective set is measurable, has the Baire property (differs from an open set by a meager set, that is, a set which is a countable union of nowhere dense sets), and the perfect set property (is either countable or contains a perfect subset).”
“… The consistency of the existence of Woodin cardinals can be proved using determinacy hypotheses. Working in ZF+AD+DC one can prove that Θ0 is Woodin in the class of hereditarily ordinal-definable sets. Θ0 is the first ordinal onto which the continuum cannot be surjected…”
ZF+AD+DC defined as follows (again, thanks 3 times to Wikipedia):
ZF = Zermelo-Fraenkel set theory (without the Axiom of Choice = AC)
AD = the axiom of determinacy in set theory. “It was introduced by Polish mathematicians: Mycielski and Steinhaus. It states the following”:
“Consider infinite two-person games with perfect information. Then, every game of length ω where both players choose integers is determined, i.e., one of the two players has a winning strategy.”
“The axiom of determinacy is inconsistent with the axiom of choice (AC); indeed, it has been shown that it implies that all sets of reals are Lebesgue measurable and have the property of Baire.”
“AD implies the consistency of ZF. Hence it is not possible to prove in ZF that ZF is consistent with AD.”
DC = the axiom of dependent choices, “a weak form of the axiom of choice (AC) which is still sufficient to develop most of real analysis. Unlike full AC, DC is insufficient to prove (given ZF) that there is a nonmeasurable set of reals, or that there is a set of reals without the property of Baire or without the perfect set property.”
“DC is (over the theory ZF) equivalent to the statement that every (nonempty) pruned tree has a branch. It is also equivalent[1] to the Baire category theorem for complete metric spaces.”
For a while, I was fascinated again by transfinite visions. But it’s too hard for me. I thanked him, and returned to the finite cosmos.
I think that Confused (#10) and shaker (#20) made a good point, which remains unanswered.
You began with “A class is any collection of things which have some common property that defines them: the class of logical statements, the class of numbers.” That would allow the class of things that can be regarded as units, and since each class is a single thing (associated with its definitive property) that would allow a class of all classes.
Then (post #12): “A class isn’t just a collection of objects – it’s a collection of objects which is defined by a common property posessed by all of the objects in it. There’s no way to formulate a statement defining the class of all classes.” There still is, though, and such a class is equinumerous with the class of all properties that can be used to define classes (whose elements share the property of being properties).
Also, we can consider the class of all the ordinals (in ZFC, or in NBG, etc.), and the class of all the cardinals (similarly), and then we have two classes. We are talking about the pair-set of 2 classes. (We may not like it, but we are!)
Then (post #23): “Anyway – in NBG theory, you can’t define “being a class” as a property that defines a class. In English, it may make sense to talk about “being a class” as a property. But in formalism of NBG set theory where the class/set distinction is defined, you *can’t* say that.” Well, we can make us a formal system that does not suffer from Russell’s paradox. But what if we think of elementary arithmetic as being true in any possible world. That is, what if we think of cardinal numbers as being more than just formal fictions?
Ok, I had 2 somewhat unrelated questions.
a) Fields are a term you haven’t defined in the basics series. I had a kind of intuitive understanding of them but just now wiki’d the definition. That might be a good article.
b) I was waiting for you to get to these on your own but I will go ahead and bring them up. What about ‘traditionally defined’ nimbers. In Winning Ways nimbers, or fuzzy games as he calls them, are surreal games with the simplest (ie 0 nimber) being {0|0} or {{|}|{|}} if I remember correctly. That definition seems more intuitive to me. The game * (his sign like notation for these games) is the game such that the first person to move moves the game into a 0 game which is the game such that the first person to move wins. I was actually suprised this wasn’t brought up in the first surreal games post since in the games section of On Numbers and Games opens with something like:
“there are 4 types of games:
g>0 = Right wins
g
However, as much as I do not like it, somewhere deep down at the gut level, I do agree with the utilitarian approach -as long as something useful and consistent can be done with the conceptual machinery, some hand-waving can be tolerated.
Now Heidegger would have a problem with this forgetfulness and practicality in the name of ‘preparing’ beings and, in fact, the very Nature, for some utilitarian purposes but such issues are best left to fringe philosophers outside the realm of the Empire.
Enigman, the problem here is that isn’t writing out the formal axioms, but rather english accessible to the non-mathematician. There’s a reason we use formalism, though, and that’s because things tend to get lost in translation. In the formal construction, classes are not “things” of the type referred to in the first rule.
Jon:
Fields are discussed in the basics posts here, and defined by example here.
Have you read them? Perhaps not the most comprehensive description though, so more basics posts on algebras could be a good proposal if they aren’t enough.
Thanks Confused, another good point (I hope I do lie beyond those Empiricists’ reaches). And yest Antendren, if proper classes are not things, then problem solved. Cantor’s idea was also that proper classes are too big to be thought of as unities, as I recall.
My problem with that is not that set theories don’t work, for they do seem to. It’s just that, since I can think of all the ordinals, and all the cardinals, and of how there is a one-to-one correspondance between those two classes (so that they seem to have the same cardinality), hence they do not seem to be too big to be unities, those two (units).
Now, there is one way in which they could fail to be unities (any others?), and that is if they don’t really exist, not even in the tenuous way in which invisible unicorns (one of them, two of them) do. That is, if being a set is not a definite property. But then what are we talking about? Not numbers (one thing, two things). So what are we doing? Not mathematics!