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

תוכן שנמחק תוכן שנוסף
שורה 12:
 
'''הוכחה''': יהו <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>.
 
'''משפט''': אם לכל n טבעי, <math>A_n</math> בת מנייה, אז <math>\bigcup^\infty_{n=0}A_n</math> נוסח אחר: איחוד בן מנייה של קבוצות בנות מנייה הוא בן מנייה.
 
'''הוכחה''': לכל n טבעי, תהי <math>f_n:A_n\to\N</math> חד חד ערכית. נגדיר את הפונקציה <math>f:\bigcup^\infty_{n=0}A_n\to\N</math> על פי <math>f(x)=p_n^{f_n(x)}</math> כאשר <math>x\in A_n</math> ו<math>p_n</math> הוא הראשוני הn. מתכונת הפירוק היחיד של המספרים הטבעיים, נקבל שf חד חד ערכית.
 
'''משפט''': חיתוך של קבוצה בת מנייה עם קבוצה כלשהי הוא בן מנייה.
שורה 20 ⟵ 24:
 
'''הוכחה''': נתבונן בקבוצה <math>\N\times\N</math>. נוכל למנות את איבריה כך: [[קובץ:Rationals.png|250px]] לכן <math>|\N\times\N|=\aleph_0</math>. המנייה המתוארת ניתנת לביטוי גם באמצעות הפונקציה: <math>\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.</math>. ראו הוכחה [[w:פונקציית זיווג#היפוך פונקציית הזיווג|כאן]] לכך שהפונקציה חד חד ערכית ועל. כעת, אם <math>f:A\to\N,g:B\to\N</math> חד חד ערכיות, אז הפונקצייה <math>\psi:A\times B\to\N</math> המוגדרת על פי <math>\psi(x,y)=\pi(f(x),g(y))</math> היא חד חד ערכית.
 
===משפטים נוספים על קבוצות בנות מנייה===
'''משפט''': תת קבוצה של קבוצה בת מנייה היא בת מנייה.