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

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

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

הגדרה

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.}

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

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

הגדרה

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.}

כאשר מחשבים פונקציית זיווג על המספרים $k_{1}$ ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_2} נהוג לסמן את התוצאה באמצעות סוגריים זוויתיים
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle k_1, k_2 \rangle \,.}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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})$

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

בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z = \langle x, y \rangle = \frac{(x + y)(x + y + 1)}{2} + y }

נמצא את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} .

נגדיר:

• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w=x+y}
• $t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}}$

אז מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z=t+y} .

נפתור את המשוואה הריבועית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^2+w-2t=0} הנובעת מהגדרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} , ונקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w=\frac{\sqrt{8t+1}-1}{2}} , מכיוון ש$w\geq 0$.

נשתמש בכך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\leq z=t+y<t+(w+1)=\frac{(w+1)^2+(w+1)}{2}} . הפתרון של אי שוויון זה הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w+1>\frac{\sqrt{8z+1}-1}{2}} . נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\leq\frac{\sqrt{8z+1}-1}{2}<w+1}

מכך נובע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w=\left\lfloor{\frac{\sqrt{8z+1}-1}{2}}\right\rfloor} , ומצאנו את $w$. כעת נחשב:

• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=\frac{w^2+w}{2}}
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=z-t}
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=w-y}

מצאנו זוג יחיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y)=\left(\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor -z+\frac{\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor ^2+\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor }{2},z-\frac{\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor ^2+\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor }{2}\right)} המקיים $\pi (x,y)=z$, לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} חד חד ערכית ועל.

קישורים חיצוניים

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

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

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