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

גרסה מ־10:20, 17 בינואר 2017

הגדרות. יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:

חסם מלעיל של B הוא איבר $x\in A$ כך שמתקיים $\forall y\in B:(y,x)\in R$
חסם מלרע של B הוא איבר $x\in A$ כך שמתקיים $\forall y\in B:(x,y)\in R$
החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן $sup(B)$
החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן $inf(B)$

דוגמאות

דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).

למשל $sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1$

דוגמא עבור $\{A_i\}_{i\in I}$ אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא $\cup _{i\in I} A_i$

דוגמא.

נביט בקבוצה $A=\{1,2,3,4,5\}$ ונגדיר עליה יחס סדר חלקי:

$R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)\}$

(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)

נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד $B=\{1,3,5\}$ . קבוצת חסמי המלעיל של B הינה $\{2,4\}$ . המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.

הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים $[(a,b)\in R]\or[(b,a)\in R]$ אזי R נקרא יחס סדר מלא.

למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.

יחסי שקילות

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

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

דוגמא: תהא $A=\{1,2,3,4,5,6\}$ . נגדיר תת הקבוצות $A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}$

נגדיר יחס R על A כך $\exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy$

טענה R יחס שקילות

הוכחה:

1. רפלקסיביות - נניח $x\in A$ לכן x שייך ל $A_i$ עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן $(x,x)\in R$ .

2. סימטריות - נניח $(x,y)\in R$ אזי $x,y\in A_i$ עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם $(y,x)\in R$ .

3. טרנזיטיביות - נניח $[(x,y)\in R] \and [(y,z)\in R]$ אזי קיימים i,j כך ש $x,y\in Aֹ_i$ וגם $y,z\in A_j$ . לכן $y\in A_i\cap A_j$ . מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש $A_i=A_j$ ולכן $x,y,z\in A_i$ ולכן $(x,z)\in R$ כפי שרצינו.

הגדרה: תהא 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$ )

כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).

דוגמא נוספת:

נגדיר יחס שקילות 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)$

הגדרה:

יהא 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}

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

@@ שורה 28: / שורה 28: @@
 '''הגדרה.''' יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר מלא'''.
-=== תרגיל (ממבחן קיץ תשעה מועד ב) ===
+למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא.
-תהא <math>X</math> קבוצת כל הסדרות הבינאריות (סדרה בינארית היא <math>a_1a_2a_3\dots</math> כאשר <math>a_n\in \{0,1\}</math>). נגדיר יחס <math>R</math> על <math>X</math> כך:
+שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.
-עבור <math>a=a_1a_2\dots ,b=b_1b_2\dots \in X</math>
-<math>aRb \iff \; \forall n\; a_n-b_n \neq (-1)^n</math>
+===יחסי שקילות===
+הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
+#רפלקסיבי
+#סימטרי
+#טרנזיטיבי
-א. הוכיחו ש <math>R</math> יחס סדר על <math>X</math>
+דוגמא: תהא <math>A=\{1,2,3,4,5,6\}</math>. נגדיר תת הקבוצות <math>A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}</math>
-ב. קבעו האם <math>R</math> יחס סדר '''מלא''' על <math>X</math>
+נגדיר יחס R על A כך <math>\exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy</math>
-ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב <math>X</math> (ביחס ל <math>R</math>)
+טענה R יחס שקילות
-==== פתרון ====
+הוכחה:
-דרך שקולה לתאר את היחס שמפשטת את השאלה היא כך
-<math>aRb \iff \big( \forall k \; a_{2k}=1 \Rightarrow b_{2k}=1, \; a_{2k-1}=0\Rightarrow b_{2k-1}=0\big)</math>
+. רפלקסיביות - נניח <math>x\in A</math> לכן x שייך ל <math>A_i</math> עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן <math>(x,x)\in R</math>.
-כלומר במיקומים הזוגיים, אם a שווה 1 אז זה גורר ש b שווה 1
+. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>x,y\in A_i</math> עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם <math>(y,x)\in R</math>.
-ובמיקומים האי זוגיים, אם a שווה 0 אז זה גורר ש b שווה 0
+. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי קיימים i,j כך ש <math>x,y\in Aֹ_i</math> וגם <math>y,z\in A_j</math>. לכן <math>y\in A_i\cap A_j</math>. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש<math>A_i=A_j</math> ולכן <math>x,y,z\in A_i</math> ולכן <math>(x,z)\in R</math> כפי שרצינו.
-א. תרגיל לבד!
-ב. לא סדר מלא, למשל <math>a=000\dots, b=111\dots </math> לא מתייחסים זה לזה.
+הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</math>
+כך ש:
+* <math>\forall i\in I: A_i \neq \emptyset </math>
+* <math>\cup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
+* הקבוצות <math>A_i</math> הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
-ג. קימיים, <math>M=010101\dots</math> הינו איבר הגדול ביותר כי לכל <math>a</math> מתקים <math>aRM</math>
+כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).
-<math>m=101010\dots</math> הינו איבר קטן ביותר כי לכל <math>a</math> מתקים <math>mRa</math>
+דוגמא נוספת:
+נגדיר יחס שקילות R על <math>\mathbb{Z}</math> ע"י  <math>3|(x-y) \Leftrightarrow xRy</math>
+טענה: R אכן יחס שקילות
+הוכחה:
+. רפלקסיביות - נניח <math>\forall x\in \mathbb{Z}:3|0=x-x</math> לכן <math>xRx</math>
+. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>3|(x-y)</math> ולכן גם <math>3|(y-x)=-(x-y)</math>
+. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי <math>3|(x-y)\and 3|(y-z) </math>
+ולכן גם <math>3|(z-x)=(z-y)+(y-x)</math>
+הגדרה:
+יהא R יחס שקילות על A  אזי
+# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
+# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>
+למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=\{A_1,A_2,A_3\}</math>
+בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
+<math>\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+משפט: יהא R יחס שקילות על A אזי
+# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\phi </math> (כלומר מחלקות השקילות זרות)
+# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
+הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
+מסקנה:
+תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A }
+<math>\leftrightarrow</math> {חלוקות של A}
+חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.

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

גרסה מ־10:20, 17 בינואר 2017

דוגמאות

יחסי שקילות

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים