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