Иккинчи боб

---

Mavzu:Tartib munosabati. Tartiblangan toʻplamlar. 
 
 
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 xAgar 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
M
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 
m
A

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)
2
M
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. 
Teorema: (matematik induktsiya tamoyili). Xar bir 
n
N

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 
n
N

 uchun chin bo`ladi. 

---

I s b o t. Faraz qilaylik, biror 
n
N

uchun T(n) chin bo`lmasin. T(n)
tasdiq chin bo`lmagan barcha 
n
N

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 
2) faraziga zid. 
M i s o l. Ixtiyoriy 
n
N

uchun ushbu 
2
2
2
(
1)(2
1)
1
2 ...
6
n n
n
n





tenglikni isbotlaymiz. 
Agar 
n

1 bo`lsa, bu tenglik ravshan. Faraz qilaylik, bu tenglik n sondan 
kichik bo`lgan barcha natural sonlar uchun o`rinli bo`lsin. Xususan
2
2
2
(
1) (2
1)
1
2 ... (
1)
6
n n
n
n
n



 

tenglik o`rinli bo`lsin. Bu tenglikning ikki tomoniga n
2
 sonni qo`shamiz: 
2
2
2
2
2
2
(
1) (2
1)
1
2
... (
1)
6
(
1)(2
1)
(2
3
1 6 )
6
6
n
n n
n
n
n
n
n n
n
n
n
n



  








 

Bu bilan matematik induktsiya tamoyiliga asosan tenglik xar qanday 
n
N

uchun o`rinli ekanligi isbotlandi.