N-арные отношения

По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X Y Z трех множеств X,Y,Z и вообще декартово произведение Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n.

Декартовым произведением Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n называется множество всех упорядоченных п - ок <х₁, х₂,..., x_n>, составленных из элементов этих множеств так, что Х₁ Х₂ ... Х_n= {<х₁, х₂,..., x_n>|x₁ X₁, x₂ X₂, …, x_n X_n}. Любое непустое подмножество N декартова произведения Х₁ Х₂ ... Х_n п множеств Х₁,Х₂,...,Х_n называется n- арным отношением между Х₁,Х₂,...,Х_n и записывается так: N Х₁ Х₂ ... Х_n.

В том случае, если M₁ = M₂ =…= M_n, то пишут Mⁿ. Часто Mⁿ называют универсальным отношением. Точка на плоскости может рассматриваться как упорядоченная пара, а в пространстве - упорядоченная тройка. Координатное представление впервые ввел Рене Декарт (1596-1650), поэтому оно и называется «декартово произведение».

Декартовым произведением

множеств М₁, М₂, М₃,..., М_п называется множество

.

Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит из п элементов, причем первый элемент принадлежит множеству М₁, второй — множеству М₂,..., п -й элемент — множеству М_n.

Теорема. Для конечных множеств A и B, мощность декартова произведения равна произведению мощностей множеств декартового произведения, т.е. | AB | = | A | | B |

Доказательство. Первый компонент упорядоченной пары можно выбрать | A | способами, второй | B | способами. Всего упорядоченных пар <a_ib_j> будет | A | | B | ч.т.д.

Пример 1. Сколько вариантов окраски квадрантов круга возможно, если допускается пять цветов краски.

Решение:

Кортеж длины 4, каждая компонента которого есть цвет краски, есть элемент декартового произведения. Пусть цвета краски образуют множество M = {к,б,з,с,ф}. Тогда М⁴ = М  М  М  М и М⁴ = 5⁴ = 625.