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

אריתמטיקה של עוצמות

תרגיל. יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.

פתרון.

קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.

נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן ב $f_a:A\rightarrow B$ את הפונקציה המתאימה לאיבר $a\in A$ .

ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא $\forall a\in A : g(a)\neq g_a(a)$ . לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.

תרגיל. הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A

הוכחה. קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציה $f:A\rightarrow \{0,1\}$ (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).

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

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

הגדרה: יהיו שתי קבוצות A,B כך ש $|A|=a, |B|=b$ . אזי נגדיר פעולות בין עוצמות:

$a+b:=|A\cup B|$
$a\cdot b := |A\times B|$
$a^b := |\{f:B\rightarrow A\}|$

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

שימו לב: מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:

$a^0=1$ שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
$0^0=1$ זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
$a\neq 0 \rightarrow 0^a=0$ אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.

תכונות האריתמטיקה

בהנחת אקסיומת הבחירה:

אם a או b מייצגים עוצמה אינסופית אזי $a+b=max\{a,b\}$
אם a או b מייצגים עוצמה אינוספית ושניהם אינם אפס אזי $a\cdot b=max\{a,b\}$
אם $2\leq a$ ו $1\leq b$ ולפחות אחת מבינהם הוא אינסופי אזי $max\{a,2^b\}\leq a^b \leq max\{2^a,2^b\}$

תרגיל ממבחן תשע מועד א (שי סרוסי ואפי כהן)

יהי S יחס על $\mathbb{R}^\mathbb{R}$ (קבוצת כל הפונקציות הממשיות), המוגדר על ידי $(f,g)\in S$ אם"ם לכל $x\in\mathbb{R}$ מתקיים $f(x)-g(x)\in\mathbb{Z}$