In school, I have always seen sets. I was watching a video the other day about functors, and they started talking about a set being a collection, but not vice-versa. I also heard people talking about classes. What is their relation? Some background would be nice.

It has to do with something called Russell's paradox, but I don't know what that is.

I think that the difference between a family and a set is that the former is a function and the latter is a set. Is this right?

  • 2
    $\begingroup$ You can also read this thread for information about Russell's paradox and this one for the difference between a class and a set. $\endgroup$ – Asaf Karagila Jul 19 '12 at 20:09

The idea behind a "collection" is simply a notion of a bunch of mathematical objects which are collected into one big pile. Think of it as a big bin full of trash, diamonds and empty bottles of beer, it doesn't have to make sense what is in this collection, it's just a collection.

One of the problem to explain these things to people who are not mathematicians (or trying to "outsmart a set theorist", as I ran into several of those) is that the notion of a collection is not fully formal unless you already know what sets and class are, and even then it's not exactly what we mean.

Let me start over now. Doing mathematics we often have an idea of an object that we wish to represent formally, this is a notion. We then write axioms to describe this notion and try to see if these axioms are self-contradictory. If they are not (or if we couldn't prove that they are) we begin working with them and they become a definition. Mathematicians are guided by the notion but they work with the definition. Rarely the notion and the definition coincide, and you have a mathematical object which is exactly what our [the mathematicians] intuition tells us it should be.

In this case, a collection is a notion of something that we can talk about, like a mystery bag. We might know that all the things inside this mystery bag are apples, but we don't know which kind; we might know they are all Granny Smith, but we cannot guarantee that none of them is rotten. A collection is just like that. We can either know something about its elements or we don't, but we know that it has some.

Mathematician began by describing these collections and calling them sets, they did that in a relatively naive way, and they described the axioms in a rather naive way. To the non-mathematician (and to most of the non-set theorists) everything is still a set, and we can always assume that there is a set theorist that assured that for what we need this is true. Indeed, if we just wanted to discuss the real numbers, there is no worry at all we can assume everything we work with is a set.

This naive belief can be expressed as every collection is a set. It turned out that some collections cannot be sets, this was expressed via several paradoxes, Cantor's paradox; Russell's paradox; and other paradoxes. The exact meaning is that if we use that particular axiomatic description of "what is a set" then we can derive from it contradiction, which is to say that these axioms are inconsistent.

After this happened several people began working on ways to eliminate this problem. One method in common was to limit the way we can generate collections which are sets. This means that you can no longer derive such contradiction within the theory, namely you cannot prove that such collection even exists - or rather you can prove it doesn't.

The common set theory nowadays called ZFC (named after Zermelo and Fraenkel, the C denotes the axiom of choice) is relatively close to the naive way from which set theory emerges, and it still allows us to define collections which are not sets, though, for example "the collection of all sets". These collections are called classes, or rather proper classes.

What is definable? This is a whole story altogether, but essentially it means that we can describe it with a single formula (perhaps with parameters) of one free variable. "$x$ is taller than 1.68m" is an example to such formula, and it defines the class of all people taller than said height.

So in ZFC we may define a collection which is not a set, like the collection of all the singletons, or the collection of all sets. These are not sets because they are too big, in some sense, to be sets, but they are classes, proper classes. We can talk about collections which are not definable but that requires a lot more background in logic and set theory to get into.

To sum up

Classes are collections which can be defined, sets are particular classes which are relatively small and there are classes which are not sets. Collections is a notion which is expressed via both these mathematical objects, but need not be well-defined otherwise.

Of course when we say defined we mean in the context of a theory, e.g. ZFC. In this sense, sets are things which "really exist" whereas classes are collections we can talk about despite their possible nonexistence.

One last thing remains, families. Well, as you remarked families are functions. But functions are sets, so families are sets. We can make a slight adjustment to this, and we can, in fact, talk about class functions, and an index which is not a set but a proper class. We, therefore, can talk about families which are classes.

Generally, speaking, if so, a family is a correspondence from one collection into another which uses one collection as indices for elements from another collection.

To read more

  1. What is the difference between a class and a set?

  2. Why is "the set of all sets" a paradox, in layman's terms?

| cite | improve this answer | |
  • 1
    $\begingroup$ @AsafKaragila "classes are collections which can be defined, sets are particular classes", but not every set can be defined/is definable since there are only countably many definitions. So what is the exact difference between a class and a collection? $\endgroup$ – Dávid Natingga Oct 26 '14 at 19:27
  • 3
    $\begingroup$ @David: We allow parameters in the definition of classes. So despite having only countably many formulas, the choice of variables is uncannily large. The exact difference is that a collection is a notion whose interpretation is context dependent, it could be a set, or a class, or neither. $\endgroup$ – Asaf Karagila Oct 26 '14 at 19:50

When building foundations of mathematics using set theory, we want a system of axioms that gives us lots of sets (so we can do other mathematics with them) but is not contradictory.

An early attempt at axiomatising set theory included the "Axiom Schema of Comprehension", which says that if $p(x)$ is a first-order formula in the language of sets (a bit technical, but you can take it to mean "a statement about sets which is either true or false for each set x"), then $\{x : p(x) \}$ is a set. Russel showed, however, that using this axiom leads to a paradox: take $p(x)$ to be "$x$ is not an element of $x$", then considering whether $\{x : p(x) \}$ is an element of itself leads to a contradiction.

So, when we axiomatize set theory, we must be more restrictive about what is a set. However, $\{x : p(x) \}$ is still a useful notion and we call it a "class". In particular, formula $p(x)$, which we use to define classes, have the variable $x$ ranging over just sets, so we do not get Russel's paradox. Note that a class can still be a set: in fact, all sets are classes. We call classes that are not sets "proper classes".

| cite | improve this answer | |
  • $\begingroup$ I don't know of any formal definition of a collection, it may just be an informal notion? Due to the limitations of first order logic, not all collections (used informally ;) ) of things we would like to consider arise as classes. $\endgroup$ – tmh Jul 19 '12 at 19:58
  • 1
    $\begingroup$ What about "that thing which contains the class of all sets, and the class of all ordinals, and nothing else"? It cannot be a set because sets cannot contain proper classes. It also cannot be a proper class because it has only two elements. Yet it would be a strange restriction not to have it, because you implicitly use it if you speak about those two classes (the phrase "those two classes" already implies that you have a bijection between it and some two-element set, or you couldn't reasonably use the word "two" here). $\endgroup$ – celtschk Jul 19 '12 at 20:26

In predicate logic, we might have a statement like "for all values of $x$, $\phi(x)$ is a true statement", where $\phi(x)$ might be a statement such as $x=x$. What are the "values of $x$" that we are talking about? Well, those values of $x$ are "sets".

Set theory allows us to generate classes of sets: we can say, for example, "the collection of all sets $x$ that satisfy a condition $\phi(x)$". In set builder notation, this is written $\{x:\phi(x)\}$. The question might arise: can we assume this new class of sets is a set itself?

Intuitively, it may seem reasonable to consider $\{x:\phi(x)\}$ to be a value of $x$. However, Russell's paradox shows us that such an assumption leads to a contradiction.

The paradox asks us to consider the collection of all sets $x$ that are not members of itself. That is $\{x:x\not \in x\}$; we will call this set $R$. Is the resulting class a member of itself? Well, if we accept $\{x:x \not \in x\}$ to be a possible value of $x$, then we arrive at the contradiction that this set, $$R \in R \iff R \not \in R$$

So, sets are the members of the universe of discourse: that is, they are all the "values of $x$" that we refer to when we create a statement using quantifiers like "for all $x$" or "there exists an $x$".

Classes on the other hand, are collections of sets. Some classes are sets, such as $\{x\}$ (in most set theories), but others are not, such as the class $R$ described earlier. All sets are classes, but not all classes are sets.

| cite | improve this answer | |
  • 7
    $\begingroup$ This answer explains Russell's Paradox quite clearly. However, it does not answer the question about the difference between set, collection, and class. $\endgroup$ – Code-Guru Jul 19 '12 at 19:53

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.