Here is a clear, complete, exam-oriented explanation of the Properties of Relations and Functions in Discrete Structures.
Everything is explained step-by-step with examples so you can write it easily in exams.
⭐ PART–A: Properties of Relations
Let ( R \subseteq A \times A ) be a relation on a set A.
There are 6 main properties of relations.
1️⃣ Reflexive Relation
A relation (R) on set (A) is reflexive if:
[
(a, a) \in R \quad \forall a \in A
]
Every element must be related to itself.
Example
A = {1,2,3}
R = {(1,1),(2,2),(3,3),(1,2)} → Reflexive
Not Reflexive
Missing (3,3) etc.
2️⃣ Irreflexive Relation
No element is related to itself.
[
(a, a) \notin R \quad \forall a \in A
]
Example
R = {(1,2),(2,3)} → Irreflexive
3️⃣ Symmetric Relation
A relation (R) is symmetric if:
[
(a,b) \in R \Rightarrow (b,a) \in R
]
Example
R = {(1,2), (2,1), (3,3)} → Symmetric
4️⃣ Asymmetric Relation
If:
[
(a,b) \in R \Rightarrow (b,a) \notin R
]
AND
[
(a,a) \notin R
]
Example
R = {(1,2),(2,3)} → Asymmetric
5️⃣ Antisymmetric Relation
If:
[
(a,b) \in R \land (b,a) \in R \Rightarrow a = b
]
Example
R = {(1,1),(2,2),(1,2)} → Antisymmetric
Not antisymmetric if both (a,b) and (b,a) exist with a ≠ b.
6️⃣ Transitive Relation
A relation (R) is transitive if:
[
(a,b) \in R \land (b,c) \in R \Rightarrow (a,c) \in R
]
Example
R = {(1,2), (2,3), (1,3)} → Transitive
⭐ Special Types of Relations
✔ Equivalence Relation
A relation is equivalence if it is:
- Reflexive
- Symmetric
- Transitive
Example:
“has same remainder mod 3” → Equivalence relation.
✔ Partial Order Relation
A relation is partial order if it is:
- Reflexive
- Antisymmetric
- Transitive
Example: ≤ on integers.
⭐ PART–B: Properties of Functions
A function is a special type of relation where:
- Every element of the domain must be mapped
- No element of the domain has more than one image
Formally:
[
f : A \to B
]
1️⃣ One–One Function (Injective)
A function (f) is one–one if:
[
f(a_1) = f(a_2) \Rightarrow a_1 = a_2
]
No two different elements of domain map to the same element of codomain.
Example
f(x) = x + 1 → One–one
Non-injective
f(x) = x² (because f(2)=f(-2))
2️⃣ Onto Function (Surjective)
A function is onto if:
Every element of codomain has at least one preimage.
[
\text{Range} = \text{Codomain}
]
Example
f : {1,2,3} → {a,b,c}
f(1)=a, f(2)=b, f(3)=c → Onto
3️⃣ One–One Onto (Bijective)
Function is both injective and surjective.
It creates a perfect pairing between A and B.
Example
f(x) = x → Bijective
4️⃣ Into Function
Not every element of codomain is mapped.
Example
A={1,2,3}, B={a,b,c,d}
Mapping covers only a,b,c → Into
5️⃣ Many–One Function
Two or more different domain elements map to the same codomain element.
Example
f : {1,2,3} → {a,b}
f(1)=a, f(2)=a, f(3)=b → Many-one
6️⃣ Constant Function
All domain elements map to the same codomain element.
⭐ Summary Table for Relations
| Property | Meaning |
|---|---|
| Reflexive | (a,a) in R |
| Irreflexive | no (a,a) in R |
| Symmetric | (a,b) ⇒ (b,a) |
| Asymmetric | (a,b) ⇒ not (b,a) |
| Antisymmetric | both ⇒ a=b |
| Transitive | (a,b),(b,c) ⇒ (a,c) |
⭐ Summary Table for Functions
| Function Type | Meaning |
|---|---|
| One–One | No repetition in range |
| Onto | Range = Codomain |
| Bijective | One–one + Onto |
| Into | Range ⊂ Codomain |
| Many–One | Different A map to same B |