מטריצת אולם

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

הגדרה

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

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

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

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

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

יישומים

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

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