ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್‌ಗಳು (Equivalence Relations) ಮತ್ತು ಪಾರ್ಶಿಯಲ್ ಆರ್ಡರಿಂಗ್ (Partial Ordering) | Equivalence Relations and Partial Ordering
In the syllabus of UGC NET CS
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due
Key points
- ಈಕ್ವಿವಲೆನ್ಸ್: ರಿಫ್ಲೆಕ್ಸಿವ್ + ಸಿಮೆಟ್ರಿಕ್ + ಟ್ರಾನ್ಸಿಟಿವ್; ಪಾರ್ಶಿಯಲ್ ಆರ್ಡರ್: ರಿಫ್ಲೆಕ್ಸಿವ್ + ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ + ಟ್ರಾನ್ಸಿಟಿವ್. | Equivalence: reflexive + symmetric + transitive; partial order: reflexive + antisymmetric + transitive.
- ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್‌ಗಳ ಸಂಖ್ಯೆ ಬೆಲ್ ಸಂಖ್ಯೆ: 1, 2, 5, 15, 52. | The number of equivalence relations is the Bell number: 1, 2, 5, 15, 52.
- ಮ್ಯಾಕ್ಸಿಮಲ್ ಹಲವು ಇರಬಹುದು; ಗ್ರೇಟೆಸ್ಟ್ ಇದ್ದರೆ ಒಂದೇ. | There can be many maximal elements; a greatest element, if any, is unique.
- ಭಾಗಿಸುವಿಕೆಯಲ್ಲಿ ಎಲ್‌ಯುಬಿ = ಎಲ್‌ಸಿಎಂ, ಜಿಎಲ್‌ಬಿ = ಜಿಸಿಡಿ. | Under divisibility, LUB = LCM and GLB = GCD.
- ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳ ಮೇಲೆ ಭಾಗಿಸುವಿಕೆ ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ಅಲ್ಲ. | Divisibility on all integers is not antisymmetric.
On this page
ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್ (Equivalence Relation) | Equivalence relations
ರಿಫ್ಲೆಕ್ಸಿವ್, ಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಟ್ರಾನ್ಸಿಟಿವ್ ಆಗಿರುವ ರಿಲೇಶನ್ ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್. a ಯ ಈಕ್ವಿವಲೆನ್ಸ್ ಕ್ಲಾಸ್ (Equivalence Class) [a] ಎಂದರೆ a ಗೆ ಸಂಬಂಧಿಸಿದ ಎಲ್ಲಾ ಸದಸ್ಯರು. | A relation that is reflexive, symmetric and transitive is an equivalence relation. The equivalence class [a] is the set of everything related to a.
- ಎರಡು ಕ್ಲಾಸ್‌ಗಳು ಒಂದೇ ಆಗಿರುತ್ತವೆ ಅಥವಾ ಸಂಪೂರ್ಣ ಬೇರೆ; ಭಾಗಶಃ ಒಂದಾಗುವುದಿಲ್ಲ. | Two classes are either identical or disjoint; they never partly overlap.
- ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್‌ಗಳು ಮತ್ತು ಪಾರ್ಟಿಶನ್‌ಗಳು (Partitions) ಒಂದಕ್ಕೊಂದು ನಿಖರವಾಗಿ ಹೊಂದುತ್ತವೆ. | Equivalence relations and partitions correspond one to one.
- n ಸದಸ್ಯರ ಸೆಟ್‌ನ ಮೇಲೆ ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್‌ಗಳ ಸಂಖ್ಯೆ = ಬೆಲ್ ಸಂಖ್ಯೆ (Bell Number): 1, 2, 5, 15, 52 (n = 1 ರಿಂದ 5). | The number of equivalence relations on n elements is the Bell number: 1, 2, 5, 15, 52 for n = 1 to 5.
- ಕಾಂಗ್ರುಯೆನ್ಸ್ ಮಾಡ್ಯುಲೊ n (Congruence modulo n): a − b ಎಂಬುದು n ನಿಂದ ಭಾಗವಾದರೆ a ≡ b; ಇದಕ್ಕೆ n ಕ್ಲಾಸ್‌ಗಳು. | Congruence modulo n: a ≡ b when n divides a − b; it has n classes.
R = {(1, 2)} ಹೊಂದಿರುವ {1, 2, 3} ಮೇಲಿನ ಚಿಕ್ಕ ಈಕ್ವಿವಲೆನ್ಸ್ ರಿಲೇಶನ್: ಡಯಾಗೊನಲ್ 3 ಜೋಡಿ + (1, 2) + (2, 1) = 5 ಜೋಡಿಗಳು. ಪಾರ್ಟಿಶನ್ {{1, 2}, {3}}. | The smallest equivalence relation on {1, 2, 3} containing (1, 2): 3 diagonal pairs + (1, 2) + (2, 1) = 5 pairs. The partition is {{1, 2}, {3}}.
ಪಾರ್ಶಿಯಲ್ ಆರ್ಡರ್ (Partial Order) ಮತ್ತು ಪೋಸೆಟ್ (Poset) | Partial orders and posets
ರಿಫ್ಲೆಕ್ಸಿವ್, ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಟ್ರಾನ್ಸಿಟಿವ್ ಆಗಿರುವ ರಿಲೇಶನ್ ಪಾರ್ಶಿಯಲ್ ಆರ್ಡರ್; ಸೆಟ್ ಜೊತೆಗೆ ಅದು ಪೋಸೆಟ್ (Poset). ಪ್ರತಿ ಎರಡು ಸದಸ್ಯರೂ ಹೋಲಿಸಬಹುದಾದರೆ ಅದು ಟೋಟಲ್ ಆರ್ಡರ್ (Total Order). | A relation that is reflexive, antisymmetric and transitive is a partial order; with its set it forms a poset. If every two elements are comparable it is a total order.
ಧನ ಪೂರ್ಣಾಂಕಗಳ ಮೇಲೆ ಭಾಗಿಸುವಿಕೆ (divides) ಪಾರ್ಶಿಯಲ್ ಆರ್ಡರ್. ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳ ಮೇಲೆ ಅಲ್ಲ: 2 ಎಂಬುದು −2 ಅನ್ನು ಭಾಗಿಸುತ್ತದೆ ಮತ್ತು −2 ಎಂಬುದು 2 ಅನ್ನು ಭಾಗಿಸುತ್ತದೆ, ಆದರೆ 2 ≠ −2, ಆದ್ದರಿಂದ ಆಂಟಿಸಿಮೆಟ್ರಿ ಮುರಿಯುತ್ತದೆ. | Divisibility on the positive integers is a partial order. On all integers it is not: 2 divides −2 and −2 divides 2, yet 2 ≠ −2, so antisymmetry fails.
ಹ್ಯಾಸ್ ಡಯಾಗ್ರಾಮ್ (Hasse Diagram) | Hasse diagrams
ಹ್ಯಾಸ್ ಡಯಾಗ್ರಾಮ್‌ನಲ್ಲಿ ಲೂಪ್‌ಗಳನ್ನು ಮತ್ತು ಟ್ರಾನ್ಸಿಟಿವಿಟಿಯಿಂದ ಬರುವ ಅಂಚುಗಳನ್ನು ತೆಗೆಯಲಾಗುತ್ತದೆ; ದೊಡ್ಡ ಸದಸ್ಯ ಮೇಲೆ ಇರುವುದರಿಂದ ಬಾಣಗಳೂ ಬೇಡ. ಕವರಿಂಗ್ (Covering) ಸಂಬಂಧಗಳು ಮಾತ್ರ ಉಳಿಯುತ್ತವೆ. | A Hasse diagram drops loops and edges implied by transitivity, and since larger elements sit higher, arrows are dropped too. Only the covering relations remain.
ವಿಶೇಷ ಸದಸ್ಯರು | Special elements
| ಪದ | Term | ಅರ್ಥ | Meaning |
|---|---|
| ಮ್ಯಾಕ್ಸಿಮಲ್ (Maximal) | Maximal | ಅದಕ್ಕಿಂತ ದೊಡ್ಡದು ಯಾವುದೂ ಇಲ್ಲ; ಹಲವು ಇರಬಹುದು | nothing is above it; there may be several |
| ಗ್ರೇಟೆಸ್ಟ್ (Greatest) | Greatest | ಪ್ರತಿ ಸದಸ್ಯಕ್ಕಿಂತ ದೊಡ್ಡದು; ಇದ್ದರೆ ಒಂದೇ | above every element; unique if it exists |
| ಮಿನಿಮಲ್ (Minimal) ಮತ್ತು ಲೀಸ್ಟ್ (Least) | Minimal and least | ಮೇಲಿನ ಎರಡರ ವಿರುದ್ಧ ರೂಪಗಳು | the mirror images of the two above |
| ಎಲ್‌ಯುಬಿ (LUB) ಅಥವಾ ಸುಪ್ರೀಮಮ್ (Supremum) | LUB or supremum | ಎಲ್ಲಾ ಅಪ್ಪರ್ ಬೌಂಡ್‌ಗಳಲ್ಲಿ (Upper Bounds) ಚಿಕ್ಕದು | the least of all upper bounds |
| ಜಿಎಲ್‌ಬಿ (GLB) ಅಥವಾ ಇನ್‌ಫಿಮಮ್ (Infimum) | GLB or infimum | ಎಲ್ಲಾ ಲೋವರ್ ಬೌಂಡ್‌ಗಳಲ್ಲಿ (Lower Bounds) ದೊಡ್ಡದು | the greatest of all lower bounds |
ಭಾಗಿಸುವಿಕೆ ಪೋಸೆಟ್‌ನಲ್ಲಿ: ಎಲ್‌ಯುಬಿ (LUB) = ಎಲ್‌ಸಿಎಂ (LCM), ಜಿಎಲ್‌ಬಿ (GLB) = ಜಿಸಿಡಿ (GCD), ಅವು ಸೆಟ್‌ನಲ್ಲಿದ್ದರೆ. | In a divisibility poset: LUB = LCM and GLB = GCD, provided they lie in the set.
ಸೀಮಿತ ಪೋಸೆಟ್‌ನಲ್ಲಿ ಒಂದೇ ಮ್ಯಾಕ್ಸಿಮಲ್ ಸದಸ್ಯ ಇದ್ದರೆ ಅದೇ ಗ್ರೇಟೆಸ್ಟ್. ಎರಡು ಅಥವಾ ಹೆಚ್ಚು ಮ್ಯಾಕ್ಸಿಮಲ್ ಇದ್ದರೆ ಗ್ರೇಟೆಸ್ಟ್ ಇಲ್ಲ. | In a finite poset a unique maximal element is the greatest element. With two or more maximal elements there is no greatest.
ಲ್ಯಾಟಿಸ್ (Lattice) | Lattices
ಪ್ರತಿ ಜೋಡಿ ಸದಸ್ಯರಿಗೆ ಎಲ್‌ಯುಬಿ (ಜಾಯಿನ್, Join) ಮತ್ತು ಜಿಎಲ್‌ಬಿ (ಮೀಟ್, Meet) ಇರುವ ಪೋಸೆಟ್ ಲ್ಯಾಟಿಸ್. ({1, 2, 3, 6}, ಭಾಗಿಸುವಿಕೆ) ಲ್ಯಾಟಿಸ್; ({1, 2, 3}, ಭಾಗಿಸುವಿಕೆ) ಅಲ್ಲ, ಏಕೆಂದರೆ 2 ಮತ್ತು 3 ಕ್ಕೆ ಅಪ್ಪರ್ ಬೌಂಡ್ ಇಲ್ಲ. | A poset in which every pair has a LUB (join) and a GLB (meet) is a lattice. ({1, 2, 3, 6}, divides) is a lattice; ({1, 2, 3}, divides) is not, because 2 and 3 have no upper bound.
Practice questions
Answer all, then check. Explanations appear after checking.
Finished this topic? Tick it off.
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due