Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Теория множеств: понятие и виды отображений

На главную Математический раздел Криптография и т.д. Новости

Что такое отображение и однозначное отображение

Правило вида f: A->B, ставящее в соответствие каждому элементу множества A какой-либо элемент (или элементы) множества B, называется отображением из A в B. Пример: A - множество футбольных команд, B - множество населённых пунктов; каждой футбольной команде ставится в соответствие пункт, где находится её родной стадион (ну или стадион, где она официально играет "на своём поле", если нет собственного стадиона).

Если какому-либо элементу множества A соответствует более одного элемента множества B, то отображение многозначное. Пример многозначного изображения можно привести следующий. Пусть A - множество олигархов, B - множество особняков. Есть олигархи, владеющие несколькими особняками. Тогда отображение, ставящее в соответствие каждому олигарху его особняки, является многозначным.

В дискретной математике, как правило, рассматриваются однозначные отображения. Отображение из A в B однозначное, если всякому элементу из A поставлен в соответствие только один элемент из B. Пример однозначного отображения: пусть есть воинская часть, в ней множество солдат и множество батальонов. Отображение, ставящее в соответствие солдату батальон, в котором он числится, однозначное, если только в списках составов не допущено ошибок. Заметим, что определение однозначного отображения из A в B не запрещает ситуаций, когда двум разным элементам множества A соответствует один и тот же элемент из B. Ярко видно это по примеру с солдатами.

Далее мы рассмотрим некоторые виды однозначных отображений, для простоты понятие "однозначное" иногда будем опускать.

Что такое однозначное инъективное и однозначное сюръективное отображение

Если разные элементы множества A отображаются в разные элементы множества B, то есть нет случаев, когда двум элементам из A соответствует один и тот же элемент из B, то отображение из A в B - инъективное. Пример: пусть множество A - множество государств, множество B - множество существующих городов. Отображение, ставящее в соответствие государству его столицу, - инъективное. А вот в примере с солдатами отображение из множество солдат во множество батальонов - неинъективное. Важное свойство инъективных отображений: пусть A и B - множества с конечным числом элементов, причём в А больше элементов, чем в B. Тогда не может существовать инъективных отображений из A в B. Скажем, A - множество морковок, B - множество ящиков. В соответствие морковке ставится ящик, куда мы её кладём. Если морковок больше, чем ящиков, мы же не можем избежать того, что в каком-то ящике будет хотя бы две морковки? Это нехитрое свойство по-умному называется принципом Дирихле.

Инъективные отображения применительно к современным технологиям важны тем, что только такие отображения могут применяться для кодирования информации. Если несколько кодируемых сообщений имеют одинаковый код, возникнет неоднозначность при декодировании, иногда мы не сможем восстановить, что было закодировано.

Отображение из A в B, при котором в каждый элемент из B отображается хотя бы один элемент из A, называется сюръективным. Пусть A - множество голов, забитых на футбольном турнире, B - множество игроков - участников турнира. Отображение, ставящее в соответствие голу игрока, который его забил, не является сюръективным, если некоторые игроки вообще не забили ни одного гола (например, почти стопроцентно это вратари).

Важное свойство сюръективных отображений: пусть A и B - множества с конечным числом элементов, причём в А меньше элементов, чем в B. Тогда не может существовать сюръективных отображений из A в B. Опять пример про морковки и ящики, но теперь ящиков больше, чем морковок. Тогда выходит, что по-любому какой-то ящик будет пустым.

Заметим ещё, что инъективность и сюръективность заранее никак не связаны: ни одно из этих свойств не обязывает, чтобы было другое.

Что такое биективное отображение

Если отображение одновременно инъективное и сюръективное, то оно биективное. В этом случае говорят, что между множествами установлена биекция (или взаимно однозначное соответствие). Каждому элементу из A соответствует один элемент из B, и никакому другому элементу из A не соответствует этот же элемент из B, при этом нет таких элементов из B, в которые не отображается кто-то из A. Пример: отображение из множества государств во множество столиц, ставящее в соответствие государству его столицу.

Только для биективного отображения можно построить обратное однозначное отображение, восстанавливающее по элементу из B элемент из A. Если отображение из A в B не является инъективным, то выходит, что несколько элементов из A могут отображаться в один элемент из B, то есть обратное отображение не будет однозначным. Теперь рассмотрим, что будет, если f: A->B несюръективно. Тогда некоторые элементы из B не участвовали в правиле отображения, в итоге говорить об обратном отображении вообще нельзя: отображение - правило для каждого элемента множества в левой части от стрелки)))

В примере со столицами и государствами обратное отображение ставит в соответствие столице государство, где она является главным городом.

(***) Обозначим |X| - количество элементов множества X. Если A и B конечны, выходит вот что. Если |A| > |B|, то нельзя построить инъективного отображения. Если |A| < |B|, то нельзя построить сюръективного отображения (смотрите примеры про морковки). Стало быть, для конечных множеств только при |A| = |B| можно построить биекцию. Если для множеств с конечным числом элементов построили биекцию, значит, у них одинаковое число элементов.

Скажем, организован бал. Если дамам и кавалерам удалось разбиться на танцующие пары, и никому не приходится тупо стоять и смотреть в сторонке, то дам и кавалеров одинаковое количество.

Парадоксальность биективных отображений

Парадокс: рассуждения абзаца (***) неверны, когда у множеств бесконечное число элементов. Скажем, пусть A = {1, 2, 3, ...} - множество натуральных чисел, B = {2, 4, 6...} - множество чётных чисел. Строим отображение f: A->B вот как: f(n) = 2n, то есть числу n из A ставим в соответствие число 2n из B (числу 1 из A соответствует 2 из B, числу 2 из A - 4 из B...). В A и B, очевидно, разное количество элементов, но биекция построена. Более того, построена биекция между множеством и его подмножеством.

Объяснение этому может быть следующее: бесконечность не является конкретным числом, это некое размытое понятие. Соответственно она и не обязана иметь те же свойства, что и обычные числа. Скажем, бесконечность, делённая на любое конечное число, отличное от нуля (а не только на единицу), даст снова бесконечность. Если же обычное число так делить, то оно даст само себя только при делении на единицу.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X