תרגול 5 מדמח קיץ תשעז: הבדלים בין גרסאות בדף

מתוך Math-Wiki
 
(7 גרסאות ביניים של אותו משתמש אינן מוצגות)
שורה 12: שורה 12:
*היחס 'מוכל-שווה' על הקבוצות
*היחס 'מוכל-שווה' על הקבוצות
*היחס 'מחלק את ' על הטבעיים
*היחס 'מחלק את ' על הטבעיים
נוכיח ש"מחלק את" על הטבעיים הינו יחס סדר חלקי:
רפלקסיבי: כל מספר מחלק את עצמו.
טרנזיטיבי: אם <math>a|b\land b|c</math> זאת אומרת ש-<math>b=ak\land c=bm</math> ולכן <math>c=a(km)</math> מה שאומר ש-<math>a|c</math>.
אנטי סימטרי: אם <math>a|b\land b|a</math> זאת אומרת ש- <math>a=bk\land b=am</math> ולכן <math>a=a(mk)</math>, כיון ש-<math>m,k\in \mathbb{N}</math> נקבל <math>m=k=1</math> מה שאומר ש-<math>a=b</math>.
'''הערה:''' היחס "מחלק את" על השלמים איננו יחס סדר חלקי, כיון שמתקיים, למשל, ש- <math>-2|2\land 2|-2\land 2\neq -2</math>.


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


הערה: <math>\left\{ 1\right\}</math> הוא גם מקסימלי יחיד שאינו גדול ביותר.
הערה: <math>\left\{ 1\right\}</math> הוא גם מקסימלי יחיד שאינו גדול ביותר.
===דוגמא===
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
<math>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)\}</math>
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
*5,3,1 הינם איברים מינימליים שכן אין איבר שקטן מאף אחד מהם. הם אינם מינימום כי אף אחד מהם לא קטן מכל האיברים האחרים.
*4 הינו מקסימום של הקבוצה, הוא בוודאי מקסימלי
*2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.




שורה 66: שורה 66:
=== דוגמאות ===
=== דוגמאות ===


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


'''דוגמא.'''
'''דוגמא.'''
שורה 79: שורה 76:


למשל <math>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>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>-2|2\land 2|-2\land 2\neq -2</math>.


===תרגיל===
===תרגיל===
שורה 112: שורה 107:


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


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


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


*שימו לב ש <math>(1,1)</math> הוא איבר קטן ביותר
*שימו לב ש <math>(1,1)</math> הוא איבר קטן ביותר
שורה 132: שורה 127:
הוכחה:
הוכחה:


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


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


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


שורה 194: שורה 189:




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


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

גרסה אחרונה מ־09:12, 22 באוגוסט 2017

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

יחסי סדר

הגדרה: יחס 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] אנטי סימטרי