תרגול 5 מדמח קיץ תשעז

חזרה למערכי התרגול

יחסי סדר

הגדרה: יחס R על A נקרא אנטי-סימטרי אם מתקיים $\forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y)$

כלומר, אם $x\neq y$ אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.

הגדרה: יחס R על A נקרא יחס סדר חלקי אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי

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

• היחס 'קטן-שווה' על המספרים
• היחס 'מוכל-שווה' על הקבוצות
• היחס 'מחלק את ' על הטבעיים

נוכיח ש"מחלק את" על הטבעיים הינו יחס סדר חלקי:

רפלקסיבי: כל מספר מחלק את עצמו.

טרנזיטיבי: אם $a|b\land b|c$ זאת אומרת ש-$b=ak\land c=bm$ ולכן $c=a(km)$ מה שאומר ש-$a|c$.

אנטי סימטרי: אם $a|b\land b|a$ זאת אומרת ש- $a=bk\land b=am$ ולכן $a=a(mk)$, כיון ש-$m,k\in \mathbb{N}$ נקבל $m=k=1$ מה שאומר ש-$a=b$.

הערה: היחס "מחלק את" על השלמים איננו יחס סדר חלקי, כיון שמתקיים, למשל, ש- $-2|2\land 2|-2\land 2\neq -2$.

הגדרה. דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה $A=\{1,2,3\}$.

הגדרות. יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:

• איבר $x\in A$ נקרא מינמלי ביחס לR אם $\forall y\in A:(y,x)\in R \rightarrow y=x$. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
• איבר $x\in A$ נקרא מקסימלי ביחס לR אם $\forall y\in A:(x,y)\in R \rightarrow y=x$. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
• איבר $x\in A$ נקרא קטן ביותר ביחס לR אם $\forall y\in A:(x,y)\in R$. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)
• איבר $x\in A$ נקרא גדול ביותר ביחס לR אם $\forall y\in A:(y,x)\in R$. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)

הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי הגדול ביותר.

הערה: מינימום $\leftarrow$ מינימלי, וכן מקסימום $\leftarrow$ מקסימלי, ולא להיפך!

תרגיל

תהא $A$ קבוצה ו$R$ יחס סדר חלקי מעליה. הוכח או הפרך: אם $a\in A$ איבר מינימלי יחיד אז $a$ הוא קטן ביותר.

פתרון

הפרכה. דוגמה נגדית: נגדיר יחס $R$ מעל $A=\mathbb{Z}\cup\left\{ \left\{ 1\right\} \right\}$ , בצורה הבאה: $aRb$ אם"ם $a,b\in\mathbb{Z}\land a\leq b \lor a=b=\left\{ 1\right\}$ .

ראשית, צ"ל שזה יחס סדר חלקי:

רפלקסיביות: לכל $a\in A$ אם $a=\left\{ 1\right\}$ אזי לפי ההגדרה aRa וכן אם $a\in\mathbb{Z}$ גם כן מתקיים aRa.

אנטי סמטריות: אם $\left(a,b\right),\left(b,a\right)\in R$ אזי אם $a=\left\{ 1\right\}$ אזי לפי ההגדרה $a=b$ (כי $a$ לא מתייחס לאף אחד אחר חוץ מלעצמו, לפי ההגדרה). אם $a\in\mathbb{Z}$ אזי בהכרח לפי הגדרת היחס גם $b\in\mathbb{Z}$ ואם $a\leq b\land b\leq a$ בשלמים אז בהכרח $a=b$.

טרנזטיביות: אם $\left(a,b\right),\left(b,c\right)\in R$ אזי אם $a=\left\{ 1\right\}$ אזי לפי ההגדרה $a=b=c$ וכמובן $\left(a,c\right)=\left(a,a\right)\in R$. אם $a\in\mathbb{Z}$ אזי בהכרח לפי הגדרת היחס גם $b\in\mathbb{Z}$ ולכן גם $c\in\mathbb{Z}$ ומתקיים $a\leq b\leq c$ ובפרט $\left(a,c\right)\in R$.

כעת, נראה שיש מינימלי יחיד שאינו קטן ביותר: $\left\{ 1\right\}$ הוא איבר מינימלי יחיד בקבוצה. מינימלי כי פרט לעצמו אף איבר לא ניתן להשוואה עימו, ולכן אין שונה ממנו שקטן ממנו, ואין עוד מינימלי כי $\forall a\in\mathbb{Z}:a-1<a$. הוא לא הקטן ביותר כי אף איבר לא ניתן להשוואה עימו, וכלן לא מתקיים שהוא קטן מכולם (הוא לא קטן מאף שלם).

הערה: $\left\{ 1\right\}$ הוא גם מקסימלי יחיד שאינו גדול ביותר.

דוגמא

נביט בקבוצה $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)\}$

(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)

• 5,3,1 הינם איברים מינימליים שכן אין איבר שקטן מאף אחד מהם. הם אינם מינימום כי אף אחד מהם לא קטן מכל האיברים האחרים.
• 4 הינו מקסימום של הקבוצה, הוא בוודאי מקסימלי
• 2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.

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

דוגמאות

דוגמא.

נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד $B=\{1,3,5\}$. קבוצת חסמי המלעיל של B הינה $\{2,4\}$. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.

דוגמא. נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. $B=\{1,1.4,1.41,1.414,1.4142,...\}$. חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה.

שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון.

דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).

למשל $sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1$

תרגיל

הוכיחו: אם $x$ חסם מלרע של $B$ וגם $x\in B$ אזי $inf(B)=x$ (וגם ב B יש איבר קטן ביותר שהוא x).

פתרון

צריך להראות ש- $x$ גדול ביותר בקבוצת חסמי המלרע של $B$. יהי $y$ חסם מלרע של $B$, לכן, לכל $b\in B$ מתקיים ש- $y\leq b$, ובפרט עבור $x\in B$ נקבל $y\leq x$. זוהי בדיוק ההגדרה של גדול ביותר.

בנוסף, יהי $b\in B$, כיון ש-$x$ חסם מלרע נקבל $x\leq b$, ולכן $x$ קטן ביותר ב-$B$.

הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים $[(a,b)\in R]\or[(b,a)\in R]$ אזי R נקרא יחס סדר מלא.

תרגיל ממבחן

הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי.

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

הוכחה.

נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B.

יחס סדר מילוני

יהיו $(A,\leq),(B,\preceq)$ שתי קבוצות סדורות חלקית.

על $A\times B$ ניתן להגדיר את היחס המילוני $R$ ע"י

$(a_1,b_1)R(a_2,b_2)\iff (a_1 < a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2)$

דוגמא

נסתכל על $\mathbb{N}\times \mathbb{N}$ אם הסדר המילוני.

נגדיר $B = \{(1,x) | x\in \mathbb{N} \}$ אזי $sup(B)=(2,1),inf(B)=(1,1)$

נגדיר $B = \{(x,1) | x\in \mathbb{N} \}$ אזי $inf(B)=(1,1)$ ו sup לא קיים.

• שימו לב ש $(1,1)$ הוא איבר קטן ביותר

מכפלה של יחסי סדר

יהיו $(A,\leq),(B,\preceq)$ שתי קבוצות סדורות חלקית.

על $A\times B$ ניתן להגדיר את היחס $R$ הבא:

$(a_1,b_1)R(a_2,b_2)\iff (a_1 \leq a_2) \land ( b_1 \preceq b_2)$

זהו יחס סדר:

הוכחה:

1. רפקלסיביות: לכל $a,b$ מתקיים כי $a\leq a, b\preceq b$ ולכן $(a,b)R(a,b)$

2. אנטי סימטריות: אם $(a,b)R(a1,b1)$ וגם $(a1,b1)R(a,b)$ אז $a\leq a1, b\preceq b1$ וגם $a1\leq a, b1 \preceq b$, כיוון שאלו יחס סדר נקבל כי $a=a1,b=b1$

3. טרנז' - תרגיל

דוגמא

נסתכל על $\mathbb{N}\times \mathbb{N}$ אם הסדר המוגדר לעיל.

נגדיר $B = \{(1,x) | x\in \mathbb{N} \}$ אזי $inf(B)=(1,1)$ ו sup לא קיים

נגדיר $B = \{(x,1) | x\in \mathbb{N} \}$ אזי $inf(B)=(1,1)$ ו sup לא קיים.

• שימו לב ש $(1,1)$ הוא איבר קטן ביותר

תרגיל (ממבחן קיץ תשעה מועד ב)

תהא $X$ קבוצת כל הסדרות הבינאריות (סדרה בינארית היא $a_1a_2a_3\dots$ כאשר $a_n\in \{0,1\}$). נגדיר יחס $R$ על $X$ כך: עבור $a=a_1a_2\dots ,b=b_1b_2\dots \in X$

$aRb \iff \; \forall n\; a_n-b_n \neq (-1)^n$

א. הוכיחו ש $R$ יחס סדר על $X$

ב. קבעו האם $R$ יחס סדר מלא על $X$

ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב $X$ (ביחס ל $R$)

פתרון

דרך שקולה לתאר את היחס שמפשטת את השאלה היא כך

$aRb \iff \big( \forall k \; a_{2k}=1 \Rightarrow b_{2k}=1, \; a_{2k-1}=0\Rightarrow b_{2k-1}=0\big)$

כלומר במיקומים הזוגיים, אם a שווה 1 אז זה גורר ש b שווה 1

ובמיקומים האי זוגיים, אם a שווה 0 אז זה גורר ש b שווה 0

א. תרגיל לבד!

ב. לא סדר מלא, למשל $a=000\dots, b=111\dots$ לא מתייחסים זה לזה.

ג. קימיים, $M=010101\dots$ הינו איבר הגדול ביותר כי לכל $a$ מתקים $aRM$

$m=101010\dots$ הינו איבר קטן ביותר כי לכל $a$ מתקים $mRa$

תרגיל (מבוחן תשעג)

יהא $A$ קבוצה ו $R\subseteq A\times A$ יחס סדר מלא עליה. נגדיר $O$ להיות קבוצת כל יחסי הסדר החלקיים על $A$, סדורה ע"י הכלה. (כלומר הזוג $(O,\subseteq)$ - במילים אחרות, חושבים על $O$ עם יחס הסדר החלקי "הכלה")

הוכח: $R$ איבר מקסימלי ב $O$

פתרון- יהי $S\in O$ יחס סדר חלקי על $A$ המקיים $R\subseteq S$ צ"ל $R=S$

נניח בשלילה כי $R$ מוכל ממש ב $S$

אזי קיים $(a,b)\in S\land(a,b)\notin R$. כיוון ש $R$ יחס מלא אזי מתקיים $(b,a)\in R$ כיוןן ש $R\subseteq S$ נובע כי $(b,a)\in S$

מכיוון ש $S$ יחס סדר חלקי (בפרט אנטי סימטרי) אזי $a=b$ (כי גם ($a,b)\in S$) אזי קיבלנו כי ּ$(a,a)=(a,b)\notin R$ סתירה לכך ש $R$ יחס סדר מלא ובפרט רפלקסיבי.

האם ב $O$ יש מקסימום (איבר גדול ביותר)?

תשובה: לא. נניח שקיים איבר מקס' $S$. כיוון שגם $R^{-1}\in O$ יחס אזי $R\cup R^{-1} \subseteq S$. בפרט אם $(a,b)\in R$ שונים (נניח שב $A$ יש 2 איברים לפחות) אזי $(b,a)\in R^{-1}$ ולכן $(a,b),(b,a)\in S$ בניגוד לכך ש $S$ אנטי סימטרי