Set Theory and Relations

Set Theory and Relations

(1) Roster method or Listing method : In this method a set is described by listing elements, separated by commas, within braces {}. The set of vowels of English alphabet may be described as {a, e, i, o, u}.

(2) Set-builder method or Rule method : In this method, a set is described by a characterizing property P(x) of its elements x. In such a case the set is described by {x: P(x) holds} or {x | P(x) holds}, which is read as ‘the set of all xsuch that P(x) holds’. The symbol ‘|’ or ‘:’ is read as ‘such that’.

The set $A={0,,1,,4,,9,,16,….}$ can be written as $A={{{x}^{2}}|xin Z}$.

UPDATED LINK
Go to above linked new page to download
Examples, Theory and Formulas, Practice 
Problems and worksheets of all topics of 

Mathematics.


Types of sets   

(2) Singleton set :A set consisting of a single element is called a singleton set. The set {5} is a singleton set.

(3) Finite set : A set is called a finite set if it is either void set or its elements can be listed (counted, labelled) by natural number 1, 2, 3, … and the process of listing terminates at a certain natural number n (say).

Cardinal number of a finite set : The number n in the above definition is called the cardinal number or order of a finite set Aand is denoted by n(A) or O(A).

(4) Infinite set : A set whose elements cannot be listed by the natural numbers 1, 2, 3, …., n, for any natural number n is called an infinite set.

(5) Equivalent set : Two finite sets A and B are equivalent if their cardinal numbers are same i.e. n(A) = n(B).

Example :$A={1,,3,,5,,7}$; $B={10,,,12,,14,,16}$ are equivalent sets, $[because ,,O(A)=O(B)=4]$.

(6) Equal set : Two sets A and B are said to be equal iffevery element of A is an element of B and also every element of B is an element of A. Symbolically, A = B if xÎ A Û x ÎB. 

(7) Universal set : A set that contains all sets in a given context is called the universal set.

(8) Power set : If S is any set, then the family of all the subsets of S is called the power set of S.

Power set of S is denoted by P(S). Symbolically, P(S) = {T : T Í S}. Obviously $varphi $ & Sare both elements of P(S).

Example :  Let S = {a, b, c}, then P(S) = {$varphi $, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Power set of a given set is always non-empty.

If A is subset of B, we write A Í B, which is read as “A is a subset of B” or “A is contained in B”.

Thus, A Í B Þ a ÎA Þa ÎB.

Proper and improper subsets : If A is a subset of B and $Ane B,$ then A is a proper subset of B. We write this as $Asubset B$.

The null set $varphi $ is subset of every set and every set is subset of itself, i.e., $varphi subset A$ and $Aunderline{subset },A$ for every set A. They are called improper subsets of A. Thus every non-empty set has two improper subsets. It should be noted that $varphi $ has only one subset $varphi $ which is improper.

All other subsets of A are called its proper subsets. Thus, if $Asubset B,$ $Ane B$, $Ane varphi $, then A  is said to be proper subset of B.

Example : Let $A={1,,2}$. Then A has $varphi ;{1},,{2},,{1,,2}$ as its subsets out of which $varphi $ and {1, 2} are improper and {1} and {2} are proper subsets.

 

The combination of rectangles and circles are called Venn–Eulerdiagrams or simply Venn-diagrams.

If A and B are not equal but they have some common elements, then to represent A and B we draw two intersecting circles.  Two disjoints sets are represented by two non-intersecting circles.

(1) Union of sets : Let A and B be two sets. The union of Aand B is the set of all elements which are in set A or in B. We denote the union of A and B by  $Acup B$, which is usually read as “A union B”.

Symbolically,      $Acup B={x:xin A,,text{or},,xin B}.$

(2) Intersection of sets : Let A and B be two sets. The intersection of A and B is the set of all those elements that belong to both A and B.

The intersection of Aand B is denoted by A ÇB (read as “A intersection B”).

Thus, A Ç B = {x : x ÎA and x Î B}.

(3) Disjoint sets :Two sets A and B are said to be disjoint, if AÇ B = f. If A Ç B ¹f, then A and B are said to be non-intersecting or non-overlapping sets.

Example : Sets {1, 2}; {3, 4} are disjoint sets.

(4) Difference of sets : Let A and B be two sets. The difference of A and B written as A – B, is the set of all those elements of Awhich do not belong to B.

Thus, A – B = {x: x ÎA and x Ï B}

Similarly, the difference$B-A$ is the set of all those elements of B that do not belong to A i.e., $B-A={xin B:xnotin A}$.

Example : Consider the sets $A={1,,2,,3}$ and $B={3,,4,,5}$, then $A-B={1,,2};,B-A={4,,5}$.

(5) Symmetric difference of two sets : Let A and B be two sets. The symmetric difference of sets A and B is the set $(A-B)cup (B-A)$ and is denoted by$ADelta B$. Thus, $ADelta B$ = $(A-B)cup (B-A)={x:xnotin Acap B}$.

(6) Complement of a set :  Let U be the universal set and let Abe a set such that A Ì U. Then, the complement of Awith respect to U is denoted by A¢or A^c or $C(A)$ or U – Aand is defined the set of all those elements of U which are not in A.

Thus,       A¢= {x ÎU : x Ï A}.

Clearly,    x ÎA¢Û x Ï A

Example : Consider $U={1,,2,……,10}$

and $A={1,,3,,5,,7,,9}$.

Then ${A}’={2,,4,,6,,8,,10}$ 

Some important results on number of elements in sets

If A, B and C are finite sets and Ube the finite universal set, then (1) n(A ÈB) = n(A) + n(B) – n(A Ç B)

(2) n(A ÈB) = n(A) + n(B) Û A, B are disjoint non-void sets.

(4) n(A DB) = Number of elements which belong to exactly one of A or B  

      = n((A – B) È (B – A))  = n(A – B) + n(B – A)            [Q (A – B) and (B – A) are disjoint]

(5) n(A ÈB ÈC) = n(A) + n(B) + n(C) – n(A ÇB) – n(B Ç C) – n(A ÇC) + n(A Ç B Ç C)

(6) n (Number of elements in exactly two of the sets A, B, C) = n(A ÇB) + n(B Ç C) + n(C ÇA) – 3n(AÇBÇC)

(7) n(Number of elements in exactly one of the sets A, B, C) 

  = n(A) + n(B) + n(C) – 2n(A Ç B) – 2n(B ÇC) – 2n(AÇ C) + 3n(A ÇB ÇC)

(8) n(A¢È B¢) = n(AÇ B)¢ = n(U) – n(A Ç B)

(9) n(A¢Ç B¢) = n(AÈ B)¢ = n(U) – n(A È B)

(1) Idempotent laws : For any set A, we have

(i)   A ÈA = A     (ii)  A Ç A = A

(2) Identity laws :For any set A, we have

(i)            A Èf= A            (ii) A ÇU = A

i.e., fand U are identity elements for union and intersection respectively.

(3) Commutative laws : For any two sets A and B, we have

(i) A È B = B È A              (ii) AÇ B = B Ç A

(iii) $ADelta B=BDelta A$

i.e., union, intersection and symmetric difference of two sets are commutative.

(iv) $A-Bne B-A$             (v) $Atimes Bne Btimes A$

i.e., difference and cartesian product of two sets are not commutative

(4) Associative laws : If A, B and C are any three sets, then

(i) (A È B) È C = A È (B È C)     (ii) AÇ (B Ç C) = (A ÇB) Ç C

(iii) $(ADelta B)Delta C=ADelta (BDelta C)$

i.e., union, intersection and symmetric difference of two sets are associative.

(iv) $(A-B)-Cne A-(B-C)$               (v) $(Atimes B)times Cne Atimes (Btimes C)$

i.e., difference and cartesian product of two sets are not associative.

(5) Distributive law : If A, B and C are any three sets, then

(i) A È(B ÇC) = (A È B) Ç(A ÈC)

(ii) A Ç (B È C) = (A Ç B) È(A ÇC)

i.e., union and intersection are distributive over intersection and union respectively.

(iii)  $Atimes (Bcap C)=(Atimes B)cap (Atimes C)$

(iv)  $Atimes (Bcup C)=(Atimes B)cup (Atimes C)$

(v)           $Atimes (B-C)=(Atimes B)-(Atimes C)$

(6) De-Morgan’s law : If A, B and C are any three sets, then

(i)            (A ÈB)¢= A¢Ç B¢

(ii)          (AÇ B)¢ = A¢È B¢

(iii)         A – (BÇ C) = (A – B) È(A – C)

(iv)          A – (BÈ C) = (A – B) Ç(A – C)

(7) If A and B are any two sets, then

(i)           A – B= A ÇB¢                  (ii)  B – A = B Ç A¢

(iii)          A – B= A ÛA ÇB = f    (iv) (A– B) ÈB = A È B

(v)          (A – B) Ç B = f                  (vi) A Í B Û B¢Í A¢

(vii)        (A – B) È (B – A) = (A ÈB) – (A Ç B)

(8)          If A, Band C are any three sets, then

(i)           A Ç(B – C) = (A Ç B) – (A Ç C)

(ii)          A Ç(B DC) = (A Ç B) D(A ÇC)

Cartesian product of sets : Let A and B be any two non-empty sets. The set of all ordered pairs (a, b) such that a Î A and b Î B is called the cartesian product of the sets A and B and is denoted by A ´ B.

Thus, A × B = [(a, b) : a ÎA and b Î B]

If A = for B = f, then we define A × B = f.

Example : Let A = {a, b, c} and B = {p, q}.

Then A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)}

Also B × A = {(p, a), (p, b), (p, c), (q, a), (q, b), (q, c)}

Theorem 1 : For any three sets A, B, C

(i)  A × (BÈ C) =(A × B) È(A × C)

(ii) A × (B ÇC) =(A × B) Ç (A × C)

Theorem 2 :  For any three sets A, B, C 

A × (B – C) = (A × B) – (A × C)

Theorem 3 :  If Aand B are any two non-empty sets, then

A × B = B× A ÛA = B

Theorem 4 :  If AÍ B, then A × A Í(A × B) Ç (B × A)

Theorem 5 :  If AÍ B, then A × C ÍB × C for any set C.

Theorem 6 :  If AÍ B and C Í D, then A × C ÍB × D

Theorem 7 :  For any sets A, B, C, D

(A × B) Ç(C ´D) = (A Ç C) × (B Ç D)

Theorem 8 :  For any three sets A, B, C

(i)  A × (B¢ È C¢)¢ = (A × B) Ç (A × C)          

(ii) A × (B¢Ç C¢)¢ = (A × B) È (A × C)

Examples on Set Theory

Let A and B be two non-empty sets, then every subset of       A × B defines a relation from A to B and every relation from A to B is a subset of A × B.

Let $Rsubseteq Atimes B$ and (a, b) Î R. Then we say that a is related to b by the relation R and write it as $a,R,b$. If $(a,,b)in R$,  we write it as$a,R,b$.

(1) Total number of relations : Let A and B be two non-empty finite sets consisting of m and n elements respectively. Then A × Bconsists of mn ordered pairs. So, total number of subset of A × B is 2^mn. Since each subset of A × B defines relation from A to B, so total number of relations from A to B is 2^mn. Among these 2^mn relations the void relation fand the universal relation A × B are trivial relations from A to B.

(2) Domain and range of a relation : Let R be a relation from a set A to a set B. Then the set of all first components or coordinates of the ordered pairs belonging to R is called the domain of R, while the set of all second components or coordinates of the ordered pairs in R is called the range of R.

Thus, Domain (R) = {a : (a, b) ÎR} and Range (R) = {b : (a, b) Î R}.

Let A, B be two sets and let R be a relation from a set A to a set B. Then  the inverse of R, denoted by R^–1, is a relation from B to A and is defined by ${{R}^{-1}}={(b,a):(a,b)in R}$

Clearly (a, b) ÎR Û(b, a) Î R^–1. Also, Dom (R) = Range $({{R}^{-1}})$ and Range (R) = Dom $({{R}^{-1}})$

Example :  Let A = {a, b, c}, B = {1, 2, 3} and R = {(a, 1), (a, 3), (b, 3), (c, 3)}.

Then,          (i)  R^–1 = {(1, a), (3, a), (3, b), (3, c)}   

                   (ii)  Dom (R) = {a, b, c} = Range $({{R}^{-1}})$  

                   (iii)  Range (R) = {1, 3} = Dom $({{R}^{-1}})$

(1) Reflexive relation : A relation R on a set A is said to be reflexive if every element of A is related to itself.

Thus, R is reflexive Û (a, a) Î R for all a Î A.

Example : Let A = {1, 2, 3} and R = {(1, 1); (1, 3)}

Then R  is not reflexive since $3in A$ but (3, 3) Ï R

A reflexive relation on A  is not necessarily the identity relation on A.

The universal relation on a non-void set A is reflexive.

(2) Symmetric relation : Relation R on a set A is said to be a symmetric relation

iff (a, b) Î R Þ (b, a) Î R for all a, b ÎA

i.e.,        aRbÞ bRa for all a, b ÎA.

it should be noted that R  is symmetric iff ${{R}^{-1}}=R$

The identity and the universal relations on a non-void set are symmetric relations.

A reflexive relation on a set A  is not necessarily symmetric.

(3) Anti-symmetric relation : Let A be any set. A relation R on set A is said to be an anti-symmetric relation iff (a, b) Î R and (b, a) ÎR Þa = b for all a, b Î A.

Thus, if a ¹ b then a may be related to bor b may be related to a, but never both.

(4) Transitive relation : Let A be any set. A relation R on set A is said to be a transitive relation iff

(a, b) ÎR and (b, c) Î R Þ (a, c) Î R for all a, b, cÎ A i.e.,  aRb and bRc Þ aRc for all a, b, cÎ A.

Transitivity fails only when there exists a, b, c such that a R b, b R c but $a,not{R},c$.

Example : Consider the set A = {1, 2, 3} and the relations

${{R}_{1}}={(1,,,2),,(1,,3)}$; ${{R}_{2}}$= {(1, 2)}; ${{R}_{3}}$= {(1, 1)};

${{R}_{4}}$ = {(1, 2), (2, 1), (1, 1)}

Then ${{R}_{1}}$, ${{R}_{2}}$, ${{R}_{3}}$ are transitive while ${{R}_{4}}$ is not transitive since in ${{R}_{4}},,(2,,,1)in {{R}_{4}};,(1,,2)in {{R}_{4}}$ but $(2,,2)notin {{R}_{4}}$.

The identity and the universal relations on a non-void sets are transitive.

(5) Identity relation :Let A be a set. Then the relation I_A = {(a, a) : a ÎA} on A is called the identity relation on A.

In other words, a relation I_Aon A is called the identity relation if every element of A is related to itself only. Every identity relation will be reflexive, symmetric and transitive.

Example : On the set = {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3)} is the identity relation on A .

It is interesting to note that every identity relation is reflexive but every reflexive relation need not be an identity relation.

(6) Equivalence relation : A relation R on a set A is said to be an equivalence relation on A iff

(i) It is reflexive i.e.(a, a) Î R for all a Î A

(ii) It is symmetric i.e.(a, b) Î R Þ(b, a) Î R, for all a, b Î A

(iii) It is transitive i.e.(a, b) Î R and (b, c) Î R Þ (a, c) Î R for all a, b, cÎ A.

Congruence modulo (m) :Let m be an arbitrary but fixed integer. Two integers a and b are said to be congruence modulo m  if $a-b$ is divisible by m  and we write $aequiv b$ (mod m).

Thus $aequiv b$ (mod m) $Leftrightarrow a-b$ is divisible by m. For example, $18equiv 3$ (mod 5) because 18 – 3 = 15 which is divisible by 5. Similarly, $3equiv 13$ (mod 2) because 3 – 13 = –10 which is divisible by 2. But 25 ¹ 2 (mod 4) because 4 is not a divisor of 25 – 3 = 22.

The relation “Congruence modulo m” is an equivalence relation.

Let R be equivalence relation in $A(ne varphi )$. Let $ain A$. Then the equivalence class of a, denoted by [a] or ${bar{a}}$ is defined as the set of all those points of A which are related to a under the relation R.

Thus [a] = {x ÎA : x R a}.

It is easy to see that

(1) $bin [a]Rightarrow ain [b]$            

(2) $bin [a]Rightarrow [a]=[b]$    

Let R and S be two relations from sets A to Band B to C respectively. Then we can define a relation SoR from A to C such that (a, c) Î SoR Û $ b Î B such that (a, b) Î R and (b, c) ÎS.

This relation is called the composition of R and S.

For example, if A = {1, 2, 3}, B = {a, b, c, d}, C={p, q, r, s} be three sets such that R = {(1, a), (2, b), (1, c), (2, d)} is a relation from A to Band S = {(a, s), (b, r), (c, r)} is a relation from Bto C. Then SoR is a relation from Ato C given by SoR = {(1, s) (2, r) (1, r)}

In this case RoSdoes not exist.