משפט קניג (תורת הקבוצות)

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

נוסח המשפט: לכל קבוצה $I$, אם לכל $i\in I$ נתונות זוג עוצמות $\kappa _{i}$ ו-$\mu _{i}$, כך שמתקיים $\kappa _{i}<\mu _{i}$, אז:

$\sum _{i\in I}\kappa _{i}<\prod _{i\in I}\mu _{i}$

אגף שמאל של המשפט סכום העוצמות $\kappa _{i}$, ואילו אגף ימין הוא מכפלת העוצמות $\mu _{i}$. אי-השוויון הוא טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים. אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (שאינו נכון כלל במקרה הסופי).

משפט קנטור מתקבל כמקרה פרטי של משפט קניג:
אם לכל $i\in I$ בוחרים $\kappa _{i}=1$ ו-$\mu _{i}=2$, אז ממשפט קניג נקבל:

$|I|=\sum _{i\in I}1<\prod _{i\in I}2=2^{|I|}$

למעשה, ממשפט קניג נובעת תוצאה חזקה יותר:

$\lambda <\lambda ^{{\mbox{cf}}(\lambda )}=\gimel (\lambda )$ כאשר ${\mbox{cf}}(\lambda )$ הוא הקופינאליות של המונה האינסופי $\lambda$, ו-$\gimel$ היא פונקציית גימל.

ניתן להוכיח זאת על ידי הבחירה הבאה (בסימונים של תחילת הערך):

$\forall i\,\kappa _{i}<\lambda \,,\sum _{i<{\mbox{cf}}(\lambda )}\kappa _{i}=\lambda \,\,,\forall i\,\mu _{i}=\lambda$.

מהעובדה הזאת נובע השיפור הבא של משפט קנטור:

${\mbox{cf}}(2^{\kappa })>\kappa$

ניתן להוכיח אותו על ידי הצבה $\lambda =2^{\kappa }$, ואז אם נניח בשלילה: ${\mbox{cf}}(2^{\kappa })\leq \kappa$ נקבל כי $\lambda ^{{\mbox{cf}}(\lambda )}\leq (2^{\kappa })^{\kappa }=2^{\kappa }=\lambda$, בסתירה לטענה הקודמת.

הוכחה

תהי $\textstyle f:\sum _{i\in I}B_{i}\rightarrow \prod _{i\in I}C_{i}$ פונקציה, ונניח כי $|B_{i}|<|C_{i}|$, לכל i. נראה כי הפונקציה הזו איננה על.

לכל $i\in I$, נגדיר את הפונקציה f_i על ידי צימצום הפונקציה f לקבוצה B_i בקלט וצמצום הפלט רק לקואורדינטה ה-i שלו. אם נחשוב על איברי המכפלה כפונקציות עם קלט ב- $I$, אז $f_{i}(x)=f(x)(i)$ עבור $x\in B_{i}$. הפונקציה הזו, $f_{i}:B_{i}\rightarrow C_{i}$, לא תהיה על בגלל שמתקיים $|B_{i}|<|C_{i}|$. לכן, ניתן לבחור $c_{i}\in C_{i}$ שאינו בתמונה של f_i.

נטען כי האיבר $c=\langle c_{i}|i\in I\rangle \in \prod C_{i}$ לא נמצא בתמונת f, ובכך נסיים את ההוכחה. אחרת, היה לו מקור, $b\in B_{i},\,i\in I$. אבל אז, הקואורדינטה ה-i של c, הייתה נמצאת בתמונה של f_i, וזו סתירה לצורה בה בחרנו את c.

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

ראו גם

• מונחים בתורת הקבוצות

קישורים חיצוניים

• משפט קניג באתר PlanetMath

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

34015287משפט קניג (תורת הקבוצות)