Упорядоченные системы: решетки, группы

Министерство образования и науки Российской Федерации
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Московский педагогический государственный университет»

Ю. В. Кочетова, Е. Е. Ширшова

УПОРЯДОЧЕННЫЕ СИСТЕМЫ: 
РЕШЕТКИ, ГРУППЫ

Курс лекций

МПГУ
Москва • 2014

УДК 512.(534.1+545+562)
ББК 22.144
 
К75

Рецензенты:

А. А. Фомин, доктор физико-математических наук, 
профессор кафедры алгебры МПГУ

В. Г. Чирский, доктор физико-математических наук, 
профессор кафедры теории чисел МПГУ

 
Кочетова, Юлия Викторовна.
К75  
Упорядоченные системы: решетки, группы : Курс лекций / 
Ю. В. Кочетова, Е. Е. Ширшова. – Москва : МПГУ, 2014. – 64 с.
 
 
ISBN 978-5-4263-0135-1
 
Учебное пособие подготовлено на кафедре алгебры МПГУ 
и адресовано студентам и аспирантам математических факультетов университетов и педвузов. Для освоения материала пособия не требуется 
специальных знаний, выходящих за рамки базового курса алгебры.

УДК 512.(534.1+545+562)
ББК 22.144

ISBN 978-5-4263-0135-1 
© МПГУ, 2014
 
© Кочетова Ю. В., Ширшова Е. Е., 2014

Содержание

Предисловие
4

1
Отношение порядка
6
1.1
Бинарные отношения и способы их представления . . . . . .
6
1.2
Операции над бинарными отношениями и их свойства . . . .
7
1.3
Свойства бинарных отношений . . . . . . . . . . . . . . . . .
10
1.4
Отношения частичного порядка и операции над ними . . . .
14
1.5
Задания к разделу "Отношение порядка" . . . . . . . . . . .
17

2
Частично упорядоченные множества
20
2.1
Свойства упорядоченных множеств
. . . . . . . . . . . . . .
20
2.2
Решетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.3
Полные решетки . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.4
Дистрибутивные решетки . . . . . . . . . . . . . . . . . . . .
30
2.5
Модулярность . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.6
Идеалы и гомоморфизмы . . . . . . . . . . . . . . . . . . . .
33
2.7
Идеалы в дистрибутивной решетке . . . . . . . . . . . . . . .
36
2.8
Задания к разделу "Частично упорядоченные множества"
.
37

3
Частично упорядоченные группы
40
3.1
Основные понятия и определения
. . . . . . . . . . . . . . .
40
3.2
Направленные группы . . . . . . . . . . . . . . . . . . . . . .
45
3.3
Подгруппы частично упорядоченных групп . . . . . . . . . .
48
3.4
Решеточно упорядоченные группы . . . . . . . . . . . . . . .
50
3.5
Отношение ортогональности
. . . . . . . . . . . . . . . . . .
54
3.6
Атомы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3.7
Линейно упорядоченные группы . . . . . . . . . . . . . . . .
57
3.8
Задания к разделу "Частично упорядоченные группы" . . .
61

Список литературы
63

СОДЕРЖАНИЕ

Предисловие

С современных позиций математика рассматривается как учение о математических структурах (под математической структурой понимают множество, между элементами которого существуют определенные отношения;
свойства этих отношений описываются с помощью аксиом), а исходной точкой в определении структуры является отношение.
Теория отношений, основные идеи которой рассмотрены в первой главе, является самостоятельным разделом математической науки, который
изучает виды отношений, их свойства, операции над ними.
В математике рассматриваются разнообразные по характеру отношения
между элементами множеств, обладающие различными свойствами, что
приводит к многообразию математических структур. Наука выделяет и
исследует более или менее определенные структуры той или иной степени
общности. К фундаментальным структурам относятся структуры порядка,
алгебраические структуры и топологические структуры.
Различные порядковые структуры (цепи, вполне упорядоченные множества, решетки, булевы алгебры и т.д.) встречаются в геометрии, в функциональном анализе, в квантовой механике, теории экспертных систем и т.д.
и находят применение во многих прикладных вопросах.
На уровне конкретных множеств важное значение имеет первоначальная порядковая структура — упорядоченное множество, как самая общая
и в то же время наиболее просто устроенная структура.
Понятие частично упорядоченного множества является одним из основных понятий, широко используемых в школьной и вузовской математике.
Оно служит объектом специальных исследований в современной алгебре и
имеет широкие приложения.
В теории упорядоченных множеств особое место занимает понятие точных граней. С помощью этого понятия формулируется специальный тип
упорядоченных множеств — решетки. Изучению свойств решеток посвящена вторая глава.
Среди основных свойств решеточных операций только закон поглощения связывает между собой обе решеточные операции. При изучении различных решеток возникают и другие связи. Наиболее важную роль играют
соотношения дистрибутивного типа. Для дистрибутивных решеток в главе 2 рассматриваются различные характеристики, в том числе при помощи тождеств, связывающих решеточные операции, а также при помощи ее
подрешеток.

ПРЕДИСЛОВИЕ

В различных разделах математики используются упорядоченные алгебраические системы, совмещающие в себе структуру алгебраической системы и структуру порядка. Так, например, строение многих алгебраических
систем обычно выявляется путем анализа связанных с ними решеток.
Теория упорядоченных алгебраических систем наиболее разработана
в рамках теории решеточно упорядоченных групп, изложению основных
идей которой посвящена глава 3.
Основным техническим средством исследования решеточно упорядоченных групп служит понятие ортогональности элементов. Его эффективность основана на том, что ортогональные элементы обладают рядом "хороших" свойств: они коммутируют, их точная верхняя грань совпадает с
произведением этих элементов. В главе 3 изучаются свойства отношения
ортогональности в решеточно упорядоченных группах и связанного с ним
понятия атома. Кроме этого рассмотрен ряд вспомогательных понятий и
конструкций теории решеточно упорядоченных групп, тесно связанных с
понятием ортогональности и необходимых для изучения свойств ортогональных элементов.
Часть материала пособия оформлена в виде заданий, доказательство
которых предлагается провести читателю самостоятельно. Задания имеют
своей целью закрепление теоретического материала, выработку некоторых
умений оперирования с введенными понятиями, а также навыков проведения самостоятельных теоретических рассуждений. Кроме того, в заданиях
рассмотрены некоторые дополнительные свойства.
При изучении тем пособия читателю полезно ознакомиться с материалом, изложенным в рекомендованной литературе. Там же, при возникновении трудностей, можно найти необходимые для решения заданий сведения.
Данное пособие написано на основе лекционных и факультативных курсов, читаемых авторами в течение многих лет студентам математического
факультета Московского педагогического государственного университета.
Оно предназначено для изучения основ теории упорядоченных алгебраических систем студентами математических факультетов университетов и
педвузов. Кроме того, содержанием второй главы пособия могут воспользоваться аспиранты при подготовке к сдаче кандидатского экзамена по
алгебре, а материалом третьей главы — студенты, изучающие курс "Числовые системы". Пособие может быть также полезным читателю, желающему самостоятельно познакомиться с основными понятиями теории частично упорядоченных групп.

1
Отношение порядка

Предполагается, что читателю известны первоначальные сведения о
множествах и операциях над ними.

1.1
Бинарные отношения и способы их представления

Определение 1.1.1. Для любых двух непустых множеств A и B их
декартовым произведением называется множество, обозначаемое A×B,
состоящее из всех упорядоченных пар (a, b), где a ∈ A, b ∈ B.

Стоит заметить, что равенство пар (a, b) = (c, d) означает одновременное выполнение двух равенств a = c и b = d.
Если A = B, то декартово произведение A × A называется декартовым
квадратом множества A.

Определение 1.1.2. Если A и B — произвольные непустые множества,
то бинарным отношением на паре множеств A и B называется всякое
подмножество ρ ⊆ A × B.
Если A = B, то говорят, что бинарное отношение ρ ⊆ A×A является
отношением, заданным на множестве A.

Для записи того, что пара (a, b) принадлежит отношению ρ, наравне с
записью (a, b) ∈ ρ используют запись aρb.

Примеры:
1. Отношения параллельности и перпендикулярности, определенные на
множестве прямых плоскости.
2. Отношение включения в произвольной совокупности множеств.

Для задания бинарного отношения применяют различные способы.
Наиболее распространенными являются следующие:

1) Перечисление пар. Этот способ подходит только для бинарного отношения ρ, состоящего из конечного числа пар.

2) Указание правила (закона), который для любой пары из A × B однозначно устанавливает, принадлежит ли эта пара данному отношению ρ
или нет.

3) Графический способ применяется в случае, когда отношение ρ задается на R или на его подмножестве. В этом случае легко изобразить ρ

• ОТНОШЕНИЕ ПОРЯДКА

7

множеством точек плоскости, что дает наглядную геометрическую характеристику.

4) Матричный способ — способ задания бинарного отношения на конечном множестве — можно описать так. Пусть A — n-элементное множество,
элементы которого перенумерованы от 1 до n, и ρ — отношение на нем.
Построим квадратную n × n матрицу (aij), на пересечении i-ой строки и
j-го столбца которой ставится единица, если xiρxj, и нуль — в противном
случае. То есть

aij =

1, если (xi, xj) ∈ ρ,
0, если (xi, xj) ̸∈ ρ.

В частности, нулевая матрица задает пустое отношение, которое не выполняется ни для одной пары, а матрица, в которой aij = 1 для всех i и j,
определяет полное отношение ρ = A × A, выполненное для всех пар.
Также особую роль играют матрицы (δij) и (1 − δij), где

δij =

1, если i = j,
0, если i ̸= j,

которым соответствуют диагональное (отношение равенства на данном
множестве A) и антидиагональное отношения.
Матрицы пустого, полного, диагонального и антидиагонального отношений обладают тем свойством, что их вид не зависит от выбора нумерации
элементов множества A. Более того, если отношение ρ на A таково, что
при любом выборе нумерации в A его матрицы совпадают, то ρ — пустое,
полное, диагональное или антидиагональное отношение.

5) С помощью ориентированного графа можно задавать отношения,
определенные на конечном множестве A. Для этого изображают элементы множества A точками на плоскости, проводя стрелку от точки xi к
точке xj, если xiρxj, и рисуя петлю, выходящую из xi и входящую в ту же
точку, если xiρxi.
Пустому отношению соответствует граф без стрелок и петель, диагональному — граф, содержащий только петли. Граф, изображающий полное
отношение, называется полным графом.

1.2
Операции над бинарными отношениями и их свойства

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

Ю.В. Кочетова, Е.Е. Ширшова •УПОРЯДОЧЕННЫЕ СИСТЕМЫ: РЕШЕТКИ, ГРУППЫ

8

выбранной нумерацию элементов этого множества.

1. Пересечением ρ∩σ (объединением ρ∪σ) отношений ρ и σ называется
их теоретико-множественное пересечение (объединение).
Для отношений ρ и σ на конечном множестве A, заданных матрицами (aij) и (bij) соответственно, матрица (cij) пересечения ρ ∩ σ удовлетворяет условию cij = aijbij, а матрица (dij) объединения ρ ∪ σ — условию
dij = aij + bij (здесь умножение и сложение элементов матриц понимается
в смысле булевой арифметики).
При построении графа пересечения учитывают только общие стрелки и
петли графов пересекаемых отношений, а в графе объединения изображают все петли и стрелки из графов ρ и σ.

2. Операции включения и равенства определяются для отношений так
же, как для множеств.
Легко видеть, что для любого отношения ρ, пустого ∅ и полного U
отношений на множестве A верно ∅ ⊆ ρ ⊆ U.

Пример. На множестве натуральных чисел N рассмотрим отношения ρ1,
ρ2 и ρ3, определяемые следующим образом:

(a, b) ∈ ρ1 ⇔ b = a + 1,
(a, b) ∈ ρ2 ⇔ a ⩽ b,
(a, b) ∈ ρ3 ⇔ b ... a.

Для этих отношений ρ1 ⊂ ρ2 и ρ3 ⊂ ρ2, но других включений между
рассматриваемыми отношениями нет, поскольку (3, 5) ∈ ρ2 и (3, 5) ̸∈ ρ1,
(3, 5) ̸∈ ρ3; (2, 3) ∈ ρ1 и (2, 3) ̸∈ ρ3; (2, 4) ∈ ρ3 и (2, 4) ̸∈ ρ1.

3. Обратное к отношению ρ отношение ρ−1 состоит из тех и только тех
пар (x, y), для которых yρx.
Ясно, что отношение ρ−1 в матричной форме представляется матрицей,
транспонированной к матрице отношения ρ, а для изображения его графа
достаточно поменять направление стрелок на графе ρ.

Предложение 1.2.1. Для любых отношений ρ и σ на множестве A справедливы равенства

(ρ−1)−1 = ρ,
(ρ ∪ σ)−1 = ρ−1 ∪ σ−1
и
(ρ ∩ σ)−1 = ρ−1 ∩ σ−1.

Кроме того, если ρ ⊆ σ, то ρ−1 ⊆ σ−1.

4. Произведением отношений ρ и σ называется отношение ρσ, для которого xρσy равносильно тому, что существует такой элемент z ∈ A, что
xρz и zσy.

• ОТНОШЕНИЕ ПОРЯДКА

9

Матрица (cij) произведения ρσ отношений ρ и σ представляется произ
ведением матриц (aij) и (bij) данных отношений, то есть cij =
nk=1
aikbkj.

Действительно, если xiρσxj, то существует xk ∈ A, для которого xiρxk и
xkσxj, поэтому aik = bkj = 1. Значит, aikbkj = 1. Так как одно из слагаемых
равно единице, то и сумма cij заведомо равна единице. Обратно, из cij = 1
следует равенство единице хотя бы одного слагаемого aikbkj, что влечет
aik = bkj = 1.
Графовая интерпретация произведения ρσ такова: вершины xi и xj соединены стрелкой, если из xi в графе ρ можно перейти в некоторую вершину xk, из которой в графе σ есть стрелка в xj.

Пример. Если ρ и σ — соответственно отношения "меньше" и "больше" на
множестве целых чисел, то ρσ = σρ является полным отношением на Z.

В общем случае произведение отношений не подчиняется коммутативному закону, что видно из следующего примера.

Пример. Если матрицы отношений ρ и σ равны соответственно

1
1
0
1
1
0
0
0
1

и

1
1
0
1
1
1
0
1
1

, то

1
1
1
1
1
1
0
1
1

и

1
1
0
1
1
1
1
1
1

— матрицы отношений ρσ и σρ.

Предложение 1.2.2. Если εA и ∅ — диагональное и пустое отношения
на множестве A, то для всякого отношения ρ на A верно

ρεA = εAρ = ρ
и
ρ∅ = ∅ρ = ∅.

Если при этом для каждого x ∈ A существует такой элемент z ∈ A,
что xρz (zρx), то ρρ−1 ⊇ εA (ρ−1ρ ⊇ εA).

Предложение 1.2.3. Для любых отношений ρ, σ и ψ, заданных на множестве A, имеют место соотношения

а) (ρσ)−1 = σ−1ρ−1;
б) ρ(σψ) = (ρσ)ψ;
в) (ρ ∪ σ)ψ = ρψ ∪ σψ,
(ρ ∩ σ)ψ ⊆ ρψ ∩ σψ;
г) если ρ ⊆ σ, то ρψ ⊆ σψ и ψρ ⊆ ψσ.

Следствие 1.2.4. Множество всех бинарных отношений на A относительно операции произведения отношений образует моноид.

Заменить в пункте в) предложения 1.2.3 включение на равенство, как
показывает следующий пример, нельзя.

Ю.В. Кочетова, Е.Е. Ширшова •УПОРЯДОЧЕННЫЕ СИСТЕМЫ: РЕШЕТКИ, ГРУППЫ

10

Пример. На четырехэлементном множестве A = {x1, x2, x3, x4} зададим
отношения ρ = {(x1, x2)}, σ = {(x1, x3)} и ψ = {(x2, x4), (x3, x4)}. Поскольку ρ ∩ σ = ∅, то по предложению 1.2.2 получаем (ρ ∩ σ)ψ = ∅. C другой
стороны, ρψ ∩ σψ = {(x1, x4)}.

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

5. Транзитивное замыкание ρ отношения ρ определяется как отношение, которому пара (x, y) принадлежит в том и только в том случае, когда
существует такая цепочка z0 = x, z1, . . . , zn = y элементов из A, что z0ρz1,
z1ρz2, . . . , zn−1ρzn.
Из данного определения легко выводим следующие соотношения.

Предложение 1.2.5. Для любого отношения ρ на множестве A

ρ ⊆ ρ
и
ρ = ρ ∪ ρ2 ∪ · · · ∪ ρn ∪ · · · ,

то есть транзитивное замыкание отношения совпадает с объединением
всех степеней этого отношения.

Согласно этой формуле, матричная форма транзитивного замыкания
отношения ρ выражается через сумму степеней матрицы ρ.
Более наглядным является построение графа ρ по графу, изображающему отношение ρ: в нем вершины xi и xj соединяет стрелка, если в графе
ρ существует путь (то есть последовательность вершин), ведущий из xi в
xj по направлению стрелок.

Предложение 1.2.6. Пусть ρ и σ — отношения на множестве A. Тогда

а) ρ = ρ;
б) если ρ ⊆ σ, то ρ ⊆ σ.

1.3
Свойства бинарных отношений

Основные свойства бинарных отношений на множестве A перечислены
в следующей таблице. В ней также указано, как наличие того или иного
свойства отражается на матрице и графе отношения, заданного на конечном множестве.
В таблице используются следующие обозначения:
ρ — отношение на множестве A;
εA, ε∗
A и ∅ — диагональное, антидиагональное и пустое отношение на A;
Mρ = (aij) — матрица отношения ρ в случае его задания на конечном
множестве.

• ОТНОШЕНИЕ ПОРЯДКА

11

Таблица 1. Свойства бинарных отношений

Название свойства

Определение свойства
Отражение свойства
Примеры отношений,
обладающих свойством

с помощью правила
с помощью
операций
на матрице
на графе

Рефлексивность
(∀x ∈ A) xρx
εA ⊆ ρ
для всех i
aii = 1
присутствуют все петли
⩽ и ⩾ на R,
делимость на N

Антирефлексивность
(∀x, y ∈ A)
(xρy ⇒ x ̸= y)

ρ ∩ εA = ∅
или ρ ⊆ ε∗
A

для всех i
aii = 0
нет ни одной петли
перпендикулярность
прямых, < и > на R

Симметричность
(∀x, y ∈ A)
(xρy ⇒ yρx)
ρ ⊆ ρ−1
для всех i, j
aij = aji
все стрелки двойные

перпендикулярность и
параллельность прямых,
подобие фигур,
смежность углов,
отношение взаимной
простоты на N

Антисимметричность
(∀x, y ∈ A)
(xρy & yρx ⇒ x = y)
ρ∩ρ−1 ⊆ εA
при i ̸= j
aijaji = 0

нет ни одной двойной
стрелки

⩽ и ⩾ на R,
делимость на N

Асимметричность

для любых x, y ∈ A
из соотношений xρy и
yρx по крайней мере
одно не выполняется

ρ ∩ ρ−1 = ∅
для всех i, j
aijaji = 0

нет ни одной двойной
стрелки и ни одной петли

< и > на R,
⊂ на некоторой
совокупности множеств

Транзитивность
(∀x, y, z ∈ A)
(xρy & yρz ⇒ xρz)
ρ2 ⊆ ρ

Mρ2 ⩽ Mρ
(матрицы
сравнивают
поэлементно)

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

параллельность прямых,
подобие фигур,
сонаправленность лучей,
включение множеств,
делимость на N

Связность
(∀x, y ∈ A)
(x ̸= y ⇒ xρy ∨ yρx)
ε∗
A ⊆ ρ∪ρ−1
при i ̸= j
aij + aji = 1

любые две точки
соединены стрелкой
<, ⩽ и >, ⩾ на R