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

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

בתורת הקבוצות, מסנן מעל קבוצה 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}\} הוא אידאל. המסנן ראשי אם ורק אם האידאל המתאים לו ראשי, והוא על-מסנן אם ורק אם האידאל המתאים לו הוא אידאל מקסימלי.

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

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