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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

מבוא[עריכת קוד מקור | עריכה]

הגדרות[עריכת קוד מקור | עריכה]

תהי X קבוצה. משפחה \ \mathcal{F} \subset P(X), שאינה ריקה ואינה כוללת את הקבוצה הריקה, נקראת מסנן, אם לכל \ A \in \mathcal{F} ולכל \ A \subset B מתקיים גם \ 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}\} הוא אידאל. המסנן ראשי אם ורק אם האידאל המתאים לו ראשי, והוא על-מסנן אם ורק אם האידאל המתאים לו הוא אידאל מקסימלי.

מסננים מיוחדים[עריכת קוד מקור | עריכה]

תורת הקבוצות המודרנית עוסקת רבות במסננים על קבוצת המספרים הטבעיים. לצורך ההגדרות בהמשך, מסמנים (עבור קבוצות של מספרים טבעיים) 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), אז מסננים בכל שכבה של ההיררכיה.

על-מכפלות[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – על מכפלה

נקבע מסנן \ \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. ההוכחה אינה קונסטרוקטיבית, משום שהיא נסמכת על הקיום של על-מסננים המכילים את המסנן הקו-סופי, וזו תוצאה של גרסה חלשה של אקסיומת הבחירה.