תרגול 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 נקרא יחס סדר מלא.

למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.

יחסי שקילות

הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא

1. רפלקסיבי
2. סימטרי
3. טרנזיטיבי

סימון מקובל:

אם R יחס שקילות מסמנים גם [math]\displaystyle{ x \sim y }[/math] עבור [math]\displaystyle{ (x,y)\in R }[/math]

דוגמא: תהא [math]\displaystyle{ A=\{1,2,3,4,5,6\} }[/math]. נגדיר תת הקבוצות [math]\displaystyle{ A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\} }[/math]

נגדיר יחס R על A כך [math]\displaystyle{ \exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy }[/math]

טענה R יחס שקילות

הוכחה:

1. רפלקסיביות - נניח [math]\displaystyle{ x\in A }[/math] לכן x שייך ל [math]\displaystyle{ A_i }[/math] עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן [math]\displaystyle{ (x,x)\in R }[/math].

2. סימטריות - נניח [math]\displaystyle{ (x,y)\in R }[/math] אזי [math]\displaystyle{ x,y\in A_i }[/math] עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם [math]\displaystyle{ (y,x)\in R }[/math].

3. טרנזיטיביות - נניח [math]\displaystyle{ [(x,y)\in R] \and [(y,z)\in R] }[/math] אזי קיימים i,j כך ש [math]\displaystyle{ x,y\in Aֹ_i }[/math] וגם [math]\displaystyle{ y,z\in A_j }[/math]. לכן [math]\displaystyle{ y\in A_i\cap A_j }[/math]. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש[math]\displaystyle{ A_i=A_j }[/math] ולכן [math]\displaystyle{ x,y,z\in A_i }[/math] ולכן [math]\displaystyle{ (x,z)\in R }[/math] כפי שרצינו.

הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] כך ש:

• [math]\displaystyle{ \forall i\in I: A_i \neq \emptyset }[/math]
• [math]\displaystyle{ \cup _{i\in I} A_i =A }[/math] כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
• הקבוצות [math]\displaystyle{ A_i }[/math] הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ([math]\displaystyle{ \forall i\not= j\in I : A_i\cap A_j = \phi }[/math])

כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).

דוגמא נוספת:

נגדיר יחס שקילות R על [math]\displaystyle{ \mathbb{Z} }[/math] ע"י [math]\displaystyle{ 3|(x-y) \Leftrightarrow xRy }[/math]

טענה: R אכן יחס שקילות

הוכחה:

1. רפלקסיביות - נניח [math]\displaystyle{ \forall x\in \mathbb{Z}:3|0=x-x }[/math] לכן [math]\displaystyle{ xRx }[/math]

2. סימטריות - נניח [math]\displaystyle{ (x,y)\in R }[/math] אזי [math]\displaystyle{ 3|(x-y) }[/math] ולכן גם [math]\displaystyle{ 3|(y-x)=-(x-y) }[/math]

3. טרנזיטיביות - נניח [math]\displaystyle{ [(x,y)\in R] \and [(y,z)\in R] }[/math] אזי [math]\displaystyle{ 3|(x-y)\and 3|(y-z) }[/math] ולכן גם [math]\displaystyle{ 3|(z-x)=(z-y)+(y-x) }[/math]

הגדרה:

יהא R יחס שקילות על A אזי

1. לכל [math]\displaystyle{ x\in A }[/math] מוגדרת מחלקת השקילות של x להיות [math]\displaystyle{ \bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} }[/math]
2. קבוצת המנה מוגדרת [math]\displaystyle{ A/R := \{ [x]_R | x\in A\} }[/math]

למשל, בדוגמא הראשונה [math]\displaystyle{ A_1,A_2,A_3 }[/math] הן מחלקות השקילות. קבוצת המנה היא [math]\displaystyle{ A/R=\{A_1,A_2,A_3\} }[/math]

בדוגמא השניה מחלקת השקילות של 0 היא [math]\displaystyle{ [0]_R=\{ 0 \pm 3 \pm 6 \dots \} }[/math] וקבוצת המנה היא [math]\displaystyle{ \mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\} }[/math] (כלומר כל השאריות האפשריות בחלוקה ב-3).

משפט: יהא R יחס שקילות על A אזי

1. לכל [math]\displaystyle{ x,y\in A }[/math] מתקיים [math]\displaystyle{ [x]=[y] }[/math] או [math]\displaystyle{ [x]\cap [y] =\phi }[/math] (כלומר מחלקות השקילות זרות)
2. [math]\displaystyle{ A=\bigcup_{[x]\in A/R}[x] }[/math] כלומר (איחוד מחלקות השקילות תתן את כל A)

הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A

מסקנה: תהא A קבוצה אזי יש התאמה {[math]\displaystyle{ R }[/math] יחס שקילות על A } [math]\displaystyle{ \leftrightarrow }[/math] {חלוקות של A}

חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.