==== תרגיל ====
תהא <math>(A,\leq)</math> קבוצה סדורה סופית לא ריקה. הוכיחו: קיים איבר מינימאלי.
=====פתרון=====
באינדוקציה על גודל הקבוצה <math>|A|=n</math>. עבור <math>n=1</math> האיבר מינימאלי.
נניח נכונות עבור <math>|A|=n-1</math> ותהא <math>|A|=n</math>. קיים <math>a\in A</math>, ונתבונן בקבוצה הסדורה <math>(A\smallsetminus \{a\},\leq )</math>, שם יש מינימאלי שנסמנו <math>b</math>.
נחזור כעת ל-<math>A</math>. נחלק למקרים:
אם <math>a\not \leq b</math> אז <math>b</math> מינימאלי גם ב-<math>A</math>: יהי <math>y\in A</math>, כך ש- <math>y\leq b</math>, ונראה <math>y=b</math>: אכן, מההנחה נקבל <math>y\neq a</math>, ולכן <math>y\in A\setminus \{a\}</math>, ומכיון ש-b מינימלי שם נקבל <math>y=b</math>.
אם <math>a\leq b</math> אז <math>a</math> מינימאלי ב-<math>A</math>. יהי <math>y\leq a</math>, ונניח בשלילה <math>y\neq a</math>. לכן <math>y\in A\setminus \{a\}</math>. כעת מטרנזיטיבות נקבל <math>y\leq b</math>, וממינימליות b נקבל <math>y=b</math>. בסה"כ יש לנו <math>a\leq b\land b\leq a</math>, ומאנטי-סימטריות נקבל <math>a=b</math> בסתירה (כי <math>b\in A\setminus \{a\}</math>).
===הגדרה===
יהא <math>(A,\leq)</math> קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר.
===חסמים==פתרון=====יהא <math>y\in A</math> צ"ל: <math>x\leq y</math>: מהעובדה שהיחס לינארי נקבל <math>x\leq y\lor y\leq x</math>. נחלק למקרים: 1. אם <math>x\leq y</math> סיימנו. 2. אם <math>y\leq x</math> אז לפי הגדרת מינימליות (ונתון ש- <math>x</math> מינימלי) נקבל <math>x=y</math> ולכן <math>x\leq y</math> . ==חסמים==
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
הוכיחו/הפריכו: אם <math>\cup_{i\in I}A_i \not\in X</math> אזי ל <math>\{A_i\mid i\in I\}</math> אין חסם עליון.
===תרגיל ממבחן===
הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי.
תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי.
'''הוכחה.'''
נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B.
===תרגיל===
נביט בQ אוסף השברים המצומצמים. נביט בR היחס המוגדר על ידי <math>(\frac{m_1}{n_1},\frac{m_2}{n_2})</math> אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math>. הוכיחו/הפריכו: R הינו יחס סדר חלקי.
'''פתרון.'''
נבדוק את תכונות היחס:
*רפלקסיביות - ברור.
*אנטי-סימטריות - אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math> וגם <math>(m_1\geq m_2)\and(n_1\geq n_2)</math> אזי <math>(m_1= m_2)\and(n_1= n_2)</math> ולכן שני השברים המצומצמים שווים.
*טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד.
לכן R הינו יחס סדר חלקי.
שאלה: מה היה קורה אילו לא דרשנו שברים מצומצמים?
=== יחס סדר מילוני ===
3. טרנז' - תרגיל
==== דוגמא דוגמה ====
נסתכל על <math>\mathbb{N}\times \mathbb{N}</math> אם הסדר המוגדר לעיל.
נגדיר <math>B = \{(x,1) | x\in \mathbb{N} \}</math> אזי <math>inf(B)=(1,1)</math> ו sup לא קיים.
*שימו לב ש <math>(1,1)</math> הוא איבר קטן ביותר. ==== תרגיל ====נסתכל על <math>\mathbb{N}\times \mathbb{Z}</math> ותתי הקבוצות *<math>B_1 = \{(4,-x) | x\in \mathbb{N} \}</math> *<math>B_2 = \{(4,x) | x\in \mathbb{N} \}</math>*<math>B_3 = \{(x,4) | x\in \mathbb{N} \}</math> #מצאו, אם קיימים, sup ו inf לקבוצות <math>B_2,B_3</math> כאשר <math>(\mathbb{N},\leq)</math> ו <math>(\mathbb{Z},\leq)</math> ו <math>\mathbb{N}\times \mathbb{Z}</math> עם יחס המכפלה#מצאו, אם קיימים, sup ו inf לקבוצות <math>B_1,B_2</math> כאשר <math>(\mathbb{N},|)</math> ו <math>(\mathbb{Z},\leq)</math> ו <math>\mathbb{N}\times \mathbb{Z}</math> עם היחס המילוני ==== תרגיל ====נסתכל על <math>\mathbb{N}\times (0,1]</math> ותתי הקבוצה <math>B = \{(4,\frac{1}{n+1}) | n\in \mathbb{N} \}</math> מצאו, אם קיימים, sup ו inf לקבוצות <math>B</math> כאשר <math>(\mathbb{N},|)</math> ו <math>(0,1],\leq)</math> ו <math>\mathbb{N}\times (0,1]</math> עם היחס המילוני ==== תרגיל ====יהיו <math>(A,\leq),(B,\preceq)</math> שני יחסי סדר משווים הוכיחו/הפריכו:#יחס המכפלה על <math>A\times B</math> הוא משווה.#היחס המילוני על <math>A\times B</math> הוא משווה. ==== תרגיל ====#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> לא סופי המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\inf B\right\} =\left\{ B\subseteq A\mid\,\exists\sup B\right\}</math> .#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\sup B\right\}=\emptyset</math> . ==תרגילים נוספים== ===תרגיל ממבחן=== הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי. תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי. '''הוכחה.''' נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B. ===תרגיל=== נביט בQ אוסף השברים המצומצמים. נביט בR היחס המוגדר על ידי <math>(\frac{m_1}{n_1},\frac{m_2}{n_2})</math> אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math>. הוכיחו/הפריכו: R הינו יחס סדר חלקי. '''פתרון.''' נבדוק את תכונות היחס:*רפלקסיביות - ברור.*אנטי-סימטריות - אם <math>(m_1\leq m_2)\and(n_1\leq n_2)</math> וגם <math>(m_1\geq m_2)\and(n_1\geq n_2)</math> אזי <math>(m_1= m_2)\and(n_1= n_2)</math> ולכן שני השברים המצומצמים שווים.*טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד. לכן R הינו יחס סדר חלקי. שאלה: מה היה קורה אילו לא דרשנו שברים מצומצמים?
=== תרגיל (ממבחן קיץ תשעה מועד ב) ===
=== תרגיל (מבוחן תשעג)===
יהא <math>A</math> קבוצה ו <math>R\subseteq A\times A</math> יחס סדר מלא עליה. נגדיר <math>O</math>
להיות קבוצת כל יחסי הסדר החלקיים על <math>A</math>, סדורה ע"י הכלה. (כלומר הזוג <math>(O,\subseteq)</math> - במילים אחרות, חושבים על <math>O</math> עם יחס הסדר החלקי "הכלה")
הוכח1. יהא <math>R\subseteq A\times A</math> יחס סדר על <math>A</math> הוכיחו: אם<math>R\subseteq A\times A</math> יחס סדר משווה עליה. אז <math>R</math> איבר מקסימלי ב <math>O</math>
2.הוכיח: אם ב <math>A</math> לפחות 2 איברים אז ב <math>(O,\subseteq)</math> אין איברים גדול ביותר 3. הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\inf</math> 4. הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\sup</math> ==== פתרון- ====יהא <math>R\subseteq A\times A</math> יחס סדר על <math>A</math> ונניח כי הוא משווה. נוכיח כי הוא איבר מקסמאלית ב <math>O</math>. יהי <math>S\in O</math> יחס סדר חלקי על <math>A</math> המקיים <math>R\subseteq S</math> צ"ל <math>R=S</math>
נניח בשלילה כי <math>R</math> מוכל ממש ב <math>S</math>
מכיוון ש <math>S</math> יחס סדר חלקי (בפרט אנטי סימטרי) אזי <math>a=b</math> (כי גם (<math>a,b)\in S</math>)
אזי קיבלנו כי ּ<math>(a,a)=(a,b)\notin R</math> סתירה לכך ש <math>R</math> יחס סדר מלא ובפרט רפלקסיבי.
=== תרגיל ===
נגדיר <math>X=\left\{ 1,2,3,\dots,10\right\}</math> . עוד נגדיר <math>\mathbb{O}</math> להיות קבוצת כל יחסי השקילות על <math>X</math>.נגדיר יחס <math>\preceq</math> מעל <math>\mathbb{O}</math> על ידי הכלל <math>R_{1}\preceq R_{2}\iff\left(\left|X/R_{1}\right|<\left|X/R_{1}\right|\right)\lor\left(R_{1}=R_{2}\right)</math> כאשר <math>\left|X/R_{1}\right|</math> פירושו מספר האיברים בקבוצת המנה של היחס <math>R_{1}</math>.
1. הוכיחו: כי <math>\preceq</math> הוא יחס סדר על <math>\mathbb{O}</math>.
2. הוכיחו/הפריכו: זהו יחס סדר קווי
3. מצאו, אם קיימים, איבר קטן ביותר ב<math>\left(\mathbb{O},\preceq\right)</math> ואיבר גדול ביותר ב <math>\left(\mathbb{O},\preceq\right)</math>
האם ב === תרגיל === תהא <math>OA=\left\{ \left(a_{1},a_{2},a_{3}\right):\,a_{1},a_{2},a_{3}\in\mathbb{N}\right\} =\mathbb{N}^{3}</math> יש מקסימום . נגדיר יחס סדר (איבר גדול ביותראין צורך להוכיח)?<math>\leq</math> על A כך <math>\left(a_{1},a_{2},a_{3}\right)\leq\left(b_{1},b_{2},b_{3}\right)\iff\forall i\in\left\{ 1,2,3\right\} :\,a_{i}\leq b_{i}</math>
תשובה: לא. נניח שקיים איבר מקס' #מצאו <math>S</math>. כיוון שגם <math>R^{-1}m\in OA</math> יחס אזי איבר קטן ביותר, אם קיים.#מצאו איברים מינמאלים ב <math>RA\backslash\left\cup R^{-1} m\subseteq S</math>. בפרט אם <math>(a,b)right\in R</math> שונים (נניח שב <math>A</math> יש 2 איברים לפחות) אזי <math>(b,a)\in R^{-1}</math> ולכן <math>(a,b),(b,a)\in S</math> בניגוד לכך ש <math>S</math> אנטי סימטריאם קיימים.