Part 05- Discrete Mathematics for computer science- Anti Symmetric Relation with core Cocept
Part 05- Discrete Mathematics for computer science- Anti Symmetric Relation with core Cocept
Here is Part 05 of Discrete Mathematics for Computer Science, focused on the Anti-Symmetric Relation, explained with core concepts, examples, and logic — especially useful for GATE, CS/IT, and university-level understanding.
Contents
🧠 What is an Anti-Symmetric Relation?
A binary relation RR on a set AA is said to be anti-symmetric if:
If (a,b)∈R and (b,a)∈R, then a=b\text{If } (a, b) \in R \text{ and } (b, a) \in R, \text{ then } a = b
In simple terms:
👉 If both aa is related to bb and bb is related to aa**, then they must be the same element.
📘 Formal Definition
Let AA be a set and R⊆A×AR \subseteq A \times A.
RR is anti-symmetric if:
∀a,b∈A, (a,b)∈R∧(b,a)∈R⇒a=b\forall a, b \in A, \ (a, b) \in R \land (b, a) \in R \Rightarrow a = b
🔍 Key Concept:
-
Anti-symmetric does not mean symmetric = false.
-
It is allowed to have both (a,b)(a,b) and (b,a)(b,a) only when a=ba = b.
-
Reflexive elements like (a,a)(a,a) are fine.
✅ Examples of Anti-Symmetric Relations
🔹 Example 1: “Less than or equal to” (≤) on real numbers
If a≤ba \leq b and b≤ab \leq a, then a=ba = b
→ ✅ Anti-symmetric
🔹 Example 2: Subset relation (⊆) on sets
If A⊆BA \subseteq B and B⊆AB \subseteq A, then A=BA = B
→ ✅ Anti-symmetric
🔹 Example 3: Divisibility Relation on Natural Numbers
Let aRb ⟺ a∣baRb \iff a \mid b (a divides b)
If a∣ba \mid b and b∣ab \mid a, then a=ba = b
→ ✅ Anti-symmetric
❌ Non-Anti-Symmetric Example
🔹 Let A={1,2}A = \{1, 2\}, and R={(1,2),(2,1)}R = \{(1,2), (2,1)\}
Here, both (1,2)(1,2) and (2,1)(2,1) exist but 1≠21 \ne 2
→ ❌ Not anti-symmetric
📊 Summary Table of Relations
Relation Property | Reflexive | Symmetric | Anti-symmetric | Transitive |
---|---|---|---|---|
== (Equality) | ✅ | ✅ | ✅ | ✅ |
≤\leq | ✅ | ❌ | ✅ | ✅ |
Subset (⊆) | ✅ | ❌ | ✅ | ✅ |
“Friend of” Relation | ✅ (maybe) | ✅ | ❌ | ❌ |
🔄 Quick Check: How to Test Anti-Symmetry
Given relation RR on set AA:
-
List all pairs (a,b) in RR
-
For each pair, check if (b,a) also exists.
-
If yes, then ensure a=ba = b. If even one pair violates this, it’s not anti-symmetric.
🎯 Key Takeaways:
-
Anti-symmetric ≠ Not symmetric
-
Reflexive relations can be anti-symmetric.
-
Useful in partial orders, posets, and hierarchical data.
Would you like practice questions (MCQs or reasoning-based) on anti-symmetric relations for GATE or university exams?