Set Theory


Naive set theory considers elementary properties of the union and intersection operators -- Venn diagrams, the DeMorgan laws, elementary counting techniques such as the inclusion-exclusion principle, partially ordered sets, and so on. This is perhaps as much of set theory as the typical mathematician uses. Indeed, one may "construct" the natural numbers, real numbers, and so on in this framework.

1. Ordered Pairs

We begin by introducing the notion of the ordered pair. If a and b are sets, then the unordered pair {a, b} is a set whose elements are exactly a and b. The “order” in which a and b are put together plays no role; {a, b} = {b, a}. For many applications, we need to pair a and b in a way making possible to “read off” which set comes “first” and which comes “second.” We denote this ordered pair of a and b by (a, b); a is the first coordinate of the pair (a, b), b is the second coordinate.

As any object of our study, the ordered pair has to be a set. It should be defined in such a way that two ordered pairs are equal if and only if their first coordinates are equal and their second coordinates are equal. This guarantees in particular that (a, b) ≠ (b,a) if a ≠ b.

Definition. (a, b) = {{a}, {a, b}}.

2. Relations

A binary relation is determined by specifying all ordered pairs of objects in that relation; it does not matter by what property the set of these ordered pairs is described. We are led to the following definition.

Definition. A set R is a binary relation if all elements of R are ordered pairs, i.e., if for any z ∈ R there exist x and y such that z = (x, y).

It is customary to write xRy instead of (x, y) ∈ R. We say that x is in relation R with y if xRy holds.

The set of all x which are in relation R with some y is called the domain of R and denoted by “dom R.” So dom R = {x | there exists y such that xRy}. dom R is the set of all first coordinates of ordered pairs in R.

The set of all y such that, for some x, x is in relation R with y is called the range of R, denoted by “ran R.” So ran R = {y | there exists x such that xRy}.

3. Functions

Function, as understood in mathematics, is a procedure, a rule, assigning to any object a from the domain of the function a unique object b, the value of the function at a. A function, therefore, represents a special type of relation, a relation where every object a from the domain is related to precisely one object in the range, namely, to the value of the function at a.

4. Natural Numbers

In order to develop mathematics within the framework of the axiomatic set theory, it is necessary to define natural numbers. We all know natural numbers intuitively: 0, 1, 2, 3, ..., 17, …, 324, etc., and we can easily give examples of sets having zero, one, two, or three elements.

To define number 0, we choose a representative of all sets having no elements. But this is easy, since there is only one such set. We define 0 = Ø. Let us proceed to sets having one element (singletons): {Ø}, {{Ø}}, {{Ø, {Ø}}}; in general, {x}. How should we choose a representative? Since we already defined one particular object, namely 0, a natural choice is {0}. So we define

1 = {0} = {Ø}.

Next we consider sets with two elements: {Ø, {Ø}}, {{Ø}, {Ø, {Ø}}}, {{Ø}, {{Ø}}}, etc. By now, we have defined 0 and 1, and 0 ≠ 1. We single out a particular two-element set, the set whose elements are the previously defined numbers 0 and 1:

2 = {0,1} = {Ø, {Ø}}.

5. Cardinality of Sets

From the point of view of pure set theory, the most basic question about a set is: How many elements does it have? It is a fundamental observation that we can define the statement “sets A and B have the same number of elements” without knowing anything about numbers.

Definition. Sets A and B have the same cardinality if there is a one-to-one function f with domain A and range B. We denote this by |A| = |B|.

Definition. The cardinality of A is less than or equal to the cardinality of B (notation: |A| ≤ |B|) if there is a one-to-one mapping of A into B.

For example the cardinality of the set {3, 1, 2} is 3.

6. Finite Sets

Finite sets can be defined as those sets whose size is a natural number.

Definition. A set S is finite if it has the same cardinality as some natural number n ∈ N. We then define |S| = n and say that S has n elements. A set is infinite if it is not finite.

7. Countable Sets

Definition. A set S is countable if |S| = |N|. A set S is at most countable if |S| ≤ |N|.

Thus a set S is countable if there is a one-to-one mapping of N onto S, that is, if S is the range of an infinite one-to-one sequence.

8. Uncountable Sets :

All infinite sets whose cardinalities we have determined up to this point turned out to be countable. Naturally, a question arises whether perhaps all infinite sets are countable. If it were so, this book might end with the preceding section. It was a great discovery of Georg Cantor that uncountable sets, in fact, exist. This discovery provided an impetus for the development of set theory and became a source of its depth and richness.

9.Null Set:
In mathematical sets, the null set, also called the empty set, is the set that does not contain anything. It is symbolized
for { }. There is only one null set. This is because there is logically only one way that a set can contain nothing.

The null set makes it possible to explicitly define the results of operations on certain sets that would otherwise not be explicitly definable. The intersection of two disjoint sets (two sets that contain no elements in common) is the null set. For example:

{1, 3, 5, 7, 9...} Ç{2, 4, 6, 8, and 10...} = f

10.Equality of sets: Two sets are equal if and only if they have the same elements.
More formally, for any sets A and B, A = B if and only if all the elements of A present in B.

Thus for example {1, 2, 3} = {3, 2, 1}, that is the order of elements does not matter, and {1, 2, 3} = {3, 2, 1, 1}, that is duplications do not make any difference for sets.

11.Subset: A set A is a subset of a set B if and only if everything in A is also in B.
More formally, for any sets A and B, A is a subset of B, and denoted by A
ÍB, if and only if all the elements of A are present in B
If A
ÍB, and A ¹B, then A is said to be a proper subset of B and it is denoted by A ÌB .

For example {1, 2} Í{3, 2, 1}. Also {1, 2}Ì{3, 2, 1}.

12.Universal set: A set, which has all the elements in the universe of discourse, is called a universal set.

Three subset relationships involving empty set and universal set are listed below as theorems without proof.

Note that the set A in the next four theorems are arbitrary. So A can be an empty set or universal set.

Theorem 1: For an arbitrary set A: A ÍU.

Theorem 2: For an arbitrary set A: fÍA.

Theorem 3: For an arbitrary set A A ÍA.

13.Power set: The set of all subsets of a set A is called the power set of A and denoted by 2A or j(A) .

For example for A = {1, 2}, j (A) = {f, {1}, {2}, {1, 2} } .

Theorem 4: For an arbitrary set A, the number of subsets of A is 2|A|.

Sponsered Links

All Rights Reserved. Copyright 2006-10