2 – апта. Арнайы бинарлық қатынастар
жүктеу/скачать 172,92 Kb.
|
2 лекция (2)
| 1.7 Реттелген жиындар.
Анықтама. 1) А жиынында анықталған рефлексивтi, антисимметриялы және транзитивтi R қатынасы А жиынындағы жартылай рет деп аталады. Егер элементі табылып, кез келген үшін () болса, онда элементі ең кіші элемент ( ең үлкен элемент) деп аталады. Егер элементінен кіші (үлкен) элемент болмаса, оны минимал (максимал) элемент деп айтады. 2) R қатынасы A жиынында анықталған жартылай рет болсын. Егер кез келген a,bA элементтерi үшiн (a,b)R немесе (b,a)R шарттарының ең болмағанда бiреуi орындалса, R қатынасын сызықты рет деп атаймыз. 3) Егер реттелген жиынның және b элементтері үшін және қатынастарының ешқайсысы орындалмаса, онда және b элементтерін салыстырымсыз деп атайды. 4) және реттік қатынастары берілсін. Егер биекциясы үшін үшін шарты орындалса, онда бұл реттік қатынастарды изоморфты деп айтады. Белгілеуі: . Жоғарыдағы анықтамалардан кез келген екі элементі салыстырымды болатын реттелген жиынның сызықты рет болатынын көреміз. Сызықты реттерде ең үлкен элемент (ең кіші элемент) болуы да, болмауы да мүмкін. Енді осы анықтамада берілген түсініктерге мысалдар келтірейік. Мысалдар. Егер – нақты сандар жиынының кез келген iшкi жиыны болса, онда R (a,b) a,b ab қатынасы сызықты рет болады. B . P(B) жиыны жиынының барлық iшкi жиындарының жиыны болсын. Егер W P(B) болса, онда U = { (X,Y) X,YW, X қатынасы W жиынында анықталған жартылай рет болады. Әрине бұл рет сызықты рет болмайды. Мысалы, қиылыспайтын бос емес жиындар өзара салыстырымсыз. m,n) m,n және m саны n санына қалдықсыз бөлiнедi қатынасы да жартылай рет, бiрақ сызықты рет болмайды. Мысалы, бірден және нөлден өзге ең үлкен ортақ бөлгіші 1-ге тең екі сан өзара салыстырымсыз. Қазақ тілінің алфавиті сызықты рет, ондағы . Осы сызықты рет арқылы қазақ тіліндегі барлық сөздер жиынында лексикографиялық ретті былай тағайындаймыз: . Мысалы ІлесбекІлесгүл. Теңдік қатынасы жартылай рет болады, бірақ сызықты рет емес, өйткені әртүрлі элементтер бұл қатынас бойынша салыстырымсыз. Осы рет бойынша берілген жиынның әрбір элементі әрі минимал элемент, әрі максимал элемент болады. Бірақ бұл жиында ең үлкен элемент те, ең кіші элемент те жоқ. және реттелген жиындар берілсін. Онда лексикографиялық ретке ұқсастырып, бос емес жиынындағы ретті шартымен анықтауға болады. Бұл рет сызықты емес. Мысалы, (2,3) және (1,2) парлары салыстырымсыз. Берілген жиынында анықталған барлық эквиваленттілік қатынастар «ішкі жиын болу» қатынасы бойынша жартылай реттелген жиын болады. Бұл реттелген жиынның минимал элементі – диагоналдық элементтерден тұратын қатынасы, ал максимал элементі – жиынының барлық элементтерінің парлар жиыны болады.
Жоғарыдағы мысалдар минимал элементтердің ең кіші элемент болуы міндетті емес екенін көрсетеді. Бұл мысалда 2 және 3 сандары минимал элементтер, бірақ ең кіші элементтер емес. Ал 24 әрі максимал, әрі ең үлкен элемент. Бірақ, максимал элементтер де әрқашан ең үлкен элемент болуы тиіс емес. Ең кіші және ең үлкен элементтерден өзге сәйкес минимал және максимал элементтер болмауы мүмкін. Мысалы, натурал сандар жиынындағы бөлу қатынасы арқылы анықталған ретте ең кіші элемент бар, ол – 1 және ең үлкен элемент бар, ол – 0, бірақ 1-ден өзге минимал элемент, 0-ден өзге максимал элемент жоқ. жүктеу/скачать 172,92 Kb. Достарыңызбен бөлісу:
|