שיעור פתרון

מבחן תשפ"ד ב', מועד א', שאלה 2 - הוכחות בקבוצות

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

נוסח השאלה

נתונות קבוצות A,B. עבור הטענה: אם A×B = B×A, אז A=B או A=∅ או B=∅.

  1. נסחו את הקונטרפוזיציה של הטענה.
  2. הוכיחו את הטענה.

בנוסף, נתונות N₀={0,1,2,3,...}, A₁={7,9,11}, A₂={11,13,15,...}. חשבו:

C = {x ∈ N₀ | ∃y ∈ A₁, ∀z ∈ A₂, x ≥ yz}

זיהוי השיטה

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

פתרון מודרך

א. קונטרפוזיציה

נוסח הסעיף: נסחו את הקונטרפוזיציה של הטענה.

הטענה המקורית היא:

A×B = B×A → (A=B ∨ A=∅ ∨ B=∅)

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

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

A≠B ∧ A≠∅ ∧ B≠∅ → A×B ≠ B×A

ב. הוכחת הטענה

נוסח הסעיף: הוכיחו את הטענה.

נוכיח את הקונטרפוזיציה. נניח ש-A≠B, וששתי הקבוצות אינן ריקות.

לפי הגדרת שוויון קבוצות, מכיוון ש-A≠B, קיים איבר שנמצא באחת מהקבוצות ולא בשנייה. בגלל שהטענה סימטרית ב-A וב-B, נניח בלי הגבלת הכלליות שקיים x∈A\B. כלומר:

x∈A,   x∉B

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

מהנתון B≠∅ מותר לבחור איבר כלשהו מתוך B. נסמן אותו y:

y∈B

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

x∈A,   y∈B   ⟹   (x,y)∈A×B

עכשיו בודקים את אותו זוג מול B×A. כדי ש-(x,y) יהיה שייך ל-B×A, הרכיב הראשון שלו חייב להיות שייך ל-B. כלומר היה צריך להתקיים x∈B.

אבל בחרנו את x כך ש-x∉B. לכן:

(x,y)∉B×A

מצאנו זוג סדור שמקיים:

(x,y)∈A×B ∧ (x,y)∉B×A

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

ג. חישוב הקבוצה C

נוסח הסעיף: נתונות N₀={0,1,2,3,...}, A₁={7,9,11}, A₂={11,13,15,...}. חשבו:

C = {x ∈ N₀ | ∃y ∈ A₁, ∀z ∈ A₂, x ≥ yz}

נחשב את C דרך תנאי השייכות שלה. יהי x∈N₀ מועמד להיות איבר ב-C. לפי ההגדרה, כדי ש-x יהיה ב-C צריך להתקיים:

∃y∈A₁,   ∀z∈A₂: x ≥ yz

כלומר צריך למצוא y∈A₁ אחד שעבורו x גדול או שווה לכל המכפלות yz. כאן כדאי לבדוק את הכיוון השלילי, כי A₂ אינה חסומה מלמעלה: אם לכל בחירה של y אפשר למצוא z גדול שמפיל את האי-שוויון, אז לא ייתכן שקיים y שעובד לכל z.

לכן נבדוק את שלילת תנאי השייכות:

∀y∈A₁,   ∃z∈A₂: yz > x

ניקח y∈A₁ כלשהו. מכיוון ש-A₁={7,9,11}, מתקיים y≥7, ולכן לכל z>0:

yz ≥ 7z

מכיוון ש-A₂={11,13,15,...} מכילה מספרים אי-זוגיים גדולים כרצוננו, אפשר לבחור מתוכה מספר אי-זוגי z הגדול מ-max(11,x/7). בפרט מתקיים z>x/7.

עבור z זה נקבל:

yz ≥ 7z > 7·(x/7) = x

כלומר, לכל בחירה של y∈A₁, אפשר למצוא z∈A₂ שעבורו yz>x. לכן אף y לא יכול לגרום ל-x≥yz להתקיים לכל z∈A₂, ומכאן x∉C.

הניתוח לא השתמש בתכונה מיוחדת של x, ולכן הוא נכון לכל x∈N₀. אין איברים שמקיימים את תנאי השייכות, ולכן C=∅.

תשובה סופית

הקונטרפוזיציה היא: אם A≠B וגם A≠∅ וגם B≠∅, אז A×B≠B×A.

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

הקבוצה המבוקשת היא C=∅.

המשך במבחן

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

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

לשאלה הבאה: שאלה 3 - קבוצת חזקה, ספירה והפרש סימטרי