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

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

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

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


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

משפט קנטור מתקבל כמקרה פרטי של משפט קניג:
אם לכל בוחרים ו-, אז ממשפט קניג נקבל:

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

כאשר הוא הקופינאליות של המונה האינסופי , ו- היא פונקציית גימל.

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

.

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

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

הוכחה

תהי פונקציה, ונניח כי , לכל i. נראה כי הפונקציה הזו איננה על.

לכל , נגדיר את הפונקציה fi על ידי צימצום הפונקציה f לקבוצה Bi בקלט וצמצום הפלט רק לקואורדינטה ה-i שלו. אם נחשוב על איברי המכפלה כפונקציות עם קלט ב- , אז עבור . הפונקציה הזו, , לא תהיה על בגלל שמתקיים . לכן, ניתן לבחור שאינו בתמונה של fi.

נטען כי האיבר לא נמצא בתמונת f, ובכך נסיים את ההוכחה. אחרת, היה לו מקור, . אבל אז, הקואורדינטה ה-i של c, הייתה נמצאת בתמונה של fi, וזו סתירה לצורה בה בחרנו את c.

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

ראו גם

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

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