מטריצת אולם

בתורת הקבוצות, מטריצת אוּלַםאנגלית: Ulam matrix) היא מערך של תתי קבוצות של מונה עם תכונות מסוימות. מטריצות אולם הוצגו על ידי סטניסלב אולם והן שימושיות למספר הוכחות, בהן ההוכחה שמונה מדיד ממשית הוא אי-נשיג חלש.

הגדרהעריכה

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

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

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

התנאי הראשון מתקיים: נניח   ו-  . אם קיים  , אז, מההגדרה,  .

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

יישומיםעריכה

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

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