Том 1 (1113039), страница 16
Текст из файла (страница 16)
Доказать, что а) Х х (Е(д Е) = (Х х Е) (д (Х х Р); б) Х х (Е Г1 Е) = (Х х Е) Г1 (Х х Р); в) (Х Г1 У) х (Е Г1 Е) = (Х х Е) Г( (У х Е). 10.11. Пусть А — конечное множество, состоящее из и элементов. Найти число всех подмножеств этого множества (включая пустое множество и само множество А). 10.12. Пусть А — конечное множество, состоящее из и элементов. Найти число всех подмножеств этого множества, состоящих из т элементов. 10.13.
Обозначим через т(А) число элементов множества А. Доказать, что для любых конечных множеств А, В, С выполнены соотношения: а) т(А 1 В) = т(А) — т(А Г1 В); б) т(А (д В) = т(А) + т(В) — т(А Г1 В); в) т(А(зВ(зС) = т(А)+т(В)+т(С) — т(АГ1В) — т(АГ1С)— — т(В Г1 С) + т(А Г1 В Г1 С). й11.
Отображения Пусть Х, У вЂ” два множества. Отображением 1" множества Х во множество У называется закон, посредством которого каждому элементу х е Х ставится в соответствие однозначно определенный элемент у Е У. Символически отображение записывается в виде 1": Х ч У. Запись у = 1"(х) или х ~- ° у означает, что элемент х при отображении у переходит в элемент у. Полным прообразом элемента у е У называется множество (у) = (х е Х ~ у(х) = у).
Образом отображен л у" называется множество 1(Х) = (у Е У~ Их Е Х: у = у(х)). Отображение з": Х ч У называется: ° иньективным, если из того, что хг 4 хг, следует, что Г(хг) ~ 1(хг), или, другими словами, если уравнение 1(х) = у (11.1) при любом у е У имеет не более одного решения; ° сюрьеьшивным или ошобразкением на, если у(Х) = У, или, другими словами, если уравнение (11.1) при любом у е У имеет хоти бы одно решение; ° биективныль или взаимно однозначным, если оно и инъективно, и сюръективно, или, другими словами, если уравнение (11.1) при любом у Е У имеет,и притом единственное, решение.
107 311. Отображения Два отображения (: Х вЂ” ~ У и д: Х У называются ровнььии, если 1(х) = д(х), 'Фх й Х. Тозюдественным 7единичным) отоброзюением на множестве Х называется отображение ех: Х вЂ” ~ Х, которое переводит каждый элемент х й Х в себя. Биективное отображение множества М на себя называется перестановкой (подстоновкой) множества М. Если множество М состоит из и элементов, то его элементы можно занумеровать числами 1,2,...,и и тогда каждую перестановку з можно записать в виде таблицы (а~ аз ... аь ... а ) ' (11.2) в которой под каждым номером й указывается номер аь того элемента, ко- торый является образом элемента с номером 1с.
Очевидно, 1) а, й (1,2,...,п), 2) а, ~ а, при 1 ~ у, так что а = (ам аз,...,а„) — перестановка (34) из чисел 1,2,..., и. Заметим, что термин пперестановка" используется н как название отоб- ражения (11.2), и как фиксированное расположение чисел 1, 2,..., п в опре- деленном порядке а. Это естественно, так как л~ежеу отображениями (11.2) и упорядочением а чисел 1,2,...,и, очевидно, существует взаимно одно- значное соответствие. Если в таблице (11,2) поменять местами столбцы, то получится другая запись той же перестановки ж (А дз д-) (11.3) 1 2 3 4 3 1 4 3 2 — ~ 4 1 2 Поэтому 2 3 4 ) где б = (А,))г,.,д ) и э = (ум уз,..., у ) — перестановки из первых и натуральных чисел.
Перестановка (11.2) называется четной, если а — четная перестановка, т.е. если о(а) — четно. В записи (11.3) перестановка з четная тогда и только тогда, когда о(В) + о( у) — четно (см. ниже задачу 11.16). Произведением (суперпозицией или композицией) отображений д; Х У и (: У вЂ” ~ Я называется отображение (д: Х вЂ” ~ Я, определенное правилом (д(х) = 7(д(х)), Чх й Х. Пример 11.1.
Найти произведения з1 и зз перестановок з=(2 4 1 3)из=(3 4 2 1). Р е ш е н и е. Произведение перестановок в данной задаче является супер- позицией двух отображений множества М = (1,2,3,4) на себя. Согласно обозначениям, принятым в определении произведения отображений, в перестановке зг первой выполняется перестановка д а второй — перестановка з. Суперпозицию перестановок 1и з наглядно представить следующей схемой Глава 111. Множества и отображения 108 Аналогично г 1 1 — ~ 2 — ~ 4 2 4 1 3 1 ч 3 4 3 — ~ 2 1г=(4 1 3 2). 1 2 3 4 1 '1=ех, О '=ею Теорема 11.2.
Если д; Х ч У, 1: У ч Х и 1д = ех, то д иньективно, а 1 сюрьективно. Теореме 11.3 (критерий обратимости). Отображение обратимо тогда и только тогда, когда оно баективно. Т е о р е м а 11.4. Обратимые отображения обладают следующими свойствами: 1) обратное отображение единственно; д) произведение обратимых отобраэкений обратимо, при этом (1дГ' =д '1 '. ЗАДАЧИ 11.1. Пусть Кч — множество всех положительных вещественных чисел и пусть каждому числу а Е К поставлено в соответствие число х такое, что хй = [а[. Определяет ли это правило отображение а) Ке — К; б) К+ — Ке; в) К вЂ” К+? Если да, то будет ли оно сюръективным, инъективным, биективным? 11.2.
Определяет ли правило 1(х) = э(их отображение а) 1':К вЂ” К; в) 1:К вЂ” -[ — 1;1]; б) (: [ — и/2;и/2] — [ — 1; Ц; г) (: Ке — Ке? В каких иэ случаев а)-г) это правило определяет биективное отображение? 11.3. Пусть каждому подмножеству множества А поставлена в соответствие его характеристическая функция. Будет ли это Теорема 11.1. Произведение отображений обладает следующими свойствами: 11 (ех = 1; е~ 1 = 1 для любого отображения (; Х ч У; д) произведение отображений ассоциативно, т.е. если 6: Х ч У, д: У - Е, 1: Е - и, 1(да) = (1д)А д) произведение иньектпивных (сюрьекгпивных, биективн х) отображений иньективно (соотвегпсгпвенно сюрьектпивно, биективно). Пусть 1: Х вЂ” ~ У.
Отображение ( г: У Х называется обратным к отображению 1, если ~П. Отображения 109 биективным отображением множества всех подмножеств множества А на множество функций, принимающих значения О и 1? 11.4. Отображение 1: Х вЂ” У ставит в соответствие паре вещественных чисел а) их сумму; в) их произведение; б) их разность; г) их частное. Для каждого из случаев а) — г) указать подходящие множества Х и У. 11.5.
Является ли отображением И х И вЂ” И правило, которое паре чисел а, о е И ставит в соответствие частное а/а? 11.6. Пусть Х вЂ” множество всех невырожденных матриц иго порядка. Является ли отображением Х х Х вЂ” Х правило, которое любой паре матриц из Х ставит в соответствие а) их сумму; б) их произведение? 11.7. Пусть Š— множество, состоящее из и элементов. Установить биективное отображение множества А всех отображений Е во множество (О; Ц на множество В всех подмножеств множества Е.
11.8. Пусть Е, Š— подмножества множества Х и 1": Х вЂ” У. Показать, что: а) У(ЕОЕ) = ~(Е) 0~(Е); б) Г(ЕП Г) С ДЕ) О Г(Г). Что изменится в этих соотношениях, если ~ биективно? 11.9. Пусть Е и à — конечные множества, состоящие их т и и элементов соответственно. Найти число всех отображений Е в Г. 11.10. Пусть Е и Š— конечные множества, состоящие из т н и элементов соответственно.
Показать, что; а) для существования инъективного отображения Е в Г необходимо и достаточно, чтобы т ( и; б) число инъективных отображений Е в Г равно п(п — 1)... (и — т+ 1). 11.11. Пусть Е и à — конечные множества, состоящие из т и и элементов соответственно. Показать, что: а) для существования сюръективного отображения Е на Р необходимо и достаточно, чтобы т > п; б) число сюръективных отображений Е на Г равно п~ — п(п — 1)т +...
+ ( — 1)"Сь(п — ь)~л +... + ( — 1)а 'Сп '. 11.12. Пусть Е и Š— конечные множества, состоящие из т и и элементов соответственно. Показать, что: Глава 1П. Множества и отображения 110 а) для существования биективного отображения Е на Е необходимо и достаточно, чтобы 2п = п; 6) число биективных отображений Е на Е равно пй 11.13. Доказать, что если множество Х бесконечно, а его подмножество У конечно, то существует биективное отображение Х 1 У вЂ” Х. 11.14.
Для отображения 1: Х вЂ” У отображение д: Х вЂ” ~ У называется левым (соответственно правьм) обраглннлц если д1' = ех (соответственно 1д = еу). Доказать, что: а) отображение 1 инъективно в том и только том случае, если оно обладает левым обратным; б) отображение ~ сюръективно в том и только том случае, если оно обладает правым обратным. 11.15. Найти произведение перестановок: 3421 1423 ' ) 1423 4321 5 6 4 2 3 1 3 2 5 1 6 4 в указанном и обратном порядке 11.16. Доказать, что при записи перестановки ~ 1 <11 пг с"и 1 Ма /1 2 ...п1 в виде ~ ' ' ' ( общее число инверсий а( г) в перестановке Ь-12" У( '71,'уг,,'уп и сумма 1г(а) + о-(13) имеют одинаковую четность. 11.17.
Пусть 1". — биективное отображение Х на У'. Показать, что для подмножеств Е и Е множества У имеют место соотно- щения ~-1(Е и Е) = ~-'(Е) и ~-'(Е); ~-1(Е г1 Е) = ~-'(Е) г1 ~-1(Е); У '~Е) = 1-'(Е) В12. Эквивалентность и алгебраические законы ~12. Эквивалентность и алгебраические законы Говорят, что на множестве Х задано бинарное отношение И, если ука- зано непустое подмножество Е декартова квадрата этого множества. Если при этом (х, у) Е Е, то говорят, что элементы х и у связаны отношениелг те, и обозначают символом х~у.
Бинарное отношение Я на множестве Х называется; ° рефлексценым, если х1сх, эх Е Х; ° симметричным, если имеет место нмплнкацня хну ~ уЕх; ° транзитиеньллл если имеет хлеста импликация хну, утех ~ хЯ». Бинарное отношение Е на множестве Х называется отношением экви- валентности, если оно рефлексивно, симметрично и транзитивно. Если па- ра элементов х,у е Х связана отношением эквивалентности, то говорят,что х и у эквивалентны, и обозначают символом х у. В конкретных случаях вместо этого символа могут быть использованы и другие, например, х = у, х = — у. Классам экеиеалентностпи, порожденным элементом а, называется ллножество с1 (а) = (х е Х)х а).
Любой элемент класса эквивалентности называется представителем этого класса. Творе м а 12.1. Класс экеиеалентности порождаетасл любым своим представителем. Теорема 12.2. Деа класса эквивалентности либо не пересекают- сл, либо совпадают. Таким образом, любое отношение эквивалентности на множестве определяет разбиение этого множества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
