תרגול 10 תשעז

הגדרות. יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:

חסם מלעיל של B הוא איבר $x\in A$ כך שמתקיים $\forall y\in B:(y,x)\in R$
חסם מלרע של B הוא איבר $x\in A$ כך שמתקיים $\forall y\in B:(x,y)\in R$
החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן $sup(B)$
החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן $inf(B)$

דוגמאות

דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).

למשל $sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1$

דוגמא עבור $\{A_i\}_{i\in I}$ אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא $\cup _{i\in I} A_i$

דוגמא.

נביט בקבוצה $A=\{1,2,3,4,5\}$ ונגדיר עליה יחס סדר חלקי:

$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)\}$

(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)

נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד $B=\{1,3,5\}$ . קבוצת חסמי המלעיל של B הינה $\{2,4\}$ . המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.

הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים $[(a,b)\in R]\or[(b,a)\in R]$ אזי R נקרא יחס סדר מלא.

תרגיל (ממבחן קיץ תשעה מועד ב)

תהא $X$ קבוצת כל הסדרות הבינאריות (סדרה בינארית היא $a_1a_2a_3\dots$ כאשר $a_n\in \{0,1\}$ ). נגדיר יחס $R$ על $X$ כך: עבור $a=a_1a_2\dots ,b=b_1b_2\dots \in X$