הצגת המקור של הדף "לוגיקה מסדר שני"

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

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

בלוגיקה מסדר שני אפשר לבטא את העובדה "<math>A</math> סופית" - כי המשמעות של עובדה זו היא שכל [[פונקציה חח"ע]] מ-<math>A</math> לעצמו היא גם [[פונקציה על|על]]. באופן דומה, ניתן לבטא גם את העובדה "<math>A</math> [[קבוצה בת מנייה|בת מנייה]]" - כי אז בין כל שתי תתי-קבוצות אינסופיות של <math>A</math> יש פונקציה חח"ע ועל. שני המושגים האלו אינם ניתנים לביטוי בלוגיקה מסדר ראשון, לפי [[משפט הקומפקטיות]] ו[[משפט לוונהיים-סקולם]], ולכן שני המשפטים האלו אינם מתקיימים בלוגיקה מסדר שני. 

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

== כללי הסקה ==
קיימות מספר מערכות אפשריות של כללי הסקה ללוגיקה מסדר שני, אף אחת מהן איננה [[משפט השלמות של גדל|שלמה]]. מערכות אלו הן ''תקפות'' כלומר אינן יכולות להוכיח משפט שגוי. 

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

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

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

== קשר למונים גדולים ==
תחת הנחת קיום של [[מונה גדול|מונים גדולים]] ניתן להוכיח כי גרסאות של המשפטים הקלאסיים של הלוגיקה מסדר ראשון עדיין מתקיימים גם בלוגיקה מסדר שני. כך למשל [[מנחם מגידור|מגידור]] הוכיח כי [[מונה על-קומפקטי|המונה העל-קומפקטי]] הראשון (אם קיים אחד), ניתן לאפיון כמונה המינימלי בו לכל מודל מ[[עוצמה (מתמטיקה)|עוצמה]] גדולה או שווה מהמונה ולכל משפט בשפה מסדר שני <math>\Phi</math> שמכיל רק כמת "לכל" אחד מסדר שני (וכמתים רבים כרצוננו מסדר ראשון), יש [[תת-מודל]] מעוצמה קטנה מהמונה בו <math>\Phi</math> מתקיים. 

מצד שני, אם <math>\kappa</math> על-קומפקטי, אז לכל משפט בלוגיקה מסדר כלשהו שמתקיים במודל <math>M</math>, כאשר  <math>|M| \ge \kappa</math> יש תת-מודל <math>N</math> של <math>M</math>, בו <math>|N| < \kappa</math>, ו-<math>N</math> מקיים את המשפט. 

באופן דומה, מונה הוא [[מונה קומפקטי חלש|קומפקטי-חלש]] אם ורק אם כל פסוק מסדר שני במבנה <math>\langle V_\kappa,\in,R \rangle</math> (עבור יחס <math>R</math> שמייצג תת-קבוצה כלשהי של <math>V_\kappa</math>), בו יש רק כמת כולל בודד על משתנה מסדר שני וכל שאר הכמתים הם מסדר ראשון ''משתקף'', כלומר מתקיים גם במבנה <math>\langle V_\alpha,\in,R \cap V_\alpha \rangle</math> עבור סודר <math>\alpha < \kappa</math>.

== ראו גם ==

* [[אריתמטיקה מסדר שני]] {{אנ|second order arithmetic}}
* [[מתמטיקה הפוכה]] {{אנ|reverse mathematics}}

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

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:לוגיקה מתמטית]]

[[fr:Logique d'ordre supérieur#Logique du second ordre]]