'''הגדרה.''' דיאגרמת הסה Hasse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
'''הגדרה:''' יהי R יחס על A, אזי '''היחס ההופכי''' מוגדר להיות <math>R^{-1}=\{(y,x)|(x,y)\in R\}</math>
====תרגיל====
הוכח שאם R יחס סדר חלקי, גם ההופכי שלו יחס סדר חלקי
=====פתרון=====
*רפלקסיביות: לכל איבר a מתקיים <math>(a,a)\in R</math> ולכן <math>(a,a)\in R^{-1}</math>
*טרנזיטיביות: נניח <math>(x,y),(y,z)\in R^{-1}</math> לכן מתקיים <math>(y,x),(z,y)\in R</math> לכן לפי הטרנזיטיביות של R מתקיים <math>(z,x)\in R</math> ולכן <math>(x,z)\in R^{-1}</math>.
*אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y.
==איברים מיוחדים==
'''הגדרות.''' יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:
*איבר <math>x\in A</math> נקרא '''מינמלי''' ביחס לR אם <math>\forall y\in A:(y,x)\in R \rightarrow y=x</math>. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
*איבר <math>x\in A</math> נקרא '''מקסימלי''' ביחס לR אם <math>\forall y\in A:(x,y)\in R \rightarrow y=x</math>. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
*איבר <math>x\in A</math> נקרא '''איבר קטן ביותר/מינימום''' ביחס לR אם <math>\forall y\in A:(x,y)\in R</math>. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)*איבר <math>x\in A</math> נקרא '''איבר גדול ביותר/מקסימום''' ביחס לR אם <math>\forall y\in A:(y,x)\in R</math>. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B) מינוח/סימון: עבור קבוצה A נסמן לעיתים יחס סדר ב <math>\leq</math>. לא להתבלבל עם ה"קטן שווה" ה"רגיל"!. אם A קבוצה ו <math>leq</math> יחס סדר עליה, נסמן <math>(A,\leq)</math> ונקרא ל A קבוצה סדורה חלקית. עוד נאמר במקרה זה כי איבר x קטן שווה מאיבר y אם מתקיים <math>x\leq y</math>
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר מינימום הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי המקסימום.
הערה: מינימום <math>\leftarrow</math> מינימלי, וכן מקסימום <math>\leftarrow</math> מקסימלי, ולא להיפך!
'''====דוגמא.'''====
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
*2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.
==== תרגיל ====
תהא <math>(A,\leq)</math> קבוצה סדורה. הוכיחו/הפריכו: אם x מיני' יחיד אזי הוא איבר קטן ביותר
'''הגדרה:''' יהי R יחס על A, אזי '''היחס ההופכי''' מוגדר להיות ==== תרגיל ====תהא <math>R^{-1}=\{(yA,x\leq)|(</math> קבוצה סדורה. הוכיחו/הפריכו: אם x,מינימאלי יחיד ו y)מקסימאלי יחיד אזי <math>x\in R\}leq y</math>
'''==== תרגיל====תהא <math>(A,\leq)</math> קבוצה סדורה סופית לא ריקה. הוכיחו: קיים איבר מינימאלי.'''
הוכח שאם R יחס סדר חלקי=====פתרון=====באינדוקציה על גודל הקבוצה <math>|A|=n</math>. עבור <math>n=1</math> האיבר מינימאלי.נניח נכונות עבור <math>|A|=n-1</math> ותהא <math>|A|=n</math>. קיים <math>a\in A</math>, גם ההופכי שלו יחס סדר חלקיונתבונן בקבוצה הסדורה <math>(A\smallsetminus \{a\},\leq )</math>, שם יש מינימאלי שנסמנו <math>b</math>.
'''פתרוןנחזור כעת ל-<math>A</math>.''' נחלק למקרים:*רפלקסיביותאם <math>a\not \leq b</math> אז <math>b</math> מינימאלי גם ב-<math>A</math>: לכל איבר יהי <math>y\in A</math>, כך ש- <math>y\leq b</math>, ונראה <math>y=b</math>: אכן, מההנחה נקבל <math>y\neq a מתקיים </math>(, ולכן <math>y\in A\setminus \{a\}</math>,ומכיון ש-b מינימלי שם נקבל <math>y=b</math>. אם <math>a)\in Rleq b</math> ולכן אז <math>(a</math> מינימאלי ב-<math>A</math>. יהי <math>y\leq a</math>,ונניח בשלילה <math>y\neq a)</math>. לכן <math>y\in R^A\setminus \{-1a\}</math>*טרנזיטיביות: נניח . כעת מטרנזיטיבות נקבל <math>(x,y)\leq b</math>,(וממינימליות b נקבל <math>y=b</math>. בסה"כ יש לנו <math>a\leq b\land b\leq a</math>,z)ומאנטי-סימטריות נקבל <math>a=b</math> בסתירה (כי <math>b\in R^A\setminus \{-1a\}</math> לכן ). ===הגדרה=== יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(ya,xb),\in R]\or[(zb,ya)\in R]</math> לכן לפי הטרנזיטיביות של אזי R מתקיים נקרא '''יחס סדר קווי/לינארי'''. ====תרגיל====יהא <math>(zA,x\leq)</math> קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר. =====פתרון=====יהא <math>y\in RA</math> ולכן צ"ל: <math>(x,z)\in R^{-leq y</math>: מהעובדה שהיחס לינארי נקבל <math>x\leq y\lor y\leq x</math>. נחלק למקרים: 1}. אם <math>x\leq y</math>סיימנו.*אנטי-סימטריות: 2. אם <math>y\leq x ביחס לy וגם </math> אז לפי הגדרת מינימליות (ונתון ש- <math>x</math> מינימלי) נקבל <math>x=y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, </math> ולכן <math>x=\leq y</math> . ==חסמים==
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
*החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>sup(B)</math>
*החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math>
=== דוגמאות ===
====דוגמא.====
שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון.
====דוגמא(בהרצאה בד"כ)====
נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה 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> אוסף תתי קבוצות של A. החסם העליון שלה ב <math>(P(A),\subseteq)</math> הוא
<math>\cup _{i\in I} A_i </math> והחסם התחתון (אם זה אוסף לא ריק) שלהם הוא<math>\cap_{i\in I}A_i</math>
הוכיחו/הפריכו: אם <math>\cup_{i\in I}A_i \not\in X</math> אזי ל <math>\{A_i\mid i\in I\}</math> אין חסם עליון.
===הגדרה===
יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר קווי/לינארי'''.
====תרגיל====
יהא <math>(A,\leq)</math> קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר.
===תרגיל ממבחן===
הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי.
תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי.
'''הוכחה.'''
נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B.
===תרגיל===
נביט בQ אוסף השברים המצומצמים. נביט בR היחס המוגדר על ידי <math>(\frac{m_1}{n_1},\frac{m_2}{n_2})</math> אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math>. הוכיחו/הפריכו: R הינו יחס סדר חלקי.
'''פתרון.'''
נבדוק את תכונות היחס:
*רפלקסיביות - ברור.
*אנטי-סימטריות - אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math> וגם <math>(m_1\geq m_2)\and(n_1\geq n_2)</math> אזי <math>(m_1= m_2)\and(n_1= n_2)</math> ולכן שני השברים המצומצמים שווים.
*טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד.
לכן R הינו יחס סדר חלקי.
שאלה: מה היה קורה אילו לא דרשנו שברים מצומצמים?
=== יחס סדר מילוני ===
3. טרנז' - תרגיל
==== דוגמא דוגמה ====
נסתכל על <math>\mathbb{N}\times \mathbb{N}</math> אם הסדר המוגדר לעיל.
נגדיר <math>B = \{(x,1) | x\in \mathbb{N} \}</math> אזי <math>inf(B)=(1,1)</math> ו sup לא קיים.
*שימו לב ש <math>(1,1)</math> הוא איבר קטן ביותר. ==== תרגיל ====נסתכל על <math>\mathbb{N}\times \mathbb{Z}</math> ותתי הקבוצות *<math>B_1 = \{(4,-x) | x\in \mathbb{N} \}</math> *<math>B_2 = \{(4,x) | x\in \mathbb{N} \}</math>*<math>B_3 = \{(x,4) | x\in \mathbb{N} \}</math> #מצאו, אם קיימים, sup ו inf לקבוצות <math>B_2,B_3</math> כאשר <math>(\mathbb{N},\leq)</math> ו <math>(\mathbb{Z},\leq)</math> ו <math>\mathbb{N}\times \mathbb{Z}</math> עם יחס המכפלה#מצאו, אם קיימים, sup ו inf לקבוצות <math>B_1,B_2</math> כאשר <math>(\mathbb{N},|)</math> ו <math>(\mathbb{Z},\leq)</math> ו <math>\mathbb{N}\times \mathbb{Z}</math> עם היחס המילוני ==== תרגיל ====נסתכל על <math>\mathbb{N}\times (0,1]</math> ותתי הקבוצה <math>B = \{(4,\frac{1}{n+1}) | n\in \mathbb{N} \}</math> מצאו, אם קיימים, sup ו inf לקבוצות <math>B</math> כאשר <math>(\mathbb{N},|)</math> ו <math>(0,1],\leq)</math> ו <math>\mathbb{N}\times (0,1]</math> עם היחס המילוני ==== תרגיל ====יהיו <math>(A,\leq),(B,\preceq)</math> שני יחסי סדר משווים הוכיחו/הפריכו:#יחס המכפלה על <math>A\times B</math> הוא משווה.#היחס המילוני על <math>A\times B</math> הוא משווה. ==== תרגיל ====#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> לא סופי המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\inf B\right\} =\left\{ B\subseteq A\mid\,\exists\sup B\right\}</math> .#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\sup B\right\}=\emptyset</math> . ==תרגילים נוספים== ===תרגיל ממבחן=== הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי. תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי. '''הוכחה.''' נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B. ===תרגיל=== נביט בQ אוסף השברים המצומצמים. נביט בR היחס המוגדר על ידי <math>(\frac{m_1}{n_1},\frac{m_2}{n_2})</math> אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math>. הוכיחו/הפריכו: R הינו יחס סדר חלקי. '''פתרון.''' נבדוק את תכונות היחס:*רפלקסיביות - ברור.*אנטי-סימטריות - אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math> וגם <math>(m_1\geq m_2)\and(n_1\geq n_2)</math> אזי <math>(m_1= m_2)\and(n_1= n_2)</math> ולכן שני השברים המצומצמים שווים.*טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד. לכן R הינו יחס סדר חלקי. שאלה: מה היה קורה אילו לא דרשנו שברים מצומצמים?
=== תרגיל (ממבחן קיץ תשעה מועד ב) ===
=== תרגיל (מבוחן תשעג)===
יהא <math>A</math> קבוצה ו <math>R\subseteq A\times A</math> יחס סדר מלא עליה. נגדיר <math>O</math>
להיות קבוצת כל יחסי הסדר החלקיים על <math>A</math>, סדורה ע"י הכלה. (כלומר הזוג <math>(O,\subseteq)</math> - במילים אחרות, חושבים על <math>O</math> עם יחס הסדר החלקי "הכלה")
הוכח1. יהא <math>R\subseteq A\times A</math> יחס סדר על <math>A</math> הוכיחו: אם<math>R\subseteq A\times A</math> יחס סדר משווה עליה. אז <math>R</math> איבר מקסימלי ב <math>O</math>
2.הוכיח: אם ב <math>A</math> לפחות 2 איברים אז ב <math>(O,\subseteq)</math> אין איברים גדול ביותר 3. הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\inf</math> 4. הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\sup</math> ==== פתרון- ====יהא <math>R\subseteq A\times A</math> יחס סדר על <math>A</math> ונניח כי הוא משווה. נוכיח כי הוא איבר מקסמאלית ב <math>O</math>. יהי <math>S\in O</math> יחס סדר חלקי על <math>A</math> המקיים <math>R\subseteq S</math> צ"ל <math>R=S</math>
נניח בשלילה כי <math>R</math> מוכל ממש ב <math>S</math>
מכיוון ש <math>S</math> יחס סדר חלקי (בפרט אנטי סימטרי) אזי <math>a=b</math> (כי גם (<math>a,b)\in S</math>)
אזי קיבלנו כי ּ<math>(a,a)=(a,b)\notin R</math> סתירה לכך ש <math>R</math> יחס סדר מלא ובפרט רפלקסיבי.
=== תרגיל ===
נגדיר <math>X=\left\{ 1,2,3,\dots,10\right\}</math> . עוד נגדיר <math>\mathbb{O}</math> להיות קבוצת כל יחסי השקילות על <math>X</math>.נגדיר יחס <math>\preceq</math> מעל <math>\mathbb{O}</math> על ידי הכלל <math>R_{1}\preceq R_{2}\iff\left(\left|X/R_{1}\right|<\left|X/R_{1}\right|\right)\lor\left(R_{1}=R_{2}\right)</math> כאשר <math>\left|X/R_{1}\right|</math> פירושו מספר האיברים בקבוצת המנה של היחס <math>R_{1}</math>.
1. הוכיחו: כי <math>\preceq</math> הוא יחס סדר על <math>\mathbb{O}</math>.
2. הוכיחו/הפריכו: זהו יחס סדר קווי
3. מצאו, אם קיימים, איבר קטן ביותר ב<math>\left(\mathbb{O},\preceq\right)</math> ואיבר גדול ביותר ב <math>\left(\mathbb{O},\preceq\right)</math>
האם ב === תרגיל === תהא <math>OA=\left\{ \left(a_{1},a_{2},a_{3}\right):\,a_{1},a_{2},a_{3}\in\mathbb{N}\right\} =\mathbb{N}^{3}</math> יש מקסימום . נגדיר יחס סדר (איבר גדול ביותראין צורך להוכיח)?<math>\leq</math> על A כך <math>\left(a_{1},a_{2},a_{3}\right)\leq\left(b_{1},b_{2},b_{3}\right)\iff\forall i\in\left\{ 1,2,3\right\} :\,a_{i}\leq b_{i}</math>
תשובה: לא. נניח שקיים איבר מקס' #מצאו <math>S</math>. כיוון שגם <math>R^{-1}m\in OA</math> יחס אזי איבר קטן ביותר, אם קיים.#מצאו איברים מינמאלים ב <math>RA\backslash\left\cup R^{-1} m\subseteq S</math>. בפרט אם <math>(a,b)right\in R</math> שונים (נניח שב <math>A</math> יש 2 איברים לפחות) אזי <math>(b,a)\in R^{-1}</math> ולכן <math>(a,b),(b,a)\in S</math> בניגוד לכך ש <math>S</math> אנטי סימטריאם קיימים.