Sets, relations and operations

0 Conversations

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:

SymbolSet
Z{...,-4,-3,-2,-1,0,1,2,3,4,...}
N{0,1,2,3,4,...}
Q{x|x is a fraction} = {x|x=a/b where a,b belong to Z}1
Q+All positive elements of Q
RAll real numbers
R*All non-zero real numbers
CAll complex numbers2
C*All non-zero complex numbers


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 is3 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:

*01
000
101


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.

1Well, almost anyway. It should really be the set of all partitions of the set given in the second definition under the equivalence operation of '='2Numbers involving the square root of -1 in one way or the other... We will get back to these later.3It doesn't matter if you take on your left or your right shoe first

Bookmark on your Personal Space


Conversations About This Entry

There are no Conversations for this Entry

Entry

A490132

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more