תורת הקבוצות

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

6.3.6. דוגמא מסכמת – קבוצת מחרוזות מעל S, T

העולם $plot:\[A\]$ יוגדר להיות כל המחרוזות הסופיות מעל $plot:\[s,t\]$ , כלומר הקבוצה $plot:\[{\left\{ {s,t} \right\}^*}\]$ .

הבסיס $plot:\[B\]$ הינו $plot:\[\left\{ {\varepsilon ,st,ts} \right\}\]$ , וקבוצת הפעולות $plot:\[F\]$ הינה $plot:\[F = \left\{ {{f_1}\left( { \cdot , \cdot } \right),{f_2}\left( { \cdot , \cdot } \right),{f_3}\left( \cdot \right)} \right\}\]$ , כאשר

$plot:\[\begin{gathered} {f_1}\left( {\alpha ,\beta } \right) = s\alpha \beta t,{f_2}\left( {\alpha ,\beta } \right) = t\alpha \beta s \hfill \\ {f_3}\left( \alpha \right) = \left\{ {\begin{array}{*{20}{c}} {\alpha {\text{ without the last }}st} \hfill & {\alpha {\text{ contains }}st{\text{ that are not as the first 2 letters}}} \hfill \\ \alpha \hfill & {{\text{else}}} \hfill \\ \end{array} } \right. \hfill \\ \end{gathered} \]$

לדוגמא: $plot:\[{f_3}\left( {stt} \right) = stt,{f_3}\left( {ttts} \right) = ttts,{f_3}\left( {stst} \right) = st\]$ .

הגדרנו כאן קבוצה אינדוקטיבית מעל $plot:\[B,F\]$ : $plot:\[{X_{s,t}}\]$

נראה עבור מילה מסויימת כי היא נמצאת ב- $plot:\[{X_{s,t}}\]$ . עושים זאת על ידי הצגת סדרת יצירה המייצרת את המילה. תהי המילה $plot:\[\alpha = tststs\]$ . למילה זו אינסוף סדרות יצירה. אחת מהן לדוגמא:

$plot:\[st\xrightarrow[{{f_2}\left( {\varepsilon ,st} \right)}]{}tsts\xrightarrow[{{f_1}\left( {tsts,\varepsilon } \right)}]{}ststst\xrightarrow[{f2}]{}tstststs\xrightarrow[{{f_3}}]{}tststs\]$

נשים לב:

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

איך מראים ש- $plot:\[\alpha \notin {X_{B,F}}\]$ ? נמצא תכונה T המקיימת כי $plot:\[\alpha \]$ לא מקיים את T וגם כל איברי $plot:\[{X_{B,F}}\]$ מקיימים את T. נגדיר קבוצה $plot:\[Y\]$ שאיבריה הם כל איברי $plot:\[A\]$ המקיימים את התכונה ואז נדרוש $plot:\[{X_{B,F}} \subseteq Y\]$ אבל $plot:\[\alpha \notin Y\]$ . לפי משפט ההוכחה באינדוקציה, על מנת להוכיח שקבוצה $plot:\[Y\]$ מקיימת כי $plot:\[{X_{B,F}} \subseteq Y\]$ מספיק להראות כי: $plot:\[B \subseteq Y\]$ וכי $plot:\[Y\]$ סגורה ל- $plot:\[F\]$ .

טענה

נטען: $plot:\[tsst \ne {X_{s,t}}\]$

הוכחה: התכונה T – אם $plot:\[\alpha \]$ מתחיל ב- $plot:\[t\]$ אזי הוא מסתיים ב- $plot:\[s\]$ .

נוכיח באינדוקציית מבנה של איבר ב- $plot:\[{X_{s,t}}\]$ מקיים את T.

בסיס: נעבור על כל איברי הבסיס $plot:\[B\]$ :

$plot:\[\varepsilon \]$ מקיים את T באופן ריק. $plot:\[st\]$ מקיים את T באופן ריק. $plot:\[ts\]$ מקיים את T.

סגור: נעבור על כל הפעולות ב-F ונראה כי $plot:\[Y\]$ סגור לפעולות.

$plot:\[{f_1}\left( { \cdot , \cdot } \right)\]$ - אם $plot:\[\alpha ,\beta \in Y\]$ אז $plot:\[{f_1}\left( {\alpha ,\beta } \right) = s\alpha \beta t \in Y\]$ .

$plot:\[{f_2}\left( { \cdot , \cdot } \right)\]$ - אם $plot:\[\alpha ,\beta \in Y\]$ אזי $plot:\[{f_2}\left( {\alpha ,\beta } \right) = t\alpha \beta s \in Y\]$ .

$plot:\[{f_3}\left( \cdot \right)\]$ - נניח כי $plot:\[\beta \in Y\]$ ויהי $plot:\[\alpha = {f_3}\left( \beta \right)\]$ . נפריד למקרים:

אין כלל השמטת רצף $plot:\[st\]$ . במקרה זה $plot:\[\alpha = \beta \]$ ולכן $plot:\[\alpha = \beta \in Y\]$ .
השמטת רצף $plot:\[st\]$ מהאמצע: $plot:\[\beta = {\beta _1}st{\beta _2}\]$ $plot:\[\left( {{\beta _1},{\beta _2} \ne \varepsilon } \right)\]$ ואז $plot:\[\alpha = {\beta _1}{\beta _2}\]$ . ההתחלה והסוף של $plot:\[\beta \]$ נשמרו ב- $plot:\[\alpha \]$ ולכן $plot:\[\alpha \in Y\]$ .
השמטת רצף $plot:\[st\]$ מהסוף - $plot:\[\alpha = {\beta _1}, & \beta = {\beta _1}st\]$ .

צריך להוכיח כי אם $plot:\[\alpha \]$ מתחיל ב- $plot:\[t\]$ אז הא מסתיים ב- $plot:\[s\]$ . נוכיח כי לא ייתכן ש- $plot:\[\alpha \]$ מתחיל ב- $plot:\[t\]$ ולכן הטענה תתקים באופן ריק.

נניח בשלילה כי $plot:\[\alpha \]$ מתחיל ב- $plot:\[t\]$ . $plot:\[\alpha = {\beta _1}\]$ ולכן $plot:\[{\beta _1}\]$ מתחיל ב- $plot:\[t\]$ . לפי הגדרה $plot:\[\beta = {\beta _1}st\]$ ולכן גם $plot:\[\beta \]$ מתחיל ב- $plot:\[t\]$ אבל גם מסתיים ב- $plot:\[t\]$ , בניגוד להנחת האינדוקציה כי $plot:\[\beta \in Y\]$ .

הראנו כי $plot:\[{X_{s,t}} \subseteq Y\]$ . נראה כעת כי $plot:\[\alpha \]$ לא מקיים את T:

$plot:\[tsst\]$ מתחיל ב- $plot:\[t\]$ ומסתיים ב- $plot:\[t\]$ $plot:\[ \Leftarrow \]$ לא מקיים את $plot:\[T\]$ $plot:\[tsst \notin {X_{s,t}} \Leftarrow tsst \notin Y \Leftarrow \]$ .

דוגמא

תהיינה $plot:\[{S_1} = {X_{{B_1},{F_1}}},{S_2} = {X_{{B_2},{F_2}}}\]$ כך ש- $plot:\[{S_1} = {S_2}\]$ .

הוכיחו: $plot:\[\underbrace {{X_{{B_1} \cup {B_2},{F_1} \cup {F_2}}}}_{{S_3}} = {S_1} = {S_2}\]$ .

נראה $plot:\[{S_1} \subseteq {S_3}\]$ : ניתן להסתפק בכך שכל סדרת יצירה ב- $plot:\[{S_1}\]$ היא גם סדרת יצירה ב- $plot:\[{S_3}\]$ לפי הגדרת האיחוד.

נראה $plot:\[{S_3} \subseteq {S_1}\]$ : (באינדוקציה)

בסיס: לכל $plot:\[b \in {B_1} \cup {B_2}\]$ , נראה כי $plot:\[b \in {S_1}\]$ .

$plot:\[b \in {B_1} \cup {B_2}\]$ , ולכן: $plot:\[b \in {S_1} \Leftarrow b \in {B_1}\]$ כי $plot:\[{B_1} \subseteq {S_1}\]$ .

או $plot:\[b \in {S_2} \Leftarrow b \in {B_2}\]$ כי $plot:\[{B_2} \subseteq {S_2}\]$ ולפי הנתון $plot:\[{S_1} = {S_2}\]$ ולכן $plot:\[b \in {S_1}\]$ .

סגור: $plot:\[{a_1},...,{a_n} \in {S_1}\]$ . נראה סגירות של אגף ימין $plot:\[\left( {{S_1}} \right)\]$ לפעולות של הקבוצה באגף שמאל $plot:\[\left( {{S_3}} \right)\]$ .

תהי $plot:\[f \in {F_1} \cup {F_2}\]$ . אם $plot:\[f \in {F_1}\]$ אזי $plot:\[f\left( {{a_1},...,{a_n}} \right) \in {S_1}\]$ כי $plot:\[{S_1}\]$ סגורה לפעולות $plot:\[{F_1}\]$ . אם $plot:\[f \in {F_2}\]$ אזי $plot:\[f\left( {{a_1},...,{a_n}} \right) \in {S_2}\]$ כי $plot:\[{S_2}\]$ סגורה לפעולות $plot:\[{F_2}\]$ ולפי הנתון $plot:\[{S_1} = {S_2}\]$ ולכן $plot:\[f\left( {{a_1},...,{a_n}} \right) \in {S_1}\]$ .

EOF

לפרק הקודם6.3.5. משפט הרקורסיה

מתמטיקה דיסקרטית למסמכים נוספים בתחום

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

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

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

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

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

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

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