תורת הקבוצות/עוצמות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "עוצמה של קבוצה תהיינה A,B קבוצות. ותהי F פונקציה F : A → B אם F הינה פונקציה חד-חד ערכית ועל א..." |
בנציון יעבץ (שיחה | תרומות) אין תקציר עריכה |
||
שורה 1:
'''עוצמה''' היא מדד לגודל הקבוצה, גם אם הקבוצה אינסופית. אם הקבוצה סופית, אז עוצמה שלה היא מספר האיברים בה. כך למשל, העוצמה של הקבוצה <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>\aleph_0</math> (קרי: '''אָלֶף אֶפֶס''') הוא הסימון המקובל לעוצמת הקבוצה <math>\N</math>, כלומר <math>|\N|=\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>A,B</math> בנות מנייה, אז <math>A\cup B</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\end{cases}</math>, שהיא גם כן חד חד ערכית ועל. לכן <math>|A\cup B|=\aleph_0</math>.
| |||