युग्मन फलन

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

परिभाषा

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

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .$अधिक आम तौर पर, सेट ए पर एक युग्मन फ़ंक्शन एक ऐसा फ़ंक्शन होता है जो ए से तत्वों की प्रत्येक जोड़ी को ए के तत्व में मैप करता है, जैसे कि ए के तत्वों के दो जोड़े ए के विभिन्न तत्वों से जुड़े होते हैं, या से आपत्ति $A^{2}$ ए को.

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

हॉपक्रॉफ्ट और उल्मैन (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})$).

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

File:Cantor's Pairing Function.svg

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

File:Cantor's Pairing Function Plot.svg

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

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

$\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) उलटा है. गणना में कुछ मध्यवर्ती मानों को परिभाषित करना सहायक होता है:

$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\!$

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

$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 .$

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

$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.

व्युत्पत्ति

File:Diagonal argument.svg

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

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

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

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

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

$\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.

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

${\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 ^{2}=\kappa$ किसी भी अनंत कार्डिनल के लिए $\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 )$ और उपरोक्त युग्म फ़ंक्शन बढ़ते क्रम में पूर्णांक युग्मों की गणना से अधिक कुछ नहीं है। (टॉक भी देखें: पसंद के बारे में टार्स्की का प्रमेय#विपरीत का प्रमाण।)