מסנן (מתמטיקה)

קובץ:Asche transparent background.png

ערך זה דורש ידע מוקדם. אם אתם מתקשים להבין את הערך מומלץ לעיין ב:

סדר חלקי

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

הגדרה מתמטית

בהינתן קבוצה <math>X</math> ועליה יחס סדר חלקי <math>\le</math>, הקבוצה <math>F\subseteq X</math> תקרא מסנן על <math>X</math> אם ורק אם היא מקיימת את התכונות הבאות:

1. <math>F</math> אינה ריקה. כלומר, <math>F\ne \emptyset</math>.
2. <math>F</math> קבוצה מכוונת מטה: לכל <math>a,b\in F</math> קיים <math>c\in F</math> כך ש-<math>c\le a</math> וגם <math>c\le b</math>
3. <math>F</math> קבוצה עליונה: לכל <math>a\in F</math> ולכל <math>b\in X</math> המקיים <math>a \le b</math>, מתקיים בהכרח ש-<math>b\in F</math>

סוגי מסננים

מסנן טריוויאלי ומסנן אמיתי

ניתן להיווכח כי אם <math>X</math> עצמו הוא קבוצה מכוונת מטה, הוא בהכרח מסנן על עצמו. מסנן זה, אם קיים, נקרא המסנן הטריוויאלי של <math>X</math>. אם <math>F</math> הוא מסנן על <math>X</math> שאיננו המסנן הטריוויאלי, <math>F</math> יקרא מסנן אמיתי על <math>X</math>.

מסנן ראשי

בהינתן קבוצה סדורה <math>(X,\le)</math> ואיבר כלשהו <math>c\in X</math>, מגדירים את המסנן הראשי של <math>c</math> באופן הבא:

<math>F_c:=\left\{x\in X\mid c\le x\right\}</math>

כלומר, <math>F_c</math> הוא אוסף כל האיברים שגדולים מ-<math>c</math>. ניתן להוכיח כי זהו מסנן.

קבוצה <math>F\subseteq X</math> תקרא מסנן ראשי אם ורק אם קיים <math>c\in X</math> כך ש-<math>F=F_c</math>. ניתן להוכיח כי מסנן הוא מסנן ראשי אם ורק אם יש לו איבר מינימלי. על כן, אם קבוצה סדורה ביחס סדר טוב, אז כל מסנן בה הוא מסנן ראשי.

על-מסנן

בהינתן קבוצה סדורה <math>(X,\le)</math> ומסנן <math>F\subseteq X</math>, <math>F</math> יקרא על-מסנן אם ורק אם הוא מסנן מקסימלי שאיננו טריוויאלי. כלומר, לא קיים מסנן אחר <math>F'</math> כך ש-<math>F\subset F'\subset X</math>.

משפט העל-מסננים קובע כי כל מסנן אמיתי מוכל בעל-מסנן. כלומר, לכל מסנן כלשהו <math>F\subset X</math> קיים על-מסנן <math>U</math> כך ש-<math>F\subseteq U \subset X</math>, כאשר <math>F=U</math> אם ורק אם <math>F</math> בעצמה על-מסנן. הוכחת המשפט מתבצעת באמצעות הלמה של צורן.

שימושים

תורת הקבוצות

קובץ:Postscript-viewer-blue.svg ערך מורחב – מסנן (תורת הקבוצות)

שימוש מרכזי של מסננים בתורת הקבוצות הוא במסננים לפי יחס ההכלה. בהינתן קבוצה כלשהי <math>X</math>, מסנן במובנים של תורת הקבוצות הוא משפחה <math>\mathcal{F}</math> של תת-קבוצות של <math>X</math> שמהווה מסנן על <math>\mathcal{P}(X)</math> (קבוצת כל תת-הקבוצות של <math>X</math>) לפי יחס ההכלה <math>\subseteq</math>. מסנן <math>\mathcal{F}</math> זה יקרא מסנן קבוצתי על <math>X</math>. כאשר ברור מן ההקשר שהמסנן הוא מסנן קבוצתי, ניתן לקרוא לו פשוט מסנן על <math>X</math>, זאת למרות שהוא הלכה-למעשה מסנן על <math>\mathcal{P}(X)</math>.

עבור מסננים קבוצתיים, ניתן להמיר את האקסיומות של מסננים כללים באקסיומות הבאות:

1. <math>\mathcal{F}\ne \emptyset</math>.
2. לכל <math>A,B\in \mathcal{F}</math> מתקיים ש-<math>A\cap B\in \mathcal{F}</math>
3. לכל <math>A\in \mathcal{F}</math> ולכל <math>A\subseteq B\subseteq X</math>, מתקיים בהכרח ש-<math>B\in \mathcal{F}</math>

מתכונות אלו נובע בהכרח כי <math>X</math> עצמו הוא איבר של <math>\mathcal{F}</math>. למסננים קבוצתיים לרוב דורשים בנוסף כי <math>\emptyset\notin\mathcal{F}</math>, אחרת <math>\mathcal{F}</math> הוא המסנן הטריוויאלי.

דוגמה חשובה למסנן מתחום תורת הקבוצות הוא המסנן הקו-סופי שנקרא גם מסנן פרשה על שם המתמטיקאי רנה מוריס פרשה. בהינתן קבוצה <math>X</math> מעוצמה אינסופית, מסנן פרשה מוגדר כך: <math>\mathcal{F}:=\left\{A\subseteq X\mid X\backslash A\text{ is finite}\right\}</math>. כלומר, <math>\mathcal{F}</math> הוא אוסף כל תתי-הקבוצות של <math>X</math> שהמשלים שלהם הוא ממידה סופית. מסנן זה הוא מסנן אמיתי שאיננו מסנן ראשי.

טופולוגיה

למסננים יש מספר שימושים בטופולוגיה. עבור מרחב טופולוגי <math>(X,\tau)</math> ונקודה <math>x\in X</math>, מערכת הסביבות של <math>x</math> המסומנת ב-<math>\mathcal{N}(x)</math> היא מסנן קבוצתי.

מסננים קבוצתיים יכולים לשמש כאמצעי חלופי להגדרת מושג ההתכנסות במרחבים טופולוגיים. מגדירים כי מסנן <math>\mathcal{F}\subset \mathcal{P}(X)</math> מתכנס לנקודה <math>x\in X</math> אם ורק אם <math>\mathcal{N}(x)\subseteq \mathcal{F}</math>. כלומר, אם <math>\mathcal{F}</math> מכילה את כל הסביבות של <math>x</math>, היא מתכנסת ל-<math>x</math>. ניתן להוכיח כי אם המרחב הוא מרחב האוסדורף, אז כל מסנן מתכנס לכל היותר לנקודה אחת.

שימוש נוסף במסננים בטופולוגיה הוא בהגדרה של מרחב אחיד על-ידי כיסוי אחיד. בהינתן זוג כיסויים של <math>X</math> המסומנים ב-<math>\mathcal{C}_1,\mathcal{C}_2</math>\ אומרים כי <math>\mathcal{C}_2</math> הוא עידון-כוכב של <math>\mathcal{C}_1</math> ומסמנים <math>\mathcal{C}_2\le^* \mathcal{C}_1</math>, אם ורק אם לכל <math>U\in \mathcal{C}_2</math> קיים <math>V\in \mathcal{C}_1</math> כך שלכל <math>U'\in \mathcal{C}_2</math> המקיים <math>U\cap U'\ne \emptyset</math>, מתקיים ש-<math>U'\subseteq V</math>. במילים אחרות, לכל קבוצה מהכיסוי <math>\mathcal{C}_2</math> יש קבוצה ב-<math>\mathcal{C}_1</math> שמכילה את כל הקבוצות מהכיסוי <math>\mathcal{C}_2</math> ש"נוגעות בה". אוסף כיסויים של <math>X</math> ייקרא כיסוי אחיד אם ורק אם הוא מסנן ביחס ל-<math>\le^*</math>. כיסוי אחיד מגדיר באופן חד-חד ערכי מרחב אחיד על <math>X</math>.

לוגיקה

השימוש העיקרי של מסננים בלוגיקה הוא על-ידי על-מכפלות.

בהינתן קבוצת אינדקסים <math>I</math>, מגדירים לכל אינדקס <math>i\in I</math> קבוצה <math>A_i</math>. בנוסף מגדירים מסנן קבוצתי <math>\mathcal{F}\subseteq \mathcal{P}(I)</math> על אינדקסים אלו. כעת מגדירים יחס שקילות <math>\sim</math> על המכפלה הקרטזית <math>\prod_{i\in I}{A_i}</math> כך שלכל <math>a,b\in \prod_{i\in I}{A_i}</math> מתקיים ש-<math>a\sim b</math> אם ורק אם <math>\left\{i\in I\mid a_i=b_i\right\}\in \mathcal{F}</math>. מרחב המנה <math>\prod_{i\in I}{A_i}</math> על לפי יחס שקילות זה מסומן ב-<math>\prod_{i\in I}{A_i}/ \mathcal{F}</math> ונקרא על-מכפלה.

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

קשר לאידיאלים בחוג הפונקציות על הקבוצה

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה והשלימו אותו.

דוגמאות נוספות

• בהינתן מרחב מידה <math>(X,\Omega,\mu)</math>, הקבוצה <math>\mathcal{F}:=\left\{A\in \Omega\mid \mu(X \backslash A)=0\right\}</math> היא מסנן קבוצתי על <math>X</math>.
• בהינתן מרחב הפונקציות הממשיות הרציפות <math>C(\mathbb{R})</math>, ניתן להגדיר יחס סדר חלקי <math>\le</math> כך ש-<math>f\le g</math> אם ורק אם <math>f(x)\le g(x)</math> לכל <math>x\in \mathbb{R}</math> (כלומר, אי-שוויון נקודה-נקודה). מגדירים את הקבוצה <math>\mathcal{F}:=\left\{f\in C(\mathbb{R})\mid \lim_{x\to\infty}{f(x)}=\infty\right\}</math>. ניתן להוכיח כי <math>\mathcal{F}</math> הוא מסנן על <math>C(\mathbb{R})</math> לפי <math>\le</math>.

ראו גם

• מסנן (תורת הקבוצות)
• מערכת סביבות
• על-מכפלה

קישורים חיצוניים

• מסנן, באתר MathWorld (באנגלית)