תרגול 11 תשעז

חזרה לדף מערכי התרגול.

יחסי שקילות - תרגילים נוספים

תרגיל

תהא $B\subseteq A$ קבוצה ותת קבוצה. נגדיר יחס $\sim \subseteq P(A)\times P(A)$ ע"י $C\sim D\iff C\cap B=D\cap B$. הוכיחו:

א. זהו יחס שקילות.

ב. לכל $X\subseteq A$ קיימת $C\subseteq B$ כך ש $[X]_R=[C]_R$.

ג. אם $C,D\subseteq B$ שונות, אז $[C]\neq [D]$.

פיתרון

א. רפלקסיביות: כמובן ש- $\forall C\subseteq A:C\cap B=C\cap B$, ולכן $C\sim C$.

סימטריות: נניח $C\sim D$ אזי $C\cap B=D\cap B\iff D\cap B=C\cap B$, ולכן $D\sim C$.

טרנזיטיביות: נניח $C\sim D\land D\sim E$ אזי $C\cap B=D\cap B\land D\cap B=E\cap B$ ומטרנזיטיביות יחס השיוויון נקבל הדרוש.

ב. יהי $X\subseteq A$ נשים לב שמתקיים $(X\cap B)\cap B=X\cap B$ ולכן $[X]_R=[X\cap B]_R$, ובנוסף מתקיים $X\cap B\subseteq B$ ולכן נוכל לבחור $C=X\cap B$.

ג. תהיינה $C,D\subseteq B$ שונות. לכן קיים (בה"כ) $x\in C\smallsetminus D$ וכמובן $x\in B$, ולכן נקבל $x\in C\cap B\land x\notin D\cap B$ כלומר $C\cap B\neq D\cap B$ ולכן $[C]\neq [D]$.

שאלה ממבחן

א. תהי $A$ קבוצה לא ריקה ותהי $\{R_i\}_{i\in I}$ משפחה של יחסי שקילות על $A$. הוכיחו כי החיתוך הכללי $R=\cap_{i\in I}R_i$ הינו יחס שקילויות על $A$.

ב. נסמן $R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\}$. מהם $R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n$? מהן קבוצות המנה $\mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2$?

פתרון

א. רפלקסיביות: מאחר ו-$\forall a\in A\forall i\in I : (a,a)\in R_i$ נובע ש-$\forall a\in A: (a,a)\in R$.

סימטריות: נניח $(x,y)\in R$ לכן $\forall i\in I:(x,y)\in R_i$ ולכן נובע מסמטריות היחסים ש $\forall i\in I:(y,x)\in R_i$ ולכן $(y,x)\in R$.

טרנזיטיביות: נניח $(x,y),(y,z)\in \mathbb R$ אזי $\forall i\in I:(x,y),(y,z)\in R_i$, וכיון שהוא יחס שקילות אז נובע $\forall i\in I:(x,z)\in R_i$, ולפי הגדרת החיתוך הכללי נקבל $(x,z)\in R$

ב. $R_1$ הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.

$R_2$ הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.

$R$ הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן $R$ הינו אוסף הזוגות מהצורה $(q,q)$ עבור $q$ מספר שלם. (יחס השיוויון).

$\mathbb{Z}/R_1$ הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים.

$\mathbb{Z}/R_2$ מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח).

$\mathbb{Z}/R$ הינו אוסף כל הקבוצות המכילות איבר שלם בודד.