Иккинчи боб

TARTIB MUNOSABATI. MATEMATIK INDUKTSIYA

Endi A to`plamda tartib munosabati kiritamiz.
A to`plamdagi antirefleksiv va tranzitiv bo`lgan R munosabatga A to`plamda tartib munosabati deyiladi va aRb o`rniga a < b yoki a > b yoziladi.
Misollar:
1) R xaqiqiy sonlar to`plamida x va u sonlar orasidagi x < u tengsizlik munosabati;

2. 
   Biror M to`plamning barcha qism to`plamlari tizimini 2^M orqali belgilaymiz. U xolda 2^M da qism to`plamlar orasidagi " " munosabat tengsizlik munosabati bo`ladi,
   
3. 
   N natural sonlar to`plamida bo`linish munosabati:
   agar u son x ga bo`linsa va u x bo`lsa, ular xmunosabatda deymiz.
   

Agar A to`plamda biror tartib munosabati berilgan bo`lsa, A to`plam qisman tartiblangan deyiladi.
Agar qisman tartiblangan A to`plamda ixtiyoriy x, u A elementlar uchun x < u, x u, x > u munosabatlarning biri o`rinli bo`lsa, bunday to`plam chiziqli tartiblangan deyiladi.
Yuqorida keltirilgan misollarga qaytamiz: 1) R-chiziqli tartiblangan; 2) agar M to`plamda faqat bitta element bo`lsagina 2<sup>M</sup> to`plam chiziqli tartiblangan bo`ladi.
Agar qisman tartiblangan A to`plamning ixtiyoriy V qism to`plami elementlari uchun A dagi tartib munosabati qaralsa, u munosabat V da xam tartib munosabati bo`ladi. Agar A- chizikli tartiblangan bo`lsa, V xam chiziqli tartiblangan bo`ladi (isbotlang!).
A to`plam qisman tartiblangan bo`lsin. Agar element uchun x< m (x> m) tengsizlikni qanoatlantiruvchi x A element mavjud bo`lmasa, bunday m element minimal (maksimal) zlement deyiladi.
Yuqorida keltirilgan misollarga yana qaytamiz:
1) R da minimal element xam maksimal element xam yo`q;
2) to`plamda bo`sh to`plam-minimal element, M to`plam-maksimal element.
Endi N natural sonlar to`plamida "<" sifatida natural sonlar orasidagi oddiy tengsizlikni olamiz. U xolda N da 1-minimal element bo`ladi, ammo maksimal elementlar mavjud emas. Agar N to`plam N ning ixtiyoriy qism to`plami bo`lsa, unda minimal element mavjud. Bunday element N ayniyat elementlari ichida eng kichigi. Quyida N da xuddi shu tartib ko`riladi.
Natural sonlar to`plamidagi qism to`plamlarning bu xossasidan matematik formulalar va teoremalarni isbotlashning quyidagi usuli kelib chiqadi.
T e o r e m a (matematik induktsiya tamoyili). Xar bir uchun T(n) tasdiq (formula) muloxaza berilgan bo`lsin. Agar shunday qoida (usul) mavjud bo`lsaki, bunga asosan:

1. 
   T(1) tasdiqning chinligini (to`g`riligini) isbotlash mumkin bo`lsa va
   
2. 
   muchun T(m) tasdiqnn chin deb faraz qilib, T(n) ning chinligini ko`rsatish mumkin bo`lsa, u xolda T(n) n tasdiq xar qanday unun chin bo`ladi.
   

I s b o t. Faraz qilaylik, biror uchun T(n) chin bo`lmasin. T(n) tasdiq chin bo`lmagan barcha lar to`plamni N orqali belgilaymiz. Farazimizga muvofiq N to`plam bo`sh emas. .N to`plam N ning qism to`plami bo`lgani uchun uning minimal elementi mavjud. Uni n_o orqali belgilaymiz, U xolda T(n_o) chin emas, ammo xar qanday m< n_o uchun T(m)-chin. Bu esa teoremaning faraziga zid.
M i s o l. Ixtiyoriy uchun ushbu

tenglikni isbotlaymiz.
Agar 1 bo`lsa, bu tenglik ravshan. Faraz qilaylik, bu tenglik n sondan kichik bo`lgan barcha natural sonlar uchun o`rinli bo`lsin. Xususan

tenglik o`rinli bo`lsin. Bu tenglikning ikki tomoniga n² sonni qo`shamiz:

Bu bilan matematik induktsiya tamoyiliga asosan tenglik xar qanday uchun o`rinli ekanligi isbotlandi.