Sets

A set, as mathematicians have it, is simply a collection of some sort of items -- you can talk about the set of all h2g2 articles; that is simply all articles on www.h2g2.com referenced all in one chunk. Or the set the numbers 2, 3 and 4 -- in set notation {2,3,4}.

Something included in a set is called a member or element of that set. Examples are the current article (for the first set mentioned in the last paragraph), or the number 2 (for the second set mentioned). You can even include sets in sets -- such as the set consisting of 1, 2, and the set of 2 and 3: {1,2,{2,3}}.

Each element in a set is only counted once. Thus {1,1,1,2,3} is equal to {1,2,3}. The number of unique elements in a set is called the cardinality of that set. More information about cardinalities is availible.

A set may have no members at all. This is a rather special set, called the null set or the empty set, and it is normally denoted by Ø. Sets may also have infinite numbers of elements -- there are even different kinds of infinities used when discussing this. One easy way to describe an infinite set where the elements have some sort of relation to each other, is to do it with a characterizing property: {x|x is an article in h2g2} or {x|x is either 1, 2 or 3}.

Further examples of sets that are described this way are: {x|x is the square of a whole number} which is the set {1,4,9,16,25,36,49,...} and {x|x is a whole number} (we call this set Z). Since we will be referring to examples throughout this whole project, I will give a table over important and common sets:

A set is well defined, if we can be absolutely certain whether each object is either in the set or not in the set. We don't need to know whether it is or not, we only need to know that it only can be either in the set or not. Thus the 'set' The set of some positive number is not well defined, since we cannot know which positive number is in the set.

Subsets

A subset of a set is a set such that all the members of the subset are also members of the superset. Thus {1,2,3} is a subset of Z, and of N, and of Q, and of R, and of C etc. Note that both the superset itself and Ø are subsets of the superset.

A proper subset is a subset that is neither the superset or Ø.

If we define a set S={1,2,3}, then this set has a total of 8 subsets, and 6 proper subsets:

Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}

where the proper subsets are:

{1}, {2}, {3}, {1,2}, {1,3} and {2,3}

Relations

Strictly mathematically (and for some, boringly) speaking, a relation is often defined as a set of ordered pairs of two sets. Thus, the relation 'Can be written using' would among others have the members (h2g2 article, Plain Text), (h2g2 article, GuideML) and (h2g2 article, HTML)...

This doesn't say too much to the layman though, now does it? What does it mean then, really?

A relation is a way of establishing whether a statement about two entities is true or not. The pairs 'included' in the relation show the combinations of entities that are true in that sense, and the order of each pair shows what direction this property goes. For an example, the relation 'Is a son of' is clearly quite one-way. The case is apparently impossible that A is a son of B and B is a son of A.

Equivalence relations

One of the more important classes of relations that mathematicians study are the equivalence relations. An equivalence relation is a relation with three definite characteristics (we denote three elements of the set in which the relation is defined with a,b,c and the relation with ~:

1. a~a, that is every element is equivalent with itself.
2. If a~b then b~a, that is if a is equivalent with b, then b is equivalent with a.
3. If a~b and b~c then a~c, that is if a is equivalent with b is equivalent with c, then a is equivalent with c.

Partitions

If we have an equivalence relation ~ defined on a set S, then use this to divide the set into subsets that both fill S (i.e. there is no element of S that is not an element of at least one subset) and that are disjunct (i.e. no element belongs to more than one subset). We call a set of subsets that fulfills these two rules a partition. The subsets included in a partition are called cells.

If we look at the subset P={x|x~a} for some element a, we can see that any other element either belongs to P (i.e. it is equivalent to a under ~), or it doesn't (i.e. it's not equivalent to a). If we set ã=P and take another element b that is not an element of ã, we can proceed and build up a subset P' based on all elements equivalent to b. As long as there are any elements not yet included, we can always choose one of these and build another subset on this element, and since the element chosen never is equivalent to any element already in another set, no element will belong to more than one subset -- i.e. all subsets will be disjunct. And since we will be able to keep on doing this until no elements are left to put in subsets, these subsets will fill S.

If we conversely have a partition P, then we can define the equivalence relation ~={(x,y)|x and y belong to the same cell}.

Thus, every equivalence relation gives a partition of the set it works on, and every partition of a set defines an equivalence relation.

Operations

You almost certainly already know of some operations -- in both Z, Q and R (which are some of the set you normally work with in school), you have several binary operations -- that is operations that take two elements to a third -- defined: '+', '-', '*', '/'

You also most certainly know of a couple of unary operations -- at least '-' -- the operation that takes a number to the negation of itself.

But what do mathematicians, and above all set theoreticians make of it?

A binary operation may be defined by that it assigns to each ordered pair (a,b) of a set S an element of the set S. In other words, addition (as an example of a binary operation) assigns to each and every pair of real numbers (the set R) a real number as the result of the addition. (1,2) has (in R, and with normal addition) 3 assigned to it.

We require further of a binary operation, that the two operands are from the basic set and that the result is in the same basic set. Thus, addition is not a binary operation on the set R^*, since 2+(-2) (both in R^*), which is equal to 0, is not in R^*.

Commutativity

Order. Order matters. You normally don't first take your shirt on and then your pajama off, do you?

The same applies to mathematics. The ability to do something regardless of what order you do it in is called commutativity. If a binary operation '*' is commutative, it means that if a*b=c then b*a=c. Addition is normally commutative. Subtraction is not. Multiplication is, division is not. Taking your shoes on is³ but the act of dressing as a whole is not.

Associativity

Before you define everything 'good enough', mathematicians tend to be very picky. Among other things, they tend to be picky about where all parenthesises are placed. Does a*b*c mean (a*b)*c or does it mean a*(b*c).

If we (in order to produce an example of a operation with tricky parenthesises) define a*b to mean the lesser of a and b -- i.e. 2*7=2, 7*6=6, 12*13=12 etc., and then define axb to mean (a*b)+2. Then 'x' is an operation, since it maps every pair of real numbers unto another real number. It is also commutative, since a*b=b*a. But (2x5)x9=4x9=6 and 2x(5x9)=2x7=4. Thus in this case, parenthesises matter quite a bit.

If doesn't matters in this way where the parenthesises are put -- or in more formal language: if for a binary operation *

a*(b*c)=(a*b)*c

then this operation is called associative. If the operation is associative, the parenthesises are no longer necessarily needed -- an expression like a*b*c*d*e is not ambiguous.

Table building

One way of displaying a binary operation -- if the set it operates upon is small enough -- is to put all combinations in a table. If we have the set of {0,1} and define our operation to be multiplication as we normally know it, then we will recieve a table as follows:

In order to read out the result of a specific multiplication from this table, you look up the first operand to the left, and the second operand on top, and find the element in the same row as the first operand and in the same column as the second operand. This is the result of your operation.

One of the neat things about such a table is that you can quickly determine whether the operation is commutative or not, since if the operation is commutative, then the upper right and lower left halves have to be each others mirror images.