שיעור פתרון

מבחן תשפ"א ב', מועד א', שאלה 5 - יחס שקילות באמצעות איחוד וחלוקה

שיעורי תאוריה רלוונטיים

יחסי שקילות ומחלקות שקילות

נוסח השאלה

תהי A≠∅ ותהי B⊆A. נגדיר יחס R על P(A) כך:

(X,Y)∈R ⇔ X∪B=Y∪B

הוכיחו כי R הוא יחס שקילות על P(A).
חשבו את מחלקות השקילות של R כאשר B=∅. נמקו.
חשבו את מחלקות השקילות של R כאשר B=A. נמקו.

כתבו את איברי יחס השקילות S המוגדר על ידי החלוקה {{1,2,3},{4},{5,6}} של C={1,2,3,4,5,6}.

זיהוי השיטה

בסעיף א שלוש תכונות השקילות נובעות מתכונות השוויון לאחר איחוד עם אותה קבוצה קבועה. במקרי הקצה בודקים מה האיחוד עושה לכל תת-קבוצה. בסעיף ב בונים לכל בלוק את המכפלה הקרטזית שלו עם עצמו ורק אז מאחדים.

פתרון מודרך

א1. הוכחת יחס שקילות

נוסח הסעיף: הוכיחו כי היחס (X,Y)∈R ⇔ X∪B=Y∪B הוא יחס שקילות על P(A).

רפלקסיביות

תהי X∈P(A) שרירותית. מתקיים X∪B=X∪B. לפי הגדרת היחס (X,X)∈R, ולכן היחס רפלקסיבי.

סימטריות

תהיינה X,Y∈P(A), ונניח (X,Y)∈R. לפי ההגדרה:

X∪B=Y∪B

שוויון קבוצות הוא סימטרי, ולכן Y∪B=X∪B. לפי הגדרת היחס (Y,X)∈R, והיחס סימטרי.

טרנזיטיביות

תהיינה X,Y,Z∈P(A), ונניח (X,Y)∈R וגם (Y,Z)∈R. פתיחת שתי ההנחות נותנת:

X∪B=Y∪B, Y∪B=Z∪B

מטרנזיטיביות השוויון מתקבל X∪B=Z∪B. לפי הגדרת היחס (X,Z)∈R, ולכן היחס טרנזיטיבי.

היחס רפלקסיבי, סימטרי וטרנזיטיבי, ולכן הוא יחס שקילות על P(A).

א2. מחלקות השקילות כאשר B=∅

נוסח הסעיף: חשבו את מחלקות השקילות של R כאשר B=∅.

נציב את הקבוצה הריקה בהגדרת היחס:

(X,Y)∈R ⇔ X∪∅=Y∪∅ ⇔ X=Y

לכן כל תת-קבוצה קשורה רק לעצמה. עבור כל X∈P(A) מתקבלת מחלקת יחידון:

[X]={X}

כלומר קבוצת המנה היא:

P(A)/R={{X} | X∈P(A)}

א3. מחלקות השקילות כאשר B=A

נוסח הסעיף: חשבו את מחלקות השקילות של R כאשר B=A.

לכל X⊆A מתקיים X∪A=A. לכן לכל X,Y∈P(A):

X∪A=A=Y∪A

כל שתי תתי-הקבוצות קשורות זו לזו, ולכן קיימת מחלקת שקילות אחת בלבד:

[X]=P(A) לכל X∈P(A), P(A)/R={P(A)}

ב. בניית היחס מן החלוקה

נוסח הסעיף: כתבו את איברי יחס השקילות S המוגדר על ידי החלוקה {{1,2,3},{4},{5,6}} של C={1,2,3,4,5,6}.

נסמן את הבלוקים B₁={1,2,3}, B₂={4}, B₃={5,6}. היחס מכיל זוג סדור בדיוק כאשר שני רכיביו באותו בלוק:

S=(B₁×B₁)∪(B₂×B₂)∪(B₃×B₃)

בבלוק הראשון, כאשר הרכיב הראשון הוא 1, הרכיב השני יכול להיות 1,2,3. חוזרים על אותה בחירה עבור רכיב ראשון 2 ועבור רכיב ראשון 3:

B₁×B₁={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

הבלוק היחידוני תורם רק זוג עצמי אחד:

B₂×B₂={(4,4)}

בבלוק השלישי כל אחד משני האיברים יכול להופיע בכל אחד משני הרכיבים:

B₃×B₃={(5,5),(5,6),(6,5),(6,6)}

אין זוגות בין בלוקים שונים. לאחר האיחוד:

S={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4),(5,5),(5,6),(6,5),(6,6)}

בדיקת ספירה: הבלוקים תורמים 3²+1²+2²=9+1+4=14 זוגות, בדיוק כמספר הזוגות ברשימה.

תשובה סופית

R הוא יחס שקילות על P(A).

אם B=∅, כל מחלקה היא {X}. אם B=A, קיימת מחלקה אחת: P(A).

S={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4),(5,5),(5,6),(6,5),(6,6)}.

המשך במבחן

מבחן תשפ"א ב', מועד א' · שאלה 5

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 6 - סדר החלוקה ופעולות בין יחסים