מציאת עוצמה של קבוצת שפות

כיצד למצוא את עוצמת קבוצת כל השפות המקיימות L=L^* מעל הא"ב \Sigma =\left \{ 1 \right \} ?
אשמח להכוונה,
תודה רבה.

מילה מעל האלפבית \Sigma = \{1\} היא פשוט מילה שמורכבת מכמות מסוימת של אחדים ולכן היא ייחודית על-פי אורכה. לכן אנו יכולים להתאים את קבוצת המילים מעל האלפבית \Sigma = \{1\} לקבוצת המספרים הטבעיים. תחת זיהוי זה, שרשור מילים שקול לחיבור מספרים טבעיים.

שפה מעל \Sigma היא קבוצה של כל המחרוזות מעל האלפבית \Sigma. לכן ניתן להתאים את השפה עם קבוצת המספריים הטבעיים L\subseteq \mathbb{N}. לפיכך השפה L^* מתאימה לקבוצת כל הסכומים הסופיים של המספרים ב-L. אי-לכך מתקיים L=L^* אם"ם L סגורה תחת חיבור סופי.

פישטנו את הבעיה הנתונה לבעיה מתורת הקבוצות: מהי העוצמה של קבוצת כל תתי-הקבוצות של \mathbb{N} שסגורים תחת חיבור סופי. ישנן מספר דרכים להוכיח זאת. אראה כאן אחת מהן.

כמובן, יש אינסוף קבוצות שמקיימות את התנאי. לכל אחת n\in\mathbb{N}, הקבוצה \langle n \rangle = \{kn\mid k\in \mathbb{N}\} של כפולות של n סגורה תחת חיבור סופי. אני טוען כי אם L\subseteq \mathbb{N} סגורה תחת חיבור סופי אזי קיימים N ו-n טבעיים כך שמתקיים L\subseteq \langle n\rangle וגם L\cap [N,\infty) = \langle n\rangle \cap [N,\infty) כאשר [N,\infty) = \{m\in \mathbb{N}\mid N\leq m\}. שים לב כי מספר האפשרויות לבחור את n ו-N היא בת מניה. לאחר שהגודרו n ו-N נוכל להסיק כי עבור L יש מספר סופי של אפשרויות (2^N). לכן, ע"פ טענה זו נובע כי קבוצת תתי-הקבוצות של \mathbb N שסגורות תחת חיבור סופי היא בעלת עוצמה \aleph_0.

נותר רק להוכיח את הטענה. את החלק הטכני והלא כל כך מורכב, אני משאיר לך. כמו כן, ישנן מספר דרכים אחרות לפתור את השאלה. דרך זו הרגישה הכי מעניינת ופשוטה.

תודה רבה