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

Напомним, что  ориентированным графом называется пара (V,A), состоящая из множества V и подмножества A Í V ´ V.  Элементы из A называются стрелками, а элементы из V – вершинами. Для стрелки (u,v) вершина u называется началом, а вершина v – концом.

Пусть (X,£) – частично упорядоченное множество. Множество

]x,y[ = {v Î X: x < v < y}

называется открытым интервалом с концами x и y.

Определение 1

Диаграммой Хассе называется ориентированный граф (V,A) с V = X и   A = {(u,v): u<v   и    ]u,v[ = Æ}.

Пример 1

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

Снимок

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

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

Пример 2

•®•®•® … ®•®•
Рис. 5.2. Диаграмма Хассе целого неотрицательного числа
Для целого неотрицательного числа n³ 0 будем обозначать через [n] множество {0, 1, …∙, n}, с отношением  0 < 1< …∙ < n. Его диаграммой  Хассе  будет ориентированный граф (рис. 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.

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

Пример 3

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

Снимок1

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

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

Теорема 1

Пусть n > 0 – положительное натуральное число, n = — его разложение в произведение попарно не равных простых множителей pi > 1. Тогда частично упорядоченное множество (Dn, |) будет изоморфно декартовому произведению линейно упорядоченных множеств:

[a1]´ [a2]´ … ´ [am].

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

Каждый делитель числа n =  будет равен числу , для некоторых 0£b1£a10 £ b2 £ a2, …, 0 £ bm £ am. Изоморфизм определяется как отображение, ставящее в соответствие числу  элемент (b1, b2, …, bm).