מתמטיקה בדידה - תרגיל 7

1.	תהינה A,B,C,D קבוצות כלשהן המקימות A~B   ו  C~D. הוכח כי  .
איזו הגדרה מוצדקת ע"י הוכחה זו?

2.	תהא a  עוצמה, ותהא B קבוצה בעלת עוצמה | B |  > a  . הוכח שקיימת תת קבוצה של B בעלת עוצמה a.

3.	חשב ונמק:
א.	
ב.	 
ג.	
ד.	
ה.	 
ו.	

4.	הוכח כי הקבוצות הבאות בנות מניה:
א.	
ב.	קבוצת כל הסדרות החשבוניות שכל אבריהן שלמים.
ג.	קבוצת כל המשוואות הריבועיות שמקדמיהן הם מספרים שלמים.
ד.	קבוצת כל המספרים הממשיים שהם פתרונות של משוואה ריבועית במקדמים 
שלמים.

5.	מה עוצמת קבוצת כל התוכניות בשפת C?

6.	הראה שקבוצת כל הסדרות האינסופיות המונוטוניות עולות שאבריהן הם מספרים ראשוניים אינה בת מניה.

7.	חשב את עוצמת הקבוצות הבאות:
א.	
ב.	
ג.	קבוצת היחסים ב-N.
ד.	קבוצת היחסים מ-N ל-R.
ה.	קבוצת יחסי השקילות ב-N.
ו.	קבוצת היחסים האי-רפלקסיביים ב-R.
ז.	קבוצת היחסים הטרנזיטיביים ב-R.

8.	נגדיר יחס  S על  ע"י:

א.	הוכח כי  S הוא יחס שקילות.
ב.	מה עוצמת כל מחלקת שקילות של  S? הוכח את תשובתך.
ג.	מה עוצמת קבוצת המנה? הוכח את תשובתך.

בהצלחה