מטריצת אולם

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

הגדרה

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

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

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

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