תרגול 9 תשעז
מתוך Math-Wiki
תרגיל
יהיו . נגדיר את היחס:
. בדוק האם:
א.
ב.
תרגיל
תהיינה קבוצות,
. הוכח או הפרך:
א. .
ב.
פיתרון:
א. הכיוון בוודאי נכון. אבל הכיוון השני לא מתקיים. דוגמא נגדית: ניקח:
ונקבל: אבל כמובן
.
ב. הוכחה: יהי אזי לפי הגדרה קיים
כך ש-
. כעת, כיון ש-
נובע ש-
, ולכן לפי הגדרת ההרכבה נקבל
.
תכונות של יחסים על קבוצה
הגדרה: יחס R על קבוצה A פירושו
תהי קבוצה A ויחס R עליה אזי
- R נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים
)
- R נקרא סימטרי אם aRb גורר שגם bRa (מתקיים
)
- R נקרא טרנזיטיבי אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים
)
- R נקרא אנטי סימטרי (חלש) אם aRb וגם bRa גורר כי a=b (מתקיים
ובאופן שקול:
)
דוגמאות:
- יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
- יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
- יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
- יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
- יחס 'אדם x שמע על אדם y' הינו רפלקסיבי
הערה: יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמא: ואז R גם וגם, S לא ולא.