## Sunday, March 29, 2015

### A Set is Not a Collection

The usual introduction to sets says that a physical collection or a list of items is a good example of a set, maybe even the archetype of a set. But that is not really what mathematical sets are. A physical collection is a very atypical sort of set if it is a set at all, and a list is an even worse example.

These descriptions can make set theory seem arbitrary and capricious. What is the point of the intersection operation? If you have that bag of stuff over there and I have this bag of stuff over here, then it doesn’t make sense to talk about the bag of stuff that is in both bags. There isn’t anything that is in both bags. If you think of a set as a list of items, then union seems odd. If you have a list of things over there and I have a list of things over here, and we combine the lists, then some things might appear in the combined list twice. Why take out the duplicates? Why doesn’t it matter that something was originally in both lists?

If you understand what a set really is, then the answers to these questions are obvious. Before I say what a set really is, here is a little history of logic: Classical logic was based on a form of argument called a syllogism. The propositions of a syllogism are called categorical propositions because they express a relationship between two categories.

A category is a sort of general classification usually expressed as a plural noun or an adjective. For a given category, each individual either fits the category or does not. For example “Men” is a category that all men fit. “Blue” is a category that a thing fits if and only if it is blue.

A categorical proposition expresses a relationship between categories:

1. No men are blue.
2. Some men are wise.
3. Some wise are not blue.

As you can see, sentence 3 is a logical conclusion from sentences 1 and 2. This is called a syllogism. A syllogism consists of three categorical propositions where the third is a conclusion drawn from the first two. If A and B are categories, then there exactly are four categorical sentences comparing them:

1. All A are B
2. Some A are B
3. No A is B
4. Some A are not B

There are exactly 24 possible syllogisms, some of which are valid and some of which are not. The literature on this topic is voluminous from Aristotle until Boole. Around the time of Boole, mathematicians were starting to chafe under the limits of this system of logic.

One of the problems is that there is no place for logical connectives. You can have a compound category such as “blue and wise”, “blue or man”, etc, but the form of the syllogism didn’t really allow for exploring the relationships of these compounds. Perhaps an even more pressing problem was the issue of extensionality.

So what is extensionality? Well, if you know set theory you may read Sentence 4 as “A is a subset of B”, sentence 5 as “the intersection of A and B is non-empty”, etc. But that is not always the right interpretation because categories are not extensional.

A set is entirely defined by its members, but a category is not. There are two aspects to a category: the things that fit the category, and what the category says about those things. Consider the sentence:

1. The chairman of the board is the president of the company.

This sentence is equating two categories: “chairman of the board” and “president of the company”. If you think in terms of set theory then you would say that for this statement to be true, there has to be an individual who is both chairman of the board and president of the company. That is the extensional interpretation, but it is not only interpretation. Suppose the company charter has a rule that says that whoever is president of the company is automatically chairman of the board. If the current president/chairman leaves office, does the sentence become untrue until they appoint a new president? Of course not. In this intensional interpretation the sentence is about the categories themselves and not about what fits the categories.

When there is an individual who fits the category “the chairman of the board”, this individual is called the extension of the category. When there is no individual who fits the category we say that the extension of the category is empty. If there are multiple individuals who fit a category, then they are all in the extension of the category. And that is what a set is: a set is the extension of a category.

All of the features of set theory come from this interpretation. If you have two categories, C1 and C2, with corresponding extensions, S1 and S2, then

S1 union S2 is the extension of the category “C1 or C2”
S1 intersect S2 is the extension of the category “C1 and C2”
complement S1 is the extension of the category “not C1”

Mathematical propositions express categories, so if F(x) is a mathematical proposition about x then { x : F(x) } is an extension-taking mechanism. It says, “give me the extension of F(x)”.

It took around 2,000 years for mathematicians and logicians to decisively separate out the extension from the intension of a category to create set theory. This was a huge, titanic advance in mathematics and logic. Since then set theory has taken over and left intensionality mostly unstudied and even unremarked. Not to take away from the importance of extensional set theory, but I think this trend to ignore intensionality altogether is unfortunate because the intensional approach has a lot of interesting and useful characteristics.