88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 3 - היסטוריית גרסאות

אריאל: /* פתרון */

2022-11-28T08:44:36Z

פתרון

→ הגרסה הקודמת		גרסה מ־08:44, 28 בנובמבר 2022
שורה 67:		שורה 67:
	נחזור כעת ל-<math>A</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\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 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>).

	===הגדרה===		===הגדרה===

אריאל: /* פתרון */

2022-11-28T08:42:36Z

פתרון

→ הגרסה הקודמת		גרסה מ־08:42, 28 בנובמבר 2022
שורה 67:		שורה 67:
	נחזור כעת ל-<math>A</math>. נחלק למקרים:		נחזור כעת ל-<math>A</math>. נחלק למקרים:

	אם <math>a\not \leq b</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>b</math> ~~(טרנזיטיביות) וכיון ש-~~<math>b</math> ~~מינימאלי ב-~~<math>A\~~smallsetminus \~~{a\}</math> נקבל ~~שזה~~ <math>b</math> ~~בסתירה לכך ש-~~ <math>a\leq b\land a\~~neq 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>).

	===הגדרה===		===הגדרה===

אריאל: /* הגדרה */

2022-11-28T08:13:25Z

הגדרה

→ הגרסה הקודמת		גרסה מ־08:13, 28 בנובמבר 2022
שורה 77:		שורה 77:
	====תרגיל====		====תרגיל====
	יהא <math>(A,\leq)</math> קבוצה סדורה קווית. הוכיחו כי אם x מינמאלי אז x קטן ביותר.		יהא <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> .

	==חסמים==		==חסמים==

רגב991: /* תרגיילים נוספים */

2022-09-16T13:05:37Z

תרגיילים נוספים

→ הגרסה הקודמת		גרסה מ־13:05, 16 בספטמבר 2022
שורה 182:		שורה 182:
	#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\sup B\right\}=\emptyset</math> .		#תנו דוגמה לקסח <math>\left(A,\leq\right)</math> המקיים כי: <math>\left\{ B\subseteq A\mid\,\exists\sup B\right\}=\emptyset</math> .

	==~~תרגיילים~~ נוספים==		==תרגילים נוספים==

	===תרגיל ממבחן===		===תרגיל ממבחן===

אחיה בר-און: /* פתרון */

2020-07-22T13:44:17Z

פתרון

→ הגרסה הקודמת		גרסה מ־13:44, 22 ביולי 2020
שורה 252:		שורה 252:

	==== פתרון====		==== פתרון====
	יהא <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\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>R</math> מוכל ממש ב <math>S</math>

אחיה בר-און: /* תרגיל (מבוחן תשעג) */

2020-07-22T13:43:58Z

תרגיל (מבוחן תשעג)

→ הגרסה הקודמת		גרסה מ־13:43, 22 ביולי 2020
שורה 240:		שורה 240:

	=== תרגיל (מבוחן תשעג)===		=== תרגיל (מבוחן תשעג)===
	יהא <math>A</math> קבוצה ~~ו <math>R\subseteq A\times A</math> יחס סדר מלא עליה~~. נגדיר <math>O</math>		יהא <math>A</math> קבוצה. נגדיר <math>O</math>
	להיות קבוצת כל יחסי הסדר החלקיים על <math>A</math>, סדורה ע"י הכלה. (כלומר הזוג <math>(O,\subseteq)</math> - במילים אחרות, חושבים על <math>O</math> עם יחס הסדר החלקי "הכלה")		להיות קבוצת כל יחסי הסדר החלקיים על <math>A</math>, סדורה ע"י הכלה. (כלומר הזוג <math>(O,\subseteq)</math> - במילים אחרות, חושבים על <math>O</math> עם יחס הסדר החלקי "הכלה")

	~~הוכח~~: <math>R</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>

	פתרון- יהי <math>S\in O</math> יחס סדר חלקי על <math>A</math> המקיים <math>R\subseteq S</math> צ"ל <math>R=S</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>R</math> מוכל ממש ב <math>S</math>
שורה 254:		שורה 261:
	מכיוון ש <math>S</math> יחס סדר חלקי (בפרט אנטי סימטרי) אזי <math>a=b</math> (כי גם (<math>a,b)\in 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>(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> אנטי סימטרי.

	~~הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\inf</math>~~

	~~הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\sup</math>~~

	=== תרגיל ===		=== תרגיל ===

אחיה בר-און: /* תזכורת */

2020-07-21T16:01:17Z

תזכורת

הצגת שינויים

אחיה בר-און: /* תרגיל (מבוחן תשעג) */

2020-07-20T17:29:27Z

תרגיל (מבוחן תשעג)

→ הגרסה הקודמת		גרסה מ־17:29, 20 ביולי 2020
שורה 403:		שורה 403:
	אזי קיבלנו כי ּ<math>(a,a)=(a,b)\notin R</math> סתירה לכך ש <math>R</math> יחס סדר מלא ובפרט רפלקסיבי.		אזי קיבלנו כי ּ<math>(a,a)=(a,b)\notin R</math> סתירה לכך ש <math>R</math> יחס סדר מלא ובפרט רפלקסיבי.

			==== שאלות המשך ====
	האם ב <math>O</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> אנטי סימטרי.		תשובה: לא. נניח שקיים איבר מקס' <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> אנטי סימטרי.

			הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\inf</math>

			הוכיחו/הפריכו: לכל קבוצה לא ריקה <math>B\subseteq\mathbb{O}</math> קיים <math>\sup</math>

	=== תרגיל ===		=== תרגיל ===

אחיה בר-און: /* תרגיל */

2020-07-19T12:06:47Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:06, 19 ביולי 2020
שורה 419:		שורה 419:

	=== תרגיל ===		=== תרגיל ===
	תהא <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>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>m\in A</math> איבר קטן ביותר, אם קיים.
	#מצאו איברים מינמאלים ב <math>A\backslash\left\{ m\right\}</math> , אם קיימים.		#מצאו איברים מינמאלים ב <math>A\backslash\left\{ m\right\}</math> , אם קיימים.

אחיה בר-און: /* תרגיל */

2020-07-19T12:06:15Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:06, 19 ביולי 2020
שורה 416:		שורה 416:

	3. מצאו, אם קיימים, איבר קטן ביותר ב<math>\left(\mathbb{O},\preceq\right)</math> ואיבר גדול ביותר ב <math>\left(\mathbb{O},\preceq\right)</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> , אם קיימים.