उपसर्ग क्रम
गणित में, विशेष रूप से क्रम सिद्धांत में, एक उपसर्ग क्रमित समुच्चय निरंतर प्रगति और निरंतर शाखा की संभावना को प्रस्तुत करके एक ट्री की सहज अवधारणा को सामान्यीकृत करता है। प्राकृतिक उपसर्ग क्रम प्रायः तब होते हैं जब गतिशील प्रणालियों को समय (पूरी तरह से व्यवस्थित समुच्चय) से कुछ प्रावस्था समष्टि तक फलनो के एक समुच्चय के रूप में माना जाता है। इस स्थिति में, समुच्चय के तत्वों को सामान्यतः प्रणाली के निष्पादन के रूप में संदर्भित किया जाता है।
उपसर्ग क्रम नाम शब्दों पर उपसर्ग क्रम से उत्पन्न होता है, जो एक विशेष प्रकार का उपरज्जु संबंध है और, अपने इसके अलग अभिलक्षण के कारण, एक ट्री है।
औपचारिक परिभाषा
एक उपसर्ग क्रम एक समुच्चय P पर एक द्विआधारी संबंध ≤ है जो प्रतिसममित, सकर्मक , परावर्ती और अधोमुखी समग्रता है, अर्थात, P में सभी a, b और c के लिए, हमारे पास यह है,
- a≤ a (स्वतुल्यता),
- यदि a ≤ b और b ≤ a तो a = b (प्रतिसममिति),
- यदि a ≤ b और b ≤ c तो a ≤ c (संक्रामिता),
- यदि a ≤ c और b ≤ c तो a ≤ b या b ≤ a (अधोमुखी समग्रता)।
उपसर्ग क्रमों के बीच फलन
जबकि आंशिक क्रमों के बीच क्रम-संरक्षण फलनो पर विचार करना सामान्य है, फिर भी उपसर्ग क्रमों के बीच सबसे महत्वपूर्ण प्रकार के फलन तथाकथित हिस्ट्री (विवरण) संरक्षण फलन हैं। एक उपसर्ग क्रमित समुच्चय P को देखते हुए, एक बिंदु p∈P का हिस्ट्री (परिभाषा के अनुसार पूरी तरह से क्रमित) समुच्चय p− = {q | q ≤ p} है। उपसर्ग क्रम P और Q के बीच एक फलन f: P → Q तब हिस्ट्री को संरक्षित करता है जब प्रत्येक p∈P के लिए हम f(p−) = f(p)− प्राप्त करते हैं। इसी प्रकार, एक बिंदु p∈P का भावी (उपसर्ग क्रमित) समुच्चय p+ = {q | p ≤ q} है और f भावी का संरक्षण है यदि सभी p∈P के लिए हम f(p+) = f(p)+ प्राप्त करते हैं।
प्रत्येक हिस्ट्री संरक्षण फलन और प्रत्येक भावी संरक्षण फलन भी क्रम संरक्षण है, लेकिन इसके विपरीत नहीं है। गतिशील प्रणालियों के सिद्धांत में, हिस्ट्री को संरक्षित करने वाले मानचित्र इस अंतर्ज्ञान को प्रग्रहण करते हैं कि एक प्रणाली में व्यवहार दूसरे में व्यवहार का "परिशोधन" है। इसके अतिरिक्त, जो फलन हिस्ट्री और भावी को संरक्षित करने वाले विशेषण फलन हैं, वे प्रणाली के बीच द्विअनुकरण की धारणा को प्रग्रहण करते हैं, और इस प्रकार यह अंतर्ज्ञान होता है कि एक विनिर्देश के संबंध में दिया गया शोधन सही है।
हिस्ट्री संरक्षित फलन की श्रेणी हमेशा एक उपसर्ग सवृत उपसमुच्चय होती है, जहां एक उपसमुच्चय S ⊆ P उपसर्ग सवृत होता है यदि t∈S और s≤t के साथ सभी s,t ∈ P के लिए हम s∈S प्राप्त करते हैं।
उत्पाद और सम्मिलन
उपसर्ग क्रमों की श्रेणी में मानचित्रों को आकारिकी के रूप में संरक्षित करने वाले हिस्ट्री को लेने से उत्पाद की एक धारणा बनती है जो दो क्रमों का कार्तीय गुणन नहीं है क्योंकि कार्तीय गुणन हमेशा एक उपसर्ग क्रम नहीं होता है। इसके बजाय, यह मूल उपसर्ग क्रमों को यादृच्छिक रूप से अंतः पत्रण की ओर ले जाता है। दो उपसर्ग क्रमों का मिलन असंयुक्त सम्मिलन है, जैसा कि आंशिक क्रमों के साथ होता है।
समरूपता
हिस्ट्री को संरक्षित करने वाला कोई भी विशेषण फलन एक क्रम समरूपता है। इसके अतिरिक्त, यदि किसी दिए गए उपसर्ग क्रमित समुच्चय P के लिए हम समुच्चय P- ≜ {P- | p∈ P} का निर्माण करते हैं तो हम प्राप्त करते हैं कि यह समुच्चय उपसमुच्चय संबंध ⊆ द्वारा क्रमित उपसर्ग है, और इसके अतिरिक्त, फलन अधिकतम, P- → P एक समरूपता है, जहां अधिकतम (S) प्रत्येक समुच्चय S∈P- के लिए अनुमापी है और P पर क्रम के संदर्भ में (अर्थात अधिकतम (P -) ≜ P ) है।
संदर्भ
- Cuijpers, Pieter (2013). "Prefix Orders as a General Model of Dynamics" (PDF). Proceedings of the 9th International Workshop on Developments in Computational Models (DCM). pp. 25–29.
- Cuijpers, Pieter (2013). "The Categorical Limit of a Sequence of Dynamical Systems". EPTCS 120: Proceedings EXPRESS/SOS 2013. 120: 78–92. doi:10.4204/EPTCS.120.7.
- Ferlez, James; Cleaveland, Rance; Marcus, Steve (2014). "Generalized Synchronization Trees". LLNCS 8412: Proceedings of FOSSACS'14. Lecture Notes in Computer Science. 8412: 304–319. doi:10.1007/978-3-642-54830-7_20. ISBN 978-3-642-54829-1.
