הגדרה 1 (קבוצה)

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

\{ a,b,2,3\}=\{ a,b,2,3,3 \}

סימון: אם $a$ הוא איבר בקבוצה $A$ , נסמן: $a \in A$ .

דוגמה

1 \in \{ 1,a,2 \}

אם $a$ לא איבר ב- $A$ , נסמן $a \not\in A$ .

הנחת בסיס: לכל איבר $a$ ולכל קבוצה $A$ , בדיוק אחד מהשניים מתקיים: $a \in A$ או $a \not\in A$ .

אקסיומה 1

קבוצה A שווה לקבוצה B( $A=B$ ) ⇔ לכל $a \in A$ מתקיים $a \in B$ ולכל $b \in B$ מתקיים $b \in A$ .

קבוצות מפורסמות

המספרים הטבעיים $\mathbb{N}$ . בקורס זה(בניגוד לאינפי ואלגברה) $0 \in \mathbb{N}$ . ⇐ $\mathbb{N} =\{ 0,1,2,3,\dots \}$
המספרים הטבעיים ללא אפס $\mathbb{N}^+$
המספרים השלמים $\mathbb{Z}$ . ⇐ $\mathbb{Z}=\{ \dots,-2,-1,0,1,2,\dots \}$
המספרים הרציונליים $\mathbb{Q}$ . ⇐ $\mathbb{Q}=\left\{ \frac{m}{n}|m,n \in \mathbb{Z}, n\neq0 \right\}=\left\{ \frac{m}{n}|m \in \mathbb{Z}, n \in \mathbb{N}^+ \right\}$
המספרים הממשיים $\mathbb{R}$ ⇐ $\mathbb{R}=\{ -\infty<x<\infty \}$

הקבוצה הריקה

הגדרה 2 (הקבוצה הריקה)

קבוצה שאין בה אף איבר תקרא הקבוצה הריקה. קבוצה זו מקיימת כי $\forall a \not\in A$

\emptyset=\{ \}

הקבוצה הריקה אינה שקולה לקבוצה בה יש את הקבוצה הריקה

\emptyset \neq \{ \emptyset \}

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

הכלה

הגדרה 3 (הכלה)

אם לכל $a \in A$ מתקיים $a \in B$ נגיד כי הקבוצה A מוכלת בקבוצה B ונסמן כך:

A \subseteq B

ניתן להגיד כי A היא תת קבוצה של B.

דוגמה

\{ 1,2 \} \subseteq \{ 1,a,2 \}

ניתן להגיד כי $\mathbb{N}$ היא תת קבוצה של $\mathbb{Z}$ ונסמן כך: $\mathbb{N} \subseteq \mathbb{Z}$ .

תכונות של הכלה

לכל A: $A \subseteq A$
הסבר: כל איבר ב-A הוא איבר ב-A
לכל A: $\emptyset \subseteq A$
הסבר: כדי להוכיח $\emptyset \not\subseteq A$ יש למצוא $a \in \emptyset$ כך ש- $a \not\in A$
אין $a$ כזה כי $a \not\in \emptyset$ לכל $a$ .
לכן אין דוגמה נגדית והטענה נכונה.
לכל A,B: $A=B$ ⇔ $A \subseteq B$ וגם $B \subseteq A$ .
טרנזיטיביות ההכלה: לכל A,B,C: אם $A \subseteq B$ וגם $B \subseteq C$ אזי $A \subseteq C$ .
נוכיח: יהי $a \in A$ . מהנתון $a \in B$ ולכן $a \in C$ וכך, לפי ההגדרה $A \subseteq C$ .

איחוד

יהיו A,B קבוצו. אזי:

A \cup B= \{ a|a \in A\; \underline{or}\; a \in B \}

תורת הקבוצות 2025-11-02 11.36.50.excalidraw.svg

דוגמה

\{ 1,2 \} \cup \{ 2,3 \}=\{ 1,2,3 \}

משפט

לכל A: $A \cup \emptyset = A$
לכל A,B: $A \cup B=B \cup A$ (קומוטטיביות)
לכל A,B,C: $(A \cup B)\cup C= A \cup(B \cup C)$ (אסוציאטיביות)
לכל $A \subseteq B$ מתקיים $A \cup B = B$ .

חיתוך

הגדרה 4 (חיתוך)

A \cap B= \{ a| a \in A \land a \in B \}

תורת הקבוצות 2025-11-02 11.46.05.excalidraw.svg

דוגמה

\{ 1,2 \} \cap \{ 2,3 \} = \{ 2 \}

משפט

לכל A: $A \cap \emptyset = \emptyset$
לכל A,B: $A \cap B=B \cap A$
לכל A,B,C: $A \cap (B \cap C)=(A \cap B)\cap C$

חוק הפילוג

(A \cap B) \cup C = (A \cup C)\cap(B \cup C)

חוקי הפילוג מתקיימים בין קבוצות.
הוכחה:
יהי $a \in (A \cap B)\cup C$ .
לפי ההגדרה, ישנם שני מצבים אפשריים: או ש- $a \in A \cap B$ או ש- $a \in C$ .
לפי הגדרת החיתוך או ש-( $a \in A$ וגם $a \in B$ ) או ש- $a \in C$ .
⇐ אנו יודעים כי $a \in C$ או ש- $a \in A$ . ⇐ $a \in A \cup C$
⇐ וגם או ש- $a \in C$ או ש- $a \in B$ . ⇐ $a \in B \cup C$
ולכן:

a \in (A \cup C) \cap (B \cup C)

כמובן שנצרך להוכיח לכיוון השני או שכל הטענות צריכות להיות אמ"א(במקרה הזה הן כן) כדי להוכיח
‎∎

ניתן גם להראות כי:

(A \cup B) \cap C = (A \cap C) \cup (B \cap C)

חיסור

A \setminus B=\{ a| a \in A \land a \not\in B \}

דוגמה

\{ 1,2 \} \setminus \{ 2,3 \}=\{ 1 \}

הגדרה 5

לכל A: $A \setminus \emptyset = A$ וגם $\emptyset \setminus A = \emptyset$

השלמה

הגדרה 6 (קבוצה משלימה)

הקבוצה המשלימה של $A$ כאשר אנחנו תחת קבוצת עולם $W$ הינה $W \setminus A$ .
נסמן:

\overline{A}=W \setminus A

דוגמה

במידה והעולם הוא $\mathbb{R}$ אזי $\overline{\mathbb{Q}}$ הוא קבוצת האי רציונליים.
במידה והעולם הוא $\mathbb{N}$ (כולל 0) אזי $\overline{\mathbb{N}^+}=\{ 0 \}$

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

הערה

למה כל מה שלמדנו היום הוא שקר :)

אם כל דבר יכול להיות איבר, גם $A$ יכולה להיות איבר ב- $A$ .

דוגמה (קבוצת כל הקבוצות)

אם קבוצה מכילה את כל הקבוצות אזי גם אותה קבוצה מוכלת בקבוצה הזו.

דוגמה (קבוצת כל הדברים שניתן לתאר בעזרת שמונה מילים)

מכיוון שאת הקבוצה ניתן לתאר בעזרת 8 מילים, היא שייכת לעצמה(כפי שניתן לראות בכותרת)

הגדרה 7

S=\{ A|A \not\in A \}

אנו מכירים כמה קבוצות כאלו: $\mathbb{N},\emptyset,\{ 1,2,3 \}\in S$ .

האם S שייכת ל-S?

אם כן אזי $S$ לא אמורה להיות שייכת ל-S.
אם לא אזי $S$ אמורה להיות שייכת ל-S.

כך הגענו לפרדוקס:

S \not\in S \iff S \in S

זוהי סתירה להנחת הבסיס.

הערה

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

כללי דה מורגן

משפט (כללי דה-מורגן)

לכל שתי קבוצות $A,B$ :

\overline{A \cap B}=\overline{A}\cup \overline{B}

\overline{A \cup B}=\overline{A}\cap \overline{B}

הוכחה: (1)
על מנת להוכיח שוויון בין קבוצות נוכיח הכלה דו כיוונית:
יהי $x \in \overline{A \cap B}$ .
על פי הגדרת המשלים:

x \in \overline{A \cap B} \iff x \not\in A \cap B

על פי הגדרת החיתוך:

x \not\in A \cap B \iff x \not\in A \lor x \not\in B

על פי הגדרת השלמה:

x \not\in A \lor x \not\in B \iff x \in \overline{A} \lor x \in \overline{B}

על פי הגדרת האיחוד:

x \in \overline{A} \lor x \in \overline{B} \iff x \in \overline{A} \cup \overline{B}

‎∎

הערה

את $2$ אפשר להוכיח באופן דומה.

הכללת איחוד וחיתוך

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

הגדרה 8 (הכללת איחוד)

יהיו $A_{1},A_{2},\dots A_{n}$ קבוצות.
נגדיר:

\bigcup_{1\leq i \leq n}A_{i}=\{ x| \exists 1 \leq i \leq n:\ x \in A_{i} \}

דוגמה

A_{1}=\{ 1,2 \}\quad A_{2}=\{ 2, 5 \}\quad A_{3}=\{ 5 \}

\bigcup_{1\leq i \leq 3}A_{i}=\{ 1,2,5 \}

כעת נאחד $\infty$ קבוצות.

הגדרה 9 (איחוד כללי אינסופי)

יהיו $A_{1},A_{2},A_{3},\dots$ קבוצות.
נגדיר:

\bigcup_{1\leq i}A_{i}=\{ x|\exists\ i\geq1\text:\; x \in A_{i} \}

דוגמה

A_{1}=\{ 1 \}\quad A_{2}=\{ 1,2 \}\quad A_{3}=\{ 1,2,3 \}\quad\dots

\bigcup_{i\leq 1}A_{i}=\mathbb{N}^+

הגדרה 10 (חיתוך כללי אינסופי)

יהי $A_{1},A_{2},A_{3},\dots$ קבוצות. אזי:

\bigcap_{1\leq i}A_{i}=\{ x | \forall i \geq 1:\ x \in A_{i} \}

הגדרה 11 (קבוצת החזקה)

תהי $A$ קבוצה. קבוצת החזקה של $A$ היא קבוצת כל תת הקבוצות של $A$ :

P(A)=\{ B|B \subseteq A \}

לפעמים מסמנים $2^A$ .

דוגמה

A=\{ 1,2 \} \qquad P(A)=\{ \emptyset,\{ 1 \},\{ 2 \},\{ 1,2 \} \}

P(\emptyset)=\{ \emptyset \}

P(\{ \emptyset \})=\{ \emptyset,\{ \emptyset \} \}

מכפלה קרטזית וזוגות סדורים

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

הגדרה 12 (זוג סדור)

זוג סדור הינו זוג איברים $(a,b)$ כך ש:

(a,b)=(c,d) \iff a=c \land b=d

נגדיר פעולה מעל 2 קבוצות שיוצרת קבוצה שבה כל הזוגות הסדורים מהקבוצות הללו:

הגדרה 13 (מכפלה קרטזית)

בהינתן קבוצה $A$ וקבוצה $B$ , נקרא מכפלה קרטזית לקבוצת כל הזוגות הסדורים של אברי $A$ עם איברי $B$ :

A\times B=\{ (a,b)|a \in A \land b \in B \}

דוגמה

\{ 1,2 \}\times \{ a,b,c \}=\{ (1,a),(1,b),(1,c),(2,a),(2,b),(2,c) \}

\{ 1,2 \}\times \{ 1,2 \}=\{ (1,1),(1,2),(2,1),(2,2) \}

הערה

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

תכונות של מכפלה קרטזית

לא קומוטטיבית: $\{ 1 \}\times \{ a \}=\{ \{ 1,a \} \}$ ולעומת זאת $\{ a \}\times \{ 1 \}=\{ (a,1) \}$
לכל קבוצה $A$ : $A\times \emptyset=\emptyset=\emptyset \times A$
הסבר: מההגדרה, אנו יודעים כי אין $b \in \emptyset$ ולכן, אנו מקבלים רשימה ריקה של זוגות סדורים ולכן הקבוצה הריקה.
לכל $A,B$ : אם $A\times B=\emptyset$ אם ורק אם $A=\emptyset$ או $B=\emptyset$ .
הסבר:
נניח כי $A\times B=\emptyset$ אבל $A\neq \emptyset$ וגם $B \neq \emptyset$ .
אם $A\neq \emptyset$ אזי קיים $a \in A$
אם $B \neq \emptyset$ אזי קיים $b \in B$
⇐ מהגדרת $A\times B$ קיים הזוג הסדור $(a,b)$ ב- $A\times B$ , סתירה לנתון ש- $A\times B=\emptyset$ .
לכל $A,B,C$ : אם $A \subseteq B$ , אז $A\times C \subseteq B\times C$ (מוטוניות)
הסבר:
נניח $A \subseteq B$ . יהי $(a,c)\in A\times C$ . אזי $a \in A$ וגם $c \in C$ .
מהנתון, אנו יודעים כי $a \in B$ ולכן $(a,c)\in B \times C$
ולכן, $A\times C \subseteq B\times C$
לכל $A,B,C$ : נקח פעולה $😊$ כאשר $😊 \in \{ \cap,\cup,\setminus \}$ . אזי:
$(A 😊 B)\times C=(A\times C)😊(B\times C)$
הוכחה, עבור איחוד:
נראה שוויון באמצעות הכלה דו כיוונית.
$x = (a,c) \in(A \cup B)\times C \iff a \in A \cup B \land c \in C \iff (a \in A \lor a \in B) \land c \in C$
$\iff (a \in A \land c \in C)\lor (a \in B \land c \in C) \iff (a,c) \in A\times C \lor (a,c)\in B\times C$
$\iff x \in (A\times C)\cup(B\times C)$

הרחבה של מכפלה קרטזית ל- $k$ איברים סדורים

הגדרה 14 (מכפלה קרטזית ל-

k

איברים)

נקרא ל- $(a_{1},a_{2},\dots a_{k})$ $k$ -יה סדורה.
בהתאמה, נרחיב את המכפלה הקרטזית ל- $k$ קבוצות:

A_{1}\times A_{2}\times\dots \times A_{k}=\{ (a_{1},\dots,a_{k})|\forall 1\leq i\leq k:\ a_{i} \in A_{i} \}

דוגמה

\{ 1,2 \}\times \{ a \}\times\{ \gamma \}=\{ (1,a,\gamma),(2,a,\gamma) \}

הערה

(A_{1}\times A_{2})\times A_{3}=\{ ({\color{lightblue}{(a,b)}},{\color{green}c})|a \in A_{1},b \in A_{2}, c \in A_{3} \}

פעולה זו אינה אסוציאטיבית.

יחסים

מוטיבציה

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

דוגמה

15 מתחלק ב-3 ⇐ קשר בין מספרים ב- $\mathbb{Z}$ .

דוגמה

\{ 1 \}\subseteq \{ 1,2 \}

זהו קשר בין קבוצות

נניח קשר בין איברים בסדרה כפי שראינו בדוגמה 1:

\{ (m,n)|m,n \in \mathbb{Z},\; \exists q:\ n\cdot q=m \} \subset \mathbb{Z}\times \mathbb{Z}

הקבוצה הזו נקראת יחס מעל השלמים.

פורמליות

הגדרה 15 (יחס דו מקומי)

יחס דו מקומי $R$ מקבוצה $A$ ל- $B$ הוא

R \subseteq A\times B

דוגמה

A=\{ 1,2,3 \}\quad B=\{ a,b \}

ולכן, יכול להיות בינהם יחס כך:

R_{1}=\{ (1,a),(2,b),(1,b) \}

ישנם עוד יחסים כגון:

R_{2}=\{ (1,b) \}

R_{3}=\emptyset

R_{4}=A\times B

נסתכל על תיאור גרפי של היחס $R_{1}$ :
1 - תורת הקבוצות 2025-11-16 10.52.51.excalidraw.svg

באופן כללי:

הגדרה 16 (יחס

R

מקומי)

יחס $R$ מקומי של קבוצות $A_{1},A_{2},\dots,A_{k}$ הינו:

R \subseteq A_{1}\times\dots \times A_{k}

פעולות על יחסים

1. הרכבת יחסים

הגדרה 17 (הרכבת יחסים)

יהי $R \subseteq A\times B$ ו- $S \subseteq B\times C$ ;.
ההרכבה של $S$ על $R$ הינה:

S \circ R=\{ (a,c)|\exists b \in B:\ (a,b)\in R \land (b,c) \in S \} \subseteq A\times C

דוגמה

A=\{ 1,2,3 \}\quad B=\{ a,b \}\quad C=\{\ :),:(\ \}

1 - תורת הקבוצות 2025-11-16 11.01.48.excalidraw.svg
נראה את היחס כעת:

\begin{cases} R=\{ (1,a),(2,a) \} \\ S=\{ (a,\ :)\ ),(b,\ :( \ ) \} \end{cases} \implies S \circ R=\{ (1, :)\ ),(2, :)\ ) \}

תכונות של הרכבה

1. אי קיום קומוטטיביות

R \subseteq A\times B \quad S \subseteq B\times C

הגדרנו את: $S \circ R$ .
מה לגבי $R \circ S$ ? הוא לא בהכרח מוגדר. גם במקרה שכן, לא בהכרח: $R \circ S=S \circ R$ .

2. קיום אסוציאטיביות

יהיו $R \subseteq A\times B,\quad S \subseteq B\times C, \quad T \subseteq C \times D$ .

T \circ(S \circ R) =(T \circ S)\circ R

הוכחה:
נראה הכלה דו כיוונית:

(a,b)\in T \circ(S \circ R) \iff \exists c \in C:\ (a,c) \in S \circ R \land (c,d)\in T

\iff \exists c \in C:\ \exists b \in B:\; (a,b)\in R \land (b,c) \in S \land (c,d) \in T

\iff \exists b \in B:\ \exists c \in C:\; (a,b) \in R \land (b,c)\in S \land (c,d)\in T

\iff \exists b \in B:\ (a,b) \in R \land (b,d)\in T \circ S

\iff (a,b) \in (T \circ S)\circ R

מכיוון שמתקיימת הכלה דו כיוונית:

T \circ(S \circ R) =(T \circ S)\circ R

‎∎

2. חזקה של יחסים

הגדרה 18 (חזקה של יחסים)

יהי $R \subseteq A\times A$ (" $R$ יחס מעל $A$ ").
נגדיר:

R^i=\underbrace{R \circ R \circ \dots \circ R}_{i}

יותר פורמלית נגדיר:

R^0 = \{ (a,a)|a \in A \}

לכל $i>0$ : $R^i=R^{i-1}\circ R$ .

דוגמה

R^2=R^1 \circ R=R^0 \circ R \circ R=\{ (a,a)|a \in R \}\circ R \circ R

החזקה $R^0$ הינו אדיש להרכבה. ( $R^0 \circ R=R$ ו- $R \circ R^0=R$ )
נקבל כי:

R^2=R \circ R

דוגמה (

R

מעל

\mathbb{N}

)

R=\{ (n,n+1)| n \in \mathbb{N} \}=\{ (0,1),(1,2),\dots \}

R^2=\{ (n,n+2)|n \in \mathbb{N} \}

R^i=\{ (n,n+i)|n \in \mathbb{N} \}

הערה

בדוגמה הקודמת, אם נקח:

\bigcup R^i=\{ (n,m)| n\leq m \}

כלומר, היחס $\leq$ מעל $\mathbb{N}$ .

התקיימות חוקי חזקות

משפט

לכל $i,j$ :

R^i \circ R^j=R^{i+j}

3. היפוך של יחסים

הגדרה 19 (היפוך יחס)

יהי $R \subseteq A\times B$ אזי היחס ההפוך הינו $R^{-1}\subseteq B\times A$ כך:

R^{-1}=\{ (b,a)|(a,b) \in R \}

תכונות

1. היפוך של היפוך

(R^{-1})^{-1}=R

2. היפוך של הרכבה:

(S \circ R)^{-1}=R^{-1} \circ S^{-1}

נשים לב כי הסדר שלהם משתנה.
הוכחה:

(c,a) \in (S \circ R)^{-1} \iff (a,c) \in S \circ R

\iff \exists b \in B:\ (a,b) \in R \land (b,c) \in S

\iff \exists b \in B:\ (b,a) \in R^{-1} \land (c,b) \in S^{-1}

\iff (c,a) \in R^{-1} \circ S^{-1}

‎∎

הערה

כאשר $(a,b)\in R$ מסמנים $aRb$ ולפעמים גם אומרים: $a$ מתייחס ל- $b$ .

מסקנה/עוד משפט

משפט

מתקיים גם:

R^{-i}\equiv (R^{-1})^i = (R^i)^{-1}

יחסים מעל $A$

לכל קטע זה נסמן:

R \subseteq A\times A

הנה כמה תכונות של יחסים יחודיים אלו:

תכונות

1. רפלקסיביות

הגדרה 20 (יחס רפלקסיבי)

היחס $R$ נקרא רפלקסיבי אם לכל $a \in A$ מתקיים $aRa$ .

R=\{ (1,1),(2,2),(3,3),(1,3) \}

לעומת זאת, היחס הבא אינו רפלקסיבי:

R=\{ (1,1),(2,2),(1,3) \}

הערה

אנו צריכים לדעת מעל איזו קבוצה מוגדר היחס כדי לדעת מה תכונות שלו. נניח היחס:

R=\{ (1,1),(2,2) \}

אשר אינו רפלקסיבי מעל $A$ אך רפלקסיבי מעל $\{ 1,2 \}$ .

2. סימטריות

הגדרה 21 (סימטריות)

היחס $R$ נקרא סימטרי אם לכל $aRb$ מתקיים $bRa$ .

R=\{ (1,2),(2,1),(3,3) \}

הערה

היחס הריק הוא סימטרי באופן ריק.

R=\emptyset

3. אנטי סימטריות

הגדרה 22 (אנטי-סימטריות)

היחס $R$ נקרא אנטי-סימטרי אם לכל $aRb$ ו- $bRa$ מתקיים $a=b$ .
(באופן שקול: אם $a \neq b$ אז או $(a,b)\not\in R$ או ש- $(b,a)\not\in R$ )

דוגמה

R=\{ (1,2),(1,1) \}

זהו יחס אנטי סמטרי.

R=\{ (1,1),(2,2) \}

זהו יחס אנטי סמטרי וגם יחס סימטרי.

R=\{ (1,3),(1,2),(2,1) \}

היחס הנ"ל אינו סמטרי ואינו אנטי סמטרי.

4. טרנזיטיביות

הגדרה 23 (טרנזיטיביות)

היחס $R$ הינו טרנזיטיבי אם לכל $aRb$ ו- $bRc$ מתקיים: $aRc$ .

דוגמה

R=\{ (1,2),(2,3),(1,3),(1,1) \}

זהו יחס טרנזיטיבי.

קשר בין פעולות לתכונות

היחס $R$ רפלקסיבי ⇔ $R^0 \subseteq R$
היחס $R$ סימטרי ⇔ $R^{-1}=R$
היחס $R$ טרנזיטיבי ⇔ $R^2 \subseteq R$

הגדרה 24 (יחס סדר (חלקי))

יחס $R$ מעל $A$ נקרא יחס סדר (חלקי) אם הוא: רפלקסיבי, אנטי סימטרי וטרנזיטיבי.

דוגמה

A=\{ 1,2,\dots,6 \}

והיחס "מחלק את"
אנו יודעים, מכיוון שדיברנו על התכונות שלו, כי הוא יחס סדר.
1 - תורת הקבוצות 2025-11-23 10.44.18.excalidraw.svg

דוגמה

היחס $\leq$ מעל $\{ 1,2,3 \}$ . נצייר גם אותו:
1 - תורת הקבוצות 2025-11-23 10.48.02.excalidraw.svg

דוגמה

היחס $\subseteq$ מעל קבוצת קבוצות:

P(\{ 1,2 \})=\{ \emptyset,\{ 1 \},\{ 2 \},\{ 1,2 \} \}

1 - תורת הקבוצות 2025-11-23 10.51.25.excalidraw.svg

הגדרה 25 (יחס סדר מלא)

יחס סדר מלא $R$ הוא יחס סדר חלקי שבו לכל $a,b \in A$ : $aRb$ או $bRa$ .

דוגמה

היחס $\leq$ מעל $\{ 1,2,3 \}$ הינו יחס סדר מלא.
לעומת זאת, $\subseteq$ מעל $P(\{ 1,2 \})$ הוא יחס סדר חלקי שאינו מלא.

הגדרה 26 (יחס שקילות)

יחס $R$ מעל $A$ נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.

דוגמה

A=\{ 1,2,3 \}

R=\{ (1,1),(2,2),(3,3),(1,3),(3,1) \}

1 - תורת הקבוצות 2025-11-23 11.07.48.excalidraw.svg

מחלקות שקילות

הגדרה 27 (מחלקת שקילות)

יהי $R$ יחס שקילות מעל $A$ .
נגדיר את מחלקת השקילות של $a \in A$ :

[a]_{R}= \{ b | aRb \}

הגדרה 28 (חלוקה של

A

)

תהי $A$ קבוצה. חלוקה של $A$ היא קבוצת קבוצות: $\{ S_{1},S_{2},\dots \}$ כך ש:

לכל $i\geq1$ מתקיים $S_{i}\neq \emptyset$ .
לכל $1\leq i<j$ מתקיים $S_{i}\cap S_{j}=\emptyset$ .
מתקיים: $\bigcup_{i\geq1}S_{i}=A$ .

משפט

יהי $R$ יחס שקילות מעל $A$ . אזי $\{ [a]_{R}|a \in A \}$ הינו חלוקה של $A$ .

הוכחה:
תהי $[a]_{R}$ מחלקת שקילות. $R$ הינו רפלקסיבי, לכן, $aRa$ ומהגדרת $[a]_{R}$ אנו יודעים כי $a \in [a]_{R}$ ⇐ $[a]_{R}\neq \emptyset$ .
מאחר ש- $a \in [a]_{R}$ לכל $a \in A$ מתקיים $\bigcup_{a \in A}[a]_{R}=A$

נראה כי לכל $a,b \in A$ :

אם $aRb$ אזי $[a]_{R}=[b]_{R}$ .
אם $(a,b)\not\in R$ אזי $[a]_{R}\cap [b]_{R}=\emptyset$ .

נניח כי $aRb$ . נוכיח באמצעות הכלה דו כיוונית.
יהי $c \in [a]_{R}$ . מההגדרה, אנו יודעים כי $aRc$ .
מסמיטריות $R$ , נדע כי $bRa$ ולכן, מטרניזיטביות $R$ , נקבל כי $bRc$ .
ולכן, $c \in [b]_{R}$ ולכן: $[a]_{R}\subseteq[b]_{R}$ .
באותה הדרך, רק בהיפוך $a$ ו- $b$ , נראה כי $[b]_{R}\subseteq[a]_{R}$ .
ולכן, $[a]_{R}=[b]_{R}$ .

נניח $a \cancel{R}b$ . נניח בשלילה כי קיים $c$ כך ש: $c \in [a]_{R}\cap[b]_{R}$ .
מהגדרת $[a]_{R}$ מתקיים $aRc$ ומהגדרת $[b]_{R}$ מתקיים $bRc$ .
באמצעות הסימטריה מעל $R$ אנו יודעים כי $cRb$ ולכן, לאור הטרנזיטיביות ב- $R$ , $aRb$ וזוהי סטירה.
‎∎

דוגמה (ההגדרה המדוייקת של המספרים הרציונליים)

הגדרנו את $\mathbb{Q}$ כך:

\mathbb{Q}=\left\{\begin{array}{c|c} \frac{m}{n} & m \in \mathbb{Z},n \in \mathbb{N}^+ \end{array}\right\}

נגדיר יחס מעל האיברים מהצורה $\frac{m}{n}$ שיבטא את הזהות הסמנטית שלהם.
הצעה: השברים $\frac{m}{n}, \frac{m'}{n'}$ שווים כאשר מתרחש: $m\cdot n'=m'\cdot n$ .
נשים לב כי זהו יחס שקילות:

רפלקסיבי: מכיוון ש- $m\cdot n=m\cdot n$ .
סימטרי: נובע מסימטריות השוויון
טרנזיטיביות: נובע מטרנזיטיביות של השוויון.

⇐ זהו אכן יחס שקילות ⇐ היחס מחלק את $\left\{ \frac{m}{n}|\dots \right\}$ למחלקות שקילות.
כעת, נגדיר: $\mathbb{Q}$ הינו אוסף מחלקות השקילות.

הערה

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

פונקציות

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

\{ (a_{1},f(a_{1})),\underbrace{(a_{2},f(a_{2}))}_{\R{יחס}},\dots \}

הגדרה 29 (פונקציה)

פונקציה $f$ מ- $A$ ל- $B$ היא $f \subseteq A\times B$ המקיים:

קיום: לכל $a \in A$ קיים $b \in B$ כך ש- $(a,b)\in f$ .
יחידות: לכל $a \in A$ ו- $b_{1},b_{2} \in B$ מתקיים שאם $(a,b_{1}),(a,b_{2})\in f$ אזי $b_{1}=b_{2}$ .

נסמן: $f: A\to B$ . כאשר $A$ הוא התחום ו- $B$ היא טווח.
כמו כן, אם $afb$ נסמן: $f(a)=b$ .

דוגמה

נסתכל על היחס הבא אשר הינו פונקציה:
1 - תורת הקבוצות 2025-11-30 10.40.45.excalidraw.svg
והיחס הבא אשר אינו פונקציה:

דוגמה (נסתכל על כמה דוגמות מוכרות)

$f:\mathbb{R}\to \mathbb{R} \qquad \forall x \in A:\; f(x)=x^2$
ואז: $\left\{ (1,1),(2,4),\left( \frac{1}{2}, \frac{1}{4} \right),\dots \right\}$
$f_{2}:A\to P(A) \qquad \forall a \in A:\; f_{2}(a)=\{ a \}$
דוגמה: [להוסיף לבד]
יהי $R$ יחס שקילות מעל $A$ . נגדיר: $f_{3}:A\to P(A) \qquad \forall a \in A:\; f(a)=[a]_{R}$
לדוגמה: $R=\{ (1,2),(2,1),(1,1),(2,2),(3,3) \}$ תהיה הפונקציה הבאה: $f_{3}=\{ (1,\{ 1,2 \}),(2,\{ 1,2 \}),(3,\{ 3 \}) \}$
$f_{4}:\underbrace{P(A)\times P(A)}_{\R{\text{זוגות סדורים של תת הקבוצות של A}}}\to P(A)$
$\forall(B,C)\in P(A)\times P(A):\; f_{4}((B,C))=B \cup C$
$I_{A}:A\to A \qquad \forall a \in A:\; I_{A}(a)=a$ זוהי פונקצית הזהות אשר אותה ניתן להגדיר לכל קבוצה.

הגדרה 30 (תמונה)

התמונה של $f:A\to B$ היא $\mathrm{Im}(f)=\{ b \in B|\exists a \in A:\; f(a)=b \}$ .

הערה

זה בעצם כל איברי $b$ שלהם יש $a$ מתאים בפונקציה. נניח, כל $b\geq0$ בפונקציה: $f(x)=x^2=b$ .

הגדרה 31 (קבוצת כל הפונקציות)

קבוצת כל הפונקציות מ- $A$ ל- $B$ תסומן: $B^A$ .

דוגמה

\{ 1,2 \}^{\{ a \}}=\{ \underbrace{\begin{matrix}\\ a\end{matrix} \nearrow \begin{matrix} 1 \\ 2\end{matrix}}_{f_{1}}, \underbrace{\begin{matrix}a \\ \\ \end{matrix} \searrow \begin{matrix} 1 \\ 2\end{matrix}}_{f_{2}} \}

ראינו כי אם $f \subseteq A\times B$ ו- $g \subseteq B\times C$ , אז $g \circ f \subseteq A\times C$ .

g \circ f=\{ (a,c)|\exists b \in B:\; afb \land bgc \}

תרגיל

אם $f,g$ פונקציות, האם בהכרח $g \circ f$ פונקציה?

כן. אם $f,g$ מקיימות קיום ויחידות, אזי גם $g \circ f$ .
נוכיח כעת:
קיום: יהי $a \in A$ . $f$ פונקציה וכל קיים $b \in B$ כך ש- $f(a)=b$ . $g$ היא גם פונקציה ולכן קיים $c \in C$ כך ש- $g(b)=c$ .
מהגדרת הרכבה: $a (g \circ f) c$ .
יחידות: יהי $a \in A$ . יהיו $c_{1},c_{2} \in C$ כך ש: $(a,c_{1}),(a,c_{2})\in g \circ f$ .
מהגדרת הרכבה: קיימים $b_{1},b_{2}$ כך ש:

\begin{matrix} (b_{1},c_{1}) \in g \quad (a,b_{1})\in f \\ (b_{2},c_{2})\in g \quad (a,b_{2})\in f \end{matrix}

מיחידות $f$ : $b_{1}=b_{2}=b$ . מיחידות $g$ : $c_{1}=c_{2}$ .
ולכן $g \circ f:A\to C$ . נכתוב: $g \circ f(a)=c$ או $g(f(a))=c$ .
∎

תכונות של פונקציות

הגדרה 32 (על)

$f:A\to B$ נקראת על אם $\mathrm{Im}(f)=B$
כלומר: לכל $b \in B$ קיים $a \in A$ כך ש- $f(a)=b$ .

כלומר, לכל $b \in B$ נכנסת לפחות קשת אחת.

הגדרה 33 (חד-חד ערכית)

$f$ נקראת חד-חד ערכית(חח"ע) אם לכל $a_{1},a_{2} \in A$ ולכל $b \in B$ במידה ו- $f(a_{1})=b$ וגם $f(a_{2})=b$ אזי מתקיים $a_{1}=a_{2}$ .

כלומר, לכל $b \in B$ נכנסת לכל היותר קשת אחת.

מה קורה אם הפונקציה היא גם חח"ע וגם על? אזי לכל $b \in B$ נכנסת בדיוק קשת אחת.

דוגמה

$f_{1}: \mathbb{R}\to\mathbb{R} \qquad \forall x \in \mathbb{R}:\; f_{1}(x)=x^2$
זוהי פונקציה אשר אינה חח"ע, שכן יש איבר כגון $f_{1}(1)=f_{1}(-1)$ .
זוהי פונקציה אשר אינה על, שכן $-1$ , נניח, אינו בתמונה.
$\tilde{f_{1}}=\mathbb{R}\to \mathbb{R}^+ \qquad \forall x \in A:\; \tilde{f_{1}}=x^2$
זוהי פונקציה אשר אינה חח"ע, שכן יש איבר כגון $f_{1}(1)=f_{1}(-1)$ .
זוהי פונקציה אשר הינה על.
$\tilde{\tilde{f_{1}}}:\mathbb{R}^+\to \mathbb{R}^+ \qquad \forall x \in A:\; \tilde{\tilde{f_{1}}}(x)=x^2$
הפונקציה הינה גם חחע וגם על.

הערה

פונקציה נקראת מוגדרת היטב אם היא אכן פונקציה.

דוגמה (דוגמות לפונקציות מתחזות)

4. $g: \mathbb{R}\to \mathbb{R} \qquad \forall x \in \mathbb{R}: g(x)= \frac{1}{x}$
הבעיה עם הפונקציה הזו היא שהיא אינה מוגדרת ל- $0$ ולכן אינה מקיימת קיום.
הפתרון: $\tilde{g}:\mathbb{R} \setminus \{ 0 \}\to \mathbb{R}$ . כעת, מוגדרת היטב.
5. $g_{2}:\mathbb{R}\to \mathbb{R} \qquad \forall x \in A:\; g_{2}(x)=\pm \sqrt{ x }$
אין יחידות: עבור 4, $g_{2}$ מתיימרת להחזיר שני ערכים שונים: $-2,2$ .
אין קיום: הפונקציה אינה מוגדרת לערכים שליליים.
6. $A$ קבוצה, $R$ יחס שקילות מעל $A$ ונגדיר $g_{3}:P(A)\to A$ כך ש- $\forall B \in P(A):\; g_{3}(B)=a$ עבור $B=[a]_{R}$
אין קיום: לא כל תת קבוצה היא מחלקת שקילות. למשל, $\emptyset$ .
אין יחידות: בהנתן מחלקת שקילות. יתכן ויש לה יותר מנציג אחד.

פונקציה הופכית

נשים לכ בי:

חח"ע היא דואלית לתכונת היחידות (דואלית = הגדרה זהה בהיפוך התפקידים של $A,B$ )
על היא דואלית לתכונות הקיום.

ולכן, אם $f:A\to B$ חח"ע ועל אזי, $f^{-1}:B\to A$ מוגדרת היטב וגם היא חח"ע ועל.
הסבר אינטואיטיבי: אם $f$ חח"ע ועל אז לכל $b \in B$ נכנסת בדיוק קשת אחת. ⇐ ב- $f^{-1}$ יוצאת בדיוק קשת אחת מכל $b \in B$ ⇐ היא פונקציה.
מכל $a \in A$ ב- $f$ יוצאת בדיוק קשת אחת ⇐ ב- $f^{-1}$ נכנסת בדיוק קשת אחת לכל $a \in A$ ⇐ חח"ע ועל.

הגדרה 34 (פונקציה הפיכה)

פוקציה הפיכה הינה פונקציה אשר הינה חח"ע ועל.

הגדרה 35 (פונקציה הופכית)

תהי $f:A\to B$ פונקציה הפיכה. נקרא ל- $f^{-1}$ הפונקציה ההופכית שלה ⇔ $f^{-1}:B\to A$ ולכל $f(a)=b$ מתקיים $f^{-1}(b)=a$ .

הערה

אם $f:A\to B$ הפיכה, אזי:

f^{-1}\circ f=I_{A}

f \circ f^{-1}=I_{B}

משפט

יהיו $f:A\to B,g:B\to C$ פונקציות חח"ע ועל. אזי $g \circ f:A\to C$ חח"ע ועל.

הערה

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

הוכחה: נראה כי חח"ע ועל נשמרות תחת הרכבה.
⇐ הפונקציות $f,g$ חח"ע. נוכיח: $g \circ f$ חח"ע.
יהיו $c \in C$ , $a_{1},a_{2}\in A$ כך ש: $g(f(a_{1}))=c,g(f(a_{2}))=c$ .
מההרכבה, קיימים $b_{1},b_{2} \in B$ כך ש:

\begin{matrix} f(a_{1})=b_{1}, \quad g(b_{1})=c \\ f(a_{2})=b_{2}, \quad g(b_{2})=c \end{matrix}

הפונקציה $g$ חח"ע ולכן, $b_{1}=b_{2}=b$ ולכן, מכיוון שהפונקציה $f$ חח"ע, $a_{1}=a_{2}=a$ .

⇐ הפוקציות $f,g$ על. נוכיח: $g \circ f$ על.
יהי $c \in C$ . מכיוון ש- $g$ על, קיים $b \in B$ כך ש- $g(b)=c$ . מכיוון ש- $f$ על, קיים $a \in A$ כך ש- $f(a)=b$ .
מההרכבה, $g(f(a))=c$ לכל $c \in C$ .
∎

עוצמות של קבוצות

יהיו $A,B$ שתי קבוצות.נגדיר יחס $\sim$ כך ש- $A \sim B$ אם קיימת $f:A\to B$ הפיכה.
(כלומר, רוצים להגדיר מתי ב- $A,B$ ישנה אותה כמות איברים).

טענה

תהי $X$ קבוצה של קבוצות.
אזי $\sim$ הינו יחס שקילות מעל $X$ .

הוכחה:
נוכיח שהיחס הוא רפלקסיבי, סימטרי וטרנזיטיבי.
רפלקסיבי: פונקצית הזהות $I_{A}:A\to A$ היא חח"ע ועל ולכן, ב- $A$ יש את אותה כמות איברים ב- $A$ .
סימטרי: יהיו $A,B$ קבוצות כך ש- $A \sim B$ ולכן קיימת $f:A\to B$ הפיכה.
הראנו כי אם $f$ הפיכה, אזי $f^{-1}:B\to A$ הפיכה גם כן.
טרנזיטיבי: יהיו $A,B,C$ קבוצות כך ש: $A \sim B,B \sim C$ .
אזי קיימת: $f:A\to B$ הפיכה ו- $g:B\to C$ הפיכה.
ראינו כי $g \circ f:A\to C$ הפיכה על פי משפט ⇐ $A \sim C$ .
∎

משפט (סימון חדש)

אם $A \sim B$ נסמן: $|A|=|B|$ (כאשר $|A|$ מסמן את העוצמה של $A$ ).

הגדרה 36

נסמן $|A|\leq |B|$ אם קיימת $f:A\to B$ שהיא חח"ע.

דוגמה

נקח את $\{ a,b,c \}$ ואת $\mathbb{N}$ .
נראה פונקציה חח"ע מ- $A$ ל- $\mathbb{N}$ כאשר: $a\to1,b\to2,c\to3$ ומכאן ש- $|\{ a,b,c \}|\leq |\mathbb{N}|$ .

קבוצות סופיות

הגדרה 37 (קבוצה סופית)

$A$ היא סופית אם קיים $k \in \mathbb{N}$ כך ש- $\{ 1,2,\dots,k \}\sim A$

הערה

נגדיר $\{ 1,2\dots,0 \}\neq \emptyset$ .

דוגמה

$\{ 1, a, \lambda \}\sim \{ 1,2,3 \}$ לכן, קיים $k$ כנדרש והקבוצה סופית.

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

הגדרה 38 (קבוצה אינסופית)

$A$ היא אינסופית אם לכל $k \in \mathbb{N}$ מתקיים כי $A \not\sim \{ 1,2,\dots,k \}$ .

משפטים ותכונות

משפט

קיימת $f:A\to B$ פונקציה חח"ע ⇔ קיימת $g:B\to A$ על.

משפט (משפט קנטור-שרדר-ברנשטיין)

אם $|A|\leq |B|$ וגם $|B|\leq |A|$ ואזי: $|A|=|B|$ .

הערה

כלומר: אם קיימת $f:A\to B$ חח"ע וקיימת $g:B\to A$ חח"ע אזי קיימת $h:A\to B$ הפיכה.

דוגמה

נקח $\mathbb{N},\mathbb{N}_{2}=\{ 2n|n \in \mathbb{N} \}$ .

f:\mathbb{N}_{2}\to N:\quad \forall k \in \mathbb{N}_{2}:\; f(k)=k

g:\mathbb{N}\to \mathbb{N}_{2}:\quad \forall n \in \mathbb{N}:\; g(n)=4n

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

h:\mathbb{N}\to \mathbb{N}_{2} \qquad \forall n \in \mathbb{N}:\; h(n)=2n

משפט

אם $A$ היא $\infty$ אז $|\mathbb{N}|\leq|A|$ (כלומר, $\mathbb{N}$ היא ה- $\infty$ -ית הכי קטנה)

הגדרה 39 (

\aleph_{0}

)

נסמן את עוצמת $\mathbb{N}$ כך:

|\mathbb{N}|=\aleph_{0}

קבוצות קטנות

הגדרה 40 (קבוצה בת מנייה)

$A$ נקראת בת מנייה אם $|A|\leq |\mathbb{N}|$ .
כלומר, $A$ סופית או ש- $|A|=\aleph_{0}$ .

דוגמה

הקבוצה $\mathbb{Z}$ הינה בת מנייה. נבנה $f:\mathbb{Z}\to \mathbb{N}$ חח"ע:

f(n)=\begin{cases} 2n-1 & n>0 \\ -2n & n\leq 0 \end{cases}

דוגמה

הקבוצה $\mathbb{Q}$ היא בת מנייה.

$\mathbb{Q}^+$ : נתחיל ממנה

נסתכל המטריצה האינסופית הבאה:

\begin{matrix} \frac{1}{1}& \frac{2}{1}& \frac{3}{1}& \frac{4}{1}& \frac{5}{1}& \dots \\ \frac{1}{2}& \frac{2}{2}& \frac{3}{2}& \frac{4}{2}& \frac{5}{2}& \dots \\ \frac{1}{3}& \frac{2}{3}& \frac{3}{3}& \frac{4}{3}& \frac{5}{3}& \dots \\ \vdots \end{matrix}

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

כל אלכסון סופי
האיבר $\frac{m}{n}$ נמצא באלכסון ה- $(n+m+1)$ -י. ⇐ נגיע אליו בסריקה.
הערך שכל איבר מקבל הוא האינדקס הראשון שבו נתקלים בו.

כדי להשלים את זה לכל $\mathbb{Q}$ נעשה בדיוק את אותו הדבר מהדוגמה הקודמת.

משפט

איחוד בן מניה של קבוצות בנות מניה הוא קבוצה בת מנייה.
כלומר אם $\mathcal{A}$ היא קבוצה בת-מניה של קבוצות בנות מניה אז:

\left| \bigcup_{A \in \mathcal{A}}A \right|\leq \aleph_{0}

הוכחה: מאוד דומה להוכחה של $\mathbb{Q}^+$ .;

הגדרה 41

$|A|<|B|$ אם $|A|\leq |B|$ וגם $|A|\neq |B|$ .

טענה

נסתכל על $(0,1)$ ונראה שהוא אינו בן מניה.

נראה כי $|\mathbb{N}|<|(0,1)|$ . על פי משפט(שראינו לפני כמה רגעים) ומכיוון ש- $(0,1)$ $\infty$ -ית: $|\mathbb{N}|\leq |(0,1)|$ .
כעת, נראה כי לא קיימת פונקציה $f:\mathbb{N}\to(0,1)$ על. ולכן, בפרט, לא קיימת פונקציה הפיכה.
(כדי להראות שלא בת מניה: $|(0,1)|\not\leq |\mathbb{N}|$ . כלומר, לא קיימת $g:(0,1)\to \mathbb{N}$ חח"ע, וממשפט: לא קיימת $f:\mathbb{N}\to(0,1)$ על, שזה מה שנראה כאמור)
תהי $f:\mathbb{N}\to(0,1)$ ונראה שאינה על.
יהא $x \in(0,1)$ - יש ל- $x$ יצוג: $0.\overbrace{a_{0}a_{1}a_{2}a_{3}\dots}^{\R{\text{ ספרות}}\infty}$
ראו הוכחה בסיכום אינפי - סדרות של למה לא ניתן לסדר את הרציונליים כסדרה - זה תחת כותרת משפט BW.
זוהי הוכחה בעזרת לכסון.

משפט קנטור

משפט (קנטור)

לכל $A$ : $|A|<|P(A)|$ .

מסקנה

משמעות המשפט היא שלכל קבוצה נוכל ליצור קבוצה בעלת עוצמה גדולה יותר.

|\mathbb{N}|<|P(\mathbb{N})|<|P(P(\mathbb{N}))|<\dots

זוהי סדרה $\infty$ -ית של עוצמות אינסופיות.

הוכחה:

שיעורי בית (HW)

הראו $|A|\leq |P(A)|$ .

כעת, נראה כי $|P(A)|< |A|$ . כלומר, לא קיימת $f:P(A)\to A$ חח"ע ולכן לפי משפט: לא קיימת $g:A\to P(A)$ על.
תהי $g:A\to P(A)$ . נגדיר: $S=\{ a|a \not\in g(a) \}\subseteq A$ .
נראה כי לכל $a$ : $g(a)\neq S$ , כלומר, $S$ לא מכוסה ע"י $g$ ולכן $g$ לא על.
נניח בשלילה כי קיים $a$ כך ש- $g(a)=S$ . האם $a \in S$ ?

אם $a \in S$ , אז $a \in g(a)$ , אבל לפי הגדרת $S$ : $a \not\in g(a)$ ו- $a \in g(a)$ . סתירה.
אחרת: $a \not\in S$ אז $a \not\in g(a)$ .
∎

מבוא לתורת הקבוצות ואוטומטים למדמח

תורת הקבוצות

מבוא לתורת הקבוצות ואוטומטים למדמח

תורת הקבוצות

קבוצות מפורסמות

הקבוצה הריקה

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

הכלה

תכונות של הכלה

איחוד

חיתוך

חוק הפילוג

חיסור

השלמה

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

כללי דה מורגן

הכללת איחוד וחיתוך

מכפלה קרטזית וזוגות סדורים

תכונות של מכפלה קרטזית

הרחבה של מכפלה קרטזית ל-kkk איברים סדורים

יחסים

מוטיבציה

פורמליות

פעולות על יחסים

1. הרכבת יחסים

תכונות של הרכבה

1. אי קיום קומוטטיביות

2. קיום אסוציאטיביות

2. חזקה של יחסים

התקיימות חוקי חזקות

3. היפוך של יחסים

תכונות

1. היפוך של היפוך

2. היפוך של הרכבה:

מסקנה/עוד משפט

יחסים מעל AAA

תכונות

1. רפלקסיביות

2. סימטריות

3. אנטי סימטריות

4. טרנזיטיביות

קשר בין פעולות לתכונות

מחלקות שקילות

פונקציות

תכונות של פונקציות

פונקציה הופכית

עוצמות של קבוצות

קבוצות סופיות

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

משפטים ותכונות

קבוצות קטנות

משפט קנטור

הרחבה של מכפלה קרטזית ל- $k$ איברים סדורים

יחסים מעל $A$