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

باید نشان دهیم T با مجموعه ی N هم ارز می‌باشد. برای نشان دادن هم اندازه بودن فقط باید یک تابع یک به یک پوشا به دست آورد.

هر کدام از مولفه‌های T به تنهایی هم ارز با N می‌باشند. شرایط زیر را در نظر بگیرید:

F(n) = n
- i= P(i)=F(n)
- j= G(j)=F(j)+1
- k= R(k)=F(k)+2
- T(i, j, k) = T(P(i), G(j), R(k))

تابع روبه رو یک تابع یک به یک پوشا از N به T می‌باشد. پس T شمارا است.