תורת הקבוצות/יחסי סדר: הבדלים בין גרסאות בדף

למשל, <math>1\prec2</math> (נקרא זאת: 1 קטן מ-2, או 1 לפני 2) וגם <math>2\prec4</math> ואכן מתקיים ש- <math>1\prec4</math>.

ניתן גם לראות כי <math>3\cancel{\prec}4</math> וגם <math>4\cancel{\prec}3</math>.

ניתן לראות יחס זה ניתן לתיאור גם באופן גרפי:

(כלומר <math>a|_2b</math> אם ורק אם <math>b</math> מתחלק ב-<math>a</math> ללא שארית ותוצאת החלוקה גדולה מ-1. למשל <math>5|_215</math> אבל <math>15 \cancel{|_2}5</math> וגם <math>5\cancel{|_2}5</math>)

תכונה ידוע היא שלכל מספר טבעי <math>n</math> שונה מ-0, מתקיים <math>{n\over n} = 1</math> ולכן <math>n\cancel{|_2}n</math>. כלומר, היחס אי-רפלקסיבי.

נניח כי <math>n|_2 m</math> ו-<math>m |_2 k</math> לכן קיימים <math>x,y>1</math> טבעיים עבורם <math>k=x\cdot m</math> וגם <math>m = y\cdot n</math>.

מטרנזיטיביות השוויון (ראה [[תורת הקבוצות/יחסי שקילות|יחסי שקילות]]) נקבל כי <math>k = x\cdot m = x\cdot y \cdot n</math>. כלומר <math>k=xy\cdot n</math>.

כמו כן, <math>x,y>1\to x\cdot y >1</math> וגם כפל של טבעיים הוא מספר טבעי ולכן <math>n|k_2k</math>.

לקבוצה עם יחס סדר חלקי אנו קוראים '''קבוצה''' '''סדורה חלקית'''. נגדיר:

א. נסו למצוא קבוצות <math>A,B</math> שונות ויחס סדר חלקי <math>\prec</math> כך שמתקיים <math>\{(a,b)\in A\times A|a\prec b\}=\{(a,b)\in B\times B| a\prec b\}</math>.

תהי <math>A=\{a,b,c,d,e,f,g,x,y,z\}</math>.

התבוננו בתרשים של היחס סדר החלקי <math>\lessdot</math> המוגדר עליה :

מהתרשים ניתן לראות שביחס יש אבעה איברים מקסימליים (<math>g,e,f,z</math>, למה?)

אם נקח את התת קבוצה <math>B=\{a,b,c,d,e,f,g\}</math>ונצמצם את היחס אליואליה (בצמצום הכוונה ל-<math>\lessdot \cap (B \times B)</math>)

אז ביחס החדש יש 3 איברים מקסימליים, ואיבר קטן ביותר (<math>a</math>) [הכוונה, אם נתאלם מהחלק הימני ונסתכל רק ב"גוש" השמאלי שבסרטוט).

התבוננות בתרשים מביאמביאה אותנו לחשוד בטענה הבאה:

מהנחת השלילה נובע כי <math>a\ne m</math> וגם <math>a \cancel {\prec} am</math> בסתירה לכך ש-<math>a</math> איבר קטן ביותר.

ם:ההנחה הובילה לסתירה ולכן <math>a=m</math>ובכך הראנו כי <math>a</math> הוא האיבר המינימלי היחיד. כפי שרצינו.}}שימו לב, הוכחנו כי אם ביחס סדר חלק יש איבר קטן/גדול ביותר אז הוא האיבר המינימלי/מקסימלי היחיד. הכיוון השני אינו נכון (חשבו על דוגמה נגדית).