שיעור פתרון

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

שיעורי תאוריה רלוונטיים

נוסח השאלה

תהיינה:

A={2ⁿ·5^m | m,n∈{0,1,2,...,20}} B={2ⁿ·7^m | m,n∈{0,1,2,...,20}}

חשבו ונמקו: |P(A∩B)|, |P(A×B)|.

תהי A=Z, ונגדיר יחס R על A כך:

(x,y)∈R ⇔ (x=y) ∨ (2 | x+y)

האם R רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי? הוכיחו או תנו דוגמה נגדית לכל תכונה.

זיהוי השיטה

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

פתרון מודרך

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

נוסח הסעיף: עבור הקבוצות A={2ⁿ·5^m} ו-B={2ⁿ·7^m}, כאשר כל מעריך נע בין 0 ל-20, חשבו את |P(A∩B)| ואת |P(A×B)|.

ב-A יש 21 בחירות ל-n ו-21 בחירות בלתי תלויות ל-m. בחירות שונות אינן יוצרות אותו מספר: לפי יחידות הפירוק לגורמים ראשוניים, מן השוויון 2ⁿ5^m=2^n'5^m' נובע n=n' ו-m=m'. לכן:

|A|=21·21=441

אותו טיעון חל על B, ולכן |B|=441. במכפלה הקרטזית בוחרים איבר אחד מ-A ואיבר אחד מ-B באופן בלתי תלוי:

|A×B|=441·441=194481

כל אחד מ-194481 הזוגות יכול להיכלל בתת-קבוצה או לא להיכלל בה, ולכן:

|P(A×B)|=2¹⁹⁴⁴⁸¹

כעת נמצא את החיתוך. יהי x∈A∩B. אז קיימים מעריכים בתחום הנתון כך ש:

x=2ⁿ5^m=2^a7^b

הראשוני 5 מופיע רק בצורה השמאלית, ולכן יחידות הפירוק מחייבת m=0. באותו אופן b=0, והמעריכים של 2 חייבים להיות שווים. לכן:

A∩B={2ⁿ | n∈{0,1,2,...,20}}

יש בחיתוך 21 איברים, וכל איבר מספק בחירת הכללה עצמאית בתת-קבוצה:

|P(A∩B)|=2²¹=2097152

ב. בדיקת תכונות היחס

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

רפלקסיביות

יהי x∈Z שרירותי. מתקיים x=x, ולכן התנאי הראשון בהגדרת היחס מתקיים. מכאן (x,x)∈R, והיחס רפלקסיבי.

סימטריות

יהיו x,y∈Z, ונניח (x,y)∈R. אם x=y, אז גם y=x. אם 2|x+y, קיים k∈Z כך ש-x+y=2k. מחילופיות החיבור:

y+x=x+y=2k

לכן 2|y+x. בשני המקרים (y,x)∈R, ולכן היחס סימטרי.

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

נבחר x=1 ו-y=3. מתקיים:

1+3=4=2·2

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

טרנזיטיביות

יהיו x,y,z∈Z, ונניח (x,y)∈R וגם (y,z)∈R. מכל זוג ביחס נובע שסכום רכיביו זוגי: אם הרכיבים שווים, הסכום הוא 2x או 2y; ובמקרה האחר הזוגיות נתונה ישירות. לכן קיימים k,m∈Z כך ש:

x+y=2k, y+z=2m

המטרה היא להראות ש-x+z זוגי. שני הסכומים הנתונים כוללים את y, ולכן מחברים אותם ומחסירים 2y כדי להשאיר את סכום הקצוות:

x+z=(x+y)+(y+z)-2y=2k+2m-2y=2(k+m-y)

מכיוון ש-k,m,y∈Z, גם k+m-y∈Z. לכן 2|x+z, ומכאן (x,z)∈R. היחס טרנזיטיבי.

תשובה סופית

|P(A×B)|=2¹⁹⁴⁴⁸¹, ו-|P(A∩B)|=2²¹=2097152.

היחס רפלקסיבי, סימטרי וטרנזיטיבי, אך אינו אנטי-סימטרי.

המשך במבחן

מבחן תשפ"א ב', מועד א' · שאלה 4

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 5 - יחס שקילות באמצעות איחוד וחלוקה