حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۷

برای نشان دادن ناشمارا بودن رشته مورد نظر نشان می‌دهیم که تناظری بین N و رشته مورد نظر وجود ندارد.

از برهان خلف استفاده می‌کنیم. فرض می کنیم fای وجود داشته باشد که هر عضو رشته را به هر عضو N متناظر کند. نشان می‌دهیم اینچنین fای وجود ندارد . عددی مانند X را می‌یابیم که با هیچ عددی در N متناظر نشود. برای این کارعدد X را می‌سازیم.(از روش قطری استفاده می‌کنیم)

f(n) n 1 ... 1000100010 2 ... 1100011101 3 ... 1001111111 4 ... 1000100111

برای داشتن این X عنصر شماره یک رشته شماره یک را NOT می‌کنیم و عنصر شماره 2 رشته دوم را NOT می‌کنیم و به همین ترتیب ادامه می‌دهیم رشته به دست آمده با تمامی رشته‌های متناظر با N متفاوت می‌باشد.

و چون Xای را بدست آوردیم که با هیچ کدام از عناصر N در تناظر نیست پس به تناقض می‌رسیم و این ناشمارا بودن رشته را نشان می‌دهد.