עקרון החיבור

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

קומבינטוריקה[עריכת קוד מקור | עריכה]

בניסוח פורמלי עקרון החיבור קובע כי אם בקבוצה סופית \ A יש \ n איברים ובקבוצה סופית \ B יש \ m איברים, והקבוצות A ו-B זרות, אז באיחוד \ A\cup B יש \ n+m איברים. או בסימון מקובל: \ |A \cup B| = |A| + |B|. ניתן להוכיח את עקרון החיבור באינדוקציה בהסתמך על הגדרת החיבור במערכת פאנו.

באינדוקציה מכלילים את עקרון החיבור למספר כלשהו של קבוצות. אם הקבוצות \ A_1, A_2, \ldots , A_n סופיות וזרות בזוגות, אז \ \biggl|\bigcup_{i=1}^n A_i\biggl| = \sum^n_{i=1} |A_i|.

הכללה נוספת של עקרון החיבור היא למקרה שהקבוצות אינן בהכרח זרות. במקרה כזה על סמך החלוקה של \ A \cup B לקבוצות הזרות A-B, B-A, A\cap B (ראו הפרש וחיתוך) ועל סמך עקרון החיבור, מתקבל: \ |A \cup B| = |A|+|B|-|A \cap B|.

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

תורת הקבוצות[עריכת קוד מקור | עריכה]

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

בהכללה, הסכום של קבוצה כלשהי של עוצמות מוגדרת לפי: \sum_{i \in I} |A_i| := \biggl|\bigcup_{i \in I} A_i \biggr| , כשהקבוצות הנציגות זרות בזוגות.

תורת המידה[עריכת קוד מקור | עריכה]

אם לוקחים קטע באורך n ומחברים אותו לקטע באורך m מתקבל קטע באורך n+m. זוהי תכונה בסיסית של פונקציית האורך הנקראת אדיטיביות, ומצופה שכל סוג של מידה נאותה תקיים אותה (ואף שתקיים סיגמא-אדיטיביות). באופן כללי, פונקציה \mu מקבוצה של קבוצות לקבוצה עם חיבור היא אדיטיבית אם \mu(A \cup B) = \mu(A)+\mu(B), לכל A ו-B זרות. בפרט, עקרון החיבור להסתברויות קובע שלכל שני מאורעות זרים A ו-B, ההסתברות ש-A יקרה או B יקרה היא הסכום של הסתברות ש-A יקרה עם ההסתברות ש-B יקרה.