द्विअनुकरण

सैद्धांतिक कंप्यूटर विज्ञान में द्विअनुकरण संक्रमण प्रणालियों के बीच एक द्विआधारी संबंध होता है, इसके विपरीत सहयोगी प्रणालियाँ उसी तरह से व्यवहार करती है जिस तरह एक प्रणाली दूसरे का अनुकरण करती है।

सहज रूप से दो प्रणालियाँ द्विसमान होती है। इस अर्थ में, पर्यवेक्षक द्वारा प्रत्येक प्रणाली को दूसरे से अलग नहीं किया जा सकता है।

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

एक संक्रमण प्रणाली को देखते हुए ($S$, $\Lambda$, →), जहाँ $S$ का एक समूह है, $\Lambda$ का एक समूह है और → अंकित किए गए संक्रमण का एक समूह है (अर्थात, एक उपसमूह) $S\times \Lambda \times S$), द्विअनुकरण एक द्विआधारी संबंध है $R\subseteq S\times S$, ऐसे कि दोनों $R$ और इसका विपरीत संबंध $R^{T}$ अनुकरण अनुक्रम है। इससे यह पता चलता है कि सममित सिमुलेशन एक द्विअनुकरण है। इस प्रकार कुछ लेखक द्विअनुकरण को सममित अनुकरण के रूप में परिभाषित करते है।

समान रूप से, $R$ के लिए यदि एक द्विअनुकरण है $(p,q)$ में $R$ और सभी अंकित है α में $\Lambda$:

• यदि $p\mathrel {\overset {\alpha }{\rightarrow }} p'$, फिर वहाँ है $q\mathrel {\overset {\alpha }{\rightarrow }} q'$ ऐसा है कि $(p',q')\in R$,
• यदि $q\mathrel {\overset {\alpha }{\rightarrow }} q'$, फिर वहाँ है $p\mathrel {\overset {\alpha }{\rightarrow }} p'$ ऐसा है कि $(p',q')\in R$.

दो संखयाए दिए गए $p$ और $q$ में $S$, $p$ के समान है $q$, लिखा हुआ $p\,\sim \,q$, यदि कोई द्विअनुकरण है $R$ ऐसा है कि $(p,q)\in R$. इसका मतलब है कि द्विसमानता संबंध $\,\sim \,$ सभी द्विअनुकरणों का मिलन है: $(p,q)\in \,\sim \,$ जब $(p,q)\in R$ द्विअनुकरण के लिए है $R$.

द्विअनुकरण का समूह संघ के अंतर्गत बंद होता है, इसलिए, द्विसमानता संबंध स्वयं एक द्विअनुकरण होता है। चूँकि यह सभी द्विअनुकरण का मिलन होता है, यह अद्वितीय सबसे बड़ा द्विअनुकरण होता है। द्विअनुकरण को पूर्व संबंधी, सममित और सकर्मक समापन के अनुसार भी बंद किया जाता है, इसलिए, सबसे बड़ा द्विअनुकरण प्रतिवर्ती, सममित और संक्रमणीय होती है। इससे यह निष्कर्ष निकलता है कि सबसे बड़ा द्विअनुकरण - द्विसमानता - एक तुल्यता संबंध है।

वैकल्पिक परिभाषाएँ

संबंधपरक परिभाषा

द्विअनुकरण को संबंधों की संरचना के संदर्भ में निम्नानुसार परिभाषित किया जा सकता है।

एक संक्रमण प्रणाली दी गई $(S,\Lambda ,\rightarrow )$, एक द्विअनुकरण संबंध (गणित) एक द्विआधारी संबंध है $R$ और $S$ (अर्थात, $R$ ⊆ $S$ × $S$) ऐसा है कि $\forall \alpha \in \Lambda$

$$R\ ;\ {\overset {\alpha }{\rightarrow }}\quad {\subseteq }\quad {\overset {\alpha }{\rightarrow }}\ ;\ R$$

और

$$R^{-1}\ ;\ {\overset {\alpha }{\rightarrow }}\quad {\subseteq }\quad {\overset {\alpha }{\rightarrow }}\ ;\ R^{-1}$$

संबंध संरचना की एकरसता और निरंतरता से, यह तुरंत पता चलता है कि द्विअनुकरण का समूह संघों (संबंधों की स्थिति में जुड़ता है) के अनुसार बंद होता है, और एक सरल बीजगणितीय गणना से पता चलता है कि द्विसमानता का संबंध - सभी द्विअनुकरण का जुड़ाव होता है। इस परिभाषा और द्विसमानता के संबंधित उपचार की व्याख्या किसी भी समावेशी मात्रा में की जा सकती है।

निश्चित बिंदु परिभाषा

द्विसमानता को अनुक्रम सिद्धांत में भी परिभाषित किया जा सकता है, नास्टर-टार्स्की सिद्धांत के संदर्भ में, अधिक त्रुटिहीन रूप से नीचे परिभाषित सबसे बड़े निश्चित बिंदु के रूप में एक निश्चित फलन होता है।

एक संक्रमण प्रणाली को देखते हुए ($S$, Λ, →), परिभाषित करता है $F:{\mathcal {P}}(S\times S)\to {\mathcal {P}}(S\times S)$ द्विआधारी संबंधों से एक फलन बनता है $S$ द्विआधारी संबंधों को समाप्त करने के लिए होता है $S$, निम्नलिखित नुसार:

$R$ द्विआधारी संबंध को समाप्त करता है $S$. $F(R)$ सभी जोड़ियों के समुच्चय के रूप में परिभाषित किया जाता है $(p,q)$ में $S$ × $S$ ऐसा है कि:

$$\mathrm{\forall <!--\; \forall \; -->}\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->\mathrm{\Lambda <!--\; \Lambda \; -->}.\mathrm{\forall <!--\; \forall \; -->}{p}^{\prime }\in <!--\; \in \; -->S.p\stackrel{\mathrm{\alpha <!--\; \alpha \; -->}}{\to <!--\; \to \; -->}{p}^{\prime }\Rightarrow <!--\; \Rightarrow \; -->\mathrm{\exists <!--\; \exists \; -->}$$