הבדלים בין גרסאות בדף "תרגול 10 תשעז"

מתוך Math-Wiki

קפיצה אל: ניווט, חיפוש

גרסה מ־08:54, 20 ביוני 2017

יחסי שקילות

הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא

רפלקסיבי
סימטרי
טרנזיטיבי

סימון מקובל:

אם R יחס שקילות מסמנים גם $x \sim y$ עבור $(x,y)\in R$

וכן נסמן $(A,\sim)$ את הקבוצה עם יחס השקילות

דוגמא נוספת:

נגדיר יחס שקילות R על $\mathbb{Z}$ ע"י $3|(x-y) \Leftrightarrow xRy$

טענה: R אכן יחס שקילות

הוכחה:

1. רפלקסיביות - נניח $\forall x\in \mathbb{Z}:3|0=x-x$ לכן $xRx$

2. סימטריות - נניח $(x,y)\in R$ אזי $3|(x-y)$ ולכן גם $3|(y-x)=-(x-y)$

3. טרנזיטיביות - נניח $[(x,y)\in R] \and [(y,z)\in R]$ אזי $3|(x-y)\and 3|(y-z)$ ולכן גם $3|(z-x)=(z-y)+(y-x)$

הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות $\{A_i\}_{i\in I}$ כך ש:

$\forall i\in I: A_i \neq \emptyset$
$\cup _{i\in I} A_i =A$ כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
הקבוצות $A_i$ הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ( $\forall i\not= j\in I : A_i\cap A_j = \phi$ )

הגדרה:

יהא R יחס שקילות על A אזי

לכל $x\in A$ מוגדרת מחלקת השקילות של x להיות $\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\}$
קבוצת המנה מוגדרת $A/R := \{ [x]_R | x\in A\}$

למשל, בדוגמא הראשונה $A_1,A_2,A_3$ הן מחלקות השקילות. קבוצת המנה היא $A/R=\{A_1,A_2,A_3\}$

בדוגמא השניה מחלקת השקילות של 0 היא $[0]_R=\{ 0 \pm 3 \pm 6 \dots \}$ וקבוצת המנה היא $\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}$ (כלומר כל השאריות האפשריות בחלוקה ב-3).

משפט: יהא R יחס שקילות על A אזי

לכל $x,y\in A$ מתקיים $[x]=[y]$ או $[x]\cap [y] =\phi$ (כלומר מחלקות השקילות זרות)
$A=\bigcup_{[x]\in A/R}[x]$ כלומר (איחוד מחלקות השקילות תתן את כל A)

הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A

מסקנה: תהא A קבוצה אזי יש התאמה { $R$ יחס שקילות על A } $\leftrightarrow$ {חלוקות של A}

חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.

מקור: https://math-wiki.com/index.php?title=תרגול_10_תשעז&oldid=71889