שינויים

קפיצה אל: ניווט, חיפוש

תרגול 5 מדמח קיץ תשעז

הוסרו 766 בתים, 10:09, 20 באוגוסט 2017
/* יחסי סדר */
הערה: מינימום <math>\leftarrow</math> מינימלי, וכן מקסימום <math>\leftarrow</math> מקסימלי, ולא להיפך!
====תרגיל====
תהא <math>A</math> קבוצה ו<math>R</math> יחס סדר חלקי מעליה. הוכח או הפרך: אם <math>a\in A</math> איבר מינימלי יחיד אז <math>a</math> הוא קטן ביותר.
=====פתרון=====
הפרכה. דוגמה נגדית: נגדיר יחס <math>R</math> מעל <math>A=\mathbb{Z}\cup\left\{ \left\{ 1\right\} \right\}</math> , בצורה הבאה: <math>aRb</math> אם"ם <math>a,b\in\mathbb{Z}\land a\leq b \lor a=b=\left\{ 1\right\}</math> .
'''===דוגמא.'''===
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
'''הגדרה:''' יהי R יחס על A, אזי '''היחס ההופכי''' מוגדר להיות <math>R^{-1}=\{(y,x)|(x,y)\in R\}</math>
 
'''תרגיל.'''
 
הוכח שאם R יחס סדר חלקי, גם ההופכי שלו יחס סדר חלקי
 
'''פתרון.'''
*רפלקסיביות: לכל איבר a מתקיים <math>(a,a)\in R</math> ולכן <math>(a,a)\in R^{-1}</math>
*טרנזיטיביות: נניח <math>(x,y),(y,z)\in R^{-1}</math> לכן מתקיים <math>(y,x),(z,y)\in R</math> לכן לפי הטרנזיטיביות של R מתקיים <math>(z,x)\in R</math> ולכן <math>(x,z)\in R^{-1}</math>.
*אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y.
'''הגדרות.''' יהיו תהי A קבוצה, ותהי B קבוצה המוכלת בה וR ויהי R יחס סדר חלקי:
*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math>
*חסם מלרע של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(x,y)\in R </math>
1,419
עריכות