set theory

Set theory treats all mathematical objects as the same kind of thing, a set, from whose elementary properties all of mathematics can gradually be built. The essence of a set is that it contains other things (called its elements or members). There is no need to specify the sense of containment in any detail: it is a purely abstract notion.

Georg Cantor began with the loose idea of a set or collection or group of things (not group in the technical sense), and worked out how to treat these collections as individual objects in themselves. He bit the bullet and studied properties of infinite collections, and found there were definite rules, and in fact different sizes of infinity. At the time this was held by many to be unacceptable, and even absurd. He was hotly attacked by intuitionist mathematicians such as Leopold Kronecker.

Gottlob Frege considered classes to exemplify some property, and in particular thought about the numbers as abstract entities: what every three-member collection had in common was the property of having three members, so this property defined the class of all such things. This he identified as the meaning of the number.

Bertrand Russell discovered the paradox that bears his name and it was conceded that you could not simply consider any class you pleased and expect it to behave the way Cantor had worked out. Some classes were inherently contradictory. Russell and Alfred North Whitehead developed a solution to this in their Principia Mathematica, requiring objects to exist in a hierarchy of types, so that a lower one could not dominate a higher one.

Ernst Zermelo also proposed a hierarchical resolution in about 1908, but his was an axiomatic construction, that is it began with the most elementary properties, and only admitted to existence precisely those entities that could be shown to obey the properties. (Whether there could be entities other than those that can be proved to exist is a permanently open question: this is the axiom V = L, and it has been shown to be independent of Zermelo's construction of set theory.)

He began with the notions of membership and equality. Then the only thing that can be said about a thing a and a set b is that a ∈ b. Two sets are the same set if they have the same members. A set with several members a, b, and c is denoted {a, b, c}. From here Zermelo admitted axioms, principles so obvious that they must be true. If a and b are sets then {a, b} is a set. The set uniting all their elements is a set. If some of the elements have a property in common, then there exists a set composed of exactly those elements that have the property: a subset. The set of all subsets of a set is a set.

There are about ten axioms in all (depending on the exact formulation), and they are called the Zermelo-Fraenkel axioms, or ZF, also honouring Abraham Fraenkel, who refined them around 1921. This write-up is a very general survey, and mathematicians reading it will be painfully aware of how vague I'm being. More detail will no doubt be found under specific heads such as Axiom of Separation when I or someone else gets around to them. ZF is absolutely central to all of modern mathematics. Alternatives have been proposed, but they seem mere shadows of the original conception. In the standard theory, everything is a set. It is possible to work with ZF plus atoms (called ZFA), where an atom is something that isn't a set but can be a member of a set -- but it is unnecessary.

There exists an empty set (or null set). It has no members, is denoted { } or Ø, and there is only one empty set: any two sets having no members have the same members, so are the same set. There exist one-member sets. If a is a set then {a, a} is a set (stated above), and that has the same members as {a}, so {a} is a set.

Build the numbers as follows. 0 = { }. 1 = {0}. 2 = {0, 1}, i.e. {0, {0}}. Build up from there, 3 = {0, 1, 2} and so on. All the familiar properties of the numbers 0, 1, 2, ... can be reformulated equivalently as set-theoretic properties of this particularly hierarchy of sets. Then other structures such as relations and functions can be considered as subsets of certain large combinations of these.

To define an infinite set requires a new axiom in addition to the ones I've introduced, and that allows a set omega equal to {0, 1, 2, 3, ...}. This introduces a completely new arithmetic of infinities, and leads to the creation of two hierarchies, the cardinals and the ordinals. These go on for ever and ever and become seriously more infinite in profound ways as they go on, but some properties would produce an infinity so large that they cannot be produced with the existing axioms, and a new one has to be enacted just to create them. Such sets are called inaccessible.

---

Disclaimer for mathematicians. This is written largely off the top of my head, so I'd appreciate correction by /msg if you spot a substantive factual error: but I'm trying to keep technical notation and detail out of it. It's already a long enough introduction. Feel free to beat me to nodes for any of the details, though I'll get to them eventually.

To Gritchka's excellent historical survey I might add a comment or two from the perspective of an aspiring pure mathematician.

A few decades ago it was fashionable to say that "set theory is the machine language of mathematics" -- that is, that ultimately all mathematical statements have force by virtue of their theoretical possibility of transcription, "compilation" if you will, into propositions of set theory. The benefits of this reductionist approach are obvious: axiom systems for set theory are short, and if you accept an axiom system, you are forced to accept any statement which can be compiled into it -- never mind the improbability of actually doing this compilation, as mathematicians are already accustomed to nonconstructive existence theorems. (Some people have done interesting combinatorial research on the rate of growth of proofs as they are reduced to axiom systems.)

However, there are several axiom systems you might choose: set theorists have standardized on ZFC for the most part, but category theorists routinely require the notion of a proper class (a class which is not a set) and therefore must work in a variation of Gödel-Bernays set theory. Working mathematicians not interested in the foundations of mathematics usually ignore all these issues and use something much less formal which probably resembles the Kelley-Morse variant of GB.

All these systems are formulated in classical logic, but what if your work requires another logic entirely? The semantics of type theory, for instance, closely resembles certain intuitionistic logics, and those interested in quantum mechanics or quantum computing need yet another group of logics. A set theory formulated in a nonclassical logic would be entirely different from the standard ones.

To me, however, the most convincing objection to the set-theory-as-primary approach is that mathematicians don't work that way. We have things in mind that we want to use mathematics to deal with, and we treat the set theory, the category theory, the logic, the physical world, or something else as primary depending on what works best. And when we want to study a particular theory, we need to build a metatheory around it anyway; so the better way to proceed is to be able to describe all of our theories in terms of each other.

These thoughts come largely from Paul Taylor's excellent book Practical foundations of mathematics (in the series Cambridge studies in advanced mathematics), which I encourage anyone interested in its topic to read, after getting some familiarity with basic classical logic. For that you might turn to Mathematical logic by Ebbinghaus, Flum, and Thomas.

Naive set theory, and just what's so naive about it

- a symbol-less intro for non-mathematicians

Created as part of 10998521's Maths For The Masses project

Set theory is the study of collections of things. Now that's a very simple notion, and one on which we have some definite intuitions. Amazingly, those intuitions are wrong, as I'll demonstrate.

First off, what's a set? Well, we're going to define a set as "a bunch of things". What's a thing? Quite obviously, anything's a thing, right? Anything you can name, or consider possibly having a name. Now, think of something. Anything. Now think of another thing. Now think of those two things. That's a set, that is!

If we call your first thing "a" (I don't care what it actually was - your left arm, nate, love, 2, everything, whatever), and if we call the second thing "b", then the set I mentioned is "the set consisting of a and b". Let's call that set S.

Now, we've given S a name, right? So S is a thing, right? So we can talk about S being in other sets. In fact, let's consider a new set which consists of S and some other thing (again don't worry what - call it a pilchard if you really can't deal with the abstraction) which we'll call c, and let's call this set T. So S is in T, and c is in T. Now here's a question for you - is a in T? There are two possible intuitive answers to this, both of which make their own sense, but only one gives a satisfactory and useful concept of sets. On the one hand, you could answer "Well, a is in S, and S is in T, so clearly a is in T.", which makes sense, or alternatively you could answer "Sure, a is in S, but we've said S is a thing in itself, and it's that thing that's in T not the things in it. So a isn't in T, it's just in something that's in T." which also makes a slightly more convoluted sense.

Now, that second logic is the logic of set theory, and it's the structure that it allows sets of sets of sets... to build up that makes them the appropriate objects to base mathematics on. Consider - if we accepted the first logic then when we put sets in sets we end up with just an amorphous blob comprising of everything in all those sets, while with the second we get a more tower-like construction. You can build with the second logic, with the first everything squishes down to ground level.

Just in case that second logic still doesn't fit with your intuitions, here's an example to show that sometimes we do think like that outside of maths. "The" is a word in English, so if we consider English as a set of words (don't try this at home, kids! Grammar's kinda important too), then "the" is in English. Now, English is a language, or what's the same thing, English is in the set of languages. But no one would say that this means that "the" is in the set of languages, or what's the same thing, that "the" is a language. Why, but that would be nonsense talk! So here we build rather than squish.

Now note something I slipped in in that last paragraph. I talked about the set of all languages, and said something being in it is the same as it being a language. Now this is a general and important idea - if we have some property which we can say for any particular thing it either has or hasn't - like being a language, or being green, or eating the lotus, or being a square root of -1 - then we can form the set of all things which have that property and it will contain everything that has that property and nothing else. So respectively we'd have the set of languages, of green things, of lotus-eaters, and of the square roots of -1 (i and -i). Makes sense, right?

Well, that's the basic concepts of naive set theory sorted. There is, of course, a whole lot more to it, alot of which is very interesting indeed. As I said before, the whole of mathematics is formulated these days in the language of sets, and on a day-to-day basis your average working mathematician tends to think of that language as being naive set theory (even if pressed they'll tell you they really mean ZFC, or whatever). There is also much more pure set theory you should read about if you think you might be interested - see for example set theory notation for the proper notation and further basic concepts, cardinality for how sets let us understand infinity, topology for a classic example of how set theory lets us make concrete, in an abstract kinda way, the most general notions, also the Axiom of Choice, Cantor Ternery Set, and any other soft link down there that looks interesting.

But for the remainder of this writeup I'll be more interested in the fact that what I've just presented, simple and in accordance with (one possible) intuition though it is, is actually wrong. That is, we can show that by accepting the simple things we've accepted above - that anything can be in any set, the way sets can be considered as things, and that a property can define a set - forces us to accept a logical contradiction. If sets could work this way then there would be something which is both true and not true, which is patently ridiculous. And what's more, although this is creeping away from intuition and into formal logic, it's true in a sense that if something's both true and not true then everything is true. So if naive set theory were true then Santa Claus would be Elvis' grand-daughter, David Icke would be the father of God, and so on. Here's how it works. We've said that anything can be in a set. And we've said that sets are things. So there's nothing to stop a set being in itself. Now that sounds weird and like it might lead to problems, and it does. For any given set, we can tell whether or not it is in itself. So we can consider the property of "a thing not being in itself" - let's call it not being "weird". So as above, we can consider the associated set of all things which aren't weird - that is, the set of all sets which aren't in themselves. Let's call the set W. OK? But now let's ask, all innocent and wide-eyed, a simple question. Is W weird? Is W in itself?

Can you feel the ground starting to shake? OK, let's suppose W isn't in itself. Then W isn't weird. But doesn't that mean that W is in W? Well, yes, it does. So W is in W. But then W is the set of things not in themselves, so W isn't in W. But then W is in W. But then - Oh my God! W is in W, and W isn't in W, and we've got a big nasty paradox, and Kurt Cobain is the bastard offspring of Hitler and Thatcher, but Kurt Cobain isn't the bastard offspring of Hitler and Thatcher, so the edifice crumbles and everything is wrong.

Well, hopefully you didn't see that coming from the start, which is why this is called "naive" set theory. Neither did mathematicians a century or so ago, and it took one Bertrand Russell to come up with the paradox I've just given (though he didn't mention weirdness or Thatcher) to set them right. Since then much work has gone into getting set theory both consistent and useable - the basic approach being to put conditions on when a set can be in another set.

So the moral of the story is that you shouldn't always trust your intuition, especially where mathematics and logic are concerned. We need to be very careful not to end up with a contradiction. This is what the axiomatic method is all about, and it's what gives mathematics its special claim to a certain kind of pure and certain truth. (though there are still unresolved, indeed unresolvable problems - but that's the subject of another node)