שינויים
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
'''הלמה של צורןהגדרה.''' תהי קבוצה A אשר מוגדר עליה יחס סדר חלקי R נקראת קבוצה '''סדורה חלקית '''לא ריקה. תת קבוצה של קבוצה סדורה חלקית <math>C\subseteq A</math> נקראת ''' כך שלכל שרשרת המוכלת בA קיים חסם מלעיל מA''' אם R מהווה יחס סדר מלא/משווה על C. אזי קיים בA איבר מקסימלי (איבר שאין איבר שונה ממנו הגדול ממנו)כלומר לכל <math>c_1,c_2\in C</math> מתקיים כי <math>c_1Rc_2</math> או <math>c_2Rc_1</math>. דוגמה פרטית וחשובה: עבור 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>. במילים פשוטות: ניתן לבנות פונקציה הבוחרת נציג מכל קבוצה.
*'''הלמה של צורן.''': תהי 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>g:\Big\{f^{-1}\Big[\{b\}\Big]:b\in im(f)\Big\}\rightarrow A</math> השולחת כל קבוצת מקורות לנציג כלשהו שלה.
'''הוכחה (באמצעות הלמה של צורן).'''. נביט באוסף תתי הקבוצות של A כך שהצמצום של f עליהן חח"ע. (האוסף לא ריק כי תמיד אפשר להצטמצם לקבוצה הריקה)
ט: תהא <math>\{B_i\}_{i\in I}</math> שרשרת כלשהיא של קבוצת שהצמצום של f עליהם חח"ע אזי הצמצום של f על <math>B:=\bigcup_{i\in I}B_i</math> ג"כ חח"ע
ואז <math>B\cup \{x\}</math> קבוצה שמכילה ממש את <math>B</math> והצמצום של f עליה חח"ע. סתירה.
'''באמצעות עקרון המקסימום של האוסדורף'''
===תרגיל ממבחן תשס"ט מועד א' (ד"ר שי סרוסי וד"ר אלי בגנו)===
קבוצה נקראת "מגניבה" אם ההפרש בין כל שני איברים שונים בה אינו רציונאלי. הוכח כי קיימת קבוצה מגניבה C כך שלכל <math>C\subset B</math> מתקיים כי B אינה מגניבה. כמו כן, הוכח שמתקיים שלכל איבר שאינו ב-C יש איבר מ-C אשר ההפרש בינהם רציונאלי.
אם כן, האיחוד הכללי הינו חסם מקסימלי של השרשרת (כי הוא מכיל את כל הקבוצות בשרשרת) מתוך אוסף הקבוצות המגניבות, ולכן לפי הלמה של צורן קיימת קבוצה מגניבה מקסימלית ביחס להכלה. זה אומר שכל קבוצה מגניבה המכילה את C שווה לה.
<math>\{B\subseteq V| B \; is \; linearly \; independent \}</math>. (האוסף לא ריק כי וקטור בודד שונה מאפס מהווה קבוצה בת"ל)
תהא <math>\{B_i\}_{i\in I}</math> שרשרת של קבוצות בת"ל.
א. הוכח כי קיימת ל-B תת קבוצה A מעוצמה a
ב. הוכח כי B היא איחוד זר של קבוצות אשר כל אחת מהן מעוצמה a.
א. מההגדרה של השוואת עוצמות, קיימת פונקציה חח"ע מקבוצה בעוצמת a אל תוך B. התמונה של פונקציה זו הינה תת קבוצה A בתוך B מעוצמה a.
תהא <math>X</math>. קבוצה <math>F\subseteq P(X)</math> תקרא בוב אם:
(כלומר אם <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 )
