תורת הקבוצות

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

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

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

הגדרת הקבוצה ויחסים בין קבוצות

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

• "העצם $x$ אבר בקבוצה $A$"
• "העצם $x$ אינו אבר בקבוצה $A$"

את השייכות מסמנים כך: $x\in A$ , כלומר $x$ אבר של הקבוצה $A$ . אבר אינו יכול "להופיע פעמיים" בקבוצה: או שהוא שייך לה, או שאינו שייך. אם $x$ אינו אבר של $A$ , מסמנים $x\notin A$ .

נתבונן עתה בקבוצה $A$ כלשהי, ועליה נשאל, "האם בקבוצה $A$ יש אברים?"

• אם אין בה אברים, זוהי הקבוצה הריקה ונסמן אותה: $A=\varnothing$ .
• אם יש בה אברים, אז היא אינה קבוצה ריקה לכן $A\neq \varnothing$ .

את הקבוצה $A$ שבה קיימים שלושת האברים $a,b,c$ נסמן:

$A=\{a,b,c\}$

יחסים בין קבוצות

אומרים כי $A$ מוכלת ב־$B$ או חלקית ל־$B$ (ומסמנים $A\subseteq B$) אם כל אבר של $A$ הוא אבר של $B$ . יחס חשוב זה מגדיר את השוויון בין קבוצות: קבוצות הן שוות אם יש להן אותם אברים, כלומר $A=B$ אם ורק אם $A\subseteq B$ וגם $B\subseteq A$ . זו תכונה מהותית של קבוצות, הממחישה שאין להן מבנה או תכונות מעבר לרשימת האברים שהן מכילות. שילוב היחסים מאפשר להגדיר חלקיות ממש: $A$ חלקית ממש לקבוצה $B$ אם ורק אם היא חלקית לה, אך אינה שווה לה; במקרה זה כותבים $A\subset B$ או $A\subsetneq B$ . בעוד שיחס ההכלה הוא יחס סדר חלש, חלקיות אמיתית היא יחס סדר חזק.

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

דיאגרמת ון של החיתוך של $A,B$

באוסף של קבוצות מתקיימות הפעולות הבאות:

• איחוד: האיחוד של שתי קבוצות $A,B$ הוא קבוצה המכילה את כל האברים של $A$ ואת כל האברים של $B$ , ורק אותם.

בכתיב פורמלי:

$x\in A\cup B$ ($x$ הוא אבר ב־$A\cup B$) אם ורק אם $x\in A$ או $x\in B$ .

• חיתוך: החיתוך של שתי קבוצות $A,B$ הוא הקבוצה המכילה את כל האברים ב־$A$ השייכים גם ל־$B$ (או באופן שקול, כל האברים ב־$B$ השייכים גם ל־$A$), ורק אותם.

בכתיב פורמלי:

$x\in A\cap B$ ($x$ הוא אבר ב־$A\cap B$) אם ורק אם $x\in A$ וגם $x\in B$ .

דוגמאות:

• החיתוך של קבוצת אזרחי ישראל עם קבוצת אזרחי צרפת הוא קבוצת האנשים שלהם אזרחות כפולה, ישראלית־צרפתית.
• החיתוך של קבוצת הגברים הישראלים וקבוצת הנשים הישראליות הוא הקבוצה הריקה – אלה שתי קבוצות זרות.

• משלים: משלים של קבוצה $G$ הוא קבוצה אחרת, המכילה את כל האברים שאינם נמצאים ב־$G$ . זאת ביחס לקבוצה $U$ כלשהי שהיא "הקבוצה האוניברסלית" – קבוצה שבהקשר הנוכחי של הדיון, כל קבוצה שעליה נדבר היא תת-קבוצה של $U$ .

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

• הפרש: ההפרש בין קבוצה $A$ לקבוצה $B$ הוא הקבוצה המכילה את כל האברים השייכים ל־$A$ אך לא ל־$B$ .

בכתיב פורמלי:

$x\in A-B$ ($x$ הוא אבר ב־$A-B$) אם ורק אם $x\in A$ וגם $x\notin B$ .

או $A-B=A\cap B^{c}$

• מכפלה קרטזית: המכפלה הקרטזית של שתי קבוצות $A,B$ מסומנת $A\times B$ , והיא הקבוצה המכילה את אוסף הזוגות $(a,b)$ עבורם $a\in A,b\in B$ .

באופן כללי, אם $\{A_{i}\}_{i\in I}$ קבוצות, אז $\times _{i\in I}{A_{i}}$ היא המכפלה הקרטזית שלהן, ובנויה פורמלית מפונקציות $f:I\to \bigcup A_{i}$ עבורן $f(i)\in A_{i}$ .

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

• הפרש סימטרי: הפרש סימטרי של שתי קבוצות $A,B$ הוא הקבוצה $C$ המורכבת מכל אברי $A$ שלא שייכים ל־$B$ וכל אברי $B$ שלא שייכים ל־$A$ – כלומר, כל האברים השייכים בדיוק לאחת הקבוצות.

בכתיב פורמלי:

$A\Delta B=(A-B)\cup (B-A)=(A\cup B)-(A\cap B)$

• קבוצת החזקה: קבוצת החזקה של קבוצה נתונה $A$ היא קבוצת כל תת־הקבוצות של $A$ , היינו $P(A)=\{B:B\subseteq A\}$ . עוצמת קבוצת החזקה היא $2^{|A|}$ , ומשפט קנטור קובע כי עוצמת קבוצת החזקה גדולה ממש מעוצמת הקבוצה.

יחסים ופונקציות

יחס

יחסים הם דבר נפוץ מאד במתמטיקה, המהווים כלי חשוב לזיהוי קבוצות ואברים. פורמלית, יחס מקבוצה $A$ לקבוצה $B$ הוא תת־קבוצה של המכפלה הקרטזית $R\subseteq A\times B$ , ולכל $(a,b)\in R$ מסמנים $aRb$ . אומרים שהיחס הוא על קבוצה $A$ אם זה יחס מהקבוצה אל עצמה. למשל, היחס $<$ על הקבוצה $\{1,2,3\}$ הוא היחס $<={\bigl \{}(1,2),(2,3){\bigr \}}$ .

יחס על $A$ נקרא רפלקסיבי אם $\forall a\in A:(a,a)\in R$ , סימטרי אם $(a,a')\in R\Rightarrow (a',a)\in R$ , וטרנזיטיבי אם $aRb,bRc\Rightarrow aRc$ . יחס המקיים את שלוש התכונות הללו נקרא יחס שקילות – ליחסים כאלה תפקיד בסיסי וחשוב בכל תחומי המתמטיקה, והם מגדירים שקילויות בין אברים וקבוצות, ומאגדים אברים הנחשבים שקולים לאבר אחד, המכונה מחלקת השקילות. מחלקות השקילות מהוות חלוקה של הקבוצה – הן זרות ואיחודן הוא כל הקבוצה. גם ההפך נכון – בהינתן חלוקה, ניתן להגדיר יחס שקילות שמחלקות השקילות שלו הן אברי החלוקה. כלומר, יש התאמה מלאה בין יחסי שקילות לחלוקות של קבוצה נתונה.

יחס על $A$ יקרא יחס סדר אם הוא טרנזיטיבי ואנטי רפלקסיבי, היינו $\forall a\in A:(a,a)\notin R$ . היחס יקרא יחס סדר מלא אם כל שני אברים ניתנים להשוואה, ויחס סדר טוב אם הוא מלא ולכל תת־קבוצה לא־ריקה יש אבר ראשון. יחסי הסדר הקלאסיים על המספרים כולם יחסי סדר מלאים. יחס ההכלה הוא יחס סדר לא מלא. לכל יחס סדר ניתן לבנות את דיאגרמת הסה שלו – בדיאגרמה זו יש קו בין אבר תחתון לעליון, אם התחתון מתייחס לעליון. במקרה שהיחס מלא, מתקבלת שרשרת ארוכה של התייחסויות. באופן כללי, שרשרת עולה ביחס היא מהצורה $a_{1}<a_{2}<a_{3}<\ldots$ . הלמה של צורן קובעת כי בקבוצה סדורה חלקית, אם לכל שרשרת קיים חסם מלעיל, אז יש בקבוצה אבר מקסימלי.

פונקציה

פונקציה היא התאמה בין קבוצות. זהו מונח כללי מאד בו משתמשים באופן טוטאלי בכל תחומי המתמטיקה.

פורמלית, פונקציה מקבוצה $A$ (המכונה מקור הפונקציה) לקבוצה $B$ (המכונה טווח הפונקציה) היא יחס חד־ערכי, כלומר תת־קבוצה $R\subseteq A\times B$ המקיים $aRb,aRb'\Rightarrow b=b'$ . כלומר, לכל אבר במקור מתאים אבר יחיד בטווח. פונקציה המקיימת את התנאי ההפוך נקראת פונקציה חד-חד-ערכית, פונקציה עבורה לכל אבר בטווח קיים מקור נקראת פונקציה על. פונקציה שהיא גם על וגם חד־חד־ערכית נקראת שקילות קבוצות; פונקציה כזו היא גם הפיכה, וגם ההפך נכון.

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

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

מתי קבוצה היא "סופית", ומתי היא "אינסופית"? נתאר קבוצה אשר מייצגת את כל המספרים הטבעיים, כלומר ...1,2,3 אשר כבר מוכרים לנו מחיי היום יום ונגדיר אותה חלקית:

$\mathbb {N} =\{1,2,3,\ldots \}$

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

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

למשל לקבוצות הסופיות $A,B$ המוגדרות:

${\begin{aligned}A&=\{1,2,3,4\}\\B&=\{c,d,e,f\}\end{aligned}}$

נבנה פונקציה חד־חד־ערכית מ־$A$ על $B$ : (בשימוש בזוגות סדורים)

$f={\bigl (}A,B,{\bigl \{}(1,c),(2,d),(3,e),(4,f){\bigr \}}{\bigr )}$

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

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

${\begin{aligned}\mathbb {N} &=\{1,2,3,\ldots \}\\\mathbb {N} _{2}&=\{2,4,6,\ldots \}\end{aligned}}$

נגדיר פונקציה

$f:\mathbb {N} \to \mathbb {N} _{2},\quad f(x)=2x$

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

נגדיר באופן מדויק מהי קבוצה אינסופית:

קבוצה אינסופית היא קבוצה שקיימת קבוצה החלקית לה ממש ושקולה לה.

או לחלופין:

קבוצה היא אינסופית אם ורק אם קיימת פונקציה חד-חד-ערכית מ־$A$ ל־$A$ שאינה על $A$.

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

ישנן קבוצות אינסופיות רבות שונות בגודלן זו מזו. מושג העוצמה משמש כיום כלי מרכזי בהתייחסות מתמטית ל"גודלן" של קבוצות אינסופיות (וסופיות). העוצמה של קבוצה היא מונח חשוב שעולה במקומות רבים במתמטיקה. מסמנים את העוצמה של קבוצה ב-$|A|$ ; אומרים כי $|A|\leq |B|$ אם יש פונקציה חד־חד־ערכית $f:A\to B$ , ו־$|B|\leq |A|$ אם יש פונקציה על $f:A\to B$ . קבוצות נקראות שקולות עוצמה אם יש ביניהן פונקציה הפיכה, ומסמנים $|A|=|B|$ . משפט קנטור-שרדר-ברנשטיין קובע כי אם $|A|\leq |B|,|B|\leq |A|$ אזי ניתן להסיק כי $|A|=|B|$ .

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

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

סודרים

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

סודר הוא קבוצה הסדורה היטב לפי היחס $\in$ שהיא גם $\in$־טרנזיטיבית (כלומר, אם $x\in y\in A$ אז $x\in A$ . לסודרים מבנה מיוחד – כל סודר הוא יחיד עד כדי שוויון, ומתקיימת בין כל הסודרים טריכוטומיות – כלומר ניתן להשוות באופן יחיד בין כל שני סודרים. במילים אחרות, הסודרים מסודרים אחד אחרי השני במעין שרשרת מאד ארוכה - בעזרתם ניתן לספור דברים. יתרה מזאת, כל קבוצה סדורה היטב איזומורפית סדר לסודר יחיד, המהווה מעין נציג קנוני במחלקה שלה.

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

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

פרדוקסים

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

לקריאה נוספת

• אברהם הלוי פרנקל, מבוא למתמטיקה, כרך שני: האינסוף והמרחב, חטיבה ראשונה: תורת הקבוצות, הוצאת מסדה, 1953

קישורים חיצוניים

• שמואל ברגר, ‏תורת הקבוצות, האוניברסיטה הפתוחה, 1992 (הספר במיזם פא"ר)
• תורת הקבוצות – הרצאות מוקלטות של פרופ' רון אהרוני

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0