حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۷
برای نشان دادن ناشمارا بودن رشته مورد نظر نشان میدهیم که تناظری بین 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 در تناظر نیست پس به تناقض میرسیم و این ناشمارا بودن رشته را نشان میدهد.