פונקציית זיווג
(הופנה מהדף פונקציית הזיווג של קנטור)
ערך מחפש מקורות | |
במתמטיקה, פונקציית זיווג היא תהליך המקודד באופן ייחודי שני מספרים טבעיים למספר טבעי יחיד.
כל פונקציית זיווג יכולה לשמש בתורת הקבוצות על מנת להוכיח כי לקבוצת המספרים השלמים ולקבוצת המספרים הרציונליים עוצמה זהה לעוצמה של הטבעיים.
הגדרה
פונקציית זיווג היא פונקציה פרימיטיבית רקורסיבית חד-חד-ערכית ועל:
פונקציית הזיווג של קנטור
הגדרה
פונקציית הזיווג של קנטור היא פונקציית זיווג
מוגדרת כדלהלן:
כאשר מחשבים פונקציית זיווג על המספרים נהוג לסמן את התוצאה באמצעות סוגריים זוויתיים .
ניתן להכליל את הפונקציה הנ"ל לפונקציית הווקטור של קנטור
כדלהלן:
היפוך פונקציית הזיווג
בהינתן עבורו , נמצא את .
נגדיר:
אז מתקיים .
נפתור את המשוואה הריבועית הנובעת מהגדרת , ונקבל , מאחר ש-.
נשתמש בכך שמתקיים . הפתרון של אי-שוויון זה הוא . נקבל:
מכך נובע . כעת נחשב:
מצאנו זוג יחיד המקיים , לכן חד-חד-ערכית ועל.
קישורים חיצוניים
- String Module Error: Target string is empty.html פונקציית זיווג, באתר MathWorld (באנגלית) המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.