הועלה לאתר:  
מספר עמודים: 95
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת הקבוצות

ספר אלקטרוני מאת: ניר אדר

5.3. הגדרה 2 לקבוצה אינסופית – הגדרה לפי תכונה

קבוצה plot:\[A\] היא אינסופית אמ"מ קיימת plot:\[f:A \to A\] חח"ע כך ש-plot:\[f(A) \subset A\],

כלומר קיימת פונקציה מ-A לעצמה שהיא חח"ע אבל לא על.

הוכחה שקבוצת הטבעייםplot:\[\mathbb{N}\] היא אינסופית לפי הגדרה 2:

תהי plot:\[f:\mathbb{N} \to \mathbb{N}\] שתוגדר להיות plot:\[f(n) = n + 1\]. פונקציה זו היא חח"ע, אולם plot:\[f\left( \mathbb{N} \right) = \mathbb{N}\backslash \left\{ 0 \right\}\].

מסקנה

עבור 2 קבוצות אינסופיות plot:\[A\] ו-plot:\[B\], אם plot:\[\left| A \right| = \left| B \right|\] אזי קיימת פונקציהplot:\[f\] חח"ע מ-plot:\[A\] ל-plot:\[B\]שאיננה על.

טענה (בלא הוכחה)

כל ההגדרות לקבוצה אין סופית שקולות.

משפט

אם A היא קבוצה אינסופית, אזי מתקיימות הטענות הבאות:

  1. כל קבוצה B המקיימת plot:\[A \subseteq B\] היא קבוצה אינסופית.
  1. כל קבוצה B שעבורה קיימת פונקציה חח"ע plot:\[f:A \to B\] היא אינסופית.
  1. כל קבוצה B שעבורה קיימת פונקציה על plot:\[f:B \to A\] היא אינסופית.
  1. הקבוצהplot:\[P\left( A \right)\] היא אינסופית.
  1. לכל קבוצה לא ריקהplot:\[B\], הקבוצהplot:\[A \times B\] היא אינסופית.
  1. עבור כל קבוצהplot:\[B\], הקבוצה plot:\[A \cup B\] היא אינסופית.
  1. לכל קבוצה לא ריקה B, הקבוצה plot:\[{A^B}\] (קבוצת הפונקציות מ-B ל-(A היא אינסופית.


הוכחות

1.

נתון ש-plot:\[A\] היא אינסופית ומכאן שקיימת plot:\[f:A \to A\] חח"ע ולא על. נשתמש ב-plot:\[f\] כדי להגדיר פונקציה מ-plot:\[B\] אל plot:\[B\] שהיא חח"ע ולא על.

6.

מכיוון ש-plot:\[A \subseteq A \cup B\] על פי טענה 1 מתקיים כי plot:\[A \cup B\] היא אינסופית.

4.

נוכיח שקיימת פונקציה חח"ע plot:\[f:A \to P\left( A \right)\] ואז על פי טענה 2 יתקיים ש-plot:\[P\left( A \right)\] היא אינסופית.

צריך להתאים כל איבר ב-A לתת קבוצה שונה של plot:\[A\]. נבחר: plot:\[\forall a \in A,f\left( a \right) = \left\{ a \right\}\] - פונקציה חח"ע מ-plot:\[A\] ל-plot:\[P\left( A \right)\].

5.

נוכיח שקיימת פונקציה חח"ע plot:\[f:A \to A \times B\] ועל פי 2 נסיק ש-plot:\[A \times B\] הינה אינסופית. נבחר איבר כלשהו plot:\[b\] השייך ל-plot:\[B\] (קיים כזה), plot:\[\forall a \in A,f(a) = f(a,b)\].

7.

נוכיח שקיימת פונקציה חח"ע מ-plot:\[A\] ל-plot:\[{A^B}\] (לקבוצת הפונקציות מ-plot:\[B\] אל plot:\[A\]).

לפי 2 נקבל ש-plot:\[{A^B}\] הינה אינסופית. צריך להתאים לכל איבר ב-plot:\[A\] פונקציה שונה מ-plot:\[B\] ל-plot:\[A\].

נבחר plot:\[\forall a \in A,f(a) = {g_a}\] כאשר plot:\[{g_a}\] מוגדרת כך: plot:\[\forall b \in B,{g_a}(b) = a, & {g_a}:B \to A\].

משפט

תהי plot:\[\Sigma \] שפה. אם plot:\[\Sigma  \ne \phi \] אזי plot:\[{\Sigma ^*}\]  הינה קבוצה אינסופית.

plot:\[{\Sigma ^*}\] מוגדרת להיות קבוצת כל המילים הסופיות הנבנות מאותיות plot:\[\Sigma \].

כדי להוכיח משפט זה, מספיק שנראה כי קיימת plot:\[f:\mathbb{N} \to {\Sigma ^*}\] חח"ע.



תגיות המסמך:

לפרק הקודם5.2. הגדרה 1 לקבוצה אינסופית
לפרק הבא5.4. קבוצה בת מניה
מאת: סטודנטית

הוכחות להגדרה 2

אשמח להגדרות פורמליות מפורטות עבור המשפט. תודה רבה
מאת: ילדה

תודה רבה!

תודה על ההסבר המצוין
מאת: אני

תודה

מברוק! תודה
מאת: ברק

יש לכם טעות

בסגור הטרנזיטיבי שהתקבל אצלכם, קיימים הזוגות <4,1> ו-<1,4>, אבל מתוקף היותו טרנזיטיבי הוא חייב גם להכיל את <1,1> ו-<4,4>. ההגדרה של טרנזיטיביות לא מחייבית a,b,c שונים.

כנ"ל לגבי <2,3> ו-<4,2> - חייב להימצא הזוג הסדור <4,3>.
מצאתי עוד 3 דוגמאות כאלה..
מאת: יואב

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...
מאת: יואב

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...
מאת: אמיר

קבוצה סופית

מישו יכול להעלות את ההוכחה לכך שכל תת קבוצה של קבוצה סופית היא סופית ? זה ברור אבל אני צריך את ההגדרה הפורמלית לזה ..
מאת: רעות

תודה רבה

תודה רבה ספר מעולה מסביר מצויין שתצליח תמיד :-)
מאת: עומר

סגור טרנזיטיבי

ניר אתה בטוח ש- (4,2) הוא חלק מהסגור הטרנזיטיבי (משפט 3 מלמעלה)?
אני לא סגור על החומר, אבל אני לא חושב שזה נכון...
מאת: אחד שלומד

יפה מאוד אך ישנן כמה טעויות

ישנן כמה טעויות (קריטיות להוכחה) כשעברתי על החומר,
למשל בהוכחה ש R* טרנזיטיבית (סעיף 2) יש בלבול שלם בין x,y,z אז צריך לתקן את זה.
מאת: אני

כל הכבוד!!!!

כל הכבוד על העבודה שעשית כאן!!!
נורא עוזר!!!!
מאת: אני

תודה רבה רבה רבה רבה!

כל הכבוד על העלאת הסיכום המעולה הזה לטובת כולם!
מאת: אלעד

המון תודה

וואו, חומר כל כך ברור ומסודר!
עברתי על עשרות ספרים ואף אחד לא ברור וענייני כמו זה - פשוט כל הכבוד!
תודה, תודה תודה!
מאת: אולג

תודה רבה!!!!!!!!

אף פעם לא ברור לי מה האינטרס של אנשים כמוך, להעלות חומר ממש מועיל לאינטרנט בחינם...

בכל אופן, רציתי לומר: כל הכבוד ותודה רבה, הסיכומים שלך מאוד עזרו לי ואני מאוד מעריך את הזמן והמאמץ שהושקע בהם.

והלוואי ויהיו רבים כמוך...
שיתוף:
| עוד