לוגיקה - שאלה בתחשיב הפסוקים (קבוצה ספיקה מקסימלית)

[csstud]

נאמר שקבוצת פסוקים http://www.codecogs.com/gif.latex?%5CSigma היא ספיקה מקסימלית אם http://www.codecogs.com/gif.latex?%5CSigma ספיקה ולא קיימת http://www.codecogs.com/gif.latex?%5CSigma%20' ספיקה כך ש-http://www.codecogs.com/gif.latex?%5CSigma%20' מכילה ממש את http://www.codecogs.com/gif.latex?%5CSigma.

 

צ"ל שכל קבוצה ספיקה S מוכלת בקבוצה ספיקה מקסימלית.

 

ניסיתי להגיד שאם S ספיקה מקסימלית, אז הטענה נכונה כי S בהכרח מכילה את עצמה, ואם S ספיקה לא מקסימלית אז קיימת S' ספיקה כך שS' מכילה את S, אבל כאן נתקעתי. נראה לי הגיוני אינטואיטיבית שאפשר להמשיך ולמצוא קבוצות כאלה כשכל אחת ספיקה ומכילה את הקודמת ולכן גם את S, עד שנגיע לקבוצה מקסימלית. אבל אני לא יודע אם אפשר להגיע מזה לפתרון.

 

יש למישהו מושג?

[incog]

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

[csstud]

אתה יכול לתת לי כיוון לגבי הדרך האחרת?

 

נראה לי שלא למדנו על הלמה של צורן (ומויקיפדיה לא הצלחתי להבין מה היא אומרת).

[incog]

הדרך האחרת (אני מניח שהשפה היא בת מניה, אם אתה לא מכיר את הלמה של צורן סביר להניח שזה לא אומר לך הרבה ואתם מניחים את זה בלי לציין זאת).
תהא:  {A_i} קבוצת כל הפסוקים.
נגדיר באינדוקציה את: S_n, בצורה הבאה:
S_0 זה בעצם S שנתונה לך.
כעת נניח שהגדרנו את: S_i  נגדיר את S_(i+1)  d בצורה הבאה:

1) אם S_i איחוד עם A_i  זו קבוצה ספיקה אזי: S_(i+1 ) d תהיה S_i איחוד עם {A_i}.
2) אחרת: S_i+1=S_i.
 

כעת נגדיר: S'=  איחוד על כל ה- S_n.
לפי הגדרה מתקיים ש: S'  מכילה את S, נשאר לך להוכיח שני דברים:
1) S' ספיקה (זה נובע מהבניה שלנו של ה- S_n , מספיק להראות שכל אחד מהם ספיק ואת זה קל לעשות באינדוקציה)
2) S' מקסימלית (תוכיח משהו יותר חזק: לכל פסוק A מתקיים או ש: A שייך ל-S' או ש: ~A שייך ל-S' , כמובן שאם S' מקיימת את זה אז היא מקסימלית)

זו כמובן סקיצה של ההוכחה וצריך לרשום את זה מסודר ובפירוט, אם משהו לא מובן אשמח לעזור.

[csstud]

קודם כל תודה רבה על המאמץ.

 

לא הבנתי איך איחוד של קבוצה כלשהי עם A_i יכול לתת לי קבוצה ספיקה, הרי קבוצת כל הפסוקים היא לא ספיקה.

[incog]

אה לא הסימונים שלי קצת מבלבלים,  אני עשיתי אינומרציה של כך הפסוקים: A_1,A_2,...,A_n,...,  
בכל שלב של הבדיקה אני בודק את S_n ו- A_n  (שים לב ש- A_n זה פסוק אחד! לא כולם), אם הקבוצה שמורכבת מ- S_n והפסוק הבודד! A_n זו קבוצה ספיקה אז S_n+1 תהיה הקבוצה הזו (כלומר S_n ועוד A_n , לא כולם!) , אחרת S_n=S_n+1

[csstud]

אה, הבנתי עכשיו (גם מה זה A_i וגם את סכמת ההוכחה).

אוקיי, נראה לי שאני אסתדר מכאן. שוב תודה!

[ohad]

עריכה 2: חשבתי שמצאתי פיתרון יותר טוב, אבל בסוף יצא משהו דומה מאוד ל incog.

 

מה אתם אומרים על ההוכחה הזו:

http://i.imm.io/Rr4s.png

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

נערך בתאריך ינואר 2, 2013 - על-ידי ohad

[incog]

ההוכחה הזו שאתה מציין הוא פחות או יותר ההוכחה שהזכרתי עם הלמה של צורן (כמובן שזה הרבה יותר פשוט ואלגנטי עם הלמה של צורן).

 

בכל אופן לא הבנתי כמה דברים בהוכחה שלך:
 

1) לא ברור לי למה אתה יכול למספר? הרי מספר ההרחבות של-S הוא בעוצמת הרצף (כל פסוק יכול להופיע או לא להופיע שם)
2) לא הבנתי בידיוק מה זו הקבוצה- S'  (יש שם בעיות בסימונים אתה לא יכול להשתמש פעמיים ב-i), משהו גם לא בסדר S' על פי הסימון הראשוני היא קבוצה של קבוצות של פסוקים לכן זה לא ברור מה זה אומר: S' ספיקה.

 

 

בכל מקרה עדיין אתה צוריך להוכיח ש-S' היא אכן ספיקה מקסימלית.

[ohad]

צודק (באופן לא מפתיע...), איך עכשיו?

http://i.imm.io/RuJa.png

ואם כבר, אז קראתי קצת על הלמה של צורן (ויקיפדיה והבלוג של גדי), 

והבנתי שהיא תלויה באקסיומת הבחירה שלא ניתן להשתמש בה בכל המערכות...

[incog]

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

 

בכל אופן אם קראת על הלמה של צורן אז אתה בטח מבין שמה שאתה עושה פה זה פשוט מנסה להוכיח מקרה מאוד ספציפי של הלמה.

 

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

קח את הודגמא הבאה:
נמספר את כל הנוסחאות A1,..,A_n,..,, (יש אינסוף כאלה), ונניח:
1) אנחנו מתחילים עם S ריקה (זה סתם לצורך נוחות אתה יכול להניח ש-S לא ריקה ופשוט למספר את הנוסחאות בלי אלו שמופיעות ב-S)
2) הקבוצה שמכילה את כל הנוסחאות הזוגיות ואת A_1 היא ספיקה. 
(ממש לא בעיה לבנות ממש באופן קונקרטי מודל כזה)
 

כעת נניח את המקרה הבא: בתהליך האינדוקטיבי שלך הקבוצות שהתקבלו הם S_n זו קבוצת כל הנוסחאות הזוגיות עד 2n 
(כלומר: A_2,A_4,...,A_2n).
אזי זו אכן סדרה עולה שמקימת את כל התנאים שלך, ומתקיים ש-S' זו הקבוצה שמכילה את כל הנוסחאות הזוגיות, אבל זו כמובן לא קבוצה ספיקה מקסימלית (אפשר להוסיף לה את A_1).

[ohad]

אכן דברים קשים incog... :(

בצר לי חזרתי לפיתרון שלך וניסחתי אותו (עם חיפוף קל בסוף כי כמה אפשר לפרמל):

http://i.imm.io/RvMJ.png

תודה רבה על כל התיקונים וההפרכות!!