Соответствия

Проекция множества

Операция проектирования множества тесно связана с операцией проектирования кортежа и может применять­ся лишь к таким множествам, элементами которых явля­ются кортежи одинаковой длины.

Пусть М — множество, состоящее из кортежей длиной s. Тогда проекцией множества М будем называть мно­жество проекций кортежей из М.

Пример 1.2. Пусть М={(1, 2, 3, 4, 5), (2, 1, 3, 5, 5), (3, 3, 3, 3, 3), (3, 2, 3, 4, 3)}. Тогда Пр₂М={2, 1, 3}; Пр₂,₄М={(2, 4), (1, 5), (3, 3)}.

Легко проверить, что если М=ХУ, то Пр₁М=Х; Пр₂М=У,

а если СХУ, то Пр₁СX; Пp₂СУ .

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

Для того чтобы задать соответствие, необходимо ука­зать: множество X, элементы которого сопоставляются с элементами другого множества; множество У, с элемен­тами которого сопоставляются элементы первого множе­ства; множество СХУ, определяющее закон в соот­ветствии с которым осуществляется соответствие, т.е. {перечисляющее все пары (х, у), участвующие в сопоставлении.

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

q=(X, Y, Q), (1.7)

в которой QXY. В этом выражении первую компонен­ту X называют областью отправления соответствия, вторую компоненту Y - областью прибытия соответствия, третью компоненту Q - гра­фиком соответствия. Термин «график» будет более по­дробно разъяснен при рас­смотрении частного вида со­ответствия, называемого функ­цией.

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

обратного (б) соответствий

Кроме рассмотренных множеств X, Y и С, с каждым
соответствием неразрывно связаны еще два множества: множество Пр₁С, называемое областью определения соот­ветствия, в которое входят элементы множества X, участ­вующие в сопоставлении, и множество Пр₂С, называемое областью значений соответствия, в которое входят элемен­ты множества У, участвующие в сопоставлении.

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

Пример 1.3.Пусть Х={1, 2},У= {3, 5}, так что X Y={(1, 3), (1, 5), (2, 3), (2,5)}. Это множество дает возможность получить16 различных соответствий. Приведем некоторые из них:

С₁={(1, 3)};Пр₁ С₁= {1};Пр₂ С₁={3};

С₂={(1, 3), (1, 5)};Пр₁С₂={l};Пр₂С₂={ 3,5}=У.