תורת הקבוצות

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

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

יחס

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

פונקציה

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

סודרים

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

פרדוקסים

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