5.4. Теорема о произведении

Теорема 1

Пусть (X,£) и (Y,£) – конечные частично упорядоченные множества, mX: X´X® Z  и   mY: Y´Y® Z   – их функции Мебиуса. Тогда, для любых x1, x2 Î  и  y1, y2 Î Y имеет место равенство:

mX´Y ( (x1, y1), (x2, y2 ) ) = mX (x1, x2) mY (y1, y2).

Доказательство

Введем дзета-функцию zX: X´X® Z, с помощью формулы:

zX ( x1, x2 ) = 1 Û x1 £ x2.

Достаточно доказать формулу:

,

где  da,b – символ Кронекера.

Вычислим левую часть доказываемой формулы:

Получили, что она равна правой части. Что и требовалось доказать.

Пример 1

Вычислим  в частично упорядоченном множестве делителей числа n ≥ 1. По доказанной теореме, в случае разложения  n = в произведение степеней различных простых чисел pi > 1, будет иметь место соотношение:

.

Поскольку

то имеем

m(1,n) = 0, если существует i такой, что ai  > 1,

m(1,n) =(-1)m, если n = p1p2pm .

Упражнения

Диаграмма Хассе

1. Нарисовать диаграмму Хассе множества подмножеств из {0,1,2,3}, упорядоченное отношением включения.

2. Нарисовать диаграмму Хассе множества делителей числа 1000, упорядоченного отношением делимости.

3. Нарисовать диаграмму Хассе множества делителей числа 360, упорядоченного отношением делимости.

4. Нарисовать диаграмму Хассе множества P3 разбиений множества {1,2,3}.

5. Нарисовать диаграмму Хассе множества P4  разбиений множества {1,2,3,4}.

6. Нарисовать диаграмму Хассе произведения P3 ´[1].

Функция Мебиуса

7. Вычислить значения m(0, x) непосредственно из определения функции Мебиуса для следующих частично упорядоченных множеств, заданных с помощью диаграмм Хассе, приведенных на рис. 5.4. 

Снимок

Рис. 5.4. Примеры диаграмм Хассе

1. Вычислить значения функции Мебиуса для множества P({1,2, …, n}),  упорядоченного отношением Í.

2. Пусть a – произвольный  элемент частично упорядоченного множества. Доказать, что . Найти значения функций Мебиуса для задачи 1 с помощью этой формулы.