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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(הלמה של צורן)
(הלמה של צורן)
שורה 19: שורה 19:
  
  
'''הוכחה (באמצעות הלמה של צורן).'''. נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע.  
+
'''הוכחה (באמצעות הלמה של צורן).'''. נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)
  
 
ט: תהא <math>\{B_i\}_{i\in I}</math> שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של  f על <math>B:=\bigcup_{i\in I}B_i</math> ג"כ חח"ע
 
ט: תהא <math>\{B_i\}_{i\in I}</math> שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של  f על <math>B:=\bigcup_{i\in I}B_i</math> ג"כ חח"ע
שורה 39: שורה 39:
 
'''תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו).''' קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי. הוכח כי קיימת קבוצה מגניבה C כך שלכל <math>C\subset B</math> מתקיים כי B אינה מגניבה. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.
 
'''תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו).''' קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי. הוכח כי קיימת קבוצה מגניבה C כך שלכל <math>C\subset B</math> מתקיים כי B אינה מגניבה. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-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> ולכן ההפרש בינהן אינו רציונאלי כפי שרצינו.
+
'''הוכחה.''' נביט באוסף הקבוצות המגניבות וביחס ההכלה (האוסף לא ריק כי כל נקודון הוא קבוצה מגניבה). לכל שרשרת של קבוצות מגניבות מתקיים כי האיחוד הכללי שלהן הינו קבוצה מגניבה. אמנם, אם 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 שווה לה.
שורה 48: שורה 48:
 
'''תרגיל.''' הוכח שלכל מרחב וקטורי קיים בסיס
 
'''תרגיל.''' הוכח שלכל מרחב וקטורי קיים בסיס
  
'''הוכחה.''' יהיה<math> V </math> מרחב וקטורי. נביט באוסף הקבוצות הבלתי תלויות שלו  <math>\{B\subseteq | B \; is \; linearly \; independent  \}</math>.
+
'''הוכחה.''' יהיה<math> V </math> מרחב וקטורי. נביט באוסף הקבוצות הבלתי תלויות שלו  <math>\{B\subseteq | B \; is \; linearly \; independent  \}</math>. (האוסף לא ריק כי וקטור בודד שונה מאפס מהווה קבוצה בת"ל)
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות בת"ל.
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות בת"ל.
  
שורה 77: שורה 77:
  
  
ב. נביט באוסף כל האוספים של תתי קבוצות זרות של A שכל אחת מהן מעוצמה a.  
+
ב. נביט באוסף כל האוספים של תתי קבוצות זרות של A שכל אחת מהן מעוצמה a. (האוסף לא ריק לפי סעיף קודם)
  
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות כך שכל אחת <math>B_i\in P(A) </math> אוסף של תתי קבוצות זרות של A מעוצמה a.
 
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות כך שכל אחת <math>B_i\in P(A) </math> אוסף של תתי קבוצות זרות של A מעוצמה a.
שורה 102: שורה 102:
 
ב. <math>B,C\in F \Rightarrow B\cap C \in F</math>
 
ב. <math>B,C\in F \Rightarrow B\cap C \in F</math>
  
ג. <math>B \in A \land  B\subset C \Rightarrow C\in F</math>
+
ג. <math>B \in F \land  B\subset C \Rightarrow C\in F</math>
  
 
הוכח שלכל קבוצה <math>A\subseteq P(X)</math> קיים <math>F</math> בוב מינמאלי שמכיל אותה  
 
הוכח שלכל קבוצה <math>A\subseteq P(X)</math> קיים <math>F</math> בוב מינמאלי שמכיל אותה  
שורה 109: שורה 109:
 
הוכחה:
 
הוכחה:
 
נגדיר <math>\{F|A\subseteq F \land F \; is \; bob\}</math> ונגדיר יחס <math>R</math> של "הכלה הפוכה"  
 
נגדיר <math>\{F|A\subseteq F \land F \; is \; bob\}</math> ונגדיר יחס <math>R</math> של "הכלה הפוכה"  
(<math>ARB\iff B\subseteq A</math> )  
+
(<math>ARB\iff B\subseteq A</math> )  (האוסף לא ריק כי <math>P(X)</math> היא בוב שמכיל את A )
 
אזי לכל שרשרת <math>\{F_i\}_{i\in I}</math> של בובים יש איבר מקסמאלי ביחס ל <math>R</math> שהוא  
 
אזי לכל שרשרת <math>\{F_i\}_{i\in I}</math> של בובים יש איבר מקסמאלי ביחס ל <math>R</math> שהוא  
 
<math>F:=\bigcap_{i\in I}F_i</math>. נראה ש <math>F</math> בוב.  
 
<math>F:=\bigcap_{i\in I}F_i</math>. נראה ש <math>F</math> בוב.  

גרסה מ־07:52, 2 באוגוסט 2013

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

הלמה של צורן

הגדרה. קבוצה A אשר מוגדר עליה יחס סדר חלקי R נקראת קבוצה סדורה חלקית. תת קבוצה של קבוצה סדורה חלקית C\subseteq A נקראת שרשרת אם R מהווה יחס סדר מלא על C.

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


הלמה של צורן שקולה לאקסיומת הבחירה. תהי \{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. במילים פשוטות: ניתן לבנות פונקציה הבוחרת נציג מכל קבוצה.


דוגמא. תהי 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 עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)

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

ה: יהיו x\not=y \in B אזי קיים j,i\in I כך ש x \in B_i, y \in B_j. כיוון שמדובר בשרשרת (היחס מצומצם אליה הוא יחס מלא) אזי

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

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

ט: im(f|_B)=im(f)

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


תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו). קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי. הוכח כי קיימת קבוצה מגניבה C כך שלכל C\subset B מתקיים כי B אינה מגניבה. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.

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

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

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


תרגיל. הוכח שלכל מרחב וקטורי קיים בסיס

הוכחה. יהיה V מרחב וקטורי. נביט באוסף הקבוצות הבלתי תלויות שלו \{B\subseteq | 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.


תרגיל. תהיינה a<b עוצמות אינסופיות, ותהי קבוצה A כך ש |A|=b

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

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


פתרון:

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


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

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

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

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

לפי הלמה של צורן קיים איבר מקס' B

אם \bigcup_{A'\in B}A'=A אז סיימנו

אחרת קיים A'':=A/\bigcup_{A'\in B}A' לא ריקה. אם העוצמה של גדולה שווה מ a אזי יש לה תת קבוצה מעוצמה a שנוכל לצרף ל B וזה יהיה סתירה למקס' של B. אם העוצמה שלה קטנה מ a אז נוכל לצרף אותה לאחת מ A'\in B ואז נקבל אוסף של קבוצות מעוצמה a שאיחודם כל A (כי |A'\cup A''|=a)


תרגיל

תהא 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 בוב מינמאלי שמכיל אותה (כלומר אם A\subseteq F' בוב אזי F\subseteq F')

הוכחה: נגדיר \{F|A\subseteq F \land F \; is \; bob\} ונגדיר יחס R של "הכלה הפוכה" (ARB\iff B\subseteq A ) (האוסף לא ריק כי P(X) היא בוב שמכיל את A ) אזי לכל שרשרת \{F_i\}_{i\in I} של בובים יש איבר מקסמאלי ביחס ל R שהוא F:=\bigcap_{i\in I}F_i. נראה ש F בוב.

א. \forall i: X\in F_i ולכן נמצא גם בחיתוך.

ב. 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

ג. באופן דומה.

לפי הלמה של צורן קיים איבר מקס' ביחס ל R שזה איבר מיני' ביחס להכלה רגילה.