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

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

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

הגדרהעריכה

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

 

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

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

הגדרהעריכה

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

 

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

 

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

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

 

כדלהלן:

 


היפוך פונקציית הזיווגעריכה

בהינתן   כך ש-  

נמצא את   ו- .

נגדיר:

  •  
  •  

אז מתקיים  .

נפתור את המשוואה הריבועית   הנובעת מהגדרת  , ונקבל  , מכיוון ש .

נשתמש בכך שמתקיים  . הפתרון של אי שוויון זה הוא  . נקבל:

 

מכך נובע  , ומצאנו את  . כעת נחשב:

  •  
  •  
  •  

מצאנו זוג יחיד   המקיים  , לכן   חד חד ערכית ועל.

קישורים חיצונייםעריכה