88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 3: הבדלים בין גרסאות בדף
(←פתרון) |
|||
| (84 גרסאות ביניים של 8 משתמשים אינן מוצגות) | |||
| שורה 1: | שורה 1: | ||
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]''' | |||
==יחסי סדר== | ==יחסי סדר== | ||
'''הגדרה:''' יחס R על A נקרא '''אנטי-סימטרי''' אם מתקיים <math>\forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y)</math> | '''הגדרה:''' יחס R על A נקרא '''אנטי-סימטרי''' אם מתקיים <math>\forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y)</math> | ||
| שורה 9: | שורה 11: | ||
*היחס 'קטן-שווה' על המספרים | *היחס 'קטן-שווה' על המספרים | ||
*היחס 'מוכל-שווה' על הקבוצות | *היחס 'מוכל-שווה' על הקבוצות | ||
*היחס 'מחלק את ' על הטבעיים | |||
'''הגדרה.''' דיאגרמת הסה 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 יחס סדר חלקי על הקבוצה: | '''הגדרות.''' יהיו 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:(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 \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:(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) | *איבר <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>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי: | ||
| שורה 33: | שורה 52: | ||
*2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום. | *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 יחס סדר חלקי: | '''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי: | ||
| שורה 51: | שורה 93: | ||
*החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math> | *החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math> | ||
====דוגמא.==== | |||
נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של B הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון. | נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <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 הוא החסם העליון של הקבוצה. | נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. <math>B=\{1,1.4,1.41,1.414,1.4142,...\}</math>. חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה. | ||
שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון. | שימו לב, אם נביט בקבוצה 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 אינו רציונאלי. | הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי. | ||
תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי. | תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי. | ||
'''הוכחה.''' | '''הוכחה.''' | ||
נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-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> , אם קיימים. | |||
גרסה אחרונה מ־08:44, 28 בנובמבר 2022
יחסי סדר
הגדרה: יחס R על A נקרא אנטי-סימטרי אם מתקיים [math]\displaystyle{ \forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y) }[/math]
כלומר, אם [math]\displaystyle{ x\neq y }[/math] אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.
הגדרה: יחס R על A נקרא יחס סדר חלקי אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
דוגמאות ליחסי סדר חלקי:
- היחס 'קטן-שווה' על המספרים
- היחס 'מוכל-שווה' על הקבוצות
- היחס 'מחלק את ' על הטבעיים
הגדרה. דיאגרמת הסה Hasse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה [math]\displaystyle{ A=\{1,2,3\} }[/math].
הגדרה: יהי R יחס על A, אזי היחס ההופכי מוגדר להיות [math]\displaystyle{ R^{-1}=\{(y,x)|(x,y)\in R\} }[/math]
תרגיל
הוכח שאם R יחס סדר חלקי, גם ההופכי שלו יחס סדר חלקי
פתרון
- רפלקסיביות: לכל איבר a מתקיים [math]\displaystyle{ (a,a)\in R }[/math] ולכן [math]\displaystyle{ (a,a)\in R^{-1} }[/math]
- טרנזיטיביות: נניח [math]\displaystyle{ (x,y),(y,z)\in R^{-1} }[/math] לכן מתקיים [math]\displaystyle{ (y,x),(z,y)\in R }[/math] לכן לפי הטרנזיטיביות של R מתקיים [math]\displaystyle{ (z,x)\in R }[/math] ולכן [math]\displaystyle{ (x,z)\in R^{-1} }[/math].
- אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y.
איברים מיוחדים
הגדרות. יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:
- איבר [math]\displaystyle{ x\in A }[/math] נקרא מינמלי ביחס לR אם [math]\displaystyle{ \forall y\in A:(y,x)\in R \rightarrow y=x }[/math]. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
- איבר [math]\displaystyle{ x\in A }[/math] נקרא מקסימלי ביחס לR אם [math]\displaystyle{ \forall y\in A:(x,y)\in R \rightarrow y=x }[/math]. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
- איבר [math]\displaystyle{ x\in A }[/math] נקרא איבר קטן ביותר/מינימום ביחס לR אם [math]\displaystyle{ \forall y\in A:(x,y)\in R }[/math]. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)
- איבר [math]\displaystyle{ x\in A }[/math] נקרא איבר גדול ביותר/מקסימום ביחס לR אם [math]\displaystyle{ \forall y\in A:(y,x)\in R }[/math]. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)
מינוח/סימון: עבור קבוצה A נסמן לעיתים יחס סדר ב [math]\displaystyle{ \leq }[/math]. לא להתבלבל עם ה"קטן שווה" ה"רגיל"!. אם A קבוצה ו [math]\displaystyle{ leq }[/math] יחס סדר עליה, נסמן [math]\displaystyle{ (A,\leq) }[/math] ונקרא ל A קבוצה סדורה חלקית. עוד נאמר במקרה זה כי איבר x קטן שווה מאיבר y אם מתקיים [math]\displaystyle{ x\leq y }[/math]
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר מינימום הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי המקסימום.
הערה: מינימום [math]\displaystyle{ \leftarrow }[/math] מינימלי, וכן מקסימום [math]\displaystyle{ \leftarrow }[/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]
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
- 5,3,1 הינם איברים מינימליים שכן אין איבר שקטן מאף אחד מהם. הם אינם מינימום כי אף אחד מהם לא קטן מכל האיברים האחרים.
- 4 הינו מקסימום של הקבוצה, הוא בוודאי מקסימלי
- 2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.
תרגיל
תהא [math]\displaystyle{ (A,\leq) }[/math] קבוצה סדורה. הוכיחו/הפריכו: אם x מיני' יחיד אזי הוא איבר קטן ביותר
תרגיל
תהא [math]\displaystyle{ (A,\leq) }[/math] קבוצה סדורה. הוכיחו/הפריכו: אם x מינימאלי יחיד ו y מקסימאלי יחיד אזי [math]\displaystyle{ x\leq y }[/math]
תרגיל
תהא [math]\displaystyle{ (A,\leq) }[/math] קבוצה סדורה סופית לא ריקה. הוכיחו: קיים איבר מינימאלי.
פתרון
באינדוקציה על גודל הקבוצה [math]\displaystyle{ |A|=n }[/math]. עבור [math]\displaystyle{ n=1 }[/math] האיבר מינימאלי. נניח נכונות עבור [math]\displaystyle{ |A|=n-1 }[/math] ותהא [math]\displaystyle{ |A|=n }[/math]. קיים [math]\displaystyle{ a\in A }[/math], ונתבונן בקבוצה הסדורה [math]\displaystyle{ (A\smallsetminus \{a\},\leq ) }[/math], שם יש מינימאלי שנסמנו [math]\displaystyle{ b }[/math].
נחזור כעת ל-[math]\displaystyle{ A }[/math]. נחלק למקרים:
אם [math]\displaystyle{ a\not \leq b }[/math] אז [math]\displaystyle{ b }[/math] מינימאלי גם ב-[math]\displaystyle{ A }[/math]: יהי [math]\displaystyle{ y\in A }[/math], כך ש- [math]\displaystyle{ y\leq b }[/math], ונראה [math]\displaystyle{ y=b }[/math]: אכן, מההנחה נקבל [math]\displaystyle{ y\neq a }[/math], ולכן [math]\displaystyle{ y\in A\setminus \{a\} }[/math], ומכיון ש-b מינימלי שם נקבל [math]\displaystyle{ y=b }[/math].
אם [math]\displaystyle{ a\leq b }[/math] אז [math]\displaystyle{ a }[/math] מינימאלי ב-[math]\displaystyle{ A }[/math]. יהי [math]\displaystyle{ y\leq a }[/math], ונניח בשלילה [math]\displaystyle{ y\neq a }[/math]. לכן [math]\displaystyle{ y\in A\setminus \{a\} }[/math]. כעת מטרנזיטיבות נקבל [math]\displaystyle{ y\leq b }[/math], וממינימליות b נקבל [math]\displaystyle{ y=b }[/math]. בסה"כ יש לנו [math]\displaystyle{ a\leq b\land b\leq a }[/math], ומאנטי-סימטריות נקבל [math]\displaystyle{ a=b }[/math] בסתירה (כי [math]\displaystyle{ b\in A\setminus \{a\} }[/math]).
הגדרה
יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים [math]\displaystyle{ [(a,b)\in R]\or[(b,a)\in R] }[/math] אזי R נקרא יחס סדר קווי/לינארי.
תרגיל
יהא [math]\displaystyle{ (A,\leq) }[/math] קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר.
פתרון
יהא [math]\displaystyle{ y\in A }[/math] צ"ל: [math]\displaystyle{ x\leq y }[/math]: מהעובדה שהיחס לינארי נקבל [math]\displaystyle{ x\leq y\lor y\leq x }[/math]. נחלק למקרים:
1. אם [math]\displaystyle{ x\leq y }[/math] סיימנו.
2. אם [math]\displaystyle{ y\leq x }[/math] אז לפי הגדרת מינימליות (ונתון ש- [math]\displaystyle{ x }[/math] מינימלי) נקבל [math]\displaystyle{ x=y }[/math] ולכן [math]\displaystyle{ x\leq y }[/math] .
חסמים
הגדרות. יהיו 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]
דוגמא.
נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד [math]\displaystyle{ B=\{1,3,5\} }[/math]. קבוצת חסמי המלעיל של B הינה [math]\displaystyle{ \{2,4\} }[/math]. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
דוגמא
נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. [math]\displaystyle{ B=\{1,1.4,1.41,1.414,1.4142,...\} }[/math]. חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה.
שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון.
דוגמא (בהרצאה בד"כ)
נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה 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] אוסף תתי קבוצות של A. החסם העליון שלה ב [math]\displaystyle{ (P(A),\subseteq) }[/math] הוא [math]\displaystyle{ \cup _{i\in I} A_i }[/math] והחסם התחתון (אם זה אוסף לא ריק) שלהם הוא[math]\displaystyle{ \cap_{i\in I}A_i }[/math]
תרגיל
מצאו [math]\displaystyle{ X\subseteq P(\mathbb{N}) }[/math] כך שבקבוצה הסדורה [math]\displaystyle{ (X,\subseteq) }[/math] קיים B שאין לו חסם עליון.
תרגיל
עבור [math]\displaystyle{ X\subseteq P(\mathbb{N}) }[/math], נסתכל בקבוצה הסדורה [math]\displaystyle{ (X,\subseteq) }[/math] וב [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] אוסף תתי קבוצות של [math]\displaystyle{ \mathbb{N} }[/math].
הוכיחו/הפריכו: אם [math]\displaystyle{ \cup_{i\in I}A_i \not\in X }[/math] אזי ל [math]\displaystyle{ \{A_i\mid i\in I\} }[/math] אין חסם עליון.
יחס סדר מילוני
יהיו [math]\displaystyle{ (A,\leq),(B,\preceq) }[/math] שתי קבוצות סדורות חלקית.
על [math]\displaystyle{ A\times B }[/math] ניתן להגדיר את היחס המילוני [math]\displaystyle{ R }[/math] ע"י
[math]\displaystyle{ (a_1,b_1)R(a_2,b_2)\iff (a_1 \lt a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2) }[/math]
דוגמא
נסתכל על [math]\displaystyle{ \mathbb{N}\times \mathbb{N} }[/math] עם הסדר המילוני.
נגדיר [math]\displaystyle{ B = \{(1,x) | x\in \mathbb{N} \} }[/math] אזי [math]\displaystyle{ sup(B)=(2,1),inf(B)=(1,1) }[/math]
נגדיר [math]\displaystyle{ B = \{(x,1) | x\in \mathbb{N} \} }[/math] אזי [math]\displaystyle{ inf(B)=(1,1) }[/math] ו sup לא קיים.
- שימו לב ש [math]\displaystyle{ (1,1) }[/math] הוא איבר קטן ביותר
מכפלה של יחסי סדר
יהיו [math]\displaystyle{ (A,\leq),(B,\preceq) }[/math] שתי קבוצות סדורות חלקית.
על [math]\displaystyle{ A\times B }[/math] ניתן להגדיר את היחס [math]\displaystyle{ R }[/math] הבא:
[math]\displaystyle{ (a_1,b_1)R(a_2,b_2)\iff (a_1 \leq a_2) \land ( b_1 \preceq b_2) }[/math]
זהו יחס סדר:
הוכחה:
1. רפקלסיביות: לכל [math]\displaystyle{ a,b }[/math] מתקיים כי [math]\displaystyle{ a\leq a, b\preceq b }[/math] ולכן [math]\displaystyle{ (a,b)R(a,b) }[/math]
2. אנטי סימטריות: אם [math]\displaystyle{ (a,b)R(a1,b1) }[/math] וגם [math]\displaystyle{ (a1,b1)R(a,b) }[/math] אז [math]\displaystyle{ a\leq a1, b\preceq b1 }[/math] וגם [math]\displaystyle{ a1\leq a, b1 \preceq b }[/math], כיוון שאלו יחס סדר נקבל כי [math]\displaystyle{ a=a1,b=b1 }[/math]
3. טרנז' - תרגיל
דוגמה
נסתכל על [math]\displaystyle{ \mathbb{N}\times \mathbb{N} }[/math] אם הסדר המוגדר לעיל.
נגדיר [math]\displaystyle{ B = \{(1,x) | x\in \mathbb{N} \} }[/math] אזי [math]\displaystyle{ inf(B)=(1,1) }[/math] ו sup לא קיים
נגדיר [math]\displaystyle{ B = \{(x,1) | x\in \mathbb{N} \} }[/math] אזי [math]\displaystyle{ inf(B)=(1,1) }[/math] ו sup לא קיים.
- שימו לב ש [math]\displaystyle{ (1,1) }[/math] הוא איבר קטן ביותר.
תרגיל
נסתכל על [math]\displaystyle{ \mathbb{N}\times \mathbb{Z} }[/math] ותתי הקבוצות
- [math]\displaystyle{ B_1 = \{(4,-x) | x\in \mathbb{N} \} }[/math]
- [math]\displaystyle{ B_2 = \{(4,x) | x\in \mathbb{N} \} }[/math]
- [math]\displaystyle{ B_3 = \{(x,4) | x\in \mathbb{N} \} }[/math]
- מצאו, אם קיימים, sup ו inf לקבוצות [math]\displaystyle{ B_2,B_3 }[/math] כאשר [math]\displaystyle{ (\mathbb{N},\leq) }[/math] ו [math]\displaystyle{ (\mathbb{Z},\leq) }[/math] ו [math]\displaystyle{ \mathbb{N}\times \mathbb{Z} }[/math] עם יחס המכפלה
- מצאו, אם קיימים, sup ו inf לקבוצות [math]\displaystyle{ B_1,B_2 }[/math] כאשר [math]\displaystyle{ (\mathbb{N},|) }[/math] ו [math]\displaystyle{ (\mathbb{Z},\leq) }[/math] ו [math]\displaystyle{ \mathbb{N}\times \mathbb{Z} }[/math] עם היחס המילוני
תרגיל
נסתכל על [math]\displaystyle{ \mathbb{N}\times (0,1] }[/math] ותתי הקבוצה [math]\displaystyle{ B = \{(4,\frac{1}{n+1}) | n\in \mathbb{N} \} }[/math]
מצאו, אם קיימים, sup ו inf לקבוצות [math]\displaystyle{ B }[/math] כאשר [math]\displaystyle{ (\mathbb{N},|) }[/math] ו [math]\displaystyle{ (0,1],\leq) }[/math] ו [math]\displaystyle{ \mathbb{N}\times (0,1] }[/math] עם היחס המילוני
תרגיל
יהיו [math]\displaystyle{ (A,\leq),(B,\preceq) }[/math] שני יחסי סדר משווים
הוכיחו/הפריכו:
- יחס המכפלה על [math]\displaystyle{ A\times B }[/math] הוא משווה.
- היחס המילוני על [math]\displaystyle{ A\times B }[/math] הוא משווה.
תרגיל
- תנו דוגמה לקסח [math]\displaystyle{ \left(A,\leq\right) }[/math] לא סופי המקיים כי: [math]\displaystyle{ \left\{ B\subseteq A\mid\,\exists\inf B\right\} =\left\{ B\subseteq A\mid\,\exists\sup B\right\} }[/math] .
- תנו דוגמה לקסח [math]\displaystyle{ \left(A,\leq\right) }[/math] המקיים כי: [math]\displaystyle{ \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]\displaystyle{ (\frac{m_1}{n_1},\frac{m_2}{n_2}) }[/math] אם [math]\displaystyle{ (m_1\leq m_2)\and(n_1\leq n_2) }[/math]. הוכיחו/הפריכו: R הינו יחס סדר חלקי.
פתרון.
נבדוק את תכונות היחס:
- רפלקסיביות - ברור.
- אנטי-סימטריות - אם [math]\displaystyle{ (m_1\leq m_2)\and(n_1\leq n_2) }[/math] וגם [math]\displaystyle{ (m_1\geq m_2)\and(n_1\geq n_2) }[/math] אזי [math]\displaystyle{ (m_1= m_2)\and(n_1= n_2) }[/math] ולכן שני השברים המצומצמים שווים.
- טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד.
לכן R הינו יחס סדר חלקי.
שאלה: מה היה קורה אילו לא דרשנו שברים מצומצמים?
תרגיל (ממבחן קיץ תשעה מועד ב)
תהא [math]\displaystyle{ X }[/math] קבוצת כל הסדרות הבינאריות (סדרה בינארית היא [math]\displaystyle{ a_1a_2a_3\dots }[/math] כאשר [math]\displaystyle{ a_n\in \{0,1\} }[/math]). נגדיר יחס [math]\displaystyle{ R }[/math] על [math]\displaystyle{ X }[/math] כך: עבור [math]\displaystyle{ a=a_1a_2\dots ,b=b_1b_2\dots \in X }[/math]
[math]\displaystyle{ aRb \iff \; \forall n\; a_n-b_n \neq (-1)^n }[/math]
א. הוכיחו ש [math]\displaystyle{ R }[/math] יחס סדר על [math]\displaystyle{ X }[/math]
ב. קבעו האם [math]\displaystyle{ R }[/math] יחס סדר מלא על [math]\displaystyle{ X }[/math]
ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב [math]\displaystyle{ X }[/math] (ביחס ל [math]\displaystyle{ R }[/math])
פתרון
דרך שקולה לתאר את היחס שמפשטת את השאלה היא כך
[math]\displaystyle{ 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]\displaystyle{ a=000\dots, b=111\dots }[/math] לא מתייחסים זה לזה.
ג. קימיים, [math]\displaystyle{ M=010101\dots }[/math] הינו איבר הגדול ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ aRM }[/math]
[math]\displaystyle{ m=101010\dots }[/math] הינו איבר קטן ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ mRa }[/math]
תרגיל (מבוחן תשעג)
יהא [math]\displaystyle{ A }[/math] קבוצה. נגדיר [math]\displaystyle{ O }[/math] להיות קבוצת כל יחסי הסדר החלקיים על [math]\displaystyle{ A }[/math], סדורה ע"י הכלה. (כלומר הזוג [math]\displaystyle{ (O,\subseteq) }[/math] - במילים אחרות, חושבים על [math]\displaystyle{ O }[/math] עם יחס הסדר החלקי "הכלה")
1. יהא [math]\displaystyle{ R\subseteq A\times A }[/math] יחס סדר על [math]\displaystyle{ A }[/math] הוכיחו: אם[math]\displaystyle{ R\subseteq A\times A }[/math] יחס סדר משווה עליה. אז [math]\displaystyle{ R }[/math] איבר מקסימלי ב [math]\displaystyle{ O }[/math]
2.הוכיח: אם ב [math]\displaystyle{ A }[/math] לפחות 2 איברים אז ב [math]\displaystyle{ (O,\subseteq) }[/math] אין איברים גדול ביותר
3. הוכיחו/הפריכו: לכל קבוצה לא ריקה [math]\displaystyle{ B\subseteq\mathbb{O} }[/math] קיים [math]\displaystyle{ \inf }[/math]
4. הוכיחו/הפריכו: לכל קבוצה לא ריקה [math]\displaystyle{ B\subseteq\mathbb{O} }[/math] קיים [math]\displaystyle{ \sup }[/math]
פתרון
יהא [math]\displaystyle{ R\subseteq A\times A }[/math] יחס סדר על [math]\displaystyle{ A }[/math] ונניח כי הוא משווה. נוכיח כי הוא איבר מקסמאלית ב [math]\displaystyle{ O }[/math]. יהי [math]\displaystyle{ S\in O }[/math] יחס סדר חלקי על [math]\displaystyle{ A }[/math] המקיים [math]\displaystyle{ R\subseteq S }[/math] צ"ל [math]\displaystyle{ R=S }[/math]
נניח בשלילה כי [math]\displaystyle{ R }[/math] מוכל ממש ב [math]\displaystyle{ S }[/math]
אזי קיים [math]\displaystyle{ (a,b)\in S\land(a,b)\notin R }[/math]. כיוון ש [math]\displaystyle{ R }[/math] יחס מלא אזי מתקיים [math]\displaystyle{ (b,a)\in R }[/math] כיוןן ש [math]\displaystyle{ R\subseteq S }[/math] נובע כי [math]\displaystyle{ (b,a)\in S }[/math]
מכיוון ש [math]\displaystyle{ S }[/math] יחס סדר חלקי (בפרט אנטי סימטרי) אזי [math]\displaystyle{ a=b }[/math] (כי גם ([math]\displaystyle{ a,b)\in S }[/math]) אזי קיבלנו כי ּ[math]\displaystyle{ (a,a)=(a,b)\notin R }[/math] סתירה לכך ש [math]\displaystyle{ R }[/math] יחס סדר מלא ובפרט רפלקסיבי.
תרגיל
נגדיר [math]\displaystyle{ X=\left\{ 1,2,3,\dots,10\right\} }[/math] . עוד נגדיר [math]\displaystyle{ \mathbb{O} }[/math] להיות קבוצת כל יחסי השקילות על [math]\displaystyle{ X }[/math].נגדיר יחס [math]\displaystyle{ \preceq }[/math] מעל [math]\displaystyle{ \mathbb{O} }[/math] על ידי הכלל [math]\displaystyle{ R_{1}\preceq R_{2}\iff\left(\left|X/R_{1}\right|\lt \left|X/R_{1}\right|\right)\lor\left(R_{1}=R_{2}\right) }[/math] כאשר [math]\displaystyle{ \left|X/R_{1}\right| }[/math] פירושו מספר האיברים בקבוצת המנה של היחס [math]\displaystyle{ R_{1} }[/math].
1. הוכיחו: כי [math]\displaystyle{ \preceq }[/math] הוא יחס סדר על [math]\displaystyle{ \mathbb{O} }[/math].
2. הוכיחו/הפריכו: זהו יחס סדר קווי
3. מצאו, אם קיימים, איבר קטן ביותר ב[math]\displaystyle{ \left(\mathbb{O},\preceq\right) }[/math] ואיבר גדול ביותר ב [math]\displaystyle{ \left(\mathbb{O},\preceq\right) }[/math]
תרגיל
תהא [math]\displaystyle{ 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]\displaystyle{ \leq }[/math] על A כך [math]\displaystyle{ \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]\displaystyle{ m\in A }[/math] איבר קטן ביותר, אם קיים.
- מצאו איברים מינמאלים ב [math]\displaystyle{ A\backslash\left\{ m\right\} }[/math] , אם קיימים.