יחידה 9: חלוקה, אי תלות בנציג, יחסי סדר¶

פירוק (חלוקה)¶

הגדרה¶

הגדרה: פירוק של קבוצה

פירוק (partition) של קבוצה $A$ הוא קבוצה $\mathcal{F}$ של תתי-קבוצות של $A$ המקיימת:

לא ריקות: $\forall X \in \mathcal{F}. \; X \neq \emptyset$
כיסוי: $\bigcup \mathcal{F} = A$
זרות הדדית: $\forall X, Y \in \mathcal{F}. \; X \neq Y \Rightarrow X \cap Y = \emptyset$

דוגמאות לפירוקים

$\{\{1, 3, 5\}, \{2, 4, 7, 8\}, \{6\}\}$ הוא פירוק של $\{1, 2, 3, 4, 5, 6, 7, 8\}$
$\{\mathbb{Z}^-, \{0\}, \mathbb{Z}^+\}$ הוא פירוק של $\mathbb{Z}$
$\{[0], [1], [2]\}$ הוא פירוק של $\mathbb{Z}$ לפי $\equiv_3$

הקשר בין יחסי שקילות לפירוקים¶

משפט: קבוצת מנה היא פירוק

יהי $E$ יחס שקילות על $A$. אז $A/E$ הוא פירוק של $A$.

הוכחה: 1. לא ריקות: לכל $x \in A$, $x \in [x]_E$ (מרפלקסיביות), לכן $[x]_E \neq \emptyset$ 2. כיסוי: לכל $x \in A$, $x \in [x]_E \in A/E$, לכן $\bigcup A/E = A$ 3. זרות: מחלקות שונות זרות (הוכחנו קודם)

משפט: ההתאמה בין יחסי שקילות לפירוקים

קיימת התאמה חח"ע ועל בין יחסי השקילות על $A$ לבין הפירוקים של $A$:

מיחס לפירוק: $E \mapsto A/E$
מפירוק ליחס: $\mathcal{F} \mapsto E_\mathcal{F}$ כאשר $xE_\mathcal{F}y \iff$ קיים $X \in \mathcal{F}$ כך ש-$x, y \in X$

אי-תלות בנציג¶

הבעיה¶

בעיית הנציג

כשמגדירים פעולה או פונקציה על קבוצת המנה, לעתים ההגדרה תלויה בבחירת נציג מכל מחלקה.

צריך להוכיח שהתוצאה לא תלויה בבחירת הנציג.

דוגמה: חיבור על $\mathbb{Z}_n$¶

דוגמה: חיבור על $\mathbb{Z}_n$

נגדיר חיבור על $\mathbb{Z}/\equiv_n$: $$[a] + [b] = [a + b]$$

צריך להוכיח: אם $[a] = [a']$ ו-$[b] = [b']$, אז $[a + b] = [a' + b']$.

הוכחה: - $[a] = [a']$ $\Rightarrow$ $n \mid (a - a')$ - $[b] = [b']$ $\Rightarrow$ $n \mid (b - b')$ - לכן $n \mid ((a + b) - (a' + b')) = (a - a') + (b - b')$ - לכן $[a + b] = [a' + b']$ ✓

מבנה ההוכחה¶

מבנה הוכחת אי-תלות בנציג

נניח $[a] = [a']$ ו-$[b] = [b']$
נתרגם להגדרת היחס: $aEa'$ ו-$bEb'$
נראה ש-$(a \star b) E (a' \star b')$
נסיק $[a \star b] = [a' \star b']$

יחסי סדר¶

יחס סדר חלקי¶

הגדרה: יחס סדר חלקי

יחס $R$ על קבוצה $A$ נקרא יחס סדר חלקי (partial order) אם הוא מקיים:

רפלקסיביות: $\forall x \in A. \; xRx$
אנטי-סימטריות: $(xRy \land yRx) \Rightarrow x = y$
טרנזיטיביות: $(xRy \land yRz) \Rightarrow xRz$

מסמנים לעתים $\leq$ או $\preceq$ ליחס סדר חלקי.

סימון

הזוג $(A, \leq)$ נקרא קבוצה סדורה חלקית (poset - partially ordered set).

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

$\leq$ על $\mathbb{R}$
$\subseteq$ על $\mathcal{P}(A)$ (יחס ההכלה)
יחס ההתחלקות $\mid$ על $\mathbb{N}^+$: $a \mid b \iff \exists k \in \mathbb{N}. b = ak$

יחס סדר מלא¶

הגדרה: יחס סדר מלא

יחס סדר חלקי $R$ על $A$ נקרא יחס סדר מלא (total/linear order) אם בנוסף הוא קשר:

\[\forall x, y \in A. \; xRy \lor yRx\]

כלומר, כל שני איברים ניתנים להשוואה.

דוגמאות

$\leq$ על $\mathbb{R}$ - יחס סדר מלא
$\subseteq$ על $\mathcal{P}(A)$ - יחס סדר חלקי (לא מלא):
$\{1\} \not\subseteq \{2\}$ וגם $\{2\} \not\subseteq \{1\}$

איברים מיוחדים¶

הגדרות: איברים מיוחדים

יהי $(A, \leq)$ קבוצה סדורה חלקית. עבור $a \in A$:

מינימלי: אין איבר קטן ממנו ממש - $\neg \exists x \in A. x < a$
מקסימלי: אין איבר גדול ממנו ממש - $\neg \exists x \in A. a < x$
מינימום (הקטן ביותר): $\forall x \in A. a \leq x$
מקסימום (הגדול ביותר): $\forall x \in A. x \leq a$

הבדל חשוב: מינימלי vs מינימום

מינימום: אם קיים, הוא יחיד
מינימלי: יכולים להיות כמה, או אף אחד
בסדר מלא: מינימלי = מינימום

חסמים¶

הגדרות: חסמים

יהי $(A, \leq)$ קבוצה סדורה ו-$B \subseteq A$:

חסם עליון של $B$: איבר $a \in A$ כך ש-$\forall b \in B. b \leq a$
חסם תחתון של $B$: איבר $a \in A$ כך ש-$\forall b \in B. a \leq b$
סופרמום: החסם העליון הקטן ביותר - $\sup(B)$
אינפימום: החסם התחתון הגדול ביותר - $\inf(B)$

טבלת סיכום: שקילות vs סדר¶

תכונה	יחס שקילות	יחס סדר חלקי
רפלקסיבי	✓	✓
סימטרי	✓	✗
אנטי-סימטרי	✗	✓
טרנזיטיבי	✓	✓

תרגילים¶

תרגיל 1

הוכיחו שהכפל על $\mathbb{Z}_n$ מוגדר היטב (אי-תלות בנציג).

תרגיל 2

ציירו את דיאגרמת האסה של $(\mathcal{P}(\{a, b, c\}), \subseteq)$.

תרגיל 3

מצאו את כל האיברים המינימליים והמקסימליים של $(\mathcal{P}(\{1,2,3\}) \setminus \{\emptyset\}, \subseteq)$.

מקורות¶

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

ספר הקורס: פרקים ב.5, ב.6 - יחסי שקילות וסדר
תרגול 9 - חלוקה, אי תלות בנציג, יחסי סדר