יחסי שקילות ומחלקות שקילות

איך מזהים שהנושא מתאים

• מבקשים להוכיח שיחס הוא יחס שקילות.
• צריך למצוא מחלקות שקילות או את קבוצת המנה.
• היחס מחלק את הקבוצה לקבוצות זרות שמכסות את כל הקבוצה.
• נתונה חלוקה ומבקשים לכתוב את כל הזוגות ביחס המתאים לה.

אינטואיציה

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

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

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

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

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

הגדרות פורמליות

יחס R הוא יחס שקילות אם הוא מקיים שלוש תכונות:

• רפלקסיביות: xRx לכל x.
• סימטריות: אם xRy, אז yRx.
• טרנזיטיביות: אם xRy וגם yRz, אז xRz.

מספר שלם n נקרא זוגי כאשר הוא כפולה של 2. פורמלית:

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

יהי B⊆A. היחס הבא מוגדר על P(A):

היחס הוא יחס שקילות משום שהוא משווה שתי תוצאות באמצעות שוויון קבוצות: רפלקסיביות, סימטריות וטרנזיטיביות עוברות ישירות מתכונות השוויון. כאשר B=∅, האיחוד אינו משנה דבר ולכן כל מחלקה היא יחידון. כאשר B=A, כל תת-קבוצה מתאחדת ל-A, ולכן כל P(A) היא מחלקה אחת.

דוגמה מלאה: יחס לפי זוגיות ההפרש

נגדיר יחס R על Z כך ש-xRy אם ורק אם x-y זוגי. נוכיח כל תכונה ישירות מן ההגדרה.

רפלקסיביות. יהי x∈Z שרירותי. צריך להראות ש-(x,x)∈R, כלומר ש-x-x זוגי. מתקיים:

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

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

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

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

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

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

כאן A היא קבוצת הבסיס, a∈A הוא נציג, ו-[a] מכילה את כל האיברים שמתייחסים ל-a. הנציג אינו בהכרח מיוחד: כל איבר אחר באותה מחלקה יכול לייצג אותה.

כאשר היחס על R מוגדר על ידי xRy ⇔ x-y∈Z, שני מספרים שקולים כאשר יש להם אותו חלק שברי. מחלקת הנציג a מתקבלת מהוספת כל מספר שלם ל-a:

הכתיב a+Z מתאר הזזה של קבוצת השלמים ב-a. לדוגמה, [0]=Z, ואילו [1.5] מכילה את כל המספרים שחלקם השברי 0.5.

מדוע מחלקות שקילות אינן חופפות חלקית? אם [a] ו-[b] חולקות איבר x, אז xRa וגם xRb. מסימטריות מתקבל aRx, ומטרנזיטיביות מתקבל aRb. כעת, אם y∈[a], אז yRa; יחד עם aRb, הטרנזיטיביות נותנת yRb, ולכן y∈[b]. קיבלנו [a]⊆[b], ובאותו טיעון בכיוון ההפוך מתקבלת ההכלה השנייה. לכן שתי המחלקות זהות. כלומר, שתי מחלקות הן זהות או זרות.

הסימון A/R הוא קבוצת המנה: איבריה הם המחלקות השונות, לא האיברים המקוריים של A. מחלקות שמתקבלות מנציגים שקולים נספרות פעם אחת בלבד, משום שהן אותה קבוצה.

חלוקה של A היא אוסף של תתי-קבוצות לא ריקות, הנקראות בלוקים, כך שאיחוד כל הבלוקים הוא A וכל שני בלוקים שונים זרים. לכן כל איבר של A נמצא בבלוק אחד בדיוק.

אם נתונה חלוקה של A לבלוקים B₁,...,B_k, היחס המתאים מכיל בדיוק את הזוגות ששני רכיביהם באותו בלוק:

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

בלוק ובו |B_i| איברים תורם |B_i|·|B_i| זוגות סדורים: בחירה אחת לרכיב הראשון ובחירה בלתי תלויה לרכיב השני.

שיטת פתרון

1. להוכחת יחס שקילות מפרידים בין רפלקסיביות, סימטריות וטרנזיטיביות. בתחילת כל חלק כותבים את חובת ההוכחה המדויקת ובוחרים איברים שרירותיים מקבוצת הבסיס לפי הכמתים שבהגדרה.
2. פותחים כל הנחה כמו xRy לתנאי שמגדיר את היחס. אם התנאי הוא קיומי, מציגים את העד הקיים ואת התחום שאליו הוא שייך.
3. בונים את התנאי עבור הזוג המבוקש בשורות אלגבריות מלאות. כאשר מתקבל עד חדש, מציגים אותו ובודקים סגירות בתחום, למשל -k∈Z או k+m∈Z.
4. לאחר שהתקיים התנאי המגדיר, חוזרים לסימון היחס וכותבים את מסקנת התכונה. אין מסיקים סימטריות או טרנזיטיביות לפני שהזוג המבוקש הוחזר במפורש ל-R.
5. כדי למצוא מחלקות שקילות מתחילים מנציג a, מתרגמים את התנאי xRa לתיאור של כל x במחלקה, ואז בוחרים נציג חדש רק מחוץ למחלקות שכבר נמצאו.
6. ביחס שמוגדר על ידי הפרש שלם פותרים x-a∈Z באמצעות עד k∈Z, ומקבלים x=a+k. כך מתקבלת המחלקה a+Z.
7. בודקים כיסוי וזרות: רפלקסיביות מבטיחה שכל איבר נמצא לפחות במחלקה של עצמו, והטיעון של חיתוך מחלקות מבטיח שאיבר אינו שייך לשתי מחלקות שונות.
8. אם נתונה חלוקה, מגדירים שני איברים כקשורים כאשר הם באותו בלוק. לכן כותבים את כל הזוגות הסדורים בתוך כל בלוק, כולל זוגות עצמיים, ולא כותבים זוגות בין בלוקים שונים.

הערות מוכנות למבחן