מסנן (תורת הקבוצות)

בתורת הקבוצות, מסנן מעל קבוצה 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}}$.

דוגמאות.

1. הדרך הקלה ביותר לבנות מסנן היא לקחת את כל הקבוצות המכילות קבוצה קבועה. מסנן כזה נקרא מסנן ראשי. במובנים רבים המסננים הראשיים הם טריוויאליים.
2. אוסף הסביבות של נקודה במרחב טופולוגי הוא מסנן.
3. כאשר $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}}$ אם לכל $\ b\in B$ יש $\ f\in {\mathcal {F}}$ כך ש- $\ f\subset b$. (מסנן כזה, אם קיים, הוא יחיד) באופן שקול, $\ {\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:

1. כל שרשרת יורדת ב-${\mathcal {F}}$ (לגבי היחס $\subseteq ^{*}$), חסומה מלרע שם (לגבי אותו יחס).
2. לכל פירוק $\mathbb {N} =P_{1}\cup P_{2}\cup \cdots$ לקבוצות אינסופיות, או שאחד החלקים $P_{i}$ שייך למסנן, או שיש במסנן קבוצה X שהחיתוך שלה עם כל חלק הוא סופי.
3. לכל פירוק $\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. ההוכחה אינה קונסטרוקטיבית, משום שהיא נסמכת על הקיום של על-מסננים המכילים את המסנן הקו-סופי, וזו תוצאה של גרסה חלשה של אקסיומת הבחירה.