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

עוצמות

הגדרה. יהיו A,B שתי קבוצות. אזי:

• אם קיימת פונקציה חח"ע מA לB אזי העוצמה של B גדולה או שווה לזו של A.
• אם קיימת פונקציה חח"ע ועל מA לB אזי אומרים שלA ולB יש אותה עוצמה

דוגמא. יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.

לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n.

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

תרגיל. הוכח שעוצמות הקבוצות הבאות שוות: $\mathbb{N},\mathbb{Z},\mathbb{Q}$

הוכחה: