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

הלמה של צורן

הגדרה. קבוצה 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 מתקבלת.