מסנן (תורת הקבוצות)
פעולות נוספות
בתורת הקבוצות, מסנן מעל קבוצה X הוא: משפחה לא ריקה של תת-קבוצות של X, הסגורה להגדלה ולחיתוך סופי, ואינה כוללת את הקבוצה הריקה. למסננים שימושים רבים בתורת הקבוצות המודרנית, לרבות לוגיקה מתמטית ואלגברה בוליאנית, ובטופולוגיה (דרך קומפקטיפיקציית סטון-צ'ך).
מבוא עריכה
הגדרות עריכה
תהי <math>X</math> קבוצה. משפחה <math>\ \mathcal{F} \subset P(X)</math>, שאינה ריקה ואינה כוללת את הקבוצה הריקה, נקראת מסנן, כאשר לכל <math>\ A \in \mathcal{F}</math> כל B המקיים <math>\ A \subset B\in P(X)</math> מקיים גם <math>\ B \in \mathcal{F}</math>, ולכל <math>\ A_1, A_2 \in \mathcal{F}</math> מתקיים <math>\ A_1 \cap A_2 \in \mathcal{F}</math>.
דוגמאות.
- הדרך הקלה ביותר לבנות מסנן היא לקחת את כל הקבוצות המכילות קבוצה קבועה. מסנן כזה נקרא מסנן ראשי. במובנים רבים המסננים הראשיים הם טריוויאליים.
- אוסף הסביבות של נקודה במרחב טופולוגי הוא מסנן.
- כאשר <math>X</math> קבוצה אינסופית, אוסף הקבוצות שהמשלים להן סופי הוא המסנן הקו-סופי או מסנן פרשה (על-שם מוריס פרשה, אחד ממייסדי הטופולוגיה). באופן כללי יותר אפשר להגדיר את המסנן הקו-<math>\lambda</math>, לכל עוצמה <math>\ \lambda<|X|</math>.
כל אוסף תת-קבוצות <math>S</math> המקיים את תכונת החיתוך הסופי יוצר מסנן: אברי המסנן הם הקבוצות המכילות חיתוך סופי כלשהו מ-<math>S</math>.
על-מסננים עריכה
מסנן מקסימלי, כלומר, כזה שאינו מוכל באף מסנן גדול יותר, נקרא על-מסנן (ultrafilter). עבור כל קבוצה <math>\ A \subset X</math>, על-מסנן מוכרח להכיל את A או את המשלים <math>\ X-A</math>. על-מסנן המכיל קבוצה סופית מכיל גם יחידון, ולכן הוא ראשי. על-מסנן שאינו ראשי מוכרח להכיל את המסנן הקו-סופי.
מסנן שחיתוך כל הקבוצות בו הוא ריק, נקרא מסנן חופשי; לדוגמה, המסנן הקו-סופי הוא כזה. מסנן חופשי אינו יכול להיות ראשי. מסנן הסביבות של נקודה במרחב T1 קשיר אינו חופשי, וגם אינו ראשי. לעומת זאת, על-מסנן הוא חופשי אם ורק אם אינו ראשי.
האיחוד של שרשרת עולה של מסננים הוא מסנן. לפי הלמה של צורן, נובע מכך שכל מסנן מוכל בעל-מסנן. תוצאה זו נקראת משפט העל-מסנן, ובעזרת מסנן פרשה נובע ממנה שיש על-מסננים לא ראשיים.
ניסוח במונחי אלגברה בוליאנית עריכה
לכל קבוצה X, קבוצת החזקה <math>\ P(X)</math> היא אלגברה בוליאנית; זהו חוג קומוטטיבי, ביחס לפעולות ההפרש הסימטרי כחיבור, והחיתוך ככפל. באלגברה הזו, אידיאל הוא משפחה של תת-קבוצות, הסגורה להקטנה ולאיחוד סופי. מכאן ש<math>\ \mathcal{F} \subset P(X)</math> הוא מסנן, אם ורק אם אוסף המשלימים <math>\ \mathcal{F}^c = \{A^c : A\in \mathcal{F}\}</math> הוא אידיאל. המסנן ראשי אם ורק אם האידיאל המתאים לו ראשי, והוא על-מסנן אם ורק אם האידיאל המתאים לו הוא אידיאל מקסימלי.
בסיס עריכה
קבוצה <math>\ B \subset P(X)</math> תיקרא בסיס למסנן <math>\ \mathcal{F}</math> אם היא סגורה לחיתוכים סופיים ולכל <math>\ f \in \mathcal{F} </math> יש <math>\ b \in B</math> כך ש-<math>\ b \subset f</math>. (מסנן כזה, אם קיים, הוא יחיד) באופן שקול, <math>\ \mathcal{F} </math> הוא המסנן הקטן ביותר שמכיל את B.
קבוצה B יכולה להיות בסיס למסנן אם ורק אם היא לא ריקה, לא מכילה את הקבוצה הריקה ולכל <math>\ b1, b2 \in B</math> יש <math>\ b \in B</math> כך ש-<math>\ b \subset b1 \cap b2</math>.
מסננים מיוחדים עריכה
תורת הקבוצות המודרנית עוסקת רבות במסננים על קבוצת המספרים הטבעיים. לצורך ההגדרות בהמשך, מסמנים (עבור קבוצות של מספרים טבעיים) <math>A \subseteq^* B</math> אם ההפרש B-A סופי, ו-<math>A =^* B</math> אם <math>A \subseteq^* B \subseteq^*A </math>. מסנן <math>\mathcal{F}</math> המקיים את התכונות השקולות הבאות נקרא נקודת-P:
- כל שרשרת יורדת ב-<math>\mathcal{F}</math> (לגבי היחס <math>\subseteq^*</math>), חסומה מלרע שם (לגבי אותו יחס).
- לכל פירוק <math>\mathbb{N} = P_1 \cup P_2 \cup \cdots</math> לקבוצות אינסופיות, או שאחד החלקים <math>P_i</math> שייך למסנן, או שיש במסנן קבוצה X שהחיתוך שלה עם כל חלק הוא סופי.
- לכל פירוק <math>\mathbb{N} = P_1 \cup P_2 \cup \cdots</math> לקבוצות אינסופיות, המסנן <math>\mathcal{F}</math> אינו מכיל את המסנן <math>\mathcal{F}(P)</math> (שהוא, לפי ההגדרה, המסנן הנוצר על ידי הקבוצות <math> \bigcup_{i>n} (P_i-\{0,1,\dots,f(i)\})</math>, כאשר n מספר כלשהו ו-f פונקציה כלשהי.
מהשערת הרצף, או אפילו מההנחה החלשה יותר <math>\mathfrak{b}=\mathfrak{c}</math>, נובע שיש נקודות-P.
הגדרה זו מוליכה ל"היררכיית-P" בת <math>\omega_1</math> שכבות (שיש גם מסננים מעליה). המסננים הראשיים שייכים לשכבה הראשונה <math>\mathcal{P}_1</math>, ואלו שהם נקודות-P לשכבה <math>\mathcal{P}_2</math>. ידוע שאם יש מסננים בשכבה כלשהי של ההיררכיה (מעבר לשכבת המסננים הראשיים; למשל, אם יש נקודות-P), אז יש מסננים בכל שכבה של ההיררכיה.
על-מכפלות עריכה
- קובץ:Postscript-viewer-blue.svg ערך מורחב – על מכפלה
נקבע מסנן <math>\ \mathcal{F}</math> מעל קבוצה X. נאמר שתת-קבוצה של X היא "גדולה" אם היא שייכת למסנן, ו"קטנה" אחרת. השימוש החשוב ביותר במסננים הוא לבניית על-מכפלות, באופן הבא: אם לכל <math>\ i \in X</math> יש קבוצה <math>\ A_i</math>, אפשר להגדיר יחס שקילות על המכפלה קרטזית בהתאם למסנן: <math>\ (a_i) \sim (b_i)</math> אם אוסף האינדקסים שעבורם <math>\ a_i = b_i</math> שייך ל-<math>\ \mathcal{F}</math>. במילים אחרות, מזהים שני וקטורים, אם הם מסכימים זה עם זה בקבוצת אינדקסים גדולה. מרחב המנה <math>\ \prod A_i / \mathcal{F}</math> נקרא "מכפלה מצומצמת". אם <math>\ \mathcal{F}</math> על-מסנן, זוהי העל-מכפלה של הקבוצות <math>\ A_i</math>.
המשפט היסודי של על-מכפלות (J. Los, 1955) קובע שהעל-מכפלה של מבנים של שפה מסדר ראשון L, מקיימת פסוק של השפה, אם ורק אם הוא מתקיים בקבוצת מודלים גדולה. זוהי תוצאה יסודית בתורת המודלים. לדוגמה, לא רק שעל-מכפלה של מספר בן-מניה של שדות היא שדה -- גם אם משתתפים במכפלה מספר סופי של חוגים שאינם שדות, העל-מכפלה (ביחס לעל-מסנן לא-ראשי) היא עדיין שדה. אם בוחרים לכל נקודה <math>\ i \in X</math> את אותו מודל <math>\ A_i = A</math>, מתקבלת על-חזקה <math>\ A^X/\mathcal{F}</math>, והיא שקולה אלמנטרית ל-A.
מן המשפט היסודי מתקבלת בנייה מפורשת עבור משפט הקומפקטיות: אם T תורה ספיקה-סופית בשפה מסדר ראשון L (כלומר, יש מודל לכל תת-קבוצה סופית של פסוקים מתוכה), ו-X קבוצת תת-הקבוצות הסופיות של T עם מודלים <math>\ M_i</math> לכל קבוצה סופית <math>\ i\in X</math>, אז קיים על-מסנן <math>\ \mathcal{F}</math> על X כך ש- <math>\ \prod_{i \in X} M_i / \mathcal{F}</math> הוא מודל לתורה T. ההוכחה אינה קונסטרוקטיבית, משום שהיא נסמכת על הקיום של על-מסננים המכילים את המסנן הקו-סופי, וזו תוצאה של גרסה חלשה של אקסיומת הבחירה.