תרגול 10 תשעז
הגדרות. יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
- חסם מלעיל של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(y,x)\in R }[/math]
- חסם מלרע של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(x,y)\in R }[/math]
- החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן [math]\displaystyle{ sup(B) }[/math]
- החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן [math]\displaystyle{ inf(B) }[/math]
דוגמאות
דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).
למשל [math]\displaystyle{ sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1 }[/math]
דוגמא עבור [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא [math]\displaystyle{ \cup _{i\in I} A_i }[/math]
דוגמא.
נביט בקבוצה [math]\displaystyle{ A=\{1,2,3,4,5\} }[/math] ונגדיר עליה יחס סדר חלקי:
[math]\displaystyle{ R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)\} }[/math]
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד [math]\displaystyle{ B=\{1,3,5\} }[/math]. קבוצת חסמי המלעיל של B הינה [math]\displaystyle{ \{2,4\} }[/math]. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים [math]\displaystyle{ [(a,b)\in R]\or[(b,a)\in R] }[/math] אזי R נקרא יחס סדר מלא.
תרגיל (ממבחן קיץ תשעה מועד ב)
תהא [math]\displaystyle{ X }[/math] קבוצת כל הסדרות הבינאריות (סדרה בינארית היא [math]\displaystyle{ a_1a_2a_3\dots }[/math] כאשר [math]\displaystyle{ a_n\in \{0,1\} }[/math]). נגדיר יחס [math]\displaystyle{ R }[/math] על [math]\displaystyle{ X }[/math] כך: עבור [math]\displaystyle{ a=a_1a_2\dots ,b=b_1b_2\dots \in X }[/math]
[math]\displaystyle{ aRb \iff \; \forall n\; a_n-b_n \neq (-1)^n }[/math]
א. הוכיחו ש [math]\displaystyle{ R }[/math] יחס סדר על [math]\displaystyle{ X }[/math]
ב. קבעו האם [math]\displaystyle{ R }[/math] יחס סדר מלא על [math]\displaystyle{ X }[/math]
ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב [math]\displaystyle{ X }[/math] (ביחס ל [math]\displaystyle{ R }[/math])
פתרון
דרך שקולה לתאר את היחס שמפשטת את השאלה היא כך
[math]\displaystyle{ aRb \iff \big( \forall k \; a_{2k}=1 \Rightarrow b_{2k}=1, \; a_{2k-1}=0\Rightarrow b_{2k-1}=0\big) }[/math]
כלומר במיקומים הזוגיים, אם a שווה 1 אז זה גורר ש b שווה 1
ובמיקומים האי זוגיים, אם a שווה 0 אז זה גורר ש b שווה 0
א. תרגיל לבד!
ב. לא סדר מלא, למשל [math]\displaystyle{ a=000\dots, b=111\dots }[/math] לא מתייחסים זה לזה.
ג. קימיים, [math]\displaystyle{ M=010101\dots }[/math] הינו איבר הגדול ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ aRM }[/math]
[math]\displaystyle{ m=101010\dots }[/math] הינו איבר קטן ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ mRa }[/math]