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

Source: https://skills101.in/learn/discrete-math/sets-relations-functions — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

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}`.

| Operation | Symbol | Meaning |
|---|---|---|
| Union | A ∪ B | in A **or** B |
| Intersection | A ∩ B | in A **and** B |
| Difference | A − B | in A but not B |
| Symmetric difference | A ⊕ B | in exactly one of them |
| Complement | A′ | everything (in the universe U) not in A |
| Subset | A ⊆ B | every element of A is in B |

![Venn diagrams for two sets A and B showing union (both circles shaded), intersection (overlap only), difference A minus B (left part only) and symmetric difference (both outer parts, not the overlap)](https://skills101.in/learn-img/discrete-math/venn.svg)

Python's `set` type implements all of these directly:

```python
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)
```

```text
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|.

```python
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], "...")
```

```text
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)}.

| Property | Meaning | "divides" on {1,2,3}? |
|---|---|---|
| **Reflexive** | (a, a) ∈ R for every a | yes |
| **Symmetric** | (a, b) ∈ R ⇒ (b, a) ∈ R | no — 1 divides 2, 2 doesn't divide 1 |
| **Antisymmetric** | (a, b) and (b, a) ∈ R ⇒ a = b | yes |
| **Transitive** | (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R | yes |

- **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", "≤", "⊆".

![A relation drawn as a directed graph: arrows between elements; a self-loop on every node means reflexive, arrows in both directions mean symmetric, and a shortcut arrow for every two-step path means transitive](https://skills101.in/learn-img/discrete-math/relation-graph.svg)

Let's write property checkers and test two relations:

```python
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))
```

```text
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.

| Type | Meaning | Example (on integers) |
|---|---|---|
| **One-one (injective)** | different inputs → different outputs | f(x) = 2x |
| **Onto (surjective)** | every element of B is hit | f(x) = x − 1 |
| **Bijective** | both — so it has an inverse | f(x) = x + 5 |

![Function types as arrow diagrams: one-one where no two arrows meet at the same output, onto where every output receives an arrow, and bijective where both hold, pairing inputs and outputs perfectly](https://skills101.in/learn-img/discrete-math/function-types.svg)

```python
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)))
```

```text
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).


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/sets-relations-functions