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

גרסה מ־11:14, 17 בינואר 2017

הערה: עבור $A$ קבוצה ויחס סדר חלקי $\leq$ עליה. נסמן $(A,\leq )$ t את הקבוצה עם היחס

הגדרות. יהיו 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)$

דוגמאות

דוגמא עבור $\{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 יקרה יחס שקילות אם הוא

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

סימון מקובל:

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

דוגמא נוספת:

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

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

@@ שורה 1: / שורה 1: @@
+'''הערה:'''
+עבור <math>A</math> קבוצה ויחס סדר חלקי <math>\leq</math> עליה. נסמן <math>(A,\leq )</math> t את הקבוצה עם היחס
 '''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
 *חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math>
@@ שורה 6: / שורה 10: @@
 === דוגמאות ===
-'''דוגמא.'''
-נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).
-למשל <math>sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1</math>
 '''דוגמא'''
@@ שורה 40: / שורה 39: @@
 אם R יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(x,y)\in R</math>
-דוגמא: תהא <math>A=\{1,2,3,4,5,6\}</math>. נגדיר תת הקבוצות <math>A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}</math>
-נגדיר יחס R על A כך <math>\exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy</math>
-טענה R יחס שקילות
-הוכחה:
-. רפלקסיביות - נניח <math>x\in A</math> לכן x שייך ל <math>A_i</math> עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן <math>(x,x)\in R</math>.
-. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>x,y\in A_i</math> עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם <math>(y,x)\in R</math>.
-. טרנזיטיביות - נניח <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> כפי שרצינו.
-הגדרה: תהא 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>)
-כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).
 דוגמא נוספת:
@@ שורה 80: / שורה 55: @@
 ולכן גם <math>3|(z-x)=(z-y)+(y-x)</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>)
 הגדרה:

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

גרסה מ־11:14, 17 בינואר 2017

דוגמאות

יחסי שקילות

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים