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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

פונקציית הזיווג של קנטור[עריכת קוד מקור | עריכה]

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

הגדרה[עריכת קוד מקור | עריכה]

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

\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 נהוג לסמן את התוצאה באמצעות סוגריים זוויתיים
\langle k_1, k_2 \rangle \,.

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

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

כדלהלן:

\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n) \,.

היפוך פונקציית הזיווג[עריכת קוד מקור | עריכה]

בהינתן 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 באופן הבא: y := z - \frac{w(w + 1)}{2}

ונגדיר את x באופן הבא: x := w - y
x מוגדר היטב מכיוון ש-w => y (נניח בשלילה שלא ונקבל סתירה להגדרת w).

ונקבל כי
\langle x, y \rangle \, = \frac{1}{2}(x + y)(x + y + 1)+y = \frac{w(w + 1)}{2} + y = \frac{w(w + 1)}{2} + z - \frac{w(w + 1)}{2} = z

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