מסנן (תורת הקבוצות)
בתורת הקבוצות, מסנן מעל קבוצה X הוא: משפחה לא ריקה של תת-קבוצות של X, הסגורה להגדלה ולחיתוך סופי, ואינה כוללת את הקבוצה הריקה. למסננים שימושים רבים בתורת הקבוצות המודרנית, לרבות לוגיקה מתמטית ואלגברה בוליאנית, ובטופולוגיה (דרך קומפקטיפיקציית סטון-צ'ך).
מבוא
הגדרות
תהי $ X $ קבוצה. משפחה $ \ {\mathcal {F}}\subset P(X) $, שאינה ריקה ואינה כוללת את הקבוצה הריקה, נקראת מסנן, כאשר לכל $ \ A\in {\mathcal {F}} $ כל B המקיים $ \ A\subset B\in P(X) $ מקיים גם $ \ B\in {\mathcal {F}} $, ולכל $ \ A_{1},A_{2}\in {\mathcal {F}} $ מתקיים $ \ A_{1}\cap A_{2}\in {\mathcal {F}} $.
דוגמאות.
- הדרך הקלה ביותר לבנות מסנן היא לקחת את כל הקבוצות המכילות קבוצה קבועה. מסנן כזה נקרא מסנן ראשי. במובנים רבים המסננים הראשיים הם טריוויאליים.
- אוסף הסביבות של נקודה במרחב טופולוגי הוא מסנן.
- כאשר $ X $ קבוצה אינסופית, אוסף הקבוצות שהמשלים להן סופי הוא המסנן הקו-סופי או מסנן פרשה (על-שם מוריס פרשה, אחד ממייסדי הטופולוגיה). באופן כללי יותר אפשר להגדיר את המסנן הקו-$ \lambda $, לכל עוצמה $ \ \lambda <|X| $.
כל אוסף תת-קבוצות $ S $ המקיים את תכונת החיתוך הסופי יוצר מסנן: אברי המסנן הם הקבוצות המכילות חיתוך סופי כלשהו מ-$ S $.
על-מסננים
מסנן מקסימלי, כלומר, כזה שאינו מוכל באף מסנן גדול יותר, נקרא על-מסנן (ultrafilter). עבור כל קבוצה $ \ A\subset X $, על-מסנן מוכרח להכיל את A או את המשלים $ \ X-A $. על-מסנן המכיל קבוצה סופית מכיל גם יחידון, ולכן הוא ראשי. על-מסנן שאינו ראשי מוכרח להכיל את המסנן הקו-סופי.
מסנן שחיתוך כל הקבוצות בו הוא ריק, נקרא מסנן חופשי; לדוגמה, המסנן הקו-סופי הוא כזה. מסנן חופשי אינו יכול להיות ראשי. מסנן הסביבות של נקודה במרחב T1 קשיר אינו חופשי, וגם אינו ראשי. לעומת זאת, על-מסנן הוא חופשי אם ורק אם אינו ראשי.
האיחוד של שרשרת עולה של מסננים הוא מסנן. לפי הלמה של צורן, נובע מכך שכל מסנן מוכל בעל-מסנן. תוצאה זו נקראת משפט העל-מסנן, ובעזרת מסנן פרשה נובע ממנה שיש על-מסננים לא ראשיים.
ניסוח במונחי אלגברה בוליאנית
לכל קבוצה X, קבוצת החזקה $ \ P(X) $ היא אלגברה בוליאנית; זהו חוג קומוטטיבי, ביחס לפעולות ההפרש הסימטרי כחיבור, והחיתוך ככפל. באלגברה הזו, אידיאל הוא משפחה של תת-קבוצות, הסגורה להקטנה ולאיחוד סופי. מכאן ש$ \ {\mathcal {F}}\subset P(X) $ הוא מסנן, אם ורק אם אוסף המשלימים $ \ {\mathcal {F}}^{c}=\{A^{c}:A\in {\mathcal {F}}\} $ הוא אידיאל. המסנן ראשי אם ורק אם האידיאל המתאים לו ראשי, והוא על-מסנן אם ורק אם האידיאל המתאים לו הוא אידיאל מקסימלי.
בסיס
קבוצה $ \ B\subset P(X) $ תיקרא בסיס למסנן $ \ {\mathcal {F}} $ אם היא סגורה לחיתוכים סופיים ולכל $ \ f\in {\mathcal {F}} $ יש $ \ b\in B $ כך ש-$ \ b\subset f $. (מסנן כזה, אם קיים, הוא יחיד) באופן שקול, $ \ {\mathcal {F}} $ הוא המסנן הקטן ביותר שמכיל את B.
קבוצה B יכולה להיות בסיס למסנן אם ורק אם היא לא ריקה, לא מכילה את הקבוצה הריקה ולכל $ \ b1,b2\in B $ יש $ \ b\in B $ כך ש-$ \ b\subset b1\cap b2 $.
מסננים מיוחדים
תורת הקבוצות המודרנית עוסקת רבות במסננים על קבוצת המספרים הטבעיים. לצורך ההגדרות בהמשך, מסמנים (עבור קבוצות של מספרים טבעיים) $ A\subseteq ^{*}B $ אם ההפרש B-A סופי, ו-$ A=^{*}B $ אם $ A\subseteq ^{*}B\subseteq ^{*}A $. מסנן $ {\mathcal {F}} $ המקיים את התכונות השקולות הבאות נקרא נקודת-P:
- כל שרשרת יורדת ב-$ {\mathcal {F}} $ (לגבי היחס $ \subseteq ^{*} $), חסומה מלרע שם (לגבי אותו יחס).
- לכל פירוק $ \mathbb {N} =P_{1}\cup P_{2}\cup \cdots $ לקבוצות אינסופיות, או שאחד החלקים $ P_{i} $ שייך למסנן, או שיש במסנן קבוצה X שהחיתוך שלה עם כל חלק הוא סופי.
- לכל פירוק $ \mathbb {N} =P_{1}\cup P_{2}\cup \cdots $ לקבוצות אינסופיות, המסנן $ {\mathcal {F}} $ אינו מכיל את המסנן $ {\mathcal {F}}(P) $ (שהוא, לפי ההגדרה, המסנן הנוצר על ידי הקבוצות $ \bigcup _{i>n}(P_{i}-\{0,1,\dots ,f(i)\}) $, כאשר n מספר כלשהו ו-f פונקציה כלשהי.
מהשערת הרצף, או אפילו מההנחה החלשה יותר $ {\mathfrak {b}}={\mathfrak {c}} $, נובע שיש נקודות-P.
הגדרה זו מוליכה ל"היררכיית-P" בת $ \omega _{1} $ שכבות (שיש גם מסננים מעליה). המסננים הראשיים שייכים לשכבה הראשונה $ {\mathcal {P}}_{1} $, ואלו שהם נקודות-P לשכבה $ {\mathcal {P}}_{2} $. ידוע שאם יש מסננים בשכבה כלשהי של ההיררכיה (מעבר לשכבת המסננים הראשיים; למשל, אם יש נקודות-P), אז יש מסננים בכל שכבה של ההיררכיה.
על-מכפלות
ערך מורחב – על מכפלה
נקבע מסנן $ \ {\mathcal {F}} $ מעל קבוצה X. נאמר שתת-קבוצה של X היא "גדולה" אם היא שייכת למסנן, ו"קטנה" אחרת. השימוש החשוב ביותר במסננים הוא לבניית על-מכפלות, באופן הבא: אם לכל $ \ i\in X $ יש קבוצה $ \ A_{i} $, אפשר להגדיר יחס שקילות על המכפלה קרטזית בהתאם למסנן: $ \ (a_{i})\sim (b_{i}) $ אם אוסף האינדקסים שעבורם $ \ a_{i}=b_{i} $ שייך ל-$ \ {\mathcal {F}} $. במילים אחרות, מזהים שני וקטורים, אם הם מסכימים זה עם זה בקבוצת אינדקסים גדולה. מרחב המנה $ \ \prod A_{i}/{\mathcal {F}} $ נקרא "מכפלה מצומצמת". אם $ \ {\mathcal {F}} $ על-מסנן, זוהי העל-מכפלה של הקבוצות $ \ A_{i} $.
המשפט היסודי של על-מכפלות (J. Los, 1955) קובע שהעל-מכפלה של מבנים של שפה מסדר ראשון L, מקיימת פסוק של השפה, אם ורק אם הוא מתקיים בקבוצת מודלים גדולה. זוהי תוצאה יסודית בתורת המודלים. לדוגמה, לא רק שעל-מכפלה של מספר בן-מניה של שדות היא שדה -- גם אם משתתפים במכפלה מספר סופי של חוגים שאינם שדות, העל-מכפלה (ביחס לעל-מסנן לא-ראשי) היא עדיין שדה. אם בוחרים לכל נקודה $ \ i\in X $ את אותו מודל $ \ A_{i}=A $, מתקבלת על-חזקה $ \ A^{X}/{\mathcal {F}} $, והיא שקולה אלמנטרית ל-A.
מן המשפט היסודי מתקבלת בנייה מפורשת עבור משפט הקומפקטיות: אם T תורה ספיקה-סופית בשפה מסדר ראשון L (כלומר, יש מודל לכל תת-קבוצה סופית של פסוקים מתוכה), ו-X קבוצת תת-הקבוצות הסופיות של T עם מודלים $ \ M_{i} $ לכל קבוצה סופית $ \ i\in X $, אז קיים על-מסנן $ \ {\mathcal {F}} $ על X כך ש- $ \ \prod _{i\in X}M_{i}/{\mathcal {F}} $ הוא מודל לתורה T. ההוכחה אינה קונסטרוקטיבית, משום שהיא נסמכת על הקיום של על-מסננים המכילים את המסנן הקו-סופי, וזו תוצאה של גרסה חלשה של אקסיומת הבחירה.
ראו גם
קישורים חיצוניים
מסנן (תורת הקבוצות)40248689Q16545258