הבדלים בין גרסאות בדף "למת הסנדוויץ'"

הוסרו 3,326 בתים ,  לפני 7 שנים
מ
איחוד
(←‏פתיח: איחוד)
מ (איחוד)
 
{{לאחד|למת#הפניה הסנדוויץ'|[[משפט קנטור-שרדר-ברנשטיין}}]]
{{פירוש נוסף|נוכחי=למת הסנדוויץ' ב[[תורת הקבוצות]]|אחר=כלל הסנדוויץ' ב[[חשבון אינפיניטסימלי]]|ראו=[[כלל הסנדוויץ']]}}
{{לאחד|למת הסנדוויץ'|משפט קנטור-שרדר-ברנשטיין}}
'''למת הסנדוויץ'''' עוסקת בקביעת [[עוצמה (מתמטיקה)|עוצמה]] של [[קבוצה (מתמטיקה)|קבוצה]] שכל שידוע אודותיה הוא שהיא בין שתי עוצמות שוות.
 
'''נוסח פורמלי''': יהיו A,B,C קבוצות בעלות עוצמות המקיימות <math>|A| \leq |B| \leq |C| </math>. אם <math>|A| = |C| </math> אזי גם
עוצמת B שווה להן.
 
==הוכחה==
עקרונית טענה זו נובעת ישירות מ[[משפט קנטור-שרדר-ברנשטיין]], שכן אם <math>|A| = |C| </math> אז מתקיים גם <math>|B| \leq |A| </math> וגם <math>|A| \leq |B|</math>, ולכן בהכרח <math>|B| = |A|</math>. אולם יש הוכחה של משפט זה שעושה שימוש בלמת הסנדוויץ' ועל-כן נוכיח אותה באופן עצמאי.
 
;הוכחה
נתון כי <math>|A| = |C|</math> ולכן קיימת פונקציה f [[פונקציה חד-חד-ערכית ועל|חד-חד ערכית ועל]] מ-A על C. כמו-כן נתון כי <math>|B| \leq |C|</math> ולכן ניתן לשכן את B בתוך C. אם-כך נתייחס ל-B כאל תת-קבוצה של C.
 
נגדיר <math>P_0 = A \setminus B</math>, ובאופן [[רקורסיה|רקורסיבי]] נגדיר <math>P_{n+1} = f[P_n]</math>, כאשר הביטוי <math>f[P_n]</math> מסמן את תמונת הפונקציה f מצומצמת לתחום <math>P_n</math>. נגדיר עוד <math>P= \bigcup_nP_n </math> על כל ה-n הטבעיים.
 
כעת נגדיר פונקציה g מ-A ל-B, ונראה כי היא חד-חד ערכית ועל:
<math>
g(x) =\left\{\begin{matrix}
x & \mbox{if } x \in A \setminus P \\
f(x) & \mbox{if } x \in P \end{matrix}\right.
</math>
 
נראה כי g חד-חד ערכית. נניח כי x,y זוג איברים שונים השייכים ל-A. יש שלוש אפשרויות:
* אם <math>x,y \in P</math> אז <math>g(x)=f(x), g(y)=f(y)</math>, ומכך ש-f חד-חד ערכית נובע כי <math>g(x)=f(x) \ne g(y)=f(y)</math>.
* אם <math>x,y \in A \setminus P</math> אז <math>g(x)=x, g(y)=y</math> ולכן בבירור מתקיימת חד-חד ערכיות.
* אם <math>x \in P</math> ו-<math>y \in A \setminus P</math> (ללא הגבלת הכלליות) אז <math>g(x)=f(x), g(y)=y</math>. נשים לב שמתקיים כי <math>f(x) \in P</math> ומההנחה נובע <math>y \notin P</math> ומכאן החד-חד ערכיות.
 
נראה כי g על B. יהי y איבר ב-B, נדון בשני מקרים:
* אם <math>y \in P</math> אז בבירור <math>y \notin P_0 = A \setminus P</math> ולכן קיים n טבעי כלשהו שעבורו <math>y \in P_n </math> ולפי ההגדרה <math>P_n=f[P_{n-1}]</math>. כלומר y בתמונת g עבור x כלשהו.
* אם <math> y \in A \setminus P</math> אז מהגדרת g נובע כי <math>g(y)=y</math>.
 
מכאן ש-g פונקציה חד-חד ערכית ועל מ-A על B, כלומר <math>|B| = |A|</math>.
 
[[קטגוריה:משפטים בתורת הקבוצות]]
8,258

עריכות