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

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

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

הגדרה

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

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

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

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

הגדרה

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

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

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

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

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

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

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

כדלהלן:

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

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

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

נמצא את $x,y$.

נגדיר את $w$ להיות המספר הטבעי המקסימלי עבורו ${\frac {w(w+1)}{2}}<z$.

$w$ מוגדר היטב מכיוון שקבוצת כל המספרים המשולשיים היא אינסופית וחלקית לטבעיים ולכן סדורה היטב.

נגדיר $y:=z-{\frac {w(w+1)}{2}},\ x:=w-y$

$x$ מוגדר היטב מכיוון ש־$w\geq y$ (נניח בשלילה שלא ונקבל סתירה להגדרת $w$).

ונקבל כי

$\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y={\frac {w(w+1)}{2}}+y={\frac {w(w+1)}{2}}+z-{\frac {w(w+1)}{2}}=z$

ולכן מצאנו זוג יחיד $x,y$ המהווה מקור ל־$z$ ולכן פונקציית הזיווג היא הפיכה ולכן ח.ח.ע ועל.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0