وظيفة الاقتران

في الرياضيات ، دالة الاقتران هي عملية ترميز فريدة لعددين طبيعيين في عدد طبيعي واحد.

يمكن استخدام أي دالة اقتران في نظرية المجموعات لإثبات أن الأعداد الصحيحة والأعداد النسبية لها نفس عدد العناصر مثل الأعداد الطبيعية. ^{[ 1 ]}

تعريف

دالة الاقتران هي دالة تقابل

{\displaystyle \pi

^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}

تعميم

وبشكل أعم، دالة الاقتران على مجموعة $A$ هي دالة تقوم بتحويل كل زوج من العناصر من $A$ إلى عنصر من $A$ بحيث تكون أزواج العناصر المتميزة من $A$ ترتبط بعناصر مميزة من $A$ ، ^{[ 5 ]}^{[ أ ]} أو تقابل من $A^{2}$ ل $A$ [ ⁶^]

بدلاً من التجريد من المجال، يمكن أيضًا تعميم عدد عناصر دالة الاقتران: توجد دالة اقتران كانتور معممة من الرتبة n على $\mathbb {N}$ [ ³^]

وظيفة اقتران كانتور

دالة اقتران كانتور هي دالة اقتران بدائية تكرارية

{\displaystyle \pi

محدد بواسطة

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

أين $k_{1},k_{2}\in \{0,1,2,3,\dots \}$ [ ⁷^]

ويمكن التعبير عنها أيضاً على النحو التالي: $\pi (x,y):={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}$ [ ⁵^]

كما أنها رتيبة تمامًا بالنسبة لكل وسيط، أي لجميع $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}')$ .

تُعرف العبارة التي تنص على أن هذه هي دالة الاقتران التربيعية الوحيدة بنظرية فويتر-بوليا . ^{[ 8 ]} $أما مسألة ما$ $إذا$ كانت هذه هي دالة الاقتران متعددة الحدود الوحيدة فلا تزال محل نقاش. عند تطبيق دالة الاقتران على $k1$ و $k2$ $، نرمز$ $عادةً$ $إلى$ العدد الناتج $بالرمز$ $⟨k1 , k2⟩$ . ^{[ 9 ]}

يمكن تعميم هذا التعريف استقرائياً ليشمل دالة كانتور الثلاثية

\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}).$ ^{[ 10 ]}

تعميم آخر لدالة اقتران كانتور إلى تقابل $\pi ^{(n)}\colon \mathbb {N} ^{n}\to \mathbb {N}$ يتم توفيرها بواسطة نظام الأعداد التوافقية :

\pi ^{(n)}(x_{1},\dots ,x_{n})={\binom {x_{1}+\dots +x_{n}+n-1}{n}}+{\binom {x_{1}+\dots +x_{n-1}+n-2}{n-1}}+\dots +{\binom {x_{1}+x_{2}+1}{2}}+{\binom {x_{1}}{1}}.

عكس دالة اقتران كانتور

يترك $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 \times 80 = 6320

،

6320 \div 2 =

3160

3160 + 32 =

3192

إذن $π (47, 32) = 3192$ .

لإيجاد قيمتي $x$ و $y$ بحيث يكون $π (x, y) = 1432$ :

8 \times 1432 = 11456

،

11456 + 1 =

11457

\sqrt 11457 =

107.037

107.037 - 1 =

106.037

106.037 \div 2 =

53.019

⌊53.019⌋ = 53

,

إذن $w = 53$ ؛

53 + 1 = 54

،

53 \times 54 = 2862

،

2862 \div 2 =

1431

إذن $t = 1431$ ؛

1432 - 1431 = 1

،

إذن $y = 1$ ;

53 - 1 = 52

،

إذن $x = 52$ ؛ وبالتالي $π (52, 1) = 1432$ .

الاشتقاق

يُعدّ الشكل البياني لدالة اقتران كانتور، وهو عبارة عن متوالية قطرية، حيلةً شائعةً في التعامل مع المتتاليات اللانهائية وقابلية العد . ^{[ ب ]} يمكن التحقق من صحة هذه الدالة ذات الشكل القطري باستخدام القواعد الجبرية لمجموعة من كثيرات الحدود، والتي ستكون الدالة التربيعية أبسطها، وذلك باستخدام طريقة الاستقراء . في الواقع، يمكن اتباع هذه التقنية نفسها لمحاولة استنتاج أي عدد من الدوال الأخرى لأي مجموعة متنوعة من مخططات تعداد المستوى.

يمكن عادةً تعريف دالة الاقتران استقرائيًا - أي، بمعرفة الزوج رقم $(ن$ )، ما هو الزوج رقم $(ن + ١)$ ؟ ويمكن التعبير عن كيفية تقدم دالة كانتور قطريًا عبر المستوى كما يلي:

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

.

يجب أن تحدد الدالة أيضًا ما يجب فعله عندما تصل إلى حدود الربع الأول - تعود دالة الاقتران الخاصة بكانتور إلى المحور السيني لاستئناف تقدمها القطري خطوة واحدة إلى الخارج، أو جبريًا:

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

.

كما نحتاج إلى تحديد نقطة البداية، وما ستكون الخطوة الأولية في طريقة الاستقراء لدينا: $π (0, 0) = 0$ .

لنفترض وجود متعددة حدود تربيعية ثنائية الأبعاد تُناسب هذه الشروط (وإلا، يُمكن تكرار العملية بتجربة متعددة حدود من درجة أعلى). ويكون الشكل العام حينها كما يلي:

\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$ للحصول على

ب = أ

د = 1 - أ

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$ ، وبالتالي جميع المعلمات:

أ = ½ = ب = د ​ ​ ​ ​

ج = 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}}

هي دالة اقتران كانتور، وقد أثبتنا أيضًا من خلال الاشتقاق أن هذا يفي بجميع شروط الاستقراء.

وظيفة اقتران كانتور المزاحة

دالة الاقتران التالية: ${\displaystyle \langle i,j\rangle$ ، حيث $i,j\in \{1,2,3,\dots \}$ [ ¹¹^] هي نفسها دالة اقتران كانتور، ولكنها مُزاحة لاستبعاد الصفر (أي ^، $i=k_{2}+1$ ، $j=k_{1}+1$ ، و $\langle i,j\rangle -1=\pi (k_{2},k_{1})$ ). ^{[ 7 ]} تم استخدامه في كتاب الكمبيوتر المدرسي الشهير لهوبكروفت وأولمان (1979).

بالنسبة للأعداد الترتيبية

توجد دالة اقتران "قياسية" للأعداد الترتيبية ، وهي في الوقت نفسه دالة اقتران لكل عدد ألفي (أي العدد الترتيبي الأول لكل عدد أصلي قابل للترتيب الجيد لانهائي ). وتُستنتج هذه الدالة من الترتيب الجيد التالي لأزواج الأعداد الترتيبية: ^{[ 12 ]}

(\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}}

الفكرة الأساسية هي أن $\max(\alpha ,\beta )$ يُستخدم كمفتاح فرز أساسي . لذلك، لكل ترتيب $\alpha$ ، جميع الأزواج التي يكون فيها كلا المدخلين أقل من $\alpha$ يأتي قبل جميع الأزواج الأخرى ؛ بعبارة أخرى، الضرب الديكارتي $\alpha \times \alpha$ يتم ربط ⁠ بجزء أولي من هذا الترتيب الجديد، مع الإشارة إلى نوع ترتيب الجزء الأولي بواسطة ⁠ $\gamma (\alpha )$ ⁠ .

منذ $\gamma (\alpha )$ ⁠ عبارة عن متتالية ترتيبية متزايدة تمامًا، ⁠ $\gamma (\alpha )\geq \alpha$ وهي متصلة أيضاً، لأنه بالنسبة للترتيب الحدي $\lambda$ لدينا $\lambda \times \lambda =\bigcup _{\alpha <\lambda }(\alpha \times \alpha )$ . الآن لجميع أرقام الألف ⁠ $\alpha$ ، $\gamma (\alpha )=\alpha$ يمكن إثبات ذلك بالاستقراء المتسامي :^{[ 13 ]}

إذا $\alpha =\omega$ ثم $\gamma (\alpha )=\omega$ بالاستمرارية منذ $\gamma (n)=n^{2}$ هو عدد طبيعي لكل عدد طبيعي $n$ ⁠ .
إذا $\alpha >\omega$ إذا كان ترتيبًا أوليًا، فإن $\gamma (\alpha )=\alpha$ بالاستمرارية منذ $\vert \gamma (\delta )\vert =\vert \delta \times \delta \vert =\vert \delta \vert ^{2}=\vert \delta \vert <\vert \alpha \vert$ لكل اللانهاية $\delta <\alpha$ ، حيث $\vert \delta \vert ^{2}=\vert \delta \vert$ يمكن إثبات ذلك بتطبيق فرضية الاستقراء على الترتيب الأولي لـ $\delta$ ⁠ .

من أهم نتائج وظيفة الاقتران هذه أن $\kappa ^{2}=\kappa$ لكل عدد أصلي لانهائي قابل للترتيب الجيد $\kappa$ . على وجه الخصوص، في ZFC، كل عدد أصلي قابل للترتيب الجيد، لذلك ⁠ $\kappa ^{2}=\kappa$ ينطبق هذا على جميع الأعداد الأصلية اللانهائية $\kappa$ . وعلى العكس من ذلك، فإن العبارة " $\kappa ^{2}=\kappa$ ينطبق هذا على جميع الأعداد الأصلية اللانهائية $\kappa$ " يشير إلى بديهية الاختيار ؛ هذه النتيجة تُعرف باسم نظرية تارسكي حول الاختيار .

الاقتصار على الأعداد الطبيعية

تقييد دالة الاقتران "الأساسية" للأعداد الترتيبية بمجموعة الأعداد الطبيعية $\mathbb {N} \equiv \omega$ ينتج عن ذلك دالة اقتران مختلفة عن دالة اقتران كانتور، والتي اعتبرها زودزيك "أكثر أناقة".^{[ 5 ]} الصيغة الصريحة التي تحدد دالة الاقتران هذه هي:

\operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x<y,\\x^{2}+x+y&{\text{if}}\ x\geq 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}}

(نوعياً، يقوم بتعيين أرقام متتالية للأزواج على طول حواف المربعات.)

تتجلى إحدى مزايا دالة الاقتران هذه عند استخدام دالة الاقتران لتمثيل بنية تشبه الشجرة الثنائية ، حيث يكون الأول $c$ تمثل الأعداد الطبيعية أنواعًا مختلفة من الأوراق، و $\operatorname {Pair} [x,y]+c$ يمثل شجرة ثنائية ذات شجرتين فرعيتين، يمنى ويسرى، ممثلتين بـ $x$ و $y$ على التوالي. تضمن دالة الاقتران هذه أن جميع الأشجار الثنائية مرتبة حسب العمق. ومن الأمثلة الملموسة على هذا النوع من البنية الشبيهة بالشجرة الثنائية تعبير حساب التوافيق SK .^{[ 5 ]}

وظائف الاقتران الأخرى

الوظيفة $P_{2}(x,y):=2^{x}(2y+1)-1$ هي دالة اقتران.

في عام 1990، اقترح ريغان أول دالة اقتران معروفة قابلة للحساب في زمن خطي وبمساحة ثابتة (إذ لا يمكن حساب الأمثلة المعروفة سابقًا في زمن خطي إلا إذا كان الضرب كذلك ، وهو أمر مشكوك فيه). في الواقع، يمكن حساب كل من دالة الاقتران هذه ومعكوسها باستخدام محولات ذات حالات محدودة . في الورقة البحثية نفسها، اقترح المؤلف دالتين اقتران رتيبتين إضافيتين يمكن حسابهما عبر الإنترنت في زمن خطي وبمساحة لوغاريتمية ؛ ويمكن أيضًا حساب الأولى دون اتصال بالإنترنت بمساحة ثابتة. ^{[ 4 ]}

في عام 2001، اقترح بيجون دالة اقتران تعتمد على تشابك البتات ، والتي تُعرَّف بشكل متكرر على النحو التالي:

\langle i,j\rangle _{P}={\begin{cases}\bot &{\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 على التوالي. ^{[ 14 ]}

الاقتباسات

ملحوظات

↑ أي حقنة من $A^{2}\rightarrow A$ .
↑ يُستخدم مصطلح "الحجة القطرية" أحيانًا للإشارة إلى هذا النوع من التعداد، ولكنه لا يرتبط بشكل مباشر بحجة كانتور القطرية .

الحواشي

↑ حمامة :
تنشأ وظائف الاقتران بشكل طبيعي في البرهان على أن عدد الأعداد النسبية $\mathbb {Q}$ والأعداد الصحيحة غير السالبة $\mathbb {Z} _{\geq 0}$ هي نفسها، أي $|\mathbb {Q} |=|\mathbb {Z} _{\geq 0}|=\aleph _{0}$ ، والتي تعود في الأصل إلى كانتور.
↑ حمامة .
1 2 Lisi 2007 .
1 2 ريغان 1992 .
1 2 3 4 5 Szudzik 2006 .
↑ Szudzik 2017 .
1 2 حمامة ، المعادلة 8.
↑ شتاين (1999 ، ص 448-452) نقلاً عن بيجون .
↑ روجرز، هارتلي (1 يناير 1967). نظرية الدوال التكرارية والحوسبة الفعالة . مطبعة معهد ماساتشوستس للتكنولوجيا. ص 64. ISBN 978-0262680523.{{cite book}}: صيانة CS1: التاريخ والسنة ( رابط )
↑ الحمام ، المعادلات 13-7.
↑ هوبكروفت وأولمان (1979 ، ص 169) المشار إليه في ( بيجون ، المعادلات 2، 3) .
^ جيش 2006 ، التعريف 3.12.
↑ جيتش 2006 ، النظرية 3.5.
↑ الحمامة ، المعادلة 12.

مراجع

ستيفن بيجون. "دالة الاقتران" . عالم الرياضيات .
ليسي، ميري (2007). "بعض الملاحظات حول دالة اقتران كانتور" . مجلة الرياضيات . 62 : 55-65 .
ريغان، كينيث و. (ديسمبر 1992). "دوال الاقتران ذات الحد الأدنى من التعقيد" . مجلة علوم الحاسوب والأنظمة . 45 (3): 285-295 . doi : 10.1016/0022-0000(92)90027-G . ISSN 0022-0000 .
سودزيك، ماثيو (2006). "دالة اقتران أنيقة" (ملف PDF) . szudzik.com . مؤرشف (ملف PDF) من الأصل بتاريخ 25 نوفمبر 2011. تم الاطلاع عليه بتاريخ 16 أغسطس 2021 .
Szudzik, Matthew P. (1 يونيو 2017). "دالة روزنبرغ-سترونغ للاقتران". arXiv : 1706.04129 [ cs.DM ].
جيتش، توماس (2006). نظرية المجموعات . سلسلة دراسات سبرينغر في الرياضيات (طبعة الألفية الثالثة ). سبرينغر-فيرلاغ. doi : 10.1007/3-540-44761-X . ISBN 3-540-44085-2.
هوبكروفت، جون إي .؛ أولمان، جيفري د. (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة (الطبعة الأولى ). أديسون-ويسلي. ISBN 0-201-02988-X.
شتاين، شيرمان ك. (1999). الرياضيات: الكون من صنع الإنسان ( الطبعة الثالثة). دوفر. ISBN 9780486404509.

[6] أي حقنة من $A^{2}\rightarrow A$ .

[12] يُستخدم مصطلح "الحجة القطرية" أحيانًا للإشارة إلى هذا النوع من التعداد، ولكنه لا يرتبط بشكل مباشر بحجة كانتور القطرية .

[1] حمامة :
تنشأ وظائف الاقتران بشكل طبيعي في البرهان على أن عدد الأعداد النسبية $\mathbb {Q}$ والأعداد الصحيحة غير السالبة $\mathbb {Z} _{\geq 0}$ هي نفسها، أي $|\mathbb {Q} |=|\mathbb {Z} _{\geq 0}|=\aleph _{0}$ ، والتي تعود في الأصل إلى كانتور.

[FOOTNOTEPigeon-2] حمامة .

[FOOTNOTELisi2007-3] 1 2 Lisi 2007 .

[FOOTNOTERegan1992-4] 1 2 ريغان 1992 .

[FOOTNOTESzudzik2006-5] 1 2 3 4 5 Szudzik 2006 .

[FOOTNOTESzudzik2017-7] Szudzik 2017 .

[FOOTNOTEPigeonEquation_8-8] 1 2 حمامة ، المعادلة 8.

[9] شتاين (1999 ، ص 448-452) نقلاً عن بيجون .

[10] روجرز، هارتلي (1 يناير 1967). نظرية الدوال التكرارية والحوسبة الفعالة . مطبعة معهد ماساتشوستس للتكنولوجيا. ص 64. ISBN 978-0262680523.{{cite book}}: صيانة CS1: التاريخ والسنة ( رابط )

[FOOTNOTEPigeonEquations_13-7-11] الحمام ، المعادلات 13-7.

[13] هوبكروفت وأولمان (1979 ، ص 169) المشار إليه في ( بيجون ، المعادلات 2، 3) .

[FOOTNOTEJech2006Definition_3.12-14] جيش 2006 ، التعريف 3.12.

[FOOTNOTEJech2006Theorem_3.5-15] جيتش 2006 ، النظرية 3.5.

[FOOTNOTEPigeonEquation_12-16] الحمامة ، المعادلة 12.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ أ ]

6

7

[ 8 ]

[ 9 ]

[ 10 ]

[ ب ]

11

[ 12 ]

[ 13 ]

[ 14 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗