ProTeacher

Tag: Equivalence Relations

  • UGC NET Computer Science Unit 1 – Sets & Relations

    UNIT–1 (SETS & RELATIONS)

    (Set Operations, Representation of Relations, Properties of Relations, Equivalence & Partial Order Relations)

    PART A — SETS

    1. What is a Set? (Definition)

    A set is a well-defined collection of objects (called elements) such that it is possible to clearly decide whether an element belongs to the set or not.

    Key idea:
    ✔ “Well-defined” means no ambiguity.
    ✔ Sets are written using curly braces.

    Examples:

    • A = {1,2,3,4}

    • B = {a, e, i, o, u}

    • C = {x | x is an even natural number}

    Non-example:

    • “All beautiful flowers” → not well-defined (beauty is subjective)

    2. Important Types of Sets

    2.1 Empty set (Null set)

    A set with no elements.
    Symbol: Ø or { }
    Example: Set of even prime numbers > 2.

    2.2 Finite and Infinite sets

    • Finite: elements can be counted

    • Infinite: unending, e.g., natural numbers ℕ

    2.3 Equal sets

    Two sets A and B are equal if every element of A is in B and vice-versa.

    2.4 Subset

    A ⊆ B means every element of A is also in B.

    Example:
    A = {1,2}
    B = {1,2,3,4}
    → A ⊆ B

    Proper subset:
    A ⊂ B if A ⊆ B and A ≠ B.

    2.5 Power Set

    P(A) = set of all subsets of A.
    If |A| = n → |P(A)| = 2ⁿ.

    Example:
    A = {1,2}
    P(A) = { Ø, {1}, {2}, {1,2} }

    3. SET OPERATIONS

    Operations on sets are exactly parallel to logical operations.

    Let A and B be sets in a universal set U.

    3.1 Union (A ∪ B)

    Statement: Set of all elements that belong to A, or to B, or to both.

    Example:
    A={1,2}, B={2,3}
    A∪B = {1,2,3}

    3.2 Intersection (A ∩ B)

    Statement: Elements common to both A and B.

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

    3.3 Difference (A – B)

    Statement: Elements belonging to A but not in B.

    A − B = {elements in A that are not in B}

    Example:
    A={1,2,3}, B={2,4}
    A−B={1,3}

    3.4 Symmetric Difference (A Δ B)

    Statement: Elements that are in A or in B but NOT in both.
    AΔB = (A−B) ∪ (B−A)

    Example:
    A={1,2,3}, B={3,4,5}
    AΔB = {1,2,4,5}

    3.5 Complement (A′)

    Everything in the universal set U that is NOT in A.

    A′ = U − A

    4. IMPORTANT SET IDENTITIES

    These laws are vital for proofs and simplifications.

    Identity Laws

    • A ∪ Ø = A
      → “Adding nothing changes the set.”

    • A ∩ U = A
      → “Intersecting with everything gives the set.”

    Domination Laws

    • A ∪ U = U

    • A ∩ Ø = Ø

    Statement:
    “Union with universal set gives universal set; intersection with empty set gives empty set.”

    Idempotent Laws

    • A ∪ A = A

    • A ∩ A = A

    Commutative Laws

    • A ∪ B = B ∪ A

    • A ∩ B = B ∩ A

    Associative Laws

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

    • (A ∩ B) ∩ C = A ∩ (B ∩ C)

    Distributive Laws

    • A ∩ (B ∪ C) = (A∩B) ∪ (A∩C)

    • A ∪ (B ∩ C) = (A∪B) ∪ (A∪C)

    Absorption Laws

    • A ∪ (A ∩ B) = A

    • A ∩ (A ∪ B) = A

    De Morgan’s Laws

    • (A ∪ B)′ = A′ ∩ B′

    • (A ∩ B)′ = A′ ∪ B′

    These correspond to logical laws for (∨, ∧, ¬).

    PART B — RELATIONS

    Relations form the mathematical structure for describing connections between objects.
    They generalize functions, orders, equivalence, graph relations, database relations, etc.

    5. RELATION — DEFINITION

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

    That is:
    R ⊆ A × B

    Where A × B = {(a,b) | a ∈ A, b ∈ B}

    5.1 Binary Relation on a Set

    A relation R on A is a subset of A × A.

    Example:
    A={1,2,3}
    R = {(1,1),(2,2),(1,3)} is a relation on A.

    6. REPRESENTATION OF RELATIONS

    A relation can be represented in three ways:

    6.1 (a) Set of Ordered Pairs

    Direct listing of (a,b).

    Example:
    R = {(1,2),(2,3),(3,1)}

    6.1 (b) Matrix Representation

    If A = {a₁,a₂,…,aₙ}, R is represented by an n×n matrix M:

    mij={1if (ai,aj)∈R0otherwise

    Used heavily in computing and adjacency matrices.

    6.1 (c) Directed Graph (Digraph)

    • Each element of A is a node.

    • Each pair (a,b) ∈ R is a directed edge from a→b.

    Graphical representation helps visualize transitivity, symmetry, closure, etc.

    7. PROPERTIES OF RELATIONS

    These properties define the nature of the relationship.

    Let R be a relation on set A.

    7.1 Reflexive Relation

    Definition (Statement):

    A relation R on A is reflexive if every element relates to itself.

    (a,a)∈R for every a∈A

    Example:
    A = {1,2,3}
    R = {(1,1),(2,2),(3,3),(1,2)} → reflexive

    Non-example:
    Missing even one (a,a) → not reflexive.

    7.2 Symmetric Relation

    Definition (Statement):

    A relation R is symmetric if:

    If (a,b) ∈ R then (b,a) ∈ R.

    Example (symmetric):
    R = {(1,2),(2,1),(2,3),(3,2)}

    Non-example:
    If (1,2) ∈ R but (2,1) ∉ R → not symmetric.

    7.3 Antisymmetric Relation

    Definition (Statement):

    A relation R is antisymmetric if:

    If (a,b) ∈ R and (b,a) ∈ R, then a = b.

    Example (antisymmetric):
    Set A = {1,2,3}
    Relation: “≤”
    Because if a ≤ b and b ≤ a → a = b.

    Non-example:
    (1,2) and (2,1) in R with 1≠2 → violates antisymmetry.

    7.4 Transitive Relation

    Definition (Statement):

    A relation R is transitive if:

    If (a,b) and (b,c) ∈ R → (a,c) must also be in R.

    Example:
    If a divides b and b divides c → a divides c.

    Non-example:
    If (a,b),(b,c) ∈ R but (a,c) ∉ R.

    8. COMBINED RELATIONS — IMPORTANT TYPES

    8.1 Equivalence Relation (VERY IMPORTANT)

    Definition (Statement):

    A relation R on A is an equivalence relation if it is:

    1. Reflexive

    2. Symmetric

    3. Transitive

    Meaning:
    An equivalence relation groups elements into “categories” or “classes” of items that are considered equivalent.

    Equivalence Class

    For element a ∈ A, the equivalence class is:

    [a]={x∈A∣(a,x)∈R}

    Meaning:
    “All elements related to a.”

    Example: Congruence modulo n

    Define relation:
    a ≡ b (mod n)
    Meaning: “a and b leave same remainder when divided by n.”

    Properties:
    ✔ reflexive: a≡a
    ✔ symmetric: if a≡b then b≡a
    ✔ transitive: if a≡b and b≡c then a≡c

    → So it’s an equivalence relation.

    Each equivalence class contains all numbers with same remainder.

    8.2 Partition of a Set

    Equivalence relations partition a set into disjoint subsets (equivalence classes).

    Properties of partition:

    1. Classes are nonempty

    2. Classes are disjoint

    3. Union of all classes = A

    Equivalence relations ↔ partitions.

    These two concepts are dual to each other.

    9. PARTIAL ORDER RELATIONS (POSets)

    These describe ordered or hierarchical structure.

    9.1 Partial Order Relation

    Definition (Statement):

    A relation R on A is a partial order if it is:

    1. Reflexive

    2. Antisymmetric

    3. Transitive

    Symbol: (A, ≤) is a poset (partially ordered set).

    Example:

    • “Divides” relation on {1,2,4,8}

    • “Subset (⊆)” relation on P(S)

    9.2 Total (Linear) Order

    A partial order is total if every pair of elements is comparable.

    That is, for any a and b:
    Either a ≤ b or b ≤ a.

    Example (total order):

    • Natural numbers with ≤

    • Alphabet with alphabetical order

    Non-example:
    Subset relation is not total.

    9.3 Hasse Diagrams (Poset Representation)

    Used to represent partial orders graphically:

    Rules:

    • Draw elements as nodes

    • Draw edge upward if a < b and there is no c such that a < c < b

    • Omit loops and transitive edges

    10. Reflexive–Symmetric–Transitive Closures (Advanced but important)

    Sometimes a relation R does not have a property, and we want the smallest relation that includes R and satisfies the property.

    Reflexive closure:

    Add (a,a) for all a ∈ A missing from R.

    Symmetric closure:

    Add (b,a) if (a,b) is in R but (b,a) missing.

    Transitive closure:

    Add (a,c) whenever (a,b) and (b,c) exist.

    Used in database theory (Warshall’s algorithm), graph theory, and automata.