UNIT–2

 SET THEORY

2.1 Basic concepts of set theory

Sets- A set is a collection of well-defined objects which are called the elements or members of the set.

We generally use capital letters to denote sets and lowercase letters for elements.

If any element which exists in the set is to be denoted as-

Suppose an element ‘a’ is from a set X, then it is represented as- aX

Which means the element ‘a’ belongs to the set X.

If the element is not form the group then we use ‘not belongs to’.

Representation of sets-

There are two ways to represent sets.

1. In first way, the elements of the set are separated by comma and contained in the bracket-{  }.

2. The second way is that we define the characteristic of the element.

For example-

Suppose we have a set ‘A’ of all odd integers which are greater than 3.

Then we can represent it two ways-

1. A = {5, 7, 9…….}

2. A = {x | x is an odd integer, x>3 }

Subsets-

Let every element of set X is also an element of a set Y, then X is said to be the subset of Y.

Symbolically it is written as-

Which is read as- X is the subset of Y.

Note- If X = Y then

Proper sub-set-

A set X is called proper subset the set Y is-

1. X is subset of Y

2. Y is not subset of X

Note- every set is a subset to itself.

Equal sets-

If X and Y are two sets such that every element of X is an element of Y and every element of Y is an element of X, the set and set Y will be equal always.

We write it as X = Y and read as X and Y are identical.

Super set-

If X is a subset of Y, then Y is called a super set of X.

Null set-

A set which does not contain any element is known as null set.

We denote a null set by ∅

The null set is a subset of every set.

Singleton-

A set which has only one element is called singleton.

Example- A = {10} and B = {∅}

Theorem- if ∅ and ∅’ are empty sets then ∅=∅’

Proof: Let ∅≠ ∅’  then the following conditions must be true-

1. There is element x∈∅ such that x∉∅’

2. There is element x∈∅’ such that x∉∅.

but both these conditions are false since ∅’ and ∅’ has any elements if follows that ∅=∅’.

2.2 Operations on sets

1. Union and intersection-

Union-We denote union of two sets as- A∪B, which is the set of all elements which belongs to A or to B.

That is-

                                       A∪B = {x |x∈∅A or x∈∅B}

Intersection- We denote intersection of two sets as- A∩B, which is the set of all elements which belongs to A and to B.

That is-

                                        A∩B = {x |x∈∅A and x∈∅B }

Note- Two sets are said to be disjoint if they have no common elements in common.

 Example: If A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8, 9} and C = {5, 6, 7, 8, 9, 10}

Then-

A∪B = {1, 2, 3, 4, 5, 6,7, 8, 9}

A∪C = {1, 2, 3, 4, 5, 6,7, 8, 9,10}

B∪C = {4, 5, 6,7, 8, 9, 10}

A∩B = {4, 5, 6}

A∩C = {5, 6}

B∩C = {5, 6, 7, 8, 9}

Property-1-

An element x belongs to the union A∪B if x belongs to A or x belongs to B; hence every element

In A belongs to A ∪B, and every element in B belongs to A ∪B. That is,

 A ⊆A ∪B and B ⊆A ∪B

Property-2-

An element x belongs to the union A∪B if x belongs to A or x belongs to B; hence every element

In A belongs to A ∪B, and every element in B belongs to A ∪B. That is,

                                          A ⊆A ∪B and B ⊆A ∪B

Complements, differences and symmetric differences-

Complement-

The complementof a set A, denoted by , is the set of elements which belong to U(universal set)but which do not belong to A. That is

= {x | x ∈U, x /∈A}

Difference-

The differenceof A and B, denoted byA\B or A-B, is the set of elements which belong to A but which do not belong to Bthat is-

A-B = {x | x ∈A, x / ∈B}

The set A\Bor A-Bis read “A minus B”.

Symmetric difference-

The symmetric differenceof sets A and B, denoted by A⊕B, consists of those elements which belong to A or B but not to both. That is

A ⊕B = (A ∪B)-(A ∩B) or A ⊕B = (A-B) ∪(B-A)

Cardinality of sets-

If A is finite set with n distinct elements, then n is called the cardinality of A. The cardinality of A is denoted by |A| [or by n (A)].

Example:Let A = {a, b, c, d}, then A is a finite set and |A| = 4

Cardinality of union of two sets-

Number of elements in A ∪B: (Cardinality of union) If A and B are any two finite sets then, the numbers of elements in A ∪B, denoted by | A ∪B | is given by | A ∪B | = | A | + | B | −| A ∩B |

Principal of inclusion and Exclusion-

Let we have A andB are finite sets. Then A ∪B and A ∩B are

Finite and

n(A ∪B) = n(A) + n(B) −n(A ∩B)

That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B) (inclusion) and then

Subtracting n(A ∩B) (exclusion) since its elements were counted twice

For three sets-

n(A ∪B ∪C) = n(A) + n(B) + n(C) −n(A ∩B) −n(A ∩C) −n(B ∩C) + n(A ∩B ∩C)

2.3 Ordered pair & n-tuples

Ordered pair-

An ordered pair of element a and b, where a is designated as the first element and b as the second element, it is denoted by (a, b).

In particular

If and only if a = c and b = d. thus
 

Unless a = b.

n-tuple-

A finite sequence over a set A is a function from {1, 2,….,n} into A, and it is usually denoted by

Such a sequence which is finite is called an n-tuple.

Here ‘n’ is a non-negative integer.

Tuples are written by listing the elements with parentheses ().

2.4 Cartesian product

Suppose we have two sets A and B, then we can form the set-

To be the set of all ordered pairs (x,y) where x is an element of A and y is an element of B.

Here we call the Cartesian product of A and B.

Example: If A = {1, 2} and B = {3, 4, 5} then find .

Sol.

Example: Let A = {1, 2} and B = {a, b, c}, then-

And

Note-

1.

2.

3. The Cartesian product of two sets of real numbers can be represented by tree diagrams.

Theorems-

If A, B, C are sets then-

1.

2.

Proof-

1.

2.

Theorem-

If A, B, and C are non-empty sets then A ⊆B ⇒A × C ⊆B × C

Proof: Let (a, b) be any element A × C, then

⇒a∈B and b ∈C (becauseA ⊆B)

⇒ (a, b)∈B × C

Hence A × C ⊆B × C

Cartesian product of n-sets-

Let denote n sets where n ≥2 , then the Cartesian product is the set ofall n-tuples of the form where

From the definition we have