Соответствия между множествами

Рассмотрим два множества X и У. Элементы этих множеств могут какимлибо образом сопоставляться друг с другом, образуя пары (х, у). Если способ такого сопоставления определен, т. е. для каждого элемента х € X указан элемент уе У, с которым сопоставляется элемент х, то говорят, что между множествами X и У установлено соответствие. При этом не обязательно, чтобы в сопоставлении участвовали все элементы. Для задания соответствия необходимо:

• • множество X, элементы которого сопоставляются с элементами другого множества;
• • множество У, с элементами которого сопоставляются элементы первого множества;
• • множество Q q X хУ, определяющее закон, в соответствии с которым осуществляется соответствие, т. е. перечисляющее все пары (х, у), участвующие в сопоставлении.

Таким образом, соответствие, обозначаемое как q, представляет собой тройку множеств.

в которой Qq X хУ. В этом выражении первую компоненту X называют областью отправления соответствия, вторую — У — областью прибытия соответствия, третью Q — графиком соответствия.

С каждым соответствием неразрывно связаны еще два множества: множество Р Q, называемое областью определения соответствия, в которое входят элементы множества X, участвующие в сопоставлении, и множество P2Q, называемое областью значений соответствия, в которое входят элементы множества У, участвующие в сопоставлении.

Если (х, у) € Q, то говорят, что элемент у соответствует элементу х. Геометрически такое соответствие изображается стрелкой, направленной от х к у.

Пример. Задано: Х= {1, 2}, Г= {3, 5}, Хх У={( 1,3), (1,5), (2,3), (2,5)}.

Это дает возможность получить 16 различных соответствий:

Пример. В системе электроснабжения предприятия имеются три подстанции. Две из них аир связаны единой сетью, обеспечивают основной технологический процесс и работают в две смены. Третья у — маломощная, обеспечивает электроснабжение вспомогательных производств. Подстанция р находится на профилактическом обслуживании и на момент решения настоящей задачи отключена. В штате предприятия имеются три дежурных электрика а, Ь_у с, из которых с находится в отпуске.

Распределение дежурных электриков по подстанциям представляет собой соответствие, одним из возможных видов которого является следующее:

Геометрически это соответствие изображено на рис. 4.7, а. Областью определения его является множество Р Q — {а, Ь), а областью значений — PjQ ~ {а, у}.

Рис. 4.7. Геометрическое представление прямого (а) и обратного (б) соответствия

Для каждого соответствия q = (X, Y, Q), Q q X xY существует обратное соответствие, когда определяются элементы х & X, с которыми сопоставляются элементы у е Y. Соответствие, обратное соответствию q, обозначается как.

В предыдущем примере обратным соответствием будет закрепление подстанций за каждым дежурным электриком.

что геометрически соответствует изменению направления стрелок (рис. 4.7,6).

Попарное соответствие между элементами двух множеств называется взаимно однозначным соответствием. Пусть X и У два конечных множества с т и, соответственно, с п элементами. Взаимно однозначное соответствие между ними можно установить, только если т = п.

Число взаимно однозначных соответствий определяется на основе следующих рассуждений. Первый элемент множества X может быть сопоставлен с любым из п элементов множества У. Второй элемент множества X может быть сопоставлен с любым из оставшихся л-1 элементов множества У и т. д.

После тою, как такое сопоставление проведено для л-1 элементов множества X, последний элемент его может быть сопоставлен с единственным оставшимся элементом множества У.

Следовательно, общее число N взаимно однозначных соответствий для двух множеств с л элементами будет.

Число^{-элементных} подмножеств множества X, содержащего п элементов, при п > к, определится числом сочетаний из п элементов по 1с.

Общее число L всевозможных подмножеств л-элементного множества X вычисляется по формуле При этом числа Cj = 1 и С" = 1 определяют пустое множество 0 и само множество X. Множества 0 и А' называют несобственными подмножествами множества X. Все остальные — собственными.