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

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

הגדרה מתמטית

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

1. $F$ אינה ריקה. כלומר, $F\ne \mathrm{\varnothing }$.
2. כיווניות כלפי מטה: לכל $a,b\in F$ קיים $c\in F$ כך ש-$c\le a$ וגם $c\le b$
3. סגירות כלפי מעלה: לכל $a\in F$ ולכל $b\in X$ המקיים $a\le b$, מתקיים בהכרח ש-$b\in F$

סוגי מסננים

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

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

מסנן ראשי

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

$F_c:=\{x\in X\mid c\le x\}$

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

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

על-מסנן

בהינתן קבוצה סדורה $(X,\le )$ ומסנן $F\subseteq X$, $F$ יקרא על-מסנן אם ורק אם הוא מסנן מקסימלי שאיננו טריוויאלי. כלומר, לא קיים מסנן אחר $F^{\prime }$ כך ש-$F\subset F^{\prime }\subset X$.

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

שימושים

תורת הקבוצות

תבנית:הפניה לערך מורחב שימוש מרכזי של מסננים בתורת הקבוצות הוא במסננים לפי יחס ההכלה. בהינתן קבוצה כלשהי $X$, מסנן במובנים של תורת הקבוצות הוא משפחה $ℱ$ של תת-קבוצות של $X$ שמהווה מסנן על $𝒫(X)$ (קבוצת כל תת-הקבוצות של $X$) לפי יחס ההכלה $\subseteq$. מסנן $ℱ$ זה יקרא מסנן קבוצתי על $X$. כאשר ברור מן ההקשר שהמסנן הוא מסנן קבוצתי, ניתן לקרוא לו פשוט מסנן על $X$, זאת למרות שהוא הלכה-למעשה מסנן על $𝒫(X)$.

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

1. $ℱ\ne \mathrm{\varnothing }$.
2. לכל $A,B\in ℱ$ מתקיים ש-$A\cap B\in ℱ$
3. לכל $A\in ℱ$ ולכל $A\subseteq B\subseteq X$, מתקיים בהכרח ש-$B\in ℱ$

מתכונות אלו נובע בהכרח כי $X$ עצמו הוא איבר של $ℱ$. למסננים קבוצתיים לרוב דורשים בנוסף כי $\mathrm{\varnothing }\notin ℱ$, אחרת $ℱ$ הוא המסנן הטריוויאלי.

דוגמה חשובה למסנן מתחום תורת הקבוצות הוא המסנן הקו-סופי שנקרא גם מסנן פרשה על שם המתמטיקאי רנה מוריס פרשה. בהינתן קבוצה $X$ מעוצמה אינסופית, מסנן פרשה מוגדר כך: $ℱ:=\{A\subseteq X\mid X\mathrm{\setminus }A\text{ is finite}\}$. כלומר, $ℱ$ הוא אוסף כל תתי-הקבוצות של $X$ שהמשלים שלהם הוא ממידה סופית. מסנן זה הוא מסנן אמיתי שאיננו מסנן ראשי.

טופולוגיה

למסננים יש מספר שימושים בטופולוגיה. עבור מרחב טופולוגי $(X,\tau )$ ונקודה $x\in X$, מערכת הסביבות של $x$ המסומנת ב-$𝒩(x)$ היא מסנן קבוצתי.

מסננים קבוצתיים יכולים לשמש כאמצעי חלופי להגדרת מושג ההתכנסות במרחבים טופולוגיים. מגדירים כי מסנן $ℱ\subset 𝒫(X)$ מתכנס לנקודה $x\in X$ אם ורק אם $𝒩(x)\subseteq ℱ$. כלומר, אם $ℱ$ מכילה את כל הסביבות של $x$, היא מתכנסת ל-$x$. ניתן להוכיח כי אם המרחב הוא מרחב האוסדורף, אז כל מסנן מתכנס לכל היותר לנקודה אחת.

שימוש נוסף במסננים בטופולוגיה הוא בהגדרה של מרחב אחיד על-ידי כיסוי אחיד. בהינתן זוג כיסויים של $X$ המסומנים ב-${𝒞}_1,{𝒞}_2$\ אומרים כי ${𝒞}_2$ הוא עידון-כוכב של ${𝒞}_1$ ומסמנים ${𝒞}_2{\le }^{\ast }{𝒞}_1$, אם ורק אם לכל $U\in {𝒞}_2$ קיים $V\in {𝒞}_1$ כך שלכל $U^{\prime }\in {𝒞}_2$ המקיים $U\cap U^{\prime }\ne \mathrm{\varnothing }$, מתקיים ש-$U^{\prime }\subseteq V$. במילים אחרות, לכל קבוצה מהכיסוי ${𝒞}_2$ יש קבוצה ב-${𝒞}_1$ שמכילה את כל הקבוצות מהכיסוי ${𝒞}_2$ ש"נוגעות בה". אוסף כיסויים של $X$ ייקרא כיסוי אחיד אם ורק אם הוא מסנן ביחס ל-${\le }^{\ast }$. כיסוי אחיד מגדיר באופן חד-חד ערכי מרחב אחיד על $X$.

לוגיקה

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

בהינתן קבוצת אינדקסים $I$, מגדירים לכל אינדקס $i\in I$ קבוצה $A_i$. בנוסף מגדירים מסנן קבוצתי $ℱ\subseteq 𝒫(I)$ על אינדקסים אלו. כעת מגדירים יחס שקילות $\sim$ על המכפלה הקרטזית $\prod _{i\in I}{A}_i$ כך שלכל $a,b\in \prod _{i\in I}{A}_i$ מתקיים ש-$a\sim b$ אם ורק אם $\{i\in I\mid a_i=b_i\}\in ℱ$. מרחב המנה $\prod _{i\in I}{A}_i$ על לפי יחס שקילות זה מסומן ב-$\prod _{i\in I}{A}_i/ℱ$ ונקרא על-מכפלה.

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

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

• בהינתן מרחב מידה $(X,\mathrm{\Omega },\mu )$, הקבוצה $ℱ:=\{A\in \mathrm{\Omega }\mid \mu (X\mathrm{\setminus }A)=0\}$ היא מסנן קבוצתי על $X$.
• בהינתן מרחב הפונקציות הממשיות הרציפות $C(ℝ)$, ניתן להגדיר יחס סדר חלקי $\le$ כך ש-$f\le g$ אם ורק אם $f(x)\le g(x)$ לכל $x\in ℝ$ (כלומר, אי-שוויון נקודה-נקודה). מגדירים את הקבוצה $ℱ:=\{f\in C(ℝ)\mid \underset{x\to \mathrm{\infty }}{lim}f(x)=\mathrm{\infty }\}$. ניתן להוכיח כי $ℱ$ הוא מסנן על $C(ℝ)$ לפי $\le$.

ראו גם

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

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

• תבנית:MathWorld