Sets, Relations and Functions — Operations, Properties, Equivalence Relations and Bijections

Databases are built on sets, social networks on relations, hash tables on functions. This lesson gives you the vocabulary every later topic — and many interview and GATE questions — uses.

1. Sets

A set is an unordered collection of distinct elements: A = {1, 2, 3}. Order doesn't matter and duplicates don't count: {1, 2, 2} = {2, 1}.

Python's set type implements all of these directly:

python_students = {"Asha", "Ravi", "Meera", "Kabir"}
java_students = {"Ravi", "Kabir", "Zoya"}

print("both courses      :", sorted(python_students & java_students))
print("either course     :", sorted(python_students | java_students))
print("only Python       :", sorted(python_students - java_students))
print("exactly one course:", sorted(python_students ^ java_students))
print("is {'Ravi'} a subset of Java?", {"Ravi"} <= java_students)

both courses      : ['Kabir', 'Ravi']
either course     : ['Asha', 'Kabir', 'Meera', 'Ravi', 'Zoya']
only Python       : ['Asha', 'Meera']
exactly one course: ['Asha', 'Meera', 'Zoya']
is {'Ravi'} a subset of Java? True

Inclusion–exclusion (two sets): |A ∪ B| = |A| + |B| − |A ∩ B| → 4 + 3 − 2 = 5. ✓

2. Power set and Cartesian product

• Power set P(A) = the set of all subsets of A. If |A| = n, then |P(A)| = 2ⁿ (each element is either in or out).
• Cartesian product A × B = all ordered pairs (a, b). |A × B| = |A| · |B|.

from itertools import chain, combinations, product

A = {1, 2, 3}
power = list(chain.from_iterable(combinations(sorted(A), r) for r in range(len(A) + 1)))
print("P(A) has", len(power), "subsets:", power)

sizes = ["S", "M"]
colours = ["red", "blue", "black"]
print("T-shirt variants:", len(list(product(sizes, colours))), list(product(sizes, colours))[:3], "...")

P(A) has 8 subsets: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
T-shirt variants: 6 [('S', 'red'), ('S', 'blue'), ('S', 'black')] ...

3. Relations

A relation R from A to B is any subset of A × B. A relation on a set A is a subset of A × A. Example on A = {1, 2, 3}: "a divides b" = {(1,1), (1,2), (1,3), (2,2), (3,3)}.

• Equivalence relation = reflexive + symmetric + transitive. It splits the set into equivalence classes (a partition). Example: "same remainder mod 3".
• Partial order = reflexive + antisymmetric + transitive (lesson 8). Example: "divides", "≤", "⊆".

Let's write property checkers and test two relations:

def props(R, A):
    reflexive = all((a, a) in R for a in A)
    symmetric = all((b, a) in R for (a, b) in R)
    antisymmetric = all(a == b for (a, b) in R if (b, a) in R)
    transitive = all((a, d) in R for (a, b) in R for (c, d) in R if b == c)
    return dict(reflexive=reflexive, symmetric=symmetric, antisymmetric=antisymmetric, transitive=transitive)

A = {1, 2, 3, 4, 5, 6}
divides = {(a, b) for a in A for b in A if b % a == 0}
same_mod3 = {(a, b) for a in A for b in A if a % 3 == b % 3}

print("divides  :", props(divides, A))
print("same mod3:", props(same_mod3, A))
classes = {frozenset(b for b in A if (a, b) in same_mod3) for a in A}
print("equivalence classes of mod 3:", sorted(sorted(c) for c in classes))

divides  : {'reflexive': True, 'symmetric': False, 'antisymmetric': True, 'transitive': True}
same mod3: {'reflexive': True, 'symmetric': True, 'antisymmetric': False, 'transitive': True}
equivalence classes of mod 3: [[1, 4], [2, 5], [3, 6]]

Counting relations (exam favourite): on a set with n elements there are 2^(n²) relations, 2^(n² − n) reflexive ones, and 2^(n(n+1)/2) symmetric ones.

4. Functions

A function f: A → B assigns exactly one output in B to every input in A.

def classify(f, A, B):
    images = [f(a) for a in A]
    one_one = len(set(images)) == len(images)
    onto = set(images) == set(B)
    return f"one-one={one_one}, onto={onto}, bijective={one_one and onto}"

A = [0, 1, 2, 3]
print("x mod 2 -> {0,1}      :", classify(lambda x: x % 2, A, [0, 1]))
print("2x -> {0..6}          :", classify(lambda x: 2 * x, A, range(7)))
print("(x+1) mod 4 -> {0..3} :", classify(lambda x: (x + 1) % 4, A, range(4)))

x mod 2 -> {0,1}      : one-one=False, onto=True, bijective=False
2x -> {0..6}          : one-one=True, onto=False, bijective=False
(x+1) mod 4 -> {0..3} : one-one=True, onto=True, bijective=True

Where this matters in code: a hash function is (usually) not one-one — collisions happen; an encryption function must be a bijection, or you couldn't decrypt.

Counting functions from a set of size m to a set of size n: nᵐ functions in total; n!/(n − m)! one-one functions (if m ≤ n).

Common mistakes

• Treating sets as ordered or allowing duplicates.
• Forgetting the empty set and the set itself in a power set.
• Checking symmetric/transitive with only a few pairs — the property must hold for all pairs.
• Calling a relation "antisymmetric" means "not symmetric" — they're different (a relation can be both or neither).

Quick recap

• Sets: ∪, ∩, −, ⊕, complement; |A ∪ B| = |A| + |B| − |A ∩ B|; |P(A)| = 2ⁿ; |A × B| = |A||B|.
• Relation properties: reflexive, symmetric, antisymmetric, transitive.
• Equivalence = R + S + T (partitions into classes); partial order = R + AS + T.
• Functions: one-one, onto, bijective (invertible).