उपसर्ग क्रम

गणित में, विशेष रूप से क्रम सिद्धांत में, एक उपसर्ग क्रमित समुच्चय निरंतर प्रगति और निरंतर शाखा की संभावना को प्रस्तुत करके एक वृक्ष की सहज अवधारणा को सामान्यीकृत करता है। प्राकृतिक उपसर्ग क्रम प्रायः तब होते हैं जब गतिशील प्रणालियों को समय (पूरी तरह से व्यवस्थित समुच्चय) से कुछ प्रावस्था समष्टि तक फलनो के एक समुच्चय के रूप में माना जाता है। इस स्थिति में, समुच्चय के तत्वों को आमतौर पर प्रणाली के निष्पादन के रूप में संदर्भित किया जाता है।

उपसर्ग क्रम नाम शब्दों पर उपसर्ग क्रम से उत्पन्न होता है, जो एक विशेष प्रकार का उपरज्जु संबंध है और, अपने इसके अभिलक्षण के कारण, एक वृक्ष है।

औपचारिक परिभाषा

एक उपसर्ग क्रम एक समुच्चय 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 | क्यू ≤ पी}. एक फ़ंक्शन f: P → Q उपसर्ग क्रम 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} हम पाते हैं कि यह समुच्चय उपसमुच्चय संबंध ⊆ द्वारा क्रमित उपसर्ग है, और इसके अलावा, फ़ंक्शन max: P- → P एक समरूपता है, जहां max(S) प्रत्येक समुच्चय S∈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.