מבחן תשפ"ג ב', מועד א', שאלה 4 - עוצמות ותכונות יחס

נוסח השאלה

זיהוי השיטה

בסעיף א סופרים בחירות של מעריכים ומוכיחים שהן יוצרות ערכים שונים בעזרת יחידות הפירוק לגורמים ראשוניים. בסעיף ב פותחים את הגדרת היחס עבור כל תכונה; תכונה נכונה מוכיחים לכל האיברים, ותכונה שנכשלת מפריכים בדוגמה שמקיימת את הנחות ההגדרה.

פתרון מודרך

א. חישוב העוצמות

נוסח הסעיף: עבור A={3ⁿ·7^m | m,n∈{0,...,15}} ו-B={3ⁿ·11^m | m,n∈{0,...,15}}, חשבו ונמקו את |P(A)×P(B)| ואת |P(A∩B)|.

בכל קבוצה יש 16 אפשרויות למעריך הראשון ו-16 אפשרויות למעריך השני. צריך לוודא שבחירות שונות אינן יוצרות אותו מספר.

אם 3ⁿ·7^m=3^a·7^b, יחידות הפירוק לגורמים ראשוניים מחייבת n=a וגם m=b. לכן ההתאמה בין זוג מעריכים לאיבר של A היא חד-חד-ערכית. אותו טיעון עובד עבור B.

קבוצת חזקה של קבוצה בת 256 איברים מכילה 2²⁵⁶ תתי-קבוצות. במכפלה הקרטזית בוחרים באופן בלתי תלוי תת-קבוצה של A ותת-קבוצה של B:

כדי למצוא את החיתוך, יהי מספר ששייך גם ל-A וגם ל-B. קיימים מעריכים בתחום כך ש:

באגף ימין אין גורם 7, ולכן m=0. באגף שמאל אין גורם 11, ולכן b=0. עבור הגורם המשותף 3 מתקבל n=a. לכן:

יש בחיתוך 16 איברים, ולכן:

ב. תכונות היחס R

נוסח הסעיף: על C=Z מוגדר יחס R על ידי (x,y)∈R ⇔ x+y=1. קבעו אם היחס רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי, והוכיחו או תנו דוגמה נגדית.

רפלקסיביות

רפלקסיביות דורשת שלכל x∈Z יתקיים (x,x)∈R, כלומר x+x=1. נבחר x=0. אז:

לכן (0,0)∉R, והיחס אינו רפלקסיבי.

סימטריות

יהיו x,y∈Z שרירותיים, ונניח (x,y)∈R. לפי הגדרת היחס:

חיבור הוא קומוטטיבי, ולכן y+x=x+y=1. לפי הגדרת היחס (y,x)∈R, והיחס סימטרי.

אנטי-סימטריות

אנטי-סימטריות דורשת שאם (x,y)∈R וגם (y,x)∈R, אז x=y. נבחר x=0 ו-y=1. מתקיים:

לכן (0,1)∈R וגם (1,0)∈R, אבל 0≠1. היחס אינו אנטי-סימטרי.

טרנזיטיביות

טרנזיטיביות דורשת שאם (x,y)∈R וגם (y,z)∈R, אז (x,z)∈R. נבחר x=0, y=1, z=0. שתי ההנחות מתקיימות:

אבל עבור הזוג הישיר:

לכן (0,0)∉R, והיחס אינו טרנזיטיבי.