Пример 1. На рис. 5.1 показана диаграмма Хассе множества p({0,1,2}) подмножеств множества {0,1,2}, упорядоченное отношением .

Рис. 5.1. Диаграмма Хассе множества подмножеств

Предполагаются, что ребра направлены сверху вниз.

Пример 2. Для целого неотрицательного числа n0 будем обозначать через [n] множество {0, 1, ∙ ∙ ∙, n}, с отношением 0 < 1< ∙ ∙ ∙ < n. Его диаграммой Хассе будет ориентированный граф, приведенный на рис. 5.2.

    

Рис. 5.2. Диаграмма Хассе

Частично упорядоченные множества (X, )и(Y, )называются изоморфными, если существуют неубывающие отображения f: XY иg: YXтакие, что f(g(y))=yиg(f(x))=x(xX, yY).

В этом случае fназываетсяизоморфизмом, аg–обратным отображениемдляf.

Рассмотрим множество делителей (D_n, | ) натурального числаn1, упорядоченноеотношением делимостиa|ba– делитель числаb(в этом случае говорят, чтоa–делит b).

Пример 3. Пусть p и q – различные простые числа, большие единицы. Диаграмма Хассе множества ( D_n, | ) с n=p²q показана на рисунке 5.3.

Рис. 5.3. Диаграмма Хассе множества делителей

В общем случае диаграмма Хассе частично упорядоченного множества (D_n ,| ) состоит из реберm-мерного параллелепипеда, гдеm– число различных простых делителей числаn.

Теорема 1. Пусть n>0 – положительное натуральное число, n = его разложение в произведение попарно не равных простых множителей p_i>1. Тогда частично упорядоченное множество ( D_n , | ) будет изоморфно декартовому произведению [₁] [₂]   [_m] линейно упорядоченных множеств.

Доказательство.Каждый делитель числаn =будет равен числу, для некоторых 0₁₁, 0₂₂ ,   , 0_m_m. Изоморфизм определяется как отображение, ставящее в соответствие числуэлемент (₁, ₂,   , _m).

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

Пусть (X, ) – конечное частично упорядоченное множество. Рассмотрим последовательность функцийPⁿ: XX Z , определенных приn=0 иn=1 по формулам:

А при n≥2:

Pⁿ(x,y) = |{( x₁ , x₂ ,   , x_n-1) : x< x₁ < x₂ <  < x_n-1 <y}|.

Определение 1. Функцией Мебиуса  : XXz называется функция, определенная по формуле

.

Определение 2. Пусть X={ x₁ , x₂ ,  , x_n} – конечное частично упорядоченное множество, матрицей смежности называется матрица A, имеющая коэффициенты

Лемма 1. Пусть X={ x₁ , x₂ ,  , x_n} – конечное частично упорядоченное множество, A – матрица смежности. Тогда матрица M, коэффициенты которой равны значениям (x_i, x_j), будет обратной к матрице A.

Доказательство.ПустьId– единичная матрица. ПоложимQ=AId. Тогда A=Id+Q. Откуда

A^-1 = Id  Q + Q²  Q³ +  = .

Легко видеть, что коэффициенты матрицы Q^kравныP^k(x_i,x_j), откуда , в силу. Что и требовалось доказать.

Пример 1. X=[n].

, .

Отсюда получаем (i,i)=1, (i,i+1)=1. Остальные значения функции Мебиуса равны 0.

5.3. Формула обращения

Теорема 1. Пусть (X, ) – конечное частично упорядоченное множество. Тогда для любых функций f, g : X R равносильны следующие свойства

(1) ;

(2).

Доказательство.ПустьA– матрица смежности частично упорядоченного множества (X, ). Тогда выполнение равенства (1) равносильно соотношениямg(x_i)=_j a_ij f(x_j). Поскольку это равносильно равенствуg=Af, эквивалентного равенствуf=A^-1g , то получаем, что (1) верно тогда и только тогда, когда верно (2).

Рассматривая частично упорядоченное множество с двойственным отношением порядка, получаем следующую теорему.

Теорема 2. Пусть (X, ) – конечное частично упорядоченное множество. Тогда для любых функций f , g : X R равносильны следующие свойства

(1) ;

(2) .

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

Теорема 1. Пусть (X,) и (Y,) – конечные частично упорядоченные множества, _X: XX Z и _Y: YY Z – их функции Мебиуса. Тогда, для любых x₁, x₂  X и

y₁, y₂  Y имеет место равенство

_XY ( (x₁, y₁) , (x₂ , y₂ ) ) = _X (x₁, x₂) _Y (y₁, y₂).

Доказательство.Введем дзета-функцию _X : XX Z, с помощью формулы

_X ( x₁, x₂ ) = 1  x₁  x₂ . Достаточно доказать формулу

,

где _a,b – символ Кронекера. Вычислим левую часть доказываемой формулы

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

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

то имеем

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

(1,n) =(1)^m, если n = p₁p₂    p_m .