שיעור פתרון
מבחן תשפ"א ב', מועד א', שאלה 6 - סדר החלוקה ופעולות בין יחסים
שיעורי תאוריה רלוונטיים
נוסח השאלה
תהי A={2,4,8,16,32,64}. נגדיר יחס R על A כך:
(a,b)∈R ⇔ a|bאין צורך להראות ש-R הוא יחס סדר חלקי.
- מצאו איברים מינימליים ומקסימליים ב-A ביחס ל-R. האם קיים איבר קטן ביותר או איבר גדול ביותר?
- האם R הוא יחס סדר מלא? נמקו.
- אם נחליף את קבוצת הבסיס ב-B={2,4,8,-2,-4,-8}, האם R יהיה יחס סדר חלקי? נמקו.
יהיו S1,S2 שני יחסי סדר חלקיים על קבוצה C. הוכיחו או תנו דוגמה נגדית: S1\S2 הוא גם יחס סדר חלקי.
זיהוי השיטה
ביחס חלוקה קוראים את הסדר כשרשרת של כפולות. כדי להבדיל בין מינימלי לקטן ביותר בודקים אם האיבר רק חסר קודמים או ממש קודם לכל האיברים. בשינוי קבוצת הבסיס מחפשים תכונת סדר שנפגעת, ובפעולת הפרש בין יחסים בודקים תחילה את הזוגות העצמיים.
פתרון מודרך
א1. איברים קיצוניים
נוסח הסעיף: מצאו איברים מינימליים ומקסימליים ב-A={2,4,8,16,32,64} ביחס לחלוקה. האם קיים איבר קטן ביותר או איבר גדול ביותר?
איברי הקבוצה מסודרים בשרשרת:
2|4|8|16|32|64לכל איבר פרט ל-2 יש איבר שונה בקבוצה שמחלק אותו. לכן 2 הוא האיבר המינימלי היחיד. יתרה מזאת, 2 מחלק כל איבר ב-A, ולכן הוא גם האיבר הקטן ביותר.
כל איבר פרט ל-64 מחלק איבר גדול ממנו בשרשרת. לכן 64 הוא האיבר המקסימלי היחיד. כל איבר ב-A מחלק את 64, ולכן הוא גם האיבר הגדול ביותר.
א2. בדיקת סדר מלא
נוסח הסעיף: האם יחס החלוקה R הוא יחס סדר מלא על A?
כל איבר ב-A הוא חזקה של 2. יהיו a=2i ו-b=2j. אם i≤j, אז:
b=2j=2i·2j-iולכן a|b. אם j≤i, באותו אופן b|a. כל שני איברים ברי-השוואה, ולכן R הוא יחס סדר מלא.
א3. החלפת קבוצת הבסיס
נוסח הסעיף: אם קבוצת הבסיס היא B={2,4,8,-2,-4,-8}, האם יחס החלוקה הוא יחס סדר חלקי?
כדי להפריך סדר חלקי מספיק להפריך אנטי-סימטריות. נבחר את שני האיברים השונים 2 ו--2. מתקיים:
-2=2·(-1), 2=(-2)·(-1)לכן 2|-2 וגם -2|2, אך 2≠-2. היחס אינו אנטי-סימטרי, ולכן אינו יחס סדר חלקי על B.
ב. הפרש בין שני יחסי סדר
נוסח הסעיף: יהיו S1,S2 שני יחסי סדר חלקיים על C. הוכיחו או תנו דוגמה נגדית לטענה ש-S1\S2 הוא גם יחס סדר חלקי.
הטענה שגויה. כל יחס סדר חלקי הוא רפלקסיבי, ולכן כל זוג עצמי (x,x) נמצא גם ב-S1 וגם ב-S2. פעולת ההפרש מסירה מ-S1 את כל הזוגות שנמצאים ב-S2, ובפרט את כל הזוגות העצמיים.
לדוגמה, נבחר C={1} ו-S1=S2={(1,1)}. כל אחד משני היחסים הוא יחס סדר חלקי, אבל:
S1\S2=∅היחס הריק אינו מכיל את (1,1), ולכן אינו רפלקסיבי על C. מכאן שאינו יחס סדר חלקי.
תשובה סופית
האיבר המינימלי והקטן ביותר הוא 2; האיבר המקסימלי והגדול ביותר הוא 64.
R הוא סדר מלא על A, אך על B הוא אינו סדר חלקי משום שאנטי-סימטריות נכשלת.
הטענה על S1\S2 שגויה: בדוגמה היחידונית ההפרש ריק ואינו רפלקסיבי.
המשך במבחן
מבחן תשפ"א ב', מועד א' · שאלה 6
זהו פתרון השאלה האחרון במבחן.
חזרה לרשימת המבחנים