מנקודת מבט לוגית, נתבונן בעצם כלשהו (אם זהו מספר, סימול מופשט כלשהו, או קבוצה אחרת), ונשאל את השאלה: "האם העצם הזה הוא איבר בקבוצה formula_1?". כלומר, על כל עצם x כלשהו נוכל להגיד אך ורק אחת משתי האפשרויות הבאות:
את השייכות מסמנים כך: formula_6, כלומר formula_2 איבר של הקבוצה formula_1. איבר אינו יכול להופיע פעמיים בקבוצה: או שהוא שייך לה, או שאינו שייך. אם formula_2 אינו איבר של formula_1, מסמנים formula_11.
נתבונן עתה בקבוצה A כלשהי, ועליה נשאל, "האם בקבוצה A יש איברים?"
את הקבוצה formula_1 שבה קיימים שלושת האיברים formula_15 נסמן:
יחסים בין קבוצות.
אומרים ש-formula_1 מוכלת ב-formula_18 או חלקית ל-formula_18 (ומסמנים formula_20) אם כל איבר של formula_1 הוא איבר של formula_18. יחס חשוב זה מגדיר את השוויון בין קבוצות: קבוצות הן שוות אם יש להן אותם איברים, כלומר formula_23 אם ורק אם formula_20 וגם formula_25. זו תכונה מהותית של קבוצות, הממחישה שאין להן מבנה או תכונות מעבר לרשימת האיברים שהן מכילות. שילוב היחסים מאפשר להגדיר חלקיות ממש: formula_1 חלקית ממש לקבוצה formula_18 אם ורק אם היא חלקית לה, אך אינה שווה לה; במקרה זה כותבים formula_28 או formula_29. בעוד שיחס ההכלה הוא יחס סדר חלש, חלקיות אמיתית היא יחס סדר חזק.
פעולות על קבוצות.
באוסף של קבוצות מתקיימות הפעולות הבאות:
יחסים ופונקציות.
יחס.
יחסים הם דבר נפוץ מאוד במתמטיקה, המהווים כלי חשוב לזיהוי קבוצות ואיברים. פורמלית, יחס מקבוצה formula_1 לקבוצה formula_18 הוא תת-קבוצה של המכפלה הקרטזית formula_101, ולכל formula_102 מסמנים formula_103. אומרים שהיחס הוא על קבוצה formula_1 אם זה יחס מהקבוצה אל עצמה. למשל, היחס formula_105 על הקבוצה formula_106 הוא היחס formula_107.
יחס על formula_1 נקרא רפלקסיבי אם formula_109, סימטרי אם formula_110, וטרנזיטיבי אם formula_111. יחס המקיים את שלוש התכונות הללו נקרא יחס שקילות - ליחסים כאלה תפקיד בסיסי וחשוב בכל תחומי המתמטיקה, והם מגדירים שקילויות בין איברים וקבוצות, ומאגדים איברים הנחשבים שקולים לאיבר אחד, המכונה מחלקת השקילות. מחלקות השקילות מהוות חלוקה של הקבוצה - הן זרות ואיחודן הוא כל הקבוצה. גם ההפך נכון - בהינתן חלוקה, ניתן להגדיר יחס שקילות שמחלקות השקילות שלו הן איברי החלוקה. כלומר, יש התאמה מלאה בין יחסי שקילות לחלוקות של קבוצה נתונה.
יחס על formula_1 יקרא יחס סדר אם הוא טרנזיטיבי ואנטי רפלקסיבי, היינו formula_113. היחס יקרא יחס סדר מלא אם כל שני איברים ניתנים להשוואה, ויחס סדר טוב אם הוא מלא ולכל תת-קבוצה לא ריקה יש איבר ראשון. יחסי הסדר הקלאסיים על המספרים כולם יחסי סדר מלאים. יחס ההכלה הוא יחס סדר לא מלא. לכל יחס סדר ניתן לבנות את דיאגרמת הסה שלו - בדיאגרמה זו יש קו בין איבר תחתון לעליון, אם התחתון מתייחס לעליון. במקרה שהיחס מלא, מתקבלת שרשרת ארוכה של התייחסויות. באופן כללי, שרשרת עולה ביחס היא מהצורה formula_114. הלמה של צורן קובעת כי בקבוצה סדורה חלקית, אם לכל שרשרת קיים חסם מלעיל, אז יש בקבוצה איבר מקסימלי.
פונקציה.
פונקציה היא התאמה בין קבוצות. זהו מונח כללי מאוד בו משתמשים באופן טוטאלי בכל תחומי המתמטיקה.
פורמלית, פונקציה מקבוצה formula_1 (המכונה מקור הפונקציה) לקבוצה formula_18 (המכונה טווח הפונקציה) היא יחס חד ערכי, כלומר תת-קבוצה formula_101 המקיים formula_118. כלומר, לכל איבר במקור מתאים איבר יחיד בטווח. פונקציה המקיימת את התנאי ההפוך נקראת פונקציה חד-חד-ערכית, פונקציה עבורה לכל איבר בטווח קיים מקור נקראת פונקציה על. פונקציה שהיא גם על וגם חד-חד ערכית נקראת שקילות קבוצות; פונקציה כזו היא גם הפיכה, וגם ההפך נכון.
למחקר פונקציות והתכונות שלהן מקום מכריע בכל המתמטיקה. ניתן להגדיר פונקציות משמרות תכונות, פונקציות רציפות, פונקציות גזירות וכו', ולחקור את המבנים הנוצרים. הדגש על מעברים בין אובייקטים, המכליל את הרעיון של הפונקציה, נתון במושג המורפיזם בתורת הקטגוריות.
קבוצה אינסופית ועוצמה.
מתי קבוצה היא סופית, ומתי היא אינסופית? נתאר קבוצה אשר מייצגת את כל המספרים הטבעיים, כלומר ...1,2,3 אשר כבר מוכרים לנו מחיי היום יום ונגדיר אותה::
הקבוצה formula_120 מוגדרת באופן שאינו מאפשר לספור את איבריה, כלומר, אם ננסה לספור אותם אז תמיד יהיו איברים נוספים בקבוצה שעלינו לספור. תכונה זו נלמדה על ידי רבים והוצעו מספר דרכים לתאר קבוצה מסוג זה באופן מתמטי.
קנטור השתמש בדרך אחרת להתמודד עם בעיית הספירה וההתייחסות אל גודלן של קבוצות אלו. הוא החליף את פעולת הספירה האינטואיטיבית בשימוש בכלים מתמטיים כגון פונקציות, דבר שאיפשר להרחיב את היחסים המוכרים בין הקבוצות הסופיות גם לאינסופיות. אם קיים מיפוי דו-כיווני בין שתי קבוצות סופיות, שהוא פונקציה חד-חד ערכית מ-formula_1 על formula_18, הרי שלשתי הקבוצות יש אותו גודל.
למשל לקבוצות הסופיות formula_77 המוגדרות:
נבנה פונקציה חד-חד ערכית מ-formula_1 על formula_18: (בשימוש בזוגות סדורים)
מקיום המיפוי נסיק שקבוצות אלו הן באותו גודל. מצאנו דרך מתמטית לטפל בהשוואת גודלן של קבוצות סופיות בלי לספור את איבריהן. במינוח המתמטי, אם קיים יחס שקילות בין שתי קבוצות. אז הקבוצות הן שוות עצמה.
נבדוק עכשיו שקילות של קבוצות אינסופיות כלשהן, למשל, קבוצות המספרים הטבעיים, וקבוצת הטבעיים הזוגיים המוגדרות:
נגדיר פונקציה:
פונקציה זו, המוגדרת בין שתי הקבוצות, היא חד-חד ערכית ועל. מסקנה: קבוצת המספרים הטבעיים שקולה לקבוצת המספרים הטבעיים הזוגיים.
נגדיר באופן מדויק מהי קבוצה אינסופית:
או לחלופין:
תכונה זו ודאי לא מתקיימת בקבוצות סופיות, אך היא מתקיימות בקבוצות שעוצמתן אינסופית.
ישנן קבוצות אינסופיות רבות שונות בגודלן זו מזו. מושג העוצמה משמש כיום כלי מרכזי בהתייחסות מתמטית לגודלן של קבוצות אינסופיות (וסופיות). העוצמה של קבוצה היא מונח חשוב שעולה במקומות רבים במתמטיקה. מסמנים את העוצמה של קבוצה ב-formula_135; אומרים ש-formula_136 אם יש פונקציה חד-חד-ערכית formula_137, ו-formula_138 אם יש פונקציה על formula_137.קבוצות נקראות שקולות עוצמה אם יש ביניהן פונקציה הפיכה, ומסמנים formula_140. משפט קנטור-שרדר-ברנשטיין קובע כי אם מכך ש-formula_136, formula_138 ניתן להסיק כי formula_140.
תוצאות נוספות (ולעיתים מפתיעות) ביחסים בין קבוצות אינסופיות: קנטור הוכיח קיום שקילות בין קבוצת המספרים הטבעיים למספרים הרציונליים. כמו כן, אי שקילות בין כל קבוצה לקבוצת החזקה שלה (משפט קנטור) ואי שקילות בין קבוצת המספרים הטבעיים לממשיים (האלכסון של קנטור).
קבוצה השקולה לתת קבוצה כלשהי של הטבעיים נקראת קבוצה בת מנייה. חיתוך, מכפלה קרטזית סופית ואיחוד בן מנייה של קבוצות בנות מנייה נשאר בן מנייה.
סודרים.
לסודרים שימושים רבים בתחומים שונים ולא צפויים במתמטיקה, והם מהווים מונח יסוד בתורת הקבוצות.
סודר הוא קבוצה הסדורה היטב לפי היחס formula_144 שהיא גם formula_144-טרנזטיבית (כלומר, אם formula_146 אז formula_40. לסודרים מבנה מיוחד - כל סודר הוא יחיד עד כדי שוויון, ומתקיימת בין כל הסודרים טריכוטומיות - כלומר ניתן להשוות באופן יחיד בין כל שני סודרים. במילים אחרות, הסודרים מסודרים אחד אחרי השני במעין שרשרת מאוד ארוכה - בעזרתם ניתן לספור דברים. יתרה מזאת, כל קבוצה סדורה היטב איזומורפית סדר לסודר יחיד, המהווה מעין נציג קנוני במחלקה שלה.
ניתן גם להגדיר פעולות בין סודרים, כמו חיבור, הפרש, כפל וחזקה. פעולות אלו שומרות חלקית על התכונות של הפעולות הרגילות על מספרים (למשל, החיבור איננו חילופי). ניתן להגדיר פונקציות מונוטוניות ורציפות בין סודרים, ביחס לטופולוגיית סדר.
סודרים מאפשרים להגדיר בתורת הקבוצות את האינדוקציה הטרנספיניטית ולהוכיח את משפט הרקורסיה הטרנספיניטית המהווים הכללה של המונחים אינדוקציה ורקורסיה על הטבעיים, ולהם שימושים רבים.
פרדוקסים.
הגדרת מושג הקבוצה באופן שמאפשר, הלכה למעשה, לכל עצם להיכלל בה, מובילה למספר פרדוקסים, בהם הפרדוקס של ראסל. בעקבות הסתירה אליה הוביל הפרדוקס של ראסל, ובעיות נוספות, בהן הגדרת "קבוצת כל הקבוצות" והשלכותיה ביחס לקבוצת החזקה שלה (ראו פרדוקס קנטור) והפרדוקס של בורלי-פורטי, והצורך לבסס את רעיון הקבוצה באופן אקסיומטי, פותחה תורת הקבוצות האקסיומטית, שהיא למעשה התורה אליה לרוב מתכוונים היום מתמטיקאים כאשר הם מדברים על "תורת הקבוצות". האקסיומטיזציה של ארנסט צרמלו ואברהם הלוי פרנקל (אקסיומות צרמלו-פרנקל) מטילה מספר מגבלות על הגדרות של קבוצות כדי להימנע מהסתירות בתורה הנאיבית שהודגמו לעיל, והיא כיום הדרך המקובלת להתייחס לקבוצות באופן פורמלי.
פונקציה על
במתמטיקה, פונקציה מקבוצה formula_1 לקבוצה formula_2 היא על אם כל איבר בקבוצה formula_2 מתקבל כערך של הפונקציה. לדוגמה, הפונקציה המתאימה לכל עלה את העץ שעליו הוא צומח היא "על", אם על כל עץ צומח עלה אחד לפחות.
באופן פורמלי: פונקציה formula_4 היא על formula_5, אם לכל איבר בטווח (formula_5) של הפונקציה מתאים לפחות איבר אחד בתחום (formula_7) שלה (ובמילים אחרות: התמונה של formula_8 שווה לטווח שלה). בסימון מתמטי: לכל formula_9 קיים formula_10 כך ש-formula_11. במקרה זה לעיתים מסמנים: formula_12 כדי לציין ש-formula_8 היא על.