उपसर्ग क्रम
गणित में, विशेष रूप से आदेश सिद्धांत में, एक उपसर्ग क्रमित समुच्चय निरंतर प्रगति और निरंतर शाखा की संभावना को प्रस्तुत करके एक पेड़ की सहज अवधारणा को सामान्यीकृत करता है। प्राकृतिक उपसर्ग आदेश प्रायः तब होते हैं जब गतिशील प्रणालियों को समय (पूरी तरह से व्यवस्थित सेट) से कुछ प्रावस्था समष्टि तक कार्यों के एक सेट के रूप में माना जाता है। इस मामले में, सेट के तत्वों को आमतौर पर सिस्टम के निष्पादन के रूप में संदर्भित किया जाता है।
उपसर्ग क्रम नाम शब्दों पर उपसर्ग क्रम से उत्पन्न होता है, जो एक विशेष प्रकार का सबस्ट्रिंग संबंध है और, अपने अलग चरित्र के कारण, एक पेड़ है।
औपचारिक परिभाषा
एक उपसर्ग क्रम एक सेट (गणित) पी पर एक द्विआधारी संबंध ≤ है जो एंटीसिमेट्रिक संबंध, सकर्मक संबंध, रिफ्लेक्सिव संबंध और नीचे की ओर कुल है, यानी, सभी ए, बी के लिए, और पी में सी, हमारे पास वह है:
- ए ≤ ए (रिफ्लेक्सिविटी);
- अगर ए ≤ बी और बी ≤ ए तो ए = बी (एंटीसिममेट्री);
- अगर ए ≤ बी और बी ≤ सी तो ए ≤ सी (परिवर्तनशीलता);
- अगर ए ≤ सी और बी ≤ सी तो ए ≤ बी या बी ≤ ए (नीचे की ओर समग्रता)।
उपसर्ग आदेशों के बीच कार्य
जबकि आंशिक आदेशों के बीच ऑर्डर-संरक्षण कार्यों पर विचार करना सामान्य है, उपसर्ग आदेशों के बीच सबसे महत्वपूर्ण प्रकार के कार्य तथाकथित इतिहास संरक्षण कार्य हैं। एक उपसर्ग आदेशित सेट 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.
