Theory Of Sets

‫‪  [email protected]‬‬

‫ניר אדר‬

‫גירסה ‪6.12.2003 – 1.00‬‬

‫תורת הקבוצות‬ ‫ניר אדר‬

‫מסמך זה הורד מהאתר ‪.http://underwar.livedns.co.il‬‬ ‫אין להפיץ מסמך זה במדיה כלשהי‪ ,‬ללא אישור מפורש מאת המחבר‪.‬‬ ‫מחבר המסמך איננו אחראי לכל נזק‪ ,‬ישיר או עקיף‪ ,‬שיגרם עקב השימוש במידע המופיע במסמך‪ ,‬וכן‬ ‫לנכונות התוכן של הנושאים המופיעים במסמך‪ .‬עם זאת‪ ,‬המחבר עשה את מירב המאמצים כדי לספק את‬ ‫המידע המדויק והמלא ביותר‪.‬‬ ‫כל הזכויות שמורות לניר אדר‬ ‫‪ ‬‬ ‫‪Nir Adar ‬‬ ‫‪Email: [email protected]  ‬‬ ‫‪Home Page: http://underwar.livedns.co.il ‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫אנא שלחו תיקונים והערות אל המחבר‪.‬‬

‫‪ 1‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪ .1‬תוכן עניינים‬

‫‪.1‬‬

‫תוכן עניינים‬

‫‪2‬‬

‫‪.2‬‬

‫מושגי יסוד בתורת הקבוצות‬

‫‪6‬‬

‫‪.2.1‬‬

‫הגדרת קבוצה‬

‫‪6‬‬

‫‪.2.2‬‬

‫הקבוצה הריקה‬

‫‪7‬‬

‫‪.2.3‬‬

‫גודל של קבוצה‬

‫‪7‬‬

‫‪.2.4‬‬

‫גרירה לוגית ואמ"מ‬

‫‪7‬‬

‫‪.2.5‬‬

‫שייכות‬

‫‪8‬‬

‫‪.2.6‬‬

‫שוויון קבוצות‬

‫‪8‬‬

‫‪.2.7‬‬

‫תתי קבוצות‬

‫‪9‬‬

‫‪.2.8‬‬

‫דיאגרמת ון‬

‫‪10‬‬

‫פעולות על קבוצות‬

‫‪11‬‬

‫‪.3‬‬ ‫‪.3.1‬‬

‫איחוד קבוצות‬

‫‪11‬‬

‫‪.3.2‬‬

‫חיתוך קבוצות‬

‫‪11‬‬

‫‪.3.3‬‬

‫תכונות של חיתוך ואיחוד קבוצות‬

‫‪12‬‬

‫‪.3.4‬‬

‫נכון ‪ /‬לא נכון‬

‫‪12‬‬

‫‪.3.5‬‬

‫זרות הדדית‬

‫‪13‬‬

‫‪.3.6‬‬

‫הפרש בין קבוצות‬

‫‪14‬‬

‫‪.3.7‬‬

‫הפרש סימטרי‬

‫‪15‬‬

‫‪.3.8‬‬

‫משלים‬

‫‪15‬‬

‫‪.3.9‬‬

‫חוקי דה מורגן‬

‫‪17‬‬

‫‪.3.10‬‬

‫חוקי דיסטריבוטיביות‬

‫‪17‬‬

‫‪.3.11‬‬

‫חוקי ספיגה‬

‫‪18‬‬

‫‪.3.12‬‬

‫איחוד על קבוצות‬

‫‪18‬‬

‫‪.3.13‬‬

‫חיתוך על קבוצות‬

‫‪18‬‬

‫‪.3.14‬‬

‫תכונות של איחוד וחיתוך על קבוצות‬

‫‪19‬‬

‫‪.3.15‬‬

‫חוקי דה מורגן לגבי איחוד וחיתוך על קבוצות‬

‫‪19‬‬

‫‪.3.16‬‬

‫קבוצת החזקה‬

‫‪20‬‬

‫‪ 2‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬ ‫‪.3.17‬‬

‫בניה פורמלית לקבוצות‬

‫‪21‬‬

‫‪.3.18‬‬

‫הקבוצה האוניברסאלית‬

‫‪23‬‬

‫‪.3.19‬‬

‫זוג סדור‬

‫‪23‬‬

‫‪.3.20‬‬

‫מכפלה קרטזית‬

‫‪26‬‬

‫‪.4‬‬

‫רלציות‬

‫‪28‬‬

‫‪.4.1‬‬

‫הגדרות בסיסיות‬

‫‪28‬‬

‫‪.4.2‬‬

‫הרכב רלציות‬

‫‪31‬‬

‫‪.4.3‬‬

‫תכונות של יחסים‬

‫‪32‬‬

‫פונקציות‬

‫‪35‬‬

‫‪.5‬‬ ‫‪.5.1‬‬

‫הגדרות‬

‫‪35‬‬

‫‪.5.2‬‬

‫שאלות קומבינטוריות‬

‫‪36‬‬

‫‪.5.3‬‬

‫הפונקציה ההופכית‬

‫‪37‬‬

‫‪.5.4‬‬

‫תכונות של רלציה מעל קבוצה ‪A‬‬

‫‪39‬‬

‫‪.5.5‬‬

‫רלציות מיוחדות‬

‫‪39‬‬

‫‪.5.5.1‬‬

‫יחסי סדר‬

‫‪39‬‬

‫‪.5.5.2‬‬

‫יחס שקילות‬

‫‪40‬‬

‫‪.5.5.3‬‬

‫דוגמאות‬

‫‪40‬‬

‫‪.5.6‬‬

‫חזקות של רלציה‬

‫‪41‬‬

‫‪.5.7‬‬

‫הסגור של רלציה ביחס לתכונה‬

‫‪44‬‬

‫‪.5.7.1‬‬

‫סגור רפלקסיבי‬

‫‪45‬‬

‫‪.5.7.2‬‬

‫סגור סימטרי‬

‫‪45‬‬

‫‪.5.7.3‬‬

‫סגור א‪-‬רפלקסיבי‬

‫‪46‬‬

‫‪.5.7.4‬‬

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

‫‪46‬‬

‫‪.5.8‬‬

‫רלצית שקילות‬

‫‪50‬‬

‫‪.5.8.1‬‬

‫מחלקת שקילות‬

‫‪50‬‬

‫‪.5.8.2‬‬

‫למה ‪1‬‬

‫‪51‬‬

‫‪.5.8.3‬‬

‫הצגת רלצית שקילות כגרף‬

‫‪53‬‬

‫‪.5.8.4‬‬

‫קבוצת המנה‬

‫‪54‬‬

‫‪.5.8.5‬‬

‫למה ‪2‬‬

‫‪54‬‬

‫‪.5.8.6‬‬

‫למה ‪3‬‬

‫‪54‬‬

‫‪.5.8.7‬‬

‫חלוקה‬

‫‪55‬‬

‫‪.5.8.8‬‬

‫דוגמאות‬

‫‪57‬‬

‫‪ 3‬‬

‫ניר אדר‬ ‫‪.6‬‬

‫‪  [email protected]‬‬

‫עוצמות‬

‫‪59‬‬

‫‪.6.1‬‬

‫הקדמה לעוצמות‬

‫‪59‬‬

‫‪.6.2‬‬

‫הגדרה ‪ 1‬לקבוצה אינסופית‬

‫‪61‬‬

‫‪.6.3‬‬

‫הגדרה ‪ 2‬לקבוצה אינסופית – הגדרה לפי תכונה‬

‫‪62‬‬

‫‪.6.4‬‬

‫קבוצה בת מניה‬

‫‪64‬‬

‫‪.6.5‬‬

‫משפט קנטור‬

‫‪71‬‬

‫‪.6.5.1‬‬

‫הגדרות‬

‫‪71‬‬

‫‪.6.5.2‬‬

‫קבוצות שאינן בנות מניה – שיטת הליכסון של קנטור‬

‫‪72‬‬

‫‪.6.5.3‬‬

‫משפט קנטור‬

‫‪74‬‬

‫‪.6.6‬‬

‫עוצמת הרצף‬

‫‪75‬‬

‫‪.6.6.1‬‬

‫השערת הרצף‬

‫‪75‬‬

‫‪.6.6.2‬‬

‫עוצמת הרצף‬

‫‪75‬‬

‫‪.6.7‬‬

‫משפט קנטור ברנשטיין‬

‫‪79‬‬

‫‪.6.7.1‬‬

‫מוטיבציה‬

‫‪79‬‬

‫‪.6.7.2‬‬

‫ניסוח ‪1‬‬

‫‪79‬‬

‫‪.6.7.3‬‬

‫ניסוח ‪2‬‬

‫‪79‬‬

‫‪.6.7.4‬‬

‫טענה ‪1‬‬

‫‪80‬‬

‫‪.6.7.5‬‬

‫טענה ‪2‬‬

‫‪80‬‬

‫‪.7‬‬ ‫‪7.1.‬‬

‫קבוצות אינדוקטיביות‬ ‫סגירות תחת פונקציות‬

‫‪82‬‬ ‫‪82‬‬

‫‪.7.1.1‬‬

‫הגדרת סגירות תחת פונקציה‬

‫‪82‬‬

‫‪.7.1.2‬‬

‫דוגמא‬

‫‪82‬‬

‫‪.7.1.3‬‬

‫הגדרת סגירות תחת קבוצת פונקציות‬

‫‪82‬‬

‫‪.7.1.4‬‬

‫טענה ‪1‬‬

‫‪83‬‬

‫‪.7.1.5‬‬

‫טענה ‪2‬‬

‫‪83‬‬

‫עיצוב מילים‬

‫‪84‬‬

‫‪.7.2‬‬ ‫‪.7.2.1‬‬

‫בנאים של קבוצות‬

‫‪84‬‬

‫‪.7.2.2‬‬

‫עקרון הסגירות‬

‫‪84‬‬

‫‪.7.2.3‬‬

‫הגדרת אוסף מילים‬

‫‪85‬‬

‫‪.7.2.4‬‬

‫מילים מעל }‪{a, b‬‬

‫‪85‬‬

‫‪.7.2.5‬‬

‫תכונות של *‪Σ‬‬

‫‪86‬‬

‫‪.7.2.6‬‬

‫בניית קבוצת הטבעיים‬

‫‪86‬‬

‫‪.7.3‬‬

‫‪ 4‬‬

‫קבוצות אינדוקטיביות‬

‫‪87‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬ ‫‪.7.3.1‬‬

‫הגדרת קבוצות מורכבות – הגדרה באינדוקציה‬

‫‪87‬‬

‫‪.7.3.2‬‬

‫הוכחת שימושיות ההגדרה‬

‫‪88‬‬

‫‪.7.3.3‬‬

‫סדרת יצירה‬

‫‪89‬‬

‫‪.7.3.4‬‬

‫דוגמת ‪CHANGE‬‬

‫‪91‬‬

‫‪.7.3.5‬‬

‫משפט הרקורסיה‬

‫‪92‬‬

‫‪.7.3.6‬‬

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

‫‪93‬‬

‫‪ 5‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪ .2‬מושגי יסוד בתורת הקבוצות‬

‫‪  .2.1‬הגדרת קבוצה‬ ‫קבוצה היא ישות המורכבת מאוסף אלמנטים המכונים איברי הקבוצה‪ .‬אין חשיבות לסדר בין האלמנטים‬ ‫בקבוצה‪ ,‬וכמו כן אין חזרות‪ ,‬כלומר כל אלמנט מופיע פעם אחת לכל היותר‪.‬‬ ‫האלמנטים של קבוצה לא חייבים להיות מאותו סוג‪ ,‬למשל‪ ,‬חלקם יכולים להיות מספרים וחלקם אותיות‪.‬‬ ‫כמו כן‪ ,‬אלמנטים של קבוצות יכולים להיות קבוצות בעצמם‪.‬‬ ‫קבוצה מוגדרת באופן חד ערכי על ידי האלמנטים שבה‪ .‬על מנת להגדיר קבוצה יש להגדיר במפורש אילו‬ ‫אלמנטים נמצאים בקבוצה‪.‬‬ ‫דוגמאות‪:‬‬

‫}‪A = {1, 2,5‬‬ ‫‪ ‬‬

‫}‪ ‬אבג‪B = {0.5, a,‬‬ ‫}}‪C = {1,3, {1} , {1,3‬‬

‫כיצד ניתן להגדיר קבוצה?‬ ‫• ‪ ‬מניית איברי הקבוצה בין סוגריים מסולסלות‪.‬‬ ‫שיטה זו לפעמים איננה מעשית‪ ,‬לדוגמא עבור קבוצת המספרים בין ‪ 0‬ל‪,100000-‬‬ ‫ולעתים גם איננה אפשרית‪ ,‬לדוגמא‪ ,‬קבוצת המספרים השלמים‪  .‬‬ ‫• ‪ ‬ניתן לפרט את איברי הקבוצה תוך כדי שימוש ב"‪ ."...‬דוגמא‪  {1, 2,...,100} :‬‬ ‫• ‪ ‬הגדרת הקבוצה על ידי תכונה )פרדיקט( שמאפיינת את כל איברי הקבוצה ורק אותם‪.‬‬ ‫דוגמאות‪  :‬‬ ‫‪o‬‬

‫‪ 6‬‬

‫‪  . A = { X | 3 ≤ X ≤ 10 6  and also X is integer }  ‬‬

‫‪o‬‬

‫‪ ‬‬

‫טבעיים‪= { x | x ≥ 0 and x  is integer} ,‬‬

‫‪o‬‬

‫‪ ‬‬

‫‪m‬‬ ‫‪‬‬ ‫רציונליים‪=  | m, n  are integers and also n ≠ 0  ,‬‬ ‫‪n‬‬ ‫‪‬‬

‫‪ ‬‬ ‫‪ .‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ ‬‬

‫‪  .2.2‬הקבוצה הריקה‬ ‫‪ ‬‬

‫קבוצה ריקה היא קבוצה שלא מכילה אלמנטים )מספר איבריה הוא ‪.(0‬‬ ‫סימונים לקבוצה ריקה‪. {}, φ :‬‬ ‫הערה חשובה‪ :‬הקבוצה ‪ φ‬והקבוצה } ‪ {φ‬לא שוות‪ φ .‬שקית ריקה‪ {φ } ,‬שקית בתוך שקית‪.‬‬

‫‪  .2.3‬גודל של קבוצה‬ ‫קבוצה היא סופית אם קיים מספר טבעי ‪ n‬כך שמספר איבריה היא ‪. n‬‬ ‫קבוצה היא אינסופית אחרת‪ ,‬כלומר כאשר לא קיים ‪ n‬כזה‪.‬‬ ‫נשים לב לקבוצה הבאה‪ .{ { 0, 1, 2, ... } } :‬קבוצה זו בעלת איבר אחד! )קבוצה אחרת(‪.‬‬ ‫עבור קבוצה סופית ‪ ,A‬נסמן ב‪ |A|-‬את מספר איבריה = הגודל שלה‪.‬‬

‫‪φ =0‬‬ ‫‪ ‬‬

‫‪{φ} = 1‬‬ ‫‪{ X | 5 ≤ X ≤ 20 and also X is integer} = 16‬‬ ‫‪{1,3,{1,3}} |= 3‬‬

‫‪  .2.4‬גרירה לוגית ואמ"מ‬ ‫תהיינה ‪ α‬ו‪ β -‬טענות‪.‬‬ ‫• ‪ ‬כשמסמנים ‪ α ⇒ β‬ואומרים " ‪ α‬גורר את ‪ " β‬הכוונה שאם הטענה ‪ α‬מתקיימת‬ ‫אזי גם הטענה ‪ β‬חייבת להתקיים‪  .‬‬

‫• ‪ ‬כשמסמנים ‪ α ⇔ β‬ואומרים " ‪ α‬אמ"מ ‪ " β‬הכוונה היא ‪ α ⇒ β‬וגם ‪. β ⇒ α‬‬ ‫שתי הטענות או מתקיימות או לא מתקיימות ביחד‪  .‬‬

‫‪ 7‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .2.5‬שייכות‬ ‫אם ‪ a‬איבר בקבוצה ‪ ,A‬מסמנים ‪ a ∈ A‬ואומרים "‪ a‬שייך ל‪."A-‬‬ ‫אם ‪ a‬אינו איבר ב‪ A-‬מסמנים ‪ a ∉ A‬ואומרים "‪ a‬לא שייך ל‪."A-‬‬ ‫דוגמא‬ ‫}}}‪A = {1,{3},{2,5},{1,{3‬‬ ‫‪3∉ A‬‬ ‫‪{3} ∈ A‬‬ ‫‪ ‬‬

‫‪{2} ∉ A‬‬ ‫‪{1,{3}} ∈ A‬‬

‫‪φ∉A‬‬ ‫}}‪A = {1,{},3,{4,5‬‬ ‫‪φ∈A‬‬

‫‪  .2.6‬שוויון קבוצות‬ ‫שתי קבוצות ‪ S , S ′‬הן שוות אם יש להן בדיוק אותן איברים‪.‬‬ ‫באופן פורמלי‪ ,‬השוויון ‪ S = S ′‬מתקיים אמ"מ לכל ‪. a ∈ S ⇔ a ∈ S ′ , a‬‬

‫‪ 8‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .2.7‬תתי קבוצות‬ ‫תהיינה ‪ A‬ו‪ B-‬קבוצות‪ A .‬נקראת תת קבוצה של ‪ B‬אמ"מ כל איבר ב‪ A-‬הוא גם איבר ב‪,B-‬‬ ‫כלומר‪x ∈ B ⇐ x ∈ A :‬‬

‫סימון לתת קבוצה‪. A ⊆ B :‬‬ ‫נאמר כי ‪ A‬מוכלת ב‪ ,B-‬וכי ‪ A‬היא קבוצה חלקית ל‪.B-‬‬ ‫תכונות של הכלה‬ ‫‪  .1‬לכל קבוצה ‪  . φ ⊆ A ,A‬‬

‫‪  .2‬לכל קבוצה ‪) . A ⊆ A ,A‬רפלקסיביות(‬ ‫‪  .3‬לכל ‪ , A, B, C‬אם ‪ A ⊆ B‬וגם ‪ B ⊆ C‬אזי ‪) A ⊆ C‬טרנזיטיביות(‪  .‬‬

‫אם ב‪ A-‬קיים לפחות איבר אחד שאינו שייך ל‪ B-‬אז ‪ A‬לא מוכלת ב‪ B-‬ומסמנים ‪. A ⊄ B‬‬

‫טענה‬ ‫לכל ‪ 2‬קבוצות ‪ A‬ו‪ B-‬מתקיים‪ A=B :‬אמ"מ ‪ A ⊆ B‬וגם ‪. B ⊆ A‬‬ ‫הוכחה‬ ‫כיוון ‪ :1‬נתון ‪ .A=B‬צ"ל‪ A ⊆ B :‬וגם ‪. B ⊆ A‬‬ ‫‪ ⇐ A=B‬עפ"י ההגדרה‪ x ∈ B ← x ∈ A ⇐ x ∈ B ⇔ x ∈ A :‬וגם ‪) x ∈ B → x ∈ A‬הגדרת הכלה(‬ ‫ומכאן‪ A ⊆ B :‬וגם ‪. B ⊆ A‬‬ ‫כיוון ‪ :2‬נתון ‪ A ⊆ B‬וגם ‪ . B ⊆ A‬צ"ל ‪ .A=B‬אותה הוכחה בדיוק בכיוון ההפוך‪.‬‬ ‫הגדרה ‪ -‬הכלה ממש‬ ‫‪ A‬מוכלת ממש ב‪ B-‬אמ"מ ‪ A ⊆ B‬אבל ‪ A . A ≠ B‬תת קבוצה אמיתית של ‪.B‬‬

‫סימון‪A ⊂ B :‬‬

‫‪ 9‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .2.8‬דיאגרמת ון‬ ‫מסמנים קבוצה על ידי תחום סגור במישור‪:‬‬ ‫‪ ‬‬ ‫‪ ‬‬

‫שתי קבוצות ללא איברים משותפים‪:‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫שתי קבוצות עם איברים משותפים‪:‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪:A⊆ B‬‬

‫‪ ‬‬

‫‪  10‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .3‬פעולות על קבוצות‬

‫‪  .3.1‬איחוד קבוצות‬ ‫איחוד שתי קבוצות ‪ A‬ו‪ B-‬הוא הקבוצה הבאה‪:‬‬

‫‪A ∪ B = { X | x ∈ B or x ∈ A}  ‬‬ ‫משמעות המילה "‪ "or‬בהגדרה הוא ‪ x ∈ A‬או ‪ x ∈ B‬או שניהם‪.‬‬

‫‪  .3.2‬חיתוך קבוצות‬ ‫חיתוך שתי קבוצות ‪ A‬ו‪ B-‬הוא הקבוצה הבאה‪:‬‬

‫‪A ∩ B = { X | x ∈ B and  x ∈ A}  ‬‬ ‫קבוצות ללא איברים משותפים נקראות קבוצות זרות‪.‬‬ ‫מתכונות החיתוך‪:‬‬ ‫• ‪  A∩ A = A  ‬‬ ‫• ‪  A∩φ = φ  ‬‬

‫כפי שנראה בדף הבא‪ ,‬פעולת החיתוך היא קומוטטיבית ואסוציטיבית‪.‬‬

‫‪  11‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .3.3‬תכונות של חיתוך ואיחוד קבוצות‬ ‫יהיו ‪ A, B‬קבוצות‪ ,‬אזי‪:‬‬ ‫‪ A ⊆ B   .1‬גורר כי ‪  . A ∪ B = B‬‬ ‫‪ A ⊆ B   .2‬גורר כי ‪  . A ∩ B = A‬‬ ‫‪  . A ∩ B = B ∩ A   .3‬‬ ‫‪  . A ∪ B = B ∪ A   .4‬‬ ‫‪  . ( A ∩ B) ∩ C = A ∩ ( B ∩ C )   .5‬‬ ‫‪  . ( A ∪ B) ∪ C = A ∪ ( B ∪ C )   .6‬‬ ‫‪  . A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C )   .7‬‬ ‫‪  . A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )   .8‬‬

‫‪  .3.4‬נכון ‪ /‬לא נכון‬ ‫טענה ‪1‬‬

‫אם ‪ A ∩ B = A ∩ C‬אזי ‪. B = C‬‬ ‫הטענה אינה נכונה‪.‬‬

‫נבחר ‪ , A = φ‬וגם שתי קבוצות ‪ , B ≠ C‬ונקבל ‪ A ∩ B = A ∩ C = φ‬וגם ‪. B ≠ C‬‬

‫טענה ‪2‬‬

‫אם ‪ A ∪ B = A ∪ C‬אזי ‪. B = C‬‬ ‫הטענה אינה נכונה‪.‬‬

‫נבחר ‪ A = C ≠ φ‬וגם ‪ B = φ‬ונקבל ‪ A ∪ C = A ∪ A = A‬וגם ‪. A ∪ B = A ∪ φ = A‬‬

‫‪  12‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה ‪3‬‬

‫אם ‪ A ∪ B = A ∪ C‬וגם ‪ A ∩ B = A ∩ C‬אזי ‪. B = C‬‬ ‫הטענה נכונה‪.‬‬

‫צריך להוכיח הכלה דו כיוונית‪ B ⊆ C :‬וגם ‪. C ⊆ B‬‬ ‫מספיק להוכיח כי ‪ B ⊆ C‬מכיוון שההוכחה תהיה סימטרית‪.‬‬ ‫יהי ‪ . x ∈ B‬על פי הגדרת האיחוד ‪ X ∈ A ∪ B‬ולפי הנתון ‪. x ∈ A ∪ C‬‬ ‫‪ : x ∈ A ∪ C‬אם ‪ x ∈ C‬אז סיימנו‪ .‬אחרת ‪ x ∈ A‬ולפי הגדרת החיתוך מתקיים ‪. x ∈ A ∩ B‬‬ ‫על פי הנתון ‪ x ∈ A ∩ C‬ולכן לפי הגדרת החיתוך מתקיים ‪. x ∈ C‬‬

‫‪  .3.5‬זרות הדדית‬ ‫בהינתן אוסף של קבוצות ‪ A1 , A2 ,..., An‬נאמר שהקבוצות זרות הדדית אם לכל ‪ i ≠ j‬מתקיים‬ ‫‪ , Ai ∩ A j = φ‬כלומר אין אלמנט הנמצא ביותר מקבוצה אחת‪.‬‬

‫לדוגמא‪ :‬לכל מספר טבעי ‪ i‬נגדיר את הקבוצה הבאה‪ Ai = {2i, 2i + 1} :‬ואז יתקיים‪:‬‬ ‫‪...  ‬‬

‫כל הקבוצות הנ"ל זרות הדדית‪.‬‬

‫תרגיל‬ ‫‪n‬‬

‫נתון‪ . ∩ Ai = φ :‬האם בהכרח הקבוצות זרות הדדית?‬ ‫‪i =1‬‬

‫תשובה‬ ‫לא בהכרח‪ ,‬למשל‪A1 = {1, 2} , A2 = {2,3} , A2 = {3, 4} :‬‬

‫‪ A1 ∩ A2 ∩ A3 = φ‬אולם הקבוצות אינן זרות הדדית‪  .‬‬

‫‪  13‬‬

‫}‪A1 = {2,3‬‬

‫}‪A0 = {0,1‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .3.6‬הפרש בין קבוצות‬ ‫תהיינה ‪ A‬ו‪ B-‬קבוצות‪ .‬ההפרש בין ‪ A‬ל‪ B-‬יסומן באופן הבא‪ A − B :‬או ‪ A \ B‬ויוגדר להיות‪:‬‬ ‫‪A \ B = { X | x ∈ A and  x ∉ b}  ‬‬

‫השרטוטים הבאים מדגימים שלושה זוגות של קבוצות‪ .‬בכל זוג סימנו את הקטע המייצג את ההפרש בין‬ ‫‪ A‬ל‪ B-‬בצבע אפור‪:‬‬

‫‪ ‬‬

‫דגש‪ :‬פעולת ההפרש היא איננה פעולה אסוציאטיבית!‬

‫‪  14‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .3.7‬הפרש סימטרי‬ ‫תהינה ‪ A‬ו‪ B-‬קבוצות‪ .‬ההפרש הסימטרי של ‪ A‬ו‪ B-‬היא הקבוצה‪:‬‬ ‫‪A ⊕ B = {x ∈ A or x ∈ B but not to A and B }  ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫ניתן לכתוב את ההפרש הסימטרי גם בצורה הבאה‪:‬‬ ‫‪A⊕ B = A ∪ B- A ∩ B ‬‬

‫‪  .3.8‬משלים‬ ‫נניח כי כל אבריי הקבוצות עליהן מדובר הן תתי קבוצות של קבוצה אוניברסלית ‪) U‬העולם(‪.‬‬ ‫המשלים של ‪ A‬ביחס לקבוצה האוניברסלית ‪ U‬הוא הקבוצה ‪U − A‬‬

‫סימון למשלים‪ Ac :‬או ‪  A‬‬ ‫דוגמא‬

‫‪ ‬‬

‫=‪U‬‬

‫‪ } ‬זוגי‪A={n | n ‬‬ ‫‪ } ‬אי‪-‬זוגי‪A c ={n | n ‬‬

‫‪  15‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫תכונות פעולת המשלים‬ ‫‪X ∉ A ⇔ X ∈ Ac‬‬ ‫‪ ‬‬

‫‪AC ∪ A = U‬‬ ‫‪( Ac ) c = A‬‬ ‫‪A ∩ Ac = φ‬‬ ‫‪ ‬‬

‫קשר בין הפרש למשלים‬

‫‪A − B = A ∩ Bc  ‬‬ ‫‪ ‬‬

‫נוכיח את הקשר באמצעות טבלת שייכות‪:‬‬ ‫‪  A ∩ Bc‬‬

‫‪  BC‬‬

‫‪  A-B‬‬

‫‪ B‬‬

‫‪ A‬‬

‫‪ ‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪ T‬‬

‫‪ T‬‬

‫‪  x ∈ A, x ∈ B‬‬

‫‪ T‬‬

‫‪ T‬‬

‫‪ T‬‬

‫‪ F‬‬

‫‪ T‬‬

‫‪  x ∈ A, x ∉ B‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪ T‬‬

‫‪ F‬‬

‫‪  x ∉ A, x ∈ B‬‬

‫‪ F‬‬

‫‪ T‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪ F‬‬

‫‪  x ∉ A, x ∉ B‬‬

‫שיטת השימוש בטבלת השייכות‪:‬‬ ‫‪  .1‬מקדישים עמודה עבור כל תת ביטוי הנמצא בזהות‪  .‬‬ ‫‪  .2‬מקדישים שורה עבור כל מקרי השייכות של האיבר לקבוצות הבסיסיות‪  .‬‬ ‫‪  .3‬ממלאים את הטבלה ע"פ הגדרת איחוד‪ ,‬חיתוך‪ ,‬משלים‪  .‬‬ ‫‪  .4‬משווים בין העמודות המתאימות לשני צדי הזהות‪ .‬אם העמודות זהות‪ ,‬הזהות נכונה‪  .‬‬

‫‪  16‬‬

‫ניר אדר‬

  [email protected]

‫חוקי דה מורגן‬  .3.9 1.  ( A ∩ B)C = AC ∪ B c   2.  ( A ∪ B)C = AC ∩ B c  

:‫ צ"ל‬.‫ על ידי הכלה דו כיוונית‬1 ‫נוכיח את חוק‬  ( A ∩ B ) C ⊆ AC ∪ B c .‫א‬  ( A ∩ B ) C ⊇ AC ∪ B c .‫ב‬

.‫א‬

x ∈ ( A ∩ B ) c ⇒ ‫ ⇒ הגדרת המשלים‬x ∉ A ∩ B ⇒ ‫הגדרת‬ ‫ ⇒ חיתוך‬x ∉ A or  x ∉ B ⇒ x ∈ A c  or  x ∈ B c ⇒ x ∈ A c ∪ B c   .‫הכיוון השני נעשה בדרך זהה על ידי הפיכת כיוון החצים‬

3.  A ⊆ B  implies that B \ ( B \ A ) = A .  4.  A ⊆ B  and  B ⊆ C  implies that C \ B ⊆ C \ A .  5.  C \ ( A ∪ B ) = ( C \ A ) ∩ ( C \ B ) .  6.  C \ ( A ∩ B ) = ( C \ A ) ∪ ( C \ B )  

‫חוקי דיסטריבוטיביות‬ 

.3.10

1)   A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C )   2)   A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )

  17

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪.3.11‬‬

‫‪ ‬חוקי ספיגה‬ ‫‪1)   A ∪ ( A ∩ B) = A‬‬ ‫‪ ‬‬ ‫‪2)  A ∩ (A ∪ B) = A‬‬

‫את חוקי הספיגה ניתן להוכיח על ידי חוקי דיסטריבוטיביות‪.‬‬ ‫לדוגמא‪ ,‬עבור ‪: (1‬‬

‫‪A ∪ ( A ∩ B ) = ( A ∪ A) ∩ ( A ∪ B ) = A  ‬‬ ‫‪ ‬‬

‫‪.3.12‬‬

‫‪ ‬איחוד על קבוצות‬

‫תהי ‪ X‬קבוצה לא ריקה‪ .‬נסמן ב‪ ∪ X -‬את הקבוצה המכילה את כל האלמנטים של כל האלמנטים של ‪,X‬‬ ‫כלומר ‪ y ∈ ∪ X‬אמ"מ קיים ‪ Y ∈ X‬כך ש‪ ∪ X . y ∈ Y -‬נקראת האיחוד מעל ‪.X‬‬ ‫אם }‪ X = { A, B‬אזי האיחוד מעל ‪ X‬יהיה ‪. ∪ X = A ∪ B‬‬ ‫עבור ‪ X = φ‬נגדיר ‪. ∪ X = φ‬‬ ‫דוגמאות‪:‬‬

‫}‬

‫{‬

‫‪1.  ∪ φ , {φ } , {{φ }} = {φ , {φ }}  ‬‬ ‫‪2.  ∪ {{ A} , { A, B}} = { A, B}  ‬‬

‫‪.3.13‬‬

‫‪ ‬חיתוך על קבוצות‬

‫תהי ‪ X‬קבוצה לא ריקה ‪ .‬נסמן ב‪ ∩ X -‬את הקבוצה המכילה את כל האלמנטים שהם אלמנטים של איבר‬ ‫של ‪ ,X‬כלומר‪ y ∈ ∩ X ,‬אמ"מ לכל ‪ Y ∈ X‬מתקיים כי ‪ ∩ X . y ∈ Y‬מכונה החיתוך על ‪.X‬‬ ‫אם }‪ X = { A, B‬אזי החיתוך על ‪ X‬יהיה ‪. ∪ X = A ∩ B‬‬ ‫עבור ‪ X = φ‬החיתוך איננו מוגדר‪.‬‬ ‫דוגמאות‪:‬‬

‫}‬

‫{‬

‫‪1.  ∩ φ , {φ } , {{φ }} = φ  ‬‬ ‫}‪2.  ∩ {{ A} , { A, B}} = { A‬‬

‫‪  18‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪ ‬‬

‫‪.3.14‬‬

‫‪ ‬תכונות של איחוד וחיתוך על קבוצות‬

‫יהיו ‪ A, B, C‬קבוצות ו‪ X , Y -‬קבוצות לא ריקות של קבוצות‪ .‬אזי‪:‬‬

‫‪1. ‬‬

‫= ) ‪( ∪ X ) ∩ ( ∪Y‬‬ ‫‪∪ {( A ∩ B ) ⊆ ∪ X : A ∈ X , B ∈ Y } =  ‬‬ ‫} ‪∪ {( A ∩ B ) ⊆ ∪Y : A ∈ X , B ∈ Y‬‬ ‫‪ ‬‬ ‫‪2. ‬‬

‫= ) ‪( ∩ X ) ∪ ( ∩Y‬‬ ‫‪∩ {( A ∪ B ) ⊆ ∪ X : A ∈ X , B ∈ Y } =  ‬‬ ‫} ‪∩ {( A ∪ B ) ⊆ ∪Y : A ∈ X , B ∈ Y‬‬

‫‪.3.15‬‬

‫‪ ‬חוקי דה מורגן לגבי איחוד וחיתוך על קבוצות‬

‫יהיו ‪ A, B, C‬קבוצות ו‪ X , Y -‬קבוצות לא ריקות של קבוצות‪ .‬אזי‪:‬‬

‫‪1. ‬‬

‫‪C \ ( ∪ X ) = ∩ {C \ A ⊆ C : A ∈ X }  ‬‬ ‫‪ ‬‬ ‫‪2. ‬‬

‫‪C \ ( ∩ X ) = ∪ {C \ A ⊆ C : A ∈ X }  ‬‬

‫‪  19‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪.3.16‬‬

‫‪ ‬קבוצת החזקה‬

‫תהא ‪ A‬קבוצה‪ .‬קבוצת החזקה של ‪ A‬המסומנת על ידי )‪ P(A‬או על ידי ‪ 2 A‬היא הקבוצה‪:‬‬

‫‪P ( A) = {B | B ⊆ A}  ‬‬ ‫כלומר )‪ P(A‬מכילה )כאיברים( את כל תתי הקבוצות של ‪.A‬‬ ‫דוגמא‬

‫‪ ‬‬

‫גודלה של )‪ P(A‬עבור קבוצה סופית ‪ A‬הינו‬

‫‪A‬‬

‫}‪A = {1, 2‬‬ ‫}}‪P ( A ) = {φ , {1} , {2} , {1, 2‬‬

‫‪.2‬‬

‫טענה‬

‫לכל ‪ 2‬קבוצות ‪ A‬ו‪ B-‬מתקיים‪  P ( A ∩ B ) = P( A) ∩ P ( B ) :‬‬ ‫‪ ‬‬ ‫הוכחה‪:‬‬ ‫נראה הכלה דו כיוונית‪:‬‬

‫א‪P ( A ∩ B ) ⊆ P ( A) ∩ P ( B ) .‬‬ ‫ב‪P ( A ∩ B ) ⊇ P ( A) ∩ P ( B ) .‬‬

‫א‪.‬‬

‫הגדרת ⇒ ‪C ∈ P( A ∩ B) ⇒ C ⊆ A ∩ B ⇒ C ⊆ A and C ⊆ B‬‬ ‫‪ ⇒ C ∈ P( A) ∩ P ( B )  ‬הגדרת חיתוך ⇒ ) ‪ ⇒ C ∈ P ( A) and C ∈ P ( B‬חזקה‬ ‫ב‪ .‬מתקבל מא' על ידי היפוך כיוון‪.‬‬

‫‪  20‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫תכונות של קבוצת החזקה‬ ‫יהיו ‪ A, B‬קבוצות ותהי ‪ X‬קבוצה לא ריקה של קבוצות‪ ,‬אזי‪:‬‬ ‫‪ A ⊆ B .1‬גורר כי )‪. P ( A) ⊆ P ( B‬‬

‫‪P ( A) ∪ P ( B ) ⊆ P ( A ∪ B ) .2‬‬ ‫‪P ( A ∩ B ) ⊆ P ( A) ∩ P( B) .3‬‬

‫‪∪ { P ( A) ∈ P ( P ( A)) : A ∈ X } ⊆ P ( ∪ X ) .4‬‬ ‫‪P ( ∩ X ) ⊆ ∩ { P ( A) ∈ P ( P( A)) : A ∈ X } .5‬‬

‫‪.3.17‬‬

‫‪ ‬בניה פורמלית לקבוצות‬

‫נציג כעת כיצד מגדירים קבוצות וכיצד יוצרים למעשה את הקבוצות בהן אנו עוסקים‪.‬‬ ‫הנחה ‪ :1‬קיימת הקבוצה הריקה‪.‬‬ ‫אבחנה‪ :‬הקבוצה הריקה הינה יחידה‪.‬‬ ‫הנחה ‪ :2‬לכל שתי קבוצות ‪ A, B‬קיימת קבוצה ‪ C‬ש‪ A, B -‬הם האיברים היחידים שלה‪ ,‬כלומר מתקיים‬ ‫}‪ C . C = { A, B‬נקרא הזוג הלא סדור של ‪. A, B‬‬ ‫כעת ניתן להרכיב קבוצות חדשות‪ {φ , φ } = {φ} :‬ובעזרתה את הקבוצות‪ {φ , {φ }} :‬ו‪. {{φ }} -‬‬

‫}‬

‫{‬

‫האם ניתן לקבל את הקבוצה }} ‪ ? φ , {φ } , {{φ‬כרגע לא‪ ,‬תחת ההנחות הקיימות‪.‬‬

‫הנחה ‪ :3‬כלל האיחוד‪ :‬לכל שתי קבוצות ‪ A, B‬קיימת קבוצה שאיבריה הם כל האיברים הנמצאים ב‪A -‬‬ ‫או ב‪ , B -‬כלומר ‪. C = A ∪ B‬‬ ‫כרגע‪ ,‬לכל ‪ A1 ,..., An‬ניתן לקבל את הקבוצה } ‪. { A1 ,..., An‬‬

‫‪  21‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫הנחה ‪ :4‬עקרון התכונה‪ :‬לכל קבוצה ‪  A‬ולכל תכונה ‪ ϕ‬של האיברים ב‪ , A -‬קיימת קבוצה ‪ B‬המכילה‬ ‫את איברי את המקיימים את ‪) ϕ‬ובדיוק אותם(‪.‬‬

‫דוגמאות‪:‬‬ ‫תהי הקבוצה ‪ A‬ונבחר את התכונה ‪ . a ∈ C‬נוכל להגדיר את הקבוצה }‪, B = {a ∈ A | a ∈ C‬‬ ‫ואז מתקיים ‪. B = A ∩ C‬‬ ‫תהי הקבוצה ‪ A‬ונבחר את התכונה ‪ . a ∉ C‬נוכל להגדיר את הקבוצה }‪, B = {a ∈ A | a ∉ C‬‬ ‫ואז מתקיים ‪. B = A − C‬‬

‫הנחה ‪ :5‬כלל החזקה‪ :‬לכל קבוצה ‪ , A‬קיימת קבוצה ) ‪ P ( A‬המכילה את כל תתי הקבוצות של ‪. A‬‬

‫חשוב לשים לב שזהו איננו מקרה פרטי של הנחה ‪ ,4‬כי מדובר בקבוצה של כל תתי הקבוצות של ‪ A‬ולא‬ ‫בקבוצה של איברי ‪. A‬‬

‫דוגמא‬ ‫בהנתן קבוצה ‪ , A‬הוכיחו שקיימת הקבוצה }‪ B = {S | S ⊆ A‬וגם ב‪ S -‬ישנם שלושה איברים‪.‬‬

‫פתרון‪ :‬בהינתן קבוצה ‪ , A‬על פי הנחה ‪ ,5‬קיימת )‪ . P ( A‬נשתמש בעקרון התכונה‪ ,‬עם ‪ S = 3‬על‬

‫}‬

‫{‬

‫הקבוצה ) ‪ P ( A‬ונקבל‪. B = S ∈ P ( A) S = 3 :‬‬

‫‪  22‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪.3.18‬‬

‫‪ ‬הקבוצה האוניברסאלית‬

‫נשאלת השאלה‪ :‬האם קיימת קבוצה אוניברסאלית ‪   U‬כך שעבור כל קבוצה ‪ ,A‬מתקיים כי ‪? A ∈ U‬‬ ‫נניח שקיימת קבוצה כזו‪ ,‬ונביט בקבוצה הבאה‪. U 0 = { x ∈ U : x ∉ X } :‬‬ ‫אם ‪ U 0 ∈ U 0‬אזי ‪ U 0 ∉ U 0‬לפי הגדרת ‪ U 0‬ואנו מקבלים סתירה‪.‬‬ ‫אבל אם ‪ U 0 ∉ U 0‬אזי לפי הגדרה ‪ U 0 ∈ U 0‬ושוב אנו מקבלים סתירה‪.‬‬ ‫מכאן אנו מגיעים למסקנה‪ :‬לא קיימת קבוצה אוניברסאלית המכילה את כל שאר הקבוצות‪.‬‬ ‫ניסיון נוסף להגדיר קבוצה אוניברסאלית‪:‬‬ ‫האם קיימת קבוצה אוניברסאלית ‪ V‬כל שעבור כל קבוצה ‪ ,A‬מתקיים כי ‪? { A} ∈ V‬‬ ‫נניח שכן‪ ,‬ונביט בקבוצה הבאה‪. V0 = { X ∈ V : { X } ∉ X } :‬‬ ‫אם ‪ {V0 } ∈ V0‬אזי ‪ {V0 } ∉ V0‬לפי הגדרת ‪ V0‬וקיבלנו סתירה‪.‬‬ ‫אולם אם ‪ {V0 } ∉ V0‬אזי ‪ {V0 } ∈ V0‬לפי הגדרת ‪ V0‬ושוב קיבלנו סתירה‪.‬‬ ‫מסקנה‪ :‬לא קיימת קבוצה אוניברסאלית כנ"ל‪.‬‬

‫‪.3.19‬‬

‫‪ ‬זוג סדור‬

‫נגדיר זוג סדור כשני איברים שהאחד נקבע כראשון והאחר כשני‪ .‬כלומר אנו נותנים חשיבות לסדר של‬ ‫האיברים בזוג‪ .‬איננו מגבילים את תוכן האיברים‪ .‬יתכן שבזוג סדור האיברים יהיו זהים ‪. A, A‬‬ ‫השוני בין זוג סדור לקבוצה‪:‬‬

‫• ‪ ‬בקבוצה אין משמעות לסדר‪  . { A, B} :‬‬ ‫• ‪ ‬בקבוצה אין משמעות לחזרות‪  . { A, A} = { A} :‬‬

‫הגדרה של זוג סדור ‪ A, B‬צריכה לקיים‪:‬‬

‫• ‪ ‬אם ‪ A ≠ B‬אזי ‪  . A, B ≠ B, A‬‬ ‫• ‪ A, B = A′, B′  ‬אמ"מ ‪  . A = A′, B = B′‬‬

‫‪  23‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫הצעה ראשונה להגדרה‬ ‫נגדיר‪. A, B = { A, { B}} :‬‬ ‫נראה כי ההגדרה אינה מספקת‪.‬‬

‫{‬

‫}‬

‫יהיו }‪ , A = {1} , B = {2‬אזי לפי ההגדרה שהצענו }}‪. A, B = {1} , {{2‬‬

‫}‬

‫{‬

‫כעת נבחר }‪ A′ = {{2}} , B′ = {1‬ואז יתקיים‪. A′, B′ = {1} , {{2}} :‬‬ ‫ונקבל ‪ A′, B′ = A, B‬אבל ‪. A′ ≠ A, B′ ≠ B‬‬

‫הצעה שניה להגדרה‬

‫נבנה בעזרת ההנחות את ‪ A, B‬ונראה כי ההגדרה עונה על הדרישות‪.‬‬ ‫טענה‪ :‬בהינתן ‪ A, B‬ניתן לבנות את ‪. A, B‬‬ ‫הוכחה‪:‬‬

‫• ‪ ‬מ‪ A, B -‬ניתן על פי הנחה ‪ 2‬לבנות את הקבוצה }‪  . { A, B‬‬ ‫• ‪ ‬מ‪ A -‬ניתן על פי הנחה ‪ 2‬לבנות את הקבוצה }}‪  . {{ A} , { A, B‬‬

‫נטען‪ :‬הזוג }}‪ A, B = {{ A} , { A, B‬עונה על הדרישה‪ ,‬כלומר ‪ A, B = A′, B′‬אמ"מ‬ ‫‪. A = A′, B = B′‬‬

‫הוכחה‪:‬‬ ‫כיוון ⇒ ‪ :‬טריויאלי‪.‬‬ ‫כיוון ⇐ ‪ :‬נניח כי ‪ A, B = A′, B′‬ונראה ‪. A = A′, B = B′‬‬

‫‪{{ A} , { A, B}} = {{ A′} , { A′, B′}}  ‬‬

‫‪  24‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫אפשרות אחת‪:‬‬

‫‪{ A} = { A′} ⇒ A′ = A‬‬ ‫‪ ‬‬ ‫‪{ A, B} = { A′, B′} ⇒ B ' = B‬‬ ‫אפשרות שניה‪:‬‬

‫‪{ A} = { A′, B′} ⇒ A = A′‬‬ ‫‪ ‬‬ ‫}‪{ A, B} = { A′‬‬ ‫)בקבוצה שמכילה את ‪ A‬יש איבר אחד(‪.‬‬ ‫ולכן ‪ . A = A′‬באותו אופן מאחר ו‪ { A, B} = { A′} -‬נקבל ‪ A = B‬ומכאן ‪. A = A′, B = B′‬‬

‫תכונות נלוות לזוג הסדור לפי ההגדרה שנתנו‬

‫• ‪ ‬בזוג סדור ישנם לכל היותר שני איברים‪ .‬אם ‪ A = B‬אזי ב‪ A, B -‬יש איבר אחד‪  .‬‬ ‫• ‪  . A ∉ A, B , B ∉ A, B  ‬‬

‫שלשה סדורה‬ ‫נגדיר שלשה סדורה בצורה הבאה‪. a, b, c = a, b , c :‬‬ ‫לפי הגדרה זו‪ ,‬בשלשה הסדורה שני איברים לכל היותר‪.‬‬ ‫‪-n‬יה סדורה‬

‫באופן דומה ניתן להגדיר ‪-n‬יה סדורה ‪. a1 , a2 , a3 ,..., an‬‬

‫‪a1 , a2 , a3 ... , an  ‬‬

‫‪  25‬‬

‫= ‪a1 , a2 , a3 ,..., an‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪.3.20‬‬

‫‪ ‬מכפלה קרטזית‬

‫תהיינה ‪ A‬ו‪ B-‬קבוצות‪ .‬המכפלה הקרטזית ‪ A × B‬היא הקבוצה‪:‬‬

‫‪A × B = { A, B | a ∈ A, b ∈ B}  ‬‬ ‫כלומר ‪ A × B‬היא קבוצת כל הזוגות הסדורים בהם האיבר הראשון שייך ל‪ A-‬והשני ל‪.B-‬‬ ‫פעולה זו איננה קומוטטיבית‪ .‬אם ‪ A‬שונה מ‪ B-‬אזי ‪ A × B‬שונה מ‪. B × A -‬‬

‫מתכונות המכפלה הקרטזית‪:‬‬ ‫‪. A × φ = φ × A = φ   .1‬‬ ‫‪. A × ( B ∪ C ) = ( A × B ) ∪ ( A × C )   .2‬‬

‫‪  . A × ( B ∩ C ) = ( A × B ) ∩ ( A × C )   .3‬‬ ‫‪) . ( ( A × B ) × C ) ≠ ( A × ( B × C ) )   .4‬כי ) ) ‪  . ( ( a, b ) , c ) ≠ ( a, ( b, c‬‬

‫עבור קבוצה סופית מתקיים‪  AxB = A ⋅ B :‬‬

‫סימון‬ ‫המכפלה הקרטזית ‪ A × A‬תסומן ‪. A2‬‬

‫הרחבת ההגדרה עבור ‪ n‬קבוצות‬ ‫יהיו הקבוצות ‪ . A1 , A2 ,..., An‬נגדיר את המכפלה הקרטזית שלהם בצורה הבאה‪:‬‬

‫‪A1 × A2 × ... × An = { a1 , a2 ,..., an | a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An }  ‬‬

‫‪  26‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫סימון‬ ‫המכפלה הקרטזית ‪ A × ... × A‬תסומן ב‪. An -‬‬ ‫‪n  times‬‬

‫טענה‬ ‫בהינתן ‪ A‬ו‪ , B -‬קיימת הקבוצה ‪. A × B‬‬

‫‪{{{a} ,{a, b}} | a ∈ A, b ∈ B}  ‬‬

‫= }‪A × B = { a, b | a ∈ A, b ∈ B‬‬ ‫‪ ‬‬

‫הוכחה‪:‬‬

‫) ‪{a} ⊆ A, {a} ∈ P ( A) , {a} ⊆ P ( A ∪ B‬‬ ‫‪ ‬‬ ‫) ‪{a, b} ⊆ A ∪ B, {a, b} ∈ P ( A ∪ B‬‬ ‫נסמן‪. P ( A ∪ B ) ≡ C , {a} ≡ x, {a, b} ≡ y :‬‬ ‫אנו מחפשים את }‪ x ∈ C , y ∈ C . { x, y‬ולכן ) ‪. { x, y} ∈ P ( C‬‬ ‫כלומר‪. {{a} , {a, b}} ∈ P ( P ( A ∪ B ) ) :‬‬ ‫מצאנו היכן נמצאים כל האיברים‪ ,‬וכעת נגדיר אותם‪:‬‬

‫• ‪ ‬בהינתן ‪ A, B‬נבנה בעזרת כלל האיחוד את ‪  . A ∪ B‬‬ ‫• ‪ ‬ע ידי הפעלת כלל החזקה נקבל את הקבוצה ) ) ‪  . P ( P ( A ∪ B‬‬ ‫• ‪ ‬בעזרת כלל הגזירה נגזור מתוך ) ) ‪ P ( P ( A ∪ B‬את כל הקבוצות שהן זוגות סדורים שבהם‬ ‫האיבר הראשון הוא מ‪ A -‬והאיבר השני הוא מ‪. B -‬‬

‫טענה‬ ‫יהיו שתי קבוצות לא ריקות ‪ , A, B‬אזי מתקיים כי‪. ∪ ∪ ( A × B ) = A ∪ B :‬‬

‫‪  27‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .4‬רלציות‬

‫‪  .4.1‬הגדרות בסיסיות‬ ‫יהיו ‪ A, B‬קבוצות‪.‬‬ ‫תת קבוצה )כלשהי( של ‪ A × B‬נקראת רלציה בינארית מ‪ A-‬ל‪.B-‬‬ ‫תת קבוצה של ‪ A × B × C‬נקראת רלציה טרנרית‪.‬‬ ‫תת קבוצה של ‪ A1 × A2 × ... × An‬נקראת רלציה ‪-n‬ארית‪.‬‬ ‫דוגמא‬ ‫תהי ‪ A‬הקבוצה }‪ A = {1, 2,3, 4‬ותהי ‪ B‬הקבוצה }‪ . B = {a, b, c‬דוגמא לרלציה מ‪ B-‬ל‪:A-‬‬

‫‪ ‬‬

‫‪R = { b, 4 , c,1 , b,1 }  ‬‬

‫נציג את הרלציה על ידי גרף )דו צדדי(‪:‬‬

‫במקרה הכללי ‪ -‬יתכנו צמתים שאין מהם חצים יוצאים או אין חצים נכנסים אליהם‪ .‬כמו כן יתכנו צמתים‬ ‫שיש להם יותר מחץ אחד נכנס או יוצא מהם‪.‬‬

‫‪  28‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫ייצוג על ידי מטריצה בינרית‬

‫‪4 ‬‬

‫‪3 ‬‬

‫‪2 ‬‬

‫‪1 ‬‬

‫‪B/A ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪a ‬‬

‫‪1 ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪1 ‬‬

‫‪b ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪0 ‬‬

‫‪1 ‬‬

‫‪c ‬‬

‫‪ ‬‬ ‫סימון‪ :‬אם ‪ a, b ∈ R‬נסמן ‪ . aRb‬אם ‪ a, b ∉ R‬נסמן ‪. a Rb‬‬

‫שאלה‬ ‫כמה רלציות קיימות מ‪ A-‬ל‪ B-‬כאשר ‪ A‬ו‪ B-‬הינן קבוצות סופיות?‬

‫כמספר תתי הקבוצות של ‪ , A × B‬שכן כל תת קבוצה של ‪ A × B‬היא רלציה מ‪ A-‬ל‪AxB = A ⋅ B .B-‬‬ ‫מספר תתי הקבוצות הוא‬

‫‪A⋅ B‬‬

‫‪.2‬‬

‫הגדרות‬ ‫תחום של רלציה ‪ -‬תחום של רלציה ‪ R ⊆ A × B‬היא הקבוצה‬

‫‪ xRy} ‬כך שמתקיים ‪ y ∈ B‬קיים |‪domain(R) ={x ∈ A‬‬ ‫כלומר תחום של רלציה הינו קבוצת הצמתים שיש מהן חצים יוצאים‪.‬‬

‫‪ ‬‬ ‫לדוגמא‪ :‬עבור ‪ R‬המוצג בצורה הבאה‪:‬‬

‫‪ ‬‬ ‫מתקיים כי }‪.domain(R)={a, b‬‬

‫‪  29‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪ ‬‬ ‫טווח של רלציה ‪ -‬טווח של רלציה ‪ R ⊆ A × B‬היא הקבוצה‬

‫‪ xRy} ‬כך שמתקיים ‪ x ∈ A‬קיים |‪range(R) ={Y ∈ b‬‬ ‫טווח של רלציה הינה קבוצת האיברים ב‪ B-‬שיש אליהם חצים נכנסים‪.‬‬

‫רלציה הופכית ‪ -‬רלציה הופכית של רלציה ‪ R ⊆ A × B‬היא הרלציה מ‪ B-‬ל‪ A-‬הבאה‪:‬‬

‫‪R −1 = { b, a | a, b ∈ R}  ‬‬ ‫כלומר‪. bR −1 A ⇔ aRb :‬‬

‫רלציה משלימה ‪ -‬רלציה משלימה לרלציה ‪ R ⊆ A × B‬היא הרלציה ‪  R c = A × B − R‬‬ ‫לכל ‪ a, b ∈ A × B‬מתקיים‪. aR cb ⇔ aR/ b :‬‬

‫‪  30‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫‪  .4.2‬הרכב רלציות‬ ‫כזכור‪ ,‬רלציה מ‪ A-‬ל‪ B-‬היא תת קבוצה של ‪ . A × B‬בהינתן רלציה ‪ R‬מ‪ A-‬ל‪ ( R ⊆ A × B ) B-‬ורלציה‬ ‫‪ S‬מ‪ B-‬ל‪ ( S ⊆ B × C ) C-‬ההרכב של ‪ R‬עם ‪ ,S‬המסומן על ידי ‪ , R S‬היא הרלציה‪:‬‬

‫‪R S = { x, z | x, y ∈ R, y, z ∈ S , ∀y ∈ B}  ‬‬ ‫‪ ‬‬ ‫דוגמא‬

‫‪A={1,2,3,4} ‬‬ ‫‪B={a,b,c} ‬‬ ‫‪C={T,F} ‬‬ ‫‪ ‬‬ ‫‪R= { 1,a , 1,b , 3,c }  ‬‬

‫‪A→B ‬‬

‫‪S= { a,T , b,T , c,T , c,F }  ‬‬

‫‪B →C ‬‬

‫‪ ‬‬

‫‪} ‬‬ ‫זוג נמצא ב‪ R S -‬אם קיים מסלול באורך ‪ 2‬בין איבריו‪.‬‬

‫‪  31‬‬

‫‪R S = { 1, T , 3, T , 3, F‬‬

‫‪  [email protected]‬‬

‫ניר אדר‬

‫תכונות של פעולת ההרכב‬ ‫‪ .1‬אסוציאטיביות‪ :‬לכל ‪ R1 , R2 , R3‬המקיימות ‪ R1 ⊆ A × B, R2 ⊆ B × C , R3 ⊆ C × D‬מתקיים כי‪:‬‬

‫‪( R1 R2 ) R3 = R1 ( R2 R3 )  ‬‬ ‫‪ ‬‬ ‫‪ .2‬לכל שתי רלציות‪ , R1 ⊆ A × B, R2 ⊆ BxC ,‬מתקיים‪:‬‬

‫‪−1‬‬

‫‪R1‬‬

‫‪−1‬‬

‫‪( R1 R2 ) −1 = R2‬‬

‫הוכחה‪:‬‬

‫‪ ‬הגדרת רלציה הופכית ⇔ ) ‪x, z ∈ ( R1 R2‬‬ ‫‪−1‬‬

‫‪ ‬הגדרת הרכב ⇔ ‪z, x ∈ R1 R2‬‬ ‫‪∃y ∈ B, z, y ∈ R1 , y, x ∈ R2 ⇔ ∃y ∈ B, y, z ∈ R1−1 , x, y ∈ R2 −1  ‬‬

‫ומכאן ‪x, z ∈ R2 −1 R1−1‬‬

‫‪  .4.3‬תכונות של יחסים‬ ‫‪  .1‬רפלקסיביות‪ :‬לכל ‪ , a ∈ A‬מתקיים ‪  . a, a ∈ R‬‬ ‫‪  .2‬סימטריות‪ :‬אם ‪ , ( a, b ) ∈ R‬מתקיים ‪  . ( b, a ) ∈ R‬‬ ‫‪  .3‬אנטי סימטריות‪ :‬אם ‪ a, b , b, a ∈ R‬אזי בהכרח ‪  . a = b‬‬ ‫‪  .4‬א‪-‬סימטריה‪ :‬אם ‪ , a, b ∈ R‬מתקיים ‪  . b, a ∉ R‬‬ ‫‪  .5‬טרנזיטיביות‪ :‬אם ‪ a, b , b, c ∈ R‬אזי ‪  . a, c ∈ R‬‬

‫‪  32‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫תהי הקבוצה }‪ . A = {a, b, c‬נגדיר יחס ‪ R‬מעל ‪: ( R ⊆ A × A ) A‬‬

‫‪R = { a , b , b, b , c , c , b , c , a , c }  ‬‬

‫האם היחס רפלקסיבי? לא‪ ,‬כי ‪ a, a ∉ R‬אבל ‪. a ∈ A‬‬ ‫האם היחס סימטרי? לא‪ ,‬כי ‪ a, b ∈ R‬אבל ‪  b, a ∉ R‬‬

‫האם היחס הוא אנטי סימטרי? כן‪ .‬הזוגות היחידים שמקיימים ‪ a, b , b, a ∈ R‬הם ‪ b, b‬ו‪c, c -‬‬ ‫לכן היחס הוא אנטי סימטרי‪.‬‬ ‫האם היחס הוא א‪-‬סימטרי? לא‪ ,‬כי ‪ b, b‬ו‪ c, c -‬נמצאים ביחס‪.‬‬ ‫האם היחס טרנזיטיבי? כן‪.‬‬

‫רפלקסיביות באופן ריק‬ ‫אם ‪ A ≠ φ‬ו‪ R-‬רפלקסיבי‪ ,‬אזי בהכרח ‪ . R ≠ φ‬רפלקסיביות נכונה באופן ריק רק כאשר ‪ R‬ריקה‪.‬‬

‫טרנזיטיביות באופן ריק‬

‫דוגמא‪} :‬‬

‫‪ . R = { a, b , a, c‬רלציה זו טרנזיטיבית באופן ריק‪.‬‬

‫דוגמא‬ ‫נתונות הקבוצות ‪ A, B, C‬כך שמתקיים ‪ A ∩ B = φ , A ≠ φ , B ≠ φ‬וגם ‪  . A ⊆ C , B ⊆ C‬‬

‫נגדיר יחס ‪ R‬מעל ‪:C‬‬ ‫‪R = A× B ⊆ C × C  ‬‬

‫‪  33‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫האם היחס רפלקסיבי?‬ ‫לא‪ , A ≠ φ .‬ומכאן קיים ‪ , B ≠ φ . a ∈ A‬ומכאן קיים ‪ . b ∈ B‬מכאן ‪a, b ∈ R‬‬

‫אם ‪ b=a‬אזי ‪ b ∈ A‬בסתירה לכך שהחיתוך בין ‪ A‬ל‪ B-‬הוא קבוצה ריקה‪.‬‬ ‫האם היחס סימטרי?‬ ‫לא‪ .‬יהי ‪) a, b ∈ R‬קיים כזה(‪ .‬אם ‪ b, a ∈ R‬אזי ‪ b ∈ A ∩ B‬בסתירה לנתון‪.‬‬

‫האם היחס אנטי סימטרי?‬ ‫כן‪ ,‬באופן ריק‪.‬‬ ‫אם ‪ a, b ∈ R‬וגם ‪ b, a ∈ R‬אזי ‪ b ∈ A ∩ B‬בסתירה לנתון‪.‬‬ ‫לכן אין זוג איברים ‪ a, b‬ו‪ b, a -‬הנמצאים שניהם ביחס‪.‬‬

‫האם היחס א‪-‬סימטרי?‬ ‫כן‪ .‬אם ‪ , a, b ∈ R‬נניח בשלילה שגם ‪ b, a ∈ R‬אזי ‪ b ∈ A ∩ B‬בסתירה לנתון‪.‬‬

‫האם היחס טרנזיטיבי?‬ ‫כן‪ ,‬באופן ריק‪.‬‬

‫טענה‬ ‫יהי ‪ R‬יחס‪ ,‬אזי מתקיים כי ‪ R‬סימטרי אמ"מ ‪. R = R −1‬‬ ‫הוכחה‪:‬‬ ‫⇐ נניח כי ‪ R‬סימטרי‪.‬‬ ‫ואז‪a, b ∈ R ⇔ b, a ∈ R ⇔ a, b ∈ R −1 :‬‬ ‫‪simetric‬‬

‫⇒ נניח כי ‪. R = R −1‬‬ ‫יהי ‪ . a, b ∈ R‬על פי הגדרת ‪ R −1‬נובע‪ . b, a ∈ R −1 :‬לפי הנתון ‪ R = R −1‬ולכן ‪. b, a ∈ R‬‬

‫‪  34‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5‬פונקציות‬

‫‪  .5.1‬הגדרות‬ ‫פונקציה מקבוצה ‪ A‬לקבוצה ‪ B‬היא רלציה מ‪ A-‬ל‪ B-‬המקיימת‪ :‬לכל ‪ a ∈ A‬קיים ‪ b ∈ B‬יחיד כך‬ ‫ש‪. a, b ∈ f -‬‬

‫סימונים )עבור פונקציות(‬ ‫‪ f ⊆ AxB‬נסמן כ‪f : A → B :‬‬ ‫‪ a, b ∈ f‬נסמן כ‪f (a ) = b :‬‬

‫הגדרה‬ ‫פונקציה ‪ f : A → B‬נקראת חד חד ערכית אם לכל ‪ x, y ∈ A‬מתקיים‪. f ( x ) ≠ f ( y ) ⇐ x ≠ y :‬‬

‫סימון‬ ‫‪1:1‬‬

‫‪f : A→ B  ‬‬

‫‪  35‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הגדרה‬ ‫פונקציה ‪ f : A → B‬נקראת על אם לכל איבר ‪ b ∈ B‬קיים ‪ a ∈ A‬כך ש‪. f (a ) = b -‬‬

‫הגדרה‬ ‫פונקציה ‪ f : A → B‬שהיא גם ‪ 1:1‬וגם על נקראת התאמה חח"ע‪.‬‬ ‫• ‪ ‬במקרה זה‪ ,‬הגודל של ‪ A‬ושל ‪ B‬הוא זהה‪  .‬‬ ‫‪ ‬‬

‫‪  .5.2‬שאלות קומבינטוריות‬ ‫נתונות ‪ A‬ו‪ B-‬קבוצות סופיות‪.‬‬ ‫‪ .1‬מהן מספר הפונקציות מ‪ A-‬ל‪ B-‬שהן התאמות חח"ע?‬ ‫‪ ‬‬

‫‪0‬‬ ‫‪‬‬ ‫!‪ B‬‬

‫‪A≠ B‬‬ ‫‪A=B‬‬

‫‪ ‬‬

‫‪ .2‬כמה פונקציות ‪ 1:1‬יש מ‪ A-‬ל‪?B-‬‬

‫‪B< A‬‬

‫‪0‬‬

‫‪B= A  ‬‬

‫!‪B‬‬

‫‪B> A‬‬

‫!‪B‬‬ ‫!) ‪− A‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪ ( B‬‬ ‫‪ ‬‬

‫‪ .3‬כמה פונקציות יש מ‪ A-‬ל‪?B-‬‬ ‫‪ ‬‬

‫‪  36‬‬

‫‪A‬‬

‫‪B‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .4‬כמה פונקציות יש מ‪ A-‬ל‪ B-‬שהן על?‬ ‫‪‬‬ ‫‪0‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫!‪B‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪B‬‬ ‫‪A‬‬ ‫‪i B ‬‬ ‫) ‪∑ (−1)  ( B − i‬‬ ‫‪ i =0‬‬ ‫‪ i ‬‬

‫‪B> A‬‬ ‫‪ ‬‬

‫‪B= A‬‬ ‫‪B< A‬‬

‫‪ ‬‬

‫‪  .5.3‬הפונקציה ההופכית‬ ‫יהיו ‪ A, B‬קבוצות‪ ,‬ותהי ‪ f : A → B‬פונקציה‪ .‬הרלציה ההופכית‬ ‫במקרה ש‪-‬‬

‫‪−1‬‬

‫‪−1‬‬

‫‪ f‬היא לא בהכרח פונקציה‪.‬‬

‫‪ f‬היא פונקציה‪ ,‬היא תיקרא הפונקציה ההופכית‪ .‬נשאל מתי‬

‫‪−1‬‬

‫‪ f‬היא פונקציה‪.‬‬

‫טענה‬ ‫תהי ‪. f : A → B‬‬ ‫‪  .1‬הרלציה ההופכית‬ ‫‪  .2‬במקרה ש‪-‬‬

‫‪−1‬‬

‫‪−1‬‬

‫‪ f‬היא פונקציה אמ"מ ‪ f‬הינה התאמה חח"ע‪  .‬‬

‫‪ f‬היא פונקציה‪ ,‬אזי גם היא התאמה חח"ע‪  .‬‬

‫הוכחה‪:‬‬ ‫‪  .1‬‬

‫‪−1‬‬

‫‪ f‬היא פונקציה אמ"מ לכל ‪ b ∈ B‬קיים ‪ a ∈ A‬יחיד‪ ,‬כך ש‪. b, a ∈ f −1 -‬‬

‫מהגדרת הפונקציה ההופכית‪ ,‬נובע כי לכל ‪ b ∈ B‬קיים ‪ a ∈ A‬יחיד כך ש ‪   a, b ∈ f‬וזה‬ ‫מתקיים אמ"מ ‪ f‬התאמה חח"ע‪  .‬‬ ‫‪−1 −1‬‬

‫‪)   .2‬‬

‫‪  37‬‬

‫‪ f . f = ( f‬היא פונקציה ולכן עפ"י ‪ 1‬מתקיים ש‬

‫‪−1‬‬

‫‪ f‬היא התאמה חח"ע‪  .‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫עבור שתי קבוצות סופיות ‪ , A, B‬מתקיים ‪ A = B‬אמ"מ קיימת התאמה חח"ע בין ‪ A‬ל‪.B-‬‬

‫הגדרה‬ ‫רלציה ‪ R‬מעל קבוצה ‪ A‬היא קבוצה של ‪: A × A‬‬ ‫}‪A = {1, 2,3, 4‬‬ ‫‪R1 = { 1,1 , 1,3 , 2, 4‬‬

‫}‬ ‫‪ ‬‬ ‫} ‪3,3‬‬

‫‪R2 = { 1,1 , 2, 2 ,‬‬ ‫}‪I a = { x, x | x ∈ A‬‬ ‫‪ ‬‬

‫‪ I a‬זוהי רלצית הזהות‪.‬‬ ‫ניתן לייצג רלציות בעזרת גרף דו צדדי כמו שכבר ראינו‪ ,‬אולם ניתן לייצג רלציות גם באמצעות גרף‪.‬‬ ‫את הגרף בונים בצורה הבאה‪ :‬מציירים צומת יחיד עבור כל איבר ב‪ .A-‬יש קשת בין הצומת ‪ x‬לצומת ‪y‬‬

‫אם הזוג הסדור ‪. x, y ∈ R‬‬

‫דוגמא‬ ‫‪R= { 1,1 , 1,2 , 2,3 , 3,4 , 4,3 }  ‬‬

‫‪  38‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .5.4‬תכונות של רלציה מעל קבוצה ‪A‬‬ ‫‪  .1‬רפלקסיביות‪ :‬לכל ‪ , a ∈ A‬מתקיים ‪a, a ∈ R‬‬

‫* לכל צומת בגרף חייבת להיות קשת עצמית‪.‬‬ ‫* אם זוהי פונקציה‪ ,‬זוהי חייבת להיות פונקצית הזהות‪  .‬‬ ‫‪  .2‬סימטריות‪ :‬אם ‪ , a, b ∈ R‬מתקיים ‪b, a ∈ R‬‬ ‫* לכל קשת בגרף יש קשת הפוכה לה‪  .‬‬ ‫‪  .3‬אנטי סימטריות‪ :‬אם ‪ a, b , b, a ∈ R‬אזי בהכרח ‪  a = b‬‬ ‫‪  .4‬א‪-‬סימטריה‪ :‬אם ‪ , a, b ∈ R‬מתקיים ‪  b, a ∉ R‬‬ ‫‪  .5‬טרנזיטיביות‪ :‬אם ‪ a, b , b, c ∈ R‬אזי ‪a, c ∈ R‬‬ ‫* אם יש מסלול באורך ‪ 2‬בין ‪ 2‬צמתים‪ ,‬אזי בהכרח יש גם מסלול ישיר ביניהם‪  .‬‬

‫‪  .5.5‬רלציות מיוחדות‬

‫‪ .5.5.1‬יחסי סדר‬ ‫יחס ‪ R‬יקרא יחס סדר חלקי אם ‪ R‬רפלקסיבי‪ ,‬טרנזיטיבי ואנטי‪-‬סימטרי‪.‬‬ ‫יחס ‪ R‬יקרא יחס סדר מלא אם הוא יחס סדר חלקי וגם לכל ‪ x, y ∈ A‬מתקיים ‪ x, y ∈ R‬או‬ ‫‪ . y , x ∈ R‬יחס זה נקרא גם יחס סדר ליניארי‪.‬‬

‫‪  39‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.5.2‬יחס שקילות‬ ‫יחס יקרא יחס שקילות אם הוא רפלקסיבי‪ ,‬סימטרי וטרנזיטיבי‪.‬‬ ‫בהמשך נעמיק עוד ביחסי שקילות‪.‬‬

‫‪ .5.5.3‬דוגמאות‬ ‫נסתכל על הרלציות הבאות מעל ‪:R‬‬ ‫הרלציה < ‪ :‬לא רפלקסיבית‪ ,‬לא סימטרית‪ ,‬טרנזיטיבית‪.‬‬ ‫הרלציה ≤ ‪ :‬רפלקסיבית‪ ,‬לא סימטרית‪ ,‬טרנזיטיבית – רלצית סדר חלקי וגם רלצית סדר מלא‪.‬‬ ‫הרלציה = ‪ :‬רפלקסיבית‪ ,‬סימטרית‪ ,‬טרנזיטיבית – רלצית שקילות וגם רלצית סדר חלקי‪.‬‬ ‫הרלציה ⊆ מעל קבוצות‪ :‬רפלקסיבית‪ ,‬לא סימטרית‪ ,‬טרנזיטיבית – רלצית סדר חלקי‪.‬‬ ‫הרלציה ⊂ מעל קבוצות‪ :‬לא רפלקסיבית‪ ,‬לא סימטרית‪ ,‬טרנזיטיבית‪.‬‬

‫טענה‬ ‫הרלציה ‪ R‬סימטרית אמ"מ ‪. R = R −1‬‬

‫‪  40‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .5.6‬חזקות של רלציה‬ ‫תהיי רלציה ‪ R‬מעל קבוצה ‪ ,A‬נסמן ב‪ R 2 -‬את ‪. R R‬‬ ‫הזוג ‪ x, z‬שייך ל‪ R 2 -‬אם קיים ‪ y‬כך ש ‪ . x, y ∈ R, y, z ∈ R‬כלומר אם קיימת קשת מ‪ x-‬ל‪y-‬‬

‫כלשהו‪ ,‬ומאותו ‪ y‬אל ‪ .z‬במילים אחרות ‪ -‬אם קיימת מסלול באורך ‪ 2‬בין ‪ x‬ל‪.z-‬‬ ‫באופן דומה‪ ,‬מסמנים ב ‪ R i‬את ההרכב הבא‪ i) . R R ... R :‬פעמים(‪.‬‬ ‫בגלל תכונת האסוציאטיביות של ההרכב נקבל את המסקנה‪. R i R j = R i + j :‬‬ ‫איבר ‪ x, z‬נמצא בגרף של ‪ R i‬אם קיים מסלול באורך ‪ i‬שבין ‪ x‬ל‪ z-‬בגרף של ‪.R‬‬

‫טענה‬ ‫‪ R‬טרנזיטיבית אמ"מ ‪. R 2 ⊆ R‬‬ ‫הוכחה‪:‬‬ ‫‪ R‬טרנזיטיבית ⇔ לכל ‪ x, y, z ∈ A‬מתקיים כי ‪. x, z ∈ R ⇐ x, y ∈ R, y, z ∈ R‬‬ ‫⇔ לכל ‪ x, z ∈ A‬מתקיים כי ‪R 2 ⊆ R ⇔ x, z ∈ R ⇐ x, z ∈ R 2‬‬

‫טענה )ללא הוכחה(‬ ‫לכל ‪ 3‬רלציות ‪ s1 , s 2 , s3‬מתקיים ‪. S1 ⊆ S 2 ⇒ S1 S 3 ⊆ S 2 S 3‬‬

‫‪  41‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫תהיינה הרלציות ‪. f ⊆ A × B, g ⊆ B × C‬‬ ‫פעולת ההרכבה מוגדרת כרגיל‪ a, c ∈ f g :‬אמ"מ קיים ‪ b ∈ B‬כך ש‪. a, b ∈ f , b, c ∈ g -‬‬ ‫ניתן לראות כי ‪ . f g ⊆ A × C‬נטען‪ :‬אם ‪ f , g‬הינן פונקציות אזי ההרכב ‪ f g‬הינו פונקציה‪.‬‬

‫הוכחה‪:‬‬ ‫על מנת להראות שרלציה היא פונקציה עלינו להראות‪:‬‬ ‫‪  .1‬קיום – לכל ‪ a ∈ A‬קים ‪ c ∈ C‬כך ש‪  . a, c ∈ f g -‬‬

‫‪  .2‬יחידות – אם ‪ a, x1 ∈ f g , a, x2 ∈ f g‬אזי בהכרח ‪. x1 = x2‬‬

‫‪.1‬‬ ‫יהי ‪. a ∈ A‬‬ ‫‪ f‬היא פונקציה ⇐ קיים ‪ b ∈ B‬כך ש‪. a, b ∈ f -‬‬ ‫‪ g‬היא פונקציה ⇐ קיים ‪ c ∈ C‬כך ש‪. b, c ∈ g -‬‬ ‫⇐ על פי הגדרת ההרכב מתקיים ‪. a, c ∈ f g‬‬ ‫⇐ לכל ‪ a ∈ A‬קיים ‪ c ∈ C‬כך ש‪. a, c ∈ f g -‬‬

‫‪.2‬‬ ‫יהיו ‪ x1 , x2‬כך ש‪. a, x1 ∈ f g , a, x2 ∈ f g -‬‬ ‫‪ f‬היא פונקציה ולכן‪:‬‬ ‫• ‪ ‬קיים ‪ b1‬כך ש‪ a, b1 ∈ f -‬וגם ‪  . b1 , x1 ∈ g‬‬ ‫• ‪ ‬קיים ‪ b2‬כך ש‪ a, b2 ∈ f -‬וגם ‪  . b2 , x2 ∈ g‬‬

‫‪ f‬היא פונקציה ולכן ‪) b1 = b2‬יחידות עבור ‪.( f‬‬ ‫‪ g‬היא פונקציה ולכן מכיוון ש‪ b, x2 ∈ g , b, x1 ∈ g -‬נקבל ‪. x1 = x2‬‬

‫‪  42‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫תרגיל‬ ‫‪2‬‬

‫תהי‬

‫→‬

‫‪2‬‬

‫‪ f :‬המוגדרת כך‪. f ( x, y ) = x + y, x − y :‬‬

‫יש לענות האם ‪ f‬היא על והאם היא חח"ע‪.‬‬

‫פתרון‬

‫יהי‬

‫‪2‬‬

‫∈ ‪. a, b‬‬

‫אם ‪ x, y → a, b‬אזי נוכל לכתוב‪. a = x + y, b = x − y :‬‬ ‫זוהי מערכת משוואות בעלת פתרון יחיד‪ ,‬שהפתרון לה הינו‪:‬‬ ‫‪ ‬‬

‫מכיוון שניתן להגיע לכל ‪ a, b‬כרצוננו בתחום‬

‫‪2‬‬

‫‪2‬‬

‫‪a +b a −b‬‬ ‫‪,‬‬ ‫∈‬ ‫‪2‬‬ ‫‪2‬‬

‫= ‪x, y‬‬

‫הרי שהפונקציה הינה על‪.‬‬

‫מכיוון שפתרון מערכת המשוואות הינו יחיד הפונקציה הינה חד חד ערכית‪.‬‬

‫תרגיל‬ ‫נתונות פונקציות ‪. f : X → Y , g : Y → Z‬‬ ‫צ"ל‪ :‬אם ‪ f g‬על וגם ‪ g‬הינה חח"ע אזי ‪ f‬היא על‪.‬‬

‫הוכחה‪:‬‬ ‫כדי להוכיח כי ‪ f‬היא על עלינו להראות כי לכל איבר ‪ y ∈ Y‬קיים ‪ x ∈ X‬כך שמתקיים ‪. f ( x ) = y‬‬ ‫יהי ‪. y ∈ Y‬‬ ‫‪ g‬היא פונקציה ולכן קיים ‪ z ∈ Z‬כך ש‪. g ( y ) = z -‬‬ ‫‪ f g‬על ולכן קיים ‪ x ∈ X‬כך שמתקיים ‪) g f ( x) = z‬כלומר ‪.( g ( f ( x) ) = z‬‬ ‫כלומר בינתיים הגענו לכך ש‪. g ( y ) = z, g ( f ( x) ) = z :‬‬ ‫‪ g‬הינה חח"ע ולכן )‪ . y = f ( x‬הראנו בעצם כי קיים איבר ‪ y ∈ Y‬כך ש‪ f ( x ) = y -‬ובכך סיימנו‪.‬‬

‫‪  43‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫‪ R‬טרנזיטיבית אמ"מ לכל ‪. R i ⊆ R i −1 ⊆ R i − 2 ⊆ ... ⊆ R 2 ⊆ R ,1 ≤ i‬‬ ‫הוכחה‪) :‬באינדוקציה על ‪(i‬‬ ‫בסיס‪ i = 2 :‬ראינו בטענה הקודמת ) ‪.( R 2 ⊆ R‬‬ ‫נניח את נכונות הטענה לכל ‪ i ≤ n‬ונוכיח עבור ‪. i = n + 1‬‬ ‫על פי ההנחה מתקיים כי ‪. R n ⊆ R n −1 ⊆ R n − 2 ⊆ ... ⊆ R 2 ⊆ R‬‬ ‫יש להוסיף‪. R n +1 ⊆ R n :‬‬ ‫על פי ההנחה ‪ R n ⊆ R n −1‬ולכן על פי טענה העזר ‪ , R n R ⊆ R n −1 R‬כלומר ‪. R n +1 ⊆ R n‬‬

‫‪  .5.7‬הסגור של רלציה ביחס לתכונה‬ ‫תהיי ‪ R‬רלציה מעל קבוצה ‪ .A‬הסגור של ‪ R‬ביחס לתכונה ‪ α‬היא הרלציה ‪ S‬המקיימת את התנאים‬ ‫הבאים‪:‬‬ ‫‪ S  .1‬מקיימת את ‪. α‬‬ ‫‪  R ⊆ S   .2‬‬ ‫‪  .3‬לכל ‪ T‬שמקיימת את ‪ , α‬ו ‪ , R ⊆ T‬מתקיים ‪  S ⊆ T‬‬

‫הסגור היא הרלציה הקטנה ביותר שמקיימת את ‪ α‬ומכילה את ‪.R‬‬ ‫לא תמיד קיים סגור עבור תכונה‪ .‬עבור תכונות מסוימות יהיה קיים סגור ועבור אחרות לא‪  .‬‬

‫סגור ביחס לתכונה מסויימת – אם הוא קיים אזי הוא יחיד‪.‬‬

‫‪  44‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.7.1‬סגור רפלקסיבי‬ ‫דוגמא‬ ‫תהי הקבוצה }‪ A = {1, 2,3‬ותהי הרלציה } ‪. R = { 1, 2 , 2, 2 , 3,1‬‬ ‫הסגור הרפלקסיבי של הרלציה הינו } ‪. { 1,1 ,  2,2 ,  3,3 ,  1, 2 ,  3, 1‬‬

‫‪ 1,1 , 2, 2 , 3,3‬נובע מהגדרת רפלקסיביות‪.‬‬ ‫‪ 1, 2 , 3,1‬נובע מהגדרת הסגור‪.‬‬

‫זוהי הקבוצה הקטנה ביותר המקיימת את התנאי‪.‬‬ ‫• ‪ ‬הסגור הרפלקסיבי הוא תמיד }‪  R ∪ I a , I a = { a, a | a ∈ A‬‬

‫• ‪ ‬סגור של רלציה ביחס לתכונה נתונה היא הרלציה הקטנה ביותר המכילה את הרלציה ומקיימת‬ ‫את התכונה‪  .‬‬

‫‪ .5.7.2‬סגור סימטרי‬ ‫דוגמא‬ ‫תהי הקבוצה }‪ A = {1, 2,3, 4‬ותהי הרלציה מעל ‪. R = { 1, 2 , 3,3 , 3, 4 , 4,1 } A‬‬

‫הסגור הסימטרי יהיה }‬

‫‪. { 1, 2 , 3,3 , 3, 4 , 4,1 , 2,1 , 4,3 , 1, 4‬‬

‫• ‪ ‬הסגור הסימטרי הינו תמיד }‪  . R ∪ R −1 = R ∪ { a, b | b, a ∈ R‬‬

‫‪  45‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.7.3‬סגור א‪-‬רפלקסיבי‬ ‫רלציה ‪ R‬תיקרא א‪-‬רפלקסיבית אם לכל ‪ x ∈ A‬מתקיים ‪. x, x ∉ R‬‬

‫תהי לדוגמא הרלציה הבאה מעל הקבוצה }‪: A = {1, 2,3‬‬ ‫‪R= { 1,2 , 2,2 , 3,1 , 3,2 }  ‬‬

‫במקרה זה הסגור לא קיים‪ ,‬כי הסגור חייב להכיל את כל ‪ ,R‬ובפרט את הזוג הסדור ‪ , 2, 2‬וכל רלציה‬ ‫כזו לא מקיימת את תכונת הא‪-‬רפלקסיביות‪.‬‬

‫‪ .5.7.4‬סגור טרנזיטיבי‬ ‫תהי הקבוצה }‪ A = {1, 2,3, 4,5‬ותהי הרלציה } ‪. R = { 1, 2 , 2,3 , 2, 4 , 4,5 , 5,1‬‬ ‫הסגור הטרנזיטיבי יהיה‬

‫}‬

‫‪. { 1, 2 , 2,3 , 2, 4 , 4,5 , 5,1 , 1,3 , 4,1 , 1, 4 , 1,5 , 2,5 , 4, 2‬‬ ‫‪ ‬‬ ‫• ‪ ‬נשים לב שאם אחרי שהוספנו איברים‪ ,‬ניתן לעשות חיבורים נוספים‪ ,‬יש לעשותם‪  .‬‬

‫בהינתן רלציה ‪ R‬מעל ‪ ,A‬נגדיר את הרלציה *‪ R‬באופן הבא‪:‬‬ ‫‪− {0}  ‬‬

‫= ‪R* = R ∪ R 2 ∪ R 3 ∪ ... = ∪ R i , i‬‬

‫מתקיים כי *‪ x, y ∈ R‬אמ"מ קיים ‪ i ≥ 1‬כך ש ‪. x, y ∈ R i‬‬

‫טענה‬ ‫• ‪ ‬אם רלציה מקיימת את ‪ , α‬אז היא עצמה הסגור שלה ביחס ל‪ . α -‬מכאן שהסגור הטרנזיטיבי‬ ‫של רלציה טרנזיטיבית ‪ R‬הוא ‪  .R‬‬

‫‪  46‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫‪ ‬‬

‫• ‪ ‬לכל רלציה ‪ R* , R‬הוא הסגור הטרנזיטיבי שלה‪.‬‬ ‫‪ ‬‬

‫הוכחה‪:‬‬ ‫כדי להוכיח ש‪ R* -‬היא הסגור הטרנזיטיבי של ‪ R‬צ"ל‪:‬‬ ‫‪. R ⊆ R* .1‬‬ ‫‪ R* .2‬טרנזיטיבית‪.‬‬ ‫‪ .3‬לכל רלציה ‪ , T‬אם ‪ T‬היא טרנזיטיבית וגם ‪ R ⊆ T‬אזי ‪. R* ⊆ T‬‬ ‫‪.1‬‬ ‫ברור שמתקיים‪ ,‬כי ‪. R* = R ∪ R 2 ∪ ... ⊇ R‬‬ ‫‪.2‬‬ ‫צריך להוכיח כי אם *‪ x, y , x, z ∈ R‬אזי *‪. x, z ∈ R‬‬

‫*‪ x, y , x, z ∈ R‬גורר כי קיים ‪ x, y ∈ R i , i ≥ 1‬וקיים ‪ y , z ∈ R j , j ≥ 1‬כך ש‬ ‫‪y , z ∈ R* ⇐ y , z ∈ R i + j ⇐ y , z ∈ R i ⋅ R j‬‬

‫‪.3‬‬ ‫נשתמש בטענה אם ‪ R ⊆ T‬אזי לכל‬

‫∈ ‪ i‬מתקים ‪. R i ⊆ T i‬‬

‫תהי ‪ T‬טרנזיטיבית‪ . R ⊆ T ,‬צריך להוכיח כי ‪R* ⊆ T‬‬

‫יהי *‪ . x, y ∈ R‬מכאן קיים ‪ k‬כך ש‪ . x, y ∈ R k -‬ולפי טענת העזר‪. R ⊆ T :‬‬ ‫‪ T‬טרנזיטיבית‪ .‬מכאן קיים ‪ k‬כך ש‪ ,. x, y ∈ T k -‬ולכן ‪. x, y ∈ T‬‬

‫תכונה‬ ‫• ‪ ‬אם ‪ A‬סופית אזי‬

‫‪  47‬‬

‫‪A‬‬

‫‪. R* = R ∪ R 2 ∪ ... ∪ R‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫נגדיר את הקבוצה הבאה‪ B = { A | A ⊆ , A ≠ φ , A ≤ 10} :‬ונגדיר יחס ‪ S‬מעל ‪ B‬בצורה הבאה‪:‬‬ ‫‪S = { A1 , A2 | A1 ∩ A2 ≠ φ }  ‬‬ ‫‪ ‬‬ ‫‪  .1‬האם ‪ S‬הינו יחס טרנזיטיבי? ‪ ‬‬ ‫‪  .2‬מהו * ‪  ? S‬‬

‫‪.1‬‬ ‫‪ S‬איננו יחס טרנזיטיבי‪.‬‬ ‫דוגמא נגדית‪ :‬יהיו הקבוצות }‪. A1 = {1, 2} , A2 = {2,3} , A3 = {3, 4‬‬ ‫מתקיים‪ A1 , A2 ∈ S , A2 , A3 ∈ S :‬אולם ‪. A1 , A3 ∉ S‬‬ ‫‪.2‬‬ ‫כאשר אנו נתקלים בשאלה מסוג זה‪ ,‬השלב הראשון בפיתרון יהיה להבין מיהו ‪ S 2‬על מנת לקבל תחושה‬ ‫לגבי הפתרון‪.‬‬

‫}‬

‫‪∃A2 : A2 , A3 ∈ S , A1 , A2 ∈ S  ‬‬

‫נטען‪. S 2 = B × B :‬‬ ‫ברור כי ‪ S 2 ⊆ B × B‬מכיוון ש‪ S -‬הינו יחס מעל ‪. B‬‬ ‫צ"ל‪. B × B ⊆ S 2 :‬‬ ‫תהינה ‪ . A1 , A3 ∈ B‬צריך למצוא ‪ A2‬כך שמתקיים ‪. A1 , A2 ∈ S , A2 , A3 ∈ S‬‬ ‫‪ . ∃a1 ∈ A1 ⇐ A1 ≠ φ ⇐ A1 ∈ B‬כמו כן ‪. ∃a3 ∈ A3 ⇐ A3 ≠ φ ⇐ A3 ∈ B‬‬ ‫נבחר } ‪ . A2 = {a1 , a3‬נוודא כי ‪. A2 ∈ B‬‬ ‫‪ a1 ∈ A1 ∩ A2 ≠ φ‬ומכאן ‪ a2 ∈ A2 ∩ A3 ≠ φ . A1 , A2 ∈ S‬ומכאן ‪. A2 , A3 ∈ S‬‬ ‫מסקנה‪. A1 , A3 ∈ S 2 :‬‬

‫‪  48‬‬

‫‪{ A,A‬‬

‫‪3‬‬

‫‪1‬‬

‫= ‪S2‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬

‫נתון‬

‫}‬

‫×‬

‫{‬

‫⊆ ‪ , R = a, b a + b  is odd , R‬לדוגמא ‪. 1, 2 ∈ R‬‬

‫א‪ .‬מצא את ‪. R 2‬‬ ‫ב‪ .‬מצא את הסגור הטרנזיטיבי‪.‬‬ ‫א‪.‬‬

‫}‬

‫נסמן את הקבוצה הבאה ב‪a + b  is even : T -‬‬

‫}‬

‫נטען‪ , R 2 = T :‬כאשר ‪x, z , z , y ∈ R‬‬

‫‪{ a, b‬‬

‫‪{ x, y‬‬

‫= ‪.T‬‬

‫= ‪. R2‬‬

‫יהיו ‪. z, y , x, z ∈ R‬‬ ‫יתכנו שני מקרים‪:‬‬ ‫‪ z .1‬אי זוגי‪ x ,‬זוגי ⇐ ‪ y‬זוגי‪.‬‬ ‫‪ z .2‬זוגי‪ x ,‬אי זוגי ⇐ ‪ y‬אי זוגי‪.‬‬

‫בשני המקרים מתקיים ‪ x + y‬הוא זוגי‪ ,‬ולכן הראנו ‪. R 2 ⊆ T‬‬

‫כעת נראה את הכיוון השני‪ :‬יהיה האיבר ‪. a, b ∈ R 2‬‬ ‫אם ‪ a‬זוגי‪ ,‬נבחר ‪ c = 1‬ואז ‪ . b, c , a, c ∈ R‬אם ‪ a‬אי זוגי‪ ,‬נבחר ‪ c = 2‬ואז ‪. b, c , a, c ∈ R‬‬ ‫ומכאן ‪ . T ⊆ R 2‬הראנו הכלה דו כיוונית ולכן מתקיים השוויון‪.‬‬ ‫ב‪.‬‬ ‫ניתן לראות כי מתקיים ‪ , R 3 = R‬וכך הלאה‪ ,‬ולכן‪:‬‬ ‫‪ ‬‬

‫כלומר‬

‫‪  49‬‬

‫×‬

‫= ‪. R* = R ∪ R 2‬‬

‫‪i  is odd‬‬ ‫‪i  is even‬‬

‫‪R‬‬ ‫‪Ri =  2‬‬ ‫‪R‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .5.8‬רלצית שקילות‬ ‫רלציה תקרא רלצית שקילות אם היא רפלקסיבית‪ ,‬סימטרית וטרנזיטיבית‪.‬‬ ‫‪ R‬רפלקסיבית אם לכל ‪ x‬מתקיים ‪x, x ∈ R‬‬ ‫‪ R‬סימטרית אם לכל ‪ x, y‬כך ש‪ x, y ∈ R -‬מחייב כי ‪y , x ∈ R‬‬

‫‪ R‬טרנזיטיבית אם לכל ‪ x, y, z‬מתקיים ‪  x, z ∈ R ⇐ x, y ∈ R, y, z ∈ R‬‬ ‫‪ ‬‬

‫‪ .5.8.1‬מחלקת שקילות‬ ‫בהינתן יחס ‪ E‬מעל ‪ A‬ואיבר ‪ , x ∈ A‬נגדיר את מחלקת השקילות של ‪ x‬המסומנת על ידי‬

‫‪[ x ]E‬‬

‫באופן הבא‪:‬‬ ‫‪x, y ∈ E }  ‬‬

‫| ‪[ x ]E = { y‬‬ ‫‪ ‬‬

‫דוגמא‬ ‫‪ - A1‬קבוצת האנשים בעולם‪.‬‬

‫}‬

‫{‬

‫‪E1 = x, y x, y  live in the same country  ‬‬

‫‪ - A2‬כל המילים בעולם‪.‬‬

‫}‬

‫{‬

‫‪E2 = x, y x, y  starts with the same letter  ‬‬

‫‪ ‬‬ ‫‪ - A3‬קבוצת המספרים הטבעיים‪.‬‬

‫}‬

‫{‬

‫‪E3 = x,y x, y  has the same module in diving by 3  ‬‬

‫‪ ‬‬ ‫עבור ‪ - E1‬מהי מחלקת השקילות של ‪ x‬הגר בישראל?‬

‫‪} ‬כל תושבי ישראל{=]‪[x‬‬ ‫עבור ‪ - E 2‬מהי מחלקת השקילות של המילה "אבא"?‬

‫‪ } ‬כל המילים המתחילות ב‪-‬א'{=]אבא[‬

‫‪  50‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫עבור ‪: E3‬‬

‫‪[0]={0,3,6,9,...} ‬‬ ‫‪[1]={1,4,7,10,...} ‬‬ ‫‪[2]={2,5,8,11,...} ‬‬ ‫‪[3]= {0,3,6,9,...} ‬‬ ‫‪[4]={1,4,7,10,...} ‬‬ ‫ניתן לראות כי‪:‬‬

‫‪[0]=[3]=[6]=... ‬‬ ‫‪[1]=[4]=[7]=... ‬‬ ‫‪[2]=[5]=[8]=... ‬‬ ‫‪[0] ∩ [1] = φ‬‬ ‫‪[1] ∩ [2] = φ  ‬‬ ‫‪[0 ] ∩ [ 2 ] = φ‬‬

‫מתקיים‪:‬‬ ‫‪ ‬‬

‫‪ .5.8.2‬למה ‪1‬‬ ‫תהי ‪ A‬קבוצה‪ ,‬שני איברים ‪ x, y ∈ A‬ותהי ‪ E‬רלצית שקילות מעל ‪ ,A‬אזי‪:‬‬ ‫א‪ [ x ] = [ y ] .‬אמ"מ ‪. x, y ∈ E‬‬ ‫ב‪ [ x] ≠ [ y ] .‬אמ"מ ‪. [ x] ∩ [ y ] = φ‬‬ ‫• ‪ ‬מחלקת שקילות היא לא קבוצה ריקה )היא מתאפיינת על ידי איבר מסויים( ‪ ‬‬ ‫• ‪ ‬ניתן לכתוב את ב' גם כך‪ x, y ∉ E :‬אמ"מ ‪  . [ x] ∩ [ y ] = φ‬‬

‫‪  51‬‬

‫= ]‪[0] ∪ [1] ∪ [2‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחה‬ ‫א‪.‬‬ ‫⇐‬

‫נתון‪. [ x ] = [ y ] :‬‬ ‫צ"ל‪. x, y ∈ E :‬‬ ‫הוכחה‪ :‬לפי הגדרה‪ . y ∈ [ y ] :‬נתון כי ] ‪ [ x ] = [ y‬ומכאן ] ‪. x, y ∈ E ⇐ y ∈ [ x‬‬ ‫⇒‬ ‫נתון‪x, y ∈ E :‬‬

‫צ"ל‪[ x ] = [ y ] :‬‬ ‫הוכחה‪ :‬ראשית נטען כי ‪) y , x ∈ E‬מכיוון ש‪ E -‬הינה סימטרית(‪ .‬וכעת‪:‬‬ ‫‪a ∈ [ y]    ‬‬

‫⇔‬

‫‪ ‬הגדרת‬ ‫‪ ‬מחלקות שקילות‬

‫‪y, a ∈ E‬‬

‫⇔ ‪x, a ∈ E‬‬

‫טרנזיטיביות‬ ‫‪y , x , x ,a‬‬

‫⇔ ]‪a ∈ [ x‬‬

‫‪by‬‬ ‫‪definition‬‬

‫ולכן ] ‪. [ x ] = [ y‬‬

‫ב‪.‬‬ ‫⇒‬

‫נתון‪. [ x] ∩ [ y ] = φ :‬‬ ‫צ"ל‪. [ x] ≠ [ y ] :‬‬ ‫הטענה נכונה באופן טריויאלי מכיוון שגם ] ‪ [ x‬וגם ] ‪ [ y‬אינן ריקות‪.‬‬ ‫⇐‬

‫נתון‪. [ x] ≠ [ y ] :‬‬ ‫צ"ל‪. [ x] ∩ [ y ] = φ :‬‬ ‫נניח בשלילה כי ‪ . [ x] ∩ [ y ] ≠ φ‬כלומר קיים ] ‪ a ∈ [ x ] , [ y‬ומכאן‪:‬‬

‫‪[ x] = [ y]  ‬‬ ‫כלומר ההנחה שגויה ולכן ‪. [ x] ∩ [ y ] = φ‬‬

‫‪  52‬‬

‫⇒ ‪⇒ x, y ∈ E‬‬

‫‪Lemma 1‬‬

‫‪x, a ∈ E‬‬ ‫‪a, y ∈ E‬‬

‫⇒‬

‫‪x, a ∈ E‬‬ ‫‪y, a ∈ E‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.8.3‬הצגת רלצית שקילות כגרף‬ ‫כאשר ניגשתי בפעם הראשונה להבין את נושא רלצית השקילות ומחלקות השקילות נתקלתי בבעיה‬ ‫להבין את המשמעות שלהן בדיוק – מהי רלצית שקילות‪ ,‬ומהי מחלקת שקילות‪ ,‬ומהן אוסף כל מחלקות‬ ‫השקילות של קבוצה‪ .‬הדוגמא הבאה‪ ,‬לפחות עבורי‪ ,‬עזרה להמחיש את הנושא‪.‬‬ ‫תהי קבוצת איברים ‪ .A‬כל רלציה ‪ R‬מעל הקבוצה ‪ A‬מכילה זוגות של איברים מ‪.A-‬‬ ‫נציג את הרלציה כגרף‪ ,‬כאשר כל צומת בגרף ייצג את אחד מאיברי ‪ .A‬בין כל שני איברים בגרף תהיה‬ ‫קשת אמ"מ הם נמצאים ברלציה ‪.R‬‬ ‫לדוגמא‪ ,‬עבור הקבוצה }‪A = {1, 2,3, 4‬‬

‫והרלציה })‪{(1, 2 ) , (1,3) , ( 3,3‬‬

‫נצייר את הגרף הבא‪:‬‬ ‫‪ ‬‬

‫רלצית שקילות תחלק את הצמתים בגרפים לקבוצות זרות כך שכל קבוצה תהווה גרף מלא‪ ,‬לכל צומת‬ ‫תהיה קשת עצמית‪ ,‬ולא יהיו קשתות מחברות בין הקבוצות השונות‪ ,‬לדוגמא‪:‬‬

‫ישנן ‪ 3‬קבוצות – שלוש מחלקות שקילות הנוצרות על ידי רלצית השקילות‪.‬‬

‫‪  53‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.8.4‬קבוצת המנה‬ ‫הגדרה‬

‫תהא ‪ E‬רלצית שקילות מעל הקבוצה ‪ . A‬הקבוצה‬

‫‪E‬‬

‫‪ A‬מוגדרת כך‪:‬‬ ‫‪= {[ x] | x ∈ A}  ‬‬

‫‪E‬‬

‫‪A‬‬

‫קבוצה זו נקראת קבוצת המנה של ‪ A‬לפי ‪. E‬‬ ‫נגדיר את האינדקס של הרלציה ‪ E‬להיות מספר מחלקות השקילות השונות של ‪ , E‬או לחילופין –‬ ‫כגודל של קבוצת המנה של ‪. E‬‬

‫‪ .5.8.5‬למה ‪2‬‬

‫לכל‬

‫‪E‬‬

‫‪ , B1 , B2 ∈ A‬או ש‪ B1 ∩ B2 = φ -‬או ש‪. B1 = B2 -‬‬

‫‪ .5.8.6‬למה ‪3‬‬ ‫‪ E‬רלצית שקילות מעל ‪ .A‬איחוד כל מחלקות השקילות ייתן את הקבוצה ‪:A‬‬

‫‪∪[ x] = A . ‬‬ ‫‪x∈A‬‬

‫‪  54‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחת למה ‪3‬‬ ‫נוכיח את הטענה על ידי הכלה דו כיוונית‪.‬‬ ‫כיוון ⇐ ‪ :‬צ"ל להוכיח כי ‪ . ∪ [ x ] ⊆ A‬לכל ‪ x ∈ A‬מתקיים ‪ [ x ] ⊆ A‬ומכאן ‪. ∪ [ x ] ⊆ A‬‬ ‫‪x∈ A‬‬

‫‪x∈ A‬‬

‫כיוון ⇒ ‪ :‬צ"ל כי ] ‪ . A ⊆ ∪ [ x‬לכל ‪ x ∈ A‬מתקיים כי ] ‪ x ∈ [ x‬ולכן ] ‪. A ⊆ ∪ [ x‬‬ ‫‪x∈A‬‬

‫‪x∈A‬‬

‫‪ .5.8.7‬חלוקה‬ ‫הגדרה‬ ‫תהא ‪ A‬קבוצה כלשהי‪ .‬תתי קבוצות של ‪ A‬לא ריקות‪ ,‬זרות הדדית שאיחודן הוא ‪ A‬נקרא חלוקה‬

‫של ‪. A‬‬ ‫באופן פורמלי‪ :‬קבוצה ‪ Π‬היא חלוקה של קבוצה ‪ A‬אם מתקיימים התנאים הבאים‪:‬‬ ‫א‪ .‬אם כל איבר של ‪ Π‬הוא תת קבוצה לא ריקה ב‪.A-‬‬ ‫ב‪ .‬בעבור כל ‪ x ∈ A‬קיים בדיוק איבר אחד ‪ S ∈ Π‬עבורו ‪. x ∈ S‬‬

‫משפט‬

‫תהי ‪ E‬רלצית שקילות מעל ‪ . A‬קבוצת המנה‬

‫‪  55‬‬

‫‪E‬‬

‫‪ A‬היא חלוקה של הקבוצה ‪. A‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחה‬ ‫על פי הגדרת מחלקת השקילות מתקיים כי ‪ [ x ] ∈ A‬לכל ‪. x ∈ A‬‬ ‫כלומר האיברים בקבוצת המנה הם תתי קבוצה של ‪. A‬‬ ‫• ‪ ‬לכל ‪ x ∈ A‬מתקיים ‪ [ x ] ≠ φ‬ולכן האיברים ב‪ A -‬הם אינם קבוצות ריקות‪  .‬‬ ‫‪E‬‬ ‫• ‪ ‬על פי למה ‪ 2‬כל האיברים ב‪ A -‬הינם זרים הדדית‪  .‬‬ ‫‪E‬‬ ‫• ‪ ‬על פי למה ‪ 3‬איחוד האיברים בקבוצת המנה שווה ל‪  . A -‬‬

‫מסקנה‬ ‫כל יחס שקילות משרה חלוקה של ‪ A‬לקבוצות לא ריקות זרות הדדית שאיחודן ‪ , A‬כאשר הקבוצות הינן‬ ‫מחלקות השקילות של היחס‪.‬‬

‫טענה‬ ‫אם ‪ Π‬היא חלוקה של קבוצה ‪ A‬אזי היחס הבא הוא יחס שקילות‪.‬‬ ‫‪E = { x, y | ( ∃S , S ∈ Π ) , x ∈ S  and y ∈ S }  ‬‬

‫ומכאן‪= Π :‬‬

‫‪E‬‬

‫‪.A‬‬

‫כל חלוקה של ‪ A‬מגדירה באופן יחיד יחס שקילות‪ ,‬והקבוצות הזרות בחלוקה הן מחלקות השקילות של‬ ‫היחס‪.‬‬

‫‪  56‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .5.8.8‬דוגמאות‬ ‫‪.1‬‬ ‫‪ A‬קבוצת השלמים בין ‪ 0‬ל‪.100-‬‬ ‫‪R = { x, y | x ≡ y (mod10)}  ‬‬ ‫רפלקסיביות‪ :‬כן‪x ≡ x (mod10) :‬‬ ‫סימטריות‪ :‬כן‪x ≡ y (mod 10) ⇒ y ≡ x(mod 10) :‬‬

‫טרנזיטיביות‪ :‬כן‪:‬‬

‫⇒ )‪x ≡ y (mod 10), y ≡ z (mod 10‬‬ ‫)‪x ≡ z (mod10‬‬

‫לכן זוהי רלצית שקילות‪ .‬כעת נגדיר מי הן מחלקות השקילות‪ ,‬ונמצא את קבוצת המנה‪.‬‬ ‫מחלקות השקילות מאופיינות על ידי השאריות בחלוקה ב‪ .10‬לכן קבוצת המנה היא‪:‬‬ ‫‪A = {[0],[1],[2],[3],[4],[5],[6],[7],[8],[9]} = {[ x] | 0 ≤ x ≤ 9, x ∈ N }  ‬‬ ‫‪R‬‬

‫‪.2‬‬ ‫‪ A‬קבוצה‪ B ,‬תת קבוצה של ‪.A‬‬ ‫‪R = { x, y | x = y  or x, y ∈ B}  ‬‬

‫רפלקסיביות‪ :‬כן‪ :‬כי ‪.x=x‬‬ ‫סימטריות‪ :‬כן‪ .xRy :‬אם ‪ x=y‬אז ברור ש‪ yRx‬כי הם שווים‪.‬‬ ‫אם ‪   x ≠ y‬אזיי ‪ x,y‬שייכים ל‪ B‬ולכן גם ‪ y,x‬שייכים ל‪ B-‬ולכן ‪.yRx‬‬ ‫טרנזיטיביות‪ :‬כן‪ .xRy,yRz :‬אם כולם זהים ברור כי ‪ .xRz‬אם ‪ x,y,z‬לא זהים כולם‪ ,‬אזי‬ ‫הם שייכים ל‪ ,B-‬ולכן ‪.xRz‬‬ ‫אפיון מחלקות השקילות‪:‬‬ ‫מחלקת שקילות אחת היא ‪ B‬וכל איבר ב‪ A-‬מהווה מחלקת שקילות‪.‬‬ ‫‪B =φ‬‬ ‫}‪A =  {[ x] | x ∈ A \ B‬‬ ‫‪ ‬‬ ‫‪R {[ x] | x ∈ A \ B}∪ {B} B ≠ φ ‬‬

‫‪ ‬‬

‫נשים לב לכתיבה‪ . {[ x] | x ∈ A \ B}∪ {B} :‬הכתיבה ‪ {[ x] | x ∈ A \ B}∪ B‬היא טעות במקרה זה‪.‬‬

‫‪  57‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הסבר בעזרת דוגמא‪:‬‬ ‫‪A = { 1, 2, 3, 4, 5 } ‬‬ ‫‪B = { 1, 2 } ‬‬

‫}}‪{[ x] | x ∈ A \ B}∪ {B} = {{3},{4},{5},{1,2‬‬ ‫‪  ‬‬ ‫}‪{[ x] | x ∈ A \ B}∪ {B} = {{3},{4},{5},1,2‬‬ ‫הביטוי השני הוא כבר לא חלוקה למחלקות שקילות!‬

‫‪.3‬‬ ‫מה מספר רלציות השקילות בקבוצה סופית ‪?A‬‬ ‫הגדרת קבוצת מנה מגדירה רלציה ולהפך‪ .‬השאלה היא למעשה כמה חלוקות אפשריות‪.‬‬ ‫נניח כי ‪ .|A|=n‬מספר הרלציות הוא מספר האפשרויות לחלק את האלמנטים לתתי קבוצות כך שבכל‬ ‫קבוצה אלמנט אחד לפחות‪ ,‬ואין אלמנט המופיע ביותר מקבוצה אחת‪.‬‬ ‫כלומר‪ ,‬הבעיה שקולה לחלוקה של ‪ n‬אלמנטים שונים לתאים זהים‪ ,‬כך שאין תא ריק ואין הגבלה על‬ ‫מספר התאים‪.‬‬

‫‪  58‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .6‬עוצמות‬

‫‪  .6.1‬הקדמה לעוצמות‬ ‫מטרת נושא העוצמות היא לדבר על קבוצות בעלות אותו מספר איברים‪.‬‬ ‫עבור קבוצה סופית ‪ A‬גודל הקבוצה הינו ‪ . A‬עוצמת הקבוצה היא הגודל של ‪. A‬‬ ‫גודל במקרה זה הוא מספר האיברים בקבוצה‪.‬‬

‫משפט‬ ‫תהינה ‪ A‬ו‪ B -‬קבוצות סופיות‪ .‬מתקיים כי ‪ A = B‬אמ"מ קיימת התאמה חד חד ערכית ‪. f : A → B‬‬

‫הוכחה‪:‬‬ ‫תהינה הקבוצות } ‪. A = {a1 ,..., ak } , B = {b1 ,..., bn‬‬ ‫כיוון ⇐ ‪ :‬נניח כי ‪ . n = k‬נגדיר ‪ f : A → B‬כך‪ . f ( ai ) = bi ,1 ≤ i ≤ n :‬קל לראות ש‪ f -‬התאמה‬ ‫חד חד ערכית‪.‬‬ ‫כיוון ⇒ ‪ :‬נניח כי קיימת התאמה חח"ע – מאחר ו‪ f -‬חח"ע מתקיים כי ) ‪ f ( a1 ) ,..., f ( ak‬הם ‪k‬‬

‫איברים שונים ב‪ , B -‬ולכן ‪ . n ≥ k‬מאחר ו‪ f -‬ל‪ ,‬אז אלו הם כל האיברים‪ ,‬ולכן ‪. n = k‬‬

‫הגדרה‬ ‫נאמר ששתי קבוצות ‪ A‬ו‪ B-‬הן בעלות עוצמה שווה‪ ,‬בעלות אותה קרדינליות‪ ,‬אם קיימת ביניהם התאמה‬ ‫חח"ע‪ ,‬כלומר אם קיימת פונקציה ‪ f : A → B‬שהיא פונקציה של ‪ A‬על ‪ B‬וחח"ע‪.‬‬ ‫נאמר ש‪ A-‬ו‪ B-‬שקולות ונסמן ‪,A~B‬‬

‫‪  59‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמאות‬ ‫‪.1‬‬

‫תהי הקבוצה }‬ ‫ניקח ‪→ B‬‬

‫{‬

‫∈ ‪ . B = n 2 n‬נטען כי‬

‫~ ‪.B‬‬

‫‪ f :‬כך ש‪ . f (n) = n 2 -‬זוהי התאמה חח"ע ומכאן ‪= B‬‬

‫‪.‬‬

‫‪.2‬‬ ‫נגדיר את הקבוצה }‪ . ( a, b ) = { x | x ∈ , a < x < b‬נטען‪~ ( 0,1) :‬‬

‫כדי להוכיח זאת נשתמש בעובדה כי‬

‫‪.‬‬

‫‪ π π‬‬ ‫→ ‪ tan :  − , ‬הינה חח"ע ועל‪.‬‬ ‫‪ 2 2‬‬

‫השלבים‪:‬‬

‫‪( 0,1) → ( −1.1) ,‬‬

‫)‪1‬‬

‫= ‪f2‬‬

‫‪,‬‬

‫‪( −1,1) →  −‬‬

‫)‪2‬‬

‫= ‪f3‬‬

‫‪ π π‬‬ ‫‪− ,  → ,‬‬ ‫‪ 2 2‬‬

‫)‪3‬‬

‫‪f1 = 2 x − 1‬‬

‫‪ ‬‬

‫‪π‬‬

‫‪x‬‬

‫‪2‬‬

‫)‪( 2 x − 1‬‬

‫‪π‬‬ ‫‪2‬‬

‫‪π π‬‬

‫‪,‬‬ ‫‪ 2 2‬‬

‫כל הפונקציות הן חח"ע ועל‪.‬‬ ‫על ידי הרכבת פונקציות נקבל‪:‬‬ ‫‪π‬‬ ‫‪‬‬ ‫‪f ( 0,1) → , f ( x) = tan  ( 2 x − 1)   ‬‬ ‫‪2‬‬ ‫‪‬‬

‫טענה‬

‫היחס ‪ R‬המוגדר כך‪} :‬‬

‫‪A= B‬‬

‫‪{ A, B‬‬

‫= ‪ R‬הוא יחס שקילות‪.‬‬

‫הוכחה‪:‬‬ ‫רפלקסיביות‪ :‬צ"ל להוכיח לכל ‪ A‬כי מתקיים ‪ , A, A ∈ R‬כלומר ‪ . A = A‬ניתן להשתמש בפונקצית‬ ‫הזהות‪.‬‬

‫‪  60‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫סימטריות‪ :‬אם ‪ f : A → R‬התאמה חח"ע אזי גם ‪ f −1 : B → A‬התאמה חח"ע‪ ,‬לכן אם ‪A, B ∈ R‬‬

‫אזי גם ‪. B, A ∈ R‬‬ ‫טרנזיטיביות‪ :‬אם ‪ A, B ∈ R‬ו‪ B, C ∈ R -‬אזי גם ‪ , A, C ∈ R‬וזאת מכיוון שהרכבה של שתי‬ ‫פונקציות חח"ע ועל הינה גם חח"ע ועל‪.‬‬ ‫מחלקות השקילות של היחס נקראות המספרים הקרדינלים )עוצמות(‪.‬‬ ‫המספר הקרדינאלי‬

‫∈ ‪ n‬הוא כל הקבוצות שעוצמתן שווה לעוצמה של }‪. {1,..., n‬‬

‫• ‪ ‬כל קבוצה שהמספר הקרדינלי שלה הוא מספר סופי‪ ,‬הינה קבוצה סופית‪.‬‬

‫‪  .6.2‬הגדרה ‪ 1‬לקבוצה אינסופית‬ ‫קבוצה ‪ A‬תיקרא סופית אם קיים‬

‫∈ ‪ n‬כך שקיימת התאמה חח"ע בין ‪ A‬לבין }‪. {1,..., n‬‬

‫הקבוצה ‪ A‬תיקרא אין סופית אם לא קיים עבורה ‪ n‬כזה‪.‬‬ ‫טענה‬ ‫הקבוצה‬

‫‪ ,‬קבוצת הטבעיים‪ ,‬היא אינסופית לפי הגדרה ‪.1‬‬

‫צ"ל להראות שלא קיים‬

‫∈ ‪ n‬כך שקיימת התאמה חח"ע בין‬

‫סופית ושקיים ‪ n‬כזה כך ש‪-‬‬

‫ל‪ . {1,..., n} -‬נניח בשלילה ש‪-‬‬

‫→ }‪ f : {1,.., n‬חח"ע ועל‪ .‬נתבונן ב‪ f (1) ,..., f ( n ) -‬ויהא ‪ y‬הערך‬

‫המקסימלי מביניהם‪ .‬עבור ‪ y + 1‬לא קיים }‪ x ∈ {1,..., n‬כך ש‪ . f ( x ) = y + 1 -‬כמו כן מתקיים כי‬ ‫∈‪ y + 1‬ולכן ‪ f‬איננה על‪ ,‬בסתירה להנחה‪.‬‬

‫הגדרה הנגזרת מהגדרה ‪1‬‬ ‫‪ A‬היא קבוצה אינסופית אם קיימת ‪→ A‬‬

‫‪  61‬‬

‫‪ f :‬חח"ע‪.‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .6.3‬הגדרה ‪ 2‬לקבוצה אינסופית – הגדרה לפי תכונה‬ ‫קבוצה ‪ A‬היא אינסופית אמ"מ קיימת ‪ f : A → A‬חח"ע כך ש‪, f ( A) ⊂ A -‬‬ ‫כלומר קיימת פונקציה מ‪ A-‬לעצמה שהיא חח"ע אבל לא על‪.‬‬ ‫הוכחה שקבוצת הטבעיים‬ ‫→‬

‫תהי‬

‫היא אינסופית לפי הגדרה ‪:2‬‬

‫‪ f :‬שתוגדר להיות ‪ . f (n) = n + 1‬פונקציה זו היא חח"ע‪ ,‬אולם }‪\ {0‬‬

‫=) (‬

‫‪.f‬‬

‫מסקנה‬ ‫עבור ‪ 2‬קבוצות אינסופיות ‪ A‬ו‪ , B -‬אם ‪ A = B‬אזי קיימת פונקציה ‪ f‬חח"ע מ‪ A -‬ל‪ B -‬שאיננה על‪.‬‬

‫טענה )בלא הוכחה(‬ ‫כל ההגדרות לקבוצה אין סופית שקולות‪.‬‬ ‫‪ ‬‬

‫משפט‬ ‫אם ‪ A‬היא קבוצה אינסופית‪ ,‬אזי מתקיימות הטענות הבאות‪:‬‬ ‫‪  .1‬כל קבוצה ‪ B‬המקיימת ‪ A ⊆ B‬היא קבוצה אינסופית‪  .‬‬ ‫‪  .2‬כל קבוצה ‪ B‬שעבורה קיימת פונקציה חח"ע ‪ f : A → B‬היא אינסופית‪  .‬‬ ‫‪  .3‬כל קבוצה ‪ B‬שעבורה קיימת פונקציה על ‪ f : B → A‬היא אינסופית‪  .‬‬ ‫‪  .4‬הקבוצה ) ‪ P ( A‬היא אינסופית‪  .‬‬ ‫‪  .5‬לכל קבוצה לא ריקה ‪ , B‬הקבוצה ‪ A × B‬היא אינסופית‪  .‬‬ ‫‪  .6‬עבור כל קבוצה ‪ , B‬הקבוצה ‪ A ∪ B‬היא אינסופית‪  .‬‬ ‫‪  .7‬לכל קבוצה לא ריקה ‪ ,B‬הקבוצה ‪) A B‬קבוצת הפונקציות מ‪ B-‬ל‪ (A-‬היא אינסופית‪  .‬‬

‫‪  62‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחות‬ ‫‪.1‬‬ ‫נתון ש‪ A -‬היא אינסופית ומכאן שקיימת ‪ f : A → A‬חח"ע ולא על‪ .‬נשתמש ב‪ f -‬כדי להגדיר פונקציה‬ ‫מ‪ B -‬אל ‪ B‬שהיא חח"ע ולא על‪.‬‬ ‫‪.6‬‬ ‫מכיוון ש‪ A ⊆ A ∪ B -‬על פי טענה ‪ 1‬מתקיים כי ‪ A ∪ B‬היא אינסופית‪.‬‬ ‫‪.4‬‬ ‫נוכיח שקיימת פונקציה חח"ע ) ‪ f : A → P ( A‬ואז על פי טענה ‪ 2‬יתקיים ש‪ P ( A ) -‬היא אינסופית‪.‬‬ ‫צריך להתאים כל איבר ב‪ A-‬לתת קבוצה שונה של ‪ . A‬נבחר‪ - ∀a ∈ A, f ( a ) = {a} :‬פונקציה חח"ע‬ ‫מ‪ A -‬ל ‪. P ( A ) -‬‬

‫‪.5‬‬ ‫נוכיח שקיימת פונקציה חח"ע ‪ f : A → A × B‬ועל פי ‪ 2‬נסיק ש‪ A × B -‬הינה אינסופית‪ .‬נבחר איבר‬ ‫כלשהו ‪ b‬השייך ל‪) B -‬קיים כזה(‪. ∀a ∈ A, f (a ) = f (a, b) ,‬‬

‫‪.7‬‬ ‫נוכיח שקיימת פונקציה חח"ע מ‪ A -‬ל‪) AB -‬לקבוצת הפונקציות מ‪ B -‬אל ‪.( A‬‬ ‫לפי ‪ 2‬נקבל ש‪ AB -‬הינה אינסופית‪ .‬צריך להתאים לכל איבר ב‪ A -‬פונקציה שונה מ‪ B -‬ל‪. A -‬‬ ‫נבחר ‪ ∀a ∈ A, f (a ) = g a‬כאשר ‪ g a‬מוגדרת כך‪g a : B → A :‬‬

‫משפט‬ ‫תהי ‪ Σ‬שפה‪ .‬אם ‪ Σ ≠ φ‬אזי *‪ Σ‬הינה קבוצה אינסופית‪.‬‬ ‫*‪ Σ‬מוגדרת להיות קבוצת כל המילים הסופיות הנבנות מאותיות ‪. Σ‬‬ ‫כדי להוכיח משפט זה‪ ,‬מספיק שנראה כי קיימת *‪→ Σ‬‬

‫‪  63‬‬

‫‪ f :‬חח"ע‪.‬‬

‫‪. ∀b ∈ B, g a (b) = a,‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ ‬‬

‫‪  .6.4‬קבוצה בת מניה‬ ‫סימון‬ ‫נסמן את העוצמה של קבוצת הטבעיים ‪= ℵ0‬‬

‫‪.‬‬

‫הגדרה‬ ‫נאמר שקבוצה ‪ A‬היא בת מניה אם קיימת פונקציה חח"ע‬

‫→‪. f :A‬‬

‫הגדרה שקולה‪ :‬קבוצה ‪ A‬היא בת מניה אם היא סופית או שגודלה הוא ‪. ℵ0‬‬ ‫הערה חשובה‪ :‬במקומות רבים בספרות‪ ,‬כולל בגירסה הקודמת של מסמך זה‪ ,‬קבוצה בת מניה מוגדרת‬ ‫כקבוצה אינסופית בלבד שגודלה ‪ . ℵ0‬עניין זה הוא עניין של מוסכמה בלבד‪  .‬‬

‫קבוצה ‪ A‬אינסופית תיקרא בת מניה אם ‪. A = ℵ0‬‬

‫כיצד מוכיחים שקבוצה ‪ A‬אינסופית היא בת מניה?‬ ‫‪  .1‬מציגים התאמה חח"ע בין ‪ A‬לקבוצה שידוע שהיא בת מניה‪  .‬‬

‫‪  .2‬מציגים פונקציה חח"ע מ‪ A -‬לקבוצה כלשהי בת מניה ופונקציה חח"ע מקבוצה בת מניה כלשהי‬ ‫ל‪ A‬ומשתמשים במשפט ‪) CSB‬יוצג בהמשך(‪  .‬‬

‫‪  .3‬מציגים מניה של אברי ‪ A‬שמקיימת‪:‬‬ ‫א‪ .‬לפני כל איבר נמצא מספר סופי של איברים‪.‬‬ ‫ב‪ .‬כל איבר נמצא במקום כלשהו במניה )כל איבר נספר(‪  .‬‬

‫‪  64‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫נטען‪:‬‬

‫הינה בת מניה‪.‬‬

‫ננסה למצוא מניה‪ .‬נסיון ראשון‪.0,1,2,...,-1,-2,-3,... :‬‬ ‫סדר זה איננו ספירה טובה‪ ,‬כי לפני המספר ‪ −1‬עומדים אינסוף איברים‪ .‬נסיון שני‪:‬‬ ‫‪ ‬‬

‫‪0 1 −1 2 −2 3 −3‬‬ ‫‪6‬‬

‫‪5‬‬

‫‪4‬‬

‫‪2‬‬

‫‪3‬‬

‫‪0 1‬‬

‫נשים לב שזוהי למעשה התאמה חד חד ערכית‪ .‬בשלב ה‪ k -‬של המניה סופרים את ‪ k‬ואת ‪. − k‬‬ ‫כל איבר ‪ x‬נספר בשלב ה‪ x -‬וכל שלב אורכו לכל היותר ‪ ,2‬לכן כל מספר‬

‫∈ ‪ x‬מופיע בסידרה‬

‫כשלפניו מספר סופי של איברים‪.‬‬ ‫גם אם קיימת עבור קבוצה מניה עם חזרות איננו נמצאים בבעיה כי קיימת עבורה גם מניה בלי‬ ‫חזרות‪ .‬מעבר ממניה עם חזרות למיניה בלי חזרות בצורה פשוטה‪ :‬מתקדמים לפי הסדר שקבענו‪.‬‬ ‫אם האיבר הנוכחי כבר נספר‪ ,‬לא נספור אותו שוב‪ .‬אחרת נספור אותו‪  .‬‬

‫משפט‬ ‫∞‬

‫תהינה ‪ A1 ,..., Ak‬קבוצות בנות מניה‪ ,‬אזי‬

‫‪∪A‬‬

‫‪i‬‬

‫הינו בן מניה‪ .‬איחוד של מספר סופי של קבוצות בנות‬

‫‪i =1‬‬

‫מניה הוא בן מניה‪.‬‬ ‫הוכחה‪ :‬אם כל הקבוצות סופיות‪ ,‬ראינו שאיחוד סופי של קבוצות סופיות הוא סופי‪.‬‬ ‫נתעניין לכן במקרה בו לפחות אחת הקבוצות הינה אינסופית‪ ,‬ומכאן שהאיחוד כולו הוא אינסופי‪.‬‬ ‫נבנה טבלה בה בעמודה יהיו הקבוצות השונות ובתוך הטבלה יהיו האיברים השונים של הקבוצות‪:‬‬ ‫}‪A1 = {a10 ,...‬‬ ‫‪ ‬‬

‫}‪A2 = {a20 ,...‬‬ ‫‪...‬‬ ‫}‪Ak = {ak 0 ,...‬‬ ‫‪ ‬‬

‫‪  65‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫בשלב ה‪ j -‬נספור את כל האיברים מהצורה ‪aij‬‬

‫‪ . i = 1,..., k‬כל שלב הוא לכל היותר באורך ‪. k‬‬ ‫∞‬

‫כל איבר יופיע בסדרה ולפניו מספר סופי של איברים ולכן‬

‫‪∪A‬‬

‫‪i‬‬

‫הינו בן מניה‪.‬‬

‫‪i =1‬‬

‫משפט )בלא הוכחה(‬ ‫איחוד של מספר בן מניה של קבוצות בנות מניה הוא בן מניה‪.‬‬ ‫טענה‬ ‫אם ‪ A‬ו‪ B-‬בנות מניה‪ ,‬אזי ‪ A × B‬בת מניה‪.‬‬ ‫טענה‬

‫‪+‬‬

‫‪a‬‬ ‫ הרציונליים החיוביים ‪ -‬בת מניה‪.‬‬‫‪b‬‬

‫‪a, b ∈ ,‬‬

‫אם נצליח לספור את החיוביים‪ ,‬נוכל לספור גם את השליליים‪ .‬ניצור טבלה‪:‬‬ ‫‪  ...‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫‪ ‬‬ ‫‪ ‬‬

‫‪ 5‬‬ ‫‪  1/5‬‬ ‫‪  2/5‬‬ ‫‪  3/5‬‬ ‫‪  4/5‬‬ ‫‪  5/5‬‬ ‫‪ ‬‬

‫‪ 4‬‬ ‫‪  1/4‬‬ ‫‪  2/4‬‬ ‫‪  3/4‬‬ ‫‪  4/4‬‬ ‫‪  5/4‬‬ ‫‪ ‬‬

‫‪ 3‬‬ ‫‪  1/3‬‬ ‫‪  2/3‬‬ ‫‪  3/3‬‬ ‫‪  4/3‬‬ ‫‪  5/3‬‬ ‫‪ ‬‬

‫‪ 2‬‬ ‫‪  1/2‬‬ ‫‪  2/2‬‬ ‫‪  3/2‬‬ ‫‪  4/2‬‬ ‫‪  5/2‬‬ ‫‪ ‬‬

‫‪ 1‬‬ ‫‪  1/1‬‬ ‫‪  2/1‬‬ ‫‪  3/1‬‬ ‫‪  4/1‬‬ ‫‪  5/1‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ 1‬‬ ‫‪ 2‬‬ ‫‪ 3‬‬ ‫‪ 4‬‬ ‫‪ 5‬‬ ‫‪  ...‬‬

‫ישנם מספרים שמופיעים כמה פעמים ‪ -‬למשל ‪ -‬כל האלכסון הראשי‪.‬‬ ‫‪a‬‬ ‫בשלב ה‪ , k > 1 , k -‬נספור את כל המספרים מהצורה‬ ‫‪b‬‬ ‫‪a‬‬ ‫כאלו(‪ .‬כל מספר מהצורה‬ ‫‪b‬‬

‫‪  66‬‬

‫כך ש‪) . a + b = k -‬ישנם ‪ k + 1‬מספרים‬

‫יספר בשלב ה‪ a + b -‬קיים שלב כזה! זוהי ספירה עם חזרות‪.‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫תהי ‪ Σ‬שפה סופית )קבוצה סופית של אותיות(‪ .‬קבוצת המילים הסופיות מעל ‪ Σ‬היא בת מניה‪.‬‬ ‫סקיצה להוכחה‪:‬‬ ‫מספר המילים באורך ‪ k‬כלשהו הקיימות הינו ‪. Σ k‬‬ ‫נגדיר מניה בה בשלב ה‪ k -‬נספור את כל המילים באורך ‪ . k‬כל שלב בספירה הוא סופי ולכן הטענה‬ ‫נכונה‪.‬‬

‫דוגמא‬ ‫תהי ‪ Σ‬קבוצה בת מניה של אותיות‪ .‬נטען‪ :‬קבוצת המילים הסופיות מעל ‪ Σ‬היא בת מניה‪.‬‬ ‫פתרון‪:‬‬ ‫עבור כל תא במילה יש אין סוף אפשרויות לאותיות לכן אי אפשר להשתמש בדרך פתרון הקודמת‪.‬‬ ‫ בשלב ה‪ , k ≥ 1 , k -‬נספור את כל המילים באורך קטן שווה ‪ k‬שהאותיות בהן הן מהקבוצה‬‫}‪. {a0 , a1 ,..., ak −1‬‬ ‫‪k‬‬

‫כמה מילים כאלו יש? ‪. ∑ k i‬‬ ‫‪i =1‬‬

‫נוכיח שכל מילה נספרת בספירה זו‪.‬‬ ‫תהיי מילה ‪ . k1k 2 ...k r‬נסתכל על האות שבה האינדקס הוא מקסימלי‪ .‬יהי ‪ s‬האינדקס‪ .‬המילה תיספר‬ ‫בשלב שהוא המקסימום בין ‪ r‬ל‪. s + 1 -‬‬

‫‪  67‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫אם ‪ B‬בת מניה ו‪ A-‬קבוצה סופית‪ ,‬אזי ‪ B A‬היא בת בניה‪.‬‬ ‫נגדיר מניה‪:‬‬ ‫בשלב ה‪ k-‬נספור את כל הפונקציות מ‪ A-‬לקבוצה } ‪ . {b1 ,..., bk‬יש‬

‫‪A‬‬

‫‪ k‬פונקציות כאלו‪.‬‬

‫בהינתן פונקציה ‪ , f : A → B‬יהיו ) ‪ f (a1 ),..., f (an‬ערכי הפונקציה‪  .‬‬ ‫יהיו ‪b1 j = f (a j ),1 ≤ j ≤ n‬‬

‫נביט על הערך המקסימלי מבין ‪ . bi1 , bi 2 ,..., bin‬יהי ‪ r‬המקסימלי שבהם‪ .‬לכן ‪ f‬נספרת בשלב ה‪. r -‬‬

‫טענה‬ ‫לכל קבוצה אין סופית ‪ A‬יש תת קבוצה בת מניה‪.‬‬ ‫נבנה קבוצה ‪. B = {bi | i ∈ N } :B‬‬ ‫יהי ‪ b0 ∈ A‬ותהי } ‪ . B0 = {b0‬יהי ‪ b1 ∈ A / B0‬ותהי }‪. B1 = {b0 , b1‬‬ ‫נניח } ‪ Bi = {b0 , b1 ,..., bi‬כאשר ‪ . Bi ⊂ A‬יהי ‪ bi +1 ∈ A / Bi‬ותהי }‪. Bi +1 = Bi ∪ {bi +11‬‬ ‫כל אחת מהקבוצות ‪ Bi‬היא סופית‪ .‬איחוד כל איברי קבוצות ‪ Bi‬הוא אינסופי‪ .‬המניה היא הסדר בו‬ ‫בחרנו איברים מ‪ .A-‬הקבוצה הזו היא עם עוצמה שווה לזו של הטבעיים‪.‬‬

‫משפט‬ ‫לכל קבוצה אינסופית ‪ A‬יש תת קבוצות אמיתיות )תת קבוצה ממש( בעלות עוצמה שווה ל‪.A-‬‬

‫כיוון‬ ‫הצורה היחידה שניתן להוכיח זאת היא לקחת תת קבוצה מ‪ A-‬ולהוכיח שקיימת בינה לבין ‪ A‬פונקציה‬ ‫חח"ע ועל‪ .‬אם ניקח את ‪ A‬ונוציא ממנה רק איבר אחד‪ ,‬נקבל קבוצה בעלת אותה עוצמה‪.‬‬ ‫‪  68‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחה‬ ‫תהיי ‪ B ⊆ A‬בת מניה } ∈ ‪ , B = {bi | i‬ותהי }‪. B′ = {bi | i ∈ , i ≥ 1‬‬ ‫נבנה העתקה בין שתי הקבוצות שהיא התאמה חח"ע‪  .‬‬

‫נבנה ‪ g‬חד חד ערכית ועל‪.‬‬ ‫‪g : A → A /{b0 }  ‬‬

‫} ‪ A /{b0‬היא תת קבוצה אמיתית של ‪ .A‬אם נצליח למצוא ‪ g‬כמבוקש נראה כי ל‪ A-‬ול } ‪ A /{b0‬יש‬ ‫אותה עוצמה‪.‬‬ ‫נגדיר את ‪:g‬‬ ‫‪x∈ A/ B‬‬ ‫‪ ‬‬ ‫) ‪x ∈ B (⇒ x ∈ bi‬‬

‫‪ x‬‬ ‫‪g ( x) = ‬‬ ‫‪bi +1‬‬ ‫‪ ‬‬

‫מסקנה חשובה‬ ‫אם ניקח קבוצה אינסופית ונוציא ממנה מספר סופי של איברים‪ ,‬נשמור על עוצמת הקבוצה‪.‬‬

‫מסקנה ללא הוכחה‬ ‫אם ניקח קבוצה מעוצמה גבוהה‪ ,‬ונוציא מספר איברים מעוצמה נמוכה יותר‪ ,‬העוצמה תישמר‪.‬‬

‫דוגמא‬ ‫תהי קבוצת הווקטורים האינסופיים מעל‬

‫כך שלכל‬

‫∈ ‪ n‬סכום האיברים במקומות‬

‫‪ n, n + 1,..., n + 6‬הינו ‪ .21‬מהי עוצמת הקבוצה?‬

‫נשים לב שהגדרת ‪ 6‬המקומות הראשונים בווקטור מגדירה את שאר האיברים שלו באופן יחיד‪ ,‬ולכן‬ ‫‪ 21 + ( 6 − 1) ‬‬ ‫‪.‬‬ ‫הקבוצה הינה קבוצה סופית‪ ,‬ומספר איבריה‪ ,‬העוצמה שלה הוא ‪‬‬ ‫‪ 6 −1 ‬‬

‫‪  69‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫נניח שאנו מבצעים את הניסוי הבא‪ :‬מטילים מטבע עד שמקבלים ‪ H‬בפעם הראשונה‪.‬‬ ‫נגדיר את הקבוצה ‪ } :O‬תוצאות הניסוי { = ‪O‬‬

‫נוכיח כי ‪ O‬היא קבוצה בת מניה‪.‬‬ ‫נגדיר ‪→ O‬‬

‫‪ f :‬בצורה באה‪:‬‬ ‫‪f ( n ) = T ,..., T , H  ‬‬

‫‪...‬‬

‫‪f (0) = H‬‬

‫‪f (1) = T , H‬‬

‫‪n  times‬‬

‫נשים לב‪:‬‬ ‫אם ‪ f‬היא על אזי ‪ O‬היא בת מניה )סופית או אינסופית(‪ .‬בנוסף‪ ,‬אם ‪ f‬חח"ע אזי ‪ O‬אינסופית‪.‬‬

‫ניתן לראות בנקל כי הפונקציה שהגדרנו היא חח"ע‪ ,‬אולם פונקציה זו איננה על‪ .‬לניסוי ‪, T , T , T ,...‬‬ ‫שהוא ניסוי חוקי‪ ,‬אין מקור‪ .‬כדי להפוך פונקציה זו לעל נגדיר אותה מחדש‪:‬‬ ‫‪f ( n + 1) = T ,..., T , H  ‬‬

‫‪...‬‬

‫‪f ( 2) = T , H‬‬

‫‪f (1) = H‬‬

‫‪f ( 0 ) = T , T ,...‬‬

‫‪n  times‬‬

‫השיטה בה השתמשו כדי להפוך את הפונקציה לעל היא שימושית ומכונה לעתים "תרגיל המלון‬ ‫האינסופי"‪ .‬מקור השם הוא בתרגיל המחשבתי הבא‪ :‬זוג מגיע לבית מלון בעל אינסוף חדרים‪ ,‬אולם‬ ‫אומרים להם שכל החדרים תפוסים‪ ,‬והשאלה – היכן למקם את בני הזוג? הפתרון‪ :‬כל דייר שכבר נמצא‬ ‫במלון יעבור לחדר הבא )דייר מחדר ‪ 1‬יעבור לחדר ‪ 2‬וכו'(‪ ,‬ואז חדר מספר ‪ 1‬יהיה פנוי עבור הזוג‪.‬‬ ‫הרעיון באופן כללי‪ :‬כיצד נוכיח שאיחוד של קבוצה סופית וקבוצה בת מניה הינו בן מניה?‬ ‫הפתרון‪ :‬נשים את הקבוצה הסופית בהתחלת הספירה‪ ,‬ואת הקבוצה האינסופית אחריה‪.‬‬

‫‪  70‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .6.5‬משפט קנטור‬

‫‪ .6.5.1‬הגדרות‬ ‫הגדרה‬ ‫‪1:1‬‬ ‫‪. f : A ‬‬ ‫נאמר ש‪ A ≺ B -‬אם קיימת ‪→ B‬‬

‫במילים אחרות‪ ,‬נאמר כי ‪ A ≺ B‬אם העוצמה של ‪ A‬קטנה או שווה לעוצמה של ‪. B‬‬

‫הגדרה‬ ‫נאמר ש‪ A ≺ B -‬אם ‪ A ≺ B‬אבל ‪. A ∼/ B‬‬

‫דוגמאות‬ ‫‪.1‬‬ ‫יהיו הקבוצות } ‪ A = {a1 , a2 ,..., an } , B = {b1 , b2 ,..., bm‬כך שמתקיים ‪ n < m‬אזי ‪. A ≺ B‬‬

‫‪.2‬‬ ‫תהי ‪ A‬קבוצה סופית‪ .‬מתקיים‪:‬‬ ‫ראינו שלא קיימת פונקציה‬

‫≺‪. A‬‬ ‫→ ‪ f : A‬חח"ע ועל‪.‬‬

‫‪.3‬‬ ‫לכל קבוצה ‪ A‬מתקיים כי )‪. A ≺ P ( A‬‬ ‫‪1:1‬‬ ‫‪ f : A ‬והיא }‪. f ( x ) = { x‬‬ ‫קיימת הפונקציה )‪→ P ( A‬‬

‫‪  71‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .6.5.2‬קבוצות שאינן בנות מניה – שיטת הליכסון של קנטור‬ ‫תהי ‪ f‬פונקציה ) ‪ . f : A → P ( A‬נראה כי קיימת קבוצה ) ‪ B f ∈ P ( A‬שאינה מתקבלת כתמונה של‬ ‫אחד מאיברי ‪ , A‬כלומר )‪ , B f ∉ f ( A‬ומכאן שכל פונקציה )‪ f : A → P ( A‬איננה על‪.‬‬

‫ניתן להציג את ‪ f‬בצורת הטבלה הבאה‪:‬‬ ‫‪ ‬‬ ‫‪  ...‬‬

‫‪  ...‬‬

‫) ‪  f ( a4‬‬

‫) ‪  f ( a3‬‬

‫) ‪f ( a2‬‬

‫) ‪  f ( a1‬‬

‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪  a1‬‬ ‫‪  a2‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪  a3‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪ ‬‬ ‫‪ ‬‬

‫‪  a4‬‬ ‫‪  ...‬‬ ‫‪  ...‬‬ ‫‪ ‬‬ ‫‪ ‬‬

‫)מניחים כי הקבוצה ‪ A‬בת מניה כי אחרת לא ניתן לרשום אותה בטבלה כנ"ל(‪.‬‬

‫במקום ה‪ ( a , f ( a )) -‬נרשום ‪ 1‬אם ) ‪ a ∈ f ( a‬או ‪ 0‬אחרת‪ .‬באופן כללי‪ :‬במקום ה‪( a , f ( a )) -‬‬ ‫‪1‬‬

‫‪1‬‬

‫‪1‬‬

‫‪k‬‬

‫‪1‬‬

‫‪j‬‬

‫נרשום ‪ 1‬אם ) ‪ a j ∈ f ( ak‬ו‪ 0-‬אחרת‪.‬‬

‫דוגמא‬ ‫תהי ‪ A‬הקבוצה } ‪ A = {a1 , a2 , a3 , a4‬ותהי ‪ f‬שמוגדרת כך‪:‬‬

‫‪ ‬‬

‫‪  72‬‬

‫} ‪f ( a2 ) = {a1 , a3‬‬

‫‪f ( a1 ) = φ ,‬‬

‫‪f ( a4 ) = φ‬‬

‫} ‪f ( a3 ) = {a1 , a2 , a3‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫נכתוב את ‪ f‬בטבלה‪:‬‬ ‫) ‪  f ( a4‬‬

‫) ‪  f ( a3‬‬

‫‪f ( a2 )  ‬‬

‫) ‪  f ( a1‬‬

‫‪ ‬‬

‫‪ 0‬‬ ‫‪ 0‬‬

‫‪ 1‬‬ ‫‪ 1‬‬

‫‪ 1‬‬ ‫‪ 0‬‬

‫‪ 0‬‬ ‫‪ 0‬‬

‫‪  a1‬‬ ‫‪  a2‬‬

‫‪ 0‬‬

‫‪ 1‬‬

‫‪ 1‬‬

‫‪ 0‬‬

‫‪  a3‬‬

‫‪ 0‬‬

‫‪ 0‬‬

‫‪ 0‬‬

‫‪ 0‬‬

‫‪  a4‬‬ ‫‪ ‬‬

‫כל עמודה בטבלה מגדירה תת קבוצה של ‪. A‬‬ ‫מציאת ‪ B f ⊆ A‬שאיננה מתקבלת על ידי ‪ f‬שקולה למציאת עמודה שאיננה מופיעה בטבלה – נמצא‬ ‫עמודה שתהיה שונה מכל עמודה אחרת‪.‬‬ ‫העמודה השונה מכל העמודות טבלה היא העמודה המתקבלת על ידי היפוך העמודות באלכסון‪.‬‬ ‫כלומר‪ ,‬אם ) ‪ a1 ⊄ f ( a1‬נרשום ‪ 1‬אחרת נרשום ‪ 0‬וכך הלאה‪:‬‬ ‫) ‪  f ( a4‬‬

‫) ‪  f ( a3‬‬

‫‪f ( a2 )  ‬‬

‫) ‪  f ( a1‬‬

‫‪ ‬‬

‫‪ 0‬‬

‫‪ 1‬‬

‫‪ 1‬‬

‫‪ 0‬‬

‫‪ 1‬‬

‫‪  a2‬‬

‫‪ 0‬‬

‫‪  10‬‬ ‫‪ 0‬‬

‫‪  01‬‬ ‫‪ 1‬‬

‫‪01‬‬ ‫‪ 0‬‬

‫‪  a1‬‬

‫‪ 0‬‬

‫‪  a3‬‬

‫‪ 0‬‬

‫‪ 0‬‬

‫‪  a4‬‬

‫‪  01‬‬

‫‪ ‬‬

‫באופן כללי‪ ,‬העמודה השונה מכל עמודה אחרת בעמודה ה‪ i -‬היא שונה לפחות באיבר ה‪. i -‬‬ ‫טכניקה זו שימושית – בעזרתה מוכיחים שקבוצות אינן בנות מניה‪.‬‬

‫‪  73‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .6.5.3‬משפט קנטור‬ ‫לכל קבוצה ‪ A , A‬אינה שקולה ל‪ .P(A)-‬כלומר‪ :‬לכל קבוצה ‪ A‬מתקיים כי )‪. A ≺ P ( A‬‬

‫הוכחה‬ ‫ההוכחה צריכה לכלול שני מרכיבים‪ :‬ראשית עלינו לראות כי )‪ A ≺ P ( A‬ולאחר מכן אנו צריכים‬ ‫להוכיח כי הקבוצות אינן שקולות‪.‬‬ ‫ראינו קודם במסמך זה כי )‪ A ≺ P ( A‬ולכן נותר להוכיח רק את השקילות‪.‬‬ ‫לשם כך נראה שלכל פונקציה ) ‪ f : A → P ( A‬קיימת קבוצה ) ‪ B f ∈ P ( A‬שאינה מתקבלת כתמונה‬ ‫של אחד מאיברי ‪ , A‬כלומר )‪ , B f ∉ f ( A‬ומכאן שכל פונקציה )‪ f : A → P ( A‬איננה על‪.‬‬

‫נוכיח את הטענה עבור כל קבוצה בת מניה )סופית או אינסופית(‪.‬‬ ‫תהי ) ‪ f : A → P ( A‬פונקציה‪ .‬נגדיר את ‪ B f‬באופן הבא‪:‬‬ ‫לכל ‪ , a ∈ A‬מתקיים ‪. a ∉ f (a ) ⇔ a ∈ B f‬‬ ‫נראה כי ) ‪ , B f ∉ f ( A‬כלומר לא קיים ‪ x ∈ A‬כך ש‪. f ( x ) = B f -‬‬ ‫נבחין בין שני מקרים‪:‬‬ ‫‪B f ≠ f ( x ) ⇐ x ∉ B f ⇐ x ∈ f ( x ) .1‬‬ ‫‪B f ≠ f ( x ) ⇐ x ∈ B f ⇐ x ∉ f ( x ) .2‬‬

‫לכן לכל פונקציה ‪ f‬קיימת ‪ B f‬שאיננה מתקבלת על ידי ‪ f‬ומכאן ש‪ f -‬איננה על‪.‬‬

‫מסקנה ממשפט קנטור‬

‫הקבוצה‬

‫‪  74‬‬

‫)‬

‫( ‪ P‬איננה בת מניה‪.‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫מסקנה ‪2‬‬

‫אנו יכולים לקבל סידרה אינסופית עולה של עוצמות‪) ≺ P ( P ( ) ) ≺ ... :‬‬

‫(‪≺ P‬‬

‫‪.‬‬

‫מכאן נובע שיש מספר אינסופי של עוצמות‪.‬‬

‫‪  .6.6‬עוצמת הרצף‬

‫‪ .6.6.1‬השערת הרצף‬ ‫שאלה‬

‫האם קיימת קבוצה ‪ B‬המקיימת‬

‫)‬

‫(‪≺ B ≺ P‬‬

‫?‬

‫השערת הרצף אומרת שאין קבוצה ‪ B‬כזו‪ .‬ייתרה מכך‪ ,‬לכל קבוצה ‪ A‬לא קיימת ) ‪. A ≺ B ≺ P ( A‬‬ ‫להשערה זו אין הוכחה‪ .‬אומרים שלא ניתן להוכיח אותה בעזרת הכלים של תורת הקבוצות‪.‬‬

‫‪ .6.6.2‬עוצמת הרצף‬ ‫הבחנה‬ ‫‪ 2‬איננה קבוצת בת מניה‪ .‬הבחנה זו נכונה לפי משפט קנטור‪.‬‬ ‫‪ 2‬היא קבוצת החזקה של המספרים הטבעיים‪ .‬כמו כן‪ ,‬ניתן לזהות אותה עם קבוצת הווקטורים‬ ‫הבינאריים האינסופיים‪.‬‬ ‫הגדרה‬ ‫עוצמת קבוצת החזקה של הטבעיים‪ , 2 ,‬תכונה עוצמת רצף‪.‬‬

‫‪  75‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הגדרה חלופית‬ ‫העוצמה של קבוצת המילים הבינריות האינסופיות נקראת עוצמת רצף‪ .‬היא זהה לעוצמה של קבוצת‬ ‫המספרים הממשיים‪.‬‬

‫סימון‬ ‫סימון לעוצמת רצף‪A = ¬ :‬‬

‫מספרים ממשיים‬ ‫נסתכל על הקטע ]‪ .[0,1‬נטען כי קבוצת המספרים בקטע זה איננה בת מניה‪.‬‬ ‫כל מספר בקטע בין ‪ 0‬ל‪ 1-‬יכול להיות מיוצג בצורה הבאה‪ 0.x1 x2 x3 ... :‬כאשר ‪. 0 ≤ xi ≤ 9‬‬ ‫נניח שקיימת ]‪ . g : N → [0,1‬נכתוב אותה‪:‬‬ ‫‪g (0) = 0.x00 x01 x02 ...‬‬ ‫‪ ‬‬

‫‪g (1) = 0.x10 x11 x12 ...‬‬ ‫‪...‬‬ ‫‪g (i ) = 0.xi 0 xi1 xi 2 ...‬‬

‫נבנה את המספר ‪:y‬‬ ‫‪ ‬‬

‫‪y = 0. y0 y1 y2 ...‬‬ ‫‪yi ≠ xii‬‬

‫המספר הזה לא יתקבל על ידי ‪ . g‬מ‪.‬ש‪.‬ל‪.‬‬

‫ההוכחה במקרה זה לא מושלמת‪ ,‬יש בה בעיה‪ .‬הבעיה נובעת מהאופי של המספרים הממשיים‪.‬‬ ‫יש מספרים שיש להם יותר מייצוג אחד‪ .‬המספר ‪ . 0.3999 = 0.4000‬למשל‪.0.9999...=1 ,‬‬ ‫זוהי בעייה שלא הייתה לנו במילים הבינריות האינסופיות‪.‬‬ ‫לכן נוסיף דרישה נוספת למספר ‪.y‬‬ ‫‪yi ≠ xii , yi ≠ {0,9}  ‬‬

‫הדרישה נובעת רק מהאופי של המספרים הממשיים‪.‬‬ ‫‪  76‬‬

‫‪y = y0 y1 y2 ...,‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫נטען‪[a, b] = (a, b) = (a, b] :‬‬

‫נפצל את ההוכחה למספר חלקים‪.‬‬ ‫טענה‪ :‬עוצמת הקטע ]‪ [0,a‬היא עוצמת הרצף‪.‬‬ ‫‪ ‬‬

‫] ‪f : [0,1] → [0, a‬‬ ‫‪f ( x) = ax‬‬

‫טענה‪ :‬עוצמת הקטע ] ‪ [ x, x + a‬היא רצף‪.‬‬ ‫‪ ‬‬

‫]‪f : [0, a ] → [ x, x + a‬‬ ‫‪f ( y) = x + y‬‬

‫מסקנה שכבר הוכחנו ברגע זה‪ :‬עוצמת כל קטע כלשהו על המספרים הממשיים היא עוצמת רצף‪.‬‬ ‫עכשיו נרצה לעבור לקטע אינסופי‪.‬‬ ‫)∞ ‪f : (0,1) → (1,‬‬ ‫‪ ‬‬

‫‪1‬‬ ‫‪x‬‬

‫= )‪f ( x‬‬

‫מכאן העוצמה של הקטע )‪ (0,1‬זהה לעוצמה של הקטע )∞ ‪. (1,‬‬ ‫ברור וטריויאלי כי )∞ ‪ . (0,2) = (0,‬ומכאן )∞ ‪ (−2,2) = (−∞,‬שזה זהה לפי הטענה ההתחלתית‬ ‫ל‪. (0,1) = (−∞, ∞) -‬‬

‫תרגיל‬ ‫תהא ‪ B‬הקבוצה הבאה‪ b } :‬ווקטור בינארי אינסופי | ‪ . B = { b‬הוכח‪. B ~ B × B :‬‬ ‫צ"ל קיומה של פונקציה חח"ע ועל ‪. f : B → B × B‬‬ ‫נבחר את הפונקציה הבאה‪ , f ( b ) = ( b′, b′′ ) :‬כאשר‪b ∈ {0,1} :‬‬ ‫*‬

‫‪ b = b0b1b2 ...,‬ונגדיר‪:‬‬ ‫‪b′′ = b1b3b5 ...  ‬‬

‫‪  77‬‬

‫‪b′ = b0b2b4 ...,‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫נראה כי פונקציה זו הינה חח"ע‪ :‬יהיו ‪ b, x ∈ B‬כך ש‪ . x ≠ b -‬צ"ל‪. f ( b ) ≠ f ( x ) :‬‬ ‫מהנתון‪ :‬קיים ‪ i‬כך ש ‪ . bi ≠ xi‬אם ‪ i‬זוגי אזי ‪ bi′/ 2 ≠ xi′/ 2‬ואז ‪ b′ ≠ x′‬ולכן ) ‪. f ( b ) ≠ f ( x‬‬ ‫אם ‪ i‬אי זוגי אזי ‪ b(′′i −1) / 2 ≠ x(′′i −1) / 2‬ואז ‪ b′′ ≠ x′′‬ולכן ) ‪. f ( b ) ≠ f ( x‬‬ ‫נראה כי ‪ f‬הינה על‪ .‬יהי ‪ . ( c, d ) ∈ B × B‬צריך למצוא ‪ b ∈ B‬כך שיתקיים ) ‪. f ( b ) = ( c, d‬‬ ‫נבחר את ‪ b‬להיות הווקטור הבא‪ . b = c0 d 0 c1d1... :‬לפי הגדרת ‪ f‬מתקיים‪. f ( b ) = ( c, d ) :‬‬ ‫סימון‬ ‫נסמן ב‪ B A -‬את אוסף הפונקציות מ‪ A -‬אל ‪. B A = { f ⊆ A × B and f  is function} : B‬‬ ‫את }‪ {0,1‬נסמן לעתים ב‪ . 2 -‬ניתן להסתכל על }‪ {0,1‬כאוסף כל הווקטורים הבינאריים‬ ‫האינסופיים‪.‬‬

‫משפט‬ ‫לכל קבוצה ‪ B‬מתקיים כי ‪. P ( B ) ~ 2 B‬‬ ‫ניתן להסתכל על הטענה כהתאמת אוסף כל הפונקציות מ‪ B -‬אל }‪. {0,1‬‬ ‫נראה פונקציה חח"ע ועל מ‪ P ( B ) -‬ל‪ : 2 B -‬עבור כל ) ‪ ( A ⊆ B ) , A ∈ P ( B‬נגדיר ‪. f ( A ) = g A‬‬ ‫‪ g A‬היא פונקציה מ‪ B -‬אל }‪ {0,1‬המוגדרת כך‪:‬‬

‫‪x∈ A‬‬ ‫‪else‬‬

‫‪1‬‬ ‫‪. gA ( x) = ‬‬ ‫‪0‬‬

‫פונקציה זו נקראת הפונקציה האופיינית של ‪ . A‬היא מסומנת לעתים גם ‪. χ A‬‬ ‫ניתן לראות בקלות כי ‪ f‬הינה חח"ע ועל‪  .‬‬

‫‪  78‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .6.7‬משפט קנטור ברנשטיין‬

‫‪ .6.7.1‬מוטיבציה‬ ‫השתמשנו ביחס ≺ בדיון על עוצמות‪ .‬אנו רוצים להראות כי יחס זה הוא יחס שימושי‪ ,‬שיש סיבה למעשה‬ ‫שהגדרנו אותו‪.‬‬ ‫נרצה לראות כי יחס זה הוא יחס סדר‪ .‬ניתן להוכיח בקלות כי הוא רפלקסיבי וטרנזיטיבי‪.‬‬ ‫משפט קנטור ברנשטיין שנראה מיד יוכיח כי הוא גם אנטי‪-‬סימטרי‪.‬‬

‫‪ .6.7.2‬ניסוח ‪1‬‬ ‫לכל ‪ 2‬קבוצות ‪ A‬ו‪:B-‬‬ ‫אם קיימת פונקציה ‪ f : A → B‬שהיא ‪ 1:1‬וגם קיימת פונקציה ‪ g : B → A‬שהיא ‪ ,1:1‬אזי קיימת‬ ‫התאמה חח"ע בין ‪ A‬ל‪.B-‬‬

‫‪ .6.7.3‬ניסוח ‪2‬‬ ‫לכל שתי קבוצות ‪ , A, B‬אם מתקיים כי ‪ A ≺ B‬וגם ‪ B ≺ A‬אזי מתקיים כי ‪. A ~ B‬‬

‫‪  79‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .6.7.4‬טענה ‪1‬‬

‫‪m‬‬ ‫‪‬‬ ‫‪=  | m, n ∈ , n ≠ 0   ‬‬ ‫‪n‬‬ ‫‪‬‬

‫*‬

‫‪,‬‬

‫*‬

‫=‬

‫נוכיח על ידי משפט קנטור ברנשטיין‪:‬‬ ‫‪1:1‬‬ ‫‪n‬‬ ‫* → ‪,f:‬‬ ‫‪1‬‬ ‫‪m‬‬ ‫‪m‬‬ ‫‪∀ ∈ * , g   = 2n ⋅ 3m , G :‬‬ ‫‪n‬‬ ‫‪n‬‬

‫= ) ‪∀n ∈ , f ( n‬‬

‫‪ ‬‬

‫‪1:1‬‬

‫→‬

‫*‬

‫‪ .6.7.5‬טענה ‪2‬‬

‫נטען‪:‬‬

‫)‬

‫(‪= P‬‬

‫‪.‬‬

‫ההוכחה תעשה בשני שלבים‪:‬‬ ‫‪ .1‬נראה כי‬

‫( ‪. ( 0,1) ~ P‬‬

‫)‬

‫~ )‪. ( 0,1‬‬

‫‪ .2‬נראה כי‬

‫‪.1‬‬ ‫מספיק למצוא‬

‫)‬

‫( ‪f : ( 0,1) → P‬‬

‫יובטח לנו קיום פונקציה‬

‫)‬

‫חח"ע ו‪) → ( 0,1) -‬‬

‫( ‪ g : P‬חח"ע ולפי משפט קנטור‪-‬ברנשטיין‬

‫( ‪ h : ( 0,1) → P‬חח"ע ועל‪.‬‬

‫‪ : f‬בהינתן )‪ , r = 0.r1r2 r3 ... ∈ ( 0,1‬כאשר ‪ ∀i‬מתקיים }‪ ri ∈ {0,...,9‬ובמספר אין סדרת ‪9‬‬

‫אינסופית‪ ,‬נגדיר את ‪ f‬בצורה הבאה‪. f ( r ) = {r1 ,10 + r2 ,100 + r3 ,...} :‬‬ ‫נראה כי ‪ f‬חח"ע‪ :‬יהיו שני מספרים ‪ . r ≠ s‬קיים ‪ . ri ≠ si‬ויתקיים‪:‬‬ ‫) ‪.10i −1 + ri ∈ f ( r ) ,10i −1 + ri ∈ f ( s‬‬

‫‪  80‬‬

‫ניר אדר‬

‫‪ : g‬בהינתן‬

‫‪  [email protected]‬‬

‫⊆ ‪ B‬נגדיר את ‪ g‬בצורה הבאה‪ , g ( B ) = 0.b1b2b3 ... :‬כך ש‪:‬‬ ‫‪ ‬‬

‫‪ g‬חח"ע‪ :‬בהינתן‬

‫‪i∈B‬‬ ‫‪else‬‬

‫‪2‬‬ ‫‪bi = ‬‬ ‫‪0‬‬

‫⊆ ‪ B, C‬כך ש‪ b ≠ c -‬באחת מהן יש איבר שאין בשניה‪.‬‬

‫בלי הגבלת הכלליות נאמר כי ‪ i ∈ B‬וגם ‪ , i ∉ C‬ואז ‪ bi = 2, ci = 0‬ואז המספר הממשי המייצג אותם‬ ‫שונה‪.‬‬ ‫לכאורה ‪ . g (φ ) = 0.000 = 0‬האם )‪ ? 0 ∈ ( 0,1‬לא‪ ,‬ולכן נגדיר עבור‬

‫)‬

‫( ‪ φ ∈ P‬את ‪ g‬באופן‬

‫מפורש‪ ,‬לדוגמא ‪. g (φ ) = 0.3‬‬

‫‪.2‬‬ ‫צריך להראות ש‪-‬‬

‫~ )‪. ( 0,1‬‬

‫נגדיר פונקציה ‪ f‬בצורה הבאה‪:‬‬

‫‪ ‬‬

‫‪1 1  x ‬‬ ‫‪2 + 2  x +1 x ≥ 0‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪f ( x) = ‬‬ ‫‪1 − 1  x  x < 0‬‬ ‫‪ 2 2  x + 1 ‬‬ ‫‪ ‬‬

‫ניתן לראות כי פונקציה זו הינה חח"ע ועל‪.‬‬

‫‪  81‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .7‬קבוצות אינדוקטיביות‬

‫‪  .7.1‬סגירות תחת פונקציות ‪ ‬‬

‫‪ .7.1.1‬הגדרת סגירות תחת פונקציה‬ ‫• ‪ ‬נאמר ש‪ A0 ⊆ A -‬סגורה תחת הפונקציה ‪ f : A → A‬אם לכל ‪ a ∈ A0‬מתקיים ‪. f ( a ) ∈ A0‬‬ ‫• ‪ ‬נאמר ש‪ A0 ⊆ A -‬סגורה תחת הפונקציה ‪) f : Ak → A‬פונקציה ‪- k‬מקומית( אם לכל‬ ‫‪ a1 , a2 ,..., ak ∈ A0‬מתקיים ‪. f ( a1 , a2 ,..., ak ) ∈ A0‬‬

‫‪ .7.1.2‬דוגמא‬

‫תהי‬

‫→‬

‫‪2‬‬

‫‪ f :‬פונקצית החיבור‪.‬‬

‫קבוצת המספרים הזוגיים הינם סגורים תחת ‪ f‬וקבוצת המספרים האי זוגיים אינם סגורים תחת ‪. f‬‬

‫‪ .7.1.3‬הגדרת סגירות תחת קבוצת פונקציות‬ ‫תהא ‪ F‬קבוצת פונקציות‪ .‬נאמר ש‪ A0 ⊆ A -‬סגורה תחת ‪ F‬אם לכל ‪ f ∈ F‬מתקיים כי ‪ A0‬סגורה‬ ‫תחת ‪. f‬‬

‫‪  82‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .7.1.4‬טענה ‪1‬‬

‫תהי ‪ F‬קבוצת פונקציות מעל ‪ A‬ותהיינה ‪ A1 , A2‬תת קבוצות של ‪ A‬שסגורות תחת ‪. F‬‬ ‫אזי‪ A1 ∩ A2 :‬סגורה תחת ‪. F‬‬ ‫הוכחה‬ ‫כדי להראות ש‪ A1 ∩ A2 -‬סגורה תחת ‪ F‬נראה כי החיתוך סגור תחת כל ‪. f ∈ F‬‬ ‫נניח ש‪ f -‬היא פונקציה ‪ k‬מקומית‪.‬‬ ‫יהיו ‪ . a1 , a2 ,..., ak ∈ A1 ∩ A2‬צ"ל‪. f ( a1 , a2 ,..., ak ) ∈ A1 ∩ A2 :‬‬ ‫מתקיים‪ a1 , a2 ,..., ak ∈ A1 :‬וגם ‪ a1 , a2 ,..., ak ∈ A2‬לפי הגדרת החיתוך‪.‬‬ ‫מתקיים‪ f ( a1 , a2 ,..., ak ) ∈ A1 :‬וגם ‪ f ( a1 , a2 ,..., ak ) ∈ A2‬ולכן ‪. f ( a1 , a2 ,..., ak ) ∈ A1 ∩ A2‬‬

‫‪ .7.1.5‬טענה ‪2‬‬ ‫תהי ‪ F‬קבוצת פונקציות מעל ‪ A‬ותהי ‪ B‬קבוצה של תתי קבוצו של ‪ A‬הסגורות מעל ‪. F‬‬ ‫מתקיים‪ :‬הקבוצה ‪ ∩ B‬גם סגורה תחת ‪. F‬‬

‫‪  83‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .7.2‬עיצוב מילים‬

‫‪ .7.2.1‬בנאים של קבוצות‬ ‫בנאים של קבוצות הינו עקרון שלפיו בונים קבוצות מקבוצות נתונות‪ .‬לדוגמא‪:‬‬ ‫• ‪ ‬עבור כל קבוצה ‪ A‬נוכל ליצור את הקבוצה }‪. { A‬‬ ‫• ‪ ‬עבור כל קבוצה ‪ A‬נוכל ליצור את הקבוצה }‪. A ∪ { A‬‬ ‫• ‪ ‬עבור כל קבוצה ‪ A‬נוכל ליצור את הקבוצה ) ‪. P ( A‬‬ ‫• ‪ ‬עבור כל קבוצה ‪ A‬וקבוצה נוספת ‪ B‬נוכל ליצור את הקבוצה ‪A, B‬‬

‫יהי ‪ F‬עקרון בונה קבוצות‪ .‬האם קיימת }‪ { F ( A ) | A is a group‬קבוצה אוניברסלית עבור ‪? F‬‬ ‫התשובה‪ :‬לא‪ .‬ההוכחה דומה להוכחה של הוכחת אי קיום קבוצת כל הקבוצות‪.‬‬

‫‪ .7.2.2‬עקרון הסגירות‬ ‫עקרון זה מאפשר לנו לקחת קבוצת בסיס ולסגור תחתיה פעולות‪.‬‬ ‫תהי ‪ C‬קבוצה של בנאים‪.‬‬ ‫עקרון הסגירות אומר כי לכל קבוצה ‪ C‬סופית ולכל קבוצה ‪ A‬קיימת קבוצה ‪ B‬כך ש‪:‬‬ ‫‪. A ⊆ B .1‬‬ ‫‪ B .2‬סגורה תחת ‪ , F‬לכל ‪. F ∈ C‬‬

‫‪  84‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .7.2.3‬הגדרת אוסף מילים‬ ‫תהי ‪ Σ‬קבוצה של אותיות‪.‬‬ ‫נגדיר בנאים עבור כל ‪ α ∈ Σ‬בצורה הבאה‪. Sα ( A ) = A, α :‬‬ ‫לפי עקרון הסגירות קיימת קבוצה ‪ B‬עבורה ‪ φ ∈ B‬וגם ‪ B‬סגורה תחת ‪ Sα‬לכל ‪. α ∈ Σ‬‬ ‫נגדיר את אוסף כל המילים מעל ‪ Σ‬בצורה הבאה‪. Σ* = ∩ { X ⊆ B : X  is Σ-closed} :‬‬ ‫נסמן‪ sα :‬היא ההגבלה של ‪ Sα‬המוכלת על הקבוצה *‪. Σ‬‬

‫‪ .7.2.4‬מילים מעל }‪{a, b‬‬ ‫תהי }‪ . Σ = {a, b‬מתקיים‪:‬‬ ‫• ‪ ‬המילה }‪ φ ∈ {a, b‬מכונה המילה הריקה ומסומנת על ידי ‪. ε‬‬ ‫*‬

‫• ‪ sa ( ε )  ‬מסמל את המילה המכילה את האות ‪. a‬‬ ‫• ‪ sb ( ε )  ‬מסמל את המילה המכילה את האות ‪  . b‬‬

‫• ‪ ‬באופן דומה‪ S a ( Sb (φ ) ) ,‬מסמל את המילה המכילה את האות ‪ b‬שלאחריה האות ‪. a‬‬ ‫באופן כללי ) ‪ sa ( w ) , sb ( w‬מסמלים את המילים המכילות את המילה ‪ w‬ואחריה ‪ a‬או ‪ b‬בהתאמה‪.‬‬ ‫נסמן‪. sa ( w ) = wa, sb ( w ) = wb :‬‬

‫‪  85‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .7.2.5‬תכונות של *‪Σ‬‬

‫מהגדרת אוסף המילים נובעות מספר תכונות שנסכמן להלן‪:‬‬ ‫‪  . ε ∈ Σ*   .1‬‬ ‫‪  .2‬אם *‪ w∈ Σ‬אזי גם *‪ wα ∈ Σ‬עבור כל ‪  . α ∈ Σ‬‬

‫‪  .3‬עקרון האינדוקציה‪ :‬אם *‪ W ⊆ Σ‬וגם ‪ ε ∈ W‬וגם עבור כל ‪ w ∈ W‬ו‪ α ∈ Σ -‬מתקיים כי‬ ‫‪ wα ∈ W‬אזי *‪  . W = Σ‬‬ ‫‪ wα ≠ ε   .4‬לכל *‪ w∈ Σ‬ולכל ‪  . α ∈ Σ‬‬ ‫‪  .5‬לכל ‪ a ∈ Σ‬הפונקציה ‪ sa‬הינה פונקציה חח"ע‪  .‬‬

‫‪ .7.2.6‬בניית קבוצת הטבעיים‬ ‫נביט במילים מעל הא"ב }‪ . {1‬א"ב זה מכיל אות בודדת‪.‬‬ ‫קבוצת המילים }‪ {1‬תכונה קבוצת המילים האונריות‪.‬‬ ‫*‬

‫נזהה קבוצה זו עם קבוצת המספרים הטבעיים‪:‬‬

‫=‬

‫= }‪. {1‬‬ ‫*‬

‫‪word‬‬

‫קבוצת הטבעיים תראה כך‪. ε = 0,1 = 1,11 = 2,111 = 3,... :‬‬ ‫עבור‬

‫∈‪ w‬נסמן את המילה ‪ w1‬בתור ‪. w + 1‬‬

‫כמו כן‪ ,‬התכונות של קבוצת אותיות שהגדרנו בסעיף הקודם מכונות ‪ Peano Axioms‬בהקשר לקבוצת‬ ‫המילים האונריות‪.‬‬

‫‪  86‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪  .7.3‬קבוצות אינדוקטיביות‬

‫‪ .7.3.1‬הגדרת קבוצות מורכבות – הגדרה באינדוקציה‬ ‫ראינו דרכים להגדרת קבוצה‪:‬‬ ‫• ‪ ‬הרכבה של הקבוצה איבר אחד איבר – "רשימת מכולת"‪ .‬כתיבה זו מסורבלת יחסית ואפשרית‬ ‫רק עבור קבוצות סופיות‪  .‬‬ ‫• ‪ ‬הגדרת קבוצה על ידי תכונה מאפיינת – לא כל התכונות קלות או ניתנות לבדיקה‪  .‬‬

‫נראה כעת דרך נוספת להגדיר קבוצה – הגדרת קבוצה באינדוקציה‪.‬‬ ‫לשם הגדרת קבוצה באינדוקציה יש צורך בקבוצת גרעין )המסומנת ב‪ ( B -‬וקבוצת פעולות‪ ,‬פונקציות‬ ‫)המסומנת ב‪.( F -‬‬ ‫הקבוצה המוגדרת באינדוקציה על ידי קבוצת הגרעין ‪ B‬וקבוצת הפעולות ‪ F‬המסומנת ב‪ X B , F -‬היא‬ ‫הקבוצה העונה על שלוש הדרישות הבאות‪:‬‬ ‫‪) B ⊆ X B , F   .1‬איברי הגרעין נמצאים ב‪  .( X B , F  -‬‬

‫‪  .2‬סגירות תחת ‪ : F‬לכל פונקציה ‪- k‬מקומית ‪ f ∈ F‬לכל ‪ a1 ,..., ak ∈ X B , F‬גם‬ ‫‪  . f ( a1 ,..., ak ) ∈ X B , F‬‬ ‫‪  .3‬כל האיברים ב‪ X B , F -‬הכרחיים לקיום הדרישות ‪) 1, 2‬אין איברים מיותרים(‪  .‬‬

‫דוגמא‬ ‫‪B = {0} , F = { f } , f ( n ) = n + 1  ‬‬ ‫‪I 3 = {0, 2, 4,...}  ‬‬

‫קיום דרישה ‪:1‬‬ ‫קיום דרישה ‪:2‬‬ ‫קיום דרישה ‪:3‬‬

‫‪  87‬‬

‫הדרישה מתקיימת‬ ‫הדרישה לא מתקיימת‬ ‫הדרישה לא מתקיימת‬

‫‪ ‬‬

‫= ‪I2‬‬

‫הדרישה מתקיימת‬ ‫הדרישה מתקיימת‬ ‫הדרישה מתקיימת‬

‫‪ ‬‬

‫= ‪I1‬‬

‫הדרישה מתקיימת‬ ‫הדרישה מתקיימת‬ ‫הדרישה לא מתקיימת‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא – שפת ‪ABA‬‬

‫תהי שפה של מילים מעל האותיות ‪ a, b‬שתוגדר כך‪ B = {a, b} , F = { f1 , f 2 , f3 } :‬כך ש‪:‬‬ ‫‪ f1‬מוסיפה ‪ aba‬מימין למילה‪ f 2 .‬מחליפה את ה‪ aa -‬הימני ביותר ב‪ b -‬ו‪ f 3 -‬מוחקת את ה‪bbb -‬‬

‫הימני ביתר‪.‬‬ ‫המילים הבאות לדוגמא שייכות לשפה‪. ab, ababa, ababaaba, abaa :‬‬

‫‪ .7.3.2‬הוכחת שימושיות ההגדרה‬ ‫נראה כי ההגדרה טובה – כלומר שבהנתן קבוצת גרעין ‪ B‬וקבוצת פעולות ‪ F‬קיימת קבוצה העונה על‬ ‫הדרישות ‪ 1-3‬והיא יחידה‪.‬‬ ‫הוכחת קיום‬ ‫נגדיר‪ X } :‬עונה על דרישות ‪.A = { X | 1, 2‬‬ ‫הקבוצה ‪ A‬איננה ריקה‪ ,‬כי הקבוצה מעליה אנו עוברים )התחום‪ ,‬העולם( נמצאת בפנים‪.‬‬ ‫נגדיר‪ . X * = ∩ A :‬נראה כי * ‪ X‬עונה על דרישות ‪.1 − 3‬‬ ‫דרישה ‪ :1‬צ"ל כי * ‪. B ⊆ X‬‬ ‫לכל ‪ X ∈ A‬מתקיים כי ‪ X‬עונה על דרישה ‪ ,1‬ולכן ‪ B ⊆ X‬ולכן * ‪. B ⊆ ∩ A = X‬‬ ‫דרישה ‪ :2‬סגירות תחת ‪. F‬‬ ‫ראינו קודם שאם ‪ A‬מכילה קבוצות שסגורות תחת ‪ , F‬מתקיים שגם ‪ ∩ A‬סגורה תחת ‪. F‬‬ ‫דרישה ‪ :3‬צ"ל שכל האיברים הכרחיים לקיום דרישות ‪:1, 2‬‬ ‫נניח בשלילה שקיים * ‪ g ∈ X‬שאינו הכרחי לקיום דרישות ‪ .1, 2‬קיימת קבוצה ‪ x‬שעונה על דרישות‬ ‫‪ 1, 2‬כך ש‪ . g ∉ x -‬מתקיים ‪ x ∈ A‬כי ‪ x‬עונה על דרישות ‪ g ∉ ∩ A = X * ⇐ g ∉ x .1, 2‬בסתירה‬ ‫לכך שהנחנו כי * ‪ . g ∈ X‬מכאן שקיימת קבוצה שעונה על דרישות ‪.1-3‬‬

‫‪  88‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫הוכחת יחידות‬ ‫לפי ההגדרה כל קבוצה ‪ X‬המקיימת את דרישות ‪ 1, 2‬מכילה את * ‪. X‬‬ ‫נניח בשלילה שקיימת ‪ X ′‬שעונה על דרישות ‪ ,1 − 3‬כך ש‪. X ′ ≠ X * -‬‬ ‫‪ X ′‬עונה על דרישות ‪ 1, 2‬ולכן ‪ . X * ⊆ X ′‬מאחר ו‪ X ′ ≠ X * -‬הרי שב‪ X ′ -‬יש איברים נוספים‪.‬‬ ‫האיברים האלו אינם הכרחיים לקיום דרישות ‪ ,1, 2‬בסתירה לכך ש‪ X ′ -‬מקיימת את ‪ ,3‬כלומר * ‪X‬‬

‫מקיימת את הדרישות ‪ 1-3‬והיא יחידה‪.‬‬

‫מסקנה – משפט ההוכחה באינדוקציה‬

‫כל קבוצה ‪ X‬שמקיימת את דרישות ‪ 1, 2‬מקיימת ‪. X B , F ⊆ X‬‬ ‫לפיכך‪ ,‬על מנת להוכיח שקבוצה ‪ Y‬מקיימת כי ‪ X B , F ⊆ Y‬מספיק להראות כי‪:‬‬ ‫‪. B ⊆ Y .1‬‬ ‫‪ Y .2‬סגורה ל‪. F -‬‬

‫‪ .7.3.3‬סדרת יצירה‬ ‫הגדרה‬ ‫סדרת יצירה עבור איבר ‪ a‬מתוך ‪ X B , F‬היא סדרה סופית ‪ a1 ,..., an‬המקיימת‪:‬‬ ‫‪. an = a   .1‬‬ ‫‪  .2‬לכל ‪ 1 ≤ i ≤ n‬מתקיים‪ ai ∈ B :‬או ‪ ai‬התקבל מאיברים קודמים בסדרה על ידי אחת‬ ‫מהפעולות ב‪  . F -‬‬

‫טענה‬ ‫בהינתן ‪ , B, F‬לכל איבר ‪ a‬מתקיים כי ‪ ⇔ a ∈ X B , F‬ל‪ a -‬יש סדרת יצירה מתוך ‪. X B , F‬‬

‫‪  89‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דגש‬ ‫סדרת יצירה הינה תמיד סופית אולם איננה יחידה או מינימלית בהכרח‪.‬‬ ‫‪ ‬‬

‫איך נראה כי ‪? a ∉ X B , F‬‬

‫כדי להוכיח כי ‪ a ∉ X B , F‬נמצא תכונה ‪ T‬המקיימת‪:‬‬ ‫‪ a .1‬לא מקיים את ‪.T‬‬

‫‪T‬‬

‫‪X B ,F‬‬

‫‪a‬‬

‫‪ .2‬כל איברי ‪ X B , F‬מקיימים את ‪.T‬‬

‫הוכחת ‪ 1‬הינה בדרך כלל מיידית‪ .‬הוכחת ‪ 2‬הינה הוכחה באינדוקציית מבנה‪.‬‬ ‫נסמן ב‪ Y -‬את קבוצה האיברים המקיימים את ‪ . T‬עלינו להוכיח כי ‪. X B , F ⊆ Y‬‬ ‫על פי משפט האינדוקציה מספיק שנוכיח‪:‬‬ ‫• ‪ , B ⊆ Y  ‬כלומר כל איברי הבסיס ‪ B‬מקיימים את ‪  .T‬‬

‫• ‪ Y  ‬סגורה תחת ‪ , F‬כלומר כל הפעולות ב‪ F -‬משמרות את התכונה ‪. T‬‬ ‫דוגמא‬ ‫תהי שפה של מילים מעל האותיות ‪ a, b‬שתוגדר כך‪ B = {a, b} , F = { f1 , f 2 , f3 } :‬כך ש‪:‬‬ ‫‪ f1‬מוסיפה ‪ aba‬מימין למילה‪ f 2 .‬מחליפה את ה‪ aa -‬הימני ביותר ב‪ b -‬ו‪ f 3 -‬מוחקת את ה‪bbb -‬‬

‫הימני ביתר‪ .‬נראה כי ‪ aba‬איננה שייכת לשפה‪.‬‬ ‫נבחר את התכונה ‪ : T‬מספר ה‪ a -‬במילה הוא אי זוגי‪.‬‬ ‫בהינתן מילה ‪ , w‬נסמן ב‪ # a ( w ) -‬את מספר ה‪ a -‬ב‪ . w -‬כעת‪:‬‬ ‫‪ aba   .1‬לא מקימת את ‪. T‬‬ ‫‪  .2‬נוכיח באינדוקציית מבנה על שפת ‪ ABA‬את התכונה ) ‪ # a ( w‬הוא אי זוגי‪) .‬חשוב לצין על מי‬ ‫מוכיחים ואת איזה תכונה מוכיחים(‪  .‬‬

‫‪  90‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫בסיס‪ :‬המילה ‪ # a ( ab ) = 1 : ab‬אי זוגי‪.‬‬ ‫סגור‪:‬‬ ‫‪ : f1‬נניח שהמילה ‪ w‬מקיימת את ‪ , T‬ונראה כי ) ‪ f1 ( w‬מקיימת את התכונה‪.‬‬ ‫‪ . # a ( f1 ( w ) ) = # a ( w ) + 2‬לפי הנחת האינדוקציה ) ‪ # a ( w‬אי זוגי‪ ,‬ולכן ) ) ‪ # a ( f1 ( w‬גם אי זוגי‪.‬‬ ‫‪ : f 2‬נניח שהמילה ‪ w‬מקיימת את ‪ , T‬ונראה כי ) ‪ f 2 ( w‬מקיימת את התכונה‪.‬‬ ‫‪ ‬אי זוגי ⇒ ‪# a ( f 2 ( w ) ) = # a ( w ) − 2‬‬

‫‪ : f 3‬נניח שהמילה ‪ w‬מקיימת את ‪ , T‬ונראה כי ) ‪ f 3 ( w‬מקיימת את התכונה‪.‬‬ ‫‪ ‬אי זוגי ⇒ ) ‪# a ( f 3 ( w ) ) = # a ( w‬‬

‫ניתן להסיק שבכל המילים שבשפת ‪ ABA‬מספר ה‪ a -‬אי זוגי ולכן ‪ aba‬לא מילה בשפה‪.‬‬

‫‪ .7.3.4‬דוגמת ‪change‬‬ ‫‪ .1‬הגדרת }‪ {a, b‬כקבוצה אינדוקטיבית‪.‬‬ ‫*‬

‫יהי הבסיס } ‪ B = {ε‬ונגדיר את הפעולות‪ F = { f a , f b } :‬כך‪. f a ( w ) = wa, fb ( w ) = wb :‬‬

‫‪ .2‬הגדרת פונקצית ‪ change‬על המבנה‪:‬‬ ‫‪change ( wa ) = change ( w ) b change ( wb ) = change ( w ) a  ‬‬

‫טענה‬ ‫לכל }‪ w ∈ {a, b‬מתקיים‪. change ( change ( w ) ) = w :‬‬ ‫*‬

‫נוכיח את הטענה באינדוקציית מבנה על }‪. {a, b‬‬ ‫*‬

‫‪  91‬‬

‫‪change ( ε ) = ε ,‬‬

‫ניר אדר‬

  [email protected]

change ( change ( ε ) ) = ε :‫בסיס‬

. change ( change ( w ) ) = w ‫ מקיימת‬w ‫ נניח כי‬:‫ הנחת האינדוקציה‬:‫סגור‬ .‫ מקיימת את התכונה‬f a ( w ) ‫ צ"ל כי‬: f a

(

)

change change ( f a ( w ) ) = change ( change ( wa ) ) = change ( change ( w ) b ) = = change ( change ( w ) ) ⋅ a = wa = f a ( w )

 

.‫ ההוכחה נעשית באופן סימטרי‬: f b

‫ כרלציה‬change ‫כתיבת‬

ε , ε ∈ change ⇐ change ( ε ) = ε . wa, ub ∈ change, wb, ua ∈ change ‫ ( אזי‬change ( w ) = u ‫ )כלומר‬w, u ∈ change ‫אם‬

‫משפט הרקורסיה‬ .7.3.5 f ‫ אזי קיימת פונקציה‬, h : Σ × E → E ‫ ותהי הפונקציה‬,‫ איבר‬a ∈ E -‫ קבוצה ו‬E ,‫בית‬-‫ אלף‬Σ ‫יהי‬

:‫ המקיימת‬f : Σ* → E ‫יחידה‬   . f ( ε ) = a   .1   . f ( ws ) = h ( s, f ( w ) ) ‫ מתקיים‬w∈ Σ* ‫ ולכל‬s ∈ Σ ‫לכל‬  .2

:change ‫בדוגמת‬ . change : Σ* → E ‫ והפונקציה הינה‬Σ = {a, b} , E = {a, b}

*

. a = ε ‫ ולכן‬f ( ε ) = ε . change ( wa ) = h ( a, change ( w ) ) = change ( w ) b : h ‫הפונקציה‬

  92

‫ניר אדר‬

‫‪  [email protected]‬‬

‫‪ .7.3.6‬דוגמא מסכמת – קבוצת מחרוזות מעל ‪S, T‬‬ ‫העולם ‪ A‬יוגדר להיות כל המחרוזות הסופיות מעל ‪ , s, t‬כלומר הקבוצה }‪. {s, t‬‬ ‫*‬

‫הבסיס ‪ B‬הינו }‪ , {ε , st , ts‬וקבוצת הפעולות ‪ F‬הינה })⋅ ( ‪ , F = { f1 ( ⋅, ⋅) , f 2 ( ⋅, ⋅) , f 3‬כאשר‬ ‫‪f1 (α , β ) = sαβ t , f 2 (α , β ) = tαβ s‬‬ ‫‪α  without the last st α  contains st  that are not as the first 2 letters  ‬‬ ‫‪f 3 (α ) = ‬‬ ‫‪else‬‬ ‫‪α‬‬

‫לדוגמא‪. f 3 ( stt ) = stt , f 3 ( ttts ) = ttts, f 3 ( stst ) = st :‬‬

‫הגדרנו כאן קבוצה אינדוקטיבית מעל ‪X s ,t : B, F‬‬

‫נראה עבור מילה מסויימת כי היא נמצאת ב‪ . X s ,t -‬עושים זאת על ידי הצגת סדרת יצירה המייצרת את‬ ‫המילה‪ .‬תהי המילה ‪ . α = tststs‬למילה זו אינסוף סדרות יצירה‪ .‬אחת מהן לדוגמא‪:‬‬ ‫→‪st ‬‬ ‫‪tsts ‬‬ ‫‪→ ststst ‬‬ ‫‪→ tstststs ‬‬ ‫‪→ tststs  ‬‬ ‫) ‪f 2 ( ε , st‬‬ ‫) ‪f1 ( tsts ,ε‬‬ ‫‪f2‬‬ ‫‪f3‬‬

‫נשים לב‪:‬‬ ‫• ‪ ‬סדרת יחידה איננה בהכרח יחידה‪  .‬‬ ‫• ‪ ‬סדרת יצירה איננה בהכרח מינימלית‪  .‬‬ ‫• ‪ ‬סדרת יצירה תמיד מתחילה באטום‪  .‬‬ ‫• ‪ ‬סדרת יצירה היא סדרה של איברים‪  .‬‬

‫איך מראים ש‪ ? α ∉ X B , F -‬נמצא תכונה ‪ T‬המקיימת כי ‪ α‬לא מקיים את ‪ T‬וגם כל איברי ‪X B , F‬‬

‫מקיימים את ‪ .T‬נגדיר קבוצה ‪ Y‬שאיבריה הם כל איברי ‪ A‬המקיימים את התכונה ואז נדרוש‬ ‫‪ X B , F ⊆ Y‬אבל ‪ . α ∉ Y‬לפי משפט ההוכחה באינדוקציה‪ ,‬על מנת להוכיח שקבוצה ‪ Y‬מקיימת כי‬ ‫‪ X B , F ⊆ Y‬מספיק להראות כי‪ B ⊆ Y :‬וכי ‪ Y‬סגורה ל‪. F -‬‬

‫‪  93‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫טענה‬ ‫נטען‪tsst ≠ X s ,t :‬‬

‫הוכחה‪ :‬התכונה ‪ – T‬אם ‪ α‬מתחיל ב‪ t -‬אזי הוא מסתיים ב‪. s -‬‬ ‫נוכיח באינדוקציית מבנה של איבר ב‪ X s ,t -‬מקיים את ‪.T‬‬ ‫בסיס‪ :‬נעבור על כל איברי הבסיס ‪: B‬‬ ‫‪ ε‬מקיים את ‪ T‬באופן ריק‪ st .‬מקיים את ‪ T‬באופן ריק‪ ts .‬מקיים את ‪.T‬‬ ‫סגור‪ :‬נעבור על כל הפעולות ב‪ F-‬ונראה כי ‪ Y‬סגור לפעולות‪.‬‬ ‫)⋅ ‪ - f1 ( ⋅,‬אם ‪ α , β ∈ Y‬אז ‪. f1 (α , β ) = sαβ t ∈ Y‬‬ ‫)⋅ ‪ - f 2 ( ⋅,‬אם ‪ α , β ∈ Y‬אזי ‪. f 2 (α , β ) = tαβ s ∈ Y‬‬ ‫)⋅ ( ‪ - f 3‬נניח כי ‪ β ∈ Y‬ויהי ) ‪ . α = f 3 ( β‬נפריד למקרים‪:‬‬ ‫‪  .1‬אין כלל השמטת רצף ‪ . st‬במקרה זה ‪ α = β‬ולכן ‪  . α = β ∈ Y‬‬

‫‪  .2‬השמטת רצף ‪ st‬מהאמצע‪ ( β1 , β 2 ≠ ε ) β = β1st β 2 :‬ואז ‪ . α = β1β 2‬ההתחלה והסוף של‬ ‫‪ β‬נשמרו ב‪ α -‬ולכן ‪  . α ∈ Y‬‬

‫‪  .3‬השמטת רצף ‪ st‬מהסוף ‪. α = β1 , β = β1st -‬‬ ‫צריך להוכיח כי אם ‪ α‬מתחיל ב‪ t -‬אז הא מסתיים ב‪ . s -‬נוכיח כי לא ייתכן ש‪ α -‬מתחיל ב‪t -‬‬

‫ולכן הטענה תתקים באופן ריק‪.‬‬ ‫נניח בשלילה כי ‪ α‬מתחיל ב‪ α = β1 . t -‬ולכן ‪ β1‬מתחיל ב‪ . t -‬לפי הגדרה ‪ β = β1st‬ולכן גם‬ ‫‪ β‬מתחיל ב‪ t -‬אבל גם מסתיים ב‪ , t -‬בניגוד להנחת האינדוקציה כי ‪  . β ∈ Y‬‬

‫הראנו כי ‪ . X s ,t ⊆ Y‬נראה כעת כי ‪ α‬לא מקיים את ‪:T‬‬ ‫‪ tsst‬מתחיל ב‪ t -‬ומסתיים ב‪ ⇐ t -‬לא מקיים את ‪. tsst ∉ X s ,t ⇐ tsst ∉ Y ⇐ T‬‬

‫‪  94‬‬

‫ניר אדר‬

‫‪  [email protected]‬‬

‫דוגמא‬ ‫תהיינה ‪ S1 = X B1 , F1 , S2 = X B2 , F2‬כך ש‪. S1 = S2 -‬‬ ‫הוכיחו‪. X B1 ∪ B2 , F1 ∪ F2 = S1 = S2 :‬‬ ‫‪S3‬‬

‫נראה ‪ : S1 ⊆ S3‬ניתן להסתפק בכך שכל סדרת יצירה ב‪ S1 -‬היא גם סדרת יצירה ב‪ S3 -‬לפי הגדרת‬ ‫האיחוד‪.‬‬ ‫נראה ‪) : S3 ⊆ S1‬באינדוקציה(‬ ‫בסיס‪ :‬לכל ‪ , b ∈ B1 ∪ B2‬נראה כי ‪. b ∈ S1‬‬ ‫‪ , b ∈ B1 ∪ B2‬ולכן‪ b ∈ S1 ⇐ b ∈ B1 :‬כי ‪. B1 ⊆ S1‬‬ ‫או ‪ b ∈ S2 ⇐ b ∈ B2‬כי ‪ B2 ⊆ S2‬ולפי הנתון ‪ S1 = S2‬ולכן ‪. b ∈ S1‬‬ ‫סגור‪ . a1 ,..., an ∈ S1 :‬נראה סגירות של אגף ימין ) ‪ ( S1‬לפעולות של הקבוצה באגף שמאל ) ‪. ( S3‬‬ ‫תהי ‪ . f ∈ F1 ∪ F2‬אם ‪ f ∈ F1‬אזי ‪ f ( a1 ,..., an ) ∈ S1‬כי ‪ S1‬סגורה לפעולות ‪ . F1‬אם ‪ f ∈ F2‬אזי‬ ‫‪ f ( a1 ,..., an ) ∈ S2‬כי ‪ S2‬סגורה לפעולות ‪ F2‬ולפי הנתון ‪ S1 = S2‬ולכן ‪. f ( a1 ,..., an ) ∈ S1‬‬

‫‪EOF‬‬

‫‪  95‬‬