'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==תזכורת==
=== תרגיל ===
היחסים הבאים הם יחסים על קבוצת הממשיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם רפלקסיבים?
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^2+y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y^2=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^2+y^2=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^3+y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y^3=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^3+y^3=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,4x+y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+5y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^2-y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y^2=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^2-y^2=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^3-y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-y^3=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x^3-y^3=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,4x-y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x-5y=7\right\} </math>
=== תרגיל ===
היחסים הבאים הם יחסים על קבוצת הטבעיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם רפלקסיבים?
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^2+y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y^2=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^2+y^2=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^3+y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y^3=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^3+y^3=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,4x+y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+5y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y=7\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^2-y=0\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y^2=1\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^2-y^2=2\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^3-y=3\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-y^3=4\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x^3-y^3=5\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,4x-y=6\right\} </math>
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x-5y=7\right\} </math>
=== תרגיל ===
עבור כל אחד מהיחסים מתרגיל קודם. קבעו האם הוא יחס סדר? האם הוא יחס שקילות? האם הוא חלוקה של הממשיים?
עבור כל אחד מיחסי השקילות של סעיף קודם - מצאו את מחלקת השקילות של האיברים <math>0,\pi, 100</math>
עבור כל אחד מיחסי השקילות של סעיף קודם - תארו את קבוצת המנה.
=== תרגיל ===
ראינו שניתן להגדיר את <math>\mathbb{Q}</math> כקבוצת מנה של יחס שקילות. הוכיחו כי ניתן להגדיר חיבור וכפל של מספר רציונאליים כמו שאנחנו רגילים.
=== תרגיל ===
מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים השלמים <math>\mathbb{Z}</math> עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הטבעיים בלבד).
הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.
=== תרגיל ===
מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים המשיים <math>\mathbb{R}</math> עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הרציונאליים בלבד).
הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.
===תרגיל===
על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר את היחסים הבאים: (היחסים יסומנו ב <math>\sim</math>)
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1=x_2^2+y_2</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1=x_2</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff y_1=y_2</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |x_1|=|x_2|</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |y_1|=|y_2|</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |x_1|+|y_1|=|x_2|+|y_2|</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2-y_1=x_2^2-y_2</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2-y_1^2=x_2^2-y_2^2</math>.
*<math>(x_1,y_1)\sim (x_2,y_2)\iff 5x_1^2-y_1=5x_2^2-y_2</math>.
הוכיחו שאלו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של <math>(0,1)</math>? ומהי, מבחינה גיאומטרית, קבוצת המנה?
=== תרגיל ===
תהא <math>X</math> קבוצה. היחסים הבאים הם יחסים על קבוצת החזקה <math>P(X)</math>. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם רפלקסיבים?
* <math>\left\{ \left(A,B\right)\,|\, A=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\subseteq B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\supseteq B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=A\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=\emptyset\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\setminus B=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=A\cup B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\setminus B=B\setminus A\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\subseteq B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\supseteq B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\cap B=A\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\cap B=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\cap B=\emptyset\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\setminus B=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\cap B=A\cup B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A^c\setminus B=B\setminus A\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A=B^c\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\subseteq B^c\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\supseteq B^c\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B^c=A\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B^c=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B^c=\emptyset\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\setminus B^c=B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\cap B^c=A\cup B\right\} </math>
* <math>\left\{ \left(A,B\right)\,|\, A\setminus B^c=B\setminus A\right\} </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>by\leq a</math> (טרנזיטיביות) וכיון ש-, ונניח בשלילה <math>by\neq a</math> מינימאלי ב-. לכן <math>y\in A\smallsetminus setminus \{a\}</math> . כעת מטרנזיטיבות נקבל שזה <math>y\leq b</math> בסתירה לכך ש- , וממינימליות b נקבל <math>y=b</math>. בסה"כ יש לנו <math>a\leq b\land ab\neq 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> .
==חסמים==
*שימו לב ש <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> . ==תרגילים נוספים==
===תרגיל ממבחן===
=== תרגיל (מבוחן תשעג)===
יהא <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>O</math> יש מקסימום (איבר גדול ביותר)?
תשובה: לא. נניח שקיים איבר מקס' <math>S</math>. כיוון שגם <math>R^{-1}\in O</math> יחס אזי <math>R\cup R^{-1} \subseteq S</math>. בפרט אם <math>(a,b)\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> אנטי סימטרי.
=== תרגיל ===
3. מצאו, אם קיימים, איבר קטן ביותר ב<math>\left(\mathbb{O},\preceq\right)</math> ואיבר גדול ביותר ב <math>\left(\mathbb{O},\preceq\right)</math>
=== תרגיל ===
תהא <math>A=\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>m\in A</math> איבר קטן ביותר, אם קיים.
#מצאו איברים מינמאלים ב <math>A\backslash\left\{ m\right\}</math> , אם קיימים.
