על על-מסננים ועל-מכפלות

אני רוצה להציג הפעם שני מושגים יחסית מופשטים, עם שימושים נרחבים בתורת הקבוצות, בטופולוגיה ובלוגיקה (ובעוד מקומות) - על-מסננים (אולטרה פילטרים באנגלית) ועל-מכפלות. אבל אציג את המושגים הללו באופן קצת יותר כללי, בתור מקרים פרטיים של מסננים ומכפלות מצומצמות. תצטרכו להמתין טיפה בסבלנות לפני שיהיה ברור למה הנושאים הללו מגניבים; ההקשר הנוכחי הוא ההוכחה שהתחלתי בפוסט הקודם לפיה \( \mbox{P}\ne\mbox{NP} \) מעל חבורות אבליות אינסופיות, אבל את השימוש הזה נראה רק בפוסט המשך; עם זאת, גם בפוסט הזה אני מתכנן להראות כמה דברים נחמדים.

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

הרעיון שמאחורי מסנן הוא זה: נתונה לנו קבוצה \( X \) כלשהי - ה”עולם” שלנו, למשל המספרים הטבעיים. ל-\( X \) יש המוני תת-קבוצות (כבר עבור הטבעיים יש מספר לא בן מניה של תת-קבוצות) ועל הקבוצות הללו יש מעין “היררכייה” - \( A \) נמצאת “מעל” \( B \) בהיררכייה אם \( B\subseteq A \). זה נותן לנו תחושה ש-\( A \) “גדולה יותר” מ-\( B \) במובן מסויים. מה שמסנן עושה הוא לאפיין אוסף כלשהו של תת-קבוצות של \( X \) שהן “גדולות” או “גבוהות בהיררכייה”. כמובן שעל אותה קבוצה אפשר להגדיר הרבה מסננים, ובכך לתת הרבה משמעויות ל”קבוצות גדולות” שכאלו.

אז איך מוגדר מסנן? פורמלית, זו קבוצה לא ריקה \( D\subseteq2^{X} \) (אוסף של תת-קבוצות של \( X \)) שלא כוללת את הקבוצה הריקה וסגורה לחיתוך ולהכלה כלפי מעלה. פורמלית:

1. \( \emptyset\notin D \) ו-\( X\in D \).
2. אם \( B\subseteq A \) ו-\( B\in D \) אז גם \( A\in D \).
3. אם \( A,B\in D \) אז גם \( A\cap B\in D \).

שימו לב לכך ש-\( X\in D \) נובע מההנחה ש-\( D \) לא ריקה ומתכונה 2, ולכן פשוט דרשתי \( X\in D \) במפורש במקום לומר ש-\( D \) לא ריקה.

ההגדרה מייד מעלה תהיה - למה דווקא התכונות הללו? אפשר עוד להבין את זה שהקבוצה הריקה לא בפנים (אם היא “גדולה”, מי לא?) ואת זה ש-\( X \) בפנים (אם היא לא “גדולה”, מי כן?) וגם הכלה כלפי מעלה נראית סבירה; אבל חיתוך? המממ. האינטואיציה היא שאם קבוצה היא ממש גדולה, אז גם לחתוך אותה עם קבוצה גדולה אחרת לא יוכל לקלקל את זה יותר מדי. כדי לקבל את התחושה כדאי לראות תכף ומייד דוגמאות. אז ניקח קבוצה אינסופית \( X \) ונתהה האם אנחנו מסוגלים למצוא מסנן מעל \( X \). די בבירור \( D=\left\{ X\right\} \) הוא מסנן, אבל טריוויאלי לגמרי ולכן לא מעניין. אז הנה מסנן יותר מעניין: \( D \) יהיה קבוצת כל הקבוצות שהן קו-סופיות. קבוצה היא קו-סופית אם המשלימה שלה היא סופית, כלומר אם יש בה את כל האיברים ב-\( X \) פרט למספר סופי של איברים. פורמלית, \( D=\left\{ A\subseteq X\ |\ \overline{A}<\infty\right\} \) (\( \overline{A} \) הוא סימון פשוט יותר ל-\( X\backslash A \)).

זה בוודאי מתאים לתחושה האינטואיטיבית שלנו של “גודל”; האם זה מקיים את האקסיומות? ובכן, בבירור אקסיומה 1 מתקיימת; גם אקסיומה 2 די פשוטה, שהרי אם \( B\subseteq A \) אז \( \overline{A}\subseteq\overline{B} \), כלומר ב-\( \overline{A} \) יש עוד פחות איברים מאשר ב-\( \overline{B} \) הסופית, ולכן גם היא סופית בעצמה. ומה באשר לחיתוך? ובכן, כאן נחלצים כללי דה-מורגן לעזרתנו: \( \overline{A\cap B}=\overline{A}\cup\overline{B} \). האיחוד של שתי קבוצות סופיות גם הוא סופי, כי גודלו חסום על ידי סכום הגדלים של הקבוצות: \( \left|\overline{A\cap B}\right|=\left|\overline{A}\cup\overline{B}\right|\le\left|\overline{A}\right|+\left|\overline{B}\right| \) ולכן \( A\cap B \) גם היא קבוצה קו-סופית. הנה לנו דוגמה לא טריוויאלית למסנן, שנקראת מסנן פרשה.

בואו נראה דוגמה אחרת. נניח ש-\( A\subseteq X \) היא תת-קבוצה לא ריקה כלשהי של \( X \). נניח שהחלטנו לראות את \( A \) בתור קבוצה “גדולה”, כלומר אנחנו בונים מסנן כך ש-\( A\in D \). אוטומטית נובע מכך ש-\( D \) חייב לכלול את כל הקבוצות שמכילות את \( A \). האם זה לכשעצמו מספיק כדי ליצור מסנן? בהחלט: \( D=\left\{ B\subseteq X\ |\ A\subseteq B\right\} \) הוא בבירור מסנן - קל לבדוק ש-3 האקסיומות מתקיימות. מסנן כזה - שמתקבל מלקיחת כל הקבוצות שמכילות קבוצה נתונה \( A \) - נקרא מסנן ראשי (מי שבקיאים בתורת החוגים ודאי יזכרו כעת במושג של אידאל ראשי שהוא דומה מאוד - זה אידאל שנוצר על ידי איבר יחיד). האם כל מסנן הוא ראשי? ובכן, דרך פשוטה לבדוק זאת היא זו: לוקחים מסנן \( D \) ומסתכלים על \( \bigcap D \) - החיתוך של כל הקבוצות במסנן. אם \( D \) הוא ראשי אנחנו מצפים לקבל את \( A \) - הקבוצה שממנה \( D \) נבנה. אם קיבלנו, למשל, קבוצה ריקה, אז \( D \) אינו ראשי. קל לראות שמסנן פרשה הוא לא ראשי, בדיוק בצורה הזו (כי למשל, לכל \( a\in X \), הקבוצה \( A=X\backslash\left\{ a\right\} \) שייכת ל-\( D \), אבל החיתוך של כולן הוא ריק).

לעומת זאת, אם \( X \) סופית ו-\( D \) הוא מסנן מעל \( X \), אז \( \bigcap D \) הוא חיתוך של מספר סופי של קבוצות ולכן באינדוקציה אפשר להראות ש-\( \bigcap D\in D \), ומכאן ש-\( D=\left\{ B\subseteq X\ |\ \bigcap D\subseteq B\right\} \). כלומר, במובן מסויים כל המסננים מעל קבוצות סופיות הם פשוטים, ואנחנו יודעים בדיוק איך הם נראים. לכן אנחנו מדברים על מסננים בהקשר של קבוצות אינסופיות, ומעתה והלאה \( X \) תמיד יהיה קבוצה אינסופית.

משחק החיתוכים הזה עשוי לעורר שאלה אחרת - נניח שיש לנו “מועמד למסנניות” \( S\subseteq2^{X} \) - אוסף כלשהו של תת-קבוצות של \( X \) שאנחנו מקווים שיהיה מסנן. מן הסתם הוא לא תמיד יהיה מסנן כי עשויות להיות חסרות בו קבוצות - למשל, ייתכן ש-\( S \) קבוצה \( A \) שיש קבוצה שמכילה אותה ואינה ב-\( S \); או שיש שתי קבוצות ב-\( S \) שהחיתוך שלהן לא ב-\( S \); התחושה היא שאפשר יהיה “לתקן” את זה על ידי הוספת עוד קבוצות - להרחיב את \( S \) עד שנקבל מסנן. אבל האם תמיד אפשר לעשות את זה?

זכרו שאסור שהקבוצה הריקה תהיה שייכת למסנן \( D \). אז אם \( \emptyset\in S \) ברור שלא משנה כמה נרחיב את \( S \) - מסנן כבר לא נקבל. אבל האם אם \( \emptyset\notin S \) אנחנו בסדר? לא בהכרח; הכי נצטרך לוודא ש-\( S \) סגורה לחיתוך. סגירות לחיתוך שתי קבוצות גוררת סגירות לחיתוך מספר סופי כלשהו של קבוצות, ולכן אנחנו חייבים לדרוש שלכל סדרה סופית של קבוצות \( A_{1},A_{2},\dots,A_{n}\in S \) יתקיים \( \bigcap A_{i}\ne\emptyset \). התכונה הזו - חיתוך כל מספר סופי של איברים של \( S \) הוא לא ריק - נקראת תכונת החיתוכים הסופיים והיא מככבת גם בטופולוגיה; במקרה שלנו, מסתבר שהיא לא רק הכרחית לכך ש-\( S \) תהיה ניתנת להרחבה למסנן אלא גם מספיקה: אם \( S \) מקיימת את תכונת החיתוכים הסופיים, אז קיים מסנן \( D \) שמכיל את \( S \).

איך בונים את \( D \)? הבניה גם כן באה בצורה טבעית למדי. ברור שנצטרך להכניס ל-\( D \) את \( S \), ולכן גם כל חיתוך סופי של איברים מ-\( S \) (כי אקסיומה 3), ולכן גם כל קבוצה שמכילה חיתוך סופי של איברים מ-\( S \) (כי אקסיומה 2), אז בואו ננסה להגדיר את \( D \) כך:

\( D=\left\{ A\subseteq X\ |\ \exists A_{1},\dots,A_{n}\in S:\bigcap A_{i}\subseteq A\right\} \)

לא קשה להראות ש-\( D \) הוא מסנן; התכונה המאתגרת היא 3, וגם היא פשוטה למדי (אם \( \bigcap A_{i}\subseteq A \) ו-\( \bigcap B_{i}\subseteq B \) אז \( \bigcap A_{i}\cap\bigcap B_{i}\subseteq A\cap B \)). מה שנחמד הוא ש-\( D \) הוא המסנן הקטן ביותר שמכיל את \( S \); פורמלית, \( D \) הוא חיתוך כל המסננים שמכילים את \( S \) (והנה אתגר חדש: להוכיח שחיתוך של מספר כלשהו של מסננים הוא בעצמו מסנן, וש-\( D \) הוא אכן החיתוך הזה). אומרים ש-\( D \) הוא המסנן שנוצר על ידי \( S \).

עכשיו משהתוודענו קצת למסננים, בואו נעבור לתקל שאלה אחרת - כמה גדול מסנן יכול להיות? נניח שיש לנו מסנן \( D \) ואנחנו רוצים להגדיל אותו ככל הניתן, למסנן “גדול ביותר” \( U \). מה אפשר להוסיף ל-\( D \)? ובכן, ברור מה אי אפשר להוסיף ל-\( D \): אם \( A\in D \) אז בשום פנים ואופן אי אפשר להוסיף ל-\( D \) את \( \overline{A} \), כי אחרת נקבל ש-\( A\cap\overline{A}=\emptyset\in U \). לכן כל מסנן \( U \) שמכיל את \( D \) חייב לקיים את התכונה שלכל קבוצה \( A\in X \), לא ייתכן שגם \( A\in U \) וגם \( \overline{A}\in U \). אם זה הדבר היחיד שמגביל את \( U \), כלומר אם לכל \( A\in X \) או שמתקיים \( A\in U \) או שמתקיים \( \overline{A}\in U \), אומרים ש-\( U \) הוא על-מסנן.

את הדיון הזה נהוג לפרמל באופן הבא: מסנן \( U \) הוא על-מסנן אם ורק אם \( U \) הוא מקסימלי, כלומר לא קיים מסנן \( U^{\prime} \) כך ש-\( U\subset U^{\prime} \) (הכלה ממש). הכיוון של “אם \( U \) הוא על-מסנן אז הוא מקסימלי” הוא ברור ועליו כבר דיברנו - אם \( U\subset U^{\prime} \) אז יש \( A\in U^{\prime} \) כך ש-\( A\notin U \), ומכיוון ש-\( U \) הוא על-מסנן אז \( \overline{A}\in U \) ולכן \( A\cap\overline{A}=\emptyset\in U^{\prime} \). האתגר הוא להוכיח שמסנן מקסימלי יקיים את תכונת העל-מסנניות תמיד. נניח בשלילה ש-\( U \) הוא מסנן מקסימלי אבל יש איזה \( A\in X \) כך ש-\( A\notin U \) וגם \( \overline{A}\notin U \), אז אפשר פשוט להוסיף את \( A \) ל-\( U \) ולקבל קבוצה שאינה בהכרח מסנן, אבל היא יוצרת מסנן \( U^{\prime} \) שמכיל ממש את \( U \). למה היא בהכרח יוצרת מסנן? כי היא מקיימת את תכונת החיתוכים הסופיים, שהרי אם יש לנו קבוצות \( B_{1},\dots,B_{n} \) כך ש-\( A\cap\bigcap B_{i}=\emptyset \) זה אומר ש-\( \bigcap B_{i}\subseteq\overline{A} \) ולכן היינו צריכים לקבל \( \overline{A}\in U \) (למה הנימוק שנתתי מספיק?).

יפה. כעת, נותנים לנו קבוצה \( S \) שמקיימת את תכונת החיתוכים הסופיים. אנחנו יודעים שאפשר להרחיב אותה למסנן, אבל האם בהכרח ניתן להרחיב אותה לעל-מסנן? התשובה היא “כן, אבל”. יש לנו כאן סיטואציה דומה ל”כל קבוצה בלתי תלויה של וקטורים במרחב וקטורי ניתנת להרחבה לבסיס”, וכמו שם כך גם כאן ההוכחה תהיה פשוטה, אבל תתבסס על אקסיומת הבחירה, או ליתר דיוק על הלמה של צורן השקולה לה. הרעיון הוא כזה: מספיק לבנות מסנן מקסימלי שמכיל את \( S \). אז נסתכל על קבוצת כל המסננים שמכילים את \( S \); על פי הלמה של צורן, מספיק להראות שכל שרשרת של מסננים (קבוצה של מסננים שמכילים את \( S \) שלכל זוג מביניהם, אחד מהם מוכל בשני) היא בעלת חסם מלעיל בקבוצה (יש מסנן שמכיל את כל המסננים בשרשרת). את זה קל להראות - בהינתן שרשרת, ניקח את האיחוד של כל איבריה ונרחיב אותו למסנן שיהיה החסם מלעיל. כדי להראות שאפשר להרחיב את האיחוד הזה צריך להראות שהאיחוד מקיים את תכונת החיתוכים הסופיים. נניח שהוא לא, אז יש \( A_{1},\dots,A_{n} \) באיחוד כך ש-\( \bigcap A_{n}=\emptyset \). זה רק מספר סופי של \( A_{i} \)-ים ולכן יש איבר בשרשרת שמכיל את כולם, והופס! סתירה לכך שהוא מסנן. הוכחה סטנדרטית לגמרי שאמורה לנבוע מאליה למי שמכיר את טכניקת ההוכחה הזו והבין מהם מסננים.

שימו לב שבמקרה שבו \( U \) הוא על-מסנן ראשי, הוא לא מסנן מעניין במיוחד. נניח ש-\( U \) הוא על-מסנן ראשי, כלומר \( U=\left\{ B\in X\ |\ A\subseteq B\right\} \) עבור איזו שהיא \( A \), אז אני טוען ש-\( A=\left\{ a\right\} \), כלומר \( A \) היא יחידון; זאת מכיוון שניקח \( a\in A \) כלשהו ונשים לב לכך שאו \( \left\{ a\right\} \) או \( \overline{\left\{ a\right\} } \) שייכים ל-\( U \). אם \( \left\{ a\right\} \in U \) אז מכיוון ש-\( A\subseteq\left\{ a\right\} \) נקבל ש-\( A=\left\{ a\right\} \); מצד שני, פשוט לא ייתכן ש-\( \overline{\left\{ a\right\} }\in U \) כי \( A\not\subseteq\overline{\left\{ a\right\} } \)! לכן העל-מסננים שמתעניינים בהם באמת הם אלו שאינם ראשיים. האם יש לנו דוגמה לעל-מסנן שכזה? ובכן, כן! ניקח את \( D \) להיות מסנן פרשה מעל \( X \) - כזכור, המסנן שכולל את כל הקבוצות הקו-סופיות. נרחיב אותו לעל-מסנן \( U \). נניח בשלילה ש-\( U=\left\{ B\in X\ |\ A\subseteq B\right\} \), אז כפי שראינו, \( A=\left\{ a\right\} \). אבל אז \( \overline{A} \) היא קבוצה קו-סופית, ולכן \( \overline{A}\in D\subseteq U \), וקיבלנו סתירה.

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

אם יש לנו שתי קבוצות \( A,B \), אז המכפלה הקרטזית שלהן, שמסומנת \( A\times B \), היא אוסף הזוגות של איבר מ-\( A \) ואיבר מ-\( B \). את הרעיון הזה קל להכליל: אם \( A_{1},\dots,A_{n} \) הן קבוצות, אז \( \prod A_{i} \) הוא אוסף ה-\( n \)-יות שבהן האיבר במקום ה-\( i \) שייך ל-\( A_{i} \). למי שהתרגל לחשוב על מכפלות בתור \( n \)-יות אני רוצה להציע נקודת מבט קצת שונה: נחשוב על כל איבר ב-\( \prod A_{i} \) בתור פונקציה, \( f:\left\{ 1,\dots,n\right\} \to\bigcup A_{i} \), עם הדרישה שלכל \( i\in\left\{ 1,\dots,n\right\} \) מתקיים \( f\left(i\right)\in A_{i} \).

הטוב בדרך ההתבוננות הזו היא שבעזרתה קל להגדיר מכפלות קרטזיות על אוספים כלליים של קבוצות, כל עוד יש לנו דרך כלשהי “לאנדקס” את הקבוצות הללו. אפשר לקחת קבוצה שרירותית \( I \) להיות “קבוצת האינדקסים” שלנו (למשל, \( I=\left\{ 1,\dots,n\right\} \) או \( I=\mathbb{N} \), אבל אפשר גם \( I=\mathbb{R} \) או דברים מופרעים יותר). עכשיו נניח שלכל \( i\in I \) יש לנו קבוצה \( A_{i} \); אפשר להגדיר את המכפלה \( \prod_{i\in I}A_{i} \) בתור אוסף הפונקציות \( f:I\to\bigcup_{i\in I}A_{i} \) כך ש-\( f\left(i\right)\in A_{i} \) לכל \( i\in I \). זה מאפשר לנו לבנות מכפלות די מוזרות למראה, כמו מכפלה של מספר לא בן מניה של קבוצות שכל אחת מאונדקסת על ידי מספר ממשי כלשהו. בפועל אם אתם רוצים לחשוב על מקרה קונקרטי, אפשר להסתפק ב-\( I=\mathbb{N} \), שהוא יחסית פשוט (\( A_{1}\times A_{2}\times A_{3}\times\dots \)).

עכשיו לפאנץ’. מה קורה אם לקבוצות שמכפילים יש מבנה? במתמטיקה אוהבים לבנות מתוך אובייקטים קיימים אובייקטים חדשים, למשל על ידי מכפלה. אפשר להכפיל חבורות ולקבל חבורה, ואפשר להכפיל חוגים ולקבל חוג, אבל האם תמיד מכפלה תיתן לנו אובייקט חדש? ובכן, קחו שדה \( \mathbb{F} \) כלשהו. למרבה הבעסה, \( \mathbb{F}\times\mathbb{F} \) לא יהיה שדה. למה? כי לא כל איבר בו יהיה הפיך: \( \left(1,0\right) \) אינו איבר האפס של \( \mathbb{F}\times\mathbb{F} \), אבל הוא אינו הפיך (כי לא משנה מה נכפיל בו, בקואורדינטה השניה תמיד יהיה 0).

עם זאת, יש דרך לצמצם את המכפלה \( \mathbb{F}\times\mathbb{F} \) כך ששוב נקבל שדה: אם נזהה את האיברים מהצורה \( \left(a,b\right) \) עם האיברים מהצורה \( \left(a,b^{\prime}\right) \), כלומר נגיד שאיברים של \( \mathbb{F}\times\mathbb{F} \) הם זהים אם הקואורדינטה הראשונה שלהם זהה, מה שנקבל יהיה עותק של \( \mathbb{F} \), שהוא שדה. אותו דבר עם \( \mathbb{F}^{3} \) - שוב, כשמזהים איברים אם הקואורדינטה הראשונה שלהם זהה. וכדומה עבור \( \mathbb{F}^{n} \). אוקיי, זה משעמם לחלוטין; מתי זה מתחיל להיות מעניין? או - כשכופלים אינסוף עותקים של \( \mathbb{F} \). אז יתברר שלא חייבים זהות בקואורדינטה אחת מסויימת כדי עדיין לקבל שדה, אלא אפשר להקל מאוד את הדרישות.

בואו נעבור שניה לדוגמה קצת שונה, שלקוחה מהחיים האמיתיים - אנליזה פונקציונלית, במקרה שלנו. אני מדבר על פונקציות ממשיות - \( f:\mathbb{R}\to\mathbb{R} \), שכבר ברור מהדיון הקודם שלנו שאפשר לחשוב עליהן בתור איברים במכפלה קרטזית של עותקים של \( \mathbb{R} \), כשכל עותק מאונדקס על ידי מספר ממשי כלשהו (\( c \)). מסיבות טכניות שלא אכנס אליהן כאן, נוח מאוד לפעמים לחשוב על שתי פונקציות \( f,g \) כזהות אם קבוצת המספרים שעליהם \( f,g \) לא מסכימים היא ממידה אפס (לא אכנס גם להגדרה של מידה כאן; זו הכללה רבת עוצמה של מושג הנפח - או במקרה של \( \mathbb{R} \), האורך). פורמלית, \( \mu\left(\left\{ x\in\mathbb{R}\ |\ f\left(x\right)\ne g\left(x\right)|\right\} \right)=0 \) כאשר \( \mu \) היא פונקצית המידה הרגילה על \( \mathbb{R} \). אפשר לנסח את זה גם בצורה חיובית: קבוצת הנקודות ש-\( f,g \) מסכימות עליהן היא מאוד גדולה. כמה גדולה? עד כדי כך שהמשלימה שלה היא ממידה אפס. נשמע מוכר? ובכן, כן: כל \( \mathbb{R} \) אינו ממידה אפס ואיחוד של שתי קבוצות ממידה אפס הוא ממידה אפס, ומכאן מקבלים די בקלות שקבוצת כל הקבוצות שהמשלימה שלהן היא ממידה אפס הן מסנן על \( \mathbb{R} \). אז מה עשינו כאן? הגדרנו שהפונקציות \( f,g \) הן זהות אם קבוצת הנקודות שעליהן \( f,g \) הסכימו הייתה שייכת למסנן מסוים שהוגדר מעל \( \mathbb{R} \). צמצמנו את המכפלה \( \prod_{x\in\mathbb{R}}\mathbb{R}_{x} \) ביחס למסנן הזה.

פורמלית העסק הזה מתבצע עם יחסי שקילות. נניח שנתונה לנו מכפלה כלשהי \( \mathcal{A}=\prod_{i\in I}A_{i} \) ונתון לנו מסנן \( D \) על הקבוצה \( I \). אז נגדיר יחס שקילות \( \equiv_{D} \) על \( \mathcal{A} \) באופן הבא: \( f\equiv_{D}g \) אם \( \left\{ i\in I\ |\ f\left(i\right)=g\left(i\right)\right\} \in D \).

למה זה יחס שקילות? ובכן, \( \left\{ i\in I\ |\ f\left(i\right)=f\left(i\right)\right\} =I\in D \), אז רפלקסיביות זה קל, וסימטריה זה עוד יותר קל. אבל מה עם טרנזיטיביות? ובכן, יהיו \( f,g,h\in\mathcal{A} \) ונגדיר \( B=\left\{ i\in I\ |\ f\left(i\right)=g\left(i\right)\right\} \) ו-\( C=\left\{ i\in I\ |\ g\left(i\right)=h\left(i\right)\right\} \). אולי קצת מפתה לומר שיתקיים \( \left\{ i\in I\ |\ f\left(i\right)=h\left(i\right)\right\} =B\cap C \) אבל זה לא נכון; מה שכן נכון הוא ש-\( B\cap C\subseteq\left\{ i\in I\ |\ f\left(i\right)=h\left(i\right)\right\} \). לכן אם \( f\equiv_{D}g \) ו-\( g\equiv_{D}h \), ולכן \( B,C\in D \), אז גם \( \left\{ i\in I\ |\ f\left(i\right)=h\left(i\right)\right\} \in D \) (זה נובע משילוב אקסיומות 2 ו-3) ולכן \( f\equiv_{D}h \) וקיבלנו גם טרנזיטיביות.

אם \( \equiv_{D} \) הוא יחס שקילות אז אפשר לחלק בו. מקבלים את הקבוצה

\( \prod_{i\in I}A_{i}/\equiv_{D}=\left\{ \left[f\right]_{D}\ |f\in\prod_{i\in I}A_{i}\right\} \)

כאשר \( \left[f\right]_{D} \) הוא סימון מחלקת השקילות של \( f \) לפי יחס השקילות \( \equiv_{D} \). לדבר הזה קוראים מכפלה מצומצמת, וכדי לסמן אותו בצורה פשוטה להבא אשתמש בסימון \( \prod_{D}A_{i} \). במקרה שבו \( D \) הוא על-מסנן קוראים למכפלה המצומצמת הזו על-מכפלה, ובמקרה שבו \( D \) הוא על-מסנן ו-\( A_{i}=A \) לכל \( i\in I \), כלומר המכפלה היא כולה של עותקים של \( A \) ספציפי אחד, אז לעל-המכפלה קוראים על-חזקה.

רעיון הבניה הזה הוא לטעמי מגניב למדי לכשעצמו (ואני מקווה שכל מי שמכיר את המושג של “פונקציות שקולות אם הן נבדלות רק בקבוצה ממידה אפס” ולא הכיר מסננים עכשיו מרגיש קצת יותר נוח עם המושג הזה), אבל עד כה כל מה שעשינו היה יבש למדי. עכשיו מגיע האקשן האמיתי, בדמות משפט Łoś. קודם כל אצטט את המשפט בלי להיכנס לפרטיו (כולל ההגדרות, שהן חשובות לכשעצמן) ואז ניגש לעבודה.

עד כה הדיון כולו היה דיון טהור בתורת הקבוצות, בלי להכניס מושגים מלוגיקה. אבל אנחנו רוצים לערב במשחק את תורת המודלים, ונעשה זאת כך: נניח שיש לנו שפה כלשהי מסדר ראשון \( \mathcal{L} \). שפה כזו כוללת, כזכור, סימני יחס, סימני פונקציות וסימני קבועים. מודל \( \mathcal{M} \) לשפה הזו כולל קבוצה לא ריקה כלשהי (התחום של המודל) ופרשנויות שמתאימות לכל סימן ב-\( \mathcal{L} \) אובייקט מתאים - לכל סימן יחס, יחס על התחום של \( \mathcal{M} \); לכל סימן פונקציה, פונקציה על התחום של \( \mathcal{M} \) ולכל סימן קבוע, איבר מהתחום של \( \mathcal{M} \). אם יש לנו מודל, אז לכל פסוק \( \varphi \) (פסוק הוא נוסחה ללא משתנים חופשיים) או ש-\( \mathcal{M}\models\varphi \) - המודל מספק את \( \varphi \), כלומר נותן לו ערך אמת - או ש-\( \mathcal{M}\not\models\varphi \).

כעת בואו נניח שיש לנו קבוצת אינדקסים כללית \( I \) וקבוצת מודלים \( \mathcal{M}_{i} \), \( i\in I \), שכולם מודלים של אותה השפה. ונניח שיש לנו על-מסנן \( U \) עבור \( I \). אז אפשר לבנות את העל-מכפלה \( \mathcal{B}=\prod_{U}\mathcal{M} \). אני מניח שברור אינטואיטיבית איך עושים את זה - הפרטים הטכניים טיפה יותר מסובכים ואחזור אליהם בהמשך. נשאלת השאלה - אילו פסוקים \( \mathcal{B} \) מספק? התשובה פשוטה, צפויה, אלגנטית ויפהפיה:

\( \mathcal{B}\models\varphi\iff\left\{ i\in I\ |\ \mathcal{M}_{i}\models\varphi\right\} \in D \)

במילים: \( \mathcal{B} \) מספק נוסחה \( \varphi \) אם ורק אם אוסף האינדקסים של מודלים במכפלה שיוצרת את \( \mathcal{B} \) שמספקים את \( \varphi \) שייך ל-\( D \). כדי שהתוצאה הזו תתקיים אנחנו חייבים להסתכל על על-מכפלה; המשפט פשוט לא נכון עבור מכפלות מצומצמות כלליות.

בפרט קורה משהו מפתיע כאשר כל ה-\( \mathcal{M}_{i} \) שווים, כלומר כאשר אנו מסתכלים על על-חזקה \( \mathcal{B} \) של \( \mathcal{M} \): במקרה הזה, \( \mathcal{B}\models\varphi\iff\mathcal{M}\models\varphi \). במילים אחרות, קיבלנו מ-\( \mathcal{M} \) מודל חדש שמבחינת לוגיקה מסדר ראשון נראה אותו הדבר בדיוק כמו \( \mathcal{M} \), למרות שהוא יכול להיות משמעותית מורכב יותר.

אם לחזור לדוגמה של השדה \( \mathbb{F} \), בואו ניקח את \( I=\mathbb{N} \), ואת \( U \) להיות על-מסנן כלשהו. ונסתכל על \( \prod_{U}\mathbb{F} \). נוסחאות השדה ניתנות לניסוח כולן בלוגיקה מסדר ראשון עם השפה המתאימה, ולכן \( \prod_{U}\mathbb{F} \) יקיים בדיוק את אותן נוסחאות כמו \( \mathbb{F} \), ובפרט את אקסיומות השדה - כלומר, קיבלנו שדה חדש, \( \prod_{U}\mathbb{F} \). מצד שני, מנין לנו שהוא אינו זהה ל-\( \mathbb{F} \)? או, טוב ששאלתם. באופן מצער למדי, הוא עשוי להיות זהה ל-\( \mathbb{F} \), במקרה שהעל-מסנן שלנו הוא לא מעניין מספיק - וזה בדיוק המקרה שבו העל-מסנן הוא ראשי. כזכור, במקרה הזה המסנן הוא מהצורה \( U=\left\{ B\subseteq I\ |\ i\in B\right\} \) עבור \( i\in I \) כלשהו, כלומר נקבל ש-\( f\equiv_{U}g \) אם ורק אם \( f\left(i\right)=g\left(i\right) \) וזו הסיטואציה ה”מנוונת” שתיארנו קודם; אבל אם \( U \) מרחיב את מסנן פרשה אז \( U \) אינו ראשי, ולכן אין קבוצה קבועה של אינדקסים שאם \( f,g \) מזדהים עליהם אז הם זהים. קיבלנו מתוך \( \mathbb{F} \) שדה חדש ומעניין \( \prod_{U}\mathbb{F} \).

כמה מעניין? הו הו הו. בואו ניקח את \( \mathbb{F}=\mathbb{R} \) ונתהה איך \( \prod_{U}\mathbb{R} \) נראה. מבלי להיכנס יותר לעובי הקורה, בואו ננסה להבין ראשית כל איך \( \mathbb{R} \) “משתכן” בתוך השדה הזה. את המספר הממשי \( a\in\mathbb{R} \) אפשר לייצג ב-\( \prod_{U}\mathbb{R} \) על ידי הפונקציה הקבועה \( f_{a}\left(i\right)=a \) - ליתר דיוק, על ידי מחלקת השקילות \( \left[f_{a}\right]_{U} \) (זכרו! \( U \) הוא על-מסנן מעל קבוצת האינדקסים \( I=\mathbb{N} \)).

עכשיו, בואו נתבונן בפונקציה \( g\left(i\right)=i \) - זו פונקציה עולה, וקל לראות ש-\( g\not\equiv_{U}f_{a} \) עבור אף \( a\in\mathbb{R} \), שכן לכל \( a\in\mathbb{R} \), \( \left\{ i\in\mathbb{N}\ |\ g\left(i\right)=f_{a}\left(i\right)\right\} =\left\{ a\right\} \notin U \). לכן \( g \) מייצגת “מספר” חדש שאינו ממשי. מצד שני, הוא איבר של \( \prod_{U}\mathbb{R} \), שהוא שדה סדור שמקיים את כל התכונות של \( \mathbb{R} \). בפרט אפשר להשוות את \( g \) עם כל \( f_{a} \). עוד לא נכנסתי להגדרות פורמליות, אבל אתם כבר ודאי מנחשים ש-\( f_{a}<g \) אם ורק אם הקבוצה \( \left\{ i\in\mathbb{N}\ |\ f_{a}\left(i\right)<g\left(i\right)\right\} \) שייכת ל-\( U \). ומכיוון שהחל מ-\( k \) הראשון שעבורו \( a<k \) יתקיים \( f_{a}\left(i\right)<g\left(i\right) \) לכל \( i\ge k \), הרי ש-\( \left\{ i\in\mathbb{N}\ |\ f_{a}\left(i\right)<g\left(i\right)\right\} \) היא קו-סופית ואכן שייכת ל-\( U \). המסקנה: השדה \( \prod_{D}\mathbb{R} \) מכיל מספרים שגדולים מכל מספר ממשי, אבל הוא עדיין שדה. אפשר גם למצוא למספרים הללו הופכי, ולקבל מספרים שקטנים מכל מספר ממשי - קיבלנו מודל לאנליזה לא סטנדרטית. כבר הראיתי בבלוג שקיים מודל כזה, כפועל יוצא של משפט הקומפקטיות; אבל עכשיו אנחנו יכולים להבין איך הוא נראה, בערך (בערך, כי אנחנו לא באמת יודעים איך \( U \) נראה, רק ש-\( U \) הוא על-מסנן של \( \mathbb{N} \) שכולל את כל הקבוצות הקו-סופיות).

האופן שבו העל-חזקה \( \prod_{D}\mathbb{R} \) החליפה את משפט הקומפקטיות אינו מקרי - אני רוצה להראות עכשיו איך משפט הקומפקטיות עצמו נובע מכל מה שעשינו עד כה.

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

הרעיון הוא פשוט: אם לכל תת-קבוצה סופית של \( \Phi \) יש מודל \( \mathcal{M}_{i} \), אז בואו ניקח את כל המודלים הללו וניצור על-מכפלה שלהם ביחס לעל-מסנן \( U \) שנבחר בצורה חכמה. אם נבחר את העל-מסנן כמו שצריך, נקבל ש-\( \prod_{U}\mathcal{M}_{i} \) מספק את \( \Phi \). במילים אחרות, אנחנו בונים בצורה “חצי-קונסטרוקטיבית” את המודל של \( \Phi \); אמנם אנחנו לא נדע איך בדיוק \( U \) נראה ולכן זו לא בניה קונסטרוקטיבית מלאה, אבל היא בהחלט יותר קונקרטית באופיה מאשר ההוכחה של משפט הקומפטיות עם משפט השלמות.

ראשית כל, על איזו קבוצה אנחנו רוצים להגדיר את \( U \) בכלל? קבוצת האינדקסים \( I \) שלנו צריכה לאנדקס את כל תת-הקבוצות הסופיות של \( \Phi \), אז זה בדיוק מה שנעשה: באופן כללי, בהינתן קבוצה \( \Phi \) כלשהי (לאו דווקא של פסוקים), אפשר להגדיר \( I=\left\{ \Phi^{\prime}\subseteq\Phi\ |\ \left|\Phi^{\prime}\right|<\infty\right\} \), כלומר ה”עולם” שעליו מגדירים מסננים יכלול את כל תת-הקבוצות הסופיות של קבוצה נתונה. יכלתי להציג את העולם הזה כבר בהתחלה, יחד עם יתר הדוגמאות למסננים, אבל העדפתי לחכות עד שתהיה לי דוגמה קונקרטית לסיטואציה שבה הוא צץ מעצמו.

אם כן, \( I \) זו קבוצת האינדקסים, ו-\( \mathcal{M}_{i} \) הוא מודל של \( i\in I \) לכל \( i\in I \) (זכרו שכל \( i \) כזה הוא בעצם \( \Phi^{\prime} \) - תת-קבוצה סופית של \( \Phi \), ואנו מניחים ש-\( \Phi^{\prime} \) היא ספיקה). איזה על-מסנן \( U \) של \( I \) ניקח? אם ניקח על-מסנן ראשי, נקבל ש-\( \prod_{U}\mathcal{M}_{i} \) זהה לאחד מהמודלים במכפלה ותו לא; זה לא מספיק טוב. אולי ניקח על-מסנן שמרחיב את מסנן פרשה? גם זה לאו דווקא יעבוד. קחו \( \varphi\in\Phi \): אנחנו רוצים להראות ש-\( \prod_{U}\mathcal{M}_{i}\models\varphi \). מה שאנחנו יודעים הוא שזה קורה אם \( \left\{ i\in I\ |\ \mathcal{M}_{i}\models\varphi\right\} \in U \), אבל למה שזה יהיה נכון עבור מסנן פרשה? אנחנו יכולים להיות בטוחים ש-\( \mathcal{M}_{i}\models\varphi \) רק עבור \( i\in I \) שהם קבוצה \( \Phi^{\prime} \) כך ש-\( \varphi\in\Phi^{\prime} \). יש הרבה כאלו, אבל אוסף כל ה-\( i \)-ים שבהם זה קורה הוא בוודאי לא קבוצה קו-סופית ולכן אי אפשר להיות בטוחים שהוא ב-\( U \). אין מנוס - צריך מסנן אחר.

איך נגדיר את המסנן החדש? בצורה הכי טבעית שרק אפשר: פשוט נדרוש שלכל \( \varphi\in\Phi \), הקבוצה \( \left\{ i\in I\ |\ \mathcal{M}_{i}\models\varphi\right\} \) תהיה במסנן. במילים אחרות, ניקח את המסנן שנוצר מתוך הקבוצה הזו. כדי להוכיח שבכלל אפשר ליצור מסנן מתוך הקבוצה הזו צריך להראות שהיא מקיימת את תכונת החיתוכים הסופיים: כלומר, שבהינתן קבוצה סופית \( \left\{ \varphi_{1},\varphi_{2},\dots,\varphi_{k}\right\} \), קיים \( i\in I \) כך ש-\( \mathcal{M}_{i}\models\varphi_{j} \) לכל \( 1\le j\le k \). אבל \( \left\{ \varphi_{1},\varphi_{2},\dots,\varphi_{k}\right\} \) היא תת-קבוצה סופית של \( \Phi \) ולכן היא בעצמה איבר של \( I \), ועם מודל \( \mathcal{M}_{i} \) כנדרש. לכן אפשר לבנות על-מסנן שמקיים בדיוק את התכונה שנזקקנו לה, וזה מסיים את הוכחת משפט הקומפקטיות.

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

ראשית כל צריך להסביר איך בדיוק בונים על-מכפלה של מודלים (או אפילו “סתם” מכפלה מצומצמת, זה עובד באותה מידה). אז נניח ש-\( I \) היא קבוצת אינדקסים, \( D \) הוא מסנן עליה ולכל \( i\in I \) יש לנו מודל \( \mathcal{M}_{i} \) עבור השפה \( \mathcal{L} \). כל מודל כזה כולל בפרט קבוצה שהיא התחום של המודל - בדרך כלל הייתי קורא לה \( D^{\mathcal{M}_{i}} \) אבל כאן \( D \) מתאר את המסנן וזה עשוי להיות בעייתי, אז אני אסמן את התחום של \( \mathcal{M}_{i} \) בתור \( \mathcal{U}_{i} \).

המודל \( \mathcal{M}=\prod_{D}\mathcal{M}_{i} \) ייבנה כך: העולם שלו יהיה \( \mathcal{U}=\prod_{D}\mathcal{U}_{i} \), שהוא פשוט מכפלה מצומצת של קבוצות אז אנחנו יודעים בדיוק איך לבנות אותו. זכרו - האיברים של העולם הזה הן מחלקות שקילות של פונקציות \( f:I\to\bigcup\mathcal{U}_{i} \). עכשיו נותר להסביר איך מגדירים במודל \( \prod_{D}\mathcal{M}_{i} \) את הפרשנויות של סימני היחס \( R \), סימני הפונקציה \( F \) וסימני הקבועים \( c \) שיש ב-\( \mathcal{L} \).

בואו ניקח סימן יחס \( R \), ולצורך פשטות נניח שהוא דו מקומי: \( R\left(x,y\right) \) (הרי סימני יחס כלליים יותר יטופלו באותו האופן). זכרו שלכל מודל \( \mathcal{M}_{i} \) יש לנו יחס \( R^{\mathcal{M}_{i}} \) מעל העולם של המודל ש”מפרש” את \( R \) באותו מודל. אנחנו צריכים להחליט מתי עבור \( f,g\in\mathcal{U} \) יתקיים ש-\( \left(f,g\right)\in R^{\mathcal{M}} \), אז ניקח את ההגדרה הטבעית ביותר לכך: \( \left(f,g\right)\in R^{\mathcal{M}} \) אם ורק אם \( \left\{ i\in I\ |\ \left(f\left(i\right),g\left(i\right)\right)\in R^{\mathcal{U}_{i}}\right\} \in D \) (רגע של מחשבה מבהיר לנו שאנחנו חייבים להגדיר את היחס ככה אם אנחנו רוצים שמשהו כמו משפט Łoś יתקיים).

עכשיו בואו ניקח סימן פונקציה \( F\in\mathcal{L} \). שוב, נניח שזו פונקציה חד-מקומית \( F\left(x\right) \) כי המקרה הכללי דומה. אנחנו צריכים להגדיר פונקציה \( F^{\mathcal{M}}:\mathcal{U}\to\mathcal{U} \). איך נעשה את זה? שוב, בצורה הכי טבעית שאפשר: \( F^{\mathcal{M}}\left(f\right)=g_{f} \), כך ש-\( g_{f}\left(i\right)=F^{\mathcal{M}_{i}}\left(f\left(i\right)\right) \).

ומה עם קבועים? ובכן, גם זה פשוט: אם \( c\in\mathcal{L} \) הוא סימן קבוע, עם פרשנויות \( c^{\mathcal{M}_{i}} \) במודלים השונים, אז נגדיר \( c^{\mathcal{M}}=f \) כאשר \( f \) היא הפונקציה \( f\left(i\right)=c^{\mathcal{M}_{i}} \).

כל ההגדרות שנתתי נראות טבעיות ופשוטות, אבל האמת היא שרימיתי בהן כהוגן כי “שכחתי” שהאיברים של \( \mathcal{U} \) הם לא פונקציות, אלא מחלקות שקילות של פונקציות. זה אומר שצריך לבדוק שכל ההגדרות שנתתי הן מוגדרות היטב - לא תלויות בבחירת נציגים. למשל, כשכתבתי \( \left(f,g\right)\in R^{\mathcal{M}} \) בעצם התכוונתי לכתוב \( \left(\left[f\right]_{D},\left[g\right]_{D}\right)\in R^{\mathcal{M}} \). אבל אולי יש פונקציות \( f^{\prime},g^{\prime} \) כך ש-\( f\equiv_{D}f^{\prime} \) ו-\( g\equiv_{D}g^{\prime} \), וגם \( \left\{ i\in I\ |\ \left(f\left(i\right),g\left(i\right)\right)\in R^{\mathcal{U}_{i}}\right\} \in D \) אבל \( \left\{ i\in I\ |\ \left(f^{\prime}\left(i\right),g^{\prime}\left(i\right)\right)\in R^{\mathcal{U}_{i}}\right\} \notin D \)? במקרה הזה, מצד אחד \( \left(\left[f\right]_{D},\left[g\right]_{D}\right)\in R^{\mathcal{M}} \) ומצד שני \( \left(\left[f^{\prime}\right]_{D},\left[g^{\prime}\right]_{D}\right)\notin R^{\mathcal{M}} \) וזה כמובן אבסורד כי \( \left(\left[f\right]_{D},\left[g\right]_{D}\right)=\left(\left[f^{\prime}\right]_{D},\left[g^{\prime}\right]_{D}\right) \).

אז איך מוכיחים שההגדרה עובדת? באופן לא מפתיע, אנו נזקקים לשימוש בתכונות שמגדירות מסננים, כפי שנזקקנו להן כשהוכחנו ש-\( \equiv_{D} \) הוא יחס טרנזיטיבי. נגדיר \( B=\left\{ i\in I\ |\ \left(f\left(i\right),g\left(i\right)\right)\in R^{\mathcal{U}_{i}}\right\} \) ונגדיר \( C_{1}=\left\{ i\in I\ |\ f\left(i\right)=f^{\prime}\left(i\right)\right\} \) ונגדיר \( C_{2}=\left\{ i\in I\ |\ g\left(i\right)=g^{\prime}\left(i\right)\right\} \), אז אם \( B\in D \) נקבל שגם \( B\cap C_{1}\cap C_{2}\in D \), ולכן גם \( \left\{ i\in I\ |\ \left(f^{\prime}\left(i\right),g^{\prime}\left(i\right)\right)\in R^{\mathcal{U}_{i}}\right\} \in D \) (כי היא מכילה את \( B\cap C_{1}\cap C_{2} \) - למה?) ולכן אם \( \left(\left[f\right]_{D},\left[g\right]_{D}\right)\in R^{\mathcal{M}} \) אז גם \( \left(\left[f^{\prime}\right]_{D},\left[g^{\prime}\right]_{D}\right)\in R^{\mathcal{M}} \), ובאותו האופן גם הכיוון ההפוך מתקיים.

תעלול דומה צריך לעשות גם כדי להוכיח ש-\( F^{\mathcal{M}} \) מוגדרת היטב, כלומר שאם \( f\equiv_{D}f^{\prime} \) אז \( F^{\mathcal{M}}\left(\left[f\right]_{D}\right)=F^{\mathcal{M}}\left(\left[f^{\prime}\right]_{D}\right) \). מה נעשה? כזכור, \( F^{\mathcal{M}}\left(f\right)=\left[g_{f}\right]_{D} \) כאשר \( g_{f}\left(i\right)=F^{\mathcal{M}_{i}}\left(f\left(i\right)\right) \) (הפעם כתבתי במפורש ש-\( F^{\mathcal{M}} \) מחזיר מחלקת שקילות). אנחנו רוצים להראות ש-\( g_{f}\equiv_{D}g_{f^{\prime}} \). בבירור \( \left\{ i\in I\ |\ g_{f}\left(i\right)=g_{f^{\prime}}\left(i\right)\right\} \) מכילה את הקבוצה \( \left\{ i\in I\ |\ f\left(i\right)=f^{\prime}\left(i\right)\right\} \), ומכיוון ש-\( f\equiv_{D}f^{\prime} \) הקבוצה השניה ב-\( D \), ולכן גם הראשונה ב-\( D \). אלו פרטים טכניים, אבל כשמתעסקים איתם בידיים סוף סוף אפשר לקבל תחושה אמיתית למה האקסיומות שמגדירות מסננים הן הכרחיות ולמה הן קולעות בול לנקודה שהמושג של מסנן מנסה לתפוס.

עכשיו אפשר להזכיר את משפט Łoś:

\( \mathcal{M}\models\varphi\iff\left\{ i\in I\ |\ \mathcal{M}_{i}\models\varphi\right\} \in D \)

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