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

1- باید ثابت کنیم هر مجموعه ی A با خودش هم اندازه‌است.

یعنی یک تابع یک به یک و پوشا از A به Aموجود است.

ثابت می‌کنیم تابع f(x)=xیک به یک و پوشاست.

f(a)=a

f(b)=b

f(a)=f(bدرنتیجه a=b پس fیک به یک است

و همچنین می‌دانیم به ازای هر bعضو a,Aوجود دارد که f(a)=b.کافیست a=bدر نظر بگیریم . پس fپوشا است .

2- اگر A با B هم اندازه باشد آنگاه B هم با A هم‌اندازه است.

اگر f تابعی باشد که ثابت می‌کند A با B هم اندازه‌است ثابت می‌کنیم تابع gکه معکوس تابع f است تابعی یک به یک و پوشا از Bبه Aاست. چون g معکوس f است و f یک به یک است پس یک به یک است. برای پوشا بودن به ازای a عضوf(a) ,A وجود دارد که g(f(a))=a و (f(a عضو B است. پس g پوشا است.

3- اگر A با B و B با C هم اندازه باشد آنگاه َA هم با C هم اندازه‌است.

اگر fوgبه ترتیب دوتابعی باشند که AراباBوBرابا Cهم اندازه می‌کنند تابعh(x)=fog(x)تابعی است که ثابت می‌کند A باC هم اندازه‌است .

h(a)=f(g(a))

h(b)=f(g(b))

h(a)=h(bپسf(g(a))=f(g(bوچون fوgهردو یک به یک هستند پس a=b پس hیک به یک است.

برای پیداکردن عضو برای اثبات پوشایی: به ازای a عضو C عضو G(F(a وجود دارد که h(G(F(a)))=a که FوGبه ترتیب معکوس توابع f و g هستند.

پس رابطه ی هم اندازه بودن یک رابطه ی هم ارزی است .