4.
נתון יחס ההעדפה:
x עדיף מ- או שקול ל- y
אם ורק אם
x1 + x2 + 1 ≥ y1 + y2
4.1
האם הוא מקיים שלמות וטרנזיטיביות?
4.2
מצא את היחס מעדיף (ממש) מ- ואת יחס השקילות (אדישות). האם היחסים האלה מקיימים טרנזיטיביות?
4.1 פיתרון:
טענה: היחס מקיים שלמות
הוכחה:
יהיו a ו-b סלי מצרכים.
צריך להראות ש-a לא פחות טוב מ-b או ש-b לא פחות טוב מ-a.
ישנם שני מקרים:
מקרה א
a1 + a2 + 1 ≥ b1 + b2
מקרה ב:
a1 + a2 + 1 < b1 + b2
אם הסלים a ו-b שייכים למקרה א, אזי נובע ישירות מההגדרה ש a לא פחות טוב מ-b.
אם הסלים אינם שייכים למקרה א, אזי הם שייכים למקרה ב. במקרה זה נקבל:
a1 + a2 < a1 + a2 + 1 < b1 + b2 < b1 + b2 + 1
כלומר b איננו פחות טוב מ-a.
היחס איננו מקיים טרנזיטיביות. דוגמא נגדית היא:
a = (2,1), b = (2,2), c = (2,3)
ניתן לראות כי a לא פחות טוב מ-b, b לא פחות טוב מ-c, אבל c איננו לא פחות טוב מ-a.
4.2 פיתרון:
היחס "עדיף מ" מוגדר כך:
x עדיף מ-y
אם:
1 x עדיף מ- או שקול ל- y
2 ולא מתקיים:
y עדיף מ- או שקול ל- x
מתנאי 1 נקבל
x1 + x2 + 1 ≥ y1 + y2
מתנאי 2 נקבל
y1 + y2 + 1 < x1 + x2
נסדר מחדש את שני התנאים, ונקבל:
x1 + x2 ≥ y1 + y2 - 1
x1 + x2 > y1 + y2 + 1
התנאי השני כולל את הראשון, ולכן
x עדיף מ-y אם ורק אם
x1 + x2 > y1 + y2 + 1
היחס "עדיף מ-" הינו טרנזיטיבי. (לא כתבתי את ההוכחה)
היחס "שקול" מוגדר כך: x שקול ל-y אם:מתנאי 1 נקבל
x1 + x2 + 1 ≥ y1 + y2
מתנאי 2 נקבל
y1 + y2 + 1 ≥ x1 + x2
נסדר מחדש את שני התנאים, ונקבל:
y1 + y2 + 1 ≥ x1 + x2 ≥ y1 + y2 - 1
היחס "שקול ל-" איננו טרנזיטיבי. הדוגמא הנגדית לטרנזיטיביות בסעיף 4.1 תקפה גם כאן.
5.
נתון יחס ההעדפה:
x עדיף מ- או שקול ל- y
אם ורק אם
x1 + x2 - 1 ≥ y1 + y2
5.1
האם הוא מקיים שלמות וטרנזיטיביות?
5.2
מצא את היחס מעדיף (ממש) מ- ואת יחס השקילות (אדישות). האם היחסים האלה מקיימים טרנזיטיביות?
5.1 פיתרון:
טענה: היחס איננו מקיים שלמות. דוגמא נגדית היא שלכל סל a, הסל איננו ניתן להשוואה עם עצמו.
היחס מקיים טרנזיטיביות. (לא כתבתי את ההוכחה).
5.2 פיתרון:
היחס "עדיף מ" מוגדר כך:
x עדיף מ-y
אם:
1 x עדיף מ- או שקול ל- y
2 ולא מתקיים:
y עדיף מ- או שקול ל- x
מתנאי 1 נקבל
x1 + x2 - 1 ≥ y1 + y2
מתנאי 2 נקבל
y1 + y2 - 1 < x1 + x2
נסדר מחדש את שני התנאים, ונקבל:
x1 + x2 ≥ y1 + y2 + 1
x1 + x2 > y1 + y2 - 1
התנאי הראשון כולל את השני, ולכן
x עדיף מ-y אם ורק אם x עדיף מ- או שקול ל-y
היחס "עדיף מ-" הינו טרנזיטיבי. זאת מפני שהוא זהה ליחס "עדיף מ- או שקול ל-".
היחס "שקול" מוגדר כך: x שקול ל-y אם:מהבדיקה בקשר ליחס "עדיף מ-" התברר שלא ייתכן ששני סלים יהיו שקולים זה לזה, כלומר שהיחס "שקול ל-" הוא ריק.
היחס "שקול ל-" הינו טרנזיטיבי, מפני שהוא ריק.