שיעור תאוריה

הוכחות בקבוצות ומכפלה קרטזית

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

אינטואיציה

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

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

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

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

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

A × B = {(a,b) | a ∈ A, b ∈ B}

כאן A ו-B הן קבוצות, ו-(a,b) הוא זוג סדור: האיבר הראשון חייב להגיע מ-A, והשני מ-B.

X∈P(B\C) ⇔ X⊆B\C

שייכות לקבוצת חזקה הופכת לתנאי הכלה. כל איבר של B\C נמצא ב-B ואינו נמצא ב-C. לכן אם X⊆B\C, שום איבר של X אינו יכול להיות ב-C, ומתקיים X∩C=∅.

D×(EΔF)=(D×E)Δ(D×F)

הזהות נובעת מדרישת השייכות לזוג. הזוג (d,x) נמצא בצד שמאל כאשר d∈D ו-x נמצא בדיוק באחת מן הקבוצות E,F. זהו בדיוק התנאי לכך שהזוג יהיה בדיוק באחת מן המכפלות D×E ו-D×F. הגורם המשותף d∈D נשמר בשני הצדדים.

הדרישה ששתי הקבוצות אינן ריקות חיונית כאשר בונים זוג מפריד. אם למשל B=∅, אז גם A×B=∅ וגם B×A=∅, אפילו כאשר A≠B. לכן הטענה על שוויון המכפלות חייבת להשאיר את המקרים הריקים כאפשרויות נפרדות.

A≠B ⇔ (A\B≠∅) ∨ (B\A≠∅)

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

A=B ⇔ (A⊆B) ∧ (B⊆A)

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

(P → Q) ≡ (¬Q → ¬P)

זו קונטרפוזיציה: במקום להוכיח ישירות "אם P אז Q", מוכיחים "אם לא Q אז לא P".

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

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

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

u∉{x∈U | ∃y∈A, ∀z∈B: P(x,y,z)} ⇔ ∀y∈A, ∃z∈B: ¬P(u,y,z)

כאן u הוא המועמד שאת שייכותו בודקים, x הוא המשתנה הקשור בהגדרת הקבוצה, U הוא תחום המועמדים, A ו-B הם תחומי הכמתים, ו-P הוא תנאי השייכות. לאחר שמציבים u במקום x, השלילה עוברת כמת אחר כמת: כדי לשלול שקיים y שעובד לכל z, צריך להראות שלכל בחירה של y קיימת בחירה של z שמכשילה את התנאי.

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

שיטת פתרון

  1. כותבים את חובת ההוכחה במונחי ההגדרות. בשוויון קבוצות החובה היא שתי הכלות; באי-שוויון החובה היא עד מפריד; בשייכות למכפלה החובה היא שייכות של כל רכיב לקבוצה המתאימה.
  2. בטענה מהצורה "אם P אז Q" בודקים אילו נתונים נותנת הוכחה ישירה ואילו נתונים נותנת הקונטרפוזיציה. בוחרים בקונטרפוזיציה רק כאשר ¬Q מספק איברים או תנאים שאפשר לעבוד איתם.
  3. מציגים את האיברים לפי סדר הכמתים: איבר שעליו הטענה חלה תמיד נבחר שרירותית; איבר קיומי נבנה לאחר מכן, ומותר לו להיות תלוי באיברים שכבר נבחרו.
  4. פותחים כל הנחה להגדרה שלה. לדוגמה, מ-(x,y)∈A×B רושמים בנפרד x∈A וגם y∈B. אין מדלגים מהסימון למסקנה.
  5. כאשר בונים זוג מפריד, בודקים בשורות נפרדות שהוא שייך למכפלה הראשונה ושאינו שייך לשנייה. באי-שייכות מציינים במפורש איזה תנאי של הגדרת המכפלה נכשל.
  6. בקבוצה עם כמתים מציבים מועמד בתנאי השייכות, שוללים כמת אחר כמת כאשר נדרשת אי-שייכות, ובונים את העד שמכשיל את התנאי. רק לאחר שהטיעון עובד לכל מועמד מסיקים שהקבוצה ריקה.
  7. בסיום אורזים את המידע בחזרה לשפת הטענה: שייכות או אי-שייכות, הכלה, שוויון או אי-שוויון. כך המסקנה נשענת ישירות על ההגדרה שנפתחה בתחילת ההוכחה.

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

  • השלילה של "או" היא "וגם לא": ¬(P∨Q∨R) ≡ ¬P∧¬Q∧¬R.
  • כדי להוכיח ש-A×B ≠ B×A, אל תנסה להשוות את כל האיברים; מספיק זוג סדור אחד שמפריד ביניהן.
  • בכמת ∀z∈A, בחירה אחת של z לא מספיקה. התנאי חייב לעבוד לכל איבר ב-A.