(←דוגמא) |
(←תרגיל (מבוחן תשעג)) |
||
(5 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 66: | שורה 66: | ||
=== דוגמאות === | === דוגמאות === | ||
− | |||
− | |||
− | |||
'''דוגמא.''' | '''דוגמא.''' | ||
שורה 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> | ||
− | |||
===תרגיל=== | ===תרגיל=== | ||
שורה 111: | שורה 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> הוא איבר קטן ביותר | ||
שורה 131: | שורה 127: | ||
הוכחה: | הוכחה: | ||
− | 1. רפקלסיביות: לכל <math>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> | ||
שורה 177: | שורה 173: | ||
=== תרגיל (מבוחן תשעג)=== | === תרגיל (מבוחן תשעג)=== | ||
− | + | תהא <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> עם יחס הסדר החלקי "הכלה") | ||
שורה 193: | שורה 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>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 נקרא אנטי-סימטרי אם מתקיים
כלומר, אם אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.
הגדרה: יחס R על A נקרא יחס סדר חלקי אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
דוגמאות ליחסי סדר חלקי:
- היחס 'קטן-שווה' על המספרים
- היחס 'מוכל-שווה' על הקבוצות
- היחס 'מחלק את ' על הטבעיים
נוכיח ש"מחלק את" על הטבעיים הינו יחס סדר חלקי:
רפלקסיבי: כל מספר מחלק את עצמו.
טרנזיטיבי: אם זאת אומרת ש-
ולכן
מה שאומר ש-
.
אנטי סימטרי: אם זאת אומרת ש-
ולכן
, כיון ש-
נקבל
מה שאומר ש-
.
הערה: היחס "מחלק את" על השלמים איננו יחס סדר חלקי, כיון שמתקיים, למשל, ש- .
הגדרה. דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה .
הגדרות. יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:
- איבר
נקרא מינמלי ביחס לR אם
. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
- איבר
נקרא מקסימלי ביחס לR אם
. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
- איבר
נקרא קטן ביותר ביחס לR אם
. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)
- איבר
נקרא גדול ביותר ביחס לR אם
. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי הגדול ביותר.
הערה: מינימום מינימלי, וכן מקסימום
מקסימלי, ולא להיפך!
תרגיל
תהא קבוצה ו
יחס סדר חלקי מעליה. הוכח או הפרך: אם
איבר מינימלי יחיד אז
הוא קטן ביותר.
פתרון
הפרכה. דוגמה נגדית: נגדיר יחס מעל
, בצורה הבאה:
אם"ם
.
ראשית, צ"ל שזה יחס סדר חלקי:
רפלקסיביות: לכל אם
אזי לפי ההגדרה aRa וכן אם
גם כן מתקיים aRa.
אנטי סמטריות: אם אזי אם
אזי לפי ההגדרה
(כי
לא מתייחס לאף אחד אחר חוץ מלעצמו, לפי ההגדרה). אם
אזי בהכרח לפי הגדרת היחס גם
ואם
בשלמים אז בהכרח
.
טרנזטיביות: אם אזי אם
אזי לפי ההגדרה
וכמובן
. אם
אזי בהכרח לפי הגדרת היחס גם
ולכן גם
ומתקיים
ובפרט
.
כעת, נראה שיש מינימלי יחיד שאינו קטן ביותר: הוא איבר מינימלי יחיד בקבוצה. מינימלי כי פרט לעצמו אף איבר לא ניתן להשוואה עימו, ולכן אין שונה ממנו שקטן ממנו, ואין עוד מינימלי כי
. הוא לא הקטן ביותר כי אף איבר לא ניתן להשוואה עימו, וכלן לא מתקיים שהוא קטן מכולם (הוא לא קטן מאף שלם).
הערה: הוא גם מקסימלי יחיד שאינו גדול ביותר.
הגדרות. תהי A קבוצה, ותהי B קבוצה המוכלת בה ויהי R יחס סדר חלקי:
- חסם מלעיל של B הוא איבר
כך שמתקיים
- חסם מלרע של B הוא איבר
כך שמתקיים
- החסם העליון (סופרמום) של B הינו האיבר הקטן ביותר בקבוצת חסמי המלעיל (אם קיים). מסומן
- החסם התחתון (אינפימום) של B הינו האיבר הגדול ביותר בקבוצת חסמי המלרע (אם קיים). מסומן
דוגמאות
דוגמא.
נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. . חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה.
שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון.
דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).
למשל
תרגיל
הוכיחו: אם חסם מלרע של
וגם
אזי
(וגם ב B יש איבר קטן ביותר
שהוא x).
פתרון
צריך להראות ש- גדול ביותר בקבוצת חסמי המלרע של
. יהי
חסם מלרע של
, לכן, לכל
מתקיים ש-
, ובפרט עבור
נקבל
. זוהי בדיוק ההגדרה של גדול ביותר.
בנוסף, יהי , כיון ש-
חסם מלרע נקבל
, ולכן
קטן ביותר ב-
.
הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים אזי R נקרא יחס סדר מלא.
תרגיל ממבחן
הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי.
תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי.
הוכחה.
נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B.
יחס סדר מילוני
יהיו שתי קבוצות סדורות חלקית.
על ניתן להגדיר את היחס המילוני
ע"י
דוגמא
נסתכל על עם הסדר המילוני.
נגדיר אזי
נגדיר אזי
ו sup לא קיים ובכלל אין חסמי מלעיל.
- שימו לב ש
הוא איבר קטן ביותר
מכפלה של יחסי סדר
יהיו שתי קבוצות סדורות חלקית.
על ניתן להגדיר את היחס
הבא:
זהו יחס סדר:
הוכחה:
1. רפקלסיביות: לכל מתקיים כי
ולכן
2. אנטי סימטריות: אם וגם
אז
וגם
, כיוון שאלו יחס סדר נקבל כי
3. טרנז' - תרגיל
דוגמא
נסתכל על אם הסדר המוגדר לעיל.
נגדיר אזי
ו sup לא קיים
נגדיר אזי
ו sup לא קיים.
- שימו לב ש
הוא איבר קטן ביותר
תרגיל (ממבחן קיץ תשעה מועד ב)
תהא קבוצת כל הסדרות הבינאריות (סדרה בינארית היא
כאשר
). נגדיר יחס
על
כך:
עבור
א. הוכיחו ש יחס סדר על
ב. קבעו האם יחס סדר מלא על
ג. מצאו (אם קיימים) איבר קטן וגדול ביותר ב (ביחס ל
)
פתרון
דרך שקולה לתאר את היחס שמפשטת את השאלה היא כך
כלומר במיקומים הזוגיים, אם a שווה 1 אז זה גורר ש b שווה 1
ובמיקומים האי זוגיים, אם a שווה 0 אז זה גורר ש b שווה 0
א. תרגיל לבד!
ב. לא סדר מלא, למשל לא מתייחסים זה לזה.
ג. קימיים, הינו איבר הגדול ביותר כי לכל
מתקים
הינו איבר קטן ביותר כי לכל
מתקים
תרגיל (מבוחן תשעג)
תהא קבוצה ו
יחס סדר מלא עליה. נגדיר
להיות קבוצת כל יחסי הסדר החלקיים על
, סדורה ע"י הכלה. (כלומר הזוג
- במילים אחרות, חושבים על
עם יחס הסדר החלקי "הכלה")
הוכח: איבר מקסימלי ב
פתרון- יהי יחס סדר חלקי על
המקיים
צ"ל
נניח בשלילה כי מוכל ממש ב
אזי קיים . כיוון ש
יחס מלא אזי מתקיים
כיוןן ש
נובע כי
מכיוון ש יחס סדר חלקי (בפרט אנטי סימטרי) אזי
(כי גם (
)
אזי קיבלנו כי ּ
סתירה לכך ש
יחס סדר מלא ובפרט רפלקסיבי.
נניח ש- . האם ב
יש מקסימום (איבר גדול ביותר)?
תשובה: לא. נניח שקיים איבר מקס' . כיוון שגם
יחס אזי
. בפרט אם
שונים (כי ב
יש 2 איברים לפחות) אזי
ולכן
בניגוד לכך ש
אנטי סימטרי