הבדלים בין גרסאות בדף "תרגול 10 תשעז"
שורה 1: | שורה 1: | ||
− | + | חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | |
+ | |||
+ | ==יחסי שקילות== | ||
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא | הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא | ||
#רפלקסיבי | #רפלקסיבי |
גרסה מ־17:38, 24 באוקטובר 2017
חזרה לדף מערכי התרגול.
יחסי שקילות
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
- רפלקסיבי
- סימטרי
- טרנזיטיבי
סימון מקובל:
אם R יחס שקילות מסמנים גם עבור
וכן נסמן את הקבוצה עם יחס השקילות
דוגמא נוספת:
נגדיר יחס שקילות R על ע"י
טענה: R אכן יחס שקילות
הוכחה:
1. רפלקסיביות - נניח לכן
2. סימטריות - נניח אזי ולכן גם
3. טרנזיטיביות - נניח אזי ולכן גם
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות כך ש:
- כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ()
הגדרה:
יהא R יחס שקילות על A אזי
- לכל מוגדרת מחלקת השקילות של x להיות
- קבוצת המנה מוגדרת
למשל, בדוגמא הראשונה הן מחלקות השקילות. קבוצת המנה היא
בדוגמא השניה מחלקת השקילות של 0 היא וקבוצת המנה היא (כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל מתקיים או (כלומר מחלקות השקילות זרות)
- כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה { יחס שקילות על A }
{חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.