תרגול 8 תשעז
חזרה לדף מערכי התרגול.
תוכן עניינים
יחסים
המכפלה הקרטזית
הגדרה: המכפלה הקרטזית של שתי קבוצות ו-
הינה אוסף כל הזוגות הסדורים -
. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים
והאיבר הבא הינו זוג חוקי
.
ניתן להכליל את ההגדרה לעיל ל--יה סדורה - כלומר
איברים מסודרים.
דוגמה: ו-
אזי מתקיים
למתכנתים: זה מאוד דומה ללולאות for מקוננות.
תרגיל
הוכח שלכל קבוצות מתקיים
פתרון
יחסים כתת קבוצה של הזוגות הסדורים
הגדרה: יהיו קבוצות,
אזי
יקרא יחס (בין
לבין
).
הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי
ל-
.
דוגמה: ונביט בתת הקבוצה
הבאה:
. מה מיוחד בזוגות אלה?
זוגות אלה הינם כל זוגות האיברים כך ש-
. (כלומר הגדרנו את היחס המייצג "קטן שווה").
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה היא יחס. גם
היא יחס, וגם
הוא יחס.
סימון: אם זוג מסוים,נניח , נמצא בקבוצת היחס
נהוג לסמן
, או
. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט
).
דוגמה: נביט בקבוצת האנשים . נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים
כך ש-
אם"ם
הוא בן של
. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
הגדרה: בהינתן יחס , היחס ההפוך
הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
הגדרה: תהי קבוצה . יחס הזהות על
הוא
כך ש-
.
הגדרה: יהיו קבוצות, ו-
יחס הכפל הוא היחס:
.
תרגיל
יהיו . נגדיר את היחס:
. בדוק האם:
א.
ב.
תכונות של יחסים על קבוצה
הגדרה: יחס על קבוצה
פירושו
.
תהי קבוצה ויחס
עליה אזי:
נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים
).
נקרא סימטרי אם
גורר שגם
(מתקיים
).
נקרא טרנזיטיבי אם יחס בין ראשון לשני (
), ויחס בין השני לשלישי (
) גורר יחס בין הראשון לשלישי (
). (מתקיים
).
נקרא אנטי סימטרי (חלש) אם
וגם
גורר כי
(מתקיים
ובאופן שקול:
)
דוגמאות:
- יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
- יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
- יחס 'שיוויון מודולו
' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
- יחס '
מחלק את
' הינו רפלקסיבי וטרנזיטיבי
- יחס 'אדם
שמע על אדם
' הינו רפלקסיבי
הערה: יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: ואז
גם וגם, ואילו
לא ולא.