מערכת פאנו

מערכת פּאַנוֹ היא מערכת מתמטית, המהווה מודל פורמלי של המספרים הטבעיים. המערכת בנויה על שני מושגי יסוד: איבר האפס ופעולת ה"עוקב". משני מושגים אלה מאפשרת אקסיומה מיוחדת לבנות, באינדוקציה, את פעולות החיבור והכפל. מערכת פאנו היא מערכת המספרים הבסיסית ביותר, וממנה אפשר לבנות את המספרים השלמים, את המספרים הרציונליים, ואת שאר מערכות המספרים. את האקסיומות הציע המתמטיקאי האיטלקי ג'וזפה פאנו בשנת 1889.

מערכת פאנו מהווה ניסוח אקסיומטי ראשון למספרים הטבעיים, שעד סוף המאה ה-19 נחשבו יסודיים במידה שאין למעלה ממנה. האקסיומות, הכתובות בלוגיקה מסדר שני, מתארות את המספרים הטבעיים בדיוק כזה, עד שקיימת רק מערכת אחת המקיימת אותן (עד כדי איזומורפיזם). לגרסאות חלשות יותר, הכוללות רק אקסיומות בלוגיקה מסדר ראשון, יש גם מודלים לא־סטנדרטיים.

הגדרה פורמלית

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

למערכת פאנו שלושה מרכיבים – קבוצה $\mathbb {N}$ , קבוע $0\in \mathbb {N}$ , ופעולה $S:\mathbb {N} \to \mathbb {N}$ , המקיימים את האקסיומות הבאות (בעברית נקרא לפעולה זו "פעולת העוקב"):

1. קיים $0\in \mathbb {N}$ כך שלכל $x\in \mathbb {N}$ לא מתקיים $S(x)=0$ (כלומר 0 הוא אבר ראשון במערכת).
2. לכל שני אברים $x,y\in \mathbb {N}$ , אם $S(x)=S(y)$ אז גם $x=y$ (כלומר $S$ פונקציה חד-חד-ערכית).
3. תת־הקבוצה היחידה $K\subseteq \mathbb {N}$ המקיימת את התכונות
   • $0\in K$
   • לכל אבר $x\in \mathbb {N}$ , אם $x\in K$ אז גם $S(x)\in K$

היא $\mathbb {N}$ עצמה. (זוהי אקסיומת האינדוקציה).

המספר 1 מוגדר במערכת הזו כעוקב של אפס, 2 מוגדר כעוקב של 1, וכן הלאה. לאחר שמגדירים את פעולת החיבור, אפשר לראות בפעולת העוקב הוספת אחד, כלומר $S(x)=x+1$ . האקסיומה השלישית, המאפשרת להגדיר ולהוכיח טענות באינדוקציה, היא ליבה של המערכת. כיוון שהאקסיומה מונה על כל תת־קבוצה $K$ , היא אינה כתובה בלוגיקה מסדר ראשון. בתורת המודלים וההוכחות הפורמליות קל יותר לנתח מערכות מסדר ראשון, ואכן קיימת גרסה המחליפה את האקסיומה השלישית בסכמת אקסיומות, כדלקמן.

3'. לכל נוסחה $\phi (x,y_{1},\ldots ,y_{k})$ בשפה, קיימת האקסיומה

$\forall {\bar {y}}{\bigl (}\phi (0,{\bar {y}})\land \forall x{\bigl (}\phi (x,{\bar {y}})\Rightarrow \phi (S(x),{\bar {y}}){\bigr )}\Rightarrow \forall x\phi (x,{\bar {y}}){\bigr )}$

כאשר ${\bar {y}}$ הוא קיצור עבור $y_{1},\ldots ,y_{k}$ .

בלוגיקה מסדר ראשון לא ניתן למנות על "כל קבוצה", כפי שעושה האקסיומה השלישית. סכימת האקסיומות, הכוללת מספר בן-מניה של אקסיומות מסדר ראשון (אחת לכל נוסחה), מבטאת את אותה טענה, אבל מסתפקת בקבוצות שהן, במובן של הלוגיקה הפורמלית, ניתנות להגדרה. האקסיומה קובעת שאם 0 מקיים תכונה מסוימת, ולכל $x$ המקיים אותה גם $x+1$ מקיים אותה, אז התכונה מתקיימת לכל $x$ .

המערכת הכוללת את שתי האקסיומות 1 ו־2 לעיל ואת סכימת האקסיומות 3 נקראת אריתמטיקת פאנו, ומסומנת בדרך־כלל באותיות PA.

הגדרת פעולות החשבון

אקסיומת האינדוקציה מאפשרת להגדיר פונקציות באופן רקורסיבי.

החיבור ($+$) הוא פעולה בינארית המוגדרת באופן הבא:

• בסיס: לכל $x$ טבעי מתקיים $x+0=x$ .
• השלב הרקורסיבי: לכל $x,y$ טבעיים מתקיים $x+S(y)=S(x+y)$ .

הכפל ($\cdot$) הוא פעולה בינארית המוגדרת באופן הבא:

• בסיס: לכל $x$ טבעי מתקיים $x\cdot 0=0$ .
• השלב הרקורסיבי: לכל $x,y$ טבעיים מתקיים $x\cdot S(y)=x+(x\cdot y)$ .

באמצעות פעולת החיבור ניתן להגדיר את יחס הסדר המוכר על הטבעיים: לכל שני מספרים טבעיים $x,y$ מתקיים $x\leq y$ אם ורק אם קיים מספר טבעי $z$ עבורו $x+z=y$ .

מהגדרה זו מקבלים שהעוקב של 0, $S(0)$ הוא איבר יחידה ביחס לכפל (לכל $x$ טבעי מתקיים: $x\cdot S(0)=x+(x\cdot 0)=x+0=x$), וסימונו המקובל הוא 1. מהגדרת החיבור נובע $S(x)=x+1$ . לפי הסימון החדש פעולת החיבור מוגדרת לפי $x+(y+1)=(x+y)+1$ ופעולת הכפל מוגדרת $x\cdot (y+1)=x+(x\cdot y)$ .

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

מודלים

ריכרד דדקינד הוכיח שמערכת האקסיומות של פאנו (עם אקסיומת האינדוקציה מסדר שני) היא קטגורית, כלומר: כל שני מודלים של מערכת זו הם איזומורפיים. בניסוח פורמלי יותר: אם $\ <\omega _{A},0_{A},S_{A}>$ ו- $\ <\omega _{B},0_{B},S_{B}>$ הם שני מודלים של מערכת פאנו, אז הפונקציה $\ f:\omega _{A}\to \omega _{B}$, המוגדרת (על-פי אקסיומת האינדוקציה של המערכת הראשונה) על ידי $\ f(0_{A})=0_{B},f(S_{A}(x))=S_{B}(f(x))$, היא איזומורפיזם בין המבנים.

מודלים לא סטנדרטיים

המספרים הטבעיים מהווים כמובן מודל של אקסיומות פאנו. כאשר מחליפים את אקסיומת האינדוקציה המלאה בגרסתה שמסדר ראשון, נכנס לפעולה משפט הקומפקטיות (החל על מערכות שהאקסיומות שלהן מסדר ראשון), שלפיו יש למערכת גם מודלים לא סטנדרטיים. לפי משפט לוונהיים-סקולם יש למערכת לא רק מודל בן-מניה, אלא גם מודלים מכל עוצמה אינסופית שהיא. כאשר מפרשים את תוצאת הקטגוריוּת של דדקינד במערכת מסדר ראשון, ההוכחה מראה שבתוך כל מודל של תורת הקבוצות, יש מודל יחיד לאריתמטיקת פאנו שהוא "הקטן ביותר" - הוא משוכן ברישא של כל מודל אחר של האריתמטיקה. במודל לא סטנדרטי של תורת הקבוצות מתקבל מודל לא סטנדרטי של האריתמטיקה, ומאלה אי-אפשר להימנע באמצעות הוספה של אקסיומות מסדר ראשון.

הגדרת המספרים הטבעיים על-פי האקסיומות של תורת הקבוצות

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

• נגדיר את המספר 0 כקבוצה הריקה $\emptyset$.
• לכל קבוצה A נגדיר את העוקב של A על ידי: $\ S(A)=A\cup \{A\}$

בדרך זו נקבל:

$\ 0=\emptyset$

$1=S(0)={\{\emptyset \}}=\{0\}$

$\ 2=S(S(0))=\{\emptyset ,\{\emptyset \}\}=\{0,1\}$

$\ 3=S(S(S(0))=\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\}=\{0,1,2\}$

וכן הלאה.

עתה, נגדיר קבוצה אינדוקטיבית: קבוצה אינדוקטיבית היא קבוצה המכילה את 0 (הקבוצה הריקה) וכן, עבור כל איבר בקבוצה, היא מכילה את העוקב לו. אזי, קבוצת המספרים הטבעיים $\ \omega$ מוגדרת כקבוצה האינדוקטיבית הקטנה ביותר (המתקבלת מחיתוך של כל הקבוצות האינדוקטיביות).

כעת ניתן להגדיר על הטבעיים סדר חלקי פשוט באמצעות הכלה (כהגדרתה בתורת הקבוצות) באופן הבא: לכל x,y טבעיים נגדיר $x\leq y$ אם ורק אם $x\subseteq y$. לפי עקרון הסדר הטוב זהו סדר טוב.

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

• מערכת פאנו, באתר MathWorld (באנגלית)
• First Order Arithmetic