Что такое взаимная однозначность (функции)?
Если у вас есть два множества Х и Y, и вы начинаете сопоставлять элементам из X элементы из Y (каждому элементу из X ставите в соответствие какой-нибудь один элемент из Y), то вы тем самым устанавливаете, как говорят, отображение из X в Y. Если вы хорошо постарались, то и ваше отображение может оказаться достаточно хорошим. Например, может оказаться так, что разным элементам из X вы сопоставили разные элементы из Y. В таком случае ваше отображение называется инъективным отображением (или инъекцией) X в Y. Если же вам удалось сделать так, что каждому элементу из Y соответствует какой-нибудь элемент из X, то вы установили сюръективное отображение (или сюръекцию) из Х на Y (обратите внимание на предлоги: инъекция — X в Y, сюръекция — X на Y).
Собственно, биекцией, или взаимно-однозначным соответствием, будет являться отображение, которое одновременно сюръективно и инъективно, т. е. одновременно является и сюръекцией и инъекцией. Это означает, что разным элементам из Х вы сопоставляете разные элементы из Y, при этом каждому элементу из Y вы сопоставляете какой-нибудь элемент из X. В сумме это и значит, что каждому элементу из X ставится в соответствие ровно один элемент из Y.
Биективность взаимно-однозначного отображения позволяет ставить в соответствие элементам из Y элементы из X по обратному закону (т. е. если вы какому-то элементу x1 из X поставили в соответствие элемент y1 из Y, то при обратном отображении вы элементу y1 сопоставите элемент x1). Проблем при этом не возникнет: сюръективность гарантирует нам, что каждому элементу из Y мы сможем что-нибудь сопоставить, а инъективность — что нам не придётся ставить два элемента из X одному элементу из Y (иначе наше сопоставление не будет однозначным). В итоге получается новое отображение, которое называют обратным отображением. Оно тоже будет биекцией.
В теории множеств есть такая характеристика множества — его мощность. Это что-то вроде количества элементов в нём. Понятно, что если вы возьмёте два множества, между которыми вы сумели установить взаимно-однозначное соответствие, то количество элементов в них одинаково (если множества конечны, иначе разговор несколько усложняется). Такие множества теория множеств практически не различает между собой, потому как вы можете просто заменить элементы одного множества элементами другого, что теорию множеств абсолютно не интересует.
Отображение во множество, отображение на множество, взаимно однозначное отображение
Пусть/есть отображение множества Е во множество F. Выражение «/ определено на Е» означает, что каждому х, принадлежащему Е, соответствует при отображении/некоторое у, принадлежащее F. Выражение «/ есть отображение Е в F» только это и означает, т.е. каждому х из Е соответствует у из F.
Но множество значений Дх) не обязано включать в себя все элементы множества F. Так, функция «sin» есть отображение множества R действительных чисел в R, но множество значений sin(x) состоит из действительных чисел у, удовлетворяющих условиям —1 фх2) всегда/(х!) ^ Дхг) в F.
Отображения
Вернемся к началу данного параграфа. Там мы начинали с рассмотрения соответствий между двумя множествами, которые по существу являются бинарными отношениями. Выделим теперь среди этих соответствий такие, когда для любого элемента первого множества найдется единственный элемент во втором множестве, который ему соответствует, т.е. находится с ним в данном отношении. Такие соответствия между двумя множествами в математике называются отображениями.
Определение 2.14. Отображением / из множества X в множество Y называется такое бинарное отношение между данными множествами, что для любого элемента хе X найдется единственный элемент у е У, такой что
Элемент у называют образом элемента х, а элемент х — прообразом элемента у.
Изобразить отображение из множества X в множество Y можно с помощью ориентированного графа (рис. 2.12).
Рис. 2.12. Отображение
На самом деле отображение имеет другое, хорошо вам известное название — функция. В школе вы рассматривали и общее понятие функции, и различные виды функций. Однако вы не знали, что функция (или отображение) — это особый вид бинарного отношения.
На рис. 2.13 показаны разные виды отображений.
Рис. 2.13. Различные виды отображений
Каждое из приведенных отображений (функций) имеет определение и свое название. О них вы подробнее узнаете, когда будете изучать функции. Нас же будет интересовать последнее отображение, которое носит название взаимно-однозначного отображения, или взаимно-однозначного соответствия. Его особенным свойством является то, что каждому элементу х из X соответствует единственный образ (элемент у из У: у = = h(x)) и для каждого элемента у из Y есть единственный его прообраз х е е X: (h(x) = у).
Обратите внимание, что в случае взаимно-однозначного отображения множество X отображается на множество У, так как при данном отображении все элементы множества У являются образами элементов множества X.
Используя взаимно-однозначное отображение, сравнивают множества. Мы пока не касались вопроса о сравнении двух множеств. Можно предположить, что для сравнения двух множеств нужно знать, сколько элементов в каждом. То, в котором больше элементов, и будет «больше». Но этот принцип сравнения, оказывается, можно применить только для конечных множеств. А что делать, если множества — бесконечные?
Для этого существует понятие «мощность множества». Мощность бесконечного множества — это аналог понятия «число элементов» для конечного.
Когда же два бесконечных множества имеют одинаковую мощность?
Определение 2.15. Множества А и В имеют одинаковую мощность
(или являются равномощными), если существует взаимно-однозначное отображение множества А на множество В.
Среди всех бесконечных множеств можно выделить те, что равномощны множеству натуральных чисел. Такие множества называются счетными.
Для того чтобы доказать, что некоторое бесконечное множество равно- мощно множеству натуральных чисел (т.е. счетно), нужно придумать правило, чтобы занумеровать все элементы данного множества, это и будет означать установление взаимно-однозначного соответствия с множеством натуральных чисел.
Приведем несколько примеров счетных множеств.
Докажем, что множество нечетных натуральных чисел счетно.
Запишем это множество: <1, 3, 5, 7,2п — 1,Занумеруем элементы этого множества следующим образом: 1 —> 1 (№ 1); 3 —> 2 (№ 2); 5 —» 3 (№ 3); . . Любому нечетному числу вида 2п — 1 будет соответствовать номер п. Другими словами, мы нашли правило, по которому занумерован! все нечетные натуральные числа. Это означает, что это множество счетно.
Очевидно (а почему?), что множество всех натуральных чисел — счетно. Множество нечетных натуральных чисел является его несобственным подмножеством. Казалось бы, мощность его должна быть меньше, чем мощность множества натуральных чисел. Но это не так. Мы только что доказали, что они равномощны.
Докажем, что множество всех целых чисел счетно. Решение
Запишем множество целых чисел в две строчки:
Будем нумеровать их в том порядке, как показывают стрелки: 0 — № 1; -1 — № 2; 1 — № 3; -2 — № 4; 2 — № 5. В результате все неотрицательные числа получат нечетные номера, а отрицательные — четные. Таким образом мы занумеруем все целые числа, а значит, получим то, что и требовалось доказать.
Докажем, что множество рациональных чисел счетно.
Напомним, что любое рациональное число можно представить в виде дроби. Запишем сначала все положительные рациональные числа в таблицу:
- 1
- 1
- 2
- 1
- 3
- 1
- 4
- 1
Выделим в таблице квадраты, показанные жирными линиями, и будем нумеровать числа в каждом квадрате последовательно но следующим правилам.
1. Если одно число в таблице встречается несколько раз (например, у, —. ), то
его занумеровывают только при первой встрече, дальше пропускают.
- 2. В каждом квадрате числа можно нумеровать в любом порядке, не пропуская ни одного, кроме равных уже ранее встречавшимся.
- 3. После нумерации чисел в любом квадрате (начиная с первого 2×2) переходят к нумерации в следующем, который содержит предыдущий.
Используя эти правила, мы будем нумеровать числа следующим образом. В пер-
- 1 2 1 2 вом квадрате — получит № 1; — — № 2; — — № 3; — — пропускаем.
- 1 2 3 3 3
Во втором квадрате — — № 4; — — № 5; — — пропускаем; — — № 6; — — № 7 и т.д.
Таким образом, все положительные рациональные числа можно занумеровать натуральными числами. Теперь нужно добавить отрицательные рациональные числа и число 0. Для этого можно составить аналогичную таблицу для отрицательных рациональных чисел. Тогда 0 можно занумеровать № 1, остальные положительные рациональные числа занумеровать нечетными натуральными числами начиная с 3. Отрицательные рациональные числа занумеровывают четными натуральными числами.
Мы показали, что множество рациональных чисел счетно.
Кроме счетных бесконечных множеств существуют и несчетные множества. Мощность этих множеств может быть различной.
Например, можно доказать, что множество действительных чисел М не является счетным [1] .
Если какое-то множество равномощно множеству действительных чисел, то говорят, что оно имеет мощность континуума. Множество действительных чисел на промежутке от 0 до 1 имеет мощность континуума.
Вообще вопрос о мощности множеств очень сложный. Можно себе поставить несколько вопросов. Бывают ли бесконечные множества, мощность которых отлична от континуума? Является ли мощность континуума самой большой? Можно ли найти множество самой большой мощности? Какова мощность множества всех звезд космического пространства?
Постарайтесь самостоятельно найти информацию для ответа на поставленные вопросы или те вопросы, которые у вас могут еще возникнуть.