הרצאה 8

תזכורת מההרצאה הקודמת

הערה קטנה: אין לי פה סיכום של ההרצאה הקודמת

משפט

הפיכה אם ורק אם חד-חד ערכית ועל

הוכחה

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

ומכיוון ש נקבל ש

נראה שהיא על:
יהי , נחפש חבר מ שיתאים לו
ניקח את ונראה שהוא מקור ל- תחת ואכן

כעת נוכיח
נניח ש- חח”ע ועל
נראה שקיימת ל הופכי, ע”י זה שנבנה אותה מפורשות

יהי . על לכן קיים עבורו . בנוסף חח”ע ולכן אותו הוא יחיד.
נגדיר לכל

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

בנוסף, לכל אם
אז

בחזרה לענייננו

טענה

תהינה, קבוצות
ו,
אם חח”ע

1. אם חח”ע אז חח”ע
2. אם על, אז על.

הוכחה

נוכיח את החלק הראשון
יהיו כך ש

חח”ע, ולכן
חח”ע ולכן

נוכיח את החלק השני
יהי . על, ולכן קיים עבורו
ו על ולכן קיים עבורו
ולכן:

כלומר גם ההרכבה על

שאלה

אם חח”ע האם בהכרח חח”ע? האם ? מה לגבי על?

טענה

תהינה קבוצות ו, פונקציות הפיכות
אז הפיכה עם, עם ההופכית:

הוכחה

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

ובאופן דומה

עוצמות

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

הגדרה של גודל קבוצה

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

אם אז נאמר
אם לא קיים כזה, נאמר ש- אינסופית.

הגדרה

תהיינה קבוצות. נכתוב ש אם קיימת פונקציה חח”ע

הערה

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

דוגמה

נסמן ב את הטבעיים הזוגיים
בבירור

אבל המוגדרת על ידי חח”ע ולכן

הגדרה

נאמר שקבוצה היא בת מניה אם

כלומר אם קיימת פונקציה חד-חד ערכית

הערה

הטבעיים זו קבוצה בת מנייה כי
המוגדרת
היא חח”ע

בקצרה

• אם קיימת פונקציה חח”ע
• בת מניה אם

בקצרה “במילים”

קבוצה היא בת מניה אם ניתן “למנות” את איבריה לפי סדר
ניתן גם לתאר כ”לאנדקס”, או למצוא חוקיות שתאפשר לעבור על כל איבריה

דוגמה

בת מניה

הוכחה

נזכיר:

נמצא פונקציה חח”ע
למשל:

נראה שהיא חח”ע
יהיו
כך ש

כאשר , לכן מחוקי חזקות של ראשוניים שאנחנו לא באמת יודעים

ולכן

הערה

יש עוד הרבה דוגמאות,

• כל 2 ראשוניים יכלו להתאים במקום
• , תרגיל בית להראות שזה חח”ע

טענה

תהינה קבוצות כך ש ,
אז

הוכחה

תהינה , חח”ע (מהנתון ידוע כי הן קיימות)
ממשפט שראינו. גם חח”ע ולכן

היא בת מניה (בלי הציור מאינפי)

נוכיח בשלבים את אי השוויון הבא

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

ניקח חתך ליחס שקילות (למשל אוסף “שברים מצומצמים עם מכנה חיובי”)
נסמן את החתך שבחרנו ב-
יהי ], אז ל יש נציג יחיד מתאים ב-, נסמנו
כלומר וגם

ועכשיו ניתן (לנסות) להגדיר

ע”י

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

ולכן

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

ולכן חח”ע ולכן
מהתרגיל, קיימת חח”ע
ולכן
ע”י