## SETS

In mathematics, Set is a well defined collection of distinct objects. The theory of Set as a mathematical discipline rose up with George Cantor, German mathematician, when he was working on some problems in Trigonometric series and series of real numbers, after he recognized the importance of some distinct collections and intervals.

Cantor defined the set as a ‘plurality conceived as a unity’ (many in one; in other words, mentally putting together a number of things and assigning them into one box).

Mathematically, a Set is ‘any collection’ of definite, distinguishable objects of our universe, conceived as a whole. The objects (or things) are called the elements or members of the set . Some sets which are often pronounced in real life are, words like ”bunch”, ”herd”, ”flock” etc. The set is a different entity from any of its members.

For example, a flock of birds (set) is not just only a single bird (member of the set). ‘Flock’ is just a mathematical concept with no material existence but ‘Bird’ or ‘birds’ are real.

## Representing sets

Sets are represented in two main ways:

1. **Standard Method**: In this method we use to write all elements of a set in a curly bracket ( { } ).

For example:

Flock of Birds := {Bird-1, Bird-2, …, Bird-100,…}

or, is a set.

Here I have used first capital letter of each term to notate the example mathematically. We read this set as, A set F is defined by a collection of objects etc..

2. **Characteristic Method or Formula Method**: In this method, we write a representative element and define that by a characteristic property. A characteristic property of a set is a property which is satisfied by each member of that set and by nothing else.

For example, above set of Flock of birds can also be written as:

which has the same meaning at a wider extent. We read it as: ”A set F is defined by element B such that B is a bird.”

## Examples of Useful Sets

Some standard sets in Mathematics are:

**Set of Natural Numbers:** It includes of the numbers, which we can count, viz. . The set of natural numbers is denoted by .

**Set of Integers:** Integers includes of negatives of natural numbers and natural numbers itself. It is denoted by . …all are integers. The rigorous definition of integers be discussed in fourth part of the series.

**Set of Rational Numbers:** Rational numbers are numbers which might be represented as , where p and q both are integers and relatively prime to each other and q not being zero. The set of rational numbers is represented by and may include elements like . The characteristic notation of the set of rational numbers is . The rigorous discussion about rational numbers will be provided in fourth part of the series.

**Empty Set:** It is possible to conceive a set with no elements at all. Such a set is variously known as an empty set or a void set or a vacuous set or a null set.

An example of emptyset is the set , since there exists no integer which square is 2 —the set is empty. The unique empty set is denoted by .

**Unit Set**: A set with only one element is called the unit set. {x} is a unit set or a singleton set.

**Universal Set:** A set which contains every possible element in the universe, is a universal set. It is denoted by .

## Subset of a Set

Let and be two sets. We say that is a **subset** of (or is superset of or is contained in (or contains ) if every element of is also an element of set . In this case we write, or respectively, having the same meaning. If every element of the set A is an element of the set B and B contains at-least one element which does not belong to A, then the set A is called a ‘proper subset’ of B (conversely, B is called the proper superset of A), otherwise A is an improper subset of B. The proper subset notion is denoted by while the latter is represented by . Subset word might be understood using ‘sub-collection’ or ‘sub-family’ as its synonyms. Two sets are equal to each other if and only if each is a subset of the other.

## Finite Set

A set is said to be finite, if it has finite number of elements. For example: A:= {a,b,c,d} is a finite set with four elements. The number of elements in a set is called the cardinality of the set.

## Infinite Set

A set is infinite, if contains infinitely many elements. The set of natural numbers, is an infinite set. The cardinality of an infinite set is infinite.

An empty set is a finite set with zero elements (i.e., zero cardinality).

## Power Set of a Set

Power set of a set A is defined as the family consisting of all subsets of A, but the subset itself. The power-set is denoted by .

## Operations on Sets

### Union of Two Sets

If A and B are two sets, then their union (or join) is the set, defined by another set such that it consists of elements from either A or B or both. If we write the sets A and B using Characteristic Method as,

.

and,

then the union set of A and B is defined by set J such that

.

For practical example, let we have two sets:

and be any two sets; then their union is .

Note that it behaves like writing all the elements of each set, just caring that you are not allowed to write one element twice.

### Intersection of Two Sets

Intersection or meet of two sets A and B is similarly defined by ‘and’ connective. The set {x: x is an element of A and x is an element of B} or briefly . It is denoted by or by or by .

For example, and by definition, if A and B be two sets defined as,

then their intersection set, defined by .

In simple words, the set formed with all common elements of two or more sets is called the intersection set of those sets.

If, again, A and B are two sets, we say that A is disjoint from B or B is disjoint from A or both A and B are mutually disjoint, if they have no common elements. Mathematically, two sets A and B are said to be disjoint iff .

If two sets are not disjoint, they are said to intersect each other.

For example, if is a set of keyboard letters, then is a partition of the set and each element of the set belongs to exactly one member (subset) of partition set. Note that there are many partition sets possible for a set. For example, is also a partition set of set .

The **complement set** or of a set is a collection of objects which do not belong to . Mathematically, .

The** relative complement of set** with respect to another set is ; i.e., intersection of set and the complement set of . This is usually shortened by , read X minus A. Thus, , that is, the set of members of which are not members of .

The complement set is considered as a relative complement set with respect to (w.r.t) the universal set, and is called the Absolute Complement Set.

### Symmetric Difference

The symmetric difference is another difference of sets and , symbolized , is defined by the union of mutual complements of sets and , i.e., .

## Cartesian Product

Let and be two sets. Then their cartesian product is defined to be the set of an ordered pair, , where and are the elements of set and set respectively. Mathematically; the product of two sets and : .

Note that .

If has elements, has elements then indeed has elements.

We see that if we product two sets, we get an ordered pair of two objects (now we’ll say them, variables). Similarly if we product more than two sets we get ordered pair of same number of variables. For example:

.

. etc.

The sets, which are being product are called the **factor sets of the ordered pair** obtained. When we form products, it is not necessary the factor sets to be distinct. The product of the same set taken times is called the -th power of and is denoted by . Thus, is . is . And so on.

## Useful Theorems on Sets

- If
- If
**Self-dual Property:**If and- Self Dual:
**Idempotent Law:**- Idempotent Law:
**Absorption Law:**- Absorption Law:
**de Morgen Law**:- de Morgen Law:
**Another Theorem**

The following statements about set A and set B are equivalent to one another

## Relation

A relation from set X to set Y is a subset of cartesian product . Similarly, a relation from set B to set A is a subset of .

Read these statements carefully:

‘Michelle is the wife of Barak Obama.’

‘John is the brother of Nick.’

‘Robert is the father of Marry.’

‘Ram is older than Laxman.’

‘Mac is the product of Apple Inc.’

After reading these statements, you will realize that first ‘Noun’ of each sentence is some how related to other. We say that each one noun is in a RELATIONSHIP to other. Mischell is related to Barak Obama, as wife. John is related to Nick, as brother. Robert is related to Marry, as father. Ram is related to Laxman in terms of age(seniority). Mac is related to Apple Inc. as a product.These relations are also used in Mathematics, but a little variations; like ‘alphabets’ or ‘numbers’ are used at place of some noun and mathematical relations are used between them. Some good examples of relations are:

is less than

is greater than

is equal to

is an element of

belongs to

divides

etc. etc.

Some examples of regular mathematical statements which we encounter daily are:

4<6 : 4 is less than 6.

5=5 : 5 is equal to 5.

6/3 : 3 divides 6.

For a general use, we can represent a statement as:

**”some x is related to y”**

Here **‘is related to’** phrase is nothing but a particular mathematical relation. For mathematical convenience, we write ”**x is related to y**” as . *x* and *y* are two objects in a certain order and they can also be used as ordered pairs (x,y).

and are the same and will be treated as the same term in further readings. If represents the relation motherhood, then means that Jane is mother of John.

All the relations we discussed above, were in between two objects (x,y), thus they are called Binary Relations. is a binary relation between a and b. Similarly, is a ternary (3-nary) relation on ordered pair (x,y,z). In general a relation working on an n-tuple is an n-ary relation working on n-tuple.

Binary relations are really important to understand for further understanding. In a binary relation, , the first object of the ordered pair is called the the **domain** of relation ρ and is defined by and the second object is called the **range** of the relation ρ and is defined by .

## Equivalence Relation

A relation is equivalence if it satisfies three properties, Symmetric, Reflexive and Transitive.

A relation is symmetric: Consider three sentences “Jen is the mother of John.”; “John is brother of Nick.” and “Jen, John and Nick live in a room altogether.”

In first sentence Jen has a relationship of motherhood to John. But can John have the same relation to Jen? Can John be mother of Jen? The answer is obviously NO! This type of relations are not symmetric. Now consider second statement. John has a brotherhood relationship with Nick. But can Nick have the same relation to John? Can Nick be brother of John? The answer is simply YES! Thus, both the sentences “John is the brother of Nick.” and “Nick is the brother of John.” are the same. We may say that both are symmetric sentences. And here the relation of ‘brotherhood’ is symmetric in nature. Again LIVING WITH is also symmetric (it’s your take to understand how?).

Now let we try to write above short discussion in general and mathematical forms. Let X and Y be two objects (numbers or people or any living or non-living thing) and have a relation ρ between them. Then we write that X is related by a relation ρ , to Y. Or** X ρ Y.**

And if ρ is a symmetric relation, we might say that Y is (also) related by a relation ρ to X. Or **Y ρ X.**

So, in one line; is true.

A relation is reflexive if X is related to itself by a relation. i.e., . Consider the statement “Jen, John and Nick live in a house altogether.” once again. Is the relation of living reflexive? How to check? Ask like, Jen lives with Jen, true? Yes! Jen lives there.

A relation is transitive, means that some objects X, Y, Z are such that if X is related to Y by the relation, Y is related to Z by the relation, then X is also related to Z by the same relation.

i.e., . For example, the relationship of brotherhood is transitive. (Why?) Now we are able to define the equivalence relation.

We say that a relation ρ is an equivalence relation if following properties are satisfied: (i)

(ii)

(iii) .

If a set X has elements and set Y has elements then the total number of relations from set A to B (or set B to A) is .

## Relation on a single set

A relation on a set A is a subset of . There are relations on set with elements out of which following are notable:

- Empty Relation: is an empty relation on set A.
- Improper Relation: is an improper or trivial relation on set A.
- Diagonal Relation: is a diagonal relation on A.

### Composition of two relations

Let R and S be two relations on set* A*. Then, and are all subsets of and hence they are also relations on A.

The relation, such that and , is called the composition of R and S on set A.

### Properties of composite relations

Let R,S and t be relations set A. Then,

### Inverse Relation

Let R be a relation on a set defined by ordered pair , then the inverse of the relation R, , is defined by ordered pair, . is called the inverse relation of R on the set.

### Remarks

Let R and S be the relations on *A*, then

## Partition of a set

A partition set of a set X is a disjoint collection of non-empty and distinct subsets of X such that each member of X is a member of exactly one member (subset) of the collection.

Let A be a set. A subset P of the power-set of A is called partition of A, if

- Union of members of P is A. i.e.,
- .

## Functions/Mappings

Function is a relation such that no two distinct members have the same first co-ordinate in its graph. is a function iff

- The members of are
**ordered pairs**, i.e., . - If ordered pairs and are members of , i.e., and , then

### Notation for functions

A function is usually defined as ordered-pairs, and so that is (was) a way to represent where is an argument of and is image (value) of . The set of arguments is called the domain of the function, while the set of images is termed as the range of the function.

Other popular notations for and are: , , , .

### Into Function

A function is into iff the range of is a subset of . i.e.,

### Onto Function

A function is onto iff the range of is . i.e.,

Generally a mapping is represented by .

### One-to-One function

A function is called one-to-one if it maps distinct elements onto distinct elements.

A function is one-to-one iff and

### Restriction of Function

If and if , then is a function on , called the restriction of to and is usually abbrevated by .

### Extension of function

The function is an extension of a function iff .

## Cardinally Equivalent Sets

A set is said to be cardinally equivalent or just ‘equivalent’ to another set if there exists one-one mapping (function) from* A* to *B*. This relation is denoted by the symbol ~. Therefore A~B means that set A and B are equivalent to each other.

## Denumerable, Countable and Uncountable Sets

A set *A* is called a denumerable (or countably infinite) set if there exists a one-one mapping from the set of natural numbers onto the set *A,*i.e., *A *is denumerable, if it’s equivalent to the set of natural numbers .

A set *A *is said to be countable set if either *A *is denumerable or *A* is finite.

A set is uncountable, if it’s infinite and not equivalent to .

## Examples:

- The set of all natural numbers is countable.
- The set of all rational numbers is countable.
- The set of all real numbers is uncountable.
- The set of all irrational numbers is uncountable.
- The set is uncountable.

## Important Theorems on Sets

- Every subset of a finite set is finite.
- Every superset of an infinite set is infinite.
- If
*A*and*B*are finite sets, then and are also finite sets. - Every subset of a countable set is countable.
- Every infinite subset of a denumerable set is denumerable.
- For countable sets,
*A & B*, is also countable. - Every superset of an uncountable set is uncountable.
- Every infinite set has a denumerable subset.
- Countably infinite sets are smallest infinite sets.
- The countable (finite) union of countable sets is countable.
- Every infinite set is equivalent to one of its proper subsets.

## Real Number System

Let represents the set of rational numbers. It is well known that is an ordered field and also the set is equipped with a relation called “less than” which is an order relation. Between two rational numbers there exists infinite number of elements of . Thus the system of rational numbers seems to be dense and so apparently complete. But it is quite easy to show that there exist some numbers (?) (e.g., etc.) which are not rational. For example, let we have to prove that is not a rational number or in other words, there exist no rational number whose square is 2. To do that if possible, purpose that is a rational number. Then according to the definition of rational numbers , where p & q are relatively prime integers. Hence, or . This implies that p is even. Let , then or . Thus is also even if 2 is rational. But since both are even, they are not relatively prime, which is a contradiction. Hence is not a rational number and the proof is complete. Similarly we can prove that why other irrational numbers are not rational. From this proof, it is clear that the set is not complete and dense and that there are some gaps between the rational numbers in form of irrational numbers. This section shows the necessity of forming a more comprehensive system of numbers other than the system of rational number. The elements of this extended set will be called a real number.

## Dedekind’s Theory

To discuss this theory we need the following definitions:

Rational number:A number which can be represented as where p is an integer and q is a non-zero integer i.e., and and p and q arerelatively prime as their greatest common divisor is 1, i.e., .

Ordered Field:Here, is, an algebraic structure on which the operations of addition, subtraction, multiplication & division by a non-zero number can be carried out.

Least or Smallest Element: Let and . Then is said to be a least element of if (i) and (ii) for every .

Greatest or Largest Element: Let and . Then is said to be a least element of if (i) and (ii) for every .

#### Dedekind’s Section (Cut) of the Set of All the Rational Numbers

Since the set of rational numbers is an ordered field, we may consider the rational numbers to be arranged in order on straight line from left to right. Now if we cut this line by some point , then the set of rational numbers is divided into two classes, lower class and upper class . The rational numbers on the left, i.e. the rational numbers less than the number corresponding to the point of cut are all in and the rational numbers on the right, i.e. The rational number greater than the point are all in . If the point is not a rational number then every rational number either belongs to or . But if is a rational number, then it may be considered as an element of .

### Real Number

Let satisfying the following conditions:

- is non-empty proper subset of .
- , < b" />< b" title="Set Theory, Functions and Real Number System" />< b" class="latex" title="a < b" /> and then this implies that .
- doesn’t have a greatest element.

Let . Then the ordered pair " title="Set Theory, Functions and Real Number System" />< L,U > " />< L,U > " title="Set Theory, Functions and Real Number System" />< L,U > " class="latex" title="< L,U > " /> is called a section or a cut of the set of rational numbers. This section of the set of rational numbers is called a real number.

Notation: The set of real numbers is denoted by .

Let then and are called Lower and Upper Class of respectively. These classes will be denoted by and respectively.

##### Remark

From the definition of a section of rational numbers, it is clear that and . Thus a real number is uniquely determined iff its lower class is known.

### Example Problem:

**Let 0, \ \text{and} \ x^2<2 \} " title="Set Theory, Functions and Real Number System" /> 0, \ \text{and} \ x^2<2 \} " /> 0, \ \text{and} \ x^2<2 \} " title="Set Theory, Functions and Real Number System" /> 0, \ \text{and} \ x^2<2 \} " class="latex" title="L = \{ x: x \in \mathbf{Q}, x \le 0 \ or \ x > 0, \ \text{and} \ x^2<2 \} " /> Then prove that is a lower class of a real number**.

**Proof:**

- Since and is non-empty proper subset of .
- Let b" title="Set Theory, Functions and Real Number System" /> b" /> b" title="Set Theory, Functions and Real Number System" /> b" class="latex" title="a,b \in \mathbf{Q} , a > b" /> and . If then . If b >" title="Set Theory, Functions and Real Number System" /> b >" /> b >" title="Set Theory, Functions and Real Number System" /> b >" class="latex" title="a > b >" /> so < 2 \Rightarrow a^2 < b^2 < 2 \Rightarrow a \in L" />< 2 \Rightarrow a^2 < b^2 < 2 \Rightarrow a \in L" title="Set Theory, Functions and Real Number System" />< 2 \Rightarrow a^2 < b^2 < 2 \Rightarrow a \in L" class="latex" title="b \in \Rightarrow b^2 < 2 \Rightarrow a^2 < b^2 < 2 \Rightarrow a \in L" />.
- Let . If then . If 0" title="Set Theory, Functions and Real Number System" /> 0" /> 0" title="Set Theory, Functions and Real Number System" /> 0" class="latex" title="a > 0" /> then < 2" />< 2" title="Set Theory, Functions and Real Number System" />< 2" class="latex" title="a^2 < 2" />.

Let for 0" title="Set Theory, Functions and Real Number System" /> 0" /> 0" title="Set Theory, Functions and Real Number System" /> 0" class="latex" title="b > 0" /> and , for any .

Also, 0" title="Set Theory, Functions and Real Number System" /> 0" /> 0" title="Set Theory, Functions and Real Number System" /> 0" class="latex" title="b-a=\dfrac{m+na}{o+pa} -a \\ =\dfrac{m+na-oa-pa^2}{o+pa} \\ =\dfrac {m+(n-o)a-pa^2}{o+pa} > 0" />

a" title="Set Theory, Functions and Real Number System" /> a" /> a" title="Set Theory, Functions and Real Number System" /> a" class="latex" title="\Rightarrow b > a" />.

And similarly, 0, \Rightarrow b^2 <2" title="Set Theory, Functions and Real Number System" /> 0, \Rightarrow b^2 <2"> 0, \Rightarrow b^2 <2" title="Set Theory, Functions and Real Number System" /> 0, \Rightarrow b^2 <2" class="latex" title="2-b^2 > 0, \Rightarrow b^2 <2">.

Thus, < a < b" />< a < b" title="Set Theory, Functions and Real Number System" />< a < b" class="latex" title="0 < a < b" /> and < 2 \Rightarrow b \in L." />< 2 \Rightarrow b \in L." title="Set Theory, Functions and Real Number System" />< 2 \Rightarrow b \in L." class="latex" title="b^2 < 2 \Rightarrow b \in L." /> Hence has no greatest element.

Since, satisfies all the conditions of a section of rational numbers, it is a lower class of a real number. [Proved]

Remark: In the given problem, is an upper class of a real number given by the set 0 \ \text{and} \ x^2 > 0 \}" title="Set Theory, Functions and Real Number System" /> 0 \ \text{and} \ x^2 > 0 \}" /> 0 \ \text{and} \ x^2 > 0 \}" title="Set Theory, Functions and Real Number System" /> 0 \ \text{and} \ x^2 > 0 \}" class="latex" title="U=\{x: x \in \mathbf{Q}, x > 0 \ \text{and} \ x^2 > 0 \}" />, since it has no smallest element.

Real Rational Number:The real number is said to be a real rational number if its upper class has a smallest element. If is the smallest element of , then we write .

Irrational Number:The real number is said to be an irrational number if does not have a smallest element.

#### Important Theorems & Results

If is a section of rational numbers, then

- is a non-empty proper subset of .
- < b \ and \ a \in U \Rightarrow b \in U" />< b \ and \ a \in U \Rightarrow b \in U" title="Set Theory, Functions and Real Number System" />< b \ and \ a \in U \Rightarrow b \in U" class="latex" title="a, b \in \mathbf{Q}, \ a < b \ and \ a \in U \Rightarrow b \in U" />.
- < b " />< b " title="Set Theory, Functions and Real Number System" />< b " class="latex" title="a \in L, b \in U \Rightarrow a < b " />.
- if is a positive rational number, then there exists such that
- if contains some positive rational numbers and 1" title="Set Theory, Functions and Real Number System" /> 1" /> 1" title="Set Theory, Functions and Real Number System" /> 1" class="latex" title="k > 1" /> then there exists and such that .

## Supremum and Infimum

First, we define** upper and lower bounds**.

A set of real numbers is **bounded from above** if there exists a real number , called an upper bound of *A*, such that for every . Similarly, *A* is **bounded from below** if there exists , called a lower bound of A, such that for every . The set to which and respectively belongs to are called the** upper and lower bounds of the set** *A. *The supremum of a set is its least upper bound and the infimum is its greatest upper bound.

## Supremum or Least Upper Bound

If the set of all upper bounds of set has a smallest number *k* then *k *is called the supremum of the set *A., *represented by* k= *Sup(*A*).

## Infimum or Greatest Lower Bound

If the set of all lower bounds of a set has a greatest number *K* then *K* is called the infimum of set *A, *represented by *K=*Inf(*A*).

Both supremum and infimum, if exist , are unique for a given set .

## Bounded Set

A set is said to be bounded if it’s bounded above as well as bounded below. When the set *A* is bounded, there exist two real numbers such that for all .