# Set Theory and Relations

## Set Theory

A set is well defined class or collection of objects.

A set is often described in the following two ways.

(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}\$.

Mathematics.

Types of sets

(1) Null set or Empty set : The set which contains no element at all is called the null set. This set is sometimes also called the ‘empty set’ or the ‘void set’. It is denoted by the symbol \$varphi \$ or {}.

(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.

Example : If\$A={2,,3,,5,,6}\$and \$B={6,,5,,3,,2}\$. Then \$A=B,\$ because each element of A is an element of B and vice-versa.

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

It should be noted that universal set is not unique. It may differ in problem to problem.

(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.

(9) Subsets (Set inclusion): If every element of set A is an element of set B, then A is a subset of B.

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.

Venn-Euler diagrams

The combination of rectangles and circles are called VennEulerdiagrams 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.

Operations on sets

(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 AB, is the set of all those elements of Awhich do not belong to B.

Thus, AB = {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 Ac or \$C(A)\$ or UAand 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.

(3) n(AB) = n(A) – n(A ÇB) i.e., n(AB) + n(A Ç B) = n(A)

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

= n((AB) È (BA))  = n(AB) + n(BA)            [Q (AB) and (BA) are disjoint]

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

(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)

Laws of algebra of sets

(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

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

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) = (AB) È(AC)

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

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

(i)           AB= A ÇB¢                  (ii)  BA = B Ç A¢

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

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

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

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

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

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

Cartesian product of sets

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)}

Important theorems on cartesian product of sets :

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 × (BC) = (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

Relations and Types of Relations

Definition

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 2mn. Since each subset of A × B defines relation from A to B, so total number of relations from A to B is 2mn. Among these 2mn 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}.

Inverse relation

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}})\$

Types of relations

(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.

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

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

In other words, a relation IAon 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.

Equivalence classes of 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]\$

(3) Two equivalence classes are either disjoint or identical.

Composition of relations

##### In general RoS¹ SoR. Also (SoR)–1= R–1oS–1.

Important Points from Set Theory and Relations
 ?  Equal sets are always equivalent but equivalent sets may need not be equal set. ?  If A  has n elements, then P(A) has 2n elements. ?  The total number of subset of a finite set containing n elements is 2n. ?  If \${{A}_{1}},,{{A}_{2}},……,{{A}_{n}}\$ is a finite family of sets, then their union is denoted by \$bigcuplimits_{i=1}^{n}{{{A}_{i}}}\$ or \${{A}_{1}}cup {{A}_{2}}cup {{A}_{3}}……cup {{A}_{n}}\$. ?  If \${{A}_{1}},,{{A}_{2}},{{A}_{3}}…….,{{A}_{n}}\$ is a finite family of sets, then their intersection is denoted by \$bigcaplimits_{i=1}^{n}{{{A}_{i}}}\$ or \${{A}_{1}}cap {{A}_{2}}cap {{A}_{3}}cap ……..cap {{A}_{n}}\$. ?  \$R-Q\$ is the set of all irrational numbers. ?  Let A and B two non-empty sets having n elements in common, then A × B and B × A have n2 elements in common. ?  The identity relation on a set A is an anti-symmetric relation. ?  The universal relation on a set A containing at least two elements is not anti-symmetric, because if   a ¹ b are in A, then a is related to b and b is related to a under the universal relation will imply that a = b but a ¹ b. ?  The set \${(a,,a),:,ain A}=D\$ is called the diagonal line of \$Atimes A\$. Then “the relation R in A is antisymmetric iff \$Rcap {{R}^{-1}}subseteq D\$”. ? The relation ‘is congruent to’ on the set T of all triangles in a plane is a transitive relation. ?  If R and S are two equivalence relations on a set A , then   R Ç S is also an equivalence relation on A. ?  The union of two equivalence relations on a set is not necessarily an equivalence relation on the set. ?  The inverse of an equivalence relation is an equivalence relation.