Discrete Structure Unit 1
Set Theory, Relation, Function & Proof Techniques

1. Set Theory

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

• Elements are written inside curly brackets.
• Duplicate elements are not allowed.
• Order of elements does not matter.
• {1,2,3} and {3,2,1} are equal sets.

2. Types of Sets

• Empty Set: A set having no element. Symbol: ∅ or { }.
• Finite Set: A set containing limited elements.
• Infinite Set: A set having unlimited elements. Example: N = {1,2,3,...}
• Equal Sets: Two sets having same elements.
• Subset: If every element of A is also in B, then A ⊆ B.

3. Set Operations

• Union: All elements from both sets. Symbol: A ∪ B.
• Intersection: Common elements. Symbol: A ∩ B.
• Difference: Elements in A but not in B. Symbol: A - B.
• Complement: Elements not present in given set. Symbol: A′.

4. Important Set Identities

• Commutative Law: A ∪ B = B ∪ A and A ∩ B = B ∩ A
• Associative Law: (A ∪ B) ∪ C = A ∪ (B ∪ C)
• Distributive Law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• De Morgan’s Law: (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′

5. Venn Diagram

A Venn diagram is a pictorial representation of sets. It is used to show union, intersection, difference and complement of sets.

• Useful in survey-based numerical problems.
• Helps in visualizing relationship between sets.
• Frequently asked in RGPV exams.

6. Countable and Uncountable Sets

Countable Set: A set whose elements can be counted or listed in a sequence.

Uncountable Set: A set whose elements cannot be listed completely.

• Natural numbers are countable.
• Integers are countable.
• Rational numbers are countable.
• Real numbers are uncountable.

7. Relation

A relation from set A to set B is a subset of Cartesian product A × B.

A relation may contain some or all ordered pairs from Cartesian product.

8. Properties of Relation

• Reflexive: aRa for every a ∈ A.
• Symmetric: If aRb, then bRa.
• Transitive: If aRb and bRc, then aRc.
• Antisymmetric: If aRb and bRa, then a = b.

9. Equivalence Relation

A relation is called an equivalence relation if it is:

• Reflexive
• Symmetric
• Transitive

Equivalence relation is the most repeated topic of Unit 1 in PYQs.

10. Equivalence Class

If R is an equivalence relation on set A, then equivalence class of element a is:

Example: If relation is defined by same remainder when divided by 2, then odd numbers form one class and even numbers form another class.

11. Function

A function is a special type of relation in which every element of domain is related to exactly one element of codomain.

• One-One Function: Different elements have different images.
• Onto Function: Every element of codomain has pre-image.
• Bijective Function: Function which is both one-one and onto.
• Inverse Function: Exists only when function is bijective.

12. Mathematical Induction

Mathematical induction is a proof technique used to prove statements for all natural numbers.

Steps:

1. Base Step: Prove statement for n = 1.
2. Induction Hypothesis: Assume true for n = k.
3. Induction Step: Prove true for n = k + 1.

13. Pigeonhole Principle

If n+1 objects are placed into n boxes, then at least one box contains more than one object.

This topic is very important for short proof questions.

1. Define equivalence relation and prove relation a + d = b + c is an equivalence relation.
2. Explain equivalence classes with suitable example.
3. Prove 1 + 2 + 3 + ... + n = n(n+1)/2 using mathematical induction.
4. Prove 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.
5. Define countable and uncountable sets. Prove rational numbers are countable.
6. Explain one-one, onto and bijective functions with examples.
7. Prove that inverse of a function exists iff function is bijective.
8. State and prove Pigeonhole Principle with example.
9. Explain Venn diagram with set operations.
10. Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Most Repeated Topics

Most Expected Questions

• Check whether given relation is equivalence relation and find equivalence classes.
• Prove relation is equivalence relation.
• Mathematical induction proof questions.
• Survey-based Venn diagram numerical problems.
• One-one, onto and bijective function based questions.
• State and prove Pigeonhole Principle.
• Prove rational numbers are countable.

• First prepare Equivalence Relation because it is the most repeated topic.
• Practice Mathematical Induction formulas for 7-mark questions.
• Prepare Venn Diagram numerical problems because they are scoring.
• Do not skip Functions, especially one-one, onto, bijective and inverse function.
• Prepare Pigeonhole Principle for short proof questions.