Спирина, М.С. Дискретная математика

Говорят, что между двумя множествами А и В установлено взаимно-однозначное со­ ответствие / , если элементы этих множеств можно представить в виде пар (я„ Ьк), для которых выполняются два условия: • Va,€ АЗЬке В так, что / (я ,) = bk; V 6 ye € B3a , t А так, что / (я , ) = Ь/. все элементы множеств попали хотя бы в одну из пар; • каждый элемент я, и Ь, попал только в одну из пар. Если между элементами множеств уста­ новлено взаимно-однозначное соответствие, то эти множества имеют одинаковое количество элементов. Гово­ рят, что они равносильны, равномощны, или эквивалентны. На рис. 1.7 показаны примеры прямого и обратного биективного ото­ бражения. Рассмотрим примеры отображений. 1. Отображение у: я -> я / 2, где я е Z, является биекцией мно­ жества Z целых чисел на некоторое множество В. Табличное зада­ ние такой биекции можно представить в виде табл. 1.3. Из табл. 1.3 видно, что каждому элементу множества Z ставит­ ся в соответствие единственный элемент множества В. И наобо­ рот, каждому элементу множества В можно поставить в соответ­ ствие единственный элемент из Z. Обратное отображение можно представить аналитически: у 1: я -> 2 я и таблично, поменяв места­ ми строки в таблице. 2. Каждому действительному числу поставим в соответствие его квадрат. Отображение х -э х 2 не является взаимно-однозначным соответствием, так как для любого образа у - х 2 можно найти два прообраза в области определения: х =+Jy и х = -у[у. 3. Англо-русский словарь устанавливает соответствие между множествами слов английского и русского языков. Такое соответ­ ствие не является однозначным, так как каждому английскому понятию соответствуют различные варианты перевода на русский язык, и наоборот. 4. Различные виды кодирования (азбука Морзе, представление чисел в различных системах счисления, шифрованные сообще- Рис. 1.6. График непре­ рывного биективного отображения у =f(x) Т а б л и ц а 1.3 Табличное задание биекции у: а -> в/2 X -2 -1 0 1 2 у(х) -1 -0,5 0 0,5 1 24