युग्मन फलन

Fगणित में, युग्मन फलन दो प्राकृतिक संख्याओं को विशिष्ट रूप से एक प्राकृतिक संख्या में कूटबद्ध करने की एक प्रक्रिया है।

किसी भी युग्मन फलन का उपयोग सेट सिद्धांत में यह सिद्ध करने के लिए किया जा सकता है कि पूर्णांक और तर्कसंगत संख्याओं में प्राकृतिक संख्याओं के समान ही प्रमुखता होती है।

परिभाषा

युग्मन फलन एक आक्षेप है

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .$

अधिक सामान्यतः, सेट A पर एक युग्मन फलन एक ऐसा फलन होता है जो A से तत्वों की प्रत्येक जोड़ी को A के तत्व में मैप करता है, जैसे कि A के तत्वों के किसी भी दो जोड़े A के विभिन्न तत्वों या $A^{2}$ से A तक एक आक्षेप से जुड़े होते हैं।

हॉपक्रॉफ्ट और उलमैन युग्मन फलन

हॉपक्रॉफ्ट और उलमैन (1979) निम्नलिखित युग्मन फलन को परिभाषित करते हैं: $\langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i$, जहां $i,j\in \{1,2,3,\dots \}$ यह नीचे दिए गए कैंटर पेयरिंग फलन के समान है, जिसे 0 (अथार्त , $i=k_{2}+1$, $j=k_{1}+1$,, और $\langle i,j\rangle -1=\pi (k_{2},k_{1})$ को बाहर करने के लिए स्थानांतरित कर दिया गया है।

कैंटर युग्मन फलन

कैंटर युग्मन फलन प्राकृतिक संख्याओं के प्रत्येक जोड़े को एक प्राकृतिक संख्या निर्दिष्ट करता है

कैंटर युग्मन फलन का ग्राफ़

कैंटर पेयरिंग फलन एक आदिम पुनरावर्ती फलन पेयरिंग फलन है

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N}$

द्वारा परिभाषित

$\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}$

जहाँ $k_{1},k_{2}\in \{0,1,2,3,\dots \}$.

इसे इस प्रकार भी व्यक्त किया जा सकता है $Pair[x,y]:={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}$.

यह पूरी तरह से मोनोटोनिक w.r.t. भी है। प्रत्येक तर्क, अर्थात् सभी के लिए $k_{1},k_{1}',k_{2},k_{2}'\in \mathbb {N}$, यदि $k_{1}<k_{1}'$, तब $\pi (k_{1},k_{2})<\pi (k_{1}',k_{2})$; इसी प्रकार, यदि $k_{2}<k_{2}'$, तब $\pi (k_{1},k_{2})<\pi (k_{1},k_{2}')$ है

यह कथन कि यह एकमात्र द्विघात युग्मन फलन है, फ़ुएटर-पोलिया प्रमेय के रूप में जाना जाता है। क्या यह एकमात्र बहुपद युग्मन फलन है, यह अभी भी एक विवर्त प्रश्न है। जब हम युग्मन फलन को k₁ और k₂ पर प्रयुक्त करते हैं तो हम अधिकांशतः परिणामी संख्या को ⟨k₁, k₂⟩ के रूप में दर्शाते हैं।

इस परिभाषा को आगमनात्मक रूप से सामान्यीकृत किया जा सकता है

$\pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N}$

जैसा $n>2$ के लिए

$\pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})$

एक जोड़ी के लिए ऊपर परिभाषित आधार स्थिति के साथ: $\pi ^{(2)}(k_{1},k_{2}):=\pi (k_{1},k_{2}).$

कैंटर युग्मन फलन को व्युत्क्रम

होने देना $z\in \mathbb {N}$ एक इच्छित प्राकृतिक संख्या हो. हम दिखाएंगे कि अद्वितीय मान उपस्थित हैं $x,y\in \mathbb {N}$ ऐसा है कि

$z=\pi (x,y)={\frac {(x+y+1)(x+y)}{2}}+y$

और इसलिए यह कार्य है π(x, y) विपरीत है. गणना में कुछ मध्यवर्ती मानों को परिभाषित करना सहायक होता है और इसलिए फलन π(x, y) विपरीत है। गणना में कुछ मध्यवर्ती मानों को परिभाषित करना सहायक होता है:

$w=x+y\!$

$t={\frac {1}{2}}w(w+1)={\frac {w^{2}+w}{2}}$

$z=t+y\!$

जहाँ t, w की त्रिभुज संख्या है। यदि हम द्विघात समीकरण को हल करते हैं

$w^{2}+w-2t=0\!$

t के फलन के रूप में w के लिए, हमें मिलता है

$w={\frac {{\sqrt {8t+1}}-1}{2}}$

जो एक सख्ती से बढ़ने वाला और निरंतर कार्य है जब t गैर-नकारात्मक वास्तविक है। तब से

$t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}$

हमें वह मिल गया

$w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1$

और इस तरह

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .$

जहां ⌊ ⌋ फ़्लोर फलन है। तो z से x और y की गणना करने के लिए, हम यह करते हैं:

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$

$t={\frac {w^{2}+w}{2}}$

$y=z-t\!$

$x=w-y.\!$

चूंकि कैंटर युग्मन इंजेक्शन फलन विपरीत है, इसलिए इसे विशेषण फलन या एक-से-एक और विशेषण फलन होना चाहिए।

उदाहरण

की गणना करना π(47, 32):

47 + 32 = 79,

79 + 1 = 80,

79 × 80 = 6320,

6320 ÷ 2 = 3160,

3160 + 32 = 3192,

इसलिए π(47, 32) = 3192.

खोजने के लिए x और y ऐसा है कि π(x, y) = 1432:

8 × 1432 = 11456,

11456 + 1 = 11457,

√11457 = 107.037,

107.037 − 1 = 106.037,

106.037 ÷ 2 = 53.019,

⌊53.019⌋ = 53,

इसलिए w = 53;

53 + 1 = 54,

53 × 54 = 2862,

2862 ÷ 2 = 1431,

इसलिए t = 1431;

1432 − 1431 = 1,

इसलिए y = 1;

53 − 1 = 52,

इसलिए x = 52; इस प्रकार π(52, 1) = 1432.

व्युत्पत्ति

कैंटर के युग्मन फलन के समान सिद्धांतों से एक विकर्ण रूप से वृद्धिशील स्नैकिंग फलन का उपयोग अधिकांशतः तर्कसंगत संख्याओं की गणना को प्रदर्शित करने के लिए किया जाता है।

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

एक युग्म फलन को सामान्यतः आगमनात्मक रूप से परिभाषित किया जा सकता है - अर्थात, nवाँ युग्म दिया गया है, (n+1)वाँ युग्म क्या है? कैंटर का कार्य जिस तरह से विमान में विकर्ण रूप से आगे बढ़ता है उसे इस प्रकार व्यक्त किया जा सकता है

$\pi (x,y)+1=\pi (x-1,y+1)$.

फलन को यह भी परिभाषित करना होगा कि जब यह पहले चतुर्थांश की सीमाओं से टकराता है तो क्या करना है - कैंटर का युग्मन फलन अपनी विकर्ण प्रगति को एक कदम आगे या बीजगणितीय रूप से फिर से प्रारंभ करने के लिए x-अक्ष पर वापस रीसेट हो जाता है:

$\pi (0,k)+1=\pi (k+1,0)$.

इसके अतिरिक्त हमें प्रारंभिक बिंदु को परिभाषित करने की आवश्यकता है हमारी प्रेरण विधि में प्रारंभिक चरण क्या होगा: π(0, 0) = 0.

मान लें कि एक द्विघात 2-आयामी बहुपद है जो इन स्थितियों में फिट हो सकता है (यदि ऐसा नहीं होता, तो कोई उच्च-डिग्री बहुपद को प्रयाश करके दोहरा सकता है)। सामान्य रूप तो यह है

$\pi (x,y)=ax^{2}+by^{2}+cxy+dx+ey+f$.

f = 0 और: प्राप्त करने के लिए हमारी प्रारंभिक और सीमा नियमो को अंकित करें:

$bk^{2}+ek+1=a(k+1)^{2}+d(k+1)$,

इसलिए हम प्राप्त करने के लिए अपने k शब्दों का मिलान कर सकते हैं

b = a

d = 1-a

e = 1+a.

इसलिए c को छोड़कर प्रत्येक पैरामीटर को a के संदर्भ में लिखा जा सकता है, और हमारे पास एक अंतिम समीकरण है, हमारा विकर्ण चरण, जो उन्हें संबंधित करेगा:

${\begin{aligned}\pi (x,y)+1&=a(x^{2}+y^{2})+cxy+(1-a)x+(1+a)y+1\\&=a((x-1)^{2}+(y+1)^{2})+c(x-1)(y+1)+(1-a)(x-1)+(1+a)(y+1).\end{aligned}}$

a और c, के लिए निश्चित मान प्राप्त करने के लिए शब्दों का फिर से विस्तार करें और मिलान करें और इस प्रकार सभी पैरामीटर:

a = 1/2 = b = d

c = 1

e = 3/2

f = 0.

इसलिए

${\begin{aligned}\pi (x,y)&={\frac {1}{2}}(x^{2}+y^{2})+xy+{\frac {1}{2}}x+{\frac {3}{2}}y\\&={\frac {1}{2}}(x+y)(x+y+1)+y,\end{aligned}}$

कैंटर युग्मन फलन है, और हमने व्युत्पत्ति के माध्यम से यह भी प्रदर्शित किया कि यह प्रेरण की सभी नियमो को पूरा करता है।

अन्य युग्मन कार्य

कार्यक्रम $P_{2}(x,y):=2^{x}(2y+1)-1$ एक युग्मन फलन है.

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

2001 में, पिजन ने बिट-इंटरलीविंग पर आधारित एक पेयरिंग फलन का प्रस्ताव रखा था जिसे पुनरावर्ती रूप से इस प्रकार परिभाषित किया गया है:

$\langle i,j\rangle _{P}={\begin{cases}T&{\text{if}}\ i=j=0;\\\langle \lfloor i/2\rfloor ,\lfloor j/2\rfloor \rangle _{P}:i_{0}:j_{0}&{\text{otherwise,}}\end{cases}}$

जहाँ $i_{0}$ और $j_{0}$ क्रमशः i और j के न्यूनतम महत्वपूर्ण बिट हैं।

2006 में, सुडज़िक ने अभिव्यक्ति द्वारा परिभाषित एक अधिक सुंदर युग्मन फलन का प्रस्ताव रखा जाता है:

$\operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x\neq \max\{x,y\},\\x^{2}+x+y&{\text{if}}\ x=\max\{x,y\}.\\\end{cases}}$

जिसे अभिव्यक्ति का उपयोग करके अयुग्मित किया जा सकता है:

$\operatorname {ElegantUnpair} [z]:={\begin{cases}\left\{z-\lfloor {\sqrt {z}}\rfloor ^{2},\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}<\lfloor {\sqrt {z}}\rfloor ,\\\left\{\lfloor {\sqrt {z}}\rfloor ,z-\lfloor {\sqrt {z}}\rfloor ^{2}-\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}\geq \lfloor {\sqrt {z}}\rfloor .\end{cases}}$

(गुणात्मक रूप से, यह वर्गों के किनारों के साथ जोड़े को निरंतर संख्याएं प्रदान करता है।) यह युग्मन फलन गहराई के आधार पर एसके कॉम्बिनेटर कैलकुलस अभिव्यक्ति का आदेश देता है। यह विधि विचार के $\mathbb {N}$ के लिए मात्र अनुप्रयोग है, जो सेट थ्योरी पर अधिकांश पाठ्यपुस्तकों में पाया जाता है, जेडएफसी में किसी भी अनंत कार्डिनल $\kappa$ के लिए $\kappa ^{2}=\kappa$ स्थापित करने के लिए उपयोग किया जाता है। $\kappa \times \kappa$ पर द्विआधारी संबंध परिभाषित करें

$(\alpha ,\beta )\preccurlyeq (\gamma ,\delta ){\text{ if either }}{\begin{cases}(\alpha ,\beta )=(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )<\max(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha <\gamma ,{\text{ or}}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha =\gamma \ {\text{and}}\ \beta <\delta .\end{cases}}$

फिर $\preccurlyeq$ को एक सुव्यवस्थित रूप में दिखाया जाता है जैसे कि प्रत्येक तत्व में ${}<\kappa$ पूर्ववर्ती होते हैं, जिसका अर्थ है कि $\kappa ^{2}=\kappa$ इससे यह निष्कर्ष निकलता है कि $(\mathbb {N} \times \mathbb {N} ,\preccurlyeq )$, $(\mathbb {N} ,\leqslant )$ का समरूपी है और उपरोक्त युग्म फलन बढ़ते क्रम में पूर्णांक युग्मों की गणना से अधिक कुछ नहीं है। (टॉक भी देखें: पसंद के बारे में टार्स्की का प्रमेय या विपरीत का प्रमाण है।)