שיעור פתרון

מבחן תשפ"ג ב', מועד א', שאלה 6 - יחסי סדר והפרש סימטרי

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

נוסח השאלה

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

((x,y),(m,n))∈R ⇔ x≤m ∧ y≤n
  1. הראו כי R הוא יחס סדר חלקי.
  2. האם R הוא יחס סדר מלא? נמקו.

יהיו S₁,S₂ שני יחסי סדר חלקיים על קבוצה C. הוכיחו או תנו דוגמה נגדית: S₁ΔS₂ הוא גם יחס סדר חלקי.

זיהוי השיטה

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

פתרון מודרך

א1. הוכחת סדר חלקי

נוסח הסעיף: עבור היחס ((x,y),(m,n))∈R ⇔ x≤m∧y≤n על A=Z×Z, הראו כי R הוא יחס סדר חלקי.

רפלקסיביות

יהי (x,y)∈A שרירותי. מתקיים x≤x וגם y≤y. לכן:

((x,y),(x,y))∈R

מכאן שהיחס רפלקסיבי.

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

יהיו (x,y),(m,n)∈A, ונניח שהיחס מתקיים בשני הכיוונים:

((x,y),(m,n))∈R,   ((m,n),(x,y))∈R

פתיחת ההגדרה נותנת:

x≤m,   y≤n,   m≤x,   n≤y

מן התנאים x≤m ו-m≤x מתקבל x=m. באותו אופן, מן התנאים על הרכיב השני מתקבל y=n. לכן (x,y)=(m,n), והיחס אנטי-סימטרי.

טרנזיטיביות

יהיו (x,y),(m,n),(u,v)∈A, ונניח:

((x,y),(m,n))∈R,   ((m,n),(u,v))∈R

לפי ההגדרה:

x≤m,   y≤n,   m≤u,   n≤v

מטרנזיטיביות של ≤ מתקבל x≤u וגם y≤v. לכן:

((x,y),(u,v))∈R

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

א2. בדיקת סדר מלא

נוסח הסעיף: האם R הוא יחס סדר מלא? נמקו.

כדי שהסדר יהיה מלא, כל שני איברים של A צריכים להיות ברי-השוואה. נבחר:

a=(0,1),   b=(1,0)

כדי ש-aRb יתקיים, צריך 0≤1 וגם 1≤0. התנאי השני נכשל, ולכן aRb אינו מתקיים.

כדי ש-bRa יתקיים, צריך 1≤0 וגם 0≤1. התנאי הראשון נכשל, ולכן גם bRa אינו מתקיים.

מצאנו שני איברים שאינם ברי-השוואה, ולכן R אינו סדר מלא.

ב. הפרש סימטרי של יחסי סדר

נוסח הסעיף: יהיו S₁,S₂ שני יחסי סדר חלקיים על קבוצה C. הוכיחו או תנו דוגמה נגדית לטענה ש-S₁ΔS₂ הוא גם יחס סדר חלקי.

הטענה אינה נכונה. כל יחס סדר חלקי הוא רפלקסיבי, ולכן לכל x∈C הזוג (x,x) נמצא גם ב-S₁ וגם ב-S₂. הפרש סימטרי שומר רק זוגות שנמצאים בדיוק ביחס אחד, ולכן כל הזוגות העצמיים נעלמים.

דוגמה מפורשת: נבחר C={1} ונגדיר:

S₁=S₂={(1,1)}

כל אחד מן היחסים הוא יחס סדר חלקי על C. אבל:

S₁ΔS₂=∅

הזוג (1,1) אינו נמצא ביחס הריק, ולכן S₁ΔS₂ אינו רפלקסיבי על C. מכאן שהוא אינו יחס סדר חלקי.

תשובה סופית

R הוא יחס סדר חלקי על Z×Z, אך אינו יחס סדר מלא.

הטענה על S₁ΔS₂ שגויה: בדוגמה C={1} ו-S₁=S₂={(1,1)}, ההפרש הסימטרי ריק ואינו רפלקסיבי.

המשך במבחן

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

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

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