מטריצת אולם

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

הגדרה

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

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

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

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

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

יישומים

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

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