הצגת המקור של הדף "תורה (לוגיקה מתמטית)"

ב[[לוגיקה מתמטית]], '''תורה''' היא מערכת הכוללת [[שפה מסדר ראשון]] וקבוצה של '''[[אקסיומה|אקסיומות]]'''. כל [[פסוק (לוגיקה מתמטית)|פסוק]] שאין לו משתנים חופשיים יכול לשמש כאקסיומה. כמו לשפה מסדר ראשון, לתורה אין "משמעות" – זוהי מערכת צורנית בלבד, המטפלת בפסוקים לפי כללים לוגיים קבועים. את הפירוש יוצקים בתורה רק כאשר בוחרים לה [[מודל (לוגיקה מתמטית)|מודל]].

בדרך כלל כוללים ברשימת האקסיומות גם את כל ה[[טאוטולוגיה (לוגיקה)|טאוטולוגיות]], שבהן מותר להציב כל פסוק.

==דוגמאות==
'''דוגמה'''. נבנה שפה מסדר ראשון עם שני יחסים, האחד אונארי (כלומר, בעל מקום אחד) שנסמן ב-<math>P</math>, והשני בינארי, שאותו נסמן ב-<math>A</math>. הפסוק <math>\exists y\,(P(y)\and A(x,y))</math> אינו יכול לשמש כאקסיומה, משום שיש לו משתנה חופשי (x). הפסוק
:<math>\forall x\,(\neg P(x)\to\exists y\,(P(y)\and A(x,y)))</math>
יכול לשמש אקסיומה, משום שאין לו משתנים חופשיים. גם
:<math>\forall x\,\forall y\,\forall z:\quad(A(x,z)\and A(y,z))\implies P(z)</math>
היא אקסיומה אפשרית.

כמודל לתורה זו, אפשר לחשוב על קבוצת האנשים והצלחות במסעדה, כאשר היחס <math>P</math> מתקיים רק עבור הצלחות, והיחס <math>A(x,y)</math> פירושו כי <math>x,y</math> מצויים באותו שולחן, כלומר בפרט <math>A(x,y)</math> הוא [[יחס שקילות]]. במקרה זה, האקסיומה הראשונה אומרת שכל סועד יושב בשולחן עליו יש צלחת, והאקסיומה השנייה אומרת שכל סועד יושב בשולחן משלו (אם <math>x,y</math> סועדים היושבים יחד, אפשר לבחור <math>z=x</math> ולהסיק כי <math>x</math> הוא צלחת).

כדוגמה נוספת, [[תורת החבורות]] עוסקת ב[[מבנה אלגברי|מבנים אלגבריים]] הנקראים [[חבורה (מבנה אלגברי)|חבורות]]. מבנים אלה הם מודלים לתורה, שהשפה שלה כוללת [[פונקציה בינארית]] אחת <math>*</math> קבוע אחד <math>e</math>, ואת הסימן של יחס השוויון, <math>=</math>. האקסיומות המגדירות חבורה הן:
*[[פעולה אסוציאטיבית|אסוציאטיביות]]: <math>\forall x\,\forall y\,\forall z:\quad(x*y)*z=x*(y*z)</math>
*קיום [[איבר יחידה]]: <math>\forall x:\quad x*e=e*x=x</math>
*קיום [[איבר הופכי]]: <math>\forall x\,\exists y:\quad x*y=y*x=e</math>
דוגמה מפורסמת לתורה לוגית היא [[מערכת פאנו|אריתמטיקת פאנו]], שהיא תורה המתוכננת לדיון ב[[מספר טבעי|מספרים טבעיים]]. בשפה שלה יש רק קבוע אחד (<math>0</math>), פונקציה אונארית אחת (פונקציית העוקב), יחס השוויון, וכמה סכימות פשוטות לגזירה של אקסיומות. במאמץ מה אפשר להגדיר בשפה הזו חיבור וכפל, ואז ניתן לנסח בה חלק משמעותי של הטענות ב[[אריתמטיקה]]. תורה כזו, או חזקה ממנה, נקראת '''תורה אריתמטית'''.

דוגמה חשובה אחרת, אולי החשובה ביותר, היא זו של [[תורת הקבוצות האקסיומטית]]: בשפה יש רק [[יחס (תורת הקבוצות)|יחס בינארי]] אחד (<math>\in</math>) ששמו 'שייכות', ומספר לא גדול של סכימות לגזירת אקסיומות. מערכת האקסיומות היסודית היא [[תורת הקבוצות האקסיומטית#האקסיומות של תורת הקבוצות|מערכת צרמלו-פרנקל]], ואותה מסמנים ב-ZF. כאשר מוסיפים לה את [[אקסיומת הבחירה]] שהיא:
*לכל <math>x</math> ולכל פונקציה <math>f</math> מ-<math>x</math>, קיימת פונקציה מ-<math>x</math> שעבורה <math>g(a)\in f(a)</math> לכל <math>a\in x</math>
מתקבלת המערכת ZFC (האות C מגיעה מהמלה ה[[אנגלית]] choice). כדי לקבל כאן פסוק חוקי, צריך לפרוש את המושג "פונקציה מ-<math>x</math>" לביטוי המכיל רק את היחס "שייך"; זהו תרגיל קל יחסית.

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

תורה שבה לא ניתן [[הוכחה (לוגיקה מתמטית)|להוכיח]] אף פסוק מן הצורה <math>\phi\and\neg\phi</math> נקראת [[עקביות (לוגיקה)|תורה עקבית]]. בתורה שאיננה עקבית אפשר להוכיח '''כל''' פסוק, ולכן קשה למצוא בכאלה עניין רב. תורה שבה, לכל פסוק נטול משתנים חופשיים, אפשר להוכיח את הפסוק או את שלילתו, נקראת [[שלמות|תורה שלמה]]. תורה שיש לה מודל יחיד (עד כדי איזומורפיזם) מ[[עוצמה (מתמטיקה)|עוצמה]] <math>\kappa</math> היא <math>\kappa</math>-קטגורית. תורה שאין לה מודלים סופיים והיא <math>\kappa</math>-קטגורית (לאיזושהי עוצמה אינסופית הגדולה או שווה לעוצמת השפה) היא שלמה. תורה היא אריתמטית אם יש לה מודל שמכיל מודל שאיזומורפי לאריתמטיקה החלשה (קבוצת הטבעיים יחד עם 4 פעולות חשבון, פונקציה אונרית "עוקב של" והיחסים <math>=,<</math>. לאריתמטיקה החלשה 7 אקסיומות שהן אקסיומות פיאנו למעט [[אינדוקציה מתמטית|אקסיומת האינדוקציה]] שהיא מסדר שני).

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

בהינתן [[מודל (לוגיקה מתמטית)|מבנה]] מתמטי  בשפה מסדר ראשון <math>L</math>, '''התורה השלמה''' של <math>M</math> בשפה זו היא אוסף כל הנוסחאות המסתפקות על ידי המודל <math>M</math>; תורה זו מסומנת <math>\text{Th}(M)</math>. זו תמיד תורה שלמה, וכל מודל שלה [[שקילות אלמנטרית|שקול אלמנטרית]] ל-<math>M</math>; אם <math>M</math> אינסופי, ייתכנו [[מודל (לוגיקה מתמטית)|מודלים]] של <math>\text{Th}(M)</math> שאינם [[איזומורפיזם|איזומורפיים]] ל-<math>M</math>. למשל, קיימים מודלים של התורה השלמה של [[מספרים טבעיים|המספרים הטבעיים]] (בשפת [[אריתמטיקה|אריתמטיקת פאנו]]) שאינם איזומורפיים להם – המודלים הלא-סטנדרטיים של האריתמטיקה.

==ראו גם==
*[[שפה מסדר ראשון]]
*[[מודל (לוגיקה מתמטית)]]
*[[הוכחה (לוגיקה מתמטית)]]

[[קטגוריה:לוגיקה מתמטית]]