לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
תרגול 9 תשעז
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
==יחסי סדר== '''הגדרה:''' יחס <math>R</math> על קבוצה <math>A</math> נקרא '''יחס סדר חלקי''' אם <math>R</math> רפלקסיבי, טרנזיטיבי ואנטי-סימטרי. דוגמאות ליחסי סדר חלקי: *היחס 'קטן-שווה' על המספרים השלמים *היחס 'מוכל-שווה' על קבוצת החזקה <math>P(\{4,5,100\})</math> *היחס 'מחלק את' על הטבעיים '''הערה:''' עבור <math>A</math> קבוצה ויחס סדר חלקי <math>\leq</math> עליה, נסמן <math>(A,\leq )</math> את הקבוצה עם היחס. '''הגדרה:''' דיאגרמת הסה (או תרשים הסה, Hasse diagram) הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר <math>x</math> מחובר בקשת לאיבר <math>y</math> מתחתיו 'גדול' ממנו ביחס (כלומר <math>x>y</math>), ובינם אין עוד איברים (כלומר אין <math>z</math> כך ש-<math>x>z>y</math>). נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>. '''הגדרות:''' יהיו <math>A</math> קבוצה ו-<math>R</math> יחס סדר חלקי על הקבוצה: *איבר <math>x\in A</math> נקרא '''מינימלי''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(y,x)\in R \rightarrow y=x</math>. כלומר, אין איבר 'קטן' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו. *איבר <math>x\in A</math> נקרא '''מקסימלי''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(x,y)\in R \rightarrow y=x</math>. כלומר, אין איבר 'גדול' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו. *איבר <math>x\in A</math> נקרא '''קטן ביותר''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(x,y)\in R</math>. כלומר, <math>x</math> 'קטן' מכל האיברים. <math>x</math> חייב להיות ביחס עם כל האיברים בקבוצה. למשל, הקבוצה הריקה תחת יחס הכלה. *איבר <math>x\in A</math> נקרא '''גדול ביותר''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(y,x)\in R</math>. כלומר, <math>x</math> 'גדול' מכל האיברים. <math>x</math> חייב להיות ביחס עם כל האיברים בקבוצה. למשל, הקבוצה <math>B</math> תחת יחס ההכלה על קבוצת החזקה של <math>B</math>. הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר גם לגבי איבר גדול ביותר. הערה: קטן ביותר גורר מינימלי, וכן גדול ביותר גורר מקסימלי. אבל לא להיפך! צייר את דיאגרמת הסה של היחס "מחלק את" על הקבוצה <math>A=\{1,2,...,10\}</math> מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר? צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר? ===תרגיל=== תהא <math>A</math> קבוצה. מצא את הקבוצה <math>\{ R\subseteq A\times A:R\text{ is an order relation} \land \forall a\in A, a \text{ is maximal } \}</math> ====פתרון==== נראה שיש רק יחס אחד כזה, והוא הזהות. יחס הזהות אכן מקיים את התנאי. נניח ש-<math>R</math> יחס סדר המקיים את התנאי ונראה ש-<math>R=I_A</math>: כיוון ראשון: כל יחס סדר <math>R</math> מקיים <math>I_A\subseteq R</math>. כיוון שני: יהי <math>(a,b) \in R</math>, אזי כיון ש-<math>a</math> מקסימלי נובע <math>b=a</math> ולכן <math>(a,b)=(a,a) \in I_A</math> כדרוש. ===תרגיל=== הוכח שאם <math>R</math> יחס סדר חלקי, אז גם היחס ההופכי שלו <math>R^{-1}</math> יחס סדר חלקי. ====פתרון==== *רפלקסיביות: לכל איבר <math>a</math> מתקיים <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>. *אנטי-סימטריות: אם <math>x</math> ביחס ל-<math>y</math> וגם <math>y</math> ביחס ל-<math>x</math> הדבר נכון באופן זהה ל-<math>R</math> וליחס ההופכי שלו (כי 'וגם' חילופי), ולכן <math>x=y</math>. '''הגדרה:''' יהי <math>R</math> יחס סדר חלקי על <math>A</math>. אם לכל שני איברים <math>a,b\in A</math> מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי <math>R</math> נקרא '''יחס סדר מלא'''. '''דוגמה''': היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמה ליחס סדר בלי איברים מינימליים או מקסימליים. ====דוגמא ליחס סדר מעניין==== היחס המילוני. ====תרגיל==== הוכיחו שאם <math>R</math> יחס סדר מלא על <math>A</math>, ו- <math>a\in A</math> איבר מינימלי יחיד אז הוא גם קטן ביותר.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)