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