یک رشته، یک دنبالهی متناهی از صفر و یک است. A یک مجموعهی متناهی از رشتههاست که برای هر دو رشتهی دلخواه α و β از آن داریم αβ=βα. (منظور از αβ رشتهای است که از کنار گذاشتن دو رشتهی α و β بهدست میآید. برای مثال اگر α=011 و β=10 باشد، آنگاه αβ=01110 خواهد بود.)
ثابت کنید که رشتهای مانند w وجود دارد که هر رشتهی دلخواه A را میتوان از کنار هم گذاشتن تعدادی w بهدست آورد.
پاسخ
در صورتی که رشتهی β از کنار هم گذاشتن تعدادی رشتهی α تولید شود، α را یک سازهی β مینامیم. طول رشتهی α را با |α| نشان میدهیم. برای حل مسئله، ابتدا دو لم زیر را ثابت میکنیم:
لم ۱: اگر αβ=βα آنگاه α و β یک سازهی مشترک دارند.
اثبات: حکم را با استقرا روی |αβ| ثابت میکنیم. اگر |αβ|=|α||β|=2 باشد، حکم واضح است.
فرض میکنیم که برای هر α′ و β′ که α′β′=β′α′ و |α′β′|<|αβ| حکم برقرار باشد و حکم را برای α و β به این صورت ثابت میکنیم: اگر فرض کنیم |β|<|α|، چون αβ=βα=A است، در نتیجه |α| رقم اول A از طرفی |α| و از طرف دیگر همان α رقم اول β است. بنابراین β=αβ′ است. پس ααβ′=αβ=βα=αβ′α و در نتیجه αβ′=β′α است. حال با توجه به این که |αβ′| از |αβ| کمتر است، با استفاده از فرض استقرا نتیجه میگیریم که α و β′ سازهی مشترک دارند که این سازهی مشترک چون هم α و هم β′ را میسازد، پس β=αβ′ را نیز میسازد.
در صورتی که |α|<|β| باشد نیز به همین صورت میتوان استدلال کرد. همچنین اگر |α|=|β| باشد، α و β باهم برابرند و در نتیجه سازهی مشترک دارند.
لم ۲: اگر α و β دو سازهی مشترک A باشند، آنگاه α و β سازهی مشترک دارند.
اثبات: چون α و β سازههای A هستند، برای هر k داریم:
k⏞AA…A=α…α=β…β=X
d را برابر بزرگترین مقسوم علیه مشترک |β| و |α| میگیریم. فرض میکنیم:
X=w1w2…wnn=k|α||β|d|wi|=d
از طرفی چون X=α…α است، داریم wi=wi+l|α|d و چون X=β…β است، داریم wi=wi+l|β|d (برای هر l). از طرف دیگر با توجه به تعریف d، l1 و l2 وجود دارند که l1|α|−l2|β|=d و در نتیجه l1|α|d=l2|β|d+1. بنابراین برای هر i داریم:
wi=wi+l1|α|d=wi+1+l2|β|d=wi+1⇒w1=w2=…
پس w=wi یک سازهی مشترک برای β و α است.
نتیجهی لم۲: اگر α1,…,αn سازههای A باشند، آنگاه αi ها سازهی مشترکی دارند.
اثبات نتیجهی فوق واضح است.
اثبات مسئله: یک عضو از A را به دلخواه انتخاب میکنیم و آن را α مینامیم. برای هر βi∈A، بنا به فرض داریم αβi=βiα و در نتیجه بنا به لم ۱ نتیجه میشود که α و βi سازهی مشترکی دارند که آن را wi مینامیم. حال همهی wi ها را در نظر میگیریم. بنا به نتیجهی لم ۲ این رشتهها دارای یک سازهی مشترک هستند که آن را w مینامیم. چون w سازهی wi و wi سازهی βi است، پس w سازهی مشترک همهی βi هاست و بنابراین حکم ثابت میشود.