Partially Ordered Set (Poset) & Totally Ordered Set
🔍 Introduction (परिचय):
Relations के विशेष प्रकार जो किसी क्रम (order) को दर्शाते हैं — उन्हें Ordered Relations कहा जाता है।
जब हम किसी set के elements के बीच “less than”, “subset of”, “divides” जैसे आदेशों की बात करते हैं, तब हम एक partially ordered set या totally ordered set की बात कर रहे होते हैं।
🧱 1. Partially Ordered Set (Poset)
📚 Definition:
Let A be a non-empty set and R be a relation on A.
If R is:
- Reflexive: aRa
- Antisymmetric: aRb and bRa ⇒ a=b
- Transitive: aRb and bRc ⇒ aRc
Then (A,R) is called a Partially Ordered Set (Poset).
🧠 Example 1:
Let A={1,2,3,4}
Define R={(a,b):a divides b}
तो,
- 1 ∣ 1,2 ∣ 4 etc
- Relation is reflexive (every number divides itself),
- antisymmetric (if a divides b and b divides a ⇒ a = b),
- transitive (a divides b, b divides c ⇒ a divides c)
✅ Hence, (A,R) is a poset.
🧱 Hasse Diagram (हासे आरेख):
Poset को draw करने का आसान तरीका — जिसमें हम सिर्फ उन elements को connect करते हैं जिनके बीच direct relation हो और जो transitivity से न निकले हों।
🧠 Example for set {1, 2, 4, 8} under “divides” relation:
8
|
4
|
2
|
1
🔝 2. Totally Ordered Set (Chain)
📚 Definition:
A poset (A,R) is called a Totally Ordered Set if every pair of elements is comparable,
i.e., for all a,b∈A either aRb
📌 इसे linear order या chain भी कहा जाता है।
🧠 Example 2:
Let A={1,2,3}and relation R=≤
- हर जोड़ी: 1 ≤ 2, 2 ≤ 3, 1 ≤ 3
✅ सभी elements आपस में comparable हैं
⇒ ये एक Totally Ordered Set है।
❌ Note:
हर totally ordered set एक poset होता है,
लेकिन हर poset necessarily totally ordered नहीं होता।
📊 Comparison Table:
| Feature | Poset | Totally Ordered Set |
|---|---|---|
| Reflexive | ✔️ | ✔️ |
| Antisymmetric | ✔️ | ✔️ |
| Transitive | ✔️ | ✔️ |
| All pairs comparable | ❌ Not necessary | ✔️ Required |
🎯 Objectives Recap:
- Ordered relations को समझना
- Poset की तीन properties: Reflexive, Antisymmetric, Transitive
- Hasse diagram बनाना सीखना
- Totally ordered set (Chain) और poset में अंतर जानना
📝 Exercise (अभ्यास प्रश्न):
📌 Short Answer Questions:
- Define Poset with an example.
- What are the three conditions for a poset?
- What is a Hasse diagram?
📌 Long Answer / Numerical Questions:
- Let A = {1, 2, 4, 8} and define R = divides
a. Show that R is a poset
b. Draw the Hasse diagram - Let A = {a, b, c} and define R = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)}
a. Is R a totally ordered set?
b. Justify each property (reflexive, antisymmetric, transitive) - Prove that a totally ordered set is always a poset but not vice versa.