עקרון החיבור

עֶקְרוֹן הַחִיבּוּר הוא עיקרון יסודי בקומבינטוריקה המופיע בצורות שונות בתחומים רבים במתמטיקה. העיקרון קובע כי אם יש קבוצה אחת של $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 _{i=1}^{n}|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$ זרות.

נראה כי תמיד קיימות קבוצות זרות כאלו: בהינתן$\kappa ,\lambda$ עוצמות שיש לחבר, ובהינתן $A,B$ קבוצות בעלות העוצמות הללו בהתאמה, הקבוצות $A\times \{0\},B\times \{1\}$ זרות ועוצמותיהן הן בהתאמה $\kappa ,\lambda$.

נראה כי החיבור לא תלוי בקבוצות שנבחרו, כלומר אם $A\sim C,B\sim D$ (הסימן $\sim$ מייצג שעוצמותיהן שוות, כלומר קיימת פונקציה חח"ע ועל ביניהן) כך שA,B זרות וC,D זרות, אז $A\cup B\sim C\cup D$: יהו $f:A\to C,g:B\to D$ חד חד ערכיות ועל. הפונקציה $\psi :A\cup B\to C\cup D$ תוגדר $\psi (x)={\begin{cases}f(x)&&x\in A\\g(x)&&x\in B\end{cases}}$. פונקציה זו חח"ע ועל, לכן $|A\cup B|=|C\cup D|$.

בהכללה, הסכום של קבוצה כלשהי של עוצמות מוגדרת לפי: $\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$ יקרה היא הסכום של ההסתברויות המתאימות.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30861115עקרון החיבור