שיחה:88-195 בדידה לתיכוניסטים תשעא/ארכיון 1

החידה בתרגיל 1

לאן שולחים את החידה בתרגיל 1?

מצטרף לשאלה.. שאלתי אותו דבר ומחקו לי..

מוזמנים לשלוח למייל שלי. matan.fatal@gmail.com

קבוצה חלקית

מה ההגדרה של קבוצה חלקית?

בקבוצה חלקית אנו מתכוונים לקבוצה המוכלת (אחת מהקבוצות השייכות לקבוצת החזקה) --ארז שיינר 21:39, 26 ביולי 2011 (IDT)

הוכחה באמצעות טבלת אמת

האם הוכחה באמצעות טבלת אמת היא פורמלית?

     כן (מתן פטאל)

בשאלה 12

נראה לי יש לכם טעות בשאלה 12 כי רשמת רגיל ולא עצמה את הקבוצת חזקה הזאת

נכון, זה צריך להיות העוצמה של קבוצת החזקה. --ארז שיינר 17:09, 27 ביולי 2011 (IDT)

תרגיל 3

לא הבנתי מה עושים בתרגיל 3

מוצאים קבוצות כך שהפסוקים הנתונים יהיו פסוקי אמת. --ארז שיינר 17:10, 27 ביולי 2011 (IDT)

אני יכול להביא סתם קבוצה מהראש {עם מספרים שלי} או להביא קבוצה ספציפית כמו הריקה וכו...?

מהראש או מכל מקום אחר (: --ארז שיינר 20:14, 27 ביולי 2011 (IDT)

אני בעד קבוצות מהלב ככה רואים שבאמת התכוונת לזה. --מתן פטאל 20:51, 27 ביולי 2011 (IDT)

תרגיל 1 שאלה 6

האם להתייחס ל- A ו-B כקבוצות זרות?

האם הוכחה פורמלית דורשת בהכרח טבלת אמת? או שאני יכול לפשט ביטוי ולהוכיח בעזרת החוקים שהראנו בכיתה?

מותר כפי שעשינו בכיתה, אין צורך בטבלאות אמת. --ארז שיינר 09:12, 28 ביולי 2011 (IDT)

תודה, אבל לא התייחסת לשאלה הראשונה, האם A,B זרות?

אה, אם זה לא נתון לא ניתן להניח את זה, כמובן.... --ארז שיינר 10:57, 28 ביולי 2011 (IDT)

דרך אגב בתרגיל אחד שאלה 10 זה אותו ילד מעצבן ממיקודם שאמר ש 12 לא נכון

בשאלה 10 הייתם צריכים להפריד את סעיף c מהשאלה כי אחרת אפשר לחשוב שנתונים לנו השדות מתחילת השדות אבל זאת רק הערה

שוב צודק, סעיף c נכון לקבוצות כלשהן ולא לאלה הנתונות בשאלה. --ארז שיינר 09:13, 28 ביולי 2011 (IDT)

תרגיל 2

בתרגיל מספר 2 בשאלה הראשונה לא הבנתי איך אני יכול להוכיח דבר כזה, אתם יכולים לתת לי כיוון או להסביר יותר טוב את השאלה?

בנוסף, בשאלה השלישית סעיף a מה זה אומר כמה יחסים יש על הקבוצה? איזה סוג יחסים?

בשאלה הראשונה, תנסה כמה דוגמאות עם קבוצות סופיות עד שתבין איך זה עובד. אין דרך להסביר יותר טוב את השאלה כי היא כתובה באופן לוגי ברור. "קיים T כך ש(R מוכל בT וגם לכל S (אם R מוכל בS אזי T מוכל בS))" (פלוס השייכות לאוסף יחסי השקילות במקומות המתאימים, כמובן).

בשאלה שלוש הכוונה לכל היחסים, לא משנה אם הם מסוג מוגדר או לא --ארז שיינר 10:55, 28 ביולי 2011 (IDT)

אני מבין למה זה נכון, זה ברור שפשוט צריך להוסיף כמות מינימאלית של איברים ל-R בכדי לקבל יחס שקילות הכי קטן המכיל את R, אבל אני לא יודע איך לגשת בכלל לשאלה, אני לא מבין מה אני צריך לקחת כנתונים ומה אני צריך להוכיח.

למה ברור שצריך להוסיף כמות מינימאלית של נתונים? איך עושים את התהליך הזה? אולי יש לו כמה אפשרויות שונות? אתה יכול למשל להניח בשלילה שזה לא נכון ואז להגיע לסתירה. אם תתאר את התהליך באופן מדוייק זה כנראה יעזור --ארז שיינר 22:45, 28 ביולי 2011 (IDT)

יש כנראה (טוב... האמת הסברנו את זה בשיעור) דרך לבנות את T באופן קונסטרוקטיבי. אני הוכחתי את זה עם הוכחה לא קונסטרוקטיבית. אגב נחמדה השאלה 3 C בתרגיל 2... יש לי כיוון אבל יש לי שם שגיאה שאני לא יודע לסדר עם נוסחאות בלבד. # אויש... כן פתרתי את זה, פשוט הספירה הידנית שלי ל 4 איברים לא הייתה נכונה... --Ohadklein 02:49, 29 ביולי 2011 (IDT)

כל הכבוד, זה תרגיל לא פשוט. --ארז שיינר 15:03, 29 ביולי 2011 (IDT)

שאלה 6a

מותר להשתמש בזהויות כמו פילוג, איחוד וחיתוך עם הקבוצה הריקה? (בשאלה 6b מן הסתם אסור להשתמש בפילוג..)

כן, מותר --ארז שיינר 22:43, 28 ביולי 2011 (IDT)

ההופכית של A^K

השאלה שלי היא האם ניתן להסיק שהמטריצה ההופכית ל-A^K ( A בחזקת K ) היא A בחזקת מינוס K

הוכחנו את זה באחד משיעורי הבית הקודמים. (פה זה אשכול שו"ת בבדידה)

תרגיל 2 שאלה 4

מה הכוונה בהגדרה אשר נמצאת מעל התרגיל ?

מה הכוונה מה הכוונה? 1. מטרת ההגדרה היא להגדיר את התרגיל. 2. אנחנו נראה שיחסים בעלי התכונה "חד ערכיות" הם בעצם פונקציות, וידוע לנו השימוש במושגים 'הרכבה' ו'הופכית' בפונקציות. כאן אנחנו מגדירים אותם מעט לפני שאתם רואים את המטרה בשביל הכיף. --ארז שיינר 15:02, 29 ביולי 2011 (IDT)

תרגיל בית 2 שאלה 2 ב'

מותר לכתוב ש R={(1,1),(2,2),(3,3)}? הרי זה מקיים את יחסי השקילויות(?) תודה.

כן, מותר. --ארז שיינר 23:06, 3 באוגוסט 2011 (IDT)

תרגיל 2 שאלה 3 c

מהיא נוסחה רקורסיבית ומה ההבדל בינה לבין נוסחה רגילה?

זה לא מחייב אותך להשתמש בנוסחא רקורסיבית. זו רק עצה שכנראה לא תצליח בלעדיה. כל איבר בסדרה רקורסיבית מוגדר ע"י האיברים הקודמים בסדרה.

תרגיל 3

בתרגיל 3 שאלה 1 סעיף ג כתוב: "אם S מכילה את R וגם ל-R יש מקסימום אזי ל-S יש מקסימום" האם S הנ"ל הוא יחס סדר? (אם כן, אז אני חושב שיש לי הוכחה, אם לא, אז זו שאלה פשוטה)

אוי... אני שוב מרגיש מטומטם כי אם יש איבר מקסימום ב R אז הוא גם איבר מקסימום ב S, כי האיבר ההוא גדול יותר משאר האיברים ב X.

שואל אחר: האם S היא בהכרח יחס על X? העניין מאוד מהותי לפתרון השאלה.

אני מניח שהכוונה בסעיפים אלה היא ש-S הינה יחס סדר, אחרת זו באמת שאלה קצת מטופשת כיוון שמקסימום מוגדר רק על יחס סדר... --ארז שיינר 22:58, 3 באוגוסט 2011 (IDT)

תרגיל 3 שאלה 2

בהגדרה בתחילת השאלה מה הכוונה "לצמצם את יחס הסדר לתת הקבוצה" האם אפשר בכלל לעשות דבר כזה? ואיך?

בתרגול שלי (ארז) הראנו את זה. יהי R יחס סדר על A ותהי B תת קבוצה של A. אזי $R\cap {B\times B}$ יחס סדר על B (זה תרגיל לא מסובך) --ארז שיינר 22:59, 3 באוגוסט 2011 (IDT)

אינסופיות

ניתן להגיד שאם לכל איבר בקבוצה קיים איבר הקטן ממנו, אזי הקבוצה אינסופית?

קטן תחת איזו הגדרה? הרי אם מדובר על יחס סדר, איבר תמיד קטן מעצמו ולכן ניתן לומר את זה על כל קבוצה סדורה. אם מדובר על יחס אנטי סימטרי וטרנזיטיבי שאינו רפלקסיבי, אזי אם הקבוצה סופית נתחיל מאיבר כלשהו, יש איבר הקטן ממנו (ולכן שונה ממנו) ולשני יש גם וכן הלאה. מתישהו נגיע לסוף התהליך בסתירה. --ארז שיינר 23:03, 3 באוגוסט 2011 (IDT)

אני יכול להפעיל את זה על יחס סדר, במידה ואני אומר שלכל X יש Y השונה ממנו וקטן ממנו?

כן

תרגיל 3 שאלה 2

בסעיף 2א) צ"ל: "הוכח שאם X קבוצה סופית אזי כל יחס סדר מלא עליה הוא סדר טוב" אם אני אציג אלגוריתם שמראה את האיבר המינימלי בקבוצה סופית X ואראה שהוא סופי אז זה יחשב להוכחה פורמלית? (אני לא מצליח לדחוף ללוגיקה את העובדה ש X סופית (חוץ מדברים "ברורים" שישר מוכיחים את הטענה))

אם האלגוריתם מדויק זו הוכחה מדויקת. לעיתים קרובות הדרך להוכיח משהו היא להציג אלגוריתם שיוכיח אותו באופן כללי (כמו למשל הוכחה שלכל מטריצה יש צורה מדורגת, בעזרת אלגוריתם גאוס) --ארז שיינר 23:05, 3 באוגוסט 2011 (IDT)

תודה, בסוף הוכחתי בשלילה באינדוקציה שאם לכל איבר קיים קטן ממנו שלא שווה לו, אז אנחנו לא חוזרים על איברים פעמיים באינדק' ומצד שני לכל איבר אנחנו מוצאים איבר חדש שבתת קבוצה של X, לכן יש בתת הקבוצה כמות איברים ככל שנרצה, בסתירה להנחה ש X סופית.

אגב, צריך לציין בתרגיל שתת הקבוצה של X שונה מ phi.

שאלה 3 סעיף 1

יחס שמכיל את כל הזוגות הרפלקסיים הוא טרנזיטיבי באופן ריק, והוא סימטרי ואנטי סימטרי. מכאן נובע שS הוא יחס סדר חלקי ויחס שקילות ?

כן --ארז שיינר 17:26, 4 באוגוסט 2011 (IDT)

שאלה כללית

האם S היא יחס על X ???? זה מאוד מהותי לכל ההוכחות ומאוד קשה לי לעבוד בלי הנתון הזה

תודה ארז אתה המתרגל הכי טוב בעולם

תרגיל 4 שאלה 4

צריך להפריך\להוכיח שf היא על. השאלה היא האם אני צריך להוכיח שf על עבור כל B המקיים את התנאים, או שמא שקיים B שביחס אליו f על? בתודה מראש, אופיר.

היי אופיר. תמיד בתרגילים מהסוג "יהיו נתונים, הוכח/הפרך: שמתקיים פסוק" צריך להוכיח שהפסוק מתקיים בכל מצב בו הנתונים נכונים, או למצוא מצב אחד בו הנתונים נכונים והפסוק לא. זה שקול למשפט "לכל סיר יש מכסה שמתאים לו". אתה לא נדרש למצוא סיר ספציפי שאתה יכול להרכיב לו מכסה, אלא להוכיח שהדבר נכון לכל סיר, או למצוא סיר אחד ולהוכיח שעבורו אין מכסה.

בקצרה - לכל B (:

ארז שיינר

יש פעמים שהתרגילים הם נכונים חוץ ממקרה מאוד קיצוני של קבוצה ריקה... גם בתרגיל 3, לדוגמא בשאלה 1 לא אמרו S יחס סדר, בשאלה 2 בהגדרה של "סדר טוב" לא התייחסו לקבוצה הריקה (יש איבר מינימום = קיים איבר שכל השאר גדולים ממנו = שקר, במקרה של B ריקה)... אני חושב שנתקלתי בעוד כמה שרק המקרה של הקבוצה הריקה מפיל אותם. אגב, שאלה 3 הייתה הרבה יותר מסובכת מהאחרות... יחסית הרבה משפטי עזר, קשה לראות את כל המהלך מההתחלה.--Ohadklein 01:20, 7 באוגוסט 2011 (IDT)

שאלה 3 סעיף ד

האם יש הבדל בין איבר מינימלי למינימום ?

כן. תקרא את ההגדרות מההרצאה או ממערכי התרגול 46.210.224.211

תרגיל 3 שאלה 1 ב

הכוונה היא שיש ב-R איבר מקסימלי או שיש בו איבר מקסימום (הגדול ביותר)?

תרגיל 3 שאלה 2

אפשר בבקשה הסבר יותר מפורט לגבי ההגדרה של סדר טוב (גם הסוגריים לא כל כך עזרו לי להבין) ואם אפשר גם דוגמא לסדר טוב כדי להבין בדיוק על מה מדובר. תודה

יהי יחס R וקבוצה A. תהי B תת קבוצה של A. אזי $R\cap (B\times B)$ הינו יחס סדר חלקי (תרגיל) והוא נקרא היחס המצומצם לB. שאר ההגדרה היא כפי שרשום בתרגיל --ארז שיינר

תירגול 4

מה הכוונה כל פעם שרשום P(A) ,הכוונה לפונקציה כלשהי ?

זו קבוצת החזקה - זה חלק בסיסי מהקורס בדידה. ניתן למצוא הגדרה במערכי השיעור כאן --ארז שיינר

תרגיל 3 שאלה 2 סעיף 3

לא הבנתי את הנוסח.. אפשר עזרה ??

הראה שהיחס קטן שווה אינו יחס סדר טוב (שמוגדר לעיל) --ארז שיינר

תרגיל 3 שאלה 2א

כשאומרים שיש לתת קבוצה של X מינימום לפי יחס סדר R, למה הכוונה? שיש איבר בתת הקבוצה שקטן מכל האיברים בR או שהוא קטן מכל האיברים בX?

        לתת קבוצה יש מינימום ביחס סדר מלא אם יש בה איבר שיותר קטן מכל שאר האיברים בתת הקבוצה. - ברק

הגדרת מינימום על תת קבוצה

אם אני אומר שאיבר כלשהו הוא מינימום בתת קבוצה X, הוא צריך להיות קטן מכל האיברים בקבוצה שX באה ממנה או קטן מאברי X?

   הוא צריך להיות קטן מכל האיברים בתת-הקבוצה. - ברק

תרגיל 3 שאלה ראשונה סעיף ד'

האם גם S על X?

   כן. - ברק

יחס סדר מלא

לא הבנתי בידיוק מה ההבדל בין יחס סדר מלא לבין חלקי אפשר בבקשה דוגמא זה יעזור.

מלא זה כזה שיש יחס בין כל שני איברים (למשל היחס גדול שווה, בין כל שני מספרים אתה יכול לומר שאחד גדול מהשני). לעומת זאת, יחס הכלה אינו מלא - אתה לא יכול לומר על כל שתי קבוצות שאחת מהן מוכלת בשנייה. --ארז שיינר

 ביחס סדר מלא אתה צריך שיהיה אפשר להשוות בין כל שני איברים, ביחס סדר חלקי אתה לא חייב שיהיה אפשר להשוות בין כל שני איברים.
 דוגמה ליחס סדר מלא:  R עם ≤ , אפשר להשוות כל שני מספרים ממשיים ולהגיד מי מביניהם יותר גדול.
 דוגמה ליחס סדר חלקי שאינו יחס סדר מלא: {Φ,{ראובן},{שמעון},{ראובן,שמעון}} עם היחס של הכלה, זה יחס אנטי סימטרי, רפלקסיבי וטרנזיטיבי  
 ולכן הוא יחס סדר חלקי, אבל אף אחת מבין הקבוצות {שמעון} , {ראובן} לא מוכלת בתוך השנייה ולכן זה לא יחס סדר מלא.  - ברק

תשובות לתרגילים

ארז אתה יכול להעלות פתרונות לתרגילים שכבר הגשנו? תודה

אשתדל להעלות במהירה. --ארז שיינר

תרגיל 3 בדידה

ב-1, S יחס על X?

  כן

סדר טוב

בהגדרה, המינימום בתתקבוצה קטנה מכל האיברים בקבוצה המקורית?

 המינימום בתת-קבוצה יותר קטן מכל האיברים בתת-הקבוצה. - ברק

שאלה בלי קשר לשיעורים

סנסיי רציתי לשאול האם המשפט "הדבר היחיד שנכון,הוא שכל הדברים לא נכונים" הוא היסק לוגי תקף אם כן איך מוכיחים את זה בדיוק?

זה שקול לפסוק "כל הפסוקים אינם נכונים". מכיוון שהפסוק הזה כולל את עצמו, הוא בעייתי. שוב, אני אדאג להביא לכם מידע בנושא גדל שיענה על כלל השאלות מסוג זה. --62.219.97.133