L (תורת הקבוצות)

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

האקסיומה V=L אומרת שכל קבוצה ניתנת לבנייה.

הגדרה

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

באופן פורמלי:

• $L_{0}=\emptyset$
• $L_{\alpha +1}={\mathcal {D}}(L_{\alpha })$ כאשר:

${\mathcal {D}}(A)=\{B\subset A|\exists \psi \,,a_{1},\dots a_{n}\in A\,,B=\{x\in A|(A,\in )\models \psi (x,a_{1},\dots ,a_{n})\}\}$

• $L_{\alpha }=\bigcup _{\beta <\alpha }L_{\beta }$ עבור סודר גבולי.
• $L=\bigcup _{\alpha }L_{\alpha }$

כלומר זהו אוסף כל תתי הקבוצות B של A כך שיש נוסחה ואיברים מ-A שמגדירים את איברי B בתוך העולם של איברי A.

גדל הציע גם הגדרה שאינה תלויה במושג הגדירות: את $L_{\alpha +1}$ בונים מתוך $L_{\alpha }\cap \{L_{\alpha }\}$ כקבוצה שסגורה תחת אוסף ספציפי של פעולות פשוטות (מכפלה קרטזית, הפעלת פונקציה וכדומה), והראה ששתי ההגדרות נותנות את אותה מחלקה L.

V=L

האקסיומה V=L או אקסיומת הבנייה, גורסת כי המחלקה L מכילה את כל הקבוצות. אקסיומה זו הוצעה על ידי גדל, שהראה גם כי היא עקבית מתוך ZF, כיוון שהמחלקה L עצמה מקיימת אותה. טענה זו משתמשת באבסולוטיות של השייכות ל-L (למשל במחלקה לא אבסולוטית כמו מחלקת הקבוצות הגדירות מתוך סודרים - OD, ייתכן שקבוצה תהיה גדירה מתוך סודרים בעולם V ולא גדירה מתוך סודרים במחלקה OD).

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

תכונות

אפשר להגדיר באינדוקציה התאמה חח"ע ועל בין $L_{\alpha }$ ל-$\alpha$ עבור כל סודר אינסופי, כלומר $|L_{\alpha }|=|\alpha |$.

הקבוצה $L_{\omega }$ היא אוסף כל הקבוצות הסופיות תורשתית (כלומר הקבוצות הסופיות שגם איבריהן סופיים ואיברי-איבריהן סופיים וכו'), כלומר $L_{\omega }=V_{\omega }$. החל משם ההיררכיות מתפצלות (גם אם V=L), משיקולי עוצמה.

L הוא מודל של ZFC

כל סודר מקיים $\alpha \in L_{\alpha +1}$, ולכן המחלקה L מכילה את כל הסודרים. בנוסף, אם המודל ההתחלתי V קיים את ZF אז גם L מקיים את ZF:

למשל, כדי להראות כי הוא מקיים את אקסיומת ההחלפה יש להשתמש בעקרון ההשתקפות (שנכון בכל בנייה מהצורה הזו): כל טענה (מסדר ראשון) שמתקיימת ב-L מתקיימת כבר ב-$L_{\alpha }$. לכן, אם נוסחה מגדירה פונקציה - עובדה זו מתקיימת כבר בתחילית כלשהי של L, ונוסיף את הקבוצה הרצויה ל-L בשלב הבא לאחר התחילית הזו.

הבנייה המפורשת של איברי L מאפשרת להגדיר סדר טוב על כל איבריו על ידי נוסחה קבועה (ראו בהמשך).

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

הסדר הטוב של L

נתאר הגדרה אפשרית עבור הסדר הטוב, אותו נסמן ב-$<_{L}$. נניח כי $x,y\in L$ שונים, ונפריד למקרים:

1. נניח $x\in L_{\alpha },y\in L_{\beta }$ ואלו הסודרים המינימליים בהם עובדה זו מתקיימת. אם $\alpha <\beta$ אז $x<_{L}y$ ואם $\alpha >\beta$ אז $x>_{L}y$. אחרת נמשיך לסעיף הבא:
2. $\alpha =\beta =\gamma +1$ (הסודר המינימלי בו $x\in L_{\alpha }$ חייב להיות סודר עוקב, לפי הבנייה של L). נבחר מספור קבוע כלשהו של כל הנוסחאות עם מספר כלשהו של פרמטרים, ונסתכל על הנוסחה בעלת המספר הנמוך ביותר שמגדירה את x (עם פרמטרים כלשהם מתוך $L_{\gamma }$) והנוסחה בעלת המספר הנמוך ביותר שמגדירה את y. אם הנוסחאות שונות, ומספר הנוסחה של x נמוך יותר אז $x<_{L}y$ ואחרת $x>_{L}y$. אם הנוסחאות שוות נמשיך לסעיף הבא:
3. x,y מוגדרים על ידי נוסחה זהה בה מעורבים n איברים של $L_{\gamma }$, נניח $(a_{1},\dots ,a_{n})$ עבור x ו-$(b_{1},\dots ,b_{n})$ עבור y. ה-n-יות האלו שונות (כיוון ש-x ו-y שונים). נסתכל על הקואורדינטה הראשונה בה הן שונות, i, ונגדיר $x<_{L}y$ אם $a_{i}<b_{i}$ ואחרת $y<_{L}x$.

מתוך הגדרה זו קל לראות כי הסדר הטוב מוגדר בצורה נכונה כבר בתוך כל תחילית של L שמכירה את המספור של הנוסחאות.

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

ניסוח מדויק של הגדרת הסדר הטוב הקנוני מאפשר לחשב כמה הנוסחה המגדירה אותו "מסובכת", במובן של כמה חילופי כמתים יש בה. מסתבר כי הנוסחה היא מאוד פשוטה - זו נוסחת $\Sigma _{1}$, כלומר נוסחה בה כל הכמתים, למעט כמת קיום יחיד, הם חסומים (כלומר מהצורה $\forall x\in y,\,\exists x\in y$).

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

השערת הרצף המוכללת ב-L

אם V=L, אז לכל סודר $\alpha$ מתקיים כי קבוצת החזקה שלו נוצרת בשלב המינימלי האפשרי: ${\mathcal {P}}(\alpha )\subset L_{\alpha ^{+}}$, כאשר $\alpha ^{+}$ הוא המונה הראשון שגדול ממש מ-$\alpha$.

ההוכחה לתכונה הזו משתמשת בעובדה שקיימת נוסחה בשפה של תורת הקבוצות שכל מודל שמקיים אותה איזומורפי ל-$L_{\gamma }$ עבור סודר מסוים או שהוא שווה לכל L. נוסחה זו מורכבת מהטענה "כל קבוצה ניתנת לבנייה" יחד עם האקסיומות הנחוצות לאבסולוטיות של השייכות ל-L. נניח $X\subset \alpha ,X\in L_{\eta }$, כאשר $\alpha <\eta$ והנוסחה שתוארה קודם מתקיימת ב-$L_{\eta }$.

ניקח תת-מודל אלמנטרי של $L_{\eta }$, בשפה בגודל $|\alpha |$ שמכילה קבוע עבור כל סודר קטן מ-$\alpha$ וקבוע עבור X, בגודל $|\alpha |$. זה אפשרי לפי משפט סקולם-לוונהיים. מודל זה יהיה איזומורפי ל-$L_{\gamma },|\gamma |=|\alpha |$, והאיזומורפיזם ישמר את כל הסודרים מתחת ל-$\alpha$. לכן X נמצאת כבר בשלב ה-$\gamma$ של הבנייה של L.

בניות דומות ומורכבות יותר משמשות להוכחת תכונות קומבינטוריות רבות בתוך L.

קונסטרקטביליות יחסית

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

נניח כי אנחנו רוצים "להוסיף" את הקבוצה A לעולם L. יש לנו שתי אפשרויות:

האפשרות הראשונה היא להתחיל מ-$L_{0}(A)=tr(A)\cup \{A\}$ - הסגור הטרנזיטיבי של A, יחד עם A כאיבר, ומשם להמשיך כמו קודם עם פעולת "קבוצת החזקה הגדירה". הסגור הטרנזיטיבי של A הוא קבוצת כל האיברים של A יחד עם קבוצת כל איברי האיברי של A וכו'. אנו צריכים להכליל אותה כדי שאקסיומת ההיקפיות תתקיים.

מודל זה, שמסומן ב-L(A)‎, יכול להיות שונה מאוד מ-L. למשל, ייתכן שלא מתקיימת בו אקסיומת הבחירה.

האפשרות השנייה היא להוסיף את A כסימן יחס (חד מקומי) לשפה שלנו, ובהתאם לשנות את מושג הגדירות לגדירות בשפה המורחבת. המודל המתקבל באופן הזה מסומן ב-L[A]‎. בניגוד לבנייה הקודמת, במודל הזה מתקיימת אקסיומת הבחירה, והחל ממונה מספיק גדול - גם השערת הרצף. מצד שני, ייתכן ש-$A\notin L[A]$.

בנייה זו משמשת להגדרת המודל המינימלי של מונה מדיד - זהו $L[U]$ כאשר U הוא על-המסנן המתאים למידה.