בתשובה לגדי אלכסנדרוביץ', 28/09/05 21:59
רגע 333504
(הדגמה לזה שמתמטיקאים מתחמקים מעיסוק בהגדרות עקרוניות)

זו לא הגדרה מוצלחת, כי היא רקורסיבית (אתה מגדיר "מרכיב" במונחי אותו מושג). בהקשרים מסויימים זה רעיון מצוין‏1, אבל בתור כלל אצבע, הייתי אומר שאפשר להשתמש בהגדרות כאלה רק כשברור שאפשר להסתדר גם בלעדיהן; מצד שני, אם *אפשר* להסתדר בלעדיהן, אז הגדרות רקורסיביות הן כלי מאד מוצלח ואלגנטי.

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

1 למשל: הדוגמא הראשונה שהתגלתה לחבורה (נוצרת סופית) עם גידול‏2 שאיננו פולינומיאלי וגם איננו אקספוננציאלי, נראית בערך כך: זוהי החבורה שנוצרת על-ידי האיברים a,b,c,d, כאשר
a=(1,b), b=(c,1), c=(d,d), d=(1,a).

2 חבורה היא הרי אוסף של מכפלות (תמיד סופיות) של ה"יוצרים" שלה, אלא שבדרך כלל יש כפילויות, למשל abab=baba. ב"גידול" הכוונה היא לשאלה כמה מהר גדלה הפונקציה (f(n שסופרת כמה איברים שונים יש מאורך n.
רגע 333776
לא הבנתי את כלל האצבע. יש כל מיני סדרות שמוגדרות רק ע"י הגדרה רקורסיבית. למשל:

A(n) = 3A(n-1) + 1 .... for A(n-1) odd
A(n) = 1/2 * A(n-1) .... for A(n-1) even

וכאן לא ידועה נוסחא לא רקורסיבית לאיבר ה n . ונניח שיצליחו להוכיח שבסדרה הזו (או סדרה דומה) לא קיימת נוסחא לא רקורסיבית לאיבר ה n. למה זה בעיה?
רגע 333821
אתה מגדיר את (A(n לפי (A(n-1 - עם זה אין שום בעיה. (דיברתי על הגדרה של מושג או של אובייקט).

(דוגמא להגדרה רקורסיבית: "A הוא המספר השלם הקטן ביותר שגדול מ- A/2+3").
רגע 333883
גם בדוגמא שלך, לא הבנתי למה הרקורסיביות היא בעייתית (אני מבין שזה רק כלל אצבע, אבל בכל זאת). נדמה לי שאפשר לנסח את ההגדרה הרקורסיבית הזו בתור שני אי שיוויונים - ואני לא רואה שום דבר בעייתי במערכת אי שיוויונים, אפילו אם אותו משתנה מופיע בשני האגפים.
רגע 333885
מצויין. למה שווה A?
רגע 333901
7, לא?

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

להבדיל אלף אלפי הבדלות, אם אני זוכר נכון גם ההגדרה של קונווי למספר היא רקורסיבית, וגם הוא מתחיל את הבניה מהמקרה היחיד שבו הוא יודע שמשהו הוא מספר על בטוח - על ידי שימוש בשתי קבוצות ריקות של מספרים.
רגע 333906
אולי 8? (זה באמת המספר השלם הקטן ביותר שגדול מ- 8/2+3).

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

גם אצל קונווי, ההגדרה של משחק בתור זוג סדור של קבוצות של משחקים היא בחצי-קריצה. הוא לא היה משתמש בה אלמלא הפיגום של הסודרים שמאפשר להגדיר את כל המשחקים באינדוקציה טרנספיניטית, כאשר משחק מדור i+1 מוגדר בתור זוג סדור של קבוצות מדור קודם (עם הגדרה מתאימה לסודרים שאינם עוקבים). גם כאן, המושג "משחק" אינו בא לעולם עד שהגדרנו "משחק מדור 0", "משחק מדור 1", וכן הלאה. "משחק" *מוגדר* בתור "משחק מאיזשהו דור".
רגע 333908
7/2+3 זה לא שש וחצי, שקטן משבע?

שאר הדברים שלך מקובלים עלי, אבל איפה יש הגדרה שהיא רקורסיבית "ממש", בלי בסיס? הרי כבר בכיתה א' מלמדים אותנו שרקורסיה חייבת לבוא עם בסיס.
רגע 333916
בדיוק: 7 הוא המספר השלם הקטן ביותר שגדול מ7/2+3.

שים לב גם שאתה שאלת את עוזי (בהקשר של ההגדרה הרקורסיבית של קונוויי) על מספרים והוא ענה לך על משחקים.
רגע 333921
זה בסדר, כי אצל קונווי ההגדרה של ''מספר'' היא מקרה פרטי של ''משחק'', שמוגדר כמו מספר רק עם פחות מגבלות. לך תבין.
רגע 333977
זהו, שאין. ''הגדרה רקורסיבית'' זה אוקסימורון, אלא אם היא בת-תיקון, שאז זה קיצור ל''תאור אלגנטי שבא במקום ההגדרה (אותה אפשר להבין מתוך ההקשר)''.
רגע 334000
רקורסיה, אם לא נקבע אחרת, מתחילה מפשטות מירבית ופשטות מירבית
מוסברת בקצרה בתגובה 333996
רגע 333918
לא הבנתי למה זה רלוונטי מהו A.

אם הייתי מגדיר את A בתור A=A+1 לא היה שום A שעונה על המשוואה - ועדיין אני לא רואה כאן מה הבעיה.
רגע 333925
הבעיה היא שהכביכול-הגדרה הזו משאירה אותנו בחוסר ודאות לגבי A שאותו היא מבקשת להגדיר במדוייק. עוזי הביא את זה כדוגמא לבעייתיות בהגדרות רקורסיביות כמו זו היפה שגדי הציע.
רגע 333929
אוקי, הבנתי.

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

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