Set theory

What is Set theory?

• Set theory is the mathematical theory of well-determined collections, called sets of objects that are called members or elements of the set
• Elements in a set can be finite or infinite

Set theory – Finite set

Objects/ Elements of  Finite set are –

• • Days of the week: { Sun, Mon, Tue, Wed, Thus, Fri, Sat}
  • Prime number below 10 : { 2,3,5,7)
  • Factors of 12 : { 1,2,3,4,6,12}
  • Name of 5 Indian city : { Delhi,Mumbai,Kanpur,Chennai,Kolkata}
  • Name of 03 Indian Cricketer: { M Dhoni, Kohli, Sachin T}
  • Months of Year : (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec}
  • 5 companies listed in NIFTY: { TATA, Eicher, Dabur, Maruti, Hero Motor}
  • 3 Hindi Movie names: (DDLJ, Sholey, Bahubali}

Set theory – Infinite set 

• Natural number N :{ 1, 2, 3, 4……………………….∞ }
• Integers Z :{ -∞ ……………………-3,-2,-1, 0, 1, 2, 3 …………….…∞ }

Set theory – Element

Objects in the set are called element

• “Name of 5 Indian cities” : { Delhi,Mumbai,Kanpur,Chennai,Kolkata}
• Delhi is an element of the “Name of 5 Indian cities”
• Mathematically it will be represented by 
  • Delhi ∈ “Name of 5 Indian cities”
• Similarly In the case of natural numbers
  • 5 ∈ N
  • 18 ∈ N

Set theory – Cardinality

The cardinality of a set is a measure of a set’s size,

• Number of items in a finite set
• Count the number of elements in the set.
  • Example set A = {1, 2, 4} has a cardinality of 3

Properties of Set theory

• Sets are unordered: the following two sets are the same
  • {Sun, Mon, Tue, Wed, Thus, Fri, Sat}
  • {Mon, Tue, Sun, Wed, Thus, Sat, Fri}
• The duplicate element does not matter
  • {Sun, Mon, Tue, Wed, Mon, Thus, Fri, Sat, Sun}

Union of Sets

The union of two sets X and Y is equal to the set of elements that are present in set X, in set Y, or in both the sets X and Y. This operation can be represented as;

X ∪ Y

Example:

• set A = {1, 3, 5} and
• set B = {1, 2, 4} then;
• A ∪ B = {1, 2, 3, 4, 5}

Properties – Union of Sets

Commutative Law: 

The union of two or more sets follows the commutative law i.e. if we have two sets A and B then,

A∪B=B∪A

Example:

• A = {a, b} and B = {b, c, d}
• So, A∪B = {a,b,c, d}
• B∪A = {b,c,d,a}

Since, in both the union, the group of elements is the same. Therefore, it satisfies commutative law.

A∪B=B∪A

Associative Law

The union operation follows the associative law i.e. if we have three sets A, B and C then

(A∪B)∪C = A∪(B∪C)

Example: 

• A = {a, b} and B = {b, c, d} and C = {a,c,e}
• (A∪B)∪C = {a,b,c,d} ∪ {a,c,e} = {a,b,c,d,e}
• A∪(B∪C) = {a, b} ∪ {b,c,d,e} = {a,b,c,d,e}
• Hence, associative law proved.

Identity Law

The union of an empty set with any set A gives the set itself i.e.,

A∪∅=A

• Suppose, A = {a,b,c} and ∅ ={}
• then, A∪∅ = {a,b,c} ∪ {} = {a,b,c}

Idempotent Law

The union of any set A with itself gives the set A i.e.,

A∪A=A

• Suppose, A = {1,2,3,4,5}
• then A ∪ A = {1,2,3,4,5} ∪ {1,2,3,4,5} = {1,2,3,4,5} = A

Domination Law

The union of a universal set U with its subset A gives the universal set itself.

A∪U=U

• Suppose, A = {1,2,4,7} and U = {1,2,3,4,5,6,7}
• then A∪U = {1,2,4,7} ∪ {1,2,3,4,5,6,7} = {1,2,3,4,5,6,7} = U

Intersection of Sets

The set operation intersection takes only the elements that are in both sets. The intersection contains the elements that the two sets have in common. The intersection is where the two sets overlap.

In set-builder notation, A ∩ B = {x ∈ U : x ∈ A and x ∈ B}.

Example:

• Let A = {a, b, c, d} and B = {b, d, e}. Then A ∩ B = {b, d}.
• Elements b and d are the only elements that are in both sets A and B.

Example:

• Let G = {t, a, n} and H = {n, a, t}. Then G ∩ H = {a, n, t}. Note that here G = H = G ∩ H.

Example:

• Let C = {2, 6, 10, 14, …} and D = {2, 4, 6, 8, …}. Then C ∩ D = {2, 6, 10, 14, …} = C.

Note: In all the examples, the intersection is a subset of each set forming the intersection, i.e., A ∩ B ⊆ A and A ∩ B ⊆ B.

Disjoint Sets

Two sets whose intersection is the empty set are called disjoint sets.

Example:

• Let E = {d, a, y} and F = {n, i, g, h, t}. Since E ∩ F = ∅, the sets E and F are disjoint sets.

Complement Sets

• If U is a universal set and A is any subset of U then the complement of A is the set of all members of the universal set U which are not the elements of A.

A′ = {x : x ∈ U and x ∉ A}

• Alternatively, it can be said that the difference between the universal set U and the subset A gives us the complement of set A.
• To make it more clear consider a universal set U of all natural numbers less than or equal to 20. Let set A which is a subset of U be defined as the set which consists of all the prime numbers. Thus we can see that A = {2,3,5,7,11,13,17,19}
• Now the complement of this set A consists of all those elements which is present in the universal set but not in A. Therefore, A′ is given by:

A′={1,4,6,8,9,10,12,14,15,16,18,20}

Example: 

Let U be the universal set which consists of all the integers greater than 5 but less than or equal to 25. Let A and B be the subsets of U defined as:

A = {x : x ∈ U and x is a perfect square}

B = {7,9,16,18,24 }

Find the complement of sets A and B and the intersection of both the complemented sets.

Solution: 

• The universal set is defined as:
• U = {6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}
• Also, A = {9,16,25} and
• B = {7,9,16,18,24}

The complement of set A is defined as:

A′ = {x : x ∈ U and x ∉ A}

• Therefore, A′ = {6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24}
• Similarly, the complement of set B can be given by:
• B′ = {6,8,10,11,12,13,14,15,17,19,20,21,22,23,25}
• The intersection of both the complemented sets is given by A′∩B′.
• A’∩ B’= {6, 8, 10, 11, 12, 13, 14, 15, 17, 19, 20, 21, 22, 23}

Set difference

• The relative complement or set difference of sets A and B
• The set difference between two sets A and B is written as A∖B; A∖B = A – B,
• It can also be defined as: A∖B = {x ∈S : x ∉ T}
• It is the set of all elements in A that are not in B.
• A∖B means the set that consists of the elements of A which are not elements of B

Example:

• A = {a, b, c, d} and B = {b, d, e}.
• A – B = {a, c}
• B – A = {e}.

Example:

• G = {t, a, n} and H = {n, a, t}.
• G – H = ∅.

Example:

• If A = {2, 3, 4} and B = {4, 5, 6} 
• A – B means elements of A that are not the elements of B. 
  i.e., in the above example A – B = {2, 3} 
  In general, B – A = {x : x ∈ B, and x ∉ A} 

If A and B are disjoint sets, then

• A – B = A  & 
• B – A = B

Example:

Find the difference between the two sets: A = {1, 2, 3} and B = {4, 5, 6}. 

• A and B
• B and A

Solution:
The two sets are disjoint as they do not have any elements in common. 

• A – B = {1, 2, 3} = A
• B – A = {4, 5, 6} = B 

Example:

Find the difference between the two sets: A = {a, b, c, d, e, f} and B = {b, d, f, g}

• A and B
• B and A

Solution:
A – B = {a, c, e} : Therefore, the elements a, c, e belong to A but not to B 

B – A = {g)  : Therefore, the element g belongs to B but not A. 

Example:

Given three sets P, Q, and R such that:

• P = {x : x is a natural number between 10 and 16},
• Q = {y : y is a even number between 8 and 20} and
• R = {7, 9, 11, 14, 18, 20}
  • Find the difference of two sets P and Q
  • Find Q – R
  • Find R – P
  • Find Q – P

Solution:

(i) P – Q = {Those elements of set P which are not in set Q}

            = {11, 13, 15}

(ii) Q – R = {Those elements of set Q not belonging to set R}

             = {10, 12, 16}

(iii) R – P = {Those elements of set R which are not in set P}

             = {7, 9, 18, 20}

(iv) Q – P = {Those elements of set Q not belonging to set P}

              = {10, 16, 18}

Set Identity

The identity relation on set A is defined as in = {(x,y) ∈ A × A|x = y}.

• • A  =  {1, 2, 3} and R be a relation defined on  set A as
  • R  =  {(1, 1), (2, 2), (3, 3)}

When we look at the ordered pairs of R, we find the following associations. 

• • (1, 1) —–> 1 is related to 1
  • (2, 2) —–> 2 is related to 2
  • (3, 3) —–> 3 is related to 3

Set Reflexive relation

Reflexive relation is the one in which every element maps to itself.

• • For example, consider a set A = {1, 2,}.

Now, the reflexive relation will be R = {(1, 1), (2, 2), (1, 2), (2, 1)}.

A relation is reflexive if: Symmetry, transitivity, and reflexivity are the three properties representing equivalence relations.

• Reflexive = ” Every element is related to itself “
• Identity   = ” Every element is related to itself only 

Set Symmetric

• The relation a=b is symmetric, but a>b is not.
• In other words, we can say the symmetric property is something where one side is a mirror image or reflection of the other.
• Or simply we can say any image or shape that can be divided into identical halves is called symmetrical and each of the divided parts is in a symmetrical relationship to each other
• A relation R in a set A is said to be in a symmetric relation only if every value of a, b ∈ A

(a, b) ∈ R and (b, a) ∈R.

• Two objects are symmetrical when they have the same size and shape but different orientations.

Example:

• R is a relation in a set A where A = {1,2,3}
• R contains another pair R = {(1,1), (1,2), (1,3), (2,3), (3,1)}
• for R = {(1,1), (1,2), (1,3), (2,3), (3,1)} in symmetry relation, we must have (2,1), (3,2).
• Then only we can say that the above relation is in symmetric relation.
• R = {(1,1), (1,2), (1,3), (2,3), (3,1), (2,1), (3,2)}

Set- Antisymmetric relations

• If (a, b) ∈ R and a ≠ b, then (b, a) R
• {(a, b) | (a, b) ∈ R × R, a < b} ; If a < b then b ≮ a

Mother-child relation:

• M ⊆ P × P relates mothers to children
• If (p, c) ∈ M then (c, p) M

Set Transitive relation

• Transitive relations;  If (a, b) ∈ R and (b, c) ∈ R
• then (a, c) ∈ R
  

  ---

• {(a, b) | (a, b) ∈ N × N, a|b} If a|b and b|c then a|c {(a, b) | (a, b) ∈ R × R, a < b} If a < b and b < c then a < c
• A relation ρ on the set N is given by R = {(a, b) ∈ N × N: a is a divisor of b}
•  R is a transitive relation.
  

  ---

• Consider A  =  { 1, 2, 3 } and R be a relation defined on set A as “is less than” and R  = {(1, 2), (2, 3), (1, 3)} Prove transitive.  

From the given set A, let
a  =  1
b  =  2
c  =  3

Then, we have

(a, b)  =  (1, 2) —–> 1 is less than 2 
(b, c)  =  (2, 3) —–> 2 is less than 3 
(a, c)  =  (1, 3) —–> 1 is less than 3 

That is, if 1 is less than 2 and 2 is less than 3, then 1 is less than 3. 

or

R2, 2R3 —–> 1R3

The above points prove that R is a transitive relation.

• ---

  If A is the set of all brothers in a family, then the R= “is a brother of” relation is transitive over A.

• if A is the brother of B and B is the brother of C then A is the brother of C 

Set Equivalence

A relation R on a set A is said to be an equivalence relation if and only if the relation R is reflexive, symmetric, and transitive.

• Reflexive: A relation is said to be reflexive, if (a, a) ∈ R, for every a ∈ A.
• Symmetric: A relation is said to be symmetric, if (a, b) ∈ R, then (b, a) ∈ R.
• Transitive: A relation is said to be transitive if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Equivalence relations can be explained in terms of the following examples:

• The sign of ‘is equal to’ on a set of numbers; for example, 1/3 is equal to 3/9.
• For a given set of triangles, the relation of ‘is similar to’ and ‘is congruent to.
• For a given set of integers, the relation of ‘is congruent to, modulo n’ shows equivalence.
• The image and domain are the same under a function, which shows the relation of equivalence.
• For a set of all angles, ‘has the same cosine’.
• For a set of all real numbers,’ has the same absolute value’.

Set Comprehension

Define first 500 natural numbers Y = {x l x N , x< 500 }

Y: {0, 1, 2, 3, 4, 5, 6, 7 …………499}

Squares of even integers Y= {x² l x Z , x mod 2=0}

Y : { 0 , 4 , 16 , 36 , 64 ,100 , 144 , ………….}

Cube of natural numbers Y = {x³ l x N }

Y: {0 , 1 , 8 , 27 , 64 ,125 ………….}

List of integers whose square root is also integer Y = {x l x Z , √x }

Y: {0, 1, 4, 9, 16, 25, 36, ………………..…∞

List of perfect squares Y = {x² l x N }

Y: {0, 1, 4, 9, 16, 25, 36 ……………………….…∞}

List of Rational numbers whose square root is also rational Y = {x l x R, √x }

Y: {0, 1, 4, 9, 16, 25, 36, ………1/4 , 9/4 , 9/16 , 16/25 ………..…∞}

Cartesian Product

The cartesian product of two sets X and Y, denoted X × Y, is the set of all ordered pairs (x, y) where x is in X and y is in Y.

• X×Y = {(x, y): x ∈ X and y ∈ Y}
• A × B = {(a, b) | a ∈ A, b ∈ B}

Example:

• A={x, y, z}
• B= {1, 2, 3};

A x B =

A x B = { (x,1) , (x,2), (x,3), (y,1), (y,2), (y,3), (z,1), (z,2), (z,3) }

B x A = 

A x B = { (1,x) , (1,y), (1,z), (2,x), (2,y), (2,z), (3,x), (3,y), (3,z) }

Example:

A = {0, 1}, B = {2, 3}

A × B =

A x B = {(0, 2), (0, 3), (1, 2), (1, 3)}

B x A =

A x B = {(2, 0), (2, 1), (3, 0), (3, 1)}

Binary relations

Y = {(m, n) | (m, n) ∈ N × N, n = m + 1}

Y = {(0, 1),(1, 2),(2, 3), . . . ,(17, 18), . . .}

Pairs (d,n), d is a factor on n

• Y = {(d, n) | (d, n) ∈ N × N, n mod d =0}

Y = {(1, 1), ………(2, 4),………(3,6), . . . ,(15, 75), . . ……… }

Filter set of Father & children names from Population P

Y = {(f, d) | (f, d) ∈ P × P, f= father of children}

Points at a distance 3 from (0, 0)

Y = {(x, y) | (x, y) ∈ R × R , }

Y = {(0, 3),(3,0) , (0,-3) ,(-3,0), (1,√8), … }

Pythagorean triples Square on the hypotenuse is the sum of the squares on the opposite sides

Y= {(a, b, c) | (a, b, c) ∈ N × N × N, a, b, c > 0, a ² + b ² = c ²}

A × B — Cartesian product

All pairs (a, b), a ∈ A, and b ∈ B

• A = {1, 4, 7}, B = {1, 16, 49}
• A × B = {(1, 1),(1, 16),(1, 49),(4, 1),(4, 16),(4, 49),(7, 1),(7, 16),(7, 49)}
• B × A = {(1, 1),(16, 1),(49, 1),(1, 4),(16, 4),(49, 4),(1, 7),(16, 7),(49, 7)}
• B × B = {(1, 1), (1, 16), (1, 49), (16, 1), (16, 16), (16, 49), (49, 1), (49, 16), (49, 49)}

Cartesian product of more than two sets

A × B × A =

{(1, 1, 1), (1, 1, 4), (1, 1, 7), (1, 16, 1), (1, 16, 7). . . (7, 49, 1), (7, 49, 16), (7, 49, 49)}