Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 3

Аналогично определяется проекция множества у на несколько осей: пр;, ~ )г=(пр;, ч о~пан)г) В частности, ' Знак Д будет обозначать конец доказательства теоремы, т.е, заменять оборот «что и требовалось доказатьм Если доказательство опущено или следует из предшествующего текста, то знак П будет ставиться непосредственно после формулировки теоремы. 1В если Р=А~ХА2Х...ХА,, то пр;,, У=А;,Х...ХА,, Отметим, что в общем случае пр~У вЂ” вовсе не обязательно прямое произведение; оно может быть его подмножеством, Пример 1.6.а. Проекция точки плоскости на 1-ю ось— это ее абсцисса (первая координата); проекция на 2-ю ось — ордината.

б. У= ((а,Ь,с(),(с,Ь,с(),(д,Ь,Ь)),пр,Р= (а,с,с(),прзР= =(Ь), при,зу=(Ь, а), (Ь, Ь)). 1.3. СООТВЕТСТВИЯ И ФУНКЦИИ Соответствия. Соответствием между множествами А и В называется подмножество 6:-АХВ. Если (а, Ь)ан6, то говорят, что Ь соответствует а при соответствии 6. Множество пр,6 называется областью определения соответствия, множество прь6 — областью значений соответствия. Если пр16=А, то соответствие называется всюду определенным или полностью определенным (в противном случае соответствие называется частичным); если пр,6=В, то соответствие называется сюръективным. Множество всех ЬенВ, соответствующих элементу аенА, называется образом а в В при соответствии 6. Множество всех а, которым соответствует Ь, называется прообразом Ь в А при соответствии 6. Если С~ пр,6, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества 0 для любого Выпр~б.

Соответствие 6 называется функциональным (или однозначным), если образом любого элемента из пр,6 является единственный элемент из пр,6. Соответствие 6 между А и В называется взаимно однозначным (иногда пишут «1-1- соответствие»), если оно всюду определено, сюръективно, функционально, и, кроме того, прообразом любого элемента из пр,6 является единственный элемент из пр,6. Пример 1.7, а. Круг 6 радиуса 1 с центром в точке (3.2) рис. 1.1), т.

е. множество пар действительных чисел х,у), удовлетворяющих соотношению (х — 3)'+ (д — 2)'(1, задает соответствие между )1 и )с (осью абсцисс и осью ординат). Образом числа 4 прн этом соответствии является единственное число 2, образом числа 3 является отрезок (1, 3] оси ординат; этот же отрезок (1, 3] является образом отрезка [2, 4] осн абсцисс, который, в свою очередь, служит прообразом числа 2.

Данное соответствие не является функциональным. Примером функционального соответствия меж- 19 ду действительными числами на том же рис. 1.1 служит дуга АВС. Еще раз напомним, что для задания соответствия надо указать не только множество 6, но и множества А и В, т. е. указать, подмножеством какого прямого произведения является 6, В данном примере тот же круг 6~ задает и дру- гое соответствие: между отрез- У ком [2, 4] и отрезком [1, 3]. При В этом по некоторым свойствам со- 5 ответствня 6,ыВз и 6~я[2, 4]р, О Я1, 3] отличаются: например, второе соответствие в отличие от первого всюду определено н сюръективно.

Учитывая эти соотношения, следовало бы опреде„ лять соответствие как тройку множеств (6, А, В), как это сделиРис. 1.1 но в [6]. Тогда не пришлось бы оговариваться, что один круг может задавать два соответствия; это и так было бы ясно из различия троек (6ь В, Й) и (6~,[2, 4], [1, 3]). Однако такие оговорки приходится делать редко; либо множества А и В ясны из контекста, либо различия в их выборе не влияют на исследуемые свойства соответствия. Поэтому «определение через тройку множеств» здесь использоваться не будет. б. Англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным (так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре'.

в. Позиция на шахматной доске представляет собой взаимно однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых имн полей. г. Различные Виды кодирования — кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и др. — являются соответствиями ' При этом остается в стороне вопрос (вообще говоря, законный), является ли множество английских слов (так же, как и русских) точно заданным множеством. 20 между кодируемыми обьектами и присваиваемыми им кодами.

Эти соответствия, как правило, обладают всеми свойствами взаимно однозначного соответствия, кроме, быть может, одного — сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. Отсутствие сюръективности означает, что не всякий код имеет смысл, т. е. соответствует какому- либо объекту. Например, кодирование телефонов г. Москвы семизначными номерами не сюръективно, так как некоторые семизначные номера не соответствуют никаким телефонам. д. Множество векторов вида (н, 2"-'), где аенУ, задает взаимно однозначное соответствие между множеством гтг натуральных чисел и множеством М степеней двойки. Взаимно однозначные соответствня и мощности множеств.

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

В качестве иллюстрации этого приема докажем важную теорему о числе подмножеств конечного множества. 'Теорема 1.2. Если для конечного множества А )А) =п, то число всех подмножеств А равно 2', т. е. 2~л'. Занумеруем элементы А номерами от 1 до а: А=(а,, а„..., а,) и рассмотрим множество В. двоичных векторов из нулей и единиц длины а. Каждому подмножеству А".л с=А поставим в соответствие вектор о=(оь оз, ..., оа) ыВ, следующим образом: ' Обращаем внимание читатели иа то, что в атом простом рассуждении оказываются существсннымн все четыре свойства взаимно одно.

значного соответствия. 21 О, если а;~А*1 п~ —— 1, если а; Я А*. Например, если А=(а, Ь, с, и', е), то подмножеству (а, с, Ы) соответствует вектор (1, О, 1, 1, 0), а подмножеству (Ь) соответствует вектор (О, 1, О, О, 0). Пустому подмножеству любого А соответствует вектор нз одних нулей, а самому А — вектор из одних единиц. Очевидно, что установленное соответствие между многкеством всех подмножеств А и двоичнымн векторами длины и является взаимно однозначным и число подмножеств А равно (В„(.

А так как В„является прямым произведением и двухэлементных множеств (О, Ц, то в силу следствия из теоремы 1.1 ~ В,~ =2". П Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие. Для конечных множеств это утверждение доказывается, что и бы. ло сделано ранее, Для бесконечных множеств оно является определением равномощности.

Множества, равномощные У, называются счетными. Соответствие, установленное в примере 1.7, д, показывает, что множество сИ,л счетно. Вообще любое бесконечное подмножество У счетно. Действительно, пусть У'~У. Выберем в У' наименьший элемент и обозначим его а,; в У" (и,) выберем наименьший элемент и обозначим его и,; наименьший элемент У"~,(пь пД обозначим пз и т. д. Поскольку для всякого натурального числа имеется лишь конечное множество меньших натуральных чисел, то любой элемент № рано или поздно получит свой номер. Эта нумерация, т. е, соответствие (пь 1), и есть взаимно однозначное соответствие между У' и У.

Множество У' счетно, Нумерацию № можно устроить следующим образом. Разобьем У' на классы. К первому классу У-', отнесем все пары чисел с минимальной суммой. Такая пара всегда одна: (1,1). Ко второму классу У,' отнесем все пары чисел с суммой 3: У., '=((1, 2), (2, Ц). В общем случае У =((а, Ь) ~а+Ь=1-(- Ц.

Каждый класс У,"., содержит ровно 1 пар. Упорядочим теперь классы по возрастанию индексов 1, а пары внутри класса — по возрастанию первого элемента н занумеруем получившуюся последовательность пар номерами 1, 2, 3... Легко видеть, что если а+Ь=1+1, то пара (а, Ь) получит номер 1+2+...+(1 — Ц+ +а. Эта нумерация и доказывает счетность №, из которой, в свою очередь, непосредственно следует счетность множества Р положительных рациональных чисел, т.

е. дробей вида а/Ь, где а и Ь вЂ” натуральные числа'. Аналогично доказывается счетность ЛР и вообще Уз для любого натурального Й. Нетрудно понять, что объединение конечного числа счетных множеств Мь Мз, ..., Мз счетно. Действительно, пере- нумеруем сначала все первые элементы множеств, затем все вторые и т. д. Объедннение счетного множества конечных множеств также счетно (сначала нумеруем все элементы первого множества, затем все элементы второго множества и т. д.). Из последнего утверждения следует, что множество всех слов в любом конечном алфавите счетно. Менее очевидно, что счетно и объединение счетного множества счетных множеств.