יחידה 4: יחסים

מושגי יסוד

זוג סדור

הגדרה: זוג סדור

זוג סדור (Ordered Pair) של שני עצמים \(a\) ו-\(b\) הוא עצם חדש המסומן \(\langle a, b \rangle\) המקיים:

\[\langle a, b \rangle = \langle c, d \rangle \iff (a = c) \land (b = d)\]

כלומר, שני זוגות סדורים שווים אם ורק אם הרכיב הראשון שווה לרכיב הראשון והרכיב השני שווה לרכיב השני.

הערה חשובה

בניגוד לקבוצות, בזוג סדור הסדר חשוב:

• \(\{a, b\} = \{b, a\}\) (קבוצות)
• \(\langle a, b \rangle \neq \langle b, a \rangle\) כאשר \(a \neq b\) (זוגות סדורים)

הגדרה פורמלית (קורצ'ובסקי)

באופן פורמלי, זוג סדור מוגדר כקבוצה:

\[\langle a, b \rangle = \{\{a\}, \{a, b\}\}\]

הגדרה זו מבטיחה את התכונה המהותית של שוויון זוגות סדורים.

מכפלה קרטזית

הגדרה: מכפלה קרטזית

המכפלה הקרטזית של שתי קבוצות \(A\) ו-\(B\) היא:

\[A \times B = \{\langle a, b \rangle \mid a \in A \land b \in B\}\]

כלומר, קבוצת כל הזוגות הסדורים שהרכיב הראשון שלהם מ-\(A\) והרכיב השני מ-\(B\).

דוגמאות

1. אם \(A = \{1, 2\}\) ו-\(B = \{x, y\}\), אז: $\(A \times B = \{\langle 1, x \rangle, \langle 1, y \rangle, \langle 2, x \rangle, \langle 2, y \rangle\}\)$

2. \(\mathbb{R} \times \mathbb{R} = \mathbb{R}^2\) - המישור הממשי (קבוצת כל הנקודות במישור)

3. \(A \times \emptyset = \emptyset\) לכל קבוצה \(A\)

משפט: עוצמת המכפלה הקרטזית

אם \(A\) ו-\(B\) קבוצות סופיות, אז:

\[|A \times B| = |A| \cdot |B|\]

n-יות סדורות

הגדרה: n-יה סדורה

n-יה סדורה (n-tuple) היא הכללה של זוג סדור ל-\(n\) רכיבים:

\[\langle a_1, a_2, \ldots, a_n \rangle\]

שני n-יות שוות אם ורק אם כל הרכיבים המתאימים שווים.

הגדרה: מכפלה קרטזית כללית

\[A_1 \times A_2 \times \cdots \times A_n = \{\langle a_1, \ldots, a_n \rangle \mid a_i \in A_i \text{ לכל } i\}\]

במיוחד, \(A^n = \underbrace{A \times A \times \cdots \times A}_{n \text{ פעמים}}\)

---

יחסים בינאריים

הגדרת יחס

הגדרה: יחס בינארי

יחס בינארי \(R\) מקבוצה \(A\) לקבוצה \(B\) הוא תת-קבוצה של המכפלה הקרטזית:

\[R \subseteq A \times B\]

כלומר, יחס הוא קבוצה של זוגות סדורים.

אם \(\langle a, b \rangle \in R\), אומרים ש-\(a\) ביחס \(R\) עם \(b\), ומסמנים גם \(aRb\).

הגדרה: יחס על קבוצה

יחס מ-\(A\) ל-\(A\) נקרא יחס על \(A\):

\[R \subseteq A \times A = A^2\]

דוגמאות ליחסים

1. יחס הסדר \(<\) על \(\mathbb{R}\): $\(<\; = \{\langle a, b \rangle \in \mathbb{R}^2 \mid a < b\}\)$

2. יחס ההתחלקות \(|\) על \(\mathbb{N}\): $\(|\; = \{\langle a, b \rangle \in \mathbb{N}^2 \mid \exists k \in \mathbb{N}. b = k \cdot a\}\)$

3. יחס החפיפה בין משולשים: \(R = \{\langle T_1, T_2 \rangle \mid T_1 \text{ חופף ל-} T_2\}\)

4. יחס ההרשמה בין סטודנטים לקורסים: $\(Reg = \{\langle s, c \rangle \mid s \text{ רשום לקורס } c\}\)$

יחס הזהות

הגדרה: יחס הזהות

יחס הזהות על קבוצה \(A\) הוא:

\[I_A = \{\langle a, a \rangle \mid a \in A\}\]

זהו היחס שבו כל איבר ביחס עם עצמו בלבד.

---

פעולות על יחסים

היחס ההפוך

הגדרה: יחס הפוך

אם \(R\) יחס מ-\(A\) ל-\(B\), אז היחס ההפוך \(R^{-1}\) הוא יחס מ-\(B\) ל-\(A\) המוגדר:

\[R^{-1} = \{\langle b, a \rangle \mid \langle a, b \rangle \in R\}\]

דוגמאות

1. \((>)^{-1} = \;<\) (ההפוך של "גדול מ-" הוא "קטן מ-")

2. היחס ההפוך ל"הורה של" הוא "ילד של":

3. \(x\) הורה של \(y\) \(\iff\) \(y\) ילד של \(x\)

משפט

לכל יחס \(R\): \((R^{-1})^{-1} = R\)

הרכבת יחסים

הגדרה: הרכבת יחסים

אם \(S\) יחס מ-\(A\) ל-\(B\) ו-\(R\) יחס מ-\(B\) ל-\(C\), אז ההרכבה \(R \circ S\) היא יחס מ-\(A\) ל-\(C\) המוגדר:

\[R \circ S = \{\langle a, c \rangle \mid \exists b \in B. \langle a, b \rangle \in S \land \langle b, c \rangle \in R\}\]

במילים: \(a\) ביחס \(R \circ S\) עם \(c\) אם קיים \(b\) כך ש-\(a\) ביחס \(S\) עם \(b\) ו-\(b\) ביחס \(R\) עם \(c\).

דוגמאות

1. הרכבת יחס "הורה של" עם עצמו נותנת את יחס "סבא/סבתא של"

2. הרכבת "הורה של" עם "אח/אחות של" נותנת "דוד/דודה של"

משפטים על הרכבת יחסים

יהיו \(R, S, T\) יחסים מתאימים. אז:

1. אסוציאטיביות: \((R \circ S) \circ T = R \circ (S \circ T)\)

2. היפוך הרכבה: \((R \circ S)^{-1} = S^{-1} \circ R^{-1}\)

3. יחס הזהות: \(R \circ I_A = R = I_B \circ R\) עבור \(R \subseteq A \times B\)

שימו לב

הרכבת יחסים אינה קומוטטיבית בדרך כלל: $\(R \circ S \neq S \circ R\)$

---

תכונות של יחסים

יהי \(R\) יחס על קבוצה \(A\) (כלומר \(R \subseteq A \times A\)).

רפלקסיביות

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

יחס \(R\) על \(A\) נקרא רפלקסיבי אם:

\[\forall x \in A. \; xRx\]

כלומר, כל איבר ביחס עם עצמו.

שקול: \(I_A \subseteq R\)

הגדרה: יחס אי-רפלקסיבי

יחס \(R\) על \(A\) נקרא אי-רפלקסיבי (או אנטי-רפלקסיבי) אם:

\[\forall x \in A. \; \neg(xRx)\]

כלומר, אף איבר אינו ביחס עם עצמו.

דוגמאות

• רפלקסיביים: \(=\), \(\leq\), \(\geq\), \(\subseteq\), יחס דמיון, יחס חפיפה
• אי-רפלקסיביים: \(<\), \(>\), \(\subsetneq\), יחס "הורה של"

שימו לב

יחס יכול להיות לא רפלקסיבי מבלי להיות אי-רפלקסיבי!

לדוגמה: \(S = \{\langle 1, 1 \rangle, \langle 2, 3 \rangle\}\) על \(\{1, 2, 3\}\)

• לא רפלקסיבי (כי \(\langle 2, 2 \rangle \notin S\))
• לא אי-רפלקסיבי (כי \(\langle 1, 1 \rangle \in S\))

סימטריות

הגדרה: יחס סימטרי

יחס \(R\) על \(A\) נקרא סימטרי אם:

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

שקול: \(R^{-1} = R\)

הגדרה: יחס אנטי-סימטרי

יחס \(R\) על \(A\) נקרא אנטי-סימטרי אם:

\[\forall x, y \in A. \; (xRy \land yRx) \Rightarrow x = y\]

כלומר, אם שני איברים שונים ביחס, אז רק לכיוון אחד.

הגדרה: יחס אנטי-סימטרי חזק

יחס \(R\) על \(A\) נקרא אנטי-סימטרי במובן החזק אם:

\[\forall x, y \in A. \; xRy \Rightarrow \neg(yRx)\]

דוגמאות

• סימטריים: \(=\), יחס דמיון, יחס חפיפה, "שכן של"
• אנטי-סימטריים: \(\leq\), \(\geq\), \(\subseteq\), יחס התחלקות
• אנטי-סימטריים חזקים: \(<\), \(>\), \(\subsetneq\), יחס "הורה של"

טרנזיטיביות

הגדרה: יחס טרנזיטיבי

יחס \(R\) על \(A\) נקרא טרנזיטיבי אם:

\[\forall x, y, z \in A. \; (xRy \land yRz) \Rightarrow xRz\]

שקול: \(R \circ R \subseteq R\)

דוגמאות

• טרנזיטיביים: \(<\), \(\leq\), \(=\), \(\subseteq\), יחס התחלקות, יחס "צאצא של"
• לא טרנזיטיביים: יחס "הורה של", יחס "אוהב את", \(\neq\)

אזהרה

כשאומרים שיחס אינו טרנזיטיבי, הכוונה היא שקיימים \(x, y, z\) כך ש-\(xRy\) ו-\(yRz\) אבל לא \(xRz\).

זה לא אומר שתמיד כש-\(xRy\) ו-\(yRz\) אז לא מתקיים \(xRz\).

---

טבלת סיכום: תכונות יחסים

תכונה	הגדרה	דוגמאות (כן)	דוגמאות (לא)
רפלקסיבי	\(\forall x. xRx\)	\(=\), \(\leq\), \(\subseteq\)	\(<\), \(\neq\)
אי-רפלקסיבי	\(\forall x. \neg(xRx)\)	\(<\), \(>\), \(\subsetneq\)	\(=\), \(\leq\)
סימטרי	\(xRy \Rightarrow yRx\)	\(=\), דמיון	\(<\), \(\leq\)
אנטי-סימטרי	\((xRy \land yRx) \Rightarrow x=y\)	\(\leq\), \(\subseteq\)	דמיון (אם לא שוויון)
טרנזיטיבי	\((xRy \land yRz) \Rightarrow xRz\)	\(<\), \(=\), \(\subseteq\)	"הורה של"

---

טעויות נפוצות

טעות 1: בלבול בין קבוצה לזוג סדור

• \(\{a, b\} = \{b, a\}\) - קבוצות שוות
• \(\langle a, b \rangle \neq \langle b, a \rangle\) (אם \(a \neq b\)) - זוגות סדורים שונים

הסדר חשוב בזוגות סדורים!

טעות 2: בלבול בין סימטרי לאנטי-סימטרי

• סימטרי: אם \(xRy\) אז גם \(yRx\)
• אנטי-סימטרי: אם \(xRy\) וגם \(yRx\) אז \(x = y\)

יחס יכול להיות גם סימטרי וגם אנטי-סימטרי! (למשל: \(=\) על קבוצה כלשהי)

טעות 3: הרכבת יחסים - סדר הפעולה

בהרכבה \(R \circ S\):

• קודם מפעילים את \(S\)
• אחר כך מפעילים את \(R\)

זה הפוך מסדר הכתיבה!

טעות 4: רפלקסיביות תלויה בקבוצה

יחס יכול להיות רפלקסיבי ביחס לקבוצה אחת ולא רפלקסיבי ביחס לאחרת.

לדוגמה: \(\{\langle 1, 1 \rangle\}\) רפלקסיבי על \(\{1\}\) אבל לא על \(\{1, 2\}\).

---

מקורות

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

• ספר הקורס (פרופ' אברון): פרק ב.5 - יחסים
• תרגול 4 - יחסים
• דף נוסחאות מורחב