פונקציית זיווג

	ערך מחפש מקורות
	רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים. אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים. אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.

במתמטיקה, פונקציית זיווג היא תהליך המקודד באופן ייחודי שני מספרים טבעיים למספר טבעי יחיד.

כל פונקציית זיווג יכולה לשמש בתורת הקבוצות על מנת להוכיח כי לקבוצת המספרים השלמים ולקבוצת המספרים הרציונליים עוצמה זהה לעוצמה של הטבעיים.

פונקציית זיווג היא פונקציה פרימיטיבית רקורסיבית חד-חד-ערכית ועל:

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

פונקציית הזיווג של קנטור היא פונקציית זיווג

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

מוגדרת כדלהלן:

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

כאשר מחשבים פונקציית זיווג על המספרים ${\displaystyle k_{1},k_{2}$ נהוג לסמן את התוצאה באמצעות סוגריים זוויתיים ${\displaystyle \langle k_{1},k_{2}\rangle }$.

ניתן להכליל את הפונקציה הנ"ל לפונקציית הווקטור של קנטור

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

כדלהלן:

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

בהינתן ${\displaystyle z}$ עבורו ${\displaystyle z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}+y}$, נמצא את ${\displaystyle x,y}$.

נגדיר:

${\displaystyle {\begin{aligned}w=x+y\\t={\frac {w(w+1)}{2}={\frac {w^{2}+w}{2}\end{aligned}$

אז מתקיים ${\displaystyle z=t+y}$.

נפתור את המשוואה הריבועית ${\displaystyle w^{2}+w-2t=0}$ הנובעת מהגדרת ${\displaystyle t}$, ונקבל ${\displaystyle w={\frac {\sqrt {8t+1}-1}{2}$, מאחר ש-${\displaystyle w\geq 0}$.

נשתמש בכך שמתקיים ${\displaystyle t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}$. הפתרון של אי-שוויון זה הוא ${\displaystyle w+1>{\frac {\sqrt {8z+1}-1}{2}$. נקבל:

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

מכך נובע ${\displaystyle w=\left\lfloor {\frac {\sqrt {8z+1}-1}{2}\right\rfloor }$. כעת נחשב:

${\displaystyle {\begin{aligned}t={\frac {w^{2}+w}{2}\\(x,y)=(w-y,z-t)\end{aligned}$

מצאנו זוג יחיד המקיים ${\displaystyle \pi (x,y)=z}$, לכן ${\displaystyle \pi }$ חד-חד-ערכית ועל.

• פונקציית זיווג, באתר MathWorld (באנגלית)