Reja: •Daraxt va unga ekvivalent tushunchalar • Daraxtlarni Prufer usulida kodlash • Daraxtlarni ularning kodi bo’yicha

Ekvivalentlik munosabati

[u7! Ref leksiv, simmetrii, va t ranzit iv m unosabat lar.

Ekvivalentlik sinfi.

1-taʼrif.

Аgar X tuplamning istalgan x elementi

uchun x r x bulsa, u xolda r munosabati X tuplamdagi reflek­

siv munosabat deb ataladi; agar x r u dan u rx kelib chitssa,

u xolda r simmetrii munosabat deb ataladi; agar x r u va

u p z dan x p z kelib chin;sa, u xolda r tranzitiv munosabat

deb ataladi.

Sh u k u r s at i l ga n u ch al a x o ssaga e ga b u lgan m u n o sa b a t l a r

m atem atikada k u p u ch r agan i uchun u larga maxsus n o m kuy i lgan .

2-taʼrif . Аgar biror tuplamdagi munosabat refleksiv,

simmetrik va tranzitiv xossalarga ega bulsa, u xolda bunday

munosabat shu tuplamdagi ekvivalentlik munosabati deyiladi

А gar r m u n o s a b a t i X tu p l am d agi e k v i v a l ye n t l i k m u n o s a ­

bati bulsa, u \o l d a Dp = X.

M i s o l l a r . K u y i d a g i x ar b i r m u n o s a b a t m a ʼ l u m

tu p l am d agi e k v i v a l ye n t l i k m u n o s a b a t i ga m i so l bula o l ad i :

1. I s t a l ga n tu p l am d agi t ye n g l i k m u n o sab ati .

2. Ye v k l i d t ye k i s l i g i n i n g x am m a u ch b u r ch ak l a r t u p l a m i -

d agi u x sh a sh l i k m u n o sa b ati .

3. Butun so n l a r tu p l am i d agi m odulь b uy i ch a t a k k o s l a m a

m u n o sab ati .

4. M a m l a k at d a ya sh o v ch i o d a m l a r tu p l am i d a gi «b i r u y d a

ya sh o vch i l a r » m u n o sa b a t i .

E k v i v a l ye n t l i k m u n o sa b ati u sh b u as o s i y x u su si yatga ega:

u t u p l a m n i k ye s i sh m a y d i g a n k i ye m t u p l a m l a r g a b u l a d i .

K ye y i n gi m i s o l , m asa l an , «bir u y da yash o vch i l ar » m u n o sa b a t i

m a m l a k a t n i b i r - b i r i b i l a n k ye s i sh m a y d i g a n « b i r u y d a

ya sh o vch i l a r » d i s m t u p l a m l a r i ga buladi . Bu a y t i l ga n l a r n i

K uyi dagi cha u m u m l a sh t i r i sh m u m k i n .

r b i r o r X tu p l am d agi e k v i v a l ye n t l i k m u n o sab a ti b u l si n .

А gar X t u p l a m n i n g А k i ye m t u p l a m i n i n g sh u n d a y x e l ye ­

m ye n t i t o p i l i b , А = {u/xru} b u lsa, u xolda А k i ye m tu p l am

ekvivalentlik sinfi yok i ekvivalentlik r - sinfi d yeb atal ad i .

Sh u n d ay k i l i b , X t u p l a m n i n g sh u n d ay e l ye m ye n t i m avj u d

b u l s ak i , А = r[{x}] t ye n g l i k b a j a r i l s a , u v ak gd a А t u p l am

e k v i v a l ye n t l i k s i n f i b uladi .

А gard a r m u n o sa b a t tu gr i si d a xech k a n d a y a n g l a sh i l m o v -

ch i l i k tu t i l m a y d i ga n b ulsa, u v a k gd a X tu p l am [x] sh a k l i d a