שאלת מבחן במתמטיקה בדידה - האוניברסיטה הפתוחה 2022 - יחסים

על הקבוצה $A = \{\langle a,b\rangle \mid a,b \in \{1,2,4\}\}$ מגדירים שני יחסים $R,S$ כך: לכל $\langle a_1,b_1\rangle, \langle a_2,b_2\rangle \in A$, $\langle a_1,b_1\rangle R \langle a_2,b_2\rangle$ אם ורק אם $a_1 b_2 = a_2 b_1$ ו- $\langle a_1,b_1\rangle S \langle a_2,b_2\rangle$ אם ורק אם $a_1 b_2 < a_2 b_1$. א. (13 נק') הראו ש- $R$ הוא יחס שקילות ורשמו באופן מפורט את מחלקות השקילות שלו. ב. (14 נק') הראו ש- $S$ הוא יחס סדר. קבעו אם הוא סדר חלקי או מלא ומיצאו בו את כל האיברים המינימליים והמקסימליים.

רמז: התנאי להמצאות ביחס $R$ או $S$ יכול להיכתב כתנאי על היחס בין $a_1/b_1$ ו-$a_2/b_2$. מחלקות השקילות של $R$ מאגדות זוגות עם אותו יחס, בעוד ש-$S$ מסדר את הזוגות לפי יחס זה.

פתרון: א. ראשית, נוכיח ש-$R$ הוא **יחס שקילות** על ידי הוכחת שלוש תכונות: רפלקסיביות, סימטריות וטרנזיטיביות. 1. **רפלקסיביות**: יהי $\langle a,b \rangle \in A$. צ"ל $\langle a,b \rangle R \langle a,b \rangle$. לפי הגדרת $R$, זה מתקיים אם ורק אם $a \cdot b = a \cdot b$, וזהו פסוק אמת. לכן $R$ רפלקסיבי. 2. **סימטריות**: נניח $\langle a_1,b_1 \rangle R \langle a_2,b_2 \rangle$. צ"ל $\langle a_2,b_2 \rangle R \langle a_1,b_1 \rangle$. מההנחה נובע $a_1 b_2 = a_2 b_1$. מכללי האריתמטיקה, שוויון זה גורר $a_2 b_1 = a_1 b_2$. לפי הגדרת $R$, זה בדיוק אומר ש- $\langle a_2,b_2 \rangle R \langle a_1,b_1 \rangle$. לכן $R$ סימטרי. 3. **טרנזיטיביות**: נניח $\langle a_1,b_1 \rangle R \langle a_2,b_2 \rangle$ וגם $\langle a_2,b_2 \rangle R \langle a_3,b_3 \rangle$. צ"ל $\langle a_1,b_1 \rangle R \langle a_3,b_3 \rangle$. מההנחות נובע: (1) $a_1 b_2 = a_2 b_1$ (2) $a_2 b_3 = a_3 b_2$ נכפול את משוואה (1) ב-$b_3$ ואת משוואה (2) ב-$b_1$ (מותר כי $b_i \in \{1,2,4\}$ ולכן אינם 0): $a_1 b_2 b_3 = a_2 b_1 b_3$ $a_2 b_3 b_1 = a_3 b_2 b_1$ מהשוויון השני נציב בראשון: $a_1 b_2 b_3 = a_3 b_2 b_1$. מכיוון ש-$b_2 \neq 0$, ניתן לחלק בו ולקבל $a_1 b_3 = a_3 b_1$. לפי הגדרת $R$, זה אומר ש- $\langle a_1,b_1 \rangle R \langle a_3,b_3 \rangle$. לכן $R$ טרנזיטיבי. מאחר ש-$R$ רפלקסיבי, סימטרי וטרנזיטיבי, הוא **יחס שקילות**. $\blacksquare$ כעת, נמצא את **מחלקות השקילות**. התנאי $\langle a_1,b_1 \rangle R \langle a_2,b_2 \rangle$ שקול ל-$\frac{a_1}{b_1} = \frac{a_2}{b_2}$ (כי $b_i \neq 0$). כלומר, כל מחלקת שקילות מכילה את כל הזוגות עם אותו יחס $a/b$. נחשב את היחסים האפשריים: * יחס $1/4$: $\langle 1,4 \rangle$. מחלקת השקילות: $[\langle 1,4 \rangle]_R = \{\langle 1,4 \rangle\}$. * יחס $1/2$: $\langle 1,2 \rangle, \langle 2,4 \rangle$. מחלקת השקילות: $[\langle 1,2 \rangle]_R = \{\langle 1,2 \rangle, \langle 2,4 \rangle\}$. * יחס $1$: $\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 4,4 \rangle$. מחלקת השקילות: $[\langle 1,1 \rangle]_R = \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 4,4 \rangle\}$. * יחס $2$: $\langle 2,1 \rangle, \langle 4,2 \rangle$. מחלקת השקילות: $[\langle 2,1 \rangle]_R = \{\langle 2,1 \rangle, \langle 4,2 \rangle\}$. * יחס $4$: $\langle 4,1 \rangle$. מחלקת השקילות: $[\langle 4,1 \rangle]_R = \{\langle 4,1 \rangle\}$. ב. נוכיח ש-$S$ הוא **יחס סדר** על ידי הוכחת התכונות הנדרשות. היחס מוגדר ע"י אי-שוויון חזק ($<$), ולכן נבדוק אנטי-רפלקסיביות, אנטי-סימטריות וטרנזיטיביות. 1. **אנטי-רפלקסיביות**: יהי $\langle a,b \rangle \in A$. היחס $\langle a,b \rangle S \langle a,b \rangle$ מתקיים אם ורק אם $a \cdot b < a \cdot b$, וזהו פסוק שקר. לכן היחס אנטי-רפלקסיבי. 2. **אנטי-סימטריות**: נניח $\langle a_1,b_1 \rangle S \langle a_2,b_2 \rangle$ וגם $\langle a_2,b_2 \rangle S \langle a_1,b_1 \rangle$. מההנחה נובע $a_1 b_2 < a_2 b_1$ וגם $a_2 b_1 < a_1 b_2$. זו סתירה עבור מספרים ממשיים, ולכן ההנחה אינה יכולה להתקיים. באופן ריק, התנאי לאנטי-סימטריות מתקיים. 3. **טרנזיטיביות**: נניח $\langle a_1,b_1 \rangle S \langle a_2,b_2 \rangle$ וגם $\langle a_2,b_2 \rangle S \langle a_3,b_3 \rangle$. מההנחות נובע: (1) $a_1 b_2 < a_2 b_1$ (2) $a_2 b_3 < a_3 b_2$ מכיוון שכל האיברים $a_i, b_i$ חיוביים, נוכל לכתוב את אי-השוויונות כיחסים: $\frac{a_1}{b_1} < \frac{a_2}{b_2}$ ו- $\frac{a_2}{b_2} < \frac{a_3}{b_3}$. מטרנזיטיביות של יחס הקטן במספרים הרציונליים, נקבל $\frac{a_1}{b_1} < \frac{a_3}{b_3}$. נכפיל את שני האגפים ב-$b_1 b_3$ (שהוא חיובי) ונקבל $a_1 b_3 < a_3 b_1$. זה בדיוק אומר ש- $\langle a_1,b_1 \rangle S \langle a_3,b_3 \rangle$. לכן $S$ טרנזיטיבי. מאחר שהיחס אנטי-רפלקסיבי, אנטי-סימטרי וטרנזיטיבי, הוא **יחס סדר חלקי חזק**. $\blacksquare$ כעת נקבע אם הסדר הוא **חלקי** או **מלא**. סדר מלא דורש שכל שני איברים שונים בקבוצה יהיו ניתנים להשוואה. ניקח שני איברים שונים הנמצאים באותה מחלקת שקילות של $R$, למשל $x = \langle 1,1 \rangle$ ו-$y = \langle 2,2 \rangle$. עבורם, $a_1 b_2 = 1 \cdot 2 = 2$ ו-$a_2 b_1 = 2 \cdot 1 = 2$. מכיוון ש-$a_1 b_2 = a_2 b_1$, לא מתקיים $x S y$ וגם לא מתקיים $y S x$. מצאנו זוג איברים שונים שאינם ניתנים להשוואה, ולכן הסדר הוא **סדר חלקי** (ולא מלא). לבסוף, נמצא את האיברים המינימליים והמקסימליים. * **איבר מינימלי**: איבר $m$ הוא מינימלי אם אין איבר $x$ כך ש-$x S m$. כלומר, אין $x$ כך ש-$\frac{a_x}{b_x} < \frac{a_m}{b_m}$. זה אומר ש-$m$ הוא איבר שהיחס $a/b$ שלו הוא הקטן ביותר. היחס הקטן ביותר שמצאנו הוא $1/4$. האיבר היחיד עם יחס זה הוא $\langle 1,4 \rangle$. לכן, **האיבר המינימלי היחיד הוא $\langle 1,4 \rangle$**. * **איבר מקסימלי**: איבר $M$ הוא מקסימלי אם אין איבר $x$ כך ש-$M S x$. כלומר, אין $x$ כך ש-$\frac{a_M}{b_M} < \frac{a_x}{b_x}$. זה אומר ש-$M$ הוא איבר שהיחס $a/b$ שלו הוא הגדול ביותר. היחס הגדול ביותר שמצאנו הוא $4$. האיבר היחיד עם יחס זה הוא $\langle 4,1 \rangle$. לכן, **האיבר המקסימלי היחיד הוא $\langle 4,1 \rangle$**.