virtualgate's picture

Sets & Relations

Basics of set theory | Set | Power Set | Cartesian Product

Set - A collection of unordered and distinct objects.
Examples:
N = {0, 1, 2, 3, .....} , the set of natural numbers
Z = {....., -2, -1, 0, 1, 2,....}, the set of integers
Z+ = {1, 2, 3,......}, the set of positive integers
Q = { p/q | p ε Z , and q≠0}, the set of rational numbers
Q+ = { x ε R | x=p/q, for some positive integers p and q }, the set of all positive rational numbers
R, the set of all real numbers

Power Set: 
Given a set S, the power set of S is the set of all subsets of the set S. It is denoted by P(S). 
Examples:
S = {0 ,1 ,2}
P(S) = P({0, 1, 2}) = {Φ, {0}, {1}, {2}, {0 ,1}, {0, 2}, {1, 2}, {1, 2, 3}}.
Note:
S = Φ
P(S) = {Φ}
P(P(S)) = {Φ, {Φ}}
Cartesian Product: The cartesian product of sets A and B, denoted by A x B, is the set of all ordered pairs (a, b), where aε A and b ε B. Hence,
A x B = {(a, b) | a ε A ∧ b ε B}
Example:
A = {1, 2}
B = {a, b, c}
A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

Set Identities:

Contributor's Info

Created: Edited:
0Comment
Set Theory Basics(1)

Subset: B is called a subset of A if the number of elements in B is less than or equal to A. Ex:

A ={1,2,3,4}

B={2,3,4}

We can say that B ⊆ A

 

Proper Subset:

B is called the proper subset of A if A contains at least one element that B doesn't contain.  So A is also called as a proper superset. B⊂ A.

 

 The cardinality of the set: Number of elements present in a set is called the cardinality of the set. Ex:

X={a,b,c,d,e,f,g}

Cardinality is denoted of X is written as |X|

|X| = 7

 

Null Set: A set having no element is called a null set. It is denoted by {} or Ø

But {Ø} is not a null set.

 

Must read Topics and Examples:-

Contributor's Info

Created:
0Comment
Set Example(1) and Tricks

1. let  A is a set such that A={a,b}

 The power set of A is P(A): is defined as a  set that contains all the subset of set A and we already know that  subsets of a set are also a set, that's why we also write-subset in set form

So subsets of A = {Ø , {a} ,{b} ,{a,b} }

P(A) ={ Ø , {a} ,{b} ,{a,b} }

P (P(A)) = { Ø ,   {Ø}   ,  {{a}}    ,    {{b}}   ,   {{a,b}}   ,   {Ø ,{a}}  ,  {Ø, {b}}   ,    {Ø ,{a,b}}   ,   {{a}, {b}}  ,    {{a} ,{a,b}}   ,   {{b}, {a,b}}   ,     {{Ø }, {a} ,{b}} ,    {{Ø } , {b} ,{a,b}}   ,   

  {{Ø } ,{a} , {a,b}}    ,     {{a} ,{b} ,{a,b}}   }

If a set  'A'contain n elements then power set  P(A ) conatain 2 elements.

 

2. Some tricks to solve questions directly.

  • A ∩ B=   AB
  • A∪ B=    A+B
  • A-B =     A ∩ B'
  • A+ AB  = A(1+B) = A      //  1+ anything =1
  • A.A'= 0
  • A+A' = 1

Disjoint Set:  Two set A and B are said to be  disjoint if A ∩ B = Ø

 

 

 

 

 

0Comment
Basics of relation | Types of relation | Reflexive | Irreflexive | Symmetric | AntiSymmetric | Asymmetric | Transitive | Equivalence

Relation: A binary relation from set A to set B is a subset of AxB (cartesian product of A and B).
Example:
A = {1, 2, 3, 4}
Find R = {(a, b) | a divides b} ?
Answer: R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
Types of relation

Relation  Definition Example
Reflexive A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (1,4)}
Irreflexive A relation R on set A is called Irreflexive if no a∈A is related to a (aRa does not hold). A = {1, 2, 3}
R = {(1,3), (1,4)}
Symmetric A relation R on set A is called Symmetric if aRb implies bRa, ∀a∈Aand ∀b∈A. A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (3,1)}
AntiSymmetric A relation R on set A is called Anti-Symmetric if aRb and bRa implies a=b, ∀a∈A and ∀b∈A. A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (2,3}
Asymmetric A relation R on set A is called Asymmetric if for all a, b in A, if (a,b) is in R, then (b,a) is not in R. A = {1, 2, 3}
R = {(1,3), (2,3}
Transitive A relation R on set A is called Transitive if aRb and bRc implies aRc, ∀a,b,c ∈A A = {1, 2, 3}
R = {(1,2), (2,3), (1,3)}
Equivalence A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. A = {1, 2, 3}
R = {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}

Contributor's Info

Created: Edited:
0Comment
Determine the relation

Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈ R if and only if

a) everyone who has visited Web page a has also visited Web page b.

b)  there are no common links found on both Web page a and Web page b  

c) there is at least one common link on Web page a and Web page b.

d) there is a Web page that includes links to both Web page a and Web page b.

 

Things you need to know

Refer to short notes : http://www.techtud.com/short-notes/basics-relation

Now, 

a) everyone who has visited Web page a has also visited Web page b.  

      (I)  Reflexive:          (a, a) ∈ R

            because,  everyone who has visited web-page a has by default visited

      (II) Transitive:         refer to the def. of Transitive and example on http://www.techtud.com/short-notes/basics-relation

      (III) NOT Symmetric: Because, A/Q        (a,b) ∈ R, but (b,a) ∉ R,

      (IV) NOT Antisymmetic : Because, A/Q  (a,b) ∈ R, but (b, a) can belong to R for some of webpages..

                                              What this means ?

                                              Consider WebPage = {1,2,3}

                                              and R = { (1,1), (2,2), (3,3),  (1, 2 ) , (2,1), (1,3) , (3,2)}

                                              This relation is antisymetric despite the fact that (1,2) and (1,2) both ∈ R

 

(b)  there are no common links found on both Web page a and Web page b  

        (I) NOT Reflexive : As note the relation says that "there are no common links found on both Web page a and Web page b " , i.e if (a, b) ∈ R, 

            a, b do not share common links ∴ (a,a) ∉ R, hence NOT Reflexive.

        (II) Symmentric : Symmetric says that if (a,b) ∈ R, then (b,a ) ∈, this is True for the given relation.

        (III)NOT Transitive:  it says that (a, b) ∧ (b, c) ⇒ (a , c) , but if this holds then web-page a and web-page will have a common link to web-                   page c

        (IV) NOT Asymmetric: as it is symmetric

 

(c) there is at least one common link on Web page a and Web page b.

       (I) NOT Reflexive : (a,b) ∈ R, if a and b share at-least one common link, but consiter a web page with no links (e) then (e,e) ∉ R. Therefore              not reflexive

       (II) Symmetric  : if (a, b) ∈ R, then a and b share atleast one common link, therefore (b,a) ∈ R. Hence , Symmetric

       (III) NOT Transitive:    if (a, b) ∈ and (b, c) ∈ R, then it is not necessary that (a,c) ∈ R. Because, if web-page a and web-page b share

             at- least one common link and web-page b and web-page c share at-least one common link then, it is not necessary that web-page a and              web-page  will also share a common link. 

      (IV) NOT Antisymmetric:  as it is symmetric 

 

(d) there is a Web page that includes links to both Web page a and Web page b.

      (I) NOT Reflexive: (a,b) ∈ R, if there exist a web-page (say web-page m) such that m has links for both web-page a and web-page b . Now, 

         (a, a) need not belong to R, as the could be no web-page pointing to web-page a.

      (II) Symmetric: if (a, b) ∈ R, i.e there is a web-page linking to web-page a and web-page b, then (b,a) ∈ R. Hence, Symmetric.

       (III) NOT Transitive: If  ( a, b) ∈ R, and (b, c) ∈  then it is not necessary that (a,c)∈ R. If web-page e points to web-page a and web-page b,             web-page f points to web-page b and web-page c then it is not necessary that there exit a web-page which'll point to both web-page a and 

          web-page c.

        (IV) NOT Antisymmetric:  As it is symmetric.

       

2Comments
GATE 2016 question on relation

A binary relation R on N×N is defined as follows: (a,b)R(c,d) if a ≤ c or b ≤ d. Consider the following propositions:

P: R is reflexive

Q: R is transitive

Which one of the following statements is TRUE?

(A) Both P and Q are true

(B) P is true and Q is false.

(C) P is false and Q is true.

(D) Both P and Q are false.

Things you need to know

refer : http://www.techtud.com/short-notes/basics-relation

Checking for Reflexivity

R is reflexive when (a,b) R (a, b) which is True as a ≤ a or b ≤ b is True.

 

Checking for Transitivity

NOT Transitive as if (a, b) R (c, d) and (c, d) R (p, q) then it is not necessart that (a, b) R (p, q) based on the condition given in the question.

Hence, Ans (B)

0Comment
Number of Ordered Pairs

Let S be a set of nelements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:

A

n and n

B

n2 and n

C

n2 and 0

D

n and 1

A relation is said to be an equivalence relation, when it satisfies 3 properties mainly:

  • Reflexive
  • Symmetric
  • Transitive

Largest equivalence relation on set S is of size n2 , this is the case when relation all the npossible pairs.

Smallest equivalence relation on set S is of size n , this is the case when relation has only reflexive element pairs.

Example: S = (1,3,5)
Largest ordered set are s x s = { (1,1) (1,3) (1,5) (3,1) (3,3) (3,5) (5,1) (5,3) (5,5) } which are 9 which equal to 3^2 = n^2
Smallest ordered set are { (1,1)( 3,3)(5,5)} which are 3 and equals to n. number of elements.

5Comments
Ir-Reflexive and Reflexive

Let A= {1,2,3,4,5,6,........ n}

1. The cardinality of smallest reflexive relations.

2. The cardinality of smallest Ir-reflexive relation.

3. The cardinality of largest Ir reflexive relation.

4.  Choose the correct:

R1= {(1,1) , (1,2), (2,4)} is reflexive 

R2= {(1,1) , (2,5)} is  ir-reflexive.

Solutions: 

1. we already know that for a relation to be reflexive "All the diagonal elements must be present " and number of diagonal elements is n So The cardinality of smallest reflexive relations is =

Diagonal elements are : (1,1) (2,2) (3,3) (4,4) .................(n,n)

 

2. Irreflexive means there should be no diagonal elements. 

So  The cardinality of the smallest Ir-reflexive relation is 0 = Ø or  {   }

 

3. It should not contain any diagonal elements so remaining elements are  n^{2} -n . This is max. Cardinality.

 

4. for R1: No, because pairs like (2,2) ,(3,3)................(n,n) is not present. 

     for R2: No, because there is a diagonal element (1,1). for irreflixive, there should not be any diagonal elements .

0Comment
Couting the Relations

let A  and B are set such that |A| =n  and |B| = m

then  |A*B| = m*n

Relation: It is a subset of cartesian product.

Since already we know |A*B| = m*n and each element in the cartesian product have two choices: either they want to be the part of the relation of they don't want. 

2 choices for m*n elements so total no. relations possible = 2m*n

 

we have already discussed the types of relations. So let's know some more details:

1. Number of Reflexive relations:-

let |A| = n

Reflexive relations are always defined on the same set :

|A*A| = n2 

if there are n elements in the set then there will be n reflexive pairs like (1,1), (2,2) ... (n,n)

So all these pairs must be present in  reflexive pairs so out of n2 elements n has one choice as they must be the part of relation but remaining  n2 -n has two choice 

So total number of reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}

 

2. The number of Ir-Reflexive relations:

Again those reflexive pairs have only one choice they must not be present so: one choice for 'n' elements and two choices for n2 -n elements.

total number of Ir- reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}

 

 

https://www.techtud.com/example-tbd/choose-correct-statement

Contributor's Info

Created:
0Comment
Non Diagonal Pair and Couting the Relations(2)

3. Symmetric relation:-

Diagonal elements have two choices either they want to be the part or they don't. But for remaining elements, if (a,b) is present then (b, a) must be present.

So  Non - Diagonal elements are chosen in this way to participate in a relation.

the total number of Non-Diagonal element are : n^{2} -n 

 and the total number of Non-Diagonal Pairs are:-  (n^{2}-n)/2

 each pair have two choices: either they want to be part of relation or they don't.

Why we are making pairs:  By making pair we are assuring either both (a,b) and (b, a) is present or both are absent.  Two elements of type (a,b) and (b,a) forms a non-diagonal pair.

 

So total number of Symmetric relations is:-  2^{(n^{2}-n)/2}. 2^{^{n}}

 

Example:- 

let us say A={1,2,3} then 

and A relation R from A to A  is shown below:

R= {(1,1) ,(1,2) , (1,3)

        (2,1) ,(2,2) , (2,3)

        (3,1) ,(3,2) ,  (3,3) }

Now If you see ,clearly the bold letters represent a diagonal and and

Total number of diagonal elements is               3

Total number of Non - Diagonal element is :-  6 

Total number of Non - Diagonal pairs :-    6/2=3 and they are like this:-

1^{st} pair ={(1,2)(2,1)}

2^{nd} pair ={(1,3)(3,1)}

3^{rd} pair ={(2,3)(3,2)}

 

 So total number of Symmetric relations  = 2^{3}. 2^{3} = 64

 

 

Contributor's Info

Created:
0Comment
Counting the Relations (3)

4. Antisymmetric Relations:-

Here Diagonal elements have 2 choices but 

for non-diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.

let |A| =n then and R is a relation from A to A, so 

Total number of elements in R = n2 

Total number of Diagonal pair = n

Total number of Non- Diagonal pair = (n^{2}-n)/2 and each have 3 choices

So Total number of  Antisymmetric Relations = 3^{(n^{2}-n)/2}. 2^{n}

 

5. Asymmetric Relations:

Diagonal pairs have only one choice as they are not allowed here.

Non-Diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.
  • So total number of Asymmetric Relation3^{(n^{2}-n)/2}. 1^{n} =3^{(n^{2}-n)/2} 

 

 

 

 

 

 

Contributor's Info

Created:
0Comment
GATE 1996 question on Set Theory

Let A and  B be sets and let Ac and  Bc denote the complements of the sets A and B. The set (A − B) ∪ (B − A) ∪ (A ∩ B) is equal to

a) A ∪ B

b) Ac ∪ Bc

c) A ∩ B

d) Ac ∩ Bc

 

0Comment
Bell number and Equivalence Relations

Sometimes in Exam, we are given a Set and then ask us to find the number of equivalence relations. for this, we use the bell Number.

Example:

let A ={1,2,3,4} .What is total number of Eqivalence relations? 

Solutions: 

Total number of elements in Set A= 4

So the total number of equivalence relation=15

 

For more bell numbers, Please refer to the given link.

https://www.youtube.com/watch?v=NjTv6cu4wQU

 

Contributor's Info

Created:
0Comment
Beautiful Examples on Set , Relation and Functions

1. If A ={1,2,3,45,}, then number of Equivalence relation is ______

2. If a set S has {\color{Red} n} elements then the minimum and maximum cardinality of an equivalence relation is ________

3. If a set S has {\color{Red} n} elements then the total number of relations that are both reflexive and Symmetric is ________

4. An element of the set can be a subset of that set. True or False?  ______

5. if a set S has {\color{Red} n} elements, The total number of relations that are Antisymmetric and  Asymmetric is _____

 

 

Solutions:

Solution 1

Number of equivalence relations can be calculated using Bell Number: Please refer to the following link

https://www.techtud.com/short-notes/bell-number-and-equivalence-relations

 

Solution 2:

Set S has n element So: for equivalence relation, the reflexive property must be satisfied (we need to satisfied reflexive, symmetric and transitive property, I am talking in reference with the question )and we have already discussed if a set has n elements then there are n reflexive pair. 

So for a minimum cardinality at least n elements must be there 

     for maximum cardinality, all elements should be present: 2

 

Solution 3:-

If a set  S has 'n' elements then the total number of elements in S* S  (Available to participate in relation )is  :  n^{2} 

out of n^{2}  , there are  n diagonal elements which must be present if a relation has to reflexive. So the diagonal element has only one choice. 

Now remaining( n^{2}-n) element will form (n^{2}-n)/2  pair and each pair have two choices: Either they can participate in the realation or not. 

So the total number of relations that are Both Symmetric and Reflexive is   {\color{Red} 2^{(n^{2}-n)/2}}

Please refer to these links: 

https://www.techtud.com/short-notes/couting-relations

https://www.techtud.com/short-notes/non-diagonal-pair-and-couting-relations2

 

Solutions 4:-

False, An element of a set can't be the subset of that element : 

A subset is set itself but an element is not set. Example:

A={1,2,3}

The question is asking whether 1 is a subset of A. No because 1 is just element but {1} is a set and hence subset of A.

Please refer to this example for more clarification.

https://www.techtud.com/example-tbd/gate-2015-power-set

 

Solution 5:

Asymmetric relations are stricter than Antisymmetric. Think Why??

Because in Antisymmetric we are allowing diagonal element (elements of type:  (1,1) , (2,2,).....(n,n)) but in Asymmetric, even diagonal elements are not allowed.

So diagonal element has only one choice they must not present.  

Remaining {\color{Red} n^{2}-n} form   ({\color{Red} n^{2}-n} ){\color{Red} /2} pair and each pair have three choices:

choice 1:  pair is not present in the relation.

choice 2:  if (a,b) is present then (b,a) is absent.

choice 3:  if (b,a) is present then (a,b) is absent 

So the total  number of relations that are both Asymmetric and  Antisymmetric is : 3^{({\color{Red} n^{2}-n} ){\color{Red} /2}} 

 

If a relation is Asymmetric it is definitely Antisymmnetic but the reverse is not true. You tell me the reason in Comment Box.

 

0Comment
Gate-2015 Power set

Example:1

If the power set of A is denoted as P(A) and A = \left\{5,\left\{6\right\}, \left\{7\right\}\right\}  Which of the following options are true?

A.    \phi \in 2^{A}

B.    \phi \subseteq 2^{A}

C.    \left\{5,\left\{6\right\}\right\} \in 2^{A}

D.    \left\{5,\left\{6\right\}\right\} \subseteq 2^{A} 

 

  1. A and C only
  2. B and C only
  3. A , B and C only
  4. A, B and D only

 

Solutions:-

 

 A = \left\{5,\left\{6\right\}, \left\{7\right\}\right\}

P(A) = { ϕ ,  {5} ,   {{6}}    ,  {{7}}  ,  {5, {6}}  ,  {5, {7}}   ,  { {6} , {7} } , {5, {6} , {7}} }

Clearly \phi \in 2^{A} and  \phi \subseteq 2^{A} But  

\left\{5,\left\{6\right\}\right\} \in 2^{A} means the elements { 5, {6}} belongs  to P(A)  

\left\{5,\left\{6\right\}\right\} \subseteq 2^{A} means the elements  { 5, {6}}  is subest of P(A)  which is wrong . Think why??

Because an element of a set can't be the subset of a set.  Instead of { 5, {6}}  if { { 5, {6}} } was given then that could be correct.

Example:

A={1,2,3} 

1 can't be a subset of A but {1} is a subset of A. Before a  set s' become a subset of some set S, s' should be a set first.

 

So only A, B, C are correct.

 

 

0Comment

  • This quiz contains 5 questions on the topic Set Theory , Relation and Function Quiz
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate