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

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

יחסי סדר

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

כלומר, אם [math]\displaystyle{ x\neq y }[/math] אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.

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

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

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

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

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

טרנזיטיבי: אם [math]\displaystyle{ a|b\land b|c }[/math] זאת אומרת ש-[math]\displaystyle{ b=ak\land c=bm }[/math] ולכן [math]\displaystyle{ c=a(km) }[/math] מה שאומר ש-[math]\displaystyle{ a|c }[/math].

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

הערה: היחס "מחלק את" על השלמים איננו יחס סדר חלקי, כיון שמתקיים, למשל, ש- [math]\displaystyle{ -2|2\land 2|-2\land 2\neq -2 }[/math].

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

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

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

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

הערה: מינימום [math]\displaystyle{ \leftarrow }[/math] מינימלי, וכן מקסימום [math]\displaystyle{ \leftarrow }[/math] מקסימלי, ולא להיפך!

תרגיל

תהא [math]\displaystyle{ A }[/math] קבוצה ו[math]\displaystyle{ R }[/math] יחס סדר חלקי מעליה. הוכח או הפרך: אם [math]\displaystyle{ a\in A }[/math] איבר מינימלי יחיד אז [math]\displaystyle{ a }[/math] הוא קטן ביותר.

פתרון

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

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

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

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

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

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

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

הגדרות. תהי A קבוצה, ותהי B קבוצה המוכלת בה ויהי R יחס סדר חלקי:

• חסם מלעיל של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(y,x)\in R }[/math]
• חסם מלרע של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(x,y)\in R }[/math]
• החסם העליון (סופרמום) של B הינו האיבר הקטן ביותר בקבוצת חסמי המלעיל (אם קיים). מסומן [math]\displaystyle{ sup(B) }[/math]
• החסם התחתון (אינפימום) של B הינו האיבר הגדול ביותר בקבוצת חסמי המלרע (אם קיים). מסומן [math]\displaystyle{ inf(B) }[/math]

דוגמאות

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

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

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

למשל [math]\displaystyle{ sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1 }[/math]

תרגיל

הוכיחו: אם [math]\displaystyle{ x }[/math] חסם מלרע של [math]\displaystyle{ B }[/math] וגם [math]\displaystyle{ x\in B }[/math] אזי [math]\displaystyle{ inf(B)=x }[/math] (וגם ב B יש איבר קטן ביותר שהוא x).

פתרון

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

בנוסף, יהי [math]\displaystyle{ b\in B }[/math], כיון ש-[math]\displaystyle{ x }[/math] חסם מלרע נקבל [math]\displaystyle{ x\leq b }[/math], ולכן [math]\displaystyle{ x }[/math] קטן ביותר ב-[math]\displaystyle{ B }[/math].

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

תרגיל ממבחן

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

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

הוכחה.

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

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

יהיו [math]\displaystyle{ (A,\leq),(B,\preceq) }[/math] שתי קבוצות סדורות חלקית.

על [math]\displaystyle{ A\times B }[/math] ניתן להגדיר את היחס המילוני [math]\displaystyle{ R }[/math] ע"י

[math]\displaystyle{ (a_1,b_1)R(a_2,b_2)\iff (a_1 \lt a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2) }[/math]

דוגמא

נסתכל על [math]\displaystyle{ \mathbb{N}\times \mathbb{N} }[/math] עם הסדר המילוני.

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

נגדיר [math]\displaystyle{ B = \{(x,1) | x\in \mathbb{N} \} }[/math] אזי [math]\displaystyle{ inf(B)=(1,1) }[/math] ו sup לא קיים ובכלל אין חסמי מלעיל.

• שימו לב ש [math]\displaystyle{ (1,1) }[/math] הוא איבר קטן ביותר

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

יהיו [math]\displaystyle{ (A,\leq),(B,\preceq) }[/math] שתי קבוצות סדורות חלקית.

על [math]\displaystyle{ A\times B }[/math] ניתן להגדיר את היחס [math]\displaystyle{ R }[/math] הבא:

[math]\displaystyle{ (a_1,b_1)R(a_2,b_2)\iff (a_1 \leq a_2) \land ( b_1 \preceq b_2) }[/math]

זהו יחס סדר:

הוכחה:

1. רפקלסיביות: לכל [math]\displaystyle{ a,b }[/math] מתקיים כי [math]\displaystyle{ a\leq a, b\preceq b }[/math] ולכן [math]\displaystyle{ (a,b)R(a,b) }[/math]

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

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

דוגמא

נסתכל על [math]\displaystyle{ \mathbb{N}\times \mathbb{N} }[/math] אם הסדר המוגדר לעיל.

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

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

• שימו לב ש [math]\displaystyle{ (1,1) }[/math] הוא איבר קטן ביותר

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

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

[math]\displaystyle{ aRb \iff \; \forall n\; a_n-b_n \neq (-1)^n }[/math]

א. הוכיחו ש [math]\displaystyle{ R }[/math] יחס סדר על [math]\displaystyle{ X }[/math]

ב. קבעו האם [math]\displaystyle{ R }[/math] יחס סדר מלא על [math]\displaystyle{ X }[/math]

ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב [math]\displaystyle{ X }[/math] (ביחס ל [math]\displaystyle{ R }[/math])

פתרון

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

[math]\displaystyle{ aRb \iff \big( \forall k \; a_{2k}=1 \Rightarrow b_{2k}=1, \; a_{2k-1}=0\Rightarrow b_{2k-1}=0\big) }[/math]

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

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

א. תרגיל לבד!

ב. לא סדר מלא, למשל [math]\displaystyle{ a=000\dots, b=111\dots }[/math] לא מתייחסים זה לזה.

ג. קימיים, [math]\displaystyle{ M=010101\dots }[/math] הינו איבר הגדול ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ aRM }[/math]

[math]\displaystyle{ m=101010\dots }[/math] הינו איבר קטן ביותר כי לכל [math]\displaystyle{ a }[/math] מתקים [math]\displaystyle{ mRa }[/math]

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

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

הוכח: [math]\displaystyle{ R }[/math] איבר מקסימלי ב [math]\displaystyle{ O }[/math]

פתרון- יהי [math]\displaystyle{ S\in O }[/math] יחס סדר חלקי על [math]\displaystyle{ A }[/math] המקיים [math]\displaystyle{ R\subseteq S }[/math] צ"ל [math]\displaystyle{ R=S }[/math]

נניח בשלילה כי [math]\displaystyle{ R }[/math] מוכל ממש ב [math]\displaystyle{ S }[/math]

אזי קיים [math]\displaystyle{ (a,b)\in S\land(a,b)\notin R }[/math]. כיוון ש [math]\displaystyle{ R }[/math] יחס מלא אזי מתקיים [math]\displaystyle{ (b,a)\in R }[/math] כיוןן ש [math]\displaystyle{ R\subseteq S }[/math] נובע כי [math]\displaystyle{ (b,a)\in S }[/math]

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

נניח ש- [math]\displaystyle{ |A|\geq 2 }[/math]. האם ב [math]\displaystyle{ O }[/math] יש מקסימום (איבר גדול ביותר)?

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