✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS (DISCRETE MATHEMATICS)

 

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS

A. Relations

Definition

A relation R from A to B is a subset of A×B.

Representation

• List of ordered pairs

• Matrix representation

• Directed graph

Operations

• Union

• Intersection

• Composition (R ∘ S)

• Inverse relation (R⁻¹)

Types of Relations

1. Reflexive: (a,a) ∈ R for all a

2. Symmetric: (a,b) ⇒ (b,a)

3. Transitive: (a,b) & (b,c) ⇒ (a,c)

4. Anti-symmetric

---

Counting Relations

If A has n elements:

Total possible relations =

$$2^{n^2}$$

---

Closure of Relations

• Reflexive closure = R ∪ {(a,a)}

• Symmetric closure = R ∪ R⁻¹

• Transitive closure = Add pairs until transitivity satisfied (Warshall)

---

Equivalence Relation

When R is:

• Reflexive

• Symmetric

• Transitive

Then A is partitioned into equivalence classes.

---

Partial Order Relation

R is:

• Reflexive

• Anti-symmetric

• Transitive

Forms a poset.

---

Power of a Relation

Rⁿ = R composed with itself n times.

---

Functions

Definition

A function f: A → B assigns each element in A to exactly one element in B.

Terms

• Domain

• Co-domain

• Range

Types

• One-one (Injective)

• Onto (Surjective)

• Bijective

• Constant

• Identity function

---

Counting Functions

From set A (m elements) to B (n elements):

$$n^m \text{ functions}$$

---

Inverse Function

Exists only for bijective functions.

---

Composition

If f: A→B and g: B→C
Then g∘f: A→C.

---

Group Theory (Basics)

A set G with binary operation * is a group if:

1. Closure

2. Associativity

3. Identity element

4. Inverse exists for all elements

If operation is commutative → Abelian group.