העולם של הקבוצות

1. הרקע הסמנטי

יש עולם קבוע שכל איבריו הם קבוצות. העולם מפרש את הכמתים $\forall ,\exists$.

יחסים בסיסיים

• שוויון $=$: יחס הזהות.
• שייכות $\in$: $x\in y$ אומר ”$x$ הוא איבר של $y$“. לכל $x,y$ מתקיים בדיוק אחד: $x\in y$ או $x\notin y$.
• הכלה $\subseteq$: $A\subseteq B$ אם $\forall x(x\in A\to x\in B)$.

מחלקות

אוסף חלקי של העולם המתואר על ידי נוסחה $\phi (x)$ נקרא מחלקה: $\{x\mid \phi (x)\}$. לא כל מחלקה היא קבוצה.

פרדוקס ראסל: המחלקה $\{x\mid x\notin x\}$ אינה קבוצה. אם הייתה קבוצה $B$: $B\in B⟺B\notin B$ — סתירה.

2. אקסיומות ZF

2.1 אקסיומת ההיקפיות (Extensionality)

$$A=B⟺\forall x(x\in A⟺x\in B)$$

שתי קבוצות שוות אם ורק אם יש להן אותם איברים.

מסקנה: הקבוצה הריקה יחידה (אם $A,B$ ריקות, הן שוות).

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

$$\exists X\forall y(y\notin X)$$

קיימת קבוצה ריקה, מסומנת $\varnothing$.

2.3 אקסיומת ההפרדה (Separation)

אם $A$ קבוצה ו-$\phi (x)$ נוסחה, אז:

$$\{x\in A\mid \phi (x)\}\text{ היא קבוצה}$$

מאפשרת להגדיר תת-קבוצות. מניעת פרדוקס ראסל: $\{x\in A\mid x\notin x\}$ קבוצה (תת-קבוצה של $A$), אך לא “כל הקבוצות”.

2.4 אקסיומת הזיווג (Pairing)

לכל $x,y$ יש קבוצה $\{x,y\}$.

שימוש: מגדיר את הזוג הסדור $⟨a,b⟩:=\{\{a\},\{a,b\}\}$.

אימות: $⟨a,b⟩=⟨c,d⟩⟺a=c\wedge b=d$. הוכחה: מהיקפיות, $\{a\}$ הוא איבר של הצד הימני, לכן $\{a\}=\{c\}$ (ולכן $a=c$) או $\{a\}=\{c,d\}$ (ולכן $a=c=d$). בשני המקרים מסיקים $b=d$.

2.5 אקסיומת האיחוד (Union)

אם $A$ קבוצה, אז $\bigcup A:=\{y\mid \exists x(x\in A\wedge y\in x)\}$ קבוצה.

דוגמה: $\bigcup \{A,B\}=A\cup B$.

2.6 אקסיומת קבוצת החזקה (Power Set)

אם $A$ קבוצה, אז $\mathcal{P}(A):=\{x\mid x\subseteq A\}$ קבוצה.

2.7 אקסיומת האינסוף

קיימת קבוצה המכילה $\varnothing$ וסגורה תחת $x\mapsto x\cup \{x\}$ (מגדירה $\mathbb{N}$).

2.8 אקסיומת ההחלפה (Replacement)

תמונת קבוצה תחת פונקציה (מוגדרת על ידי נוסחה) היא קבוצה.

2.9 אקסיומת הבסיס (Foundation/Regularity)

כל קבוצה לא-ריקה $A$ מכילה איבר $x\in A$ עם $x\cap A=\varnothing$. מונעת $x\in x$.

3. פעולות על קבוצות

$$A\cap B=\{x\mid x\in A\wedge x\in B\},A\cup B=\{x\mid x\in A\vee x\in B\}$$ $$A\setminus B=\{x\in A\mid x\notin B\},A\times B=\{⟨a,b⟩\mid a\in A,b\in B\}$$

4. אין ביקציה בין קבוצה לקבוצת החזקה שלה

משפט קנטור: לכל $f:A\to \mathcal{P}(A)$ — $f$ אינה על.

הוכחה: נגדיר $Y=\{x\in A\mid f(x)\notin x\}$. לכל $a\in A$: אם $a\in Y$ אז $f(a)\notin a$ לכן $a\notin Y$ — סתירה. לכן $Y\ne f(a)$ לכל $a$. $■$

ראה גם

• תכונות של פונקציות
• קבוצה סדורה קווית
• עקרון הסדר הטוב