'''הגדרות.''' יהיו A קבוצהחזרה ל[[83-116, B קבוצה המוכלת בה וR יחס סדר חלקי:*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(yבדידה 1 להנדסה,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>
=== דוגמאות =יחסי שקילות==הגדרה: תהא <math>A</math> קבוצה ו-<math>R</math> יחס עליה. <math>R</math> יקרא '''יחס שקילות''' (יח"ש) אם הוא#רפלקסיבי#סימטרי#טרנזיטיבי
'''דוגמא.סימון מקובל:'''נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית אם <math>R</math> יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(lcm)x, והאינפימום הוא המחלק המשותף המקסימלי(gcdy)\in R</math>.
למשל וכן נסמן <math>sup\{12,33,10\}=lcm(12A,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10sim)=1</math>את הקבוצה עם יחס השקילות.
'''דוגמא'''עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא <math>\cup _{i\in I} A_i </math>====תרגיל====
'''דוגמא.'''על <math>\mathbb{R}</math> נגדיר ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>x,y\in \mathbb{R}</math>:
נביט בקבוצה <math>AxQy\iff x-y=\{1,2,3,4,5\}17</math> ונגדיר עליה יחס סדר חלקי:
<math>R=xRy\iff x-y\in \mathbb{N}\cup \{(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)0\}</math>
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)<math>xSy\iff x-y\in 2\mathbb{Z}\cup 3\mathbb{Z}</math>.
נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=xTy\{1,3,5iff x-y\}</math>. קבוצת חסמי המלעיל של B הינה <math>in \mathbb{2,4\Z}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
'''הגדרה.''' יהי R בדקו עבור כל אחד מהם האם הוא יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר מלא'''שקילות.
למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא.שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.=====פתרון=====
<math>Q</math> לא כיון שלא רפלקסיבי, שהרי לכל <math>x\in \mathbb{R}</math> (ובפרט קיים לפחות אחד) <math>x-x===יחסי שקילות===הגדרה: תהא A קבוצה ו-R יחס עליה0\neq 17</math>. R יקרה יחס שקילות אם הוא#רפלקסיבי#סימטרי#טרנזיטיבי
'''סימון מקובל:''' <math>R</math> אמנם רפלקסיבי, אך לא סימטרי.
אם R יחס שקילות מסמנים גם <math>x \sim yS</math> עבור לא טרנזיטיבי: <math>(x,y)2S6\in Rland 6S3</math> אבל לא נכון ש-<math>2S3</math>.
דוגמא: תהא <math>A=\{1,2,3,4,5,6\}</math>. נגדיר תת הקבוצות <math>A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}T</math> כן יחס שקילות:
נגדיר יחס R על A כך רפלקסיביות: יהי <math>x\exist 1\leq i in \leq 3 : xmathbb{R}</math>,yאז <math>x-x=0\in A_i \Leftrightarrow xRymathbb{Z}</math>.
טענה R יחס שקילותסימטריות: <math>xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx</math>.
הוכחהטרנזיטיביות:<math>xTy\land yTz\Rightarrow \exists a\in \mathbb{Z}: x-y=a \land \exists b\in \mathbb{Z}: y-z=b\\ \Rightarrow x-z=x-y+y-z=a+b\in \mathbb{Z}</math>.
1. רפלקסיביות - נניח <math>x\in A</math> לכן x שייך ל <math>A_i</math> עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן <math>(x,x)\in R</math>.===מחלקות שקילות וחלוקה===
2הגדרה: תהא <math>A</math> קבוצה. סימטריות - נניח '''חלוקה''' של <math>(x,y)A</math> היא אוסף של תת קבוצות זרות של <math>A</math> המכסות את <math>A</math>. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in RI}</math> אזי כך שמתקיים:* <math>x,y\forall i\in I: A_i\neq \varnothing </math> עבור .* <math>\bigcup _{i מסוים, מכיוון שאין משמעות לסדר שייכות \in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה, נובע שגם כולה.* הקבוצות <math>A_i</math> הן '''זרות בזוגות'''. כלומר החיתוך בין כל שתי תת קבוצות הוא ריק (y,x)<math>\forall i\ne j\in RI : A_i\cap A_j = \varnothing</math>).
3. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי קיימים i,j כך ש <math>x,y\in Aֹ_i</math> וגם <math>y,z\in A_j</math>. לכן <math>y\in A_i\cap A_j</math>. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש<math>A_i=A_j</math> ולכן <math>x,y,z\in A_i</math> ולכן <math>(x,z)\in R</math> כפי שרצינו.הגדרה:
יהא <math>R</math> יחס שקילות על <math>A</math> אזי
הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות # לכל <math>\{A_i\}_{ix\in I}A</math>כך ש:* מוגדרת '''מחלקת השקילות של <math>\forall i\in I: A_i \neq \emptyset x</math>* ''' להיות <math>\cup _bar{ix}=[x]_R:=\{y\in I} A_i =A | (x,y)\in R\}</math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה .* הקבוצות <math>A_i</math> הן # '''זרותקבוצת המנה ''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (מוגדרת <math>A/R := \forall i\not= j{ [x]_R | x\in I : A_iA\cap A_j = \phi } </math>).
כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).
'''משפט''': יהא <math>R</math> יחס שקילות על <math>A</math> אזי
# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\varnothing </math> (כלומר מחלקות השקילות זרות).
# <math>A=\bigcup_{[x]\in A/R}[x]</math> (כלומר איחוד מחלקות השקילות הוא כל <math>A</math>).
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של <math>A</math>.
דוגמא נוספת:
נגדיר מסקנה:תהא <math>A</math> קבוצה אזי יש התאמה {<math>R</math> יחס שקילות R על <math>\mathbb{Z}A</math> ע"י }<math>3|(x-y) \Leftrightarrow xRyleftrightarrow</math>{חלוקות של <math>A</math>}.
טענהחידוד: R אכן מהותו העיקרית של יחס שקילותשקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
הוכחה====תרגיל====ראינו לעיל יחס <math>T\subseteq \mathbb{R}\times \mathbb{R}</math> והראינו שהוא יחס שקילות. הוכיחו:
1א. רפלקסיביות - נניח <math>\forall x\in \mathbb{ZR}:3|0=x-\smallsetminus \mathbb{Q}\Rightarrow [x]_T\subseteq \mathbb{R}\smallsetminus \mathbb{Q}</math> לכן <math>xRx</math> .
2ב. סימטריות - נניח אם <math>(x,y)\in R</math> אזי <math>3|(x-y[0,1)</math> ולכן גם שונים אז <math>3|(y-[x)=-(x-]_T\neq [y)]_T</math>.
3ג. טרנזיטיביות - נניח <math>[(\forall x,y)\in \mathbb{R] } \and [(exists y,z)\in R]</math> אזי <math>3|(x-y[0,1)\and 3|(y-z) </math> ולכן גם <math>3|(z-: [x)]_T=(z-[y)+(y-x)]_T</math>.
=====פתרון=====
א.נוכיח בשלילה: יהי <math>x\in \mathbb{R}\smallsetminus \mathbb{Q}</math> ונניח בשלילה שקיים <math>q\in \mathbb{Q}\cap [x]_T</math>. נקבל שקיים <math>a\in \mathbb{Z}</math> כך ש <math>x-q=a</math> ולכן <math>x=a+q\in \mathbb{Q}</math> בסתירה (סגירות הרציונאליים).
הגדרה:ב. בהינתן כל <math>x>y</math> ולכן <math>x-y>0</math> ומאידך, כיון ששניהם בין 0 ל-1 נקבל <math>x-y<1</math>, ולכן ההפרש בהכרח לא שלם, ולכן הם לא שקולים.
יהא R יחס שקילות על A אזיג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם.
# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math># ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>=תרגיל====
על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר יחס <math>\sim</math> לפי זה שלכל <math>(x_1,y_1),(x_2,y_2)</math>:
למשל, בדוגמא הראשונה <math>A_1(x_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=y_1)\{A_1sim (x_2,A_2,A_3y_2)\}iff x_1^2+y_1^2=x_2^2+y_2^2</math>.
בדוגמא השניה קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של 0 היא <math>[(0]_R=\{ 0 \pm 3 \pm 6 \dots \},1)</math> וקבוצת המנה היא<math>\mathbb{Z}/R= \{[0]_R? ומהי,[1]_Rמבחינה גיאומטרית,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).קבוצת המנה?
=====פתרון=====
משפט: יהא R יחס שקילות על A אזי# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\phi </math> (כלומר מחלקות השקילות זרות)# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A מסקנה:תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A } <math>\leftrightarrow</math> {חלוקות של A} חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחתמעגל עם רדיוס 1 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.