תורת הקבוצות/עוצמות: הבדלים בין גרסאות בדף

'''עוצמה''' היא מדד לגודל הקבוצה, גם אם הקבוצה אינסופית. אם הקבוצה סופית, אז עוצמה שלה היא מספר האיברים בה. כך למשל, העוצמה של הקבוצה <math>\{0,1,2\}</math> היא 3, ונסמן <math>|\{0,1,2\}|=3</math>. נאמר שלשתי קבוצות יש את אותה עוצמה, אם הן שקולות, כלומר יש פונקציה חד חד ערכית ועל ביניהן. כך למשל, הפונקציה <math>S:\N\to\N\setminus\{0\}</math> המוגדרת על פי <math>S(n)=n+1</math>, היא חד חד ערכית ועל, לכן נאמר כי <math>|\N|=|\N\setminus\{0\}|</math>. קבוצה תיקרא '''אינסופית''' אם יש לה תת קבוצה ממש בעלת אותה עוצמה. הפונקציה שהבאנו קודם מראה כי קבוצת המספרים הטבעיים אינסופית.

<math>\aleph_0</math> (קרי: '''אָלֶף אֶפֶס''') הוא הסימון המקובל לעוצמת הקבוצה <math>\N</math>, כלומר <math>|\N|=\aleph_0</math>. נאמר כי קבוצה היא '''בת מנייה''', אם היא סופית, או שעוצמתה <math>\aleph_0</math>. בשני המקרים יש פונקציה חד חד ערכית מהקבוצה לקבוצת המספרים הטבעיים, וכן אם יש פונקציה חד חד ערכית מהקבוצה לקבוצת המספרים הטבעיים, אז יש שתי אפשרויות: או שהפונקציה על ואז עוצמת הקבוצה <math>\aleph_0</math>, או שהפונקציה אינה על ואז הקבוצה סופית או שיש פונקציה אחרת על. בין כה וכה הקבוצה בת מנייה, לכן נוכל להחליף את ההגדרה בזו: קבוצה היא בת מנייה אם ורק אם יש פונקציה חד חד ערכית ממנה לקבוצת המספרים הטבעיים. כך למשל, <math>\Z</math>, קבוצת המספרים השלמים, היא בת מנייה, כי הפונקציה <math>f:\Z\to\N</math> המוגדרת <math>f(x)=\begin{cases}2x&&x\geq0\\2|x|+1&&x<0\end{cases}</math> היא חד חד ערכית ועל, לכן <math>|\Z|=|\N|=\aleph_0</math>. השם '''קבוצה בת מנייה''' בא לומר שניתן למנות את איברי הקבוצה בזה אחר זה (כלומר, לשכנם בסדרה) בלי לפספס אף איבר. אין משמעות העניין שהמנייה חייבת להסתיים מתישהו, אלא שכל איבר יגיע לאחר מספר סופי של צעדים. המנייה תיעשה על פי <math>f(0),f(1),f(2),...</math> כאשר <math>f:\N\to A</math> היא חד חד ערכית ועל (קיימת כזו כי הקבוצה בת מנייה). אם A סופית, כמובן שניתן למנות את איבריה, בכל סדר שנרצה, ותמיד לא נפספס אף איבר. גם ההיפך נכון - אם ניתן למנות איברי קבוצה בצורה הזו, אז יש פונקציה חד חד ערכית ועל ממנה לקבוצת המספרים הטבעיים: נניח שהמנייה היא <math>a_0,a_1,a_2,...</math> כאשר לכל i, <math>a_i\in A</math>. אז הפונקציה <math>f(a_n)=n</math> היא חד חד ערכית ועל (אם <math>f(a_n)=f(a_m)</math> אז בהכרח <math>n=m</math>. כמו כן, כל מספר טבעי יופיע בתמונת הפונקציה, כי הקבוצה אינסופית והמנייה לא מדלגת על אף מספר טבעי), ואז <math>|A|=\aleph_0</math>.

===איחוד, חיתוך, ומכפלה קרטזית של קבוצות בנות מנייה===

'''הוכחה''': יהו <math>f:A\to\N,g:B\to\N</math> חד חד ערכיות ועל. נגדיר פונקציות <math>p:\N\to2\N,q:\N\to2\N+1</math> (<math>2\N=\{2n:n\in\N\}</math>, וכן <math>2\N+1=\{2n+1:n\in\N\}</math>) על פי <math>p(n)=2n,q(n)=2n+1</math>. שתי פונקציות אלו חד חד ערכיות ועל, ותמונותיהן זרות, לכן נוכל להגדיר פונקציה <math>\psi:A\cup B\to\N</math> על פי <math>\psi(x)=\begin{cases}(p\circ f)(x)&&x\in A\\(q\circ g)(x)&&x\in B\setminus A\end{cases}</math>, שהיא גם כן חד חד ערכית ועל. לכן <math>|A\cup B|=\aleph_0</math>.