תורה (לוגיקה מתמטית) – הבדלי גרסאות

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