בתשובה לאורי גוראל-גורביץ', 20/07/05 23:18
יש ביקוש! 318832
(ומה זה בכלל "אלגוריתם שמכריע תקפות"?
יש ביקוש! 318842
א. ראה תגובתי לסמיילי.
ב. לגבי חיסול כמתים:
ננסה לתת דוגמא פשוטה. השפה שלנו תכלול יחס אחד "≤" ואת יחס השיוויון, שבד"כ מתיחסים אליו כחלק מהלוגיקה.
התורה שלנו תכלול את האקסיומות שאומרות ש"≤" הוא יחס סדר מלא, שהן

לכל a,b,c מתקיים:

if a ≤ b and b ≤ a then a = b (antisymmetry)
if a ≤ b and b ≤ c then a ≤ c (transitivity)
a ≤ b or b ≤ a (totalness)

בנוסף ניקח את האקסיומה שהסדר הנ"ל "צפוף":
לכל a,b קיים c כך ש:

if a≤b and not a=b then a≤c and not a=c and c≤b and not b=c

כלומר בין כל שתי נקודות יש נקודה.

בנוסף ניקח את האקסיומה שאומרת שאין נקודות קצה:
לכל a יש b,c כך ש:

b≤a and not b=a and a≤c and not a=c

כלומר לכל נקודה יש גדולה ממנה וקטנה ממנה.

התורה הנ"ל נקראת תורה של סדר מלא צפוף ללא מקודות קצה.

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

2) בגלל זה כתבתי "צפוף" במרכאות כפולות. פשוט נוהגים לכנות את התכונה הזו כך.
יש ביקוש! 318964
תודה.:)
אני באמת מצפה להמשך, אבל רק אם תהיה לך סבלנות.
יש ביקוש! 318853
את השויון אתה יכול להגדיר ע"י הפסוק הראשון שלך "(if a ≤ b and b ≤ a then a = b)" ברוח מה שהזכרתי כאן לא מזמן, כך שאינך זקוק לו כחלק מהשפה מלכתחילה. לא?
יש ביקוש! 318930
לא. היית יכול לצרף לשפה יחס, ולסמן אותו בסימן "=", ולציין ש"(if a ≤ b and b ≤ a then a = b)", אבל זה לא היה אומר ששני אובייקטים שיש ביניהם היחס = חייבים להיות באמת שווים במודל המתואר ע"י האקסיומות.

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

עכשיו, יכולת לנסות ולהוסיף אקסיומות לגבי = שהיו "מכריחות" אותו להיות מה שאתה כן רוצה: שני אובייקטים במודל הם שווים רק אם הם אותו אובייקט. למרבה הצער, בשפה מסדר ראשון לא ניתן לעשות זאת. לכן, כפי שאורי הזכיר, מתייחסים לסימן = כאל חלק מהלוגיקה: הוא לא אחד הסימנים שיש לך זכות להתאים להם איזה יחס שאתה רוצה, אלא אחד הסימנים (כמו הסימן "וגם" או "לכל") שהמשמעות שלהם קבועה; בכל מודל של התורה, "=" תמיד מציין שוויון בין איברי המודל.
יש ביקוש! 318943
אני חושב שהבנתי, תודה. עכשיו אני צריך לחשוב למה זה לא מפריע במקומות אחרים.
יש ביקוש! 318961
רק רציתי להוסיף ששום דבר משמעותי לא היה משתנה אם היינו עובדים עם = בתור יחס רגיל שמקיים את כל האקסיומות הנכונות - שהוא יחס שקילות ושאם a=b אז אפשר להחליף a ב-b בכל מקום שרוצים. היינו נאלצים לשנות קצת את ההגדרות של איזומורפיזם של מודלים אבל לא יותר מזה.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים