למת הסנדוויץ'

למת הסנדוויץ' עוסקת בקביעת עוצמה של קבוצה שכל שידוע אודותיה הוא שהיא בין שתי עוצמות שוות.

נוסח פורמלי: יהיו A,B,C קבוצות בעלות עוצמות המקיימות $|A|\leq |B|\leq |C|$. אם $|A|=|C|$ אזי גם עוצמת B שווה להן.

הוכחה

עקרונית טענה זו נובעת ישירות ממשפט קנטור-שרדר-ברנשטיין, שכן אם $|A|=|C|$ אז מתקיים גם $|B|\leq |A|$ וגם $|A|\leq |B|$, ולכן בהכרח $|B|=|A|$. אולם יש הוכחה של משפט זה שעושה שימוש בלמת הסנדוויץ' ועל-כן נוכיח אותה באופן עצמאי.

הוכחה

נתון כי $|A|=|C|$ ולכן קיימת פונקציה f חד-חד ערכית ועל מ-A על C. כמו-כן נתון כי $|B|\leq |C|$ ולכן ניתן לשכן את B בתוך C. אם-כך נתייחס ל-B כאל תת-קבוצה של C.

נגדיר $P_{0}=A\setminus B$, ובאופן רקורסיבי נגדיר $P_{n+1}=f[P_{n}]$, כאשר הביטוי $f[P_{n}]$ מסמן את תמונת הפונקציה f מצומצמת לתחום $P_{n}$. נגדיר עוד $P=\bigcup _{n}P_{n}$ על כל ה-n הטבעיים.

כעת נגדיר פונקציה g מ-A ל-B, ונראה כי היא חד-חד ערכית ועל: $g(x)=\left\{{\begin{matrix}x&{\mbox{if }}x\in A\setminus P\\f(x)&{\mbox{if }}x\in P\end{matrix}}\right.$

נראה כי g חד-חד ערכית. נניח כי x,y זוג איברים שונים השייכים ל-A. יש שלוש אפשרויות:

• אם $x,y\in P$ אז $g(x)=f(x),g(y)=f(y)$, ומכך ש-f חד-חד ערכית נובע כי $g(x)=f(x)\neq g(y)=f(y)$.
• אם $x,y\in A\setminus P$ אז $g(x)=x,g(y)=y$ ולכן בבירור מתקיימת חד-חד ערכיות.
• אם $x\in P$ ו-$y\in A\setminus P$ (ללא הגבלת הכלליות) אז $g(x)=f(x),g(y)=y$. נשים לב שמתקיים כי $f(x)\in P$ ומההנחה נובע $y\notin P$ ומכאן החד-חד ערכיות.

נראה כי g על B. יהי y איבר ב-B, נדון בשני מקרים:

• אם $y\in P$ אז בבירור $y\notin P_{0}=A\setminus P$ ולכן קיים n טבעי כלשהו שעבורו $y\in P_{n}$ ולפי ההגדרה $P_{n}=f[P_{n-1}]$. כלומר y בתמונת g עבור x כלשהו.
• אם $y\in A\setminus P$ אז מהגדרת g נובע כי $g(y)=y$.

מכאן ש-g פונקציה חד-חד ערכית ועל מ-A על B, כלומר $|B|=|A|$.