'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==יחסי סדר==
'''הגדרה:''' יחס R על A נקרא '''אנטי-סימטרי''' אם מתקיים <math>\forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y)</math>
*היחס 'קטן-שווה' על המספרים
*היחס 'מוכל-שווה' על הקבוצות
*היחס 'מחלק את ' על הטבעיים
'''הגדרה: .''' דיאגרמת הסה HassseHasse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <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> ונגדיר עליה יחס סדר חלקי:
<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>
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
*5,3,1 הינם איברים מינימליים שכן אין איבר שקטן מאף אחד מהם. הם אינם מינימום כי אף אחד מהם לא קטן מכל האיברים האחרים.
*4 הינו מקסימום של הקבוצה, הוא בוודאי מקסימלי
*2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.
==== תרגיל ====
תהא <math>(A,\leq)</math> קבוצה סדורה. הוכיחו/הפריכו: אם x מיני' יחיד אזי הוא איבר קטן ביותר
==== תרגיל ====
תהא <math>(A,\leq)</math> קבוצה סדורה. הוכיחו/הפריכו: אם x מינימאלי יחיד ו y מקסימאלי יחיד אזי <math>x\leq y</math>
==== תרגיל ====
תהא <math>(A,\leq)</math> קבוצה סדורה סופית לא ריקה. הוכיחו: קיים איבר מינימאלי.
=====פתרון=====
באינדוקציה על גודל הקבוצה <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\leq b</math> אז <math>a</math> מינימאלי ב-<math>A</math>. יהי <math>y\leq a</math>, ונניח בשלילה <math>y\neq a</math>. לכן <math>y\in A\setminus \{a\}</math>. כעת מטרנזיטיבות נקבל <math>y\leq b</math>, וממינימליות b נקבל <math>y=b</math>. בסה"כ יש לנו <math>a\leq b\land b\leq a</math>, ומאנטי-סימטריות נקבל <math>a=b</math> בסתירה (כי <math>b\in A\setminus \{a\}</math>).
===הגדרה===
יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר קווי/לינארי'''.
====תרגיל====
יהא <math>(A,\leq)</math> קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר.
=====פתרון=====
יהא <math>y\in A</math> צ"ל: <math>x\leq y</math>: מהעובדה שהיחס לינארי נקבל <math>x\leq y\lor y\leq x</math>. נחלק למקרים:
1. אם <math>x\leq y</math> סיימנו.
2. אם <math>y\leq x</math> אז לפי הגדרת מינימליות (ונתון ש- <math>x</math> מינימלי) נקבל <math>x=y</math> ולכן <math>x\leq y</math> .
==חסמים==
'''הגדרות.''' יהיו 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>
====דוגמא.====
נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של B הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
====דוגמא====
נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. <math>B=\{1,1.4,1.41,1.414,1.4142,...\}</math>. חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה.
שימו לב, אם נביט בקבוצה 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>X\subseteq P(\mathbb{N})</math> כך שבקבוצה הסדורה <math>(X,\subseteq)</math> קיים B שאין לו חסם עליון.
==== תרגיל====
עבור <math>X\subseteq P(\mathbb{N})</math>, נסתכל בקבוצה הסדורה <math>(X,\subseteq)</math> וב <math>\{A_i\}_{i\in I}</math> אוסף תתי קבוצות של <math>\mathbb{N}</math>.
הוכיחו/הפריכו: אם <math>\cup_{i\in I}A_i \not\in X</math> אזי ל <math>\{A_i\mid i\in I\}</math> אין חסם עליון.
=== יחס סדר מילוני ===
יהיו <math>(A,\leq),(B,\preceq)</math> שתי קבוצות סדורות חלקית.
על <math>A\times B</math> ניתן להגדיר את '''היחס המילוני''' <math>R</math> ע"י
<math>(a_1,b_1)R(a_2,b_2)\iff (a_1 < a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2)</math>
==== דוגמא ====
נסתכל על <math>\mathbb{N}\times \mathbb{N}</math> עם הסדר המילוני.
נגדיר <math>B = \{(1,x) | x\in \mathbb{N} \}</math> אזי <math>sup(B)=(2,1),inf(B)=(1,1)</math>
נגדיר <math>B = \{(x,1) | x\in \mathbb{N} \}</math> אזי <math>inf(B)=(1,1)</math> ו sup לא קיים.
*שימו לב ש <math>(1,1)</math> הוא איבר קטן ביותר
=== מכפלה של יחסי סדר ===
יהיו <math>(A,\leq),(B,\preceq)</math> שתי קבוצות סדורות חלקית.
על <math>A\times B</math> ניתן להגדיר את היחס <math>R</math> הבא:
<math>(a_1,b_1)R(a_2,b_2)\iff (a_1 \leq a_2) \land ( b_1 \preceq b_2)</math>
זהו יחס סדר:
הוכחה:
1. רפקלסיביות: לכל <math>a,b</math> מתקיים כי <math>a\leq a, b\preceq b</math> ולכן <math>(a,b)R(a,b)</math>
2. אנטי סימטריות: אם <math>(a,b)R(a1,b1)</math> וגם <math>(a1,b1)R(a,b) </math> אז <math>a\leq a1, b\preceq b1</math> וגם <math>a1\leq a, b1 \preceq b</math>, כיוון שאלו יחס סדר נקבל כי <math>a=a1,b=b1</math>
3. טרנז' - תרגיל
==== דוגמה ====
נסתכל על <math>\mathbb{N}\times \mathbb{N}</math> אם הסדר המוגדר לעיל.
נגדיר <math>B = \{(1,x) | x\in \mathbb{N} \}</math> אזי <math>inf(B)=(1,1)</math> ו sup לא קיים
נגדיר <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>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>
=== תרגיל (מבוחן תשעג)===
יהא <math>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>(a,b)\in S\land(a,b)\notin R</math>. כיוון ש <math>R</math> יחס מלא אזי מתקיים <math>(b,a)\in R</math>
כיוןן ש <math>R\subseteq S</math> נובע כי <math>(b,a)\in 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>A=\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>m\in A</math> איבר קטן ביותר, אם קיים.
#מצאו איברים מינמאלים ב <math>A\backslash\left\{ m\right\}</math> , אם קיימים.