תורת הקבוצות

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

תורת הקבוצות נוסחה לראשונה בידי גאורג קנטור בשנות ה-1870. קנטור פרסם מסקנות חשובות ב-1895 וב-1897 ועסק במיוחד באינסופים ובמשפטים על שקילות בין קבוצות.

קבוצה מוגדרת כאוסף של איברים. איבר הוא כל עצם ששייך לקבוצה. שייכות מסומנת ב-x∈A (x שייך ל־A). בקבוצה אין חזרות: {x,x,x} זהה ל־{x}. גם הסדר לא חשוב: {1,2,3} = {2,3,1}. אפשר לתאר קבוצה על ידי רשימה או על ידי תנאי שמזהה אילו איברים שייכים לה.

A מוכלת ב־B (A⊆B) אם כל איבר של A גם שייך ל־B. שתי קבוצות שוות בדיוק כאשר כל אחת מוכלת בשנייה. A חלקית ממש ב־B אם A⊆B אך A≠B.

איחוד (A∪B) מכיל איברים ששייכים ל־A או ל־B. חיתוך (A∩B) מכיל איברים ששייכים לשתיהן. ההפרש A\B מכיל איברים שב־A אך לא ב־B. המשלים של קבוצה תלוי בקבוצה האוניברסלית בהקשר. גם קיים הפרש סימטרי, שאינו אלא איברים שנמצאים בדיוק באחת מהקבוצות.

יחס בינארי הוא קבוצה של זוגות סדורים. יחס בין A ל־B הוא תת־קבוצה של A×B. יחס על A יכול להיות רפלקסיבי (aRa לכל a), סימטרי (aRb ⇒ bRa) וטרנזיטיבי (aRb ו־bRc ⇒ aRc). יחס שמקיים את שלוש התכונות נקרא יחס שקילות. יחס שקילות מפריד את הקבוצה למחלקות שקילות, שהן תתי־קבוצות זרות שאיחודן נותן את כל הקבוצה.

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

פונקציה היא יחס חד־ערכי ומלא בין קבוצה A (תחום) לקבוצה B (טווח). חד־ערכיות פירושה שלכל a מתאים איבר אחד יחיד ב־B. מלאות פירושה שכל איבר ב־A מקושר. פונקציה היא חד־חד־ערכית (אינג'קטיבית) אם אין שני איברים שונים שמתאימים לאותו ערך. פונקציה על (סורjektיבית) מכסה את כל הטווח. פונקציה שהיא גם על וגם חד־חד־ערכית נקראת הפיכה (ביזקטיבית). פונקציות הן כלי מרכזי בכל ענפי המתמטיקה.

הקבוצה של המספרים הטבעיים נכתבת ℕ = {1,2,3,...}. אינסוף פירושו שלא ניתן לספור את כל האיברים עד הסוף. קנטור הציע להשוות גדלים של קבוצות בעזרת פונקציות. אם קיימת פונקציה חד־חד־ערכית ועל בין שתי קבוצות, הן שוות גודל.

דוגמה: פונקציה f(n)=2n ממפה את ℕ אל קבוצת הטבעיים הזוגיים. זו פונקציה חד־חד־ערכית ועל, לכן שתי הקבוצות שקולות.

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

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

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

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

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

את השייכות כותבים x ∈ A וזה אומר x שייך ל־A. בקבוצה לא עושים חזרות. גם הסדר לא משנה: {1,2,3} זהה ל־{2,3,1}.

A מוכלת ב־B אם כל איבר של A נמצא גם ב־B. אם A מוכלת ב־B אך לא זהה לה, קוראים לזה חלקית ממש.

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

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

הטבעיים הם 1,2,3,... וממשיכים בלי סוף. אינסופי אומר שאי־אפשר לספור עד הסוף. אפשר להראות למשל שכל הטבעיים מתחברים לזוגיים בעזרת f(n)=2n. יש אינסופים גדולים יותר. קנטור הוכיח שהממשיים גדולים יותר מהטבעיים.

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

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