Friday, August 20, 2004

on sets and numbers

In the spirit of my ongoing campaign to alienate most of my readers, I've decided to add another post on mathematics (or more properly, on the foundations of mathematics which is a more interesting topic).

Probably the first symbols of numbers were collections of stones or shells or other small tokens. A herder could count his sheep (or his children) by keeping a small bag of stones and marking them off, each one to a single animal. If he had a special stone for each sheep, then this wasn't mathematics, it was naming. But if any stone could match any sheep, then the bag of stones represented a number and the herder was doing primitive mathematics.

So what is a number? Numbers don't seem to act like properties. You can ask what is the color of something, or what is its temperature and the answer is pretty much determined by the object. You can't ask what is the number of something. What is the number of a basketball team? Is it one team or twelve players? It depends on how you describe the team.

What is a set? People sometimes visualize sets as collections or groups of things, but this is only an analogy to what sets really are. A set is really the extension of a property. So once I explain what a property and an extension is, then you'll know what a set is.

A property is pretty much what you think it is. It's a description. For example "__ is red" is a property. Some things are red and some things are not. Here is an interesting pair of properties:

P1: __ is a prime number between 2 and 10
P2: __ is an odd number less than 8

What's interesting is that every number that satisfies P1 also satisfies p2 and the reverse. So are P1 and P2 the same property? Clearly not. P1 is about prime numbers and P2 is about odd numbers. They are entirely different concepts. But when two properties have this feature, we say that they are coextensive or that they have the same extension. The extension of a property is all and only those objects that satisfy the property. A set is the extension of a property viewed as an object in its own right. A collection or class. (The intension of a property is the underlying concept).

For many purposes, you only care about the extension of a property and not the intension. For example these two properties are coextensive:

P3: __ is an odd number
P4: __ is a number having a 1, 3, 5, 7, or 9 as the last decimal digit

We know that these two sets are coextensive, so we switch between them at will. There are 951 people who are going to vote yes or no. Can we be sure there will be no tie? We want to know if 951 is an odd number so we apply P4 to find out, rather than P3, which is the question we really want to answer. Since they are coextensive it doesn't matter. They describe the same set.

As sets are derived from properties, so operations and relations on sets are derived from operations and relations on properties. You can operate on properties using "and", "or", and "and not" (called logical connectives). P3 can be combined with

P5: __ is less than 8

to produce

P6: __ is an odd number and is less than 8

which is coextensive with P2. This corresponds to set intersection. If S3 is the extension of P3 and S5 is the extension of P5, then S6=S3*S5 is the extension of P6 (using * to represent set intersection). Similarly

P7: __ is an odd number or is less than 8

to produce the set union S7=S3+S5, which is the extension of P7. Finally,

P8: __ is an odd number and is not less than 8

has the set difference S8=S3-S5 as its extension.

Reducing a property to its extension is a process of abstraction. You throw away some details so that you can reason more generally. In this case, you throw away all details except the identities of the objects that satisfy the property. The underlying concept is entirely discarded.

You can think of this process of abstraction as being defined by the relation of coextension. If property p is coextensive with q and q is coextensive with r, then p is coextensive with r. We say that p, q, and r are all equivalent with respect to coextension or that they are all in the same equivalence class. Each set corresponds to an equivalence class of properties.

Of course coextension isn't the only relation we can use to abstract properties. Another one we can use is cocardinality (I made that word up to go with coextension, the usual term is "equinumerous"). Cocardinality throws out even more detail than coextension does; we don't even keep track of the identities of the elements. Two properties p and q are set to be cocardinal if there is any one-to-one mapping from the values that satisfy p to the values that satisfy q. Within the mapping, each value that satisfies p has exactly one corresponding value that satisfies q and each value that satisfies q has exactly one corresponding element that satisfies p. For example given

P9: __ is an odd number less than 6
P10: __ is an even number less than 7

the set of objects that satisfy P9 is S9={1,3,5} and the set that satisfies P10 is S10={2,4,6}. We can map S9 to S10 like this: 1<->2, 3<->4, 5<->6. Since we can create this mapping, P9 and P10 are cocardinal. Compare this to coextension, where we don't throw away the identities of the elements. Two properties are coextension only if there is a one-to-one mapping that specifically maps objects on one side to equal objects on the other. Cocardinality allows you to map objects on one side to any object on the other side.

Like coextension, cocardinality can be used to produce an abstraction. As the abstraction based on coextension produces sets, the abstraction based on cocardinality produces cardinal numbers. Every property is abstracted to the cardinal number that goes with its equivalence class.

The operations and relations on properties extend to cardinal numbers much as they do to sets. In order to avoid confusion, I'm going to switch from numbers to letters for my examples:

P11: __ is a vowel
P12: __ is a liquid consonant
P13: __ is a letter less than b.

The extension of P11 is {a,e,i,o,u} with cardinality N11=5, the extension of P12 is {l,r} with cardinality N12=2, and the extension of P13 is {a} with cardinality N13=1. Consider

P14: __ is a vowel or a liquid consonant
P15: __ is a vowel or a letter less than b

The extension of P14 is {a,e,i,o,u,l,r} with cardinality N14=7=N11+N12. So "or" corresponds to addition. But notice that the cardinality of P15 is not N11+N13. This is because addition only applies to disjoint properties. Properties that have no elements in common.

P16: __ is a vowel and not a letter less than b
P17: __ is a vowel and not a liquid

Here, "and not" corresponds to subtraction (N16=N11-N13) but only in a restricted case: where the second property is contained in the first.

Multiplication is a bit more complex and I'll handle it in a later post.

No comments: