שיחה:83-116 תשעד סמסטר א

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.

שאלות

5-6

מה אומר הסימן דלטא בתרגילים 5 ו6?

עוד לא הגענו לזה. אלו תרגילים בתורת הקב', נלמד ביום רביעי. עדי

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

בשאלה 2 בסעיף ד'- מה ההגדרה לקבוצה חלקית של A? האם זו תת-קבוצה של A? האם בכל קבוצה שהיא תמיד אפשר להגיד שה"קבוצה ריקה" היא תת קבוצה שלה? תודה.

בעיקרון לא הגענו לזה בשיעור, אבל:

מה ההגדרה לקבוצה חלקית של A? האם זו תת-קבוצה של A? כן

האם בכל קבוצה שהיא תמיד אפשר להגיד שה"קבוצה ריקה" היא תת קבוצה שלה? כן, וגם הקבוצה עצמה: [math]\displaystyle{ \forall A\ \ \ A,\emptyset\subseteq A }[/math]. עדי

דף1-תרגיל5

שימו לב! כאשר נתון X ורוצים שתוכיחו Y, התחילו מלשאול-מה יוכיח לנו את Y? אח"כ השתמשו בנתון והגיעו למסקנה.

למשל בדף 1-שאלה 5, נתון שוויון בין ההפרש הסימטרי של A ו-B להפרש הסימטרי של A ו-C. רוצים שתוכיחו B=C. אם תתחילו משייכות להפרש הסימטרי לא יהיה לכם יותר מידי לאן להתקדם. התחילו מ-"מה מוכיח לנו שוויון בין קבוצות B ו-C(כנדרש)?" הכלה דו כיוונית! כלומר, ניקח איבר ב-B, נשתמש בנתון, ונירצה לקבל שהאיבר ב-C. וכנ"ל בכיוון ההפוך.

רמז- לאחר שלקחתם איבר ב-B בידקו מה קורה אם הוא שייך ל-A ואם לאו. עדי

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

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

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

תרגיל 2

היי האם הגענו לשלב שבו אנחנו יכולים לפתור את שאלות 8, 9 ו10? תודה! עמית מיכאלי

8-כן.

ל-9-אעלה הגדרה אחרי התירגול הקרוב.

את 10 סביר שראיתם בהרצאה אך עוד לא בתירגול.

עדי

תרגיל 2 שאלה 9

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

בבקשה: נתונה הקבוצה [math]\displaystyle{ I=\{2,3,4\} }[/math]. נגדיר את הקבוצות [math]\displaystyle{ A_i: i\in I }[/math], כלומר [math]\displaystyle{ A_2,A_3,A_4 }[/math], באופן הבא: [math]\displaystyle{ \forall i\in I\ A_i=\{x:x=i^2\cdot k,\ k\in N\} }[/math], ז"א [math]\displaystyle{ A_i }[/math] מוגדרת להיות אוסף כל הכפולות השלמות של [math]\displaystyle{ i^2 }[/math]. לדוגמא: [math]\displaystyle{ A_3=\{x:x=3^2\cdot k,\ k\in N\}=\{\ 3^2\cdot 1,\ 3^2\cdot 2,\ 3^2\cdot 3,\ 3^2\cdot 4,...\}=\{9,18,27,36,...\}=\{9k:k\in N\} }[/math].

כעת, נשאלת השאלה מי מהבאים: 1,8,1152 שייך לאיחוד שלושת הקב' (כלומר שייך לפחות לאחת מהן, או במילים אחרות הוא כפולה שלמה של 4 או 9 או 16), ומי שייך לחיתוך שלושת הקבוצות (כלומר, שייך לכולן, או במילים אחרות הוא כפולה שלמה של 4 וגם של 9 וגם של 16).

אנא עדכנו אותי אם התשובה עוזרת. עדי

תרגיל 3 שאלה 4

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

יש גם להראות שהוא על AXB, אבל זה החלק הקצר יותר.

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

[math]\displaystyle{ (a,b)\in A\times A,\ (c,d)\in C\times C\ \ then\ \ ((a,c),(b,d))\in (A\times C)^2\ \ }[/math]

ולכן תתי קב' שלה יהיו יחסים על [math]\displaystyle{ A\times C }[/math].

כמו כן [math]\displaystyle{ \ ((a,b),(c,d))\in A^2\times C^2 }[/math] ולכן תתי קב' שלה יהיו יחסים מ-[math]\displaystyle{ A^2 }[/math] ל-[math]\displaystyle{ C^2 }[/math].

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

למשל, אם תנאי הסימטריות דורש לוודא ש- [math]\displaystyle{ xRy\Rightarrow yRx }[/math]

אז ביחס מעל מכפלה קרטזית נוודא ש- [math]\displaystyle{ (x_1,x_2)R(y_1,y_2)\Rightarrow (y_1,y_2)R(x_1,x_2) }[/math]

כלומר נתחיל מ- [math]\displaystyle{ (x_1,x_2)R(y_1,y_2) }[/math], ניישם את היחס ונבדוק האם זה גורר ש- [math]\displaystyle{ (y_1,y_2)R(x_1,x_2) }[/math]. עדי

תרגיל 3 שאלה 1

שלום עדי, כשפיתחתי את הביטוי AXB=BXA שבשאלה הגעתי שלכל a,b:

(a∈A) & (b∈B) אם ורק אם (a∈B) & (b∈A) איך אני ממשיך מפה? האם לנסות את 2 האפשרויות- פעם אחת כששניהם מתקיימים ופעם אחת כששניהם לא מתקיימים? תודה, מרדכי.

למעשה כמעט סיימת. שים לב מה רשמת, [math]\displaystyle{ \ \ (a\in A \Rightarrow a\in B) \and (b\in B \Rightarrow b\in A) }[/math], זה בדיוק התנאי לשוויון קבוצות. רק נותר לך לטפל במיקרים שלא קיים [math]\displaystyle{ \ a\in A }[/math] או לא קיים [math]\displaystyle{ b\in B }[/math]. עדי

תרגיל 4

באופן כללי, כשרשום 'הוכח כי קיימת' זה שקול ל'תן דוגמא ל..'?

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

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

1, 2, 3ג ו-5 (בהרצאה כיסיתם הכל). תאריך ההגשה לא לרביעי הקרוב כמובן. עדי

דף 3-שאלה 4

שלום לכולם,

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

לאור כך ובשל העובדה שמבנה התרגיל שונה מקודמיו אבקש מכם בכל לשון של בקשה להעמיק בקריאת הפיתרון המצורף ולהעלות שאלות אם משהו לא ברור.

עדי

תרגיל: יהי [math]\displaystyle{ E }[/math] יח"ש על [math]\displaystyle{ A }[/math] ויהי [math]\displaystyle{ F }[/math] יח"ש על [math]\displaystyle{ B }[/math]. תהי [math]\displaystyle{ G=\{((a_1,b_1),(a_2,b_2)):(a_1,a_2)\in E,\ (b_1,b_2)\in F\} }[/math].

הוכח כי [math]\displaystyle{ G }[/math] יח"ש על [math]\displaystyle{ A\times B }[/math].

פתרון: ראשית, בואו נבין היטב את הגדרת [math]\displaystyle{ G }[/math].

יחס זה בנוי מזוגות סדורים של זוגות סדורים (לא [math]\displaystyle{ (a_1,b_1),(a_2,b_2) }[/math] שזו סתם רשימה של שני איברים, לא [math]\displaystyle{ (a_1,b_1)\times (a_2,b_2) }[/math] שאין לי מושג מה זה, ועוד כל מיני צורות כאלו ואחרות שהופיעו בפיתרונותיכם), כך שהקואורדינטות הראשונות מתייחסות ב-E והקואורדינטות השניות מתייחסות ב-F (ולא הזוג הראשון ב-E והזוג השני ב-F).

יש להוכיח ש-G יחס על [math]\displaystyle{ A\times B }[/math]:

כלומר, נתבונן על שתי הקואורדינטות באייברי G, בכל אחת מהן יושב זוג סדור אשר יש להראות שהוא מ-[math]\displaystyle{ A\times B }[/math]. ע"פ הגדרה

[math]\displaystyle{ (a_1,a_2)\in E,\ (b_1,b_2)\in F\ \Rightarrow a_1\in A \and b_1\in B \and a_2\in A \and b_2\in B }[/math],

היות וידוע כי E פועלת על A ו-F פועלת על B.

ע"פ הגדרת מכפלה קרטזית זה אומר ש- [math]\displaystyle{ (a_1,b_1)\in A\times B \and (a_2,b_2)\in A\times B }[/math],

וע"פ הגדרת יחס זה אומר ש-G היא תת קבוצה של [math]\displaystyle{ (A\times B)^2 }[/math] ולכן יחס על [math]\displaystyle{ A\times B }[/math].

כעת נותר להכיח שיחס זה הוא שקילות, כלומר:

רפלקסיביות: נרצה להוכיח שכל איבר מתייחס לעצמו ב-G.

בדיקת רפלקסיביות מתחילה מבדיקת כל איבר בקבוצה עליה פועל היחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ \forall (a,b)\in A\times B }[/math]

(מה ידוע לנו לכל איבר כזה?)

[math]\displaystyle{ \Rightarrow a\in A \and b\in B }[/math]

(מה ידוע לנו לכל איבר ב-A ולכל איבר ב-B? היות ש-E ו-F יח"ש ידוע לנו שכל איבר ב-A מתייחס לעצמו ב-E וכל איבר ב-B מתייחס לעצמו ב-F)

[math]\displaystyle{ \Rightarrow (a,a)\in E \and (b,b)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a,b),(a,b))\in G }[/math].

סה"כ קיבלנו [math]\displaystyle{ \forall (a,b)\in A\times B\ \ ((a,b),(a,b))\in G }[/math] ולכן G רפלקסיבי.

סימטריות: נרצה להוכיח שאם איבר מתייחס לאחר אז האחר מתייחס לאיבר ב-G.

בדיקת סימטריות מתחילה מאיבר שמתייחס לאחר ביחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G }[/math]

(מה זה אומר לנו ע"פ הגדרה?)

[math]\displaystyle{ \Rightarrow (a_1,a_2)\in E \and (b_1,b_2)\in F }[/math]

היות ש-E ו-F יח"ש זה אומר

[math]\displaystyle{ (a_2,a_1)\in E \and (b_2,b_1)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a_2,b_2),(a_1,b_1))\in G }[/math]

סה"כ קיבלנו [math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\Rightarrow ((a_2,b_2),(a_1,b_1))\in G }[/math] ולכן G סימטרי.

טרנזיטיביות: נרצה להוכיח שאם איבר1 מתייחס לאיבר2 שמתייחס לאיבר3 אז איבר1 מתייחס לאיבר3 ב-G.

בדיקת טרנזיטיביות מתחילה איבר1 מתייחס לאיבר2 ואיבר2 שמתייחס לאיבר3 ביחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\and ((a_2,b_2),(a_3,b_3))\in G }[/math]

(מה זה אומר לנו ע"פ הגדרה?)

[math]\displaystyle{ \Rightarrow \underline{(a_1,a_2)\in E} \and \underline{\underline{(b_1,b_2)\in F}}\and \underline{(a_2,a_3)\in E} \and \underline{\underline{(b_2,b_3)\in F}} }[/math]

היות ש-E ו-F יח"ש זה אומר

[math]\displaystyle{ (a_1,a_3)\in E \and (b_1,b_3)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a_1,b_1),(a_3,b_3))\in G }[/math]

סה"כ קיבלנו [math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\and ((a_2,b_2),(a_3,b_3))\in G\Rightarrow ((a_1,b_1),(a_3,b_3))\in G }[/math] ולכן G טרנזיטיבי.

קבוצת החזקה (תרגיל 4 שאלה 5)

האם זה נכון לומר שאם {X} מוכל ב P(B) אזי x שייך לקבוצה B?

לא. אם {X} מוכל ב [math]\displaystyle{ P(B) }[/math] אז X שייך ל [math]\displaystyle{ P(B) }[/math] ולכן X מוכל ב-B.

למשל [math]\displaystyle{ B=\{1,2,3\} =\gt \{1\}\subseteq B =\gt \{1\}\in P(B) =\gt \{\{1\}\}\subseteq P(B) }[/math]

אבל [math]\displaystyle{ \{1\} }[/math] לא שייך ל-B הוא מוכל בו ({1} בתפקיד X). עדי

תרגיל 4

היי

האם בעקבות הדחיה של התרגול היום ליום ב' זה אומר שתהיה דחיה בתאריך ההגשה?

אפשרי. נחליט לפי ההתקדמות בשיעור. עדי

תרגיל 4 שאלה 4

היי עדי, אני בתרגיל 4 שאלה 4 איך אני מתחיל להוכיח? האם גם פה מתחילים ממה שצריך להוכיה או מהנתונים?

ולדוגמא בסעי' 1 איך מוכיחים שאם C אז או A או B? כי אם מנסים בשלילה-אז גם אם לא A, עדיין ייתכן שכן C, כיוון שאולי כן B. תודה

תמיד תתחיל ממה שצריך להוכיח ותשתמש בנתונים.

(*) תזכרו שביחס להרכבה הראינו שאם היא חח"ע אז הפונ' הפנימית חח"ע ואם היא על אז הפונ' החיצונית על. השתמשו בתכונות אלו בשאלה זו.

סעיף1--הכוונה האם קורה אחד מהם. בדוק כל אחד בנפרד.

הערה: בסעיפים 2,3 קיימים נתונים מיותרים. את 2 ניתן להוכיח לפי (*) גם בלי [math]\displaystyle{ hg }[/math] חח"ע וב-3, לפי (*) [math]\displaystyle{ hg }[/math] על גם בלי שיהיה נתון.

המלצה: אם התכונה (*) לא נותנת את המבוקש נסו לקבל אינטואיציה לדוגמא נגדית בדיאגרמה ואז תרגמו אותה למיספרים באופן פורמלי. דוגמא נגדית צריכה להיות פשוטה ככל האפשר.

לדוגמא סעיף 1:

[math]\displaystyle{ hgf }[/math] חח"ע ועל. אזי, לפי (*) [math]\displaystyle{ f,gf }[/math] חח"ע ו-[math]\displaystyle{ h,hg }[/math] על (חישבו ונמקו למה). מאף אחד מהם לא נובע ש-g חח"ע או על. ננסה למצוא דוגמא נגדית.

נרצה ש-f חח"ע, h על ו-g לא זה ולא זה:

[math]\displaystyle{ A\rightarrow_f B \rightarrow_g C \rightarrow_h D }[/math] (הנקודות מתחת לכל קב' מייצגות את אייבריה)

[math]\displaystyle{ .\ \ \rightarrow\ \ .\ \ \rightarrow\ \ .\ \ \rightarrow\ \ . }[/math]

[math]\displaystyle{ \ \ \ \ \ \ .\nearrow\ \ \ \ \ .\nearrow\ \ \ \ \ \ }[/math]

מצאו דוגמא פורמלית. עדי

תרגיל 4 שאלה 3

האם נכון לקחת את הביטוי בסעיף א', להפעיל עליו את הפונקציה ולקבל באגף שמאל את איחוד הקטעים D1, D2 ובאגף ימין לקבל פונקציה על ההופכי לכל אחד מהם בנפרד, ולהפעיל את הפונקציה כמו דיסטריביוטיביות? במילים אחרות, האם פונקציה ניתן להשתמש בפונקציה באופן אנלוגי לדיסטריבוטיביות?

רק אם תוכיח קודם קודם ש- [math]\displaystyle{ f[A\cup B]=f[A]\cup f[B] }[/math] (בשביל צד ימין), זה לא קשה אבל באותו אופן תוכל כבר להוכיח את המבוקש.

זיכרו

[math]\displaystyle{ y\in f[X]\Rightarrow \exists x\in X: f(x)=y }[/math].

[math]\displaystyle{ x\in f^{-1}[Y]\Rightarrow \exists y\in Y: f(x)=y }[/math].

עדי

תרגיל 4 שאלה 4.6

אם הרכבה של H על G הפיכה, וG הפיכה, אז קיימת G^(-1) ולכן אם נרכיב את H על G על G^(-1) נקבל חזרה את H. למה זה אומר שH הפיכה?

ושאלה נוספת. בתרגול הראנו שאם הרכבה של H על G חח"ע אז G חח"ע. האם זה משפט שאפשר להשתמש בו או שצריך להוכיח את זה? והאם אפשר להכליל את זה ליותר פונקציות - שהרכבה שומרת על התכונות (חח"ע\על) של הפונקצויות ממנה היא מורכבת? (הכוונה לפונ' בצוות ההרכבה - [math]\displaystyle{ h(g(f(w(x)))) }[/math] שומרת על התכונות של w ושל h?

כן, אפשר להשתמש בתכונות מהכיתה: הרכבת חח"ע היא חח"ע, והרכבת על היא על. כמובן שבאינדוקציה זה נכון גם ליותר משתי פונקציות. (אני לא בטוחה לגבי הדוגמא [math]\displaystyle{ h(g(f(w(x)))) }[/math] שומרת על התכונות של w ושל h, כי אתה אומר משהו רק לגבי הפונקציות החיצוניות. כדי שהרכבת 4 הפונ' נהיה חח"ע/על, ארבעתן צריכות להיות חח"ע/על).

לגבי סעיף 6, נכון, ואז אם תשתמש בתכונה שציינת (כמובן שאם G הפיכה אז גם [math]\displaystyle{ G^{-1} }[/math] הפיכה. והפיכות נותנת גם חח"ע וגם על) תקבל [math]\displaystyle{ H=(G^{-1}G)H=G^{-1}(GH) }[/math] ולכן...

עדי

תרגיל 4 שאלה 3

עדי אשמח אם תתקני אותי אם אני טועה. האם כל הסעיפים בשאלה 3 הם הוכחה (פשוט יצא לי שהוכחתי את כולם אני רוצה לדעת אם אני טועה?)

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

(בלי קשר לסעיף זה, במקרה שלא נתון על צריך לקחת בחשבון שלא כל איבר בטווח הוא תמונה).

עדי

פונקציות-תרגיל נוסף לדוגמא

[math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה. נגדיר [math]\displaystyle{ F:P(X)\rightarrow P(Y) }[/math] ע"י

[math]\displaystyle{ \forall A\in P(X)\ F(A)=\{f(a):a\in A\} }[/math]. (כלומר התמונה של כל איבר A ב [math]\displaystyle{ P(X) }[/math] היא קבוצת התמונות שלו ב-f: [math]\displaystyle{ f[A] }[/math].)

הוכח:

א. f חח"ע => F חח"ע,

ב. f על => F על.

פתרון:

א.

[math]\displaystyle{ \underline{F(A)=F(B)}\Rightarrow \{f(a):a\in A\}=\{f(b):b\in B\} }[/math] (כלומר לכל איבר בשמאלית קיים איבר ששווה לו בימנית, ולהיפך).

לכן

[math]\displaystyle{ \forall a\in A\ \exists b\in B:f(a)=f(b)\and \forall b\in B\ \exists a\in A:f(a)=f(b) }[/math]

היות ו-f חח"ע

[math]\displaystyle{ \forall a\in A\ \exists b\in B:a=b \and \forall b\in B\ \exists a\in A:a=b }[/math]

ולכן [math]\displaystyle{ \underline{A=B} }[/math] כנדרש.

ב.

[math]\displaystyle{ \underline{\forall C\in P(Y)}\ \ \ \ \underbrace{\forall c\in C\ \exists a\in A:f(a)=c} }[/math]

[math]\displaystyle{ \ \ \ \ \ \ \ \ \ \ \ \ \ }[/math]היות ו-f על

כלומר, היות וכל איבר ב-Y הוא תמונה תחת f, בפרט כל איבר ב-C הוא תמונה תחת f. ולכן, המקור (תחת F) שיתן את קבוצת התמונות C היא קבוצת המקורות שלו:

[math]\displaystyle{ \underline{\exists A\in P(X):}A=\{a:f(a)\in C\}\ \ and\ \ therefore\ \ \underline{F(A)=}\{f(a):a\in A\}=\{f(a):f(a)\in C\}=\underline{C} }[/math].

תרגיל 4 שאלה 3

הי, למה בסעיף ד' אני לא יכול להפריך באותה צורה שעשית ב-ג'? תודה.

כי שני מקורות יכולים להישלח לאותה תמונה אבל מקור לא יכול להישלח לשתי תמונות. עדי

תרגיל 4 שאלה 4 סעיף א'

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

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

לא, אתה לא יכול להפריך דברים נכונים.

עדי

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

(*==הרכבה)האם לא מספיק ש h*g*f חח"ע בכדי לקבוע כי g*f חח"ע(לפי התכונה שראינו בשיעור)? אם כי בתשובות, כתוב כי מנתון זה מסיקים f חח"ע בלבד

נכון. ראה "הערה" בדיון שכותרתו "תרגיל 4 שאלה 4". עדי

הוכחת פונקציה כ-"על"

עדי שלום!

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

"...ההגדרה של "על": שלכל Y בטווח קיים..."

אולי כדאי שתיתנו לי דוגמא שהסתבכתם (או מס' דוגמאות ככל שתירצו) ואסביר כיצד ליישם עליהן את העיקרון. עדי

תרגיל 6 שאלה 1

היי עדי, קבעתי פונקציה f שמוגדרת מ-R ל [0,1) כך ש: לכל x היא נותנת את 1/x, אבל זה טוב רק לאיברים שמחוץ לקטע [0,1). לאיפה אני אשלח את האיברים שנמצאים בקטע הזה?

האמת שהחומר של עוצמות לא יושב לי טוב בראש. אני לא יודע איך להתחיל לעבוד על שאלה 2 לדוג'. אשמח לכיוון. מרדכי.

עוד לא תירגלנו את כל החומר. בכל מקרה שימו לב לשינוי התחום ל-[math]\displaystyle{ (0,1) }[/math] (אני פשוט לא מאמינה שנספיק להגיע להתאמה בין קטע סגור-סגור לפתוח-סגור).

בכל מקרה את העבודה הקשה עשית כשהעברת קטעים אין סופיים [math]\displaystyle{ [1,\infty) }[/math] ו- [math]\displaystyle{ (-\infty,-1] }[/math] לקטעים סופיים [math]\displaystyle{ (0,1] }[/math] ו-[math]\displaystyle{ [-1,0) }[/math] ע"י [math]\displaystyle{ \frac{1}{x} }[/math].

ראינו שלהעביר קטע סופי לקטע סופי, זה לא בעיה-ע"י כיווץ/מתיחה והזזה.

לכן, פצל את התחומים שלך לקטעים שתוכל להתאים ביניהם:

[math]\displaystyle{ R=(-\infty,-1]\cup(-1,1)\cup[1,\infty)\longrightarrow (0,1)=(0,1/4]\cup(1/4,3/4)\cup[3/4,1) }[/math]

(או בחלוקה לשלישים, או כל חלוקה אחרת).

כעת, התאם את ההזזה שלך [math]\displaystyle{ [1,\infty)\rightarrow (0,1]\rightarrow [3/4,1) }[/math] ע"י כיווץ הקטע [math]\displaystyle{ (0,1] }[/math] פי מינוס ארבע והזזתו 1 קדימה.

אותו הדבר לחלק השלילי: התאם את ההזזה שלך [math]\displaystyle{ (-\infty,-1]\rightarrow [-1,0)\rightarrow (0,1/4] }[/math] ע"י כיווץ הקטע [math]\displaystyle{ [-1,0) }[/math] פי מינוס ארבע.

ההתאמה בין הקטע [math]\displaystyle{ (-1,1) }[/math] לקטע [math]\displaystyle{ (1/4,3/4) }[/math] היא כמובן ע"י כיווץ פי ארבע והזזה של חצי קדימה.

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

שים לב, אם באמצע הסידור שלך יש סידרה אינסופית, למשל (2n,1) לא תוכל לתת אחריה אינדקס לאיברים נוספים. לכן, אם ניסתכל על מישור הטבעיים:

[math]\displaystyle{ \vdots\ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ }[/math]

[math]\displaystyle{ (1,3)\ \ (2,3)\ \ (3,3)\ \ \cdots }[/math]

[math]\displaystyle{ (1,2)\ \ (2,2)\ \ (3,2)\ \ \cdots }[/math]

[math]\displaystyle{ (1,1)\ \ (2,1)\ \ (3,1)\ \ \cdots }[/math]

לא נירצה לסדר שורה אחר שורה, או עמודה אחר עמודה, אלא?

עדי

הוכחת הפונקציה כ"על"

לגבי דוגמה להוכחה של "על", תרגיל 5 שאלה 6D. נשמח אם נוכל לקבל הסבר. תודה.

מעולה! תעלו כמה שיותר, גם אם לא מהש.ב.

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

אשתמש בסעיפים c-d כדי להדגים את שני המיקרים.

[math]\displaystyle{ f(x)=\frac{1}{1+x^2} }[/math]

טיוטא- ניקרא לתמונה [math]\displaystyle{ y }[/math] ונחפש את מקורה [math]\displaystyle{ x }[/math]:

[math]\displaystyle{ y=\frac{1}{1+x^2} }[/math] במקרה של c האיבר y ממשי (כי הטווח הוא R), ונרצה לראות האם המקור x הוא ממשי (כי התחום הוא R).

[math]\displaystyle{ \frac{1}{y}=1+x^2 }[/math] ההופכי של ממשי הוא ממשי

[math]\displaystyle{ \frac{1}{y}-1=x^2 }[/math] ממשי פחות 1 הוא ממשי

[math]\displaystyle{ \sqrt{\frac{1}{y}-1}=x }[/math] אבל לא כל שורש של ממשי הוא ממשי.

לכן, סעיף c הוא לא על. איפה נחפש את הדוגמא הנגדית? כאשר [math]\displaystyle{ \frac{1}{y}-1 }[/math] הוא שלילי, כי שורש של שלילי איננו ממשי:

[math]\displaystyle{ y=2\Rightarrow \frac{1}{y}-1\lt 0\Rightarrow \sqrt{\frac{1}{y}-1}\in C\backslash R }[/math].

אם נשנה למשל את התחום ל-C, או את הטווח לממשיים החיוביים זה יפתור את הבעיה.

בואו נראה כיצד d פותר את הבעיה:

טיוטא:

[math]\displaystyle{ \frac{1}{1+x^2}=y }[/math] כאשר [math]\displaystyle{ y\in(0,1] }[/math]

[math]\displaystyle{ 1+x^2=\frac{1}{y} }[/math] כאשר [math]\displaystyle{ 1/y\in[1,\infty) }[/math]

[math]\displaystyle{ x^2=\frac{1}{y}-1 }[/math] כאשר [math]\displaystyle{ \frac{1}{y}-1\in[0,\infty)=R^+\cup\{0\} }[/math]

[math]\displaystyle{ x=\sqrt{\frac{1}{y}-1} }[/math] כל שורש של ממשי אי שלילי הוא ממשי אי שלילי.

כלומר, גילינו ש-[math]\displaystyle{ \forall y\in(0,1]\ \ \sqrt{\frac{1}{y}-1}\in R^+\cup\{0\} }[/math]

אם האיבר הנ"ל בתחום אז יש איבר בתחום ששווה לו, נקרא לו x, לכן:

[math]\displaystyle{ \underline{\forall y\in(0,1]\ \exists x\in R^+\cup\{0\}:} \sqrt{\frac{1}{y}-1}=x\Rightarrow }[/math]

(וזה החלק של העבודה ב"רוורס". כלומר בודדנו את x כדי לוודא שהטענה נכונה, ועכשיו נבודד בחזרה את y ונטען אותה)

[math]\displaystyle{ \underline{y=}\frac{1}{1+x^2}=\underline{f(x)} }[/math].

עדי

תרגיל 5 שאלה 7 ב'

הי עדי, אנחנו מתקשים להוכיח שg הפיכה ובדקנו גם בתשובות ולא הבנו כל כך, את תוכלי לפרט לנו טיפה יותר? תודה, ישי ואבישי.

בבקשה: מה שאפשר להוציא באופן אוטומטי מהפיכות ההרכבה נתן לנו את הפיכות f. מה שעומד לרשותינו כרגע זה

1. f חח"ע ועל

2. fgf חח"ע ועל

3. gf חח"ע

4. fg על

ואין מסקנות אוטומטיות נוספות, לכן נוכיח לפי הגדרה.

נרצה להוכיח ש-g חח"ע, נתחיל משוויון בין תמונות של a,b תחת g, ונקווה לגלות שוויון בין a ל-b. בדרך נשתמש ב1-4:

[math]\displaystyle{ \underline{g(a)=g(b)} }[/math]

(נרצה להשתמש בחד-חד-ערכיות של gf, ולכן כדי להוסיף את f לפני g נאמר ש-) a ו-b הם תמונות תחת f כי f על, לכן קיימים להם מקורות x ו-y בהתאמה, [math]\displaystyle{ \exists x,y:f(x)=a,f(y)=b }[/math] ולכן:

[math]\displaystyle{ gf(x)=g(f(x))=g(f(y))=gf(y) }[/math]. כעת, gf חח"ע ולכן:

[math]\displaystyle{ x=y }[/math] נפעיל f על שני האגפים, היות ו-f פונקציה נקבל:

[math]\displaystyle{ f(x)=f(y) }[/math], ולכן [math]\displaystyle{ \underline{a=b} }[/math] כנדרש.

נרצה להוכיח ש-g על, נתחיל מאיבר y בטווח של g, ונקווה לגלות שקיים לו מקור תחת g בתחום של g. בדרך נשתמש ב1-4:

מכיוון שההרכבות הנתונות מוגדרות (אחרת לא היו פונקציות ובפרט לא הפיכות) הרי שכל התחומים והטווחים בשאלה זהים:

[math]\displaystyle{ f,g:A\rightarrow A }[/math]

כעת ניקח איבר כללי בטווח g ונראה מה ידוע לנו עליו-

(ה"טיוטא" ששימשה אותי לבניית ההוכחה היא שרוצים [math]\displaystyle{ g(x)=y }[/math], כלומר נירצה לקשר בין x ל-y כאשר מתחילים מ-y.

אבל: [math]\displaystyle{ y=f^{-1}f(y) }[/math] בזכות ההפיכות של f.

אם נעביר את ההופכית של f אגף נקבל [math]\displaystyle{ fg(x)=f(y) }[/math], ולכן כל מה שחסר הוא להשתמש בתכונת העל של fg כדי לומר שלכל z יש מקור x תחת fg ולקרוא ל [math]\displaystyle{ \ \ f(y) }[/math] z (מה שמקשר את y ל-z). עכשיו נשתמש בזה ב"רוורס")

[math]\displaystyle{ \forall y\in A\ \exists z\in A:\ f(y)=z }[/math] כי f פונקציה.

כעת, מכיוון ש-fg על

[math]\displaystyle{ \forall z\in A\ \exists x\in A:\ fg(x)=z }[/math].

בסה"כ קיבלנו (אם לכל y יש z ולכל z יש x, אז בטרנזיטיביות לכל y יש x):

[math]\displaystyle{ \forall y\in A\ \exists x\in A:\ fg(x)=z=f(y) }[/math], ומכיוון ש-f חח"ע:

[math]\displaystyle{ \forall y\in A\ \exists x\in A:\ g(x)=y }[/math] כפי שרצינו.

עדי

שאלה 4 תרגיל 6

עדי בוקר טוב, בשאלה 3 הוכחנו כי העוצמה בפונ' A->B שווה B בחזקת העוצמה של A. בשאלה 4 זה נראה שאנחנו מוכיחים ש P(A) שווה ל 2 בחזקת העוצמה של A עבור מקרה פרטי שב-B יש רק 2 איברים. מה היה קורה אילו היינו לוקחים 3 איברים ב-B, או אפילו קבוצה אינסופית?

בשאלה 3 הוכחנו כי העוצמה של קב' הפונקציות מ-A ל-B שווה לעוצמת B בחזקת העוצמה של A.

בשאלה 4 זה נראה שאנחנו מוכיחים ש [math]\displaystyle{ P(A) }[/math] (שהיא איננה קב' של פונקציות כמו ב3) שווה ל 2 בחזקת העוצמה של A.

2 בחזקת העוצמה של A הוא מקרה פרטי של 3 כאשר ב-B יש 2 איברים. ולכן ניתן להשתמש ב-3 עבור מקרה פרטי זה כדי להראות שוויון בין העוצמה של קב' הפונ' מ-A לשני אייברים, שלפי 3 היא שווה ל-2 בחזקת העוצמה של A, שנרצה להוכיח ב-4 שהיא שווה לעוצמת קב' החזקה של A.

מה הקשר בין שתי הקב'? בקב' הפונ' מ-A לשני אייברים, בכל פונקציה, כל איבר יכול להישלח לאיבר הראשון או השני. בקב' החזקה של A, בכל תת קבוצה, כל איבר יכול להשתייך או לא להשתייך לתת קבוצה. נשתמש בהתאמה זו בדיוק ע"מ להראות שוויון עוצמות.

מה היה קורה אילו היינו לוקחים 3 איברים ב-B, או אפילו קבוצה אינסופית?

לא הבנתי את השאלה, או איך היא קשורה ל-4.

עדי

השאלה שלי בעצם האם ההוכחה תקפה גם כאשר B קב' הגדולה מ-2 איברים או אפילו קב' אינסופית?

אם אתה מתכוון ל-3? התשובה היא כן, [math]\displaystyle{ |\{f:A-\gt B\}|=|B|^{|A|}\ \ \forall A,B }[/math]

4 הוא מקרה פרטי של 3 כש- [math]\displaystyle{ |B|=2 }[/math]. אם תיקח [math]\displaystyle{ B }[/math] מעוצמה אחרת תקבל [math]\displaystyle{ |B|^{|A|} }[/math] שונה מ-[math]\displaystyle{ 2^{|A|} }[/math] ולכן לא רלוונטי ל-[math]\displaystyle{ P(A) }[/math].

עדי

תרגיל 6 שאלה 3

בוקר טוב עדי! לא הבנתי איך פותרים ב"פתרון" את השאלה. ובכלל, איך אפשר להגדיר פונ' הפיכה לפונ' שהיא לא חח"ע ועל!?

ראשית, אתה לא מגדיר פונ' הפיכה לפונ' שהיא לא חח"ע ועל, אתה מגדיר פונקציה הפיכה בין קבוצת פונקציות כלשהן לקבוצה אחרת, במקרה הזה-למכפלה קרטזית של הטווח. הפונקציות {f:A->B} הם המקורות שלך, הם לא בהכרח חחע/על, עליהם נפעיל פונקציה חחע ועל. כלומר ההתאמה בין אוסף הפונקציות {f:A->B} לטווח שבחרנו היא הפיכה, לא בין A לבינו.

במקרה הזה המפתח הוא ש-A ו- B הן סופיות. לכן ניתן למספר את אייברי A: [math]\displaystyle{ \ \ a_1,...,a_m }[/math] ולפי סדר זה להחשיב את סדר התמונות (שהן ב-B): [math]\displaystyle{ f(a_1)=b_{i_1},...,f(a_m)=b_{i_m} }[/math] (לא נקרא להם [math]\displaystyle{ b_1,...,b_m }[/math] כי אלו חלק מאיברי B. אנחנו פשוט רוצים לבחור m מתוכם, אבל לא בהכרח את ה-m הראשונים).

כעת, נשלח כל פונקציה מA לB (את הפונקציה עצמה. f היא מקור, אנחנו לא מגדירים f:A->B, אלא מגדירים לאן f (חחע או לא/על או לא) נישלחת ע"י פונ' g שהיא חח"ע ועל) ל-m-יית התמונות של [math]\displaystyle{ (a_1,...,a_m) }[/math]. מכיוון שתמונת [math]\displaystyle{ a_i }[/math] מוגדרת באופן אחד ויחיד, ומכיוון שכל פונקציה מגדירה m-יית תמונות באופן אחד ויחיד, ההתאמה ל [math]\displaystyle{ B^m }[/math] תהיה חח"ע ועל:

*לכל m-יה ב-[math]\displaystyle{ B^m }[/math] פונקציה השולחת את [math]\displaystyle{ (a_1,...,a_m) }[/math] אליה.

*כמו כן, פונקציות שונות יגדירו m-יות שונות היות ושוני בין פונקציות מתבטא בשוני בתמונות אשר במקרה שלנו מגדירות את ה-m-יה ב-[math]\displaystyle{ B^m }[/math] במקרה בשאלה זו אוסף המקורות הם פונקציות בעצמם

**אם הפונ' מהתחום אינה חח"ע אז ב-m-יה הסדורה שתתקבל ב- [math]\displaystyle{ B^m }[/math] יהיה אינקס חוזר, וזה בסדר גמור, יש איברים שכאלו ב-[math]\displaystyle{ B^m }[/math] ונרצה לכסות גם אותם.

**אם פונ' מהתחום אינה על אז אז ב-m-יה הסדורה ב- [math]\displaystyle{ B^m }[/math] לא יופיעו כל [math]\displaystyle{ b_1,...,b_n\in B }[/math], , וזה בסדר גמור, יש איברים שכאלו ב-[math]\displaystyle{ B^m }[/math] ונרצה לכסות גם אותם.

עדי

תרגיל 6 שאלה 1 ד'

הי עדי, אמנם הסברת את זה בכיתה ובכל זאת לא כל כך הבנתי, יש מצב שאת מסבירה איך לכתוב בצורה מתמטית את התשובה של ההכלה הדו כיוונית? תודה, אבישי.

השימוש הוא לא בהכלה דו כיוונית אלא חד-כיוונית פעמיים. A הוא ריבוע שמכיל את העיגול B, השתמש בריבוע C המוכל ב-B ותקבל: [math]\displaystyle{ C\subseteq B\subseteq A }[/math] אשר גורר כי: [math]\displaystyle{ |C|\leq |B| \leq |A| }[/math]. שיוויון העוצמות בין A ל-C נעשה כמו בכיתה ע"י טרנספורמציות לינאריות בשתי הקואורדינטות. כתוצאה מכך תקבל שב-[math]\displaystyle{ |C|\leq |B| \leq |A| }[/math] הקצוות שווים ולכן גם האמצע. עדי

תרגיל 6 שאלה 2

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

אני מניחה שהתכוונת לתרגיל 7, שאלה 2. הסוגריים תקינים, קודם "וגם q" אח"כ "או r". עדי

תרגיל 7

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

Done

תרגיל 8 שאלה 4 סעיף א'

היי, תוכלי בבקשה להסביר את הפתרון לסעיף הזה?

תודה רבה

תחשוב על השאלה כך: יש כיתה עם שבעה תלמידים (אז אפשר להבדיל בין כל אייברי הקבוצה, כנדרש בשאלה), מהם 4 בנים ו-3 בנות (אז אפשר לחלק את הכיתה לשתי תתי קבוצות זרות ומשלימות, כמו בשאלה). עכשיו זה כמו בחירת הועד (בלי תפקידים, כי סדר הבחירה לא משנה) שפתרנו בכיתה. כלומר, נרצה לבחור ועד בן 3 תלמידים כך שבדיוק שניים מהם בנים (וממילא השלישית תהיה בת) ולכן, שלב I: בחירת תת קב' של 2 מ-4 (4 מעל 2), שלב II: בחירת תת קב' של 1 מ-2 (2 מעל 1), והכפלה בין השלבים. עדי

שאלה בקומבינטוריקה

שאלה ששאלו אותי ולא הצלחתי לפתור.. בכמה דרכים אפשר לסדר 300 כדורים זהים, ב3 תאים כך שכל תא מוגבל לעד 180 כדורים? תודה!

[math]\displaystyle{ x_1+x_2+x_3=300:\ \ 0\leq x_i\leq 180\ \ \forall i }[/math].

נגדיר

[math]\displaystyle{ U=\{x_i\geq 0\} }[/math]

[math]\displaystyle{ \ A_i=\{x_i\geq 181\},\ i=1,2,3 }[/math].

רוצים[math]\displaystyle{ |\cap A_i^c| }[/math] שהם:

[math]\displaystyle{ |\cap A_i^c|=|U|-|\cup A_i|= }[/math]

[math]\displaystyle{ |U|-(|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_3\cap A_2|+|A_1\cap A_2\cap A_3|) }[/math].

[math]\displaystyle{ :|A_i| }[/math]

[math]\displaystyle{ x_1+x_2+x_3=300: x_i\geq 181, x_j\geq 0\ \ \forall j\ne i }[/math]

שקול: [math]\displaystyle{ y_1+y_2+y_3=300-181:\ y_i\geq 0\ \forall i }[/math]

[math]\displaystyle{ :|A_i\cap A_j| }[/math]

[math]\displaystyle{ x_1+x_2+x_3=300: x_i,x_j\geq 181, x_k\geq 0\ \ \forall k\ne i,j }[/math]

שקול: [math]\displaystyle{ \ \ y_1+y_2+y_3=300-2\cdot 181:\ y_i\geq 0\ \forall i }[/math]=> 0 אפשרויות, ובוודאי [math]\displaystyle{ |A_1\cap A_2\cap A_3|=0 }[/math].

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

לכן: [math]\displaystyle{ |\cap A_i^c|=|U|-3|A_i| }[/math] שהם ([math]\displaystyle{ \ 300+3-1 }[/math] מעל [math]\displaystyle{ \ 3-1\ }[/math]) פחות 3 פעמים ([math]\displaystyle{ \ 119+3-1\ }[/math] מעל [math]\displaystyle{ 3-1\ }[/math]).

עדי

רקורסיה משיעור החזרה

from the end of the lesson I didn't understand why this is right: f(n-1)(odd)= f(n-2) I would think it should be f(n-1)(odd)= 10*f(n-2)

There's a difference between adding an [math]\displaystyle{ n-1^{th} }[/math] unknown digit after [math]\displaystyle{ n-2 }[/math] known digits, and adding [math]\displaystyle{ n-2 }[/math] unknown digits before one known digit in the [math]\displaystyle{ n-1 }[/math] possition.

We apply the first one when expressing [math]\displaystyle{ f(n-1) }[/math] - that is, if [math]\displaystyle{ n-2 }[/math] positions are know, then if the [math]\displaystyle{ n-2 }[/math] position is odd, indeed you have [math]\displaystyle{ 10 }[/math] ways to fill the [math]\displaystyle{ n-1^{th} }[/math] position and if it's even you have 5 ways.

We apply the second one when expressing [math]\displaystyle{ f^{(odd)}(n-1) }[/math] - that is, if the [math]\displaystyle{ n-1 }[/math] position is known and odd then you have [math]\displaystyle{ f(n-2) }[/math] ways to fill in the [math]\displaystyle{ n-2 }[/math] previous positions.

Adi