תורת הקבוצות/תורת הקבוצות האקסיומטית

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

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

סתירות בתורת הקבוצות הנאיבית

הפרדוקס של קנטור

תהי $A$ קבוצת כל הקבוצות. על פי משפט קנטור, מתקיים $|A|<|{\mathcal {P}}(A)|$. מצד שני, ${\mathcal {P}}(A)$ היא קבוצה של קבוצות, לכן ${\mathcal {P}}(A)\subseteq A$, כלומר $|{\mathcal {P}}(A)|\leq |A|$. סתירה.

הפרדוקס של ראסל

פרדוקס זה מפורסם יותר, וידוע גם בשם פרדוקס הספר: תהי $A$ קבוצת כל הקבוצות שאינן איבר של עצמן, כלומר $A=\{x|x\not \in x\}$. האם $A\in A$? אם $A\in A$, אז מהגדרת $A$ נובע כי $A\not \in A$. אם $A\not \in A$, אז מהגדרת $A$ נובע כי $A\in A$. סתירה.

שני הפרדוקסים ניתנים לפתירה באמצעות האקסיומות של תורת הקבוצות, שנביא להלן.

אקסיומות

נביא כאן את מערכת אקסיומות ZFC - מערכת האקסיומות שנוצרה במקור על ידי ארנסט צרמלו, המיוצג על ידי Z בשם המערכת, ולאחר מכן אברהם הלוי פרנקל שינה במעט את המערכת, לכן שם המערכת שונה לZF. לאחר מכן נוספה למערכת אקסיומת הבחירה (ראו להלן) - Choice, ושם המערכת שונה לZFC. במערכת שלושה מושגי יסוד (כלומר מושגים לא מוגדרים), והם הקבוצה, השייכות ($\in$) והשוויון, ושבע אקסיומות.

אקסיומת ההיקפיות

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

$\forall x\forall y((x=y)\Leftrightarrow \forall z(z\in x\Leftrightarrow z\in y))$

ובמילים, שתי קבוצות הן שוות אם ורק אם כל קבוצה היא באחת מהן אם ורק אם היא בשנייה.

את אקסיומת ההיקפיות ניתן להבין גם כמגדירה שוויון, אך גם אז ניאלץ לקבל אותה כאקסיומה, כי המשמעות של שוויון היא שלכל פונקציה $f$ שנחשוב עליה, מתקיים $x=y\Rightarrow f(x)=f(y)$. לכן אם נרצה לחשוב על האקסיומה כהגדרה, ניאלץ לקבל את האקסיומה הבאה: $x=y\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)$.

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

אקסיומת האיחוד

ניזכר בהגדרת האיחוד: $A\cup B=\{x|x\in A\lor x\in B\}$, וכן $\bigcup _{\alpha \in A}\alpha =\{x|\exists \alpha \in A,x\in \alpha \}$. נרצה שאכן יהיו קיימות קבוצות כאלו, לכן נקבל את אקסיומת האיחוד:

$\forall x\exists y\forall z(z\in y\Leftrightarrow \exists w\in x(z\in w))$

מאקסיומת ההיקפיות נובע כי הקבוצה y נקבעת באופן יחיד, ונסמן $y=\bigcup _{\alpha \in x}\alpha$.

אקסיומת ההחלפה

בהינתן קבוצה $v$ ופעולה $f$ על איברי $v$, נרצה שתהיה קיימת תמונת הפונקציה: ${\text{Im}}(f)=\{f(x)|x\in v\}$. לכן ננסח את אקסיומת ההחלפה. אקסיומת ההחלפה אינה אקסיומה יחידה, כי אם סכמת אקסיומות, כלומר אוסף אינסופי של אקסיומות, הנקבע באופן הבא:

לכל קבוצה $v$ וטענה לוגית $\varphi (x,y)$ בשפה הלוגית של תורת הקבוצות, כך שלכל $x\in v$ קיים $y$ יחיד כך ש$\varphi (x,y)$ היא טענה נכונה, מתקיימת הטענה הבאה:

$\exists z\forall y((y\in z)\Leftrightarrow \exists x((x\in v)\land \varphi (x,y))$

מאקסיומת ההיקפיות נובע שהקבוצה $z$ נקבעת באופן יחיד, ונסמן $z=\{y|\exists x((x\in v)\land \varphi (x,y))\}$.

מאקסיומה זו נובע, למשל, קיום הקבוצה $\{a,b\}$, לכל שתי קבוצות $x,y$: מאקסיומת האינסוף להלן נובע כי קיימת הקבוצה הריקה המקיימת $\forall x(x\not \in \emptyset )$, ומאקסיומת ההיקפיות נובע כי קיומה נקבע באופן יחיד. שימוש באקסיומת קבוצת החזקה להלן יראה כי קיימת $v:={\mathcal {P(P}}(\emptyset ))=\{\emptyset ,\{\emptyset \}\}$. נגדיר את הטענה $\varphi (x,y)\equiv (((x=\emptyset )\Rightarrow (y=a))\land ((x=\{\emptyset \})\Rightarrow (y=b)))$. מהאקסיומה נובע שקיימת תמונת הטענה: $\{a,b\}$.

אקסיומת קבוצת החזקה

ניזכר בהגדרת קבוצת החזקה: ${\mathcal {P}}(A)=\{x|x\subseteq A\}$. נרצה שלכל קבוצה x, הקבוצה ${\mathcal {P}}(x)$ תהיה קיימת. לכן נקבל את אקסיומת קבוצת החזקה:

$\forall x\exists y\forall z(z\in y\Leftrightarrow \forall w(w\in z\Rightarrow w\in x))$

מאקסיומת היסוד נובע כי הקבוצה y נקבעת באופן יחיד, ונסמן $y={\mathcal {P}}(x)$.

אקסיומת היסוד

אקסיומת היסוד היא האקסיומה היחידה במערכת שנכונותה לא מובנת מאליה, כלומר היא אינה אינטואיטיבית. האקסיומה נוסחה כדי למנוע את הפרדוקסים של קנטור וראסל. נוסח האקסיומה הוא:

$\forall x(\exists y(y\in x)\Rightarrow \exists y((y\in x)\land \forall z(z\in x\Rightarrow \lnot (z\in y)))$

כלומר לכל קבוצה יש אחד מאיבריה שזר לה.

אקסיומת הקבוצה האינסופית

כל האקסיומות של ZFC לא מספיקות כדי להוכיח שקיימת קבוצה אינסופית, ולו אחת. לשם כך נוסחה אקסיומת הקבוצה האינסופית.

$\exists S[\exists x\in S\forall y(y\not \in x)\land \forall x(\exists y\in x\Rightarrow (x\in S\Leftrightarrow \exists y\in S\forall z(z\in x\Leftrightarrow z\in y\lor z=y)))]$

במילים: קיימת קבוצה $S$ כך שהקבוצה הריקה ב$S$, ולכל $x$ לא ריקה, $x\in S$ אם ורק אם קיים $y\in S$ כך ש$x=y\cup \{y\}$. ניתן להוכיח באמצעות אקסיומת היסוד ואקסיומת ההיקפיות כי $S$ נקבעת באופן יחיד, ונסמן $S=\mathbb {N}$ (קבוצת המספרים הטבעיים).

שימו לב כי באקסיומה מוצהר גם כי קיימת קבוצה $x$ כך ש$\forall y(y\not \in x)$, כלומר קבוצה ריקה. מאקסיומת ההיקפיות נובע כי קיימת רק קבוצה ריקה אחת, המסומנת $x=\emptyset$.

אקסיומת הבחירה

אקסיומה זו היא מן השימושיות ביותר בZFC. היא גם האינטואיטיבית מביניהן, וזו שהיו לגביה הכי הרבה מחלוקות. אקסיומת הבחירה קובעת כי בהינתן אוסף של קבוצות לא ריקות, ניתן לבחור איבר מכל קבוצה, גם ללא ידע קודם על הקבוצות (מלבד התכונה שהן לא ריקות). לפני שנביא את ניסוח המשפט, נקדים במספר הגדרות חשובות (שכבר הגדרנו, אך נגדיר באמצעות האקסיומות של ZFC): בהינתן קבוצות $x,y$, נובע מאקסיומת ההחלפה כי קיימת הקבוצה $\{x,y\}$, וכן קיימת הקבוצה $\{x,x\}=\{x\}$, ולכן קיימת גם $\{\{x\},\{x,y\}\}$ אותה נסמן $(x,y)$.

בהינתן קבוצות $X,Y$ ולכל $y\in Y$, נגדיר (על $X$) את הטענה $\varphi _{y}(x,\alpha )\equiv (\alpha =(x,y))$. מאקסיומת ההחלפה נובע שקיימת תמונת הטענה, אותה נסמן $X\times \{y\}$. נגדיר (על $Y$) את הטענה $\varphi (y,\alpha )\equiv (\alpha =X\times \{y\})$. מאקסיומת ההחלפה נובע שקיימת תמונת הטענה, אותה נסמן $E$. מאקסיומת האיחוד נובע שקיים איחוד הקבוצות ב$E$, אותו נסמן ב$X\times Y$.

נגדיר $(x,y,z)=((x,y),z)$. בהינתן קבוצות $A,B$, פונקציה $f:A\to B$ היא שלשה סדורה $(A,B,q)$ (לא הגדרנו כך פונקציה בפרק פונקציות, אך הגדרה זו נוחה יותר לצורך ניסוח האקסיומה, והיא שקולה באופן חד-חד-ערכי) כך ש$q\subseteq A\times B$ (כלומר $\forall x(x\in q\Rightarrow x\in A\times B)$), וכן $\forall x(x\in A\Rightarrow \exists y((y\in B)\land ((x,y)\in q)\land \forall z(((x,z)\in q)\Rightarrow (z=y))))$. מההגדרה נובע כי לכל $x\in A$, הקבוצה $y$ נקבעת באופן יחיד, ונסמן $y=f(x)$.

כעת נביא את נוסח האקסיומה:

$\forall x\exists \left(f:x\to \bigcup _{\alpha \in x}\alpha \right)\forall y(y\in x\Rightarrow f(y)\in y)$

פונקציה כגון זו המתוארת באקסיומה תיקרא פונקציית בחירה.

פתרון הסתירות

הפרדוקס של קנטור

הפרדוקס של קנטור עושה שימוש בכך ש$A$ (קבוצת כל הקבוצות) היא קבוצה, ולכן ניתן לדבר על מושגים כגון ${\mathcal {P}}(A)\subseteq A$, וכן $|A|<|{\mathcal {P}}(A)|$.

פתרון הפרדוקס יעשה על ידי שנאמר כי $A$ אינה קבוצה, ולכן הביטוי ${\mathcal {P}}(A)\subseteq A$ חסר משמעות מכמה סיבות, ביניהן שאקסיומת קבוצת החזקה חלה רק על קבוצות, וכן שלא ניתן לדבר על $x\in A$, ולכן לא תוגדר ההכלה. גם הביטוי $|A|<|{\mathcal {P}}(A)|$ מאבד משמעות. בכל פעם שנרצה לדבר על קבוצת כל הקבוצות, נחליף את המילה קבוצה במילה מחלקה.

ניתן גם להוכיח כי קבוצת כל הקבוצות אינה קיימת: נניח בשלילה שהיא קיימת, כלומר $\exists A\forall x(x\in A)$. מהגדרת $A$ נקבל כי $A\in A$. מצד שני, ניתן להפעיל את אקסיומת היסוד על הקבוצה $\{A\}$ ולקבל כי $A\not \in A$. סתירה.

הפרדוקס של ראסל

הפרדוקס של ראסל עושה שימוש בכך שהקבוצה $A=\{x|x\not \in x\}$ הוא קבוצה, לכן ניתן לדבר על הטענה $A\in A$. לכל קבוצה $x$, הפעלת אקסיומת היסוד על הקבוצה $\{x\}$ תראה כי $x\not \in x$, לכן $A$ היא קבוצת כל הקבוצות, שהסברנו כבר שאינה מוגדרת.

הפרק הקודם: סדרות של קבוצות

תורת הקבוצות האקסיומטית

הפרק הבא: אינדוקציה טרנספיניטית