Том 1 (1113042), страница 17
Текст из файла (страница 17)
6 . Пусть Х - множество всех невырожденных матриц nго порядка. Является ли отображением Х х Х � Х правило,которое любой паре матриц из Х ставит в соответствиеа) их сумму;б) их произведение?1 1 . 7. Пусть Е - множество , состоящее из п элементов. Установить биективное отображение множества А всех отображенийЕ во множество {О; 1 } на множество В всех подмножеств множества Е.1 1 . 8 . Пусть Е, F - подмножества множества Х и f : Х � УПоказать, что:б) f ( E n F ) с f ( E ) n f( F ) .а) f ( E u F ) = f (Е) u f ( F ) ;Что изменится в этих соотношениях, если f биективно?1 1 . 9 .
Пусть Е и F - конечные множества, состоящие их m ип элементов соответственно. Найти число всех отображений Е в.F.1 1 . 10. Пусть Е и F - конечные множества, состоящие из mи п элементов соответственно . Показать, что:а) для существования инъективного отображения Е в F необходимо и достаточно, чтобы m < п;б) число инъективных отображений Е в F равноп ( п - 1 ) . .
. (п - m + 1) .1 1 . 1 1 . Пусть Е и F - конечные множества, состоящие из mи п элементов соответственно. Показать , что:.а) для существования сюръективного отображения Е на Fнеобходимо и достаточно, чтобы m > п;б) число сюръективных отображений Е на F равноm-п(п - l ) m + . . . + ( - l ) k C� ( n - k ) m + . . . + ( - 1 ) п - 1 с� - 1 .1 1 . 1 2 . Пусть Е и F - конечные множества, состоящие из mи п элементов соответственно.
Показать, что:nГлава III. Множества и отображения110а) для существования биективного отображения Е на F необходимо и достаточно, чтобы m = п;б) число биективных отображений Е на F равно n! .1 1 . 1 3 . Доказать, что если множество Х бесконечно, а егоподмножество У конечно, то существует биективное отображение Х \ У � Х .1 1 . 14. Для отображения f : Х � У отображение g : Х �У называется лев'Ым (соответственно прав'Ы.м) обратнъtм, еслиgf = ех (соответственно fg = еу ) . Доказать, что:а) отображение f инъективно в том и только том случае, еслионо обладает левым обратным ;б) отображение f сюръективно в том и только том случае,если оно обладает правым обратным .1 1 .
1 5 . Найти произведение перестановок:О � � i ) С � � i } б) U � i � ) ( � � i � }в)(� � : � �) (� � � � �}г) ( �: � i �) (� � � ; �}д) ( ; : � � � �� � � � � �)()в указанном и обратном порядке.ап1 1 . 16. Доказать, что при записи перестановки ( а1 а 2/З 1 /З2 . . . /Зп )1 2 . . .
п общее число инверсии ( ) в перестановкев виде (/1 /2/п )11 , /2 , . . . , /п и сумма ( а ) + ( /З ) имеют одинаковую четность.а)·u··а·а··та1 1 . 17. Пусть f - биективное отображение Х на У . Показать,что для подмножеств Е и F множества У имеют место соотношения1 - 1 ( Е u F)= 1 - 1 ( Е) u 1 - 1 ( F ) ; 1 - 1 (Е n F ) = 1 - 1 ( Е) n 1 - 1 ( F) ;1 - 1 ( Е) = 1 - 1 ( Е) .111§ 1 2. Эквивалентность и алгебраические законы§12.Э квивалентнос ть и алгебраические законыГоворят, что на множестве Х задано бинарное отношение R , если указано непустое подмножество R декартова квадрата этого множества. Еслипри этом ( х , у) Е R , то говорят, что элементы х и у связаны отношением R ,и обозначают символом xRy .Бинарное отношение R на множестве Х называется:• рефлексцвнъш, если xRx ,Е Х;• симмеrтфи'ЧН'Ьlм, если имеет :место импликация xRy => yRx;• транзитивнъLМ, если Иl\·tеет место импликация xRy , yRz => xRz .Бинарное отношение Е на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Если пара элементов х , у Е Х связана отношением эквивалентности, то говорят, чтоу. В конкретных случаяхх и у эквивалентн'Ьl, и обозначают символом хвместо этого символа :могут быть использованы и другие, например, х\/хf"Vх == у,у.Классом эквивалентности, порожденнъtм эле.м,ентомназываетсямножество{ х Е X lx f'V а } . Любой элемент класса эквивалентностиназывается представителем, этого класса.Т е о р е м а 12. 1 . Класс эквивалентностu порождаете.я любъLМсвоuм представителем.Т е о р е м а 12 .
2. Два класса эквивалентности либо не пересекаются, лuбо совпадают.Таким образом, любое отношение эквивалентности на множествеопределяет разбиение этого множества.11I ножество всех классов эквивалентности называется фактор-множеством множества Х по отношению эквивалентности Е и обозначаетсяа,cl (а) =символом Х/ & .Внутренним законом компози'Ции (алгебраи'Ческой опе]Jа'Цией) на множестве Х называется отображение* : х х х � х.(а, Ь) с,а * х,Ь : с.Тот факт, что=�записывается символически в видеВконкретных случаях вместо символа * используют символы + , - ,и др.Алгебраическая операция * на множестве Х называется:=• коммутативной, еслиЕ Х,* а,• ассо'Цuатuвной, еслиаЕ Х.Элемент е Е Х называется нейт]Jалънъtм элементом множества Хотносителъно алгебраи'Ческой опера'Ции если а Е Х :а*( * ЬЬ) * сЬ= а * (Ь\/а,* с),Ь\/а, Ь, с*,\/а * е = е * а = а.Пусть * - алгебраическая операция на :множестве Х , обладающая нейтральным элементом е .
Элемент называется симметри'ЧН'ЬlМ элементомдля элементаесли **=х,Т е о р е м а 12.3. Нейтралън'Ьlй эле.м,ент единствен.хЕхх1х'== х1хе.Т е о р е м а 1 2 .4. Симметри'ЧН'Ьtй эле.м,ент относите.;�ъно ассо'Цuативной алгебраи'Ческой опера'Ци'l.t единствен.Говорят,что алгебраическая операция* на множествеХ обладаетЬоб]Jатной опера'Цией, если для любых двух элементов а , Е Х уравненияхимеют единственное решение.иу==Пустьи - две алгебраические операции на множестве Х . Алгебр аи ческая операцияназывается дистрибутuвной справа относительноа * Ь * i* а * 2 Ь*iалгебраической операции * 2 , если(а * 2 Ь) * 1 с = (а * 1 с) * 2 (Ь * 1 с) , \/а,Ь, с==ЕХ;Глава III. Множества и отображения1 12дистрибутивной с.л ева, еслиа * 1 Ь *2 са * 1 Ь *2 а * 1 с ,Х;и дистрибутивной, если она дистрибутивна и справа, и слева.Пусть Х и - два множества.
Внешним законом компози'Ции на множестве Х называется отображение( )=() () Va,b,c EРРхх.х�Тот факт, что (а,х) � с , обозначается символом с = а х.Внешний закон композиции на множестве Х называется дистрибутивотносителъно внутреннего закона компози'Ции * в Х , еслиа(а * Ь) = аа * аЬ, Va E P , Va , b E X.Внешний закон композиции на множестве Х называется дистрибутивнъtмотносителъно внутреннего закона компози'Ции *' весли(а *' [З) а = аа * {За, Va,/3 Е Р , Va Е Х .Н'ЫМР,ЗАД АЧИ1 2 . 1 . Привести примеры бинарного отношения:а) рефлексивного, симметричного, но не транзитивного;б) рефлексивного, транзитивного, но не симметричного;в) симметричного, транзитивного, но не рефлексивного.1 2 .
2 . Найти ошибку в следующем "доказательстве" того , чторефлексивность бинарного отношения R вытекает из симметричности и транзитивности: "Так как R симметрично, то из xRy следует, что yRx. Так как R транзитивно, то из xRy и yRx сле,цует,что xRx , т.е. R рефлексивно."1 2 .
3 . Доказать , что любое разбиение множества определяетотношение эквивалентности на этом множестве .1 2 . 4 . Пусть f : Х � Х - отображение на некотором множестве Х . Какое условие необходимо и достаточно для того,чтобы бинарное отношение R, задаваемое правилом: xRy , еслиу = f(x) , былоа ) рефлексивным; б) симметричным; в) транзитивным .1 2 . 5 . Рассматривается бинарное отношение R на некотороммножестве населенных пунктов.
Два населенных пункта считаются связанными отношением R, если либо они совпадают, либомеж,цу ними установлено железнодорожное сообщение. Являетсяли R отношением эквивалентности?1 2 . 5 . 1 . Рассматривается бинарное отношение R на множестве всех жителей земного шара. Два человека считаются свя-§ 1 2. Эквивалентность и алгебраи ческие законы1 13занными отношением R , если у них есть общие знакомые. Является ли R отношением эквивалентности?1 2 . 5 . 2 . Рассматривается бинарное отношение R на множестве всех жителей земного шара. Два человека считаются связ анными отношением R , если они владеют одним и тем же языком .
Является ли R отношением эквивалентности?1 2 . 6 . На множестве вещественных чисел IR задано бинарноеотношение R по одному из следующих правил: x Ry, еслиа) х = у; б) х < у; в) х < у; г) х > у ; д) х > у .В каком из этих правил а)-д) бинарное отношение R рефлексивно?1 2 . 7. На множестве ненулевых вещественных чисел IR \ {О }задано бинарное отношение R по одному из следующих правил:xRy, еслиа) ху > О; б) х - у Е Z ; в) х /у Е Z .Для каждого из этих правил выяснить, является ли бинарноеотношение R рефлексивным , симметричным , транзитивным?Если R является отношением эквивалентности, то найти фактормножество (IR \ {О } ) / R .1 2 .8. На множестве упорядоченных пар вещественных чисел2IR. задано бинарное отношение R по одному из следующих правил : (x 1 , x 2 ) R (y 1 , y2 ) , если< , б) х 1 < У1 , в ) х 1 = У1 ,а) х 1 У 1{ х 2 < у2 ;[ х2 < у2 ;{ х2 = у2 ;д) х1 у 1 + х2 у2 > О ; е) ( х1 - х2 ) ( у1 - У2 ) > О .Для каждого из этих правил выяснить, является ли бинарноеотн ошение R рефлексивным, симметричным , транзитивным ?1 2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
