Бинарные отношения

Рассм отнош связ-щие различ пары эл-ов некот мн-ва А. Опр: бин отн-ем наз " мн-во упор-х пар, если эл-ты <x,y> мн-ва А связаны отн-ем r(ро): хrу. Св-ва бин отнош-я: 1 бин отнош-е r наз рефл-ым(R) на мн-ве А, если для " эл-та х из А, xrx 2. Отн-е r на мн-ве А наз симм-ым(S), если для "двух эл-ов х и у из А xry Þ yrx 3. Отн-е r на А наз антиS, если хrу и уrхÞ х=у 4. Отн-е r наА наз транз-ым(T), если для "трех эл-ов х,у,z на А хrу и уrzÞ хrz 5. R,S,T отнош-е r на А наз отн-ем эквив-ти · С отн-ем эквив-ти связ-но понятие классов эквив-ти - это мн-во эл-ов из А, наход-ся с А в данном отнош-ии r. Обоз:K _a= {xÎ/хra} Св-ва 1. Класс экв-ти не пуст.Док-во. "а, аÎК_а в силу R отнош-я эквив-ти. 2 b,cÎK_a,то brc Док-во,т.к brа и сraÞпо Т brc 3 если аrb,то классы совпадают Д-во1)пусть хÎK_a Д-ем,что хÎK_b: xrа,аrb,поТ хrbÞ хÎK_b 2) yÎК_bÞyrb т.к аrb Þ поS brаÞ по T уraÞпо опр-ю у ÎК_а 4 если а,b не наход-ся в отн-ии r,то К_а и К_b ¹Æ; если аrb то К_аÇ К_b=0.Д-во:пусть хÎА,хÎК_а,хÎК_b;хra,хrb по S хrаÞаrх,arх и хrbÞпоТаrb–это явл-ся против-ем усл-юÞ из правила вывода (,AÞB)/ Þ что св-во верно 5 объед-ие классов экв-ти совп-ют с дан мн-ом.Д-воÞиз переч-ых выше св-в Т1:"отн-ие экв-ти на мнА задает на этом мн-ве разбиение на подмн-ва(классы) Т2 " разбиение мнА задает на этом мн-ве отн-ие экв-ти · Фактор мн-ва. Пусть дано А и отн-ие экв-ти s на этом мн-ве.Отн-ие s порождает на мн-ве мн-во классов экв-ти –это фактор мн-в А/s={K_a/aÎA} ·Отн-ие порядка. Бин.отн-ие наз отн-ем пор-ка, если оно Т и антиS.Отн-иеs на А наз ирR, если для "эл-та х на А пара хх Ï отн-ию s. "хÎА<x:x>Ïs Отн-ие s наз отн-ем строгого пор-ка на А,если оно ирR, T и антиS(< >) Отн-ие s наз отн-ем не строгого пор-ка, если оно R,антиS и T(£) Если для "a и b из некот мн-ва А аrb, либо brа,либо а=b,то пор-к наз линейным.В прот-ом случ пор-к наз частичным Отн-е включения на мн-ве всех подмн-в есть отн-е не строгого пор-ка. Отн-е делимости на мн-ве N есть отн-е не строгого пор-ка.Упор-ое мн-во –это мн-во с отн-ем пор-ка.Если порядок линейный,то лин-но упор-ое мн-во.Если порядок частичный,то част-упор-ое мн-во.