פתרונות נבחרים לשיעורי הבית

                                                             תרגיל מס 4

 .2הוכח או הפרך ע"י דוגמא נגדית:
א.	
הוכחה:  אם  אז .
  מכאן: .
ב.	
הוכחה:  אם  או  אז . אם  אז .
 נניח כי . נראה כי אם  וגם  אז בהכרח . יהי b איבר כלשהו ב – B (קיים איבר כזה, שכן B אינה ריקה). לכל איבר  מתקיים: . לכן . באופן דומה  ולפיכך .
ג.	
פתרון: לא נכון. דוגמא נגדית: .  אך .

3.	נתונים יחסים R, S ו – T. הוכח:
א.	אם  אז .
הוכחה:

ב.	.
הוכחה:

4.	עבור כל אחד מהיחסים הבאים המוגדרים בקבוצת המספרים הממשיים, קבע האם הוא רפלקסיבי, אנטי-רפלקסיבי, סימטרי, אנטי-סימטרי (חלש / חזק), טרנזיטיבי.
א.	 - יחס אנטי-רפלקסיבי, אנטי סימטרי חזק, לא טרנזיטיבי.
ב.	 - יחס אנטי רפלקסיבי, סימטרי, לא אנטי-סימטרי חזק/חלש, לא טרנזיטיבי.
ג.	 - יחס רפלקסיבי, סימטרי, לא אנטי-סימטרי חזק/חלש, לא טרנזיטיבי.

5.	קבע האם לכל שני יחסים R,S בתוך אותה קבוצה A מתקיים
א.	אם R ו – S רפלקסיביים, אז  רפלקסיבי.
פתרון: נכון.  ולכן .
ב.	אם R ו – S סימטריים, אז  סימטרי.
פתרון: נכון. 

ג.	אם R ו – S טרנזיטיביים, אז  טרנזיטיבי.
פתרון: לא נכון. דוגמא נגדית: .

6.	הוכח כי לא ייתכן יחס סימטרי, אנטי-סימטרי חלש שאינו טרנזיטיבי.
פתרון: נראה כי כל יחס סימטרי אנטי-סימטרי חלש R, מקיים שאם  אז
 x = y. אם , אז מהסימטריות . מהאנטי-סימטריות נובע x = y.
עלינו להראות שיחס כזה הוא טרנזיטיבי, כלומר שאם xRy וגם yRz אז xRz. הראינו שאם yRz אז y=z. כיון ש: xRy אז גם xRz.

7.	יהא R יחס סדר חזק (לא ריק).
א. הראה כי  הינו יחס סדר חזק.
פתרון: נתון ש – R טרנזיטיבי ואי-רפלקסיבי. נראה כי  טרנזיטיבי ואי-רפלקסיבי.
טרנזיטיביות: נניח  וגם . לכן קיים a עבורו , וכן קיים b עבורו . היחס R הוא טרנזיטיבי ולכן xRy וגם yRz. לכן .
אי-רפלקסיבי: נניח בשלילה . לכן קיים a עבורו . היחס R טרנזיטיבי, ולכן xRx. הגענו לסתירה.

ב.	האם  תמיד, אף פעם או לפעמים?
פתרון: לפעמים. אם R הוא היחס > על הממשיים, אז . אם R הוא היחס  על הטבעיים, אז  הוא היחס הריק.

ג.	מה ניתן לומר אם R יחס סדר חלש?
פתרון: במקרה זה . נראה כי . נניח . אזי קיים z המקיים . היחס R טרנזיטיבי ולכן xRy, כלומר . נראה עתה כי . נניח . היחס R רפלקסיבי ולכן . לפיכך  וגם  ולכן .

8.	תהא A={1,2,3}. רשום את כל יחסי השקילות בתוך A.
פתרון: נעבור על כל החלוקות של A, ונראה את יחסי השקילות המתאימים להם:
•	. היחס המתאים: .
•	. היחס המתאים: .
•	. היחס המתאים: .
•	. היחס המתאים: .
•	. היחס המתאים: .

9.	בתוך  Z נגדיר שני יחסים  T,S:
 כפולה של 5.
 כפולה של 5.
הוכח או הפרך:
א.	S הוא יחס שקילות
ב.	T הוא יחס שקילות
ג.	 הוא יחס שקילות
בכל אחד מהמקרים בהם היתה תשובתכם "נכון", מצאו את מספר האיברים בקבוצת המנה.
פתרון: 
א.	נכון, S הוא יחס שקילות. xSx שכן 0 הוא כפולה של 5. אם xSy אז x-y כפולה של חמש, ואז גם y-x כפולה של 5, ולכן ySx. אם xSy וגם ySz אז x-y וגם y-z כפולות של חמש, ולכן גם הסכום שלהם x-z הוא כפולה של 5, כלומר xSz.קבוצת המנה היא: , ולכן .
ב.	לא נכון. היחס אינו רפלקסיבי. לא מתקיים למשל 1T1.
ג.	נכון. היחס רפלקסיבי שכן לכל x, xSx, ובפרט . היחס סימטרי: אם  אז xSy או xTy. אם xSy, אז מסימטריות של S, ySx. אם xTy, אז x+y כפולה של חמש ולכן y+x גם כפולה של חמש. לכן בשני המקרים מתקיים . היחס טרנזיטיבי. נניח  וגם . אם xSy וגם ySz אז מהטרנזיטיביות של S, גם xSz. אם xSy וגם yTz, אז x-y ו – y+z כפולות של חמש. לכן גם הסכום בינהם, x+z הוא כפולה של חמש ולכן xTz. באופן דומה אם xTy וגם ySz אז xTz. אם xTy וגם yTz אז x+y וגם y+z כפולות של חמש, ולכן גם ההפרש ביניהם, x-z כפולה של חמש. לכן xSz.
כל המספרים שהשארית שלהם בחלוקה לחמש היא אפס שקולים זה לזה. כל המספרים שהשארית שלהם בחלוקה לחמש היא אחת שקולים זה לזה, והם גם שקולים לכל המספרים שהשארית שלהם בחלוקה לחמש היא ארבע. כל המספרים שהשארית שלהם בחלוקה לחמש היא שתיים שקולים זה לזה, והם גם שקולים לכל המספרים שהשארית שלהם בחלוקה לחמש היא שלוש.
קבוצת המנה היא: לכן .