Прямое произведение множеств

2.4. Прямое произведение множеств

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово (прямое) произведение множеств.

Пусть A и B - множества. Выражение вида (a, b) , где aA и bB, называется упорядоченной парой. Элемент а называют первой координатой (компонентой) пары, элемент b - второй координатой (компонентой) пары.

Равенство вида (a, b)=(c, d) означает, что a=c и b=d. В общем случае, можно рассматривать упорядоченную n-ку (a1, a2, a3, … ,an) из элементов a1A1, a2A2 … anAn. Упорядоченные n-ки иначе называют наборами или кортежами.

Определение прямого произведения множеств. Декартовым (прямым) произведением множеств A1, A2,… An называется множество упорядоченных наборов (кортежей) вида A1A2…An={( a1, a2,… an | aiAi}.

Из вышеприведенного определения следует, что для любых a1a2 справедливо (a1,a2) (a1,a2).

Операция нахождения декартова произведения множеств называется декартовым умножением множеств.

Определение степени прямого произведения. Степенью декартового произведения A1A2…An называется число множеств n, входящих в это декартово произведение.

Замечание. Если все множества Ai одинаковы, то используют обозначение

An=AA…A.

Выясним, какими свойствами обладает операция нахождения декартова произведения множеств. Так как декартовы произведения (a1, a2) (a2, a1), a1a2 состоят из различных элементов, то декартово умножение множеств свойством коммутативности не обладает.

Аналогично рассуждая, можно доказать, что для этой операции не выполняется и ассоциативность. Но она дистрибутивна относительно объединения и вычитания множеств: для любых множеств А, В и С справедливо:

(A U B)  C = ( A  C ) U ( B  C );

(A B) C = ( A C ) ( B  C ).

2.5. Отношения на множестве

Определение отношения степени n. Подмножество R декартового произведения множеств A1 A2… An называется отношением степени n (n-арным отношением).

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

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Как будет показано ниже, отношения являются математическим аналогом таблиц.

Т.к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины “отношение степени 1” и “подмножество” являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Если же множество состоит из разнотипных числовых кортежей, то это множество не является отношением ни в R1, ни в R2, ни в Rn.

Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение A1A2…An, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие - нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения.

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1 ,x2, … , xn), зависящее от n параметров и определяющее, будет ли кортеж (a1, a2, … ,an) принадлежать отношению R. Это логическое выражение называют предикатом отношения R. Более точно, кортеж (a1, a2, … ,an) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(a1, a2, … ,an) принимает значение “истина”. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

Примеры отношений.

Бинарные отношения (отношения степени 2)

В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств A1A2.

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

(x, x)R для всех xA (рефлексивность).

Если (x, y)R, то (y, x)R (симметричность).

Если (x, y)R и (y, z)R, то (x, z)R (транзитивность).

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

x=x для всех xA (рефлексивность).

Если x=y, то y=x (симметричность).

Если x=y и y=z, то x=z (транзитивность).

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

Если (x, y)R и (y, x)R, то x=y (антисимметричность).

Если (x, y)R и (y, z)R, то (x, z)R (транзитивность).

Обычно отношение порядка обозначают знаком . Если для двух элементов x и y выполняется xy , то говорят, что x “предшествует” y. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

xx для всех xA (рефлексивность).

Если x  y и y  x, то x = y (антисимметричность).

Если x  y и y  z, то x  z(транзитивность).

Определение функционального отношения. Отношение R на декартовом произведении двух множеств A1A2 называется функциональным отношением, если оно обладает следующим свойством:

Если (x, y)R и (x, z)R, то y=z (однозначность функции).

Обычно, функциональное отношение обозначают в виде функциональной зависимости - (x, y)R тогда и только тогда, когда y=f(x). Функциональные отношения (подмножества декартового произведения) называют иначе графиком функциональной зависимости.

N-арные отношения (отношения степени n).

В математике n-арные отношения рассматриваются относительно редко, в отличие от баз данных, где наиболее важными являются именно отношения, заданные на декартовом произведении более чем двух множеств.

Похожие работы

Теория вероятностей и математическая статистика

Скачать

100095

5

2

... проверить знания студента из первой части курса, которая излагается в первых четырёх модулях. Во вторых вопросах билета проверяются знания классической предельной проблемы теории вероятностей и математической статистики, которые излагаются в следующих пяти модулях. 1.  Вероятностная модель с не более чем счётным числом элементарных исходов. Пример: испытания с равновозможными исходами. 2.  ...

Об основаниях теории множеств

Скачать

23124

0

0

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

Аксиоматика теории множеств

Скачать

24811

0

698

... вующий класс (предло­жение 4), то из аксиомы S следует, что для любого множества х класс всех его элементов, удовлетворяющих дан­ной предика­тивной формуле A(у), есть множество. Однако для полного развития теории множеств потребуется ак­сиома, более сильная, чем аксиома S. Введем предварительно несколько оп­ределений. Определения Un (X) означает xyz ( X & X y = z). (X однозначен.) ...

Возможности использования элементов теории вероятностей и статистики на уроках математики в начальной школе

Скачать

53712

10

2

... монету второй раз не бросают), в четвертом — второму. Шансы игроков на выигрыш относятся как 3 к 1. В этом отношении и надо разделить ставку. Глава II. Элементы теории вероятностей и статистики на уроках математики в начальной школе (методика работы) Первый шаг на пути ознакомления младших школьников с миром вероятности состоит в длительном экспериментировании. Эксперимент повторяют много раз при ...