תורת הקבוצות

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

6.3.3. סדרת יצירה

הגדרה

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

$plot:\[{a_n} = a\]$ .
לכל $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\]$ . כעת:

$plot:\[aba\]$ לא מקימת את $plot:\[T\]$ .
נוכיח באינדוקציית מבנה על שפת $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

מאת: סטודנטית

15/12/2020 19:15

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

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

מאת: ילדה

17/4/2018 19:45

תודה רבה!

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

מאת: אני

24/12/2017 13:48

תודה

מברוק! תודה

מאת: ברק

22/12/2017 18:24

יש לכם טעות

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

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

מאת: יואב

10/12/2017 22:33

מבלבל

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

מאת: יואב

10/12/2017 22:32

מבלבל

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

מאת: אמיר

11/1/2017 13:15

קבוצה סופית

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

מאת: רעות

26/11/2016 22:48

תודה רבה

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

מאת: עומר

1/6/2013 21:30

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

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

מאת: אחד שלומד

8/3/2013 11:34

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

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

מאת: אני

26/11/2011 12:01

כל הכבוד!!!!

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

מאת: אני

20/11/2011 20:01

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

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

מאת: אלעד

8/7/2011 20:08

המון תודה

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

מאת: אולג

6/4/2010 21:54

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

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

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

והלוואי ויהיו רבים כמוך...

דיווח על הפרת זכויות יוצרים