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

תוכן שנמחק תוכן שנוסף
שורה 358:
הדוגמה הפשוטה ביותר ליחס סדר טוב הוא היחס <math><</math> על הקבוצה <math>\N</math>.
 
{{הגדרה|שם=עוקב מיידי|שם=תהי <math>(A,\prec)</math> קבוצה סדורה היטב. נגדיר את '''העוקב המיידי''' (בקצרה: עוקב) של <math>x\in A</math>, כאיבר <math>S(x)\in A</math> המקיים <math>x\prec S(x)</math>, שעבורו לא קיים <math>y\in A</math> השונה מ <math>x,S(x)</math> כך ש <math>x\prec y\prec S(x)</math>.}}
נראה שלכל איבר (מלבד האחרון, אם הוא קיים) יש עוקב מיידי: יהי <math>x\in A</math> ונגדיר <math>S=\{y:x\prec y\}</math>. מכיוון שx אינו האחרון, S אינה ריקה, ויהי <math>x'</math> האיבר הראשון ב<math>S</math>. כל האיברים בS גדולים מx, לכן <math>x\prec x'</math>. נראה שלא קיים <math>x\prec y\prec x'</math>: בשביל זה חייב להתקיים <math>x\prec y</math>, לכן <math>y\in S</math>. מכיוון ש<math>x'</math> ראשון בS, נקבל <math>x'\prec y</math>, ומכיוון ש<math>y\not=x'</math> נקבל <math>y\not\prec x'</math>. קיבלנו כי <math>x'=S(x)</math>.
 
{{משפט|שם=|תוכן=<math>(A,\prec)</math> סדורה היטב, אם ורק אם לא קיימת סדרה יורדת אינסופית (מהצורה <math>a_0\succ a_1\succ a_2...</math>) ב<math>(A,\prec)</math>.}}
'''הוכחה''': נניח שקיימת סדרה אינסופית <math>\{a_n\}^\infty_{n=0}</math> המקיימת <math>a_{n+1}\prec a_n</math>. אז הקבוצה <math>S=\{a_n:n\in\N\}</math> היא תת קבוצה של <math>A</math>, ולכל איבר בה יש איבר קטן ממנו, לכן אין בה ראשון, לכן <math>(A,\prec)</math> לא סדורה היטב.
::נניח ש<math>(A,\prec)</math> לא סדורה היטב, אז תהי <math>S\subseteq A</math> לא ריקה שאין בה איבר ראשון. נבחר <math>a_0\in S</math> (קיים כי S לא ריקה). כעת נפעל ברקורסיה ולכל n טבעי, נגדיר את <math>a_n</math> כאיבר בS שקטן מ<math>a_{n-1}</math>. (קיים כי אין ראשון). הסדרה <math>\{a_n\}^\infty_{n=0}</math> היא סדרה יורדת אינסופית.
'''[[תורת הקבוצות/משפט הסדר הטוב|משפט הסדר הטוב]]''' קובע כי על כל קבוצה ניתן להגדיר סדר טוב.
{{תורת הקבוצות|מוגבל}}