Tuesday, August 10, 2010

About Set theory

A set is an unordered well defined collection of distinct objects represented as a unit. The objects in a set are called its elements or members. By ‘well defined’ we mean that it must be possible to tell beyond doubt whether or not a given object belongs to the collection that we are considering. If we are asked to write the set of all intelligent students of a class, it is not possible to do so. No two persons will have the common list. Thus the collection of intelligent students in the class is not a set. It is not necessary that a set contains only the same type of objects. If we have a book, a football, a glass and a table, then these objects also form a set although they are different form each other.

George Cantor (1845-1918), John Venn (1834-1923), George Boole (1815-1864), Augustus De Morgan (1806-1871) influenced the development of set theory and logic.

George Cantor, in 1895, was the first to define a set formally. He is considered as the “Father of Set theory”. Cantor took the idea of set to a revolutionary level, unveiling its true power. By inventing a notion of size of set he was able compare different forms of infinity and, almost incidentally, to shortcut several traditional mathematical arguments. But the power of sets came at a price; it came with dangerous paradoxes. The paradoxes of set theory were a real threat to the security of the foundations. But with a lot of worry and care the paradoxes were sidestepped, first by Russell and Whitehead’s theory of stratified types and then more elegantly, in for example the influential work of Zermelo and Fraenkel. The notion of set is now a cornerstone of Mathematics.

Consider all of the men in a small town as members of a set. Now imagine that a barber puts up a sign in his shop that reads I shave all those men, and only those men, who do not shave themselves.

Obviously, we can further divide the set of men in this town into two further sets, those who shave themselves, and those who are shaved by the barber. To which set does the barber himself belong?

The barber cannot shave himself, because he has said he shaves only those men who do not shave themselves. Further, he can not shave himself because he shaves all men who do not shave themselves.

Russell’s Paradox arises within set theory by considering the set of all sets which are not members of themselves. Such a set appears to be a member of it if and only if it is not a member of itself.

The significance of Russell’s paradox can be seen once it is realized that, using classical logic, all sentences follow from a contradiction. In the eyes of many, it therefore appeared that no mathematical proof could be trusted once it was discovered that the logic and set theory apparently underlying all of mathematics was contradictory.

Set theory helps people to …

• see things in terms of systems

• organize things into groups

• begin to understand logic

In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set.

In computer science, we are often concerned with sets of strings of symbols from some alphabet, for example the set of strings accepted by a particular automaton.

Types of Sets

Finite Sets

A set is called a finite set if we can count the number of elements of the set. In other words, a set of finite number of elements is called a finite set. Set of students in a school, set of people living in Indore, set of natural numbers from 20 to 50 are some of the examples of finite sets.

Infinite Sets

A set in which the number of elements cannot be count is called an infinite set. In other words, a set of infinite number of elements is called an infinite set. Set of all integers, set of points on a line and set of circles with a fixed centre are some of the examples of infinite sets.

Singleton set

A set which has only one member is known as a single member set or Singleton set.

For example, a set of natural numbers between 7 and 9 is a single member set having only one element 8 i.e.{8}.

Empty set or Null set

A set which contains no element is called an empty set or null set. It is also called it void set. In listing elements of an empty set we have braces { } and having nothing within the braces.

Null set is usually denoted by the Greek letter (phi). Clearly the set {0} is not an empty set as it is a set which has one element zero belonging to it. The set of triangles with two obtuse angles is { } and the set of natural numbers between 5 and 6 is also .

Empty set is a subset of every set.

Disjoint Sets

If no element of A is in B and no element of B is in A then A and B are called disjoint sets or we can say that if A∩B=ф then A and B are disjoint sets. For example, sets {1, 2, 5} and {2, 4, 6} are disjoint sets as there is no common element in them. In other words two sets which have no common members are called disjoint sets.

One-to One Correspondence Sets

Two sets are said to be in one- to- one correspondence if they can be matched in such a way that each element of one set is associated with a single element of the other.

Let A= {a, b, c} and B= {p, q, r, s} then it is clear that A and B are not in one-to-one correspondence. If the elements of A and B are matched then one element of B remains unmatched. Thus we say that A has fewer elements than B or B has more elements than A. In other words, the set B is larger than the set A.

Equivalent Sets

Two sets X and Y are said to be equivalent sets if the number of elements in X is equal to the number of elements in Y i.e., there is one-to-one correspondence between the elements of X and Y.

For example,{1. 2. 3} and {x, y, z} are equivalent sets. The symbol “~” is used to denote equivalence.

Thus A ~ B is read as ‘A is equivalent to B’.

Equal Sets

Two sets A and B are called equal sets if every element of A is also an element of B and every element of B is also an element of A. For example {r, s, t} and {t, r, s} are equal sets.

Obviously if two sets are equal, they are equivalent too but if two sets are equivalent they may not be equal.

For example, Given A= {2, 4, 6, 8} and B = {2, 8, 4, 6}. Here every element of A is a member of B and each element of B is also a member of A. Thus Set A= Set B.

Further, if X is a set of letters in the word ‘search’ and Y is a set of letters in the word ‘reaches’, then X= {s, e, a, r, c, h} and Y= {r, e, a, c, h, e, s}

X = Y

The order of elements and repetition of elements does not change a set.

No comments:

Exam Stress

Uploaded on authorSTREAM by Pragati