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