עקרון החיבור

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

עקרון החיבור הוא עקרון יסודי בקומבינטוריקה המופיע בצורות שונות בתחומים רבים במתמטיקה. העקרון קובע כי אם יש קבוצה אחת של \ 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 יקרה היא הסכום של ההסתברויות המתאימות.