מטריצת אולם

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

הגדרה

נניח כי $\lambda ,\kappa$ הם מונים. יהי $F$ מסנן על $\lambda$. מטריצת אולם היא אוסף של תתי קבוצות של $\lambda$, $⟨A_{\alpha \beta }|\alpha <\kappa \wedge \beta <\lambda ⟩$, כך שמתקיים:

• לכל $\alpha <\kappa$ ו- $\beta \ne \gamma$, חיתוך הקבוצות $A_{\alpha \beta },A_{\alpha \gamma }$ ריק ("כל שורה מורכבת מקבוצות זרות בזוגות").
• לכל $\beta <\lambda$ מתקיים $\bigcup A_{\alpha \beta }\in F$ ("איחוד הקבוצות לאורך עמודה הוא גדול").

הדוגמה הסטנדרטית למטריצת אולם מתקבלת במקרה שבו $\lambda ={\kappa }^{+}$, ו-$F$ מסנן כך ש- $F\supseteq \{X\subseteq \lambda :|\lambda \setminus X|<\lambda \}$. לכל סודר $\xi <\lambda$ נקבע פונקציה על $f_{\xi }:\kappa \to \xi$. כעת, נגדיר $A_{\alpha \beta }=\{\xi <\lambda :f_{\xi }(\alpha )=\beta \}$. נבדוק שמתקבלת מטריצת אולם:

התנאי הראשון מתקיים: נניח $\alpha <\kappa$ ו- $\beta ,\gamma <\lambda$. אם קיים $\xi \in A_{\alpha \beta }\cap A_{\alpha \gamma }$, אז, מההגדרה, $\gamma =f_{\xi }(\alpha )=\beta$.

התנאי השני מתקיים: נניח $\beta <\lambda$. לכל סודר $\xi$ בין $\beta$ ל- $\lambda$, קיים $\alpha <\kappa$ כך ש- $f_{\xi }(\alpha )=\beta$. לפיכך $\xi \in \bigcup _{\alpha <\kappa }{A}_{\alpha \beta }$. זה מראה ש-$\lambda \setminus \bigcup _{\alpha <\kappa }{A}_{\alpha \beta }\subseteq \beta$ ולכן $\bigcup _{\alpha <\kappa }{A}_{\alpha \beta }\in F$.

יישומים

נניח $\lambda ={\kappa }^{+}$ והמסנן $F$ הוא $\lambda$-שלם (כלומר, סגור לחיתוך של פחות מ-$\lambda$ קבוצות) ומרחיב את המסנן $\{X\subseteq \lambda :|\lambda \setminus X|<\lambda \}$. תהי $⟨A_{\alpha \beta }|\alpha <\kappa \wedge \beta <\lambda ⟩$ מטריצת אולם. לכל $\beta <\lambda$ נתבונן בעמודה המתאימה לו. יש בעמודה זו $\kappa$ קבוצות, ואיחודן במסנן; מה-$\lambda$-שלמות, יש אינדקס $\alpha (\beta )<\kappa$ כך ש-$A_{\alpha (\beta )\beta }\in F^{+}$, כלומר $A_{\alpha (\beta )\beta }$ נחתכת באופן לא ריק עם כל קבוצה מ-$F$. מאחר ש-$\lambda ={\kappa }^{+}$, קיים ${\alpha }^{\ast }<\kappa$ כך ש-$S=\{\beta <\lambda :\alpha (\beta )={\alpha }^{\ast }\}$ מעוצמה $\lambda$. קיבלנו קבוצה $\{A_{{\alpha }^{\ast }\beta }:\beta \in S\}$ של קבוצות זרות ב-$F^{+}$. לעובדה זו יש מספר יישומים:

• כל מונה מדיד ממשית הוא אי נשיג חלש: נניח $\lambda$ מונה מדיד ממשית, כלומר קיימת עליו מידה $\mu :𝒫(\lambda )\to [0,1]$ שהיא $\lambda$-אדיטיבית. לא קשה להראות ש-$\lambda$ מונה סדיר. לכן מספיק להוכיח שאינו עוקב. נניח בשלילה שיש מונה $\kappa$ כך ש-$\lambda ={\kappa }^{+}$. יהי $F=\{X\subseteq \lambda :\mu (X)=1\}$. זה מסנן $\lambda$-שלם. מהאמור לעיל, קיימת קבוצה של $\lambda$ קבוצות זרות בזוגות ממידה חיובית, סתירה.
• משפט סולוביי למונים עוקבים: נניח $\lambda ={\kappa }^{+}$ ו-$S\subseteq \lambda$ קבוצה שבת. נוכיח שניתן לחלק את $S$ ל-$\lambda$ קבוצות שבת זרות בזוגות. נבנה מטריצת אולם עבור המסנן ה-$\lambda$ שלם $F=\{X\subseteq \lambda :\text{ for some club }C\subseteq \lambda ,C\cap S\subseteq X\}$. נובע שקיימת קבוצה מעוצמה $\lambda$של קבוצות זרות בזוגות ששייכות ל-$F$. נקבל חלוקה של (תת קבוצה של) $S$ ל-$\lambda$ קבוצות שבת זרות בזוגות.