שיעור פתרון

מבחן תשפ"ד ב', מועד א', שאלה 5 - יחסי שקילות

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

נוסח השאלה

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

(x,y)∈R ⇔ x-y זוגי
  1. הוכיחו כי R הוא יחס שקילות על A.
  2. חשבו את מחלקות השקילות של R.
  3. כתבו את האיברים של יחס השקילות S המוגדר על ידי החלוקה {{1,2,5},{3,6},{4}} של C={1,2,3,4,5,6}.

זיהוי השיטה

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

פתרון מודרך

א. הוכחת יחס שקילות

נוסח הסעיף: הוכיחו כי R הוא יחס שקילות על A.

רפלקסיביות

עלינו להראות שלכל x∈Z מתקיים (x,x)∈R.

יהי x∈Z מספר שלם שרירותי. לפי הגדרת היחס, צריך להראות שההפרש x-x זוגי. נכתוב אותו כמכפלה של 2 במספר שלם:

x-x = 0 = 2·0

העד הוא 0∈Z, ולכן x-x זוגי. מכאן (x,x)∈R, והיחס רפלקסיבי.

סימטריות

עלינו להראות שאם (x,y)∈R, אז גם (y,x)∈R.

יהיו x,y∈Z, ונניח ש-(x,y)∈R. לפי הגדרת היחס, x-y זוגי. לכן קיים k∈Z כך ש:

x-y = 2k

נכפיל את שני אגפי המשוואה ב--1:

y-x = -(x-y) = -2k = 2(-k)

מכיוון ש-k∈Z, גם -k∈Z, ולכן y-x זוגי. מכאן ש-(y,x)∈R, והיחס סימטרי.

טרנזיטיביות

עלינו להראות שאם (x,y)∈R וגם (y,z)∈R, אז (x,z)∈R.

יהיו x,y,z∈Z, ונניח ש-(x,y)∈R וגם (y,z)∈R. לפי הגדרת היחס קיימים k,m∈Z כך ש:

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

כדי להוכיח ש-(x,z)∈R, צריך לבנות את ההפרש x-z. שני ההפרשים הנתונים נפגשים ב-y, ולכן נחבר אותם: y מופיע פעם בחיסור ופעם בחיבור, מתבטל, ומשאיר את ההפרש בין הקצוות.

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

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

היחס רפלקסיבי, סימטרי וטרנזיטיבי, ולכן R הוא יחס שקילות על Z.

ב. מחלקות השקילות

נוסח הסעיף: חשבו את מחלקות השקילות של R.

נחשב כל מחלקה מן ההגדרה. מספר x שייך למחלקה של 0 בדיוק כאשר הפרשו מ-0 זוגי:

x∈[0] ⇔ xR₀ ⇔ ∃k∈Z: x=2k

כלומר x הוא כפולה של 2, ולכן המחלקה היא קבוצת המספרים הזוגיים:

[0] = {...,-4,-2,0,2,4,...}

באופן דומה, x-1 זוגי בדיוק כאשר x אי-זוגי:

x∈[1] ⇔ xR₁ ⇔ ∃k∈Z: x=2k+1 [1] = {...,-3,-1,1,3,5,...}

כל מספר שלם הוא או זוגי או אי-זוגי, ולא יכול להיות שניהם יחד. לכן שתי המחלקות מכסות את Z והן זרות זו לזו.

כלומר קבוצת המנה היא:

Z/R = {[0], [1]}

ג. היחס שמוגדר על ידי החלוקה

נוסח הסעיף: כתבו את האיברים של יחס השקילות S המוגדר על ידי החלוקה {{1,2,5},{3,6},{4}} של C={1,2,3,4,5,6}.

נסמן את הבלוקים ב-B₁={1,2,5}, B₂={3,6} ו-B₃={4}. שני איברים שייכים ליחס S בדיוק כאשר הם נמצאים באותו בלוק. לכן היחס מתקבל מאיחוד המכפלות הקרטזיות של כל בלוק עם עצמו:

S=(B₁×B₁)∪(B₂×B₂)∪(B₃×B₃)

נתחיל ב-B₁={1,2,5}. כאשר הרכיב הראשון הוא 1, הרכיב השני יכול להיות כל איבר באותו בלוק, ולכן מקבלים את (1,1),(1,2),(1,5). כאשר הרכיב הראשון הוא 2, מקבלים את (2,1),(2,2),(2,5). עבור רכיב ראשון 5 מקבלים את (5,1),(5,2),(5,5).

B₁×B₁={(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5)}

שימו לב ששני סדרי הזוג מופיעים: גם (1,2) וגם (2,1), מפני שאלה זוגות סדורים שונים. גם זוגות עצמיים כמו (1,1) נכללים, כי מותר לבחור אותו איבר לשני הרכיבים.

באותה דרך, מהבלוק B₂={3,6} מקבלים שני זוגות שמתחילים ב-3 ושני זוגות שמתחילים ב-6:

B₂×B₂={(3,3),(3,6),(6,3),(6,6)}

בבלוק היחידוני B₃={4} יש בחירה אחת בלבד לכל רכיב:

B₃×B₃={(4,4)}

לא מכניסים זוג כמו (1,3), משום ש-1 ו-3 נמצאים בבלוקים שונים. כעת מאחדים את שלוש קבוצות הזוגות:

S = {(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5),(3,3),(3,6),(6,3),(6,6),(4,4)}

כדי לוודא שלא חסר זוג, סופרים לפי גודל הבלוקים: הבלוק הראשון תורם 32=9 זוגות, השני תורם 22=4, והבלוק היחידוני תורם זוג אחד. ברשימה יש אפוא 9+4+1=14 זוגות, בדיוק כמספר הזוגות הנדרש.

תשובה סופית

R הוא יחס שקילות על Z.

מחלקות השקילות הן קבוצת הזוגיים וקבוצת האי-זוגיים: Z/R = {[0],[1]}.

היחס מתוך החלוקה הוא:

S = {(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5),(3,3),(3,6),(6,3),(6,6),(4,4)}

המשך במבחן

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

זהו פתרון השאלה האחרון במבחן.

חזרה לרשימת המבחנים