Theory of Ordinary Sets
Don't set under the apple tree, with anyone else but me.
------------------------------------------------------------------------------------
------------------------------------------------
A set is a class of things taken together and sharing a common property. This may not seem like much, but it's high-class stuff and eventually gets into things like infinity and transfinite numbers. You can count on it!
Cantor's Definition
According to Cantor, a set is any collection of distinguishable objects of any kind considered as a whole. In other words, consider a set as a something by itself. To be in the swing of things, call the set S. Then the objects themselves are members of S.
Membership is indicated by the symbol, Î, read as "a member of." For example, if a is a member of S, you say a Î S. But if a isn't a member of S, you say a Ï S, just like in No Parking signs.
Using 'membership,' you can say when different sets are equal. They would be the same if they had the same members. In the jargon of math, two sets are equal if and only if they have the same members.
The 'if and only if' part of the sentence specifies the sufficient and necessary conditions for sets being the same. The if condition is enough ammo to say the sets are the same, and the only if condition tells you what has to be the case for the sets to be the same.
If sets X and Y are equal, you write:
X = Y.
If not:
X ¹ Y.
Pretty simple stuff so far, right? It's just a matter of keeping the terms in mind.
Contents of Sets
Almost anything you can think of can go into a set, and that even includes other sets. So, for example, you could have the set of apples, or the set of oranges. But you could also have the set consisting of the two sets, themselves -- the two members in that case would be the set of apples and the set of oranges.
Written in neat math form, the set of apples, the set of oranges, the set of sets of apples and oranges, and the empty set would be, respectively:
Sapples = {apple1, apple2, ...}
Soranges = {orange1, orange2, ... }
Ssets = {Sapples, Soranges}
Sempty =
Æ = { }You can even include the empty set, Æ, in your set of sets. (Compare Æ, in sets, with 0, in numbers.) So you could have:
Ssets+ = {Sapples, Soranges, Sempty}
The Universal Set
Cantor also defined a universal set. This is the opposite of the empty set, in a sense -- i.e., it includes everything, instead of nothing. It generally takes the symbol U and has to do with a universe of discourse and its subsets. For instance, the universe could be the officers in your company, and the subsets could be all the possible groupings of the officers. That is, U consists of all the subsets of the sets under consideration, whatever the sets might be.
---------------------------------------------
It's okay to put sets together using apples and oranges, tables and chairs, different animals, and all that, but it can be awkward to list all the members, especially if you have many of them.
Using a Roster
You could still list them, in what is called a roster format, like listing the members of a club. In a set you can specify the members explicitly, by saying who or what they are. For example, the set, A, might consist of the numbers: 1, 3, 7, 8. We write the set symbolically as:
A = {1, 3, 7, 8}
Using a Formula
It would help to have a general way to define membership and use the definition to identify the members. Take an infinite set, A, for instance. How might you say what they are? You certainly can't list them! My guess is you'd be hard-pressed to do so, at least at first.
But the trick is really simple: you define the set as the elements, x, that meet some condition, f(x). This was Cantor's idea, in a nutshell. He defined the sets by using formulas. More precisely, he used formulas to define the membership in sets.
A formula gives you a rule for building the membership. In terms of a variable, x, for members, the principle is to define a formula in x, as the mathematician says. The formula is a rule that lets you select the members. That formula is a function of x, or f(x), which you can read as the function, f, of x, or simply f of x. The formula says:
If
x meets "a certain condition," then it is a member of the set.An example of a formula is:
x is 5 feet tall.
Using this formula, you would build the set, S, say, by including everybody five feet tall. So, the rule is simply:
If x is five feet tall, then x is a member of S.
Using a formula, we can now deal with infinite sets. You would identify the set, A, using the notation:
A = {x | f(x)}.
The vertical line is just short-hand for 'such that.' So the form can be read:
A is the set of elements, x, such that x satisfies the function, f(x).
----------------------------------------------
Sets are defined in terms of their members. But some of their more interesting properties have less to do with members than with collections of the members, or subsets of the sets. The subsets and the operations performed on them make up most of the ideas of set theory.
As an example of a subset, take the red apples in the set of apples, say. Another subset would be all the sweet apples. And yet another set would isolate all apples that are "bigger than a major league baseball," as if you really cared!
The interesting thing about subsets of sets is that they can also be subsets of other subsets, which is to say all the members of one of the subsets can also be members of the other one. This is called set inclusion. And the symbol that represents set inclusion is the right-facing horseshoe, Ì. So, if the set, A, is in set, B, or if all the members of A are in B, we write:
A Ì B
There can be subsets that are so different they have no members in common at all, or have only some members in common but are otherwise completely different. These relationships can be defined using just a few simple operators.
Two sets of special interest are the Null (or empty) set, Æ, and the Universal (or all-inclusive) set, U. The Null set has the strange property that it is contained in all sets -- nothing is in everything! And the universal set has the property that it contains all sets -- all the sets are in it. The universality refers to all of the sets that you are concerned with at the moment, or what is within your universe of discourse.
----------------------------------------------
Operations for Sets
Operations for sets are just ways to combine sets, or ways to generate new sets out of old ones. Operations on sets correspond to the operations you find in arithmetic, which you know as addition, subtraction, multiplication, and division. Operations in logic do similar kinds of things, but they work on statements.
Just as logical operations have to do with combining statements, set operations deal with sets, whereas arithmetic operations are performed on numbers.
In set theory, then, you find the operators, È (read as union, join, or sum), Ç (read as intersection, meet, or product), and Comp (read as complement).
The union of sets A and B is the set of all members either in A or in B and is written as:
A È B
So, if x is a member of A, then x is a member of A È B, and if y is a member of B, then y is a member of A È B.
Similarly, the intersection of A and B is the set of all members of A that are members of B:
A Ç B
So, if x is a member of A and if x is a member of B, then x is a member of A Ç B.
You can also define the difference between sets A and B:
A - B
as the elements in B not in A So if A = {Ann. Arnie, Amos) and B = {Ann, Arnie, Ben), then A-B = {Ben}. Similarly, B-A = {Amos}.
There is also the operation performed only on one set -- not two, as in union and intersection. The operation is complementation, Comp(A). Given a set, A, you take its complement relative to the universe of discourse, U. So, if A consists of the set {x}, with x drawn from U, then the complement of A is:
Comp(A) = {x | x Ï A}
which consists of all the members of U that are not in A.
--------------------------------------------
Characteristic Function of a Set
There's a connecting link between the algebra of sets and logic. This link is established by a characteristic function, using the fact that logicians assign truth-values to predicate statements.
For instance, in the predicate calculus the sentence 'The table is red' would be considered to be 'true' when the object denoted by 'table' satisfies the condition that it is red, i.e., that it's in the set of red tables.
Whether or not something is in a particular set becomes the test for truth. The test is made through a special kind of set specification called the characteristic function of the set. This is really a third way to specify a set.
The procedure is to first define a universe of discourse, U. This is similar to defining sets by formula. Now, though, for any given set, A, the characteristic function defines whether or not any specific element in the universe is in A.
A function, CA(x), is a characteristic function if it takes the value, 1, when x is in A, and the value, 0, when x is not in A. The function is defined for all the elements of the universe, and it maps all of U to the set of two elements {0, 1}. It is written formally as:
CA(x) = 1 if x is in the set A.
CA(x) = 0 if x is not in A.
The connection with two-valued logic is now direct -- you need only associate the truth value, false, to 0, and the truth value, true, to 1. I.e., you identify set {0, 1} with set {false, true}.
For other forms of logic this characteristic function doesn't apply. In one four-valued logic, for instance, a function has to be defined to map the whole of the universe, U, to the set of four elements 0, 1, imaginary, and uncertain. In other multi-valued logics, other functions have to be devised. Yet again, for fuzzy logic, the function has to take the fuzziness of sets into account.
-------------------------------------
.