GRE · GRE Subject Test · GRE Mathematics · נושא 20
הכנה למבחן GRE לתואר ראשון. מטרות מקומיות בתוך היקף ETS הנבדק; זהו הוראה מקורית, ולא מבחן רשמי או חיזוי ציון.
דרישות סביר: פעולות על קבוצות, כמותנים, פונקציות והוכחות יסודיות.
קדמת תמונה: הקבוצה של כניסות שהפלט שלהן נמצא בקבוצת מטרה מצוינת.
יחס שוויון: יחס שהוא רקסיבי, סימטרי וטרנזיטיבי.
| English | עברית |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | תמונה הופכת |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | יחס שקילות |
עבור f:X→Y ו-A⊆X, התמונה f(A) מורכבת מכל הפלטות f(a) כאשר a ב-A. נקודה נמצאת ב-f(A∪B) אם ורק אם היא נובעת מ-A או מ-B, ולכן f(A∪B)=f(A)∪f(B). אם A⊆B, אז f(A)⊆f(B). עבור חתך, רק f(A∩B)⊆f(A)∩f(B) הוא אוטומטי; אותה תמונה עשויה לבוא מכניסות שונות. השתמשו ב-f(x)=x², A={−1}, B={1}; התמונה השמאלית היא ריקה בעוד החתך הימני הוא {1}.
קדמות תמונה מתנהגות אחרת. עבור C⊆Y, f⁻¹(C) כאן מייצגת את קבוצת הכניסות שנשלחות לתוך C, גם אם f אין פונקציה הפוכה. שייכות לשתי קדמות תמונה פירושה אותה כניסה מדויקת שמתמפה לשתי קבוצות המטרה. כתוצאה מכך, קדמות תמונה שומרות על איחוד, חתך ומשלים ביחס לתחום/קודומיין המצוינים. אל תעבירו משפט על קדמות תמונה לתמונות. אם f היא חד-חד-על-אחת, חתכי התמונה הופכים לשווים, מכיוון שתמונות שוות כופלות כניסה משותפת.
יחס R על X הוא רקסיבי כאשר xRx לכל x, סימטרי כאשר xRy גורר yRx, וטרנזיטיבי כאשר xRy ו-yRz גוררים xRz. כל שלושת האלמנטים יוצרים יחס שוויון; מחלקות השוויון מפצלות את X. על שלמים, xRy כאשר x ו-y יש שארית זהה מודולו ארבע נותן ארבע מחלקות. היחס |x−y|≤1 הוא רקסיבי וסימטרי אך לא טרנזיטיבי: 0R1 ו-1R2 בעוד ש-0 אינו קשור ל-2. בדיקה של דיאגרמה אחת או שתי תכונות אינה מספקת.
הימל P⇒Q היא שקולה בדיוק כאשר P אמת ו-Q שקר. לכן השללת P⇒(Q∧R) היא P∧(¬Q∨¬R), ולא ¬P⇒(¬Q∧¬R). שלילת “כל x יש לו תכונה A” נותנת “קיים x ללא A”; שלילת “קיים x” נותנת “כל x אינו”. נגד-דוגמה יכולה לשלול טענה אוניברסלית, בעוד לדוגמאות אין יכולת להוכיח אותה. הכמותנים שומרים על הסדר שלהם בעת שלילה פרטנית: ¬(∀x∃y S(x,y)) היא ∃x∀y ¬S(x,y).
תן ל-f למפות גם את a וגם את b לתווית L. עם A={a}, B={b}, מתקיים f(A∩B)=∅ בעוד ש-f(A)∩f(B)={L}. עבור xRy המוגדר על ידי x=y או x=−y ב-R, הרפלקסיביות והסימטריה נובעות ישירות, ושתי שינוי סימן עדיין נותן z=±x, מה שמוכיח טרנזיטיביות. המחלקות הן {x,−x}, כאשר {0} היא סוגליה. statement שגויה "כל קובץ מאוחזב יש לו hash" פירושה לפחות קובץ אחד שאינו מאוחזב no hash; היא אינה פירושה שכל הקבצים חסרי hash.
f⁻¹(C) יכולה להציג קבוצת קדמויות ללא פונקציה הפוכה. יחס הרפלקסיבי וסימטרי עשויStill to fail טרנזיטיביות. שלל את כל הביטוי לפני שאתה מצמצם את חלקיו.
הוכיחו $f(A\cap B)\subseteq f(A)\cap f(B)$. נתנו דוגמה להכללה מחמירה. תחת מה הנחה נוספת על f השוויון נובע לכל A ו-B?
אם $y=f(x)$ עבור $x\in A\cap B$, אז x שייך לכל קבוצה, ולכן y שייך לתמונה של כל אחת. עבור החמרה, מתמפו a,b שונים לאותה c וקחו $A=\{a\}$, $B=\{b\}$. התמונה השמאלית היא ריקה והחתך הימני הוא $\{c\}$. אם f היא חד-חד-על-אחת ו-$y=f(a)=f(b)$ עם $a\in A,b\in B$, החד-חד-על-אחת נותנת a=b בחתך, ומוכיחה הכללה הפוכה. מאידך, דוגמת הסינגלט מראה שהשוויון לכל זוג כופל חד-חד-על-אחת.
על המספרים השלמים הגדר $aRb$ כאשר $a-b$ מתחלק ב-4. הוכח שזו יחס שוויון ותיאור כל מחלקה. שלל: "לכל מספר שלם n קיים מספר שלם m גדול מ-n עם התכונה P."
הפליטות משתמשת ב-$a-a=0$; הסימטריה משתמשת בשליל כפולה של ארבע; האטרנטיביות משתמשת בסכום של שתי כפולות כאלו. המחלקות הן ארבע שאריות מודולו ארבע; מחלקתו של a היא $a+4\mathbb Z$. השלל הוא: קיים מספר שלם n כך שכל מספר שלם m גדול מ-n אינו מקיים את P. באופן שקול $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. טענה זו אינה טוענת שה-P נכשל לכל מספר, ואינה טוענת שמ-m קטן או שווה ל-n לכל m.
לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.
טוען נושאים…