תורה (לוגיקה מתמטית)
בלוגיקה מתמטית, תורה היא מערכת הכוללת שפה מסדר ראשון וקבוצה של אקסיומות. כל פסוק שאין לו משתנים חופשיים יכול לשמש כאקסיומה. כמו לשפה מסדר ראשון, לתורה אין "משמעות" - זוהי מערכת צורנית בלבד, המטפלת בפסוקים לפי כללים לוגיים קבועים. את הפירוש יוצקים בתורה רק כאשר בוחרים לה מודל.
בדרך כלל כוללים ברשימת האקסיומות גם את כל הטאוטולוגיות, שבהן מותר להציב כל פסוק.
דוגמאות
דוגמה. נבנה שפה מסדר ראשון עם שני יחסים, האחד אונארי (כלומר, בעל מקום אחד) שנסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} , והשני בינארי, שאותו נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . הפסוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists y\, (P(y) \land A(x,y))} אינו יכול לשמש כאקסיומה, משום שיש לו משתנה חופשי (x). הפסוק
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \forall x (\neg P(x) \to \exists y\, (P(y) \land A(x,y)))}
יכול לשמש אקסיומה, משום שאין לו משתנים חופשיים. גם
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \forall x \forall y\forall z(A(x,z)\land A(y,z)\implies P(z))}
היא אקסיומה אפשרית.
כמודל לתורה זו, אפשר לחשוב על קבוצת האנשים והצלחות במסעדה, כאשר היחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} מתקיים רק עבור הצלחות, והיחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(x,y)} פירושו ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x,y} מצויים באותו שולחן. במקרה זה, האקסיומה הראשונה אומרת שכל סועד יושב בשולחן עליו יש צלחת, והאקסיומה השנייה אומרת שכל סועד יושב בשולחן משלו (אם x ו-y סועדים היושבים יחד, אפשר לבחור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z=x} ולהסיק ש- הפענוח נכשל (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 *} וקבוע אחד, שסימנו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} , ואת הסימן של יחס השוויון, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =} . האקסיומות המגדירות חבורה הן:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \forall x\, \forall y\, \forall z\, ((x*y)*z=x*(y*z))} (אסוציאטיביות);
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \forall x\, (x*1=x \land 1*x=x)} (קיום איבר יחידה);
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \forall x\, \exists y\, (x*y=1 \land y*x=1)} (קיום איבר הופכי).
דוגמה מפורסמת לתורה לוגית היא אריתמטיקת פאנו, שהיא תורה המתוכננת לדיון במספרים טבעיים. בשפה שלה יש רק קבוע אחד (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} ), פונקציה אונארית אחת (פונקציית העוקב), יחס השוויון, וכמה סכימות פשוטות לגזירה של אקסיומות. במאמץ-מה אפשר להגדיר בשפה הזו חיבור וכפל, ואז ניתן לנסח בה חלק משמעותי של הטענות באריתמטיקה. תורה כזו, או חזקה ממנה, נקראת תורה אריתמטית.
דוגמה חשובה אחרת, אולי החשובה ביותר, היא זו של תורת הקבוצות האקסיומטית: בשפה יש רק יחס בינארי אחד (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \in} ) ששמו 'שייכות', ומספר לא גדול של סכימות לגזירת אקסיומות. מערכת האקסיומות היסודית היא מערכת צרמלו-פרנקל, ואותה מסמנים ב-ZF. כאשר מוסיפים לה את אקסיומת הבחירה שהיא:
- לכל הפענוח נכשל (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 f} מ-הפענוח נכשל (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 x} שעבורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(a) \in f(a)} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in x} ,
מתקבלת המערכת ZFC (האות C מגיעה מהמלה האנגלית choice). כדי לקבל כאן פסוק חוקי, צריך לפרוש את המושג "פונקציה מ-הפענוח נכשל (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 \phi \land \neg \phi} נקראת תורה עקבית. בתורה שאיננה עקבית אפשר להוכיח כל פסוק, ולכן קשה למצוא בכאלה עניין רב. תורה שבה, לכל פסוק נטול משתנים חופשיים, אפשר להוכיח את הפסוק או את שלילתו, נקראת תורה שלמה. תורה שיש לה מודל יחיד (עד כדי איזומורפיזם) מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} -קטגורית. תורה שאין לה מודלים סופיים והיא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} -קטגורית (לאיזשהי עוצמה אינסופית הגדולה או שווה לעוצמת השפה) היא שלמה. תורה היא אריתמטית אם יש לה מודל שמכיל מודל שאיזומורפי לאריתמטיקה החלשה (קבוצת הטבעיים יחד עם 4 פעולות חשבון, פונקציה אונרית "עוקב של" והיחסים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <} . לאריתמטיקה החלשה 7 אקסיומות שהן אקסיומות פיאנו למעט אקסיומת האינדוקציה שהיא מסדר שני).
משפטי אי השלמות של גדל קובעים שתורה אריתמטית, אפקטיבית ועקבית לא יכולה להיות שלמה (משפט גדל הראשון). במשפט השני הראה שלא ניתן להוכיח את עקביותה של תורה כזו בעזרת האקסיומות שלה.
בהינתן מבנה מתמטי בשפה מסדר ראשון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , התורה השלמה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} בשפה זו היא אוסף כל הנוסחאות המסתפקות על ידי המודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} ; תורה זו מסומנת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{Th}(M)} . זו תמיד תורה שלמה, וכל מודל שלה שקול אלמנטרית ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} ; אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} אינסופי, ייתכנו מודלים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{Th}(M)} שאינם איזומורפיים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} . למשל, קיימים מודלים של התורה השלמה של המספרים הטבעיים (בשפת אריתמטיקת פאנו) שאינם איזומורפיים להם - המודלים הלא סטנדרטיים של האריתמטיקה.
ראו גם
