בתשובה לאורי גוראל גורביץ', 10/09/05 18:06
עוד משהו על סוסלין 329037
למרות שזה מופיד בויקי, החלטתי להוסיף עוד קצת.
קח עץ אינסופי כלשהו. קל לראות‏1 שחייבת להיות לו קומה אינסופית או ענף אינסופי.
עכשיו קח עץ מעוצמה א1 ‏2. האם חייב להיות לו ענף באורך א1?
האם חייבת להיות קומה בגודל א1?

מסתבר‏13 שאפשר לבנות עץ בגודל א1 בלי שניהם. עץ כזה נקרא עץ ארונסיאן (aronszajn).
קבוצה של איברים בעץ היא שרשרת אם לכל שני איברים אחד מהם הוא צאצא (לאו דוקא ישיר) של השני. ענף הוא שרשרת וכל שרשרת מוכלת בענף.
קבוצה של איברים בעץ היא אנטי-שרשרת אם לכל שני איברים אין צאצאים משותפים. קומה בעץ היא אנטי-שרשרת אבל לא כל אנטי-שרשרת מוכלת בקומה.
האם יש עץ בגודל א1 כך שאין בו שרשרת בגודל א1 ואין בו אנטי-שרשרת בגודל א1?
עץ כזה נקרא עץ סוסלין, ומסתבר שקיומו שקול לקיום קו סוסלין (הקבוצה מהתגובה הקודמת שאינה שקולה לממשיים)‏1.

1 תרגיל: הוכח.
2 תרגיל: הגדר.
3 כבר לא כל כך קל.
עוד משהו על סוסלין 329044
מרתק.

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

באופן כללי (ואם הבנתי נכון) אז ענף של עץ הוא שרשרת שבה יש את השורש, את אחד הבנים של השורש (נסמנו X1), את אחד הבנים של X1 (נסמנו X2) וכן הלאה...
עוד משהו על סוסלין 329121
זה נכון אם מדובר בעץ אינסופי "רגיל", כזה שהגובה שלו הוא א0. עץ כללי מוגדר להיות יחס סדר חלקי כך שלכל איבר קבוצת האיבר הקטנים ממנו סדורה היטב (ביחס לסדר המדובר). ענף מוגדר אז בתור שרשרת מקסימלית.
עוד משהו על סוסלין 329126
תודה.
עוד משהו על סוסלין 329117
הדרך הפשוטה ביותר היא להגדיר ענף בתור שרשרת מקסימלית.
עוד משהו על סוסלין 329842
הבה ונמשיכה (בתקוה שמישהו עוד קורא את זה).

מרטין מתיחס לאקסיומת מרטין.
קח יחס סדר חלקי P, לאו דווקא עץ.
נגיד ששני אברים מתיישבים אם קיים איבר שקטן משניהם.
אנטי-שרשרת היא קבוצה של איברים שאינם מתיישבים (בזוגות).
יחס הסדר שלנו הוא ccc אם אין אנטי-שרשרת לא בת-מניה.

קבוצה D היא צפופה אם לכל איבר x ב-P יש y ב-D שקטן ממנו y<x.
קבוצה F היא פילטר אם:
לכל x ו-y ב-F יש z ב-F שקטן משניהם.
אם x שייך ל-F, כל מה שגדול ממנו (ב-P) גם שייך ל-F.

אם P היתה עץ אז פילטר==ענף.

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

ברור‏1 ש-MA(א0) מתקיים.
ברור‏2 ש-MA(2^א0( לא מתקיים.

אקסיומת מרטין, MA היא הטענה MA(k) לכל k שקטנה מ-‏2^א0.
השערת הרצף גוררת MA באופן טריויאלי.

למה זה טוב?
אם אנחנו מניחים שהשערת הרצף לא נכונה (במודל שלנו) מתעוררות כמה שאלות לגבי העוצמות שבין א0 ל-‏2^א0. למשל:
האם איחוד של k קבוצות בעלות מידה אפס היא מדידה ובעלת מידה אפס?
האם איחוד של k קבוצות מקטגוריה ראשונה היא גם מקטגוריה ראשונה?
ועוד כהנה וכהנה.
מסתבר התשובות לשאלות האלו באות ביחד ו-MA(k) גורר תשובה חיובית עבור k.
גם השערת סוסלין נכנסת לכאן. MA(א1( גורר אי קיום קו או עץ סוסלין.
זה שימושי עבור כפיות. למעשה, כל מה שתארנו כאן, מאוד דומה לכפיה.

טוב, זה היה מתיש. ליל מנוחה.

1 אתם יודעים מה בא כאן.
עוד משהו על סוסלין 329843
אני לא מבינה, לא היה פשוט יותר למלא את הבטחתך ולענות לי מה מעניין בהסתברות?
עוד משהו על סוסלין 329844
וואלה. איך לא חשבתי על זה.
מחר‏1. באמת. בהסתברות 1.

1 אולי נפליגה בספינות...
עוד משהו על סוסלין 329856
כאן אני כבר לא מצליח לעקוב. אני צריך לשבת, ולכתוב את ההגדרות, ולעשות תרגילים, ולקלל את המרצה, ולא ללמוד למבחן בתורת השדות תוך כדי.
עוד משהו על סוסלין 329867
עזוב את העצים. אני מעוניין לשמוע על פרקולציה. אולי אתה תצליח להסביר לי את הקשר לקונפורמיות.
פרקולציה 330381
גבירותיי ורבותיי, עקב בקשת הקהל, פרקולציה!

קח את הגרף של Z^2, הסריג הדו-מימדי. להבהרה: הקודקודים הם כל הקואורדינטות השלמות במישור ושני קודקודים מחוברים אם המרחק בינהם הוא אחד, בקיצור, רשת דייגים אינסופית.

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

מה קורה לרשת? אנו מתענינים בשאלה האם יש רכיב אינסופי או שמא הרשת נגזרה לגזרים סופיים. אם יש רכיב אינסופי, כמה יש? אחד, שניים, אלפיים, אינסוף?

המשך יבוא...
פרקולציה 330383
במהרה, אני מקווה.
פרקולציה 330604
המשך...

במודל שתיארנו ברור‏1 שההסתברות לקיום רכיב אינסופי (נקרא לה r) עולה עם p.
ברור גם ש- r(0)=0 (אין קשתות) וש-r(1)=1 (כל הקשתות ישנן).
בעזרת חוק 0-1 של קולמוגורוב‏2 נקבל r(p) הוא 0 או 1 לכל p. מאחר ו-r עולה קיבלנו שקיימת נקודה קריטית p_c כך ש:
אם p<p_c אז r(p)=0 (אין רכיב אינסופי),
ואם p>p_c אז r(p)=1 (יש רכיב אינסופי).

נשארו השאלות מהו p_c ובפרט האם אינו טריויאלי (כלומר לא 0 או 1), מהו r(p_c), ומה קורה עם מספר רכיבי הקשירות האינסופיים.

שאלות?
תשובות?

1 תרגיל: הוכח באופן ריגורוזי.
2 לפעורי הפה: החוק אומר שאם מאורע כלשהו, התלוי בתוצאה של אינסוף הגרלות, בלתי תלוי בתוצאה של כל קבוצה סופית שלהן, אז הסתברותו היא בהכרח 0 או 1.
לא באמת הבנתי 330611
אם נתחיל מקשת קיימת (p>0) ונבדוק מה הסיכוי שהיא חלק מרכיב אין סופי, נילך לאחד הצמתות, ואז הסיכוי שקיימת קשת נוספת באותו כיוון היא p' והסיכוי שקיימת קשת בלפחות כיוון מאונך אחד היא 2p-p^2 לכן הסיכוי שיש לפחות עוד קשת אחת הוא 3p-3p^2+p^3 (שתמיד קטן מ1) והסיכוי שמהקשת הזאת יש עוד קשת הוא זהה, לכן הסיכוי שקיימות אין סוף קשתות כאלה הוא אפס. אותו חישוב מתקיים, כמובן, גם לצד השני. לכן, r(p<1)=0.
לא באמת הבנתי 330621
ראשית, לסריג הריבועי שאג"ג מתאר, אפשר להראות משיקולי סימטריה שהנקודה הקריטית היא בחצי, לפחות כאשר מדברים על פרקולצית קשתות. לא ברור לי מה בדיוק לא נכון בשיקול שלך, אבל אם תחשוב שניה על "עץ" שמכל ענף יוצאים עוד שני ענפים (כלומר כל צומת מכילה 3 ענפים‏1) ,תוכל להשתכנע שקיים p לא טריוויאלי שהוא קריטי.

לא באמת הבנתי 330625
>לסריג הריבועי שאג"ג מתאר, אפשר להראות משיקולי סימטריה שהנקודה הקריטית היא בחצי.

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

<תוכן פירסומי>
אם מישהו ממש מתענין, הוא מוזמן לבוא לשמוע את הקורס שאעביר בנושא "הילוכים מקריים ופרקולציות" במכון ויצמן בסמסטר א'.
</תוכן פירסומי>

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

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

ברור‏1 שאם התוחלת של P קטנה מ-‏1, ההכחדות היא ודאית. מה שפחות ברור הוא שאם התוחלת של P גדולה מ-‏1, יש סיכויי חיובי להשרדות (עד אינסוף). הסיכוי המדויק תלוי בהתפלגות והוא יכול להיות קטן כרצוננו, אבל הוא תמיד חיובי. עבור P עם תוחלת 1 בדיוק, ההכחדות היא ודאית‏2, אבל תוחלת גודל המשפחה ומספר הדורות היא אינסופית.

מכאן, שעבור פרקולציה על העץ הבינארי, p_c=1/2 ועבורו אין רכיבים אינסופיים.

1 הוכח.
2 מלבד במקרה הטריויאלי, בו בהסתברות 1 יש ילד אחד.
לא באמת הבנתי 330626
אתה פחות או יותר עשית את החישוב שמסלול נתון קיים בגרף. זה כמובן 0, אבל יש הרבה מסלולים אפשריים.
פרקולציה 330616
2 נראה לי שהפה נפער רק *אחרי* ששומעים מהו החוק הזה. אפשר סקיצה של ההוכחה?
פרקולציה 330628
הדבר הראשון שעולה על דעתי הוא שזה נובע בקלות מהרגולריות של המידה הרלוונטית. הרגולריות אומרת שאם יש לי קבוצה מדידה A, אז יש קבוצה פתוחה B שמכילה את A ועם מידה קרובה ל-A כרצוננו. אם מקרבים את B ע"י איחוד של מספר סופי של קבוצות פתוחות, נסמנו C. אם ההסתברות של A היתה חיובית אז ההסתברות המותנית של A בהנתן C היא גדולה כרצוננו. C הוא מאורע שתלוי במספר סופי של המשתנים ולכן A צריך להיות בלתי תלוי בו. מסקנה: ההסתברות של A היא 1.

עכשיו רק נותר לחשוב איך מוכיחים את הרגולריות של המידה הרלוונטית ולקוות שזה לא נעשה בעזרת חוק ה-‏0-1 של קולמוגורוב.
פרקולציה 330622
את זה אני פחות או יותר מכיר, אבל ראיתי שאפשר לעשות הרבה דברים יפים כאשר ''מניחים'' סימטריה קונפורמית. הבעיה היא שמעבר להגיד את המילים הללו, אני לא מבין בזה כלום.
עוד משהו על סוסלין 329894
אח, הנוסטלגיה...גם לך גיטיק נתן איזה 20 שאלות מהפרק בקומבינטוריקה של Kunen ?
עוד משהו על סוסלין 330078
25, כמדומני. אודה ולא אבוש, עבדנו על השאלות הללו בקבוצה (!) וזה היה אחד הדברים המהנים ביותר בתואר הראשון.
עוד משהו על סוסלין 330635
מרוב עצים אצלך באמת לא רואים את היער...

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

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