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

תורת הקבוצות

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

6.3.3. סדרת יצירה

הגדרה

סדרת יצירה עבור איבר plot:\[a\] מתוך plot:\[{X_{B,F}}\] היא סדרה סופית plot:\[{a_1},...,{a_n}\] המקיימת:

  1. plot:\[{a_n} = a\].
  2. לכל plot:\[1 \leqslant i \leqslant n\] מתקיים: plot:\[{a_i} \in B\] או plot:\[{a_i}\] התקבל מאיברים קודמים בסדרה על ידי אחת מהפעולות ב-plot:\[F\].

טענה

בהינתן plot:\[B,F\], לכל איבר plot:\[a\] מתקיים כי plot:\[ \Leftrightarrow a \in {X_{B,F}}\] ל-plot:\[a\] יש סדרת יצירה מתוך plot:\[{X_{B,F}}\].

דגש

סדרת יצירה הינה תמיד סופית אולם איננה יחידה או מינימלית בהכרח.

איך נראה כי plot:\[a \notin {X_{B,F}}\]?

כדי להוכיח כי plot:\[a \notin {X_{B,F}}\] נמצא תכונה T המקיימת:

1. plot:\[a\] לא מקיים את T.

2. כל איברי plot:\[{X_{B,F}}\] מקיימים את T.

הוכחת 1 הינה בדרך כלל מיידית. הוכחת 2 הינה הוכחה באינדוקציית מבנה.

נסמן ב-plot:\[Y\] את קבוצה האיברים המקיימים את plot:\[T\]. עלינו להוכיח כי plot:\[{X_{B,F}} \subseteq Y\].

על פי משפט האינדוקציה מספיק שנוכיח:

  • plot:\[B \subseteq Y\], כלומר כל איברי הבסיס plot:\[B\] מקיימים את T.
  • plot:\[Y\] סגורה תחת plot:\[F\], כלומר כל הפעולות ב-plot:\[F\] משמרות את התכונה plot:\[T\].

דוגמא

תהי שפה של מילים מעל האותיות plot:\[a,b\] שתוגדר כך: plot:\[B = \left\{ {a,b} \right\},F = \left\{ {{f_1},{f_2},{f_3}} \right\}\] כך ש:

plot:\[{f_1}\] מוסיפה plot:\[aba\] מימין למילה. plot:\[{f_2}\] מחליפה את ה-plot:\[aa\] הימני ביותר ב-plot:\[b\] ו-plot:\[{f_3}\] מוחקת את ה-plot:\[bbb\] הימני ביתר. נראה כי plot:\[aba\] איננה שייכת לשפה.

נבחר את התכונה plot:\[T\]: מספר ה-plot:\[a\] במילה הוא אי זוגי.

בהינתן מילה plot:\[w\], נסמן ב-plot:\[\# a\left( w \right)\] את מספר ה-plot:\[a\] ב-plot:\[w\]. כעת:

  1. plot:\[aba\] לא מקימת את plot:\[T\].
  2. נוכיח באינדוקציית מבנה על שפת plot:\[ABA\] את התכונה plot:\[\# a\left( w \right)\] הוא אי זוגי. (חשוב לצין על מי מוכיחים ואת איזה תכונה מוכיחים).

בסיס: המילהplot:\[ab\] : plot:\[\# a\left( {ab} \right) = 1\] אי זוגי.

סגור:

plot:\[{f_1}\]: נניח שהמילה plot:\[w\] מקיימת את plot:\[T\], ונראה כי plot:\[{f_1}\left( w \right)\] מקיימת את התכונה.

plot:\[\# a\left( {{f_1}\left( w \right)} \right) = \# a\left( w \right) + 2\]. לפי הנחת האינדוקציה plot:\[\# a\left( w \right)\] אי זוגי, ולכן plot:\[\# a\left( {{f_1}\left( w \right)} \right)\] גם אי זוגי.

plot:\[{f_2}\]: נניח שהמילה plot:\[w\] מקיימת את plot:\[T\], ונראה כי plot:\[{f_2}\left( w \right)\] מקיימת את התכונה.

plot:\[\# a\left( {{f_2}\left( w \right)} \right) = \# a\left( w \right) - 2 \Rightarrow \]אי זוגי

plot:\[{f_3}\]: נניח שהמילה plot:\[w\] מקיימת את plot:\[T\], ונראה כי plot:\[{f_3}\left( w \right)\] מקיימת את התכונה.

plot:\[\# a\left( {{f_3}\left( w \right)} \right) = \# a\left( w \right) \Rightarrow \]אי זוגי

ניתן להסיק שבכל המילים שבשפת ABA מספר ה-plot:\[a\] אי זוגי ולכן plot:\[aba\] לא מילה בשפה.

תגיות המסמך:

לפרק הקודם6.3.2. הוכחת שימושיות ההגדרה
לפרק הבא6.3.4. דוגמת change
מאת: סטודנטית

הוכחות להגדרה 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 אז צריך לתקן את זה.
מאת: אני

כל הכבוד!!!!

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

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

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

המון תודה

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

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

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

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

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