Day 02- Discrete mathematics for computer science gate-Ir-reflexive Relation with basic understanding
Day 02- Discrete mathematics for computer science gate-Ir-reflexive Relation with basic understanding
Contents
- 1 Day 02: Discrete Mathematics for Computer Science (GATE) – Irreflexive Relation with Basic Understanding
- 2 What is an Irreflexive Relation?
- 3 Difference Between Reflexive and Irreflexive Relations
- 4 Special Cases:
- 5 Importance of Irreflexive Relations in Computer Science
- 6 Day 02- Discrete mathematics for computer science gate-Ir-reflexive Relation with basic understanding
- 7 Notes on Discrete Mathematics
Day 02: Discrete Mathematics for Computer Science (GATE) – Irreflexive Relation with Basic Understanding
What is a Relation in Discrete Mathematics?
In Discrete Mathematics, a relation is a set of ordered pairs that define a connection between elements of two sets. If a relation is defined on a single set, it is called a binary relation.
What is an Irreflexive Relation?
A relation R on a set A is called irreflexive if no element in the set is related to itself. That is, for every element aa in AA:
(a,a)∉R(a, a) \notin R
This means that self-loops are not allowed in an irreflexive relation.
Example:
Let A = {1, 2, 3} and let R be a relation on A:
R={(1,2),(2,3),(3,1)}R = \{(1,2), (2,3), (3,1)\}
Since (1,1), (2,2), and (3,3) are NOT present in R, the relation is irreflexive.
Difference Between Reflexive and Irreflexive Relations
| Property | Reflexive Relation | Irreflexive Relation |
|---|---|---|
| Definition | Every element relates to itself | No element relates to itself |
| Condition | (a,a)∈R(a, a) \in R for all a∈Aa \in A | (a,a)∉R(a, a) \notin R for all a∈Aa \in A |
| Example | R={(1,1),(2,2),(3,3),(1,2)}R = \{(1,1), (2,2), (3,3), (1,2)\} | R={(1,2),(2,3),(3,1)}R = \{(1,2), (2,3), (3,1)\} |
Special Cases:
A relation can be neither reflexive nor irreflexive if some but not all elements relate to themselves.
An empty relation is always irreflexive because it contains no pairs at all.
Importance of Irreflexive Relations in Computer Science
Used in graph theory for modeling directed graphs without self-loops.
Important in order relations like strict partial order and strict preference relations.
Helps in programming languages & automata theory for defining transitions without self-loops.
Would you like practice problems or more examples?