Верхняя и нижняя граница множества

Элементы множества можно сравнивать по величине, при этом возникает задача определения max и min элемента множества.

· нижняя граница - m = inf S (инфинум множества S)

· верхняя граница - M = sup S (супремум множества S)

4. Отношения. Свойства отношений.

Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.

Отношение является математическим аналогом понятия "таблица".

Отношения обладают степенью и мощностью.

Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).

В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени . В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).

5. Отношение эквивалентности.

Отношение на множестве называется отношением эквивалентности, если оно обладает следующими свойствами:

для всех (рефлексивность)

Если , то (симметричность)

Если и , то (транзитивность)

Обычно отношение эквивалентности обозначают знаком или и говорят, что оно (отношение) задано на множестве (а не на ). Условия 1-3 в таких обозначениях выглядят более естественно:

для всех (рефлексивность)

Если , то (симметричность)

Если и , то (транзитивность)

Легко доказывается, что если на множестве задано отношение эквивалентности, то множество разбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности).

Пример. Рассмотрим на множестве вещественных чисел отношение, заданное просто равенством чисел.

Предикат такого отношения:

, или просто

Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.

6. Отношение порядка. Отношение доминирования.