הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 8"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(הלמה של צורן)
מ (אקסיומת הבחירה ואקסיומות שקולות)
 
(19 גרסאות ביניים של משתמש אחר אחד אינן מוצגות)
שורה 1: שורה 1:
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
  
=הלמה של צורן=
 
  
'''הגדרה.''' קבוצה A אשר מוגדר עליה יחס סדר חלקי R נקראת קבוצה '''סדורה חלקית'''. תת קבוצה של קבוצה סדורה חלקית <math>C\subseteq A</math> נקראת '''שרשרת''' אם R מהווה יחס סדר מלא על C.
+
====הגדרת שרשרת בקס"ח====
 +
'''הגדרה.''' קבוצה A אשר מוגדר עליה יחס סדר חלקי R נקראת קבוצה '''סדורה חלקית'''. תת קבוצה של קבוצה סדורה חלקית <math>C\subseteq A</math> נקראת '''שרשרת''' אם R מהווה יחס סדר מלא/משווה על C. כלומר לכל <math>c_1,c_2\in C</math> מתקיים כי <math>c_1Rc_2</math> או <math>c_2Rc_1</math>. שימו לב כי עבור <math>C=\{\}</math> (הקבוצה הריקה) היא תמיד שרשרת. גם לכל <math>a\in A</math> מתקיים כי עבור <math>C=\{a\}</math> היא תמיד שרשרת.
  
'''הלמה של צורן.''' תהי A קבוצה סדורה חלקית '''לא ריקה''' כך שלכל שרשרת המוכלת בA קיים חסם מלעיל מA. אזי קיים בA איבר מקסימלי (איבר שאין איבר שונה ממנו הגדול ממנו).
+
דוגמה פרטית וחשובה: עבור A שהיא קבוצה של קבוצות ו R הוא יחס ההכלה, שרשרת C היא קבוצה של חלק מהקבוצות ב A המקיימות כי כל שתי קבוצות ב C או שהראשונה מוכלת בשניה או שהשניה מוכלת בראשונה.
  
 +
=אקסיומת הבחירה ואקסיומות שקולות=
 +
'''אקסיומת הבחירה.''' תהי <math>\{A_i\}_i{\in I}</math> משפחה של קבוצות לא ריקות. אזי קיימת פונקציה <math>f:\{A_i\}_{i\in I}\rightarrow\bigcup_{i\in I}A_i </math> המקיימת <math>\forall i\in I:f(A_i)\in A_i</math>. במילים פשוטות: ניתן לבנות פונקציה הבוחרת נציג מכל קבוצה.
  
הלמה של צורן שקולה ל'''אקסיומת הבחירה.''' תהי <math>\{A_i\}_i{\in I}</math> משפחה של קבוצות לא ריקות. אזי קיימת פונקציה <math>f:\{A_i\}_{i\in I}\rightarrow\bigcup_{i\in I}A_i </math> המקיימת <math>\forall i\in I:f(A_i)\in A_i</math>. במילים פשוטות: ניתן לבנות פונקציה הבוחרת נציג מכל קבוצה.
+
תחת אקסיומות ZF (רשימת של אקסיומות "סטנדרטיות", לא משנה אם שמעתם עליהם או לא), הדברים הבאים שקולים לאקסיומת הבחירה:
  
 +
*'''הלמה של צורן.''': תהי A קבוצה סדורה חלקית '''לא ריקה''' כך שלכל שרשרת המוכלת בA קיים חסם מלעיל מA. אזי קיים בA איבר מקסימלי (איבר שאין איבר שונה ממנו הגדול ממנו).
 +
*'''עקרון המקסימום של האוסדורף''': כל שרשרת מוכלת בשרשרת מקסימלית (שרשרת מקסימאלית = שרשרת שלא מוכלת ממש באף שרשרת אחרת. לחילופין, כל איבר שנוסיף לשרשרת תגרום לה לא להיות שרשרת)
  
'''דוגמא.''' תהי <math>f:A\rightarrow B</math> פונקציה. הוכח שקיים צמצום חח"ע של f בעל תמונה זהה ל-f.
 
  
'''הוכחה (באמצעות אקסיומת הבחירה).''' נציג את A כאיחוד אוסף המקורות של כל התמונות של הפונקציה <math>A=\bigcup_{b\in im(f)}f^{-1}\Big[\{b\}\Big]</math>. לפי אקסיומת הבחירה ניתן לבנות פונקציה  
+
 
 +
 
 +
 
 +
===דוגמה===
 +
תהי <math>f:A\rightarrow B</math> פונקציה. הוכח שקיים צמצום חח"ע של f בעל תמונה זהה ל-f.
 +
 
 +
==== הוכחה====
 +
===== באמצעות אקסיומת הבחירה=====
 +
נציג את A כאיחוד אוסף המקורות של כל התמונות של הפונקציה <math>A=\bigcup_{b\in im(f)}f^{-1}\Big[\{b\}\Big]</math>. לפי אקסיומת הבחירה ניתן לבנות פונקציה  
 
<math>g:\Big\{f^{-1}\Big[\{b\}\Big]:b\in im(f)\Big\}\rightarrow A</math> השולחת כל קבוצת מקורות לנציג כלשהו שלה.
 
<math>g:\Big\{f^{-1}\Big[\{b\}\Big]:b\in im(f)\Big\}\rightarrow A</math> השולחת כל קבוצת מקורות לנציג כלשהו שלה.
  
 
נוכיח כי <math>h:=f|_{im(g)}</math> הינה חח"ע והתמונה שלה שווה לזו של f. נניח <math>h(a)=h(b)</math> לכן <math>a,b\in f^{-1}\Big[\{h(a)\}\Big]</math> אבל כל מקור של תמונה נשלח לנציג '''יחיד''' על ידי g אחרת זו סתירה לחד ערכיות ולכך ש-g הינה פונקציה. כמו כן, מכיוון שמכל מקור נבחר נציג, כל התמונה של f מתקבלת.
 
נוכיח כי <math>h:=f|_{im(g)}</math> הינה חח"ע והתמונה שלה שווה לזו של f. נניח <math>h(a)=h(b)</math> לכן <math>a,b\in f^{-1}\Big[\{h(a)\}\Big]</math> אבל כל מקור של תמונה נשלח לנציג '''יחיד''' על ידי g אחרת זו סתירה לחד ערכיות ולכך ש-g הינה פונקציה. כמו כן, מכיוון שמכל מקור נבחר נציג, כל התמונה של f מתקבלת.
  
 +
===== באמצעות הלמה של צורן=====
 +
נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)
  
'''הוכחה (באמצעות הלמה של צורן).'''. נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)
+
ט: תהא <math>\{A'_i\}_{i\in I}</math> שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של  f על <math>\hat{A}:=\bigcup_{i\in I}A'_i</math> ג"כ חח"ע
  
ט: תהא <math>\{B_i\}_{i\in I}</math> שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של  f על <math>B:=\bigcup_{i\in I}B_i</math> ג"כ חח"ע
+
ה: יהיו <math>x\not=y \in \hat{A}</math> אזי קיים <math>j,i\in I</math> כך ש <math>x \in A'_i, y \in A'_j</math>. כיוון שמדובר בשרשרת (היחס מצומצם אליה הוא יחס מלא) אזי
  
ה: יהיו <math>x\not=y \in B</math> אזי קיים <math>j,i\in I</math> כך ש <math>x \in B_i, y \in B_j</math>. כיוון שמדובר בשרשרת (היחס מצומצם אליה הוא יחס מלא) אזי
+
או ש <math>A'_i \subseteq A'_j</math> או  <math>A'_j \subseteq A'_i</math> נניח בה"כ <math>A'_j \subseteq A'_i</math> אזי <math>x\not= y \in A'_i </math>
 +
כיוון שהצמצום של f על <math>A'_i</math> היא חח"ע נקבל כי <math>f(x)\not=f(y)</math>
  
או ש <math>B_i \subseteq B_j</math> או  <math>B_j \subseteq B_i</math> נניח בה"כ <math>B_j \subseteq B_i</math>  אזי <math>x\not= y \in B_i </math>
+
לפי הלמה של צורן קיים <math>\hat{A}\subseteq A </math> מקסמאלית כך ש f מצומצמת עליה חח"ע.
כיוון שהצמצום של f על <math>B_i</math> היא חח"ע נקבל כי <math>f(x)\not=f(y)</math>
+
  
לפי הלמה של צורן קיים <math>B\subseteq A </math> מקסמאלית כך ש  f מצומצמת עליה חח"ע.
+
ט: <math>im(f|_{\hat{A}})=im(f)</math>
  
ט: <math>im(f|_B)=im(f)</math>
+
ה: אחרת קיים <math>y\in im(f)/ im(f|_{\hat{A}})</math> נבחר מקור <math>x\in A</math> ל <math>y</math>
 +
ואז <math>\hat{A}\cup \{x\}</math> קבוצה שמכילה ממש את <math>\hat{A}</math> והצמצום של f עליה חח"ע. סתירה.
  
ה: אחרת קיים <math>y\in im(f)/ im(f|_B)</math> נבחר מקור <math>x\in A</math> ל <math>y</math>
+
=====באמצעות עקרון המקסימום של האוסדורף=====
ואז <math>B\cup \{x\}</math> קבוצה שמכילה ממש את <math>B</math> והצמצום של f עליה חח"ע. סתירה.
+
נגדיר <math>\mathcal{O}= \{A'\subseteq A\mid f|_{A'} \text{ is 1-1 function }\}</math> להיות קבוצה כל תתי הקבוצות  של A שהצמצום של f עליהם היא חח"ע. נסתכל על הקסח <math>\mathcal{O}</math> עם יחס ההכלה. ונסתכל על השרשרת <math>\{\emptyset\}</math> (שימו לב שהצמצום לפונקציה הריקה היא הפונקציה (הקבוצה) הריקה והיא חח"ע).
 +
לפי עקרון המקסימום של האוסדורף קיימת שרשרת מקסמאלית C המכילה את  <math>\{\emptyset\}</math>. נגדיר <math>\hat{A} = \cup_{A'\in C}f</math>.  
  
 +
ט: צמצום f על <math>\hat{A}</math> היא חח"ע
  
 +
ה: נניח <math>x_1\neq x_2\in \hat{A}</math> אזי קיימות <math>A'_1,A'_2\in C</math> כך ש <math>x_i\in A'_i</math>. מכיוון ש C שרשרת נקבל ש <math>A'_1\subseteq A'_2</math> או להיפך. בה"כ <math>A'_1\subseteq A'_2</math> ולכן <math>x_1,x_2\in A'_2</math> ומכיוון שהצמצום של f על  <math> A'_2</math> היא חח"ע, נקבל כי <math>x_1,x_2</math> ממופים לתמונת שונות כנדרש.
  
'''תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו).''' קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי. הוכח כי קיימת קבוצה מגניבה C כך שלכל <math>C\subset B</math> מתקיים כי B אינה מגניבה. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.
+
ט: התמונה של הצמצום של f על <math>\hat{A}</math> היא <math>Im(f)</math>, כלומר <math>Im(f|_{\hat{A}})=Im(f)</math>
  
'''הוכחה.''' נביט באוסף הקבוצות המגניבות וביחס ההכלה (האוסף לא ריק כי כל נקודון הוא קבוצה מגניבה). לכל שרשרת של קבוצות מגניבות מתקיים כי האיחוד הכללי שלהן הינו קבוצה מגניבה. אמנם, אם x,y באיחוד הכללי אזי קיימות קבוצות בשרשרת S,T כך ש <math>x\in S \and y\in T</math>. מכיוון שזו שרשרת, ניתן ללא הגבלת הכלליות לומר כי <math>S\subseteq T</math> ולכן <math>x,y\in T</math> ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.
+
ה: נב"ש שקיים <math>b\in Im(f)</math> שאין לו מקור ב <math>\hat{A}</math> אזי, לפי הגדרת התמונה של f, קיים <math>a\in A</math> (כך ש <math>a\notin \hat{A}</math>) המקיים כי <math>f(a)=b</math>. נקבל כי <math>\hat{A}\cup \{a\}</math> מכילה ממש את <math>\hat{A}</math> והצמצום עליה חח"ע (השתכנעו!) ולכן אם נוסיף את <math>\hat{A}\cup \{a\}</math> לשרשרת C נקבל שרשרשת שמכילה ממש את C בסתירה למקסמאליות של C.
 +
 
 +
===תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו)===
 +
קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי.
 +
 
 +
1. הוכח כי קיימת קבוצה מגניבה C כך שלכל <math>C\subset B</math> מתקיים כי B אינה מגניבה.
 +
 
 +
2. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.
 +
 
 +
====הוכחה====
 +
הוכחת 1. שקולה ללהוכיח כי קיימת קבוצה מגניבה C מקסימאלית ביחס להכלה. נוכיח:
 +
 
 +
===== לפי הלמה של צורן =====
 +
נביט באוסף הקבוצות המגניבות וביחס ההכלה (האוסף לא ריק כי כל נקודון הוא קבוצה מגניבה). לכל שרשרת של קבוצות מגניבות מתקיים כי האיחוד הכללי שלהן הינו קבוצה מגניבה. אמנם, אם x,y באיחוד הכללי אזי קיימות קבוצות בשרשרת S,T כך ש <math>x\in S \and y\in T</math>. מכיוון שזו שרשרת, ניתן ללא הגבלת הכלליות לומר כי <math>S\subseteq T</math> ולכן <math>x,y\in T</math> ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.
  
 
אם כן, האיחוד הכללי הינו חסם מקסימלי של השרשרת (כי הוא מכיל את כל הקבוצות בשרשרת) מתוך אוסף הקבוצות המגניבות, ולכן לפי הלמה של צורן קיימת קבוצה מגניבה מקסימלית ביחס להכלה. זה אומר שכל קבוצה מגניבה המכילה את C שווה לה.
 
אם כן, האיחוד הכללי הינו חסם מקסימלי של השרשרת (כי הוא מכיל את כל הקבוצות בשרשרת) מתוך אוסף הקבוצות המגניבות, ולכן לפי הלמה של צורן קיימת קבוצה מגניבה מקסימלית ביחס להכלה. זה אומר שכל קבוצה מגניבה המכילה את C שווה לה.
 +
===== לפי עקרון המקסימום של האוסדורף =====
 +
נגדיר <math>\mathcal{O}</math> אוסף הקבוצות המגניבות, סדורה ע"י הכלה. מתקיים כי <math>\{\emptyset\}</math> שרשרת ולכן היא מוכל בשרשרת מקסימאלית <math>\mathcal{C}</math>.
 +
נגדיר <math>C=\cup_{C'\in \mathcal{C}}</math>
  
נניח שקיים איבר שאין לו הפרש רציונאלי עם אף איבר בC. אזי אם נוסיף אותו לC נקבל קבוצה מגניבה המכילה ממש את C בסתירה.
+
ט: C מגניבה
  
 +
ה: אם x,y ב C אזי קיימות קבוצות בשרשרת <math>S,T\in \mathcal{C}</math> כך ש <math>x\in S \and y\in T</math>. מכיוון שזו שרשרת, ניתן ללא הגבלת הכלליות לומר כי <math>S\subseteq T</math> ולכן <math>x,y\in T</math> ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.
  
'''תרגיל.''' הוכח שלכל מרחב וקטורי קיים בסיס
+
ט: C מגניבה ''' מקסימאלית''' (ביחס להכלה)
  
'''הוכחה.''' יהיה<math> V </math> מרחב וקטורי. נביט באוסף הקבוצות הבלתי תלויות שלו   
+
ה: נב"ש כי קיימת <math>\hat{C}</math> קבוצה מגניבה שמכילה ממש את C אזי <math>\mathcal{C}\cup \{\hat{C}\}</math> היא שרשרת שמכילה ממש את <math>\mathcal{C}</math> בסתירה למקסמאליות של <math>\mathcal{C}</math>
<math>\{B\subseteq V| B \; is \; linearly \; independent  \}</math>. (האוסף לא ריק כי וקטור בודד שונה מאפס מהווה קבוצה בת"ל)
+
 
 +
 
 +
 
 +
2. נב"ש שקיים איבר שאין לו הפרש רציונאלי עם אף איבר בC. אזי אם נוסיף אותו לC נקבל קבוצה מגניבה המכילה ממש את C בסתירה.
 +
 
 +
===תרגיל===
 +
הוכח שלכל מרחב וקטורי קיים בסיס (גם אם המרחב אינו מימד סופי)
 +
 
 +
====הוכחה====
 +
יהיה<math> V </math> מרחב וקטורי. ונרצה להוכיח שקיים בסיס למרחב
 +
===== לפי הלמה של צורן =====
 +
נביט באוסף הקבוצות הבלתי תלויות שלו   
 +
<math>\{B\subseteq V| B \; is \; linearly \; independent  \}</math>. (האוסף לא ריק כי קבוצה ריקה היא קבוצה בת"ל)
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות בת"ל.
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות בת"ל.
  
שורה 63: שורה 109:
 
ה: אחרת קיים <math>v\in V\backslash span(B)</math> אבל אז <math>B\cup \{v\} </math> מכילה ממש את B וגם בת"ל. סתירה למקס' של B.
 
ה: אחרת קיים <math>v\in V\backslash span(B)</math> אבל אז <math>B\cup \{v\} </math> מכילה ממש את B וגם בת"ל. סתירה למקס' של B.
  
 +
===== לפי עקרון המקסימום של האוסדורף =====
 +
נגדיר <math>\mathcal{O}</math> אוסף הקבוצות הבלתי תלויות שמוכלות במרחב. כלומר <math>\{B\subseteq V| B \; is \; linearly \; independent  \}</math>. בקס"ח <math>\mathcal{O}</math> סדורה ע"י הכלה מתקיים כי <math>\{\emptyset\}</math> היא שרשרת (קבוצה ריקה היא בת"ל) ולכן היא מוכל בשרשרת מקסימאלית C. נגדיר <math>B=\cup_{B'\in C}B'</math>
  
 +
ט: <math>B</math> בת"ל
  
'''תרגיל.''' תהיינה <math>a<b</math> עוצמות אינסופיות, ותהי קבוצה B כך ש <math>|B|=b</math>
+
ה: יהיה <math>\alpha_1 v_1 +\cdots +\alpha_n v_n =0</math> צ"ל של וקטורים מ B שמתאפס אזי כל וקטור שייך לאיזה שהוא <math>B_j\in C</math>. כיוון ש C שרשרת אזי כל הוקטורים נמצאים באותה קבוצה.
 +
כלומר  <math>\exists k\in I \forall i : v_i \in B_k</math> כיוון ש <math>B_k</math> קבוצה בת"ל נקבל שכל המקדמים שווים לאפס.
  
א. הוכח כי קיימת ל-B תת קבוצה A מעוצמה a
+
ט: <math>B</math> פורשת (ולכן מהווה בסיס).
  
ב. הוכח כי B היא איחוד זר של קבוצות אשר כל אחת מהן מעוצמה a.
+
ה: אחרת קיים <math>v\in V\backslash span(B)</math> אבל אז <math>B\cup \{v\} </math> מכילה ממש את B וגם בת"ל. ולכן אם נוסיף קבוצה זאת ל C נקבל שרשרת שמכילה ממש את C בסתירה למקסימאליות של C.
  
 +
===תרגיל===
 +
תהיינה <math>a<b</math> עוצמות אינסופיות, ותהי קבוצה B כך ש <math>|B|=b</math>
  
 +
א. הוכח כי קיימת ל-B תת קבוצה A מעוצמה a
 +
 +
ב. הוכח כי B היא איחוד זר של קבוצות אשר כל אחת מהן מעוצמה a.
  
'''פתרון''':
+
====פתרון====
  
 
א. מההגדרה של השוואת עוצמות, קיימת פונקציה חח"ע מקבוצה בעוצמת a אל תוך B. התמונה של פונקציה זו הינה תת קבוצה A בתוך B מעוצמה a.  
 
א. מההגדרה של השוואת עוצמות, קיימת פונקציה חח"ע מקבוצה בעוצמת a אל תוך B. התמונה של פונקציה זו הינה תת קבוצה A בתוך B מעוצמה a.  
  
  
ב. נביט באוסף כל האוספים של תתי קבוצות זרות של B שכל אחת מהן מעוצמה a.  (האוסף לא ריק לפי סעיף קודם)
+
סעיף ב. נוכיח במספר דרכים:
 +
 
 +
===== לפי הלמה של צורן =====
 +
נביט באוסף כל האוספים של תתי קבוצות זרות של B שכל אחת מהן מעוצמה a.  (האוסף לא ריק לפי סעיף קודם)
  
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות כך שכל אחת <math>B_i\in P(P(A)) </math> אוסף של תתי קבוצות זרות של B מעוצמה a.
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות כך שכל אחת <math>B_i\in P(P(A)) </math> אוסף של תתי קבוצות זרות של B מעוצמה a.
שורה 94: שורה 152:
 
אם העוצמה שלה קטנה מ a אז נוכל לצרף אותה לאחת מהקבוצות ב<math>S</math> ואז נקבל אוסף של קבוצות מעוצמה a שאיחודם שווה B.
 
אם העוצמה שלה קטנה מ a אז נוכל לצרף אותה לאחת מהקבוצות ב<math>S</math> ואז נקבל אוסף של קבוצות מעוצמה a שאיחודם שווה B.
  
 +
===== לפי עקרון המקסימום של האוסדורף =====
 +
נגדיר <math>\mathcal{O}</math> קבוצת כל האוספים של תתי קבוצות זרות של B שכל אחת מהן מעוצמה a. בקס"ח <math>\mathcal{O}</math> עם הכלה מתקיים כי <math>\{\{A\}\}</math> היא שרשרת כאשר A היא תת קבוצה של B מעוצמה a שקיימת לפי סעיף א. כעת לפי עקרון המקסימום, קיימת שרשרת C מקסימאלית. נגדיר <math>T=\cup_{T'\in C}T'</math>
  
'''תרגיל'''
+
ט: <math>T\in \mathcal{O}</math>  
+
תהא <math>X</math>. קבוצה <math>F\subseteq P(X)</math> תקרא בוב אם:
+
  
א. <math>X\in F</math>  
+
ה: יהיו <math>A_1,A_2\in T</math> אזי קיימות <math>T'_1,T'_2</math> כך ש <math>A_i\in T'_i</math> ומכיוון ש C שרשרת <math>T'_1\subseteq T'_2</math> או להיפך. נניח בה"כ כי <math>T'_1\subseteq T'_2</math> ולכן <math>A_1,A_2\in T'_2</math> ומכיוון ש <math>T'_2\in \mathcal{C}</math> נקבל כי <math>A_1,A_2</math> זרות ומעוצמה a כנדרש
  
ב. <math>B,C\in F \Rightarrow B\cap C \in F</math>
+
כעת נגדיר <math>B'=\cup_{A'\in T}A'</math> ונגדיר <math>\hat{B}=B\setminus B'</math> .
  
ג. <math>B \in F \land  B\subset C \Rightarrow C\in F</math>
+
אם <math>a<|\hat{B}|</math> אז לפי סעיף א' קיימת לה תת קבוצה <math>\hat{A}</math> מעוצמה a. לפי הגדרה <math>\hat{B}</math> מתקיים כי <math>\hat{A}</math> זרה לכל קבוצה ב T ולכן <math>T\cup \{\hat{A}\}\in \mathcal{O}</math> ואם נוסיף אותה ל C נקבל שרשרת שמכילה ממש את C בסתירה למקסימאליות של C.
  
הוכח שלכל קבוצה <math>A\subseteq P(X)</math> קיים <math>F</math> בוב מינמאלי שמכיל אותה  
+
לכן <math>|\hat{B}|\leq a</math> ונבחר קבוצה אחת A ששייכת T (קיימת לפי סעיף א) ונחליף אותה ב <math>A\cup\hat{B}</math>. מכיוון ש a עוצמה אינסופית נקבל כי <math>A\cup\hat{B}</math> מעוצמה a גם כן (בצירוף <math>|\hat{B}|\leq a</math>) וקיבלנו כעת קבוצות זרות שכל אחת מעוצמה a שהאיחוד של כולם שווה ל B כנדרש
(כלומר אם <math>A\subseteq F'</math> בוב וגם  <math>F'\subseteq F</math> אזי <math>F=F'</math>)
+
  
הוכחה:
+
===תרגיל===
נגדיר <math>\{F|A\subseteq F \land F \; is \; bob\}</math> ונגדיר יחס <math>R</math> של "הכלה הפוכה"
+
(<math>ARB\iff B\subseteq A</math> )  (האוסף לא ריק כי <math>P(X)</math> היא בוב שמכיל את A )
+
תהא <math>X</math>. קבוצה <math>F\subseteq P(X)</math> תקרא בוב אם:
אזי לכל שרשרת <math>\{F_i\}_{i\in I}</math> של בובים יש איבר מקסמאלי ביחס ל <math>R</math> שהוא
+
<math>F:=\bigcap_{i\in I}F_i</math>. נראה ש <math>F</math> בוב.
+
  
א. <math>\forall i: X\in F_i</math> ולכן נמצא גם בחיתוך.
+
א. <math>X\in F</math>  
  
ב. <math>B,C\in F \Rightarrow \forall i B,C\in F_i \Rightarrow \forall i B\cap C \in F_i \Rightarrow \ B\cap C \in F</math>  
+
ב. <math>B,C\in F \Rightarrow B\cap C \in F</math> (סגורה לחיתוכים סופיים)
  
ג. באופן דומה.
+
ג. <math>B \in F \land  B\subset C \Rightarrow C\in F</math> (סגורה כלפי מעלה)
  
לפי הלמה של צורן קיים איבר מקס' ביחס ל <math>F'</math> שזה איבר מיני' ביחס להכלה רגילה.
+
תהא קבוצה <math>A\subseteq P(X)</math> שכל חיתוך סופי של קבוצות בה שונה מקבוצה ריקה. הוכיחו: קיים <math>F\neq P(X)</math> בוב מקסימאלי שמכיל אותה.

גרסה אחרונה מ־13:56, 15 באוגוסט 2022

חזרה למערכי התרגול


הגדרת שרשרת בקס"ח

הגדרה. קבוצה A אשר מוגדר עליה יחס סדר חלקי R נקראת קבוצה סדורה חלקית. תת קבוצה של קבוצה סדורה חלקית C\subseteq A נקראת שרשרת אם R מהווה יחס סדר מלא/משווה על C. כלומר לכל c_1,c_2\in C מתקיים כי c_1Rc_2 או c_2Rc_1. שימו לב כי עבור C=\{\} (הקבוצה הריקה) היא תמיד שרשרת. גם לכל a\in A מתקיים כי עבור C=\{a\} היא תמיד שרשרת.

דוגמה פרטית וחשובה: עבור A שהיא קבוצה של קבוצות ו R הוא יחס ההכלה, שרשרת C היא קבוצה של חלק מהקבוצות ב A המקיימות כי כל שתי קבוצות ב C או שהראשונה מוכלת בשניה או שהשניה מוכלת בראשונה.

אקסיומת הבחירה ואקסיומות שקולות

אקסיומת הבחירה. תהי \{A_i\}_i{\in I} משפחה של קבוצות לא ריקות. אזי קיימת פונקציה f:\{A_i\}_{i\in I}\rightarrow\bigcup_{i\in I}A_i המקיימת \forall i\in I:f(A_i)\in A_i. במילים פשוטות: ניתן לבנות פונקציה הבוחרת נציג מכל קבוצה.

תחת אקסיומות ZF (רשימת של אקסיומות "סטנדרטיות", לא משנה אם שמעתם עליהם או לא), הדברים הבאים שקולים לאקסיומת הבחירה:

  • הלמה של צורן.: תהי A קבוצה סדורה חלקית לא ריקה כך שלכל שרשרת המוכלת בA קיים חסם מלעיל מA. אזי קיים בA איבר מקסימלי (איבר שאין איבר שונה ממנו הגדול ממנו).
  • עקרון המקסימום של האוסדורף: כל שרשרת מוכלת בשרשרת מקסימלית (שרשרת מקסימאלית = שרשרת שלא מוכלת ממש באף שרשרת אחרת. לחילופין, כל איבר שנוסיף לשרשרת תגרום לה לא להיות שרשרת)



דוגמה

תהי f:A\rightarrow B פונקציה. הוכח שקיים צמצום חח"ע של f בעל תמונה זהה ל-f.

הוכחה

באמצעות אקסיומת הבחירה

נציג את A כאיחוד אוסף המקורות של כל התמונות של הפונקציה A=\bigcup_{b\in im(f)}f^{-1}\Big[\{b\}\Big]. לפי אקסיומת הבחירה ניתן לבנות פונקציה g:\Big\{f^{-1}\Big[\{b\}\Big]:b\in im(f)\Big\}\rightarrow A השולחת כל קבוצת מקורות לנציג כלשהו שלה.

נוכיח כי h:=f|_{im(g)} הינה חח"ע והתמונה שלה שווה לזו של f. נניח h(a)=h(b) לכן a,b\in f^{-1}\Big[\{h(a)\}\Big] אבל כל מקור של תמונה נשלח לנציג יחיד על ידי g אחרת זו סתירה לחד ערכיות ולכך ש-g הינה פונקציה. כמו כן, מכיוון שמכל מקור נבחר נציג, כל התמונה של f מתקבלת.

באמצעות הלמה של צורן

נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)

ט: תהא \{A'_i\}_{i\in I} שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של f על \hat{A}:=\bigcup_{i\in I}A'_i ג"כ חח"ע

ה: יהיו x\not=y \in \hat{A} אזי קיים j,i\in I כך ש x \in A'_i, y \in A'_j. כיוון שמדובר בשרשרת (היחס מצומצם אליה הוא יחס מלא) אזי

או ש A'_i \subseteq A'_j או A'_j \subseteq A'_i נניח בה"כ A'_j \subseteq A'_i אזי x\not= y \in A'_i כיוון שהצמצום של f על A'_i היא חח"ע נקבל כי f(x)\not=f(y)

לפי הלמה של צורן קיים \hat{A}\subseteq A מקסמאלית כך ש f מצומצמת עליה חח"ע.

ט: im(f|_{\hat{A}})=im(f)

ה: אחרת קיים y\in im(f)/ im(f|_{\hat{A}}) נבחר מקור x\in A ל y ואז \hat{A}\cup \{x\} קבוצה שמכילה ממש את \hat{A} והצמצום של f עליה חח"ע. סתירה.

באמצעות עקרון המקסימום של האוסדורף

נגדיר \mathcal{O}= \{A'\subseteq A\mid f|_{A'} \text{ is 1-1 function }\} להיות קבוצה כל תתי הקבוצות של A שהצמצום של f עליהם היא חח"ע. נסתכל על הקסח \mathcal{O} עם יחס ההכלה. ונסתכל על השרשרת \{\emptyset\} (שימו לב שהצמצום לפונקציה הריקה היא הפונקציה (הקבוצה) הריקה והיא חח"ע). לפי עקרון המקסימום של האוסדורף קיימת שרשרת מקסמאלית C המכילה את \{\emptyset\}. נגדיר \hat{A} = \cup_{A'\in C}f.

ט: צמצום f על \hat{A} היא חח"ע

ה: נניח x_1\neq x_2\in \hat{A} אזי קיימות A'_1,A'_2\in C כך ש x_i\in A'_i. מכיוון ש C שרשרת נקבל ש A'_1\subseteq A'_2 או להיפך. בה"כ A'_1\subseteq A'_2 ולכן x_1,x_2\in A'_2 ומכיוון שהצמצום של f על  A'_2 היא חח"ע, נקבל כי x_1,x_2 ממופים לתמונת שונות כנדרש.

ט: התמונה של הצמצום של f על \hat{A} היא Im(f), כלומר Im(f|_{\hat{A}})=Im(f)

ה: נב"ש שקיים b\in Im(f) שאין לו מקור ב \hat{A} אזי, לפי הגדרת התמונה של f, קיים a\in A (כך ש a\notin \hat{A}) המקיים כי f(a)=b. נקבל כי \hat{A}\cup \{a\} מכילה ממש את \hat{A} והצמצום עליה חח"ע (השתכנעו!) ולכן אם נוסיף את \hat{A}\cup \{a\} לשרשרת C נקבל שרשרשת שמכילה ממש את C בסתירה למקסמאליות של C.

תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו)

קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי.

1. הוכח כי קיימת קבוצה מגניבה C כך שלכל C\subset B מתקיים כי B אינה מגניבה.

2. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.

הוכחה

הוכחת 1. שקולה ללהוכיח כי קיימת קבוצה מגניבה C מקסימאלית ביחס להכלה. נוכיח:

לפי הלמה של צורן

נביט באוסף הקבוצות המגניבות וביחס ההכלה (האוסף לא ריק כי כל נקודון הוא קבוצה מגניבה). לכל שרשרת של קבוצות מגניבות מתקיים כי האיחוד הכללי שלהן הינו קבוצה מגניבה. אמנם, אם x,y באיחוד הכללי אזי קיימות קבוצות בשרשרת S,T כך ש x\in S \and y\in T. מכיוון שזו שרשרת, ניתן ללא הגבלת הכלליות לומר כי S\subseteq T ולכן x,y\in T ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.

אם כן, האיחוד הכללי הינו חסם מקסימלי של השרשרת (כי הוא מכיל את כל הקבוצות בשרשרת) מתוך אוסף הקבוצות המגניבות, ולכן לפי הלמה של צורן קיימת קבוצה מגניבה מקסימלית ביחס להכלה. זה אומר שכל קבוצה מגניבה המכילה את C שווה לה.

לפי עקרון המקסימום של האוסדורף

נגדיר \mathcal{O} אוסף הקבוצות המגניבות, סדורה ע"י הכלה. מתקיים כי \{\emptyset\} שרשרת ולכן היא מוכל בשרשרת מקסימאלית \mathcal{C}. נגדיר C=\cup_{C'\in \mathcal{C}}

ט: C מגניבה

ה: אם x,y ב C אזי קיימות קבוצות בשרשרת S,T\in \mathcal{C} כך ש x\in S \and y\in T. מכיוון שזו שרשרת, ניתן ללא הגבלת הכלליות לומר כי S\subseteq T ולכן x,y\in T ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.

ט: C מגניבה מקסימאלית (ביחס להכלה)

ה: נב"ש כי קיימת \hat{C} קבוצה מגניבה שמכילה ממש את C אזי \mathcal{C}\cup \{\hat{C}\} היא שרשרת שמכילה ממש את \mathcal{C} בסתירה למקסמאליות של \mathcal{C}


2. נב"ש שקיים איבר שאין לו הפרש רציונאלי עם אף איבר בC. אזי אם נוסיף אותו לC נקבל קבוצה מגניבה המכילה ממש את C בסתירה.

תרגיל

הוכח שלכל מרחב וקטורי קיים בסיס (גם אם המרחב אינו מימד סופי)

הוכחה

יהיה V מרחב וקטורי. ונרצה להוכיח שקיים בסיס למרחב

לפי הלמה של צורן

נביט באוסף הקבוצות הבלתי תלויות שלו \{B\subseteq V| B \; is \; linearly \; independent  \}. (האוסף לא ריק כי קבוצה ריקה היא קבוצה בת"ל) תהא \{B_i\}_{i\in I} שרשרת של קבוצות בת"ל.

ט: B:=\bigcup_{i\in I}B_i הינו חסם מלעיל של השרשרת (כלומר צ"ל ש B בת"ל

ה: יהיה \alpha_1 v_1 +\cdots +\alpha_n v_n =0 צ"ל של וקטורים מ B שמתאפס אזי כל וקטור שייך לאיזה שהוא B_j. כיוון שמדובר בשרשרת אזי כל הוקטורים נמצאים באותה קבוצה. כלומר \exists k\in I \forall i : v_i \in B_k כיוון ש B_k קבוצה בת"ל נקבל שכל המקדמים שווים לאפס.

לכן יש קבוצה B בת"ל מקסימלית

ט: B פורשת (ולכן מהווה בסיס).

ה: אחרת קיים v\in V\backslash span(B) אבל אז B\cup \{v\} מכילה ממש את B וגם בת"ל. סתירה למקס' של B.

לפי עקרון המקסימום של האוסדורף

נגדיר \mathcal{O} אוסף הקבוצות הבלתי תלויות שמוכלות במרחב. כלומר \{B\subseteq V| B \; is \; linearly \; independent  \}. בקס"ח \mathcal{O} סדורה ע"י הכלה מתקיים כי \{\emptyset\} היא שרשרת (קבוצה ריקה היא בת"ל) ולכן היא מוכל בשרשרת מקסימאלית C. נגדיר B=\cup_{B'\in C}B'

ט: B בת"ל

ה: יהיה \alpha_1 v_1 +\cdots +\alpha_n v_n =0 צ"ל של וקטורים מ B שמתאפס אזי כל וקטור שייך לאיזה שהוא B_j\in C. כיוון ש C שרשרת אזי כל הוקטורים נמצאים באותה קבוצה. כלומר \exists k\in I \forall i : v_i \in B_k כיוון ש B_k קבוצה בת"ל נקבל שכל המקדמים שווים לאפס.

ט: B פורשת (ולכן מהווה בסיס).

ה: אחרת קיים v\in V\backslash span(B) אבל אז B\cup \{v\} מכילה ממש את B וגם בת"ל. ולכן אם נוסיף קבוצה זאת ל C נקבל שרשרת שמכילה ממש את C בסתירה למקסימאליות של C.

תרגיל

תהיינה a<b עוצמות אינסופיות, ותהי קבוצה B כך ש |B|=b

א. הוכח כי קיימת ל-B תת קבוצה A מעוצמה a

ב. הוכח כי B היא איחוד זר של קבוצות אשר כל אחת מהן מעוצמה a.

פתרון

א. מההגדרה של השוואת עוצמות, קיימת פונקציה חח"ע מקבוצה בעוצמת a אל תוך B. התמונה של פונקציה זו הינה תת קבוצה A בתוך B מעוצמה a.


סעיף ב. נוכיח במספר דרכים:

לפי הלמה של צורן

נביט באוסף כל האוספים של תתי קבוצות זרות של B שכל אחת מהן מעוצמה a. (האוסף לא ריק לפי סעיף קודם)

תהא \{B_i\}_{i\in I} שרשרת של קבוצות כך שכל אחת B_i\in P(P(A)) אוסף של תתי קבוצות זרות של B מעוצמה a.

ט: X:=\bigcup_{i\in I}B_i הינו חסם מלעיל של השרשרת.

ה: לכל 2 תתי קבוצות של B ששיכות ל X קיים i\in I כך ששתי תתי הקבוצות שיכות ל B_i ולכן זרות. בנוסף כל תת קבוצה של B ששיכת ל X שייכת ל B_i כלשהוא ולכן מעוצמה a.

לפי הלמה של צורן קיים אוסף מקס' S

אם \bigcup S=B אז סיימנו

אחרת D:=B/\bigcup S לא ריקה. אם העוצמה של D גדולה שווה מ a אזי יש לה תת קבוצה מעוצמה a שנוכל לצרף ל S וזה יהיה סתירה למקס' של S. אם העוצמה שלה קטנה מ a אז נוכל לצרף אותה לאחת מהקבוצות בS ואז נקבל אוסף של קבוצות מעוצמה a שאיחודם שווה B.

לפי עקרון המקסימום של האוסדורף

נגדיר \mathcal{O} קבוצת כל האוספים של תתי קבוצות זרות של B שכל אחת מהן מעוצמה a. בקס"ח \mathcal{O} עם הכלה מתקיים כי \{\{A\}\} היא שרשרת כאשר A היא תת קבוצה של B מעוצמה a שקיימת לפי סעיף א. כעת לפי עקרון המקסימום, קיימת שרשרת C מקסימאלית. נגדיר T=\cup_{T'\in C}T'

ט: T\in \mathcal{O}

ה: יהיו A_1,A_2\in T אזי קיימות T'_1,T'_2 כך ש A_i\in T'_i ומכיוון ש C שרשרת T'_1\subseteq T'_2 או להיפך. נניח בה"כ כי T'_1\subseteq T'_2 ולכן A_1,A_2\in T'_2 ומכיוון ש T'_2\in \mathcal{C} נקבל כי A_1,A_2 זרות ומעוצמה a כנדרש

כעת נגדיר B'=\cup_{A'\in T}A' ונגדיר \hat{B}=B\setminus B' .

אם a<|\hat{B}| אז לפי סעיף א' קיימת לה תת קבוצה \hat{A} מעוצמה a. לפי הגדרה \hat{B} מתקיים כי \hat{A} זרה לכל קבוצה ב T ולכן T\cup \{\hat{A}\}\in \mathcal{O} ואם נוסיף אותה ל C נקבל שרשרת שמכילה ממש את C בסתירה למקסימאליות של C.

לכן |\hat{B}|\leq a ונבחר קבוצה אחת A ששייכת T (קיימת לפי סעיף א) ונחליף אותה ב A\cup\hat{B}. מכיוון ש a עוצמה אינסופית נקבל כי A\cup\hat{B} מעוצמה a גם כן (בצירוף |\hat{B}|\leq a) וקיבלנו כעת קבוצות זרות שכל אחת מעוצמה a שהאיחוד של כולם שווה ל B כנדרש

תרגיל

תהא X. קבוצה F\subseteq P(X) תקרא בוב אם:

א. X\in F

ב. B,C\in F \Rightarrow B\cap C \in F (סגורה לחיתוכים סופיים)

ג. B \in F \land  B\subset C \Rightarrow C\in F (סגורה כלפי מעלה)

תהא קבוצה A\subseteq P(X) שכל חיתוך סופי של קבוצות בה שונה מקבוצה ריקה. הוכיחו: קיים F\neq P(X) בוב מקסימאלי שמכיל אותה.