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)