לדלג לתוכן

יחידה 8: יחסי שקילות ומחלקות

יחסי שקילות

הגדרה

הגדרה: יחס שקילות

יחס \(E\) על קבוצה \(A\) נקרא יחס שקילות (equivalence relation) אם הוא מקיים:

  1. רפלקסיביות: \(\forall x \in A. \; xEx\)
  2. סימטריות: \(\forall x, y \in A. \; xEy \Rightarrow yEx\)
  3. טרנזיטיביות: \(\forall x, y, z \in A. \; (xEy \land yEz) \Rightarrow xEz\)

דוגמאות ליחסי שקילות

  1. שוויון \(=\) על כל קבוצה

  2. דמיון משולשים על קבוצת המשולשים

  3. חפיפת משולשים על קבוצת המשולשים

  4. שקילות מודולו \(n\): $\(a \equiv b \pmod{n} \iff n \mid (a - b)\)$

לדוגמה: \(5 \equiv 11 \pmod{3}\) כי \(3 \mid (11 - 5) = 6\)

  1. יחס "באותו צבע" על קבוצת כדורים צבעוניים

מחלקות שקילות

הגדרה

הגדרה: מחלקת שקילות

יהי \(E\) יחס שקילות על \(A\). עבור \(x \in A\), מחלקת השקילות של \(x\) לפי \(E\) היא:

\[[x]_E = \{y \in A \mid xEy\}\]

כלומר, קבוצת כל האיברים השקולים ל-\(x\).

סימונים נפוצים

  • \([x]_E\) או \([x]\) (כשהיחס ברור מההקשר)
  • \(\overline{x}\)
  • \(x/E\)

דוגמה: מחלקות מודולו 3

יחס השקילות מודולו 3 על \(\mathbb{Z}\):

  • \([0]_{\equiv_3} = \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\} = 3\mathbb{Z}\)
  • \([1]_{\equiv_3} = \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\} = 3\mathbb{Z} + 1\)
  • \([2]_{\equiv_3} = \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\} = 3\mathbb{Z} + 2\)

שלוש מחלקות זרות שמכסות את כל \(\mathbb{Z}\).

תכונות מחלקות שקילות

משפט: תכונות מחלקות שקילות

יהי \(E\) יחס שקילות על \(A\). לכל \(x, y \in A\):

  1. כל איבר שייך למחלקה שלו: \(x \in [x]_E\) (מרפלקסיביות)

  2. שקילות היא שייכות למחלקה: \(y \in [x]_E \iff xEy\)

  3. סימטריות: \(y \in [x]_E \iff x \in [y]_E\)

  4. מחלקות שוות או זרות: $\([x]_E \cap [y]_E \neq \emptyset \iff [x]_E = [y]_E \iff xEy\)$

הוכחה (4): נראה \([x]_E \cap [y]_E \neq \emptyset \Rightarrow [x]_E = [y]_E\):

יהי \(z \in [x]_E \cap [y]_E\). אז \(xEz\) וגם \(yEz\).

מסימטריות: \(zEy\).

מטרנזיטיביות: \(xEy\).

יהי \(w \in [x]_E\). אז \(xEw\). מסימטריות \(yEx\), ומטרנזיטיביות \(yEw\), לכן \(w \in [y]_E\).

באותו אופן \([y]_E \subseteq [x]_E\). ∎

קבוצת מנה

הגדרה

הגדרה: קבוצת מנה

יהי \(E\) יחס שקילות על \(A\). קבוצת המנה (quotient set) של \(A\) לפי \(E\) היא:

\[A/E = \{[x]_E \mid x \in A\}\]

כלומר, קבוצת כל מחלקות השקילות.

דוגמאות לקבוצות מנה

  1. \(\mathbb{Z}/\equiv_2 = \{[0], [1]\}\) -- שתי מחלקות (זוגיים ואי-זוגיים)

  2. \(\mathbb{Z}/\equiv_3 = \{[0], [1], [2]\}\) -- שלוש מחלקות

  3. \(\mathbb{R}/\equiv\) כאשר \(x \equiv y \iff |x| = |y|\): קבוצת המנה היא למעשה \(\mathbb{R}_{\geq 0}\)

הפונקציה הקנונית

הגדרה: הפונקציה הקנונית

יהי \(E\) יחס שקילות על \(A\). הפונקציה הקנונית (או פונקציית המנה) היא:

\[\pi: A \to A/E, \quad \pi(x) = [x]_E\]

תכונות הפונקציה הקנונית

  1. \(\pi\) היא על (surjective)
  2. \(\pi(x) = \pi(y) \iff xEy\)
  3. \(\text{Im}(\pi) = A/E\)

שגיאות נפוצות

שגיאה 1: בלבול בין מחלקה לאיבר

  • \([a]\) היא קבוצה (מחלקת השקילות)
  • \(a\) הוא איבר (נציג של המחלקה)

שגיאה 2: שכחת לבדוק את שלושת התנאים

יחס שקילות חייב לקיים את שלושת התנאים: רפלקסיביות, סימטריה, טרנזיטיביות.

תרגילים

תרגיל 1

הוכיחו שהיחס \(R\) על \(\mathbb{Z}\) המוגדר ע"י \(xRy \iff x - y\) זוגי הוא יחס שקילות. מהן מחלקות השקילות?

תרגיל 2

יהי \(f: A \to B\) פונקציה. הגדירו על \(A\) את היחס: \(xEy \iff f(x) = f(y)\). הוכיחו ש-\(E\) יחס שקילות ותארו את מחלקות השקילות.

מקורות

מקורות היחידה

  • ספר הקורס: פרק ב.5 - יחסי שקילות
  • תרגול 8 - יחסי שקילות, מחלקות