הבדלים בין גרסאות בדף "תרגול 11 תשעז"
(←פתרון) |
(←שאלה ממבחן) |
||
שורה 32: | שורה 32: | ||
===שאלה ממבחן=== | ===שאלה ממבחן=== | ||
− | + | תהי A קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על A. | |
− | + | ||
− | + | ||
====פתרון==== | ====פתרון==== | ||
− | + | רפלקסיביות: מאחר ו <math>\forall a\in A\forall i\in I : (a,a)\in R_i</math> נובע ש <math>\forall a\in A: (a,a)\in R</math>. | |
− | + | ||
סימטריות: נניח <math>(x,y)\in R</math> לכן <math>\forall i\in I:(x,y)\in R_i</math> ולכן נובע מסמטריות היחסים ש <math>\forall i\in I:(y,x)\in R_i</math> ולכן <math>(y,x)\in R</math>. | סימטריות: נניח <math>(x,y)\in R</math> לכן <math>\forall i\in I:(x,y)\in R_i</math> ולכן נובע מסמטריות היחסים ש <math>\forall i\in I:(y,x)\in R_i</math> ולכן <math>(y,x)\in R</math>. | ||
+ | טרנזיטיביות: נניח <math>(x,y),(y,z)\in \mathbb R</math> אזי <math>\forall i\in I:(x,y),(y,z)\in R_i</math>, וכיון שהוא יחס שקילות אז נובע <math>\forall i\in I:(x,z)\in R_i</math>, ולפי הגדרת החיתוך הכללי נקבל <math>(x,z)\in R</math> | ||
− | + | ===תרגיל=== | |
− | + | תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <math>~subseteq P(A)\times P(A)</math> ע"י <math>C~D\iff C\cup B=D\cup B</math>. הוכח שזהו יחס שקילות. | |
− | + | ||
− | + | ||
− | + | ||
− | <math> | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | <math>\ | + | |
− | <math> | + | ====פיתרון==== |
+ | רפלקסיביות: כמובן ש- <math></math> |
גרסה מ־09:59, 22 בינואר 2017
תוכן עניינים
המשך יחסי שקילות
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות כך ש:
- כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ()
הגדרה:
יהא R יחס שקילות על A אזי
- לכל מוגדרת מחלקת השקילות של x להיות
- קבוצת המנה מוגדרת
למשל בדוגמא משבוע שעבר על השלמים עם היחס , מחלקת השקילות של 0 היא וקבוצת המנה היא
(כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל מתקיים או (כלומר מחלקות השקילות זרות)
- כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה { יחס שקילות על A }
{חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
שאלה ממבחן
תהי A קבוצה לא ריקה ותהי משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי הינו יחס שקילויות על A.
פתרון
רפלקסיביות: מאחר ו נובע ש .
סימטריות: נניח לכן ולכן נובע מסמטריות היחסים ש ולכן .
טרנזיטיביות: נניח אזי , וכיון שהוא יחס שקילות אז נובע , ולפי הגדרת החיתוך הכללי נקבל
תרגיל
תהא קבוצה ותת קבוצה. נגדיר יחס ע"י . הוכח שזהו יחס שקילות.
פיתרון
רפלקסיביות: כמובן ש-