XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Но упорядоченную пару можно определить и как множество, полагая, что упорядоченная пара (а, Ь) есть неупорядоченная пара Ца),(а,ЬЦ, включающая в себя одноэлементное множество (а) и неупорядоченную пару (а, 6). При а = Ь получаем (а, а) = ((аЦ. Такое определение не изменит сути понятия, но тогда следует не определять явно равенство упорядоченных пар, а доказывать теорему о равенстве упорядоченных пар как определенного вида множеств.

Простейший и важнейший пример использования упорядоченных пар дает аналитическая геометрия [П1]. Если на плоскости введена некоторал прямоугольная спстиема координат, то каждая точка плоскости однозначно задается упорядоченной парой действительных чисел — коордипашамо этой ~вочки. Ни у кого не возникает сомнений в том, что порядок, в котором перечисляются коордвнаты точки, является существенным: точка, заданная координатами (1, 3), совсем не то же самое, что точка с координатами (3, 1).

К2. Кортеж. декартово произведение 39 Обобщением понятия упорядоченной пары является у«орядоченныб тв-набор', нли коршеж. В отличие от конечного множества (ам..., а„) кортеж (аь ..., а„) на множествах Ам ..., А„характеризуется не только входящими в него элементами а1 Е Ам ..., ан е А„, но и порядком, в котором они перечисляются. Как и для упорядоченных пар, роль порядка в кортеже фиксируется определением равенства кортежей. Определение 1.2.

Два кортежа (ам ..., а„) и (Ьм ..., 6„) на множествах Ам ..., А„равны, если а; = о;, в =1, «. Число «называется длиной коршежа (или раэмерносшью корт«ежа), а элемент а; — т-й «роекиией (компонентой) коршежа. Для двух кортежей одинаковой размерности их компоненты с одинаковыми номерами называют одноименными ком«онентпами. Определение 1.2 равенства кортежей можно переформулировать так: два кортежа одинаковой размерности равны тогда и только тогда, когда их одноименные компоненты совпадают. Простейшим примером кортежа является ари2тлентический вектор. Определение 1.3. Множество всех кортежей длины « на множествах А1, ..., А„называют декарт«оным («рямым) «роиэведением множестпв Ам ..., А„и обозначают Ат х ... х Ан.

Таким образом, Ат х ... х А„= ((ам ..., а ): ат е А|, ..., а, Е Ан) . Если все множества А;, т = 1,«, равны между собой, то указанное декартово произведение называют «-й декаршовот1 сше«енью множестпва А и обозначают А". В частности, при « = 2 получаем декартпов квадрат а при « = 3 — декартпов куб множества А. 'Говорвт также: рнорадоченноа «-на (напрнмер, у~орвдоченнвв тройка, четверка, питерка н т.д.).

1. МНОЖЕСТВА И ОТНОШЕНИЯ По определению полагают, что первая декартова степень любого множества А есть само множество А, т.е. А1 = А. Декартово произведение имеет следующие свойства: 1) А х (В 0 С) = (А х В) 0 (А х С)," 2) А х (В й С) = (А х В) П (А х С); 3)АхИ=ахА=И. Эти свойства нетрудно доказать методом двух включений. Докажем, например, первое тождество. Если (х, у) Е А х (В 0 0 С), то я Е А и р Е В 0 С. Из того, что у Е В 0 С, следует уеВ или уЕС. Если уЕВ, то (х, р)еАхВ, аеслиуеС, то (я,р)еАхС. Итак, (х,у)еАхВ или (я,у)еАхС, т.е. (х, р) Е (А х В) 0 (А х С). Следовательно, А х (В 0 С) С С (А х В) 0 (А х С). Доказательство обратного включения аналогично. Обратим внимание на последнее из записанных вьппе трех тождеств.

Из него вытекает, что пустое множество при построении декартовых произведений множеств играет ту же роль, что и нуль при умножении чисел. Докажем справедливость этого тождества. В самом деле, множество И х А (для любого А) есть множество всех упорядоченных пар (х, у), таких, что хе Я и уб А. Но таких элементов и, что хе Я, не существует, и, следовательно, упорядоченных пар (х, р), принадлежащих декартову произведению И х А, не существует, т.е. о х А = о. Аналогично доказывается, что и А х о = ю. 1.3. Соответствия и бинарные отношения Отображение ~ из множества А в множество В считается заданным, если каждому элементу х е А сопоставлен единственный элемент р Е В.

Отображение ~ из множества, А в множество В обозначают записью ~: А -+ В. Элемент у Е В, который отображением у сопоставляется элементу я е А, называют образом элемента я при отпображении ~ и обозначают Дж). КЗ. Соответствия и бяллрлые отиошеввл 41 Каждое отображение однозначно определяет множество упорядоченных иар ((х, у): х Е А, у =,1 (х)), являющееся подмножеством декартова произведения А х В множества А на множество В и называемое ерафиком отображения у. Наоборот, пусть в декартовом проюведении А х В задано такое подмножество ~, что: 1) для любого х Е А существует у Е В, для которого (х, р) Е у; 2) для любых двух пар (х, р) и (х', р') множества ~ из равенства х = х' следует равенство р = р'. Тогда множество у единственным образом определяет некоторое отображение из А в В.

Это отображение, обозначаемое также ~, элементу х Е А сопоставляет элемент у Е В, удовлетворяющий условию (х, у) Е у. Таким образом, мы можем отождествить отображения с их графиками и считать, что отображение есть подмножество декартова произведения. Отображение у множества А в себя называют тиождестпеенным, если у(х) = х при всех х ю А. В общем случае для отображения,~: А -+ В может существовать несколько различных элементов множества А, образы которых совпадают.

Множество всех элементов х е А, для которых у(х) = уе, называют прообразом элемента уе Е В ири отображении У. Так, прообраз числа а, ~а~ < 1, при отображении у = вшх есть множество всех решений уравнения вшх = а, т.е. множество 1х: х = агсвша+ 2ки, и Е Е) 0 1х: х = и — агсвша+ 2ки, и Е Е).

Прообраз элемента уе Е В может быть пустым множеством. Это имеет место, например, для числа 2 при отображении у =вшх. Множество всех у Е В, таких, что найдется х Е А, для которого р = ~(х), называют областпью значений отпображения У. Область значений отображения ~ будем обозначать В(у). Отображение у: А -~ В называют иньектпивным (инъекцией), если каждый элемент ю области его значений имеет единственный прообраз, т.е. ю Дх1) = у(хз) следует х1 = хз.

42 1. МНОЖЕСТВА И ОТНОШЕНИЯ Отображение /: А ~ В называют сюръентпиеным (сюрьекциеб), если его область значений совпадает со всем множеством В. Сюръективное отображение из А в В называют также отпобраэтсением множества А на множество В. Отображение /: А -+ В называют биектпиенььн (биением), если оно одновременно инъективно и сюръектиано.

Таким образом, если отображение /: А -тВ биективно, то каждому элементу множества А отвечает единственный элемент множества В и наоборот. Тогда говорят, что множества А и В находятся между собой во взаимно однозначном соотпветпстпвии. Биекцию множества А на себя называют аетпоморфизмом мнозтсестпва А. Используют также термин' „подстановка множества". Пример 1.2. а. Отображение, заданное равенством и(п) = = п+1, есть, как нетрудно показать, биекция множества натуральных чисел 1Ч на его подмножество ге ~ (Ц. б. Отображение ьс и ~-+ 2п есть биекция множества всех натуральных чисел на множество всех четных натуральных чисел. в.

Любы показатпельнал функиил у = а*, а > О, есть биекция множества К всех действительных чисел на множество Й+ всех положительных действительных чисел. г. Функцин у = атеях есть биекция множества Й на интервал ( — тг/2, тг/2). д. Поворот окружности на заданный угол ст, т.е. отображение, сопоставляющее каждой точке окружности точку, в которую она перейдет при повороте всей окружности вокруг ее центра на угол а, есть автоморфиэм множества точек окружности. ) Пусть задано отображение /: А -+ В и С С А — некоторое множество. Множество 1(С) элементов 11 Е В, таких, что Иногда этот терман употре0люот только длл азтоморфнзма конечного множества, 1.3.

Соответствие и Оввервые отвошеиие 43 у = 1(х), х Е С, называют образом множестпеа С при отпображении у'. Например, при отображении у = егпх отрезок [О, 1) является образом множества (отрезка) [О, тг), равно как и любого объединения отрезков вида [2тгй, (2й+ 1)я] (для произвольного целого й). При й = 0 это можно записать следующим образом: егп([0, тг]) = [О, 1]. Заметим, что для любого отображения 1: А -+ В образ 1(А) всего множества А есть область значений данного отобраДля произвольного множества Р С В множество всех элементов х Е А, таких, что Дх) Е Р, называют прообразом множестпеа Р при отображении 1.

Например, для любого действительного числа а Е [О, 1) множество, которое является объединением всех отрезков вида [агсвша+ 2тгй, тг — агсвша+ 2тгй), й Е Е, есть прообраз отрезка [а, 1] при отображении у = е!пх. Прообраз области значений произвольного отображения 1: А -т В совпадает со всем множеством А. Множество всех отображений из А в В будем обозначать как В~ Понятие отображения можно обобщить. Обобщение может проходить по двум позициям. Во-первых, можно отказаться от полной определенности отображения, полагая, что образ определен не для каждого элемента множества А, а для некоторых элементов этого множества.

Тогда придем к понятию частпичноео отпображенил. При этом подмножество всех элементов А, для которых определен образ, называют областпью определения данного частпичноэо отпображения. Многие элементарные функции являются частичными отображениями множества Ж всех действительных чисел в себя. Например, функция у = Сб х есть частичное отображение с областью определения Й~ (х: х = -+ тгй,й Е Е~. Во-вторых, можно отказаться от однозначности отображения, полагая, что данному х е А сопоставлен не один, а несколь- Е МНОЖЕСТВА И ОТНОШЕНИЯ ко образов (множество образов) в множестве В. В этом случае говорят, что задано соотпветпстпвие* из множества А в множество В.

Примером могут служить обратные тригонометрические функции: скажем, „большой" арксинус [Ц, сопоставляющий каждому х Е Й множество всех таких чисел у, что вшу = х, т.е. множество, являющееся прообразом элемента х при отображении, определяемом графиком функции у = в!пх. Если задано соответствие р из А в В, будем использовать обозначение р(х) по аналогии с обозначением Дх) для отображений, понимая при этом, что р(х) есть уже не элемент множества В, а его подмножество. Аналогично графику отображения можно определить граутии соотпеетпстпвил р из множества А в множество В как множество Ср упорядоченных пар (х,у), таких, что х Е А, у Е В и элементы х, у связаны соответствием р, т.е. у Е р(х). Указанное множество Ср упорядоченных пар есть подмножество декартова произведения А х В.

Обратно, фиксируя на декартовом произведении А х В какое-либо подмножество С, мы тем самым однозначно определяем некоторое соответствие рс из А в В, а именно рс(х) = = (у: у Е В Л (х,у) Е С). Нетрудно заметить, что графиком соответствия рс будет как раз множество С, а соответствием, отвечающим графику Ср, будет р. Поэтому можно отождествить соответствие с его графиком и считать, что соответствие из множества А в множество В есть некоторое подмножество р декартова произведения А х В, т.е. р С А х В.

В частности, при р = Я получаем пустпое соотпеетпстпвие, а при р, совпадающем со всем указанным декартовым произведением, 1— универсальное соотттветпстпвие. При этом будем писать (х, у) Е р для упорядоченных пар, связанных соответствием р. Используют также термины „частичное мультиотобраиение", „частичная многозначная функция".

Характеристики

Список файлов книги