JIотгрлярнъге лекции
ПО МАТЕМАТИКЕ
--------
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 55
Л. БЕРАН
УПОРЯДОЧЕННЫЕ
МНОЖЕСТВА
Перевод с чешского
В. Н. САЛИЯ
Под редакцией Л. А. СКОРНЯКОВА
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1981
22.144
Б 48
УДК 512
L. Beran
USPORADANB
MNOZINY
Nakladatelstvf
Ml ad a front a
Praha
1978
Беран Л.
Б48 Упорядоченные множества: Пер. с чешек. — М.:
Наука, 1981, 64 с.—(Популярные лекции по ма-
тематике). — 15 коп.
Брошюра содержит популярное изложение важного для совре-
менной математики понятия частично упорядоченного множества.
Рассмотрены понятия точной верхней и точной нижней граней, вве-
дены структуры (решетки), рассмотрены алгебраические свойства
операций взятия точных граней, введены дистрибутивные структуры.
Для учащихся старших классов средней школы и студентов
младших курсов вузов.
Б 053(02)-81 8Ь81‘ 1702030000	ББК 22.144 512
20203-048
053 (02)-81
81-81. 1702030000
ф Ladislav Beran. 1978
© Перевод на русский язык.
Издательство «Наука».
Главная редакция физике-
математической литературы, 1981
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ РЕДАКТОРА	РУССКОГО ПЕРЕВОДА . . 4
ПРЕДИСЛОВИЕ ............................ 5
ВВЕДЕНИЕ ............................... 9
Глава 1. УПОРЯДОЧЕННЫЕ МНОЖЕСТВА.........П
Глава 2. РЕШЕТКИ: ОСНОВНЫЕ СВОЙСТВА.....18
Глава 3. ПРИМЕРЫ РЕШЕТОК................28
Глава 4. ОСНОВНЫЕ КЛАССЫ РЕШЕТОК........37
РЕШЕНИЯ И ОТВЕТЫ К УПРАЖНЕНИЯМ............50
ПРИЛОЖЕНИЕ ...............................58
ЛИТЕРАТУРА ...............................62
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ......................63
ПРЕДИСЛОВИЕ РЕДАКТОРА РУССКОГО ПЕРЕВОДА
Понятие частично упорядоченного множества яв-
ляется фундаментальным для современной теоретико-
множественной математики и встречается во многих при-
кладных вопросах. В предлагаемой вниманию чита-
теля книге содержится популярное изложение этого по-
нятия, а также связанные с ним понятия точной верхней
и точной нижней граней, введены решетки (структуры),
рассмотрены алгебраические свойства операций взятия
точных граней, введены модулярные и дистрибутивные
решетки. Автор не излагает сколько-нибудь глубоких
теорем. Однако предлагаемые им примеры, задачи и
упражнения позволяют овладеть введенными понятиями.
От читателя требуется владение основными понятиями
теории множеств в объеме средней школы, с популярным
изложением которых можно ознакомиться, например, по
книгам [1] (гл. I), [6] (гл. III) и [7]. В книгах [6] и
[7] можно найти дальнейшие сведения о решетках
(структурах) и булевых алгебрах. Для более глубокого
изучения этих понятий можно рекомендовать моногра-
фии [2], [3], [4] , а также § 7 гл. II учебного пособия
[5]. При подготовке русского издания были изъяты все
ссылки на чешскую литературу. Так что вся библиогра-
фия, за исключением работ [9] и [10], составлена ре-
дактором русского перевода. В оригинале имелись ссыл-
ки на доказательства, содержащиеся в книге [9]. В рус-
ском переводе они содержатся в «Приложении», напи-
санном редактором.
Л. А. Скорняков
ПРЕДИСЛОВИЕ
Теория упорядоченных множеств, наиболее разрабо-
танная в рамках теории решеток, относится к числу со-
временных математических дисциплин. Книжка, которую
вы, дорогие читатели, сейчас открыли, познакомит вас
с основными понятиями и методами этого раздела мате-
матики. Решая собранные в ней задачи и упражнения,
вы сможете усвоить важные конкретные примеры. При
этом от вас не потребуется почти никаких навыков в чис-
ленных расчетах. Но эта математика «без таблицы умно-
жения» тоже имеет свои правила, свой круг проблем,
свое очарование. Книжка позволит вам несколько иначе
взглянуть и на некоторые понятия школьной программы.
В ходе долгого исторического развития люди посто-
янно встречались с различными частными случаями упо-
рядочения. Сначала это было упорядочение привычных
вещей и повседневных явлений. Позднее — по мере того,
как совершенствовались трудовые навыки и мастер-
ство— обнаруживалось упорядочение отдельных этапов
в той или иной деятельности, и оно как приобретенный
опыт передавалось из поколения в поколение. Так уже
с первых робких шагов, с самых первых изготовленных
предметов люди обнаруживали все новые виды упоря-
дочения окружающих вещей, своей деятельности.
С некоторых из этих упорядочений мы свыклись на-
столько, что часто их просто не осознаем, как, напри-
мер, грамматический порядок слов в предложении. Мы
постоянно упорядочиваем предметы и явления по тому,
насколько они нам нравятся. Так, если нам придется
сравнивать голоса певчих птиц, то, конечно, результат
будет определяться нашей собственной оценкой их пе-
ния. После некоторых размышлений мы согласимся, что
имеем дело с упорядочениями и в следующем примере.
5
Предположим, нужно выстроить каким-то образом на-
ших четвероногих друзей — собак с кличками Бондо, Пе-
кинка, Лорд, Волк, Бублина. Как это можно сделать?
Кто-то, очевидно, предложит алфавитный порядок: Бон-
до— Бублина — Волк — Лорд — Пекинка. Другой рас-
положит лохматых псов в зависимости от того, как они
ему нравятся, скажем, так: Лорд — Бондо — Пекинка —
Бублина — Волк. Третий же, подумав, расставит их с
меньшей определенностью: конечно, больше всех ему
нравится Лорд, но вот Боидо, Пекинка и Бублина ка-
жутся ему одинаково милыми, диковатый же Волк не
вызывает большой симпатии. И тогда получится такое
расположение:
Лорд^
Бондо Пенинна Будлина
Волн
Еще пример. Малыши наблюдают за цветом проез-
жающих мимо машин. Каждый играющий стремится на-
считать как можно больше машин «своего» цвета. Пред-
положим, играют двое. Первому нужно, чтобы проехало
как можно больше машин белого цвета (мы их будем
обозначать буквой Б), но при этом он внимательно сле-
дит и за красными машинами (их мы обозначаем далее
буквой К), которые приносят очки его противнику. Ма-
шины других цветов (в обозначении Д) игроки отмечают
лишь краем глаза.
По схеме
К
Б Н
Л
б
(время у нас идет снизу вверх) мы установим не только
то, что к данному моменту игра имеет ничейный резуль-
тат, но и то, что первой проехала белая машина, потом
красная, а за ней как-то иначе окрашенная. Рассуждая
далее, видим, что оба наблюдателя отметили одновре-
менное появление белой и красной машин, а спустя не-
которое время — белой и машины, которая не была пи
красной, ни белой.
Обратимся теперь к несколько иным ситуациям. На-
верное, многие из вас в свободное время любят масте-
рить. Сначала перед вами просто набор различных
материалов, а результат — красивая модель парусника,
собранный своими руками транзисторный приемник, ма-
кет современного здания или велотрека и т. п. Вы
хорошо знаете, что для того чтобы добиться успеха в
этой своей работе, нужно действовать систематически,
другими словами, нужно определенным образом упоря-
дочить свою деятельность. Того же требует от вас и изу-
чение иностранных языков. То же самое происходит и
па более высоком уровне — при организации любой про-
изводственной деятельности. Здесь большую помощь
оказывают человеку различные вычислительные маши-
ны— от карманных калькуляторов до огромных автома-
тических устройств, управляющих целыми предприя-
тиями. Не все знают, что принцип действия этих машин
опирается на так называемый булевский тип упорядо-
чения.
Но оказывается, что и в обычных житейских ситуа-
циях вы встречаетесь с подобным способом упорядоче-
ния своих рассуждений. Например, ваши планы на се-
годняшний день могут зависеть от того, пойдет или не
пойдет Иржи в кино, а Ота поедет или не поедет к дяде.
Опыт подсказывает вам, что могут представиться сле-
дующие четыре варианта:
1)	Иржи пойдет, Ота поедет;
2)	Иржи пойдет, Ота не поедет;
3)	Иржи не пойдет, Ота поедет;
4)	Иржи не пойдет, Ота не поедет.
Если вы в своих рассуждениях будете рассматривать
эти четыре случая, то это значит, что вы использовали,
при оценке возможных ситуаций так называемую клас-
сическую булевскую логику.
Однако при изучении закономерностей квантовой ме-
ханики оказалось целесообразным обобщить этот тип
7
упорядочения — это привело к так называемому ортомо-
дулярному упорядочению. И здесь, таким образом, чело-
век опирается на опыт, приобретенный тысячелетним на-
блюдением различных упорядочений, и стремится исполь-
зовать накопленную информацию для углубления своих
знаний в области микромира.
Вопросы, затрагиваемые в этой книжке, относятся к
сравнительно узкой области теории упорядоченных мно-
жеств, они связаны в основном с программой средней
школы. Но хочется верить, что, ознакомившись с ними,
внимательный читатель осознает полезность понятия
упорядочения в элементарной математике и что он по
достоинству оценит тот длинный путь познания, который
человечество прошло от достаточно неопределенного по-
нятия упорядочения, используемого в разговорном язы-
ке, к математическому уточнению этого понятия и к со-
временному уровню его исследования,
ВВЕДЕНИЕ
В школе вы уже усвоили, вероятно, смысл выраже-
ния «число а меньше числа Ь» или значение слов «мно*
жество А является подмножеством множества В». Об-
щим у таких высказываний является то, что они ставят
один объект в определенное отношение к другому.
В дальнейшем мы и будем изучать подобные отношения.
Но сначала уточним само понятие отношения так, чтобы
оно могло стать предметом математического исследо-
вания.
Чтобы прийти к этому понятию, мы для большей на-
глядности рассмотрим пример, где участвует конечное
число элементов. Вы помните, что о двух числах /и, п
говорят, что m делит п и пишут т\п, если существует
целое число k такое, что km = л *).
Найдем все числа а, Ь из множества N^ =
= {0, 1, 2, 3, 4} такие, что а\Ь. Очевидно, мы получим
следующие случаи:
(I)
0 |0;
1 |0, 1 | 1, 1|2, 1|3, 1М
2 |0, 212, 2|4;
310, 3|3;
4|0, 4|4.
Будем теперь писать abb тогда и только тогда, когда
а, b е= 2V4 и при этом а делит Ь. Это еще один пример
связи между элементами, которую мы хотим включить
в общее понятие отношения. Прежде всего договоримся
читать запись abb словами «а находится в отношении S
♦) Обратите внимание, что согласно этому определению 0 де-
лит 0. — Прим, ред.
9
с Ь», и тогда естественным образом приходим к тому,
чтобы рассматриваемое отношение назвать отноше-
нием 6. Так что же это такое — отношение 6? В соответ-
ствии с таблицей (1) abb истинно тогда и только тогда,
когда (а,Ь) является одной из упорядоченных пар*)
следующего списка:
(2)
[ (0, 0);
I (1, 0), (1, 1), (1,2), (1,3), (1,4);
(2, 0), (2, 2), (2, 4);
(3, 0), (3, 3);
(4, 0), (4, 4).
Это приводит нас к мысли о том, что было бы целе-
сообразно определить отношение 6 как множество, эле-
ментами которого являются упорядоченные пары из таб-
лицы (2) и только они. При этом условимся рассматри-
вать запись abb как выражение того факта, что пара
(а, Ь) является элементом множества б, т. е. что
(а, б)е б.
Теперь перейдем к общему случаю. Пусть А — неко-
торое непустое множество. Декартовым квадратом мно-
жества А назовем множество А2 (обозначаемое также
А%А), элементами которого являются всевозможные
упорядоченные пары (а, Ь), где а, Ь пробегают множе-
ство А. Если р — подмножество множества А2, то будем
говорить, что р является отношением на множестве А.
Выражение (а, Ь)ер считается эквивалентным записи
apb.
Пример 1. Найти декартов квадрат множества N<.
Решение. Множество состоит из элементов, ко-
торые для наглядности расположим в виде следующей
таблицы:
(0, 0),	(0,	1),	(0, 2),	(0, 3),	(0,	4),
(1,0),	(1,	1),	(1,2),	(1,3),	(1,4),
(2, 0),	(2,	1),	(2, 2),	(2, 3),	(2,	4),
(3, 0),	(3,	1),	(3, 2),	(3, 3),	(3,	4),
(4, 0),	(4,	1),	(4, 2),	(4, 3),	(4,	4).
*) Слова «упорядоченная пара» означают, что пары (а, Ь) и
(6, а) считаются различными. — Прим, ред.
10
Заканчивая введение, вспомним, что если действи-
тельное число р меньше или равно q, мы пишем р q,
и что для любых действительных чисел р, q, г справед-
ливы следующие утверждения: (i) р р; (И) если
р q и q р, то р = q\ (Hi) если р q и q г, то
р г. Отношение на множестве 2? всех действитель-
ных чисел в соответствии с ранее сказанным мы можем
рассматривать как множество, элементами которого яв-
ляются упорядоченные пары (р, q) действительных чи-
сел такие, для которых разность q — р неотрицательна.
Глава 1
УПОРЯДОЧЕННЫЕ МНОЖЕСТВА
Заметим, что отношение б на множестве #4, опреде-
ленное на стр. 9, имеет некоторые общие свойства с от-
ношением на R, именно,
тЪт
для любого tn е N4; если
пгЪп и пбт, то т = п; если
/пбп и пЫг, то mbk.
т\т
для любого т е если
т | п и п | т, то т = п\ если
т \п и n\k, то m\k.
Напомним названия основных свойств отношений.
Пусть р — отношение на множестве А, т. е. р с А2.
Отношение р называется рефлексивным, если
(а, а) е р	ара
для любого ае Л.	для любого а е А.
(Для удобства читателей мы приводим определения в
обеих принятых нами записях.)
Отношение р по определению антисимметрично то-
гда и только тогда, когда оно обладает следующим
свойством:
если (а, Ь) е р и (Ь, а) е р, II если арб и бра, то а = Ь.
то a — b.	I
Отношение р называется транзитивным тогда и толь-
ко тогда, когда выполняется условие:
если (а, Ь) е р и (б, с) е р, ]] если арб и брс, то аре.
то (а, с) е р.	||
11
Наконец, отношение р называется симметричным
тогда и только тогда, когда для него выполняется усло-
вие:
если (а, Ь) е р, то (Ь, а) е р. J если арЬ, то Ьра.
Пример 2. Для двух действительных чисел а, b будем
писать aob тогда и только тогда, когда а: (а2 4-1)=^
sC Ь :(62+ 1). Нужно исследовать свойства так опреде-
ленного на множестве R всех действительных чисел от-
ношения.
Решение. Отношение о рефлексивно, поскольку для
любого действительного числа а частное а :(а24-1) опре-
делено и, конечно, а : (а2 + 1) а :(а2 + 1). Это отноше-
ние не является антисимметричным, так как 1/2о2 и
одновременно 2о1/2, но 1/2^2. Однако оно принадле-
жит к числу транзитивных отношений, поскольку из не-
равенств а :(а2 4-1)^ Ь :(62 + 1) и 6:(62+1)^
^c:(c2-f-l) вытекает, что а : (а2 4-1) с : (с2 + 1).
Наконец, из того, что 0о1, но пара (1, 0) не принадлежит
отношению о, заключаем, что рассматриваемое отноше-
ние симметричным не будет.
Для непустого множества Р, на котором опреде-
лено отношение р, являющееся рефлексивным, антисим-
метричным и транзитивным, введем специальное назва-
ние. Точная формулировка выглядит следующим обра-
зом. Если ф обозначает упорядоченную пару (Р, р), где
Р— непустое множество, а р — отношение, которое об-
ладает указанными тремя свойствами, то будем гово-
рить, что Ф является упорядоченным множеством*).
Иногда будем употреблять сокращенную запись: Ф есть
у. м. Множество Р называется носителем у. м. а отно-
шение р — упорядочением множества Р; элементы мно-
жества Р считаются элементами упорядоченного множе-
ства Ф. Для обозначения упорядочения на произвольном
множестве иногда употребляют символ (запись
читается «а предшествует Ьт> или «Ь следует за а») или
используют (если нет опасности непонимания) знак
(запись а Ь читается «а меньше или равно Ь» или
*) В научной литературе в этом случае чаще говорят о ча-
стично упорядоченном множестве, ибо некоторые элементы а и b
могут оказаться не сравнимыми, т. е такими, что ни (а,Ь), ни
(Ь. а) не лежит в р. В примере на с. 9 такими будут, скажем,
числа 2 и 3. — Прим. ред.
12
так же, как запись а С Ь). Выражение ат^Ь считается
равносильным выражению b а.
Пример 3. Возьмем в качестве множества Р открытый
интервал (1, оо) и для двух действительных чисел р, ц
будем писать р q тогда и только тогда, когда род,
имея в виду о, определенное в примере 2. Доказать, что
отношение является упорядочением множества
(1, оо).
Решение. Вследствие рассуждений, проведенных в
примере 2, достаточно установить антисимметричность
отношения Пусть а, Ъ — два числа из интервала
(1, оо) такие, что а < b и одновременно b С а. Тогда
из а :(а2 4- 1)^ b :(Ь2 4- 1)=^ а :(а2 4- 1), конечно, сле-
дует, что a :(а24- \ ) — Ь :(624- 1). Отсюда вытекает сна-
чала равенство
ab2 -j- а — Ьа2 4- Ь,
а затем
ab2 — Ьа2 — Ь — а,
что эквивалентно условию
ab (6 — а) = b — а.
Читатель, имевший дело с равенствами, содержащи-
ми параметр, хорошо знает, что без дополнительных рас-
суждений в подобных ситуациях нельзя поддаваться же-
ланию сократить равенство на число Ь — а. Как же то-
гда поступить? Наш опыт подсказывает, что нужно рас-
смотреть две возможности: Ь — а 0 или b — а = 0.
Если b — а ¥= 0, то обе части равенства можно разде-
лить на ненулевое число b — а, и тогда получается
ab = 1, что для наших чисел а, Ь, очевидно, невозмож-
но (ведь а ~> 1 и b > 1). Тогда единственной возмож-
ностью остается случай b — а = 0. Значит, а = Ь, и мы
доказали, что является на (1, оо) антисимметричным
отношением.
Пример 4. Для двух действительных чисел a, b > 1
будем писать axb тогда и только тогда, когда оба числа
ла:(а24- 1), л&:(624-1) принадлежат области опреде-
ления функции </ = tgx и при этом имеет место нера-
венство
13
Требуется найти такие подмножества М множества
(1, оо), на которых так определенное отношение яв-
ляется упорядоченностью.
Решение. Прежде всего, М должно быть непустым
подмножеством множества (1, оо). Отношение т, оче-
видно, при любом допустимом выборе М является реф-
лексивным и транзитивным. Теперь на время отвлечемся
от исследования отношения т. Для дальнейших рассуж-
дений нам понадобится следующее вспомогательное
предложение:
(3) Для любого действительного числа х выполняют-
ся неравенства
— — < х < —
2 хг + 1	2 ’
причем левое неравенство обращается в равенство тогда
и только тогда, когда х = — 1, а правое — тогда и толь-
ко тогда, когда х = 1.
Доказательство. Поскольку 0^(х—I)2 для
любого лей (и равенство здесь имеет место тогда и
только тогда, когда х=1), то 2х^х2+1, откуда
х:(х2+ 1)^ 1/2 (и равенство имеет место только при
х = 1). Положив х = — г, мы получим из доказанного,
что для любого г R справедливо
причем равенство возможно лишь в случае х = — z = 1,
так что для любого z е R будет
Z	1
23+1	2
и равенство достигается лишь при z = — 1. Этим завер-
шается доказательство истинности левого неравенства.
Читателю в качестве упражнения предлагается вывести
это неравенство непосредственно из неравенства
0<(х+ I)2.
Вернемся к исследованию отношения г. Из (3) видно,
что
Jt	Л
“ 2"^ aJ + 1 Т*
т. е. что па :(a2+ 1) принадлежит области определения
функции y = tgx тогда и только тогда, когда a ¥= ± 1.
Теперь легко установить, что отношение т на каждом
подмножестве М множества (1, оо) необходимо анти-
14
симметрично. Действительно, если axb и одновременно
Ьха, то
.ла . лЬ
а2 + 1 — Ь2 + 1 ’
а так как вследствие (3) и выбора М числа ла:(а2 + 1)
и яЬ : (b2 + 1) принадлежат интервалу (—л/2, л/2), мы
получаем ла :(а2 + 1) = л& :(й2+ 1), что, как было по-
казано в решении примера 3, влечет равенство а = Ь.
Условию, поставленному в примере 4, таким образом,
удовлетворяет любое непустое подмножество множества
(1, °о).
Задача 1. На множестве No всех неотрицательных
целых чисел определим отношение oi так, что (а, 6)е oi
тогда и только тогда, когда а | Ь. Докажите, что отноше-
ние ffi является упорядочением множества No.
Задача 2. Пусть Е — некоторое произвольное множе-
ство. Положим (М, /V) <= о2 тогда и только тогда, когда
McN и N cz Е. Докажите, что отношение о2 является
упорядочением множества всех подмножеств множе-
ства Е.
Задача 3. Отношение оз на множестве R всех дей-
ствительных чисел определим так, что (а, &)ес3 для
двух действительных чисел а, b тогда и только тогда,
когда а 1 или b — 1. Будет ли а3 отношением:
а) рефлексивным, Ь) антисимметричным, с) транзи-
тивным, d) симметричным?
[а) да, Ь) — d) нет.]
Задача 4. Исследуйте, будет ли отношение о, введен-
ное для действительных чисел в примере 2, определять
упорядочение на множестве:
а) [1, ос); Ь) (-1, 1); с) [-1, 1]; d) (-ос, -1];
е) (— ос, 0).
[а) — d) да, е) нет.]
Задача 5. Докажите, то выражение аоЬ в случаях Ь),
с) из задачи 4 эквивалентно неравенству а Ь, а в слу-
чаях a), d) —неравенству а Ь.
Пример 5. Для двух действительных чисел а, b пусть
а<цЬ означает, что
lg[(a- b) + V(a-fc)2+l]>0.
Нужно доказать, что асцЬ имеет место тогда и толь-
ко тогда, когда а Ь.
15
Решение. Поскольку для каждого действительного
числа х будет ^х2 + 1 > л/х2 = |х|, то х4- д/х2 + 1 >
>х + |х|>0, и поэтому выражение lg(х 4- ^х1 + 1)
определено для любого действительного числа х. Если
х>0, то х4~л/х2-)-1 >х4~1 > 1, откуда lg(x+V*2+l)>
> 1g 1 = 0. Еслих<0, положим x — — z. Из уже до-
казанного следует, что 0 < lg (z+ -\/z2 + 1) = lg(—*+
+ Vx24-1). Ho Beflblg(—х4-Ух24-1)+^(х4-л/х2-Ь1)=
= lg[(“ x+Vx2+0(x+Vx24"0] = lS 1 =0> и поэтому
0< lg(—x-|-Vx2+ 1)=— lg(x + Vx24- 1). Отсюда (при
исходном предположении х<0) будет 0>lg(x+Vx2+l).
Таким образом, мы	доказали (случай	х = 0 тривиален):
(i) Если	х > 0,	то	lg(x 4- л]х2 + 1	) > 0;
(И) Если	х < 0,	то	lg (х + V^2 + 1	) < 0;
(iii) Если	х = 0,	то	1g (х 4- Vx2+ 1	) = 0.
Предположим теперь, что число t таково, что
lg(/+ V/2+ 1)>0. Из (ii) видно, что не может быть
t < 0, а из (iii) заключаем, что невозможно и t = 0.
Остается единственная возможность t > 0. Отсюда (и из
аналогичных рассуждений в случаях (ii) и (iii)) выте-
кают следующие усиления предложений (i) — (iii):
(i') lg(x + Vx2 + 1) > 0 тогда и только тогда, когда
х > 0;	_____
(ii') lg(*+ V*2+ 1) < 0 тогда и только тогда, когда
х < 0;
(iii') 1g (х 4- Vx24-1) = 0 тогда и только тогда, когда
х — 0.
Теперь ясно, что
1g [(а - Ь) 4- У(а - Ь)2 4-1 ] > 0
тогда и только тогда, когда а — b 0, т. е. в том и толь-
ко том случае, если а Ь.
Решив задачу 2, мы увидим, что отношение включе-
ния является упорядочением множества Р(Е) всех под-
множеств множества Е или, другими словами, что упо-
рядоченная пара (Р(Е), сг) представляет собой упоря-
доченное множество. Попробуем наглядно представить
подобные упорядоченные множества, по крайней мере
16
в простейших случаях, при помощи подходящих диа-
грамм. Для этого заключим следующее соглашение.
Если ^ = (Р,	— упорядоченное множество, которое
имеет конечное число элементов, и если для двух его
О 0
Рис. 1.
о М
О 0
Рис. 2.
элементов а, b имеет место соотношение а 6, изобра-
зим оба элемента кружками, причем а расположим под
b и соединим их отрезком. Чтобы упростить диаграмму,
это соединение будем произво-
дить лишь в том случае, когда
а b и между а и b нет ни од-
ного другого элемента упорядо-
ченного множества, т. е. когда
а	и когда из того, что г Р
и а	г Ь, следует, что а = г
или г = Ь. В этом случае гово-
рят, что b покрывает а.	7
Для Е = 0 диаграмма изо-
бражена на рис. 1, для Е = {я}
см. рис. 2, для Е = {а, Ь} см.
рис. 3, диаграмма для случая Е=
= {а, 6, с} представлена на рис. 4.
Задача 6. Пусть л — некоторая плоскость, V — произ-
вольно выбранная точка на ней. Для двух точек Л, В на
л будем писать (Л,	в том и только том случае,
когда отрезки VA, VB имеют одинаковую длину. Полу-
чаем отношение 05 на множестве всех точек плоскости л.
Исследуйте его.
[Отношение сг5 рефлексивно, симметрично и транзи-
тивно, по оно не антисимметрично.]
Задача 7. Исследуйте отношение | («делит») на мно-
жестве Z всех целых чисел.
[Оно рефлексивно, транзитивно, но не является ни
симметричным, ни антисимметричным.]
Рис. 4.
2 Л. Бсран
17
Отношения Os и | оба рефлексивны и транзитивны.
Отношение р на непустом множестве Л4, являющееся
рефлексивным и транзитивным, называется квазиупоря-
дочением множества М. Отношение р на непустом мно-
жестве Л1, являющееся рефлексивным, симметричным и
транзитивным, называется эквивалентностью на множе-
стве М.
Упражнения
1.	Найдите все отношения на двухэлементном множестве {а, Ь).
2.	Среди отношений из у пр. 1 укажите
а)	все рефлексивные;
Ь)	все симметричные;
с)	все антисимметричные;
d)	все транзитивные.
3.	Постройте пример отношения, которое было бы симметрич-
ным и транзитивным, но не рефлексивным.
4.	Среди отношений из упр. 1 выделите
а)	все квазиупорядочения;
Ь)	все упорядочения;
с)	все эквивалентности.
5.	Найдите все эквивалентности
а)	на трехэлементном множестве {a, bt с) ;
Ь)	на четырехэлементном множестве {а, о, c,rf}.
Глава 2
РЕШЕТКИ: ОСНОВНЫЕ СВОЙСТВА
В дальнейшем нам потребуются понятия точной верх-
ней и точной нижней граней подмножеств носителя не-
которого у. м.
Будем говорить, что непустое подмножество М носи-
теля Р у. м. 9 = (Р,	) имеет в 9
точную нижнюю грань
тогда и только тогда, ко-
гда существует элемент Г,
который имеет следую-
щие три свойства:
(li)	/еР;
(2i)	i < m
для любого m e M\
(3i) если для некоторого
элемента i\ множества Р
неравенство i\ m не-
точную верхнюю грань
тогда и только тогда, ко-
гда существует элемент $,
который имеет следую-
щие три свойства:
(Is) seP;
(2s) tn s
для любого m M;
(3s) если для некоторого
элемента $i множества Р
неравенство $i m ис-
18
тинно при любом выборе
т пз М, то необходимо
ii I. Элемент i назы-
вается точной нижней
гранью множества М в
у. м. 5’.
Будем писать
i = inf^ Л!
тогда и только тогда, ко-
гда существует точная
нижняя грань множества
М в у. м. д* п она равна i.
тинно при любом выборе
т из М, то необходимо
s. Элемент s назы-
вается точной верхней
гранью множества М в
у. м. д*.
Будем писать
s = sup<!?Al
тогда и только тогда, ко-
гда существует точна я
верхняя грань множества
М в у. м. & и она равна s.
Символ inf читается «пнфимум», а символ sup —
«супремум».
К только что введенным определениям сделаем два
замечания. Прежде всего, для любого множества М,
0 ¥= Л! cz Р, существует не более одной точной ниж-
ней грани и не более одной точной верхней грани. В са-
мом деле, если для элемента / также выполняются усло-
вия (Ii) — (3i), то из (2i) и (3i) следует, что ii = / i,
а с другой стороны, те же требования (2i) и (35), рас-
сматриваемые для I, влекут неравенство i /. Посколь-
ку отношение антисимметрично, будет i = /. Подоб-
ные рассуждения можно провести и для точной верхней
грани. Далее отметим, что элемент d е Р такой, что
d для любого т е Л1, принято называть нижней
гранью множества М в у. м. д1. Аналогично элемент
Ле Р такой, что Л т для любого т из множества М,
называют верхней гранью множества М в у. м. Учи-
тывая это, условия (2i) и (3i) можно кратко сформули-
ровать следующим образом: от элемента i требуется,
чтобы он был нижней гранью множества Л-1 (см. (2i)) и
чтобы он был наибольшей нижней гранью этого множе-
ства (см. (3i)). Аналогично и условия (2s) и (3s) можно
представить в сокращенном виде, потребовав, чтобы
элемент s был наименьшей верхней гранью множества
М в д>.
Пример 6. Пусть Е={а, Ь} и пусть д>(Е) = (Р(Е), с)
есть упорядоченное множество, элементами которого яв-
ляются всевозможные подмножества множества Е, а в
качестве упорядочения выступает включение. Обозначим
Л12 = {{о}, {&}}, т. е. Л42 есть двухэлементное множество
2*
19
с элементами {а}, {Ь} (которые являются одноэлемент-
ными множествами). Требуется установить, существуют
ли точные грани множества М2 в у. м. 0(E), и получен-
ный результат обобщить.
Решение. Предположим, что точная верхняя грань
множества М2 в 0(E) существует, и обозначим ее че-
рез S. Согласно (1s) имеем Scf. Вследствие (2s) дол-
жно быть {а} с S и одновременно {6} az S, причем из
(3s) вытекает, что S есть наименьшее множество с та-
кими свойствами. Отсюда заключаем, что S = (а, Ь}.
Аналогичные рассуждения показывают, что точной ниж-
ней гранью множества М2 будет пустое множество 0.
Очевидно, что {а, Ь} является объединением множеств
{а}, {Ь}, а 0— пересечением множеств {а}, {Ь}.
Полученный результат приводит нас к следующему
предположению: если Е — некоторое множество и М,
N—два его подмножества, то
«>Р(Р (£),=)« ЛА-милг,
’4p(B).<=)W ПЛГ.
Это предположение будет доказано, если мы устано-
вим, что М (J ЛГ (соответственно М f| ЛГ) удовлетворяет
условиям (1s)—(3s) (соответственно (11)—(31)). Прове-
дем рассуждения для М (J N. Поскольку М U N az Е, тре-
бование (1s) выполнено. Так как AfazAfUAf и Na
с: М (J N, то истинно (2s). Если теперь Н — подмноже-
ство множества Е такое, чтоМсН hNcH, то MUVcz
с//, откуда и следует справедливость (3s).
Задача 8. Докажите, что для каждого одноэлемент-
ного подмножества {а} множества Р в любом у. м.
0 =(Р, ^) существуют sup^{a) и inf #{а}.
[В обоих случаях это будет элемент а.]
Пример 7. Пусть а, Ь — два натуральных числа. Тре-
буется установить существование нижней и верхней точ-
ных граней множества (а, Ь} в упорядоченном множе-
стве (ЛГо, (Ji) из задачи 1.
Решение. Обозначим через п (соответственно че-
рез d) наименьшее общее кратное (соответственно наи-
больший общий делитель) чисел а, Ь. Мы утверждаем,
что
п == SUP(*o, a.) <a> b}, d “ inU. a.) bY
20
Докажем первое равенство, а второе оставим чита-
телю в качестве упражнения. Прежде всего заметим, что
(1s) выполняется, поскольку для двух натуральных чи-
сел всегда существует натуральное число, являющееся
их наименьшим общим кратным. Далее, (2s) истинно,
поскольку а | п и также b | п. Наконец, и (3s) имеет место,
так как если натуральное число $1 таково, что a|$i и
b |st, то $! является общим кратным чисел а и Ь, и зна-
чит, п|$].
Задача 9. Докажите, что нижняя и верхняя точные
грани в (No, <Ti) существуют для любого двухэлемент-
ного множества {а, Ь}, где а, b — целые неотрицатель-
ные числа.
[Обратите внимание на то, что sup(Af ai) {0, а} = 0,
«} = «•]
/Множество Z не имеет в упорядоченном множестве
(Z, ни точной нижней, ни точной верхней граней, по-
скольку в Z не существует ни наибольшего, ни наимень-
шего числа. Не так легко убедиться, что верхняя или
нижняя точная грань не существует в некоторых других
ситуациях. Одна из них будет рассмотрена в нижесле-
дующем примере. При первом чтении мы рекомендуем
разобрать этот пример лишь в общих чертах, чтобы впо-
следствии вернуться к нему для более детального изу-
чения.
Пример 8. Пусть D обозначает множество тех поло-
жительных рациональных чисел q, для которых q2 > 2.
Нужно доказать, что в упорядоченном множестве
(Q, ^), где Q обозначает множество всех рациональных
чисел, множество D не имеет точной нижней грани.
Решение. Прежде всего докажем, что (i) для лю-
бого элемента q, принадлежащего D, существует элемент
q\t принадлежащий D, такой, что q{ < q. Для этого пред-
положим, что элемент q{ можно представить в виде
qx = q — е, где е — подходящее «малое» положительное
рациональное число. Элемент q\ должен принадлежать
D, и значит, должно быть истинным соотношение
2<(? — е)2, которое легко преобразуется к виду
2sq — г2 < q2 — 2. Мы потребовали выполнения этого
условия для подходящего положительного рацио-
нального числа е. Поэтому попытаемся получить бо-
лее простое условие, в которое не входило бы е2. Это мо-
жно сделать следующим образом: если выбрать е > 0
21
так, чтобы было 2e.q~< q2 — 2, то — так как 2eq — ъ2 <.
<. 2eq— будет выполняться и исходное соотношение для
е. Следующий шаг теперь очевиден: положим е =
= (q2— 2):(2q)*). Это положительное рациональное чи-
сло (проверьте), так как q по предположению рацио-
нально. Тогда число qi = q — 8 — (q2 + 2): (2q} принад-
лежит D, поскольку, проводя ниже рассуждение в об-
ратном порядке, мы получаем
q2\ — (q — е)2 = q2 — 2qe + е2 =
= ^-(^-2)+е2 = 24-82>2.
Далее покажем, что (ii) если d~^ 1—рациональное
число и d2 <.2, то существует рациональное число d\ та-
кое, что d <.d\ и d? < 2. Для доказательства этого
утверждения заметим, что 2<.(d + I)2, ибо d^z 1 вле-
чет за собой 2 < 4^(d + I)2, откуда 0<2— d? <.
<2d-f- 1. Поэтому, положив 81 = (2— d2):(2d + 1), по-
лучим 0< 8i < 1. Отсюда в2 <81, и, следовательно,
2dei + в? < 2de. 14- 8i = (2d +1) si = 2 — d2. Вследствие
этого для d\= d + 8i получаем d2 — (d + 8i)2 < 2. (Чи-
тателю, который впервые знакомится с подобными рас-
суждениями, нужно внимательно разобрать приведенное
доказательство утверждения (ii), чтобы увидеть, каким
образом (вспомним и доказательство утверждения (i))'
мы так удачно выбрали выражение для еь)
Докажем, наконец, что (iii) предположение о нали-
чии точной нижней грани множества De (Q, <) ведет
к противоречию. В самом деле, если бы d был элементом
со свойствами (li) — (3i), то, поскольку q> 1 для лю-
бого элемента q^D, было бы необходимо d 1. Если
бы имело место неравенство d2 > 2, то элемент d при-
надлежал бы D и согласно (i) существовал бы элемент
qi е D такой, что q\ < d, а это противоречит (2i). Если,
далее, допустить,что d2 — 2, rod = *J2, причем d должно
быть рациональным числом. Это противоречит хорошо
известному факту — иррациональности числа л/2.
Остается случай d2 < 2. Но согласно (ii) существует
элемент d\ такой, что d < di и d2 < 2, откуда сразу
d 1 < q2 для q е D, и значит, di < q для любого q D.
*) Заметим, что все предыдущие рассуждения имели наводя-
щий характер. Формальное доказательство можно начинать с этой
фразы. — Прим. ред.
22
Число d\ в этом случае тоже было бы рациональной
нижней гранью множества D и притом большей, чем
наибольшая нижняя грань этого множества. Это
противоречит (3i). Предположение о том, что множество
D имеет точную нижшою грань в (Q, ^). во всех слу-
чаях приводило к противоречию, поэтому указанная точ-
ная нижняя грань не существует.
Отметим, что в множестве R всех действительных чи-
сел inf(„ <}D существует и он равен д/2*-
Задача 10. Докажите следующие утверждения:
а)	не существует такого рационального числа s/t, где
s, /е Z, чтобы
10s// = 2;
Ь)	для любого натурального числа и имеет место не-
равенство
0< 101"* - 1
п
с)	если число q таково, что 10’> 2, то для любого
натурального числа п> 18: (10’ — 2) будет 2:10’<
< 10-'/«< 1;
d)	если рациональное число d таково, что 10d < 2, тэ
существует такое рациональное число q\, что q\ <. q и
одновременно 10’1 >2;
е)	если рациональное число d таково, что 10е* < 2, то
существует такое рациональное число d\, что d < di и
при этом 10d,<2;
f)	пусть Е— множество, элементами которого яв-
ляются в точности те рациональные числа q, для кото-
рых 10’> 2. Тогда в у. м. (Q, не существует точной
нижней грани множества Е;
g)	inf(/?.o£ = 1S2-
[Указания, а) Рассмотрите соотношение 5s = 2/_J,
где з, t принадлежат множеству N всех натуральных
(9
1 + — J .
10^	9	1
с) Покажите, что ----1 > —. d) Положите q{ = q — —,
где п> 18:(10’ — 2). е) Положите di = d-+--^-. где
m>9-10d:(2—10d), и докажите, что в этом случае
Ю1^ < 1 +(9:wi)<2-10-rf.J
23
Введем понятие наибольшего (наименьшего) эле-
мента упорядоченного множества. Будем говорить, что
элемент iе Р является
наибольшим элементом
у. м. ^Р=(Р, тогда и
только тогда, когда для
любого р е Р имеет ме-
сто р I. Наибольший
элемент у. м. 9 иногда
называют единичным эле-
ментом у. м. 9 и обозна-
чают, как правило, сим-
волом 1.
элемент о е Р является
наименьшим элементом
у. м. ^=(Р, тогда и
только тогда, когда для
любого ре Р имеет ме-
сто р <о. Наименьший
элемент у. м. 9 иногда
называют нулевым эле-
ментом у. м. 9 и обозна-
чают, как правило, сим-
волом 0.
Задача 11. Выясните, существует ли нулевой или
единичный элемент: а) в у. м. (N, ^), Ь) в у. м. (1Vo>oj)
(см. задачу 1).
[а) существует нулевой элемент и не существует еди-
ничный; Ь) существуют и нулевой и единичный эле-
менты.]
Если для любых двух различных элементов а, Ь упо-
рядоченного множества 9 = (Р, существуют как
sup^{a, Ь}, так и inf^{a, b}, то 9 называется решет-
кой*). Если для любого непустого подмножества М но-
сителя Р у.м. 9 = (Р, существуют как sup^Af, так и
inf^Af, то 9 называется полной решеткой.
Приведенные определения показывают, что каждая
полная решетка является решеткой. Из результата при-
мера 6 вытекает, что упорядоченное множество 9(E) =
— (Р(Е), с) является решеткой. В задаче 9 упорядо-
ченное множество ^о,01) также является решеткой. Из
примечания к этой задаче заключаем, что у. м. (Z,
не является полной решеткой. Однако решеткой оно бу-
дет, что легче всего вывести из следующих общих рас-
суждений.
Пусть 9 = (Р, есть некоторое упорядоченное
множество и для двух его элементов а, b пусть будет
а Ь. В этом случае условимся писать
m ах^ (a, b) = b, m in^> (а, b) = а
*) Употребляется также термин структура, используемый также
и в совершенно другом смысле. — Прим. ред.
24
и эти записи читать следующим образом: «максимум
(соответственно минимум) элементов а, Ь равняется Ь
(соответственно а)». Цепью называется упорядоченное
множество (/?, ^), в котором для любых двух элемен-
тов г, s будет г s или s г. Из уже знакомых нам
у. м. (N, ^), (Z, ^), (Q, ^), (R, являются це-
пями, а у. м. (No, 01) цепью не будет, поскольку в нем,
например, не выполняется ни 2013, ни 3oi2.
Пример 9. Пусть !Р=(Р, ^) есть у. м., и для двух
его элементов а, Ь пусть имеет место неравенство а Ь.
Нужно доказать, что
inf, {a, b} = min, (а, 6)
и
sup, {а, 6} = max, (а, Ь).
Решение. Приведем доказательство только пер-
вого соотношения, а проверку второго предоставим чи-
тателю. Прежде всего а = min, (а, Ь), и остается дока-
зать, что элемент а имеет свойства точной нижней грани
множества {а, Ь}. Истинность (li) очевидна. Поскольку
отношение рефлексивно, будет а а, а по предпо-
ложению а Ь, так что выполняется (2i). Если (Ц е Р
является нижней гранью множества {а, Ь}, то, конечно,
01 а и, значит, справедливо (3i).
Теорема 1. Каждая цепь является решеткой.
Доказательство. Поскольку для любых двух
элементов а, b цепи истинно а Ь или b а, то соглас-
но примеру 9 для любого двухэлементного подмноже-
ства из носителя цепи существуют как нижняя, так и
верхняя точные грани. Поэтому цепь является решеткой.
Из теоремы 1 следует, что у. м. (N, ^), (Z, ^),
(<?. <)> (*. О являются решетками. Точно так же ре-
шётками будут у. м. (D, ^) из примера 8 и у. м. (Е, ^)
из задачи 10. Однако ни одна из этих решеток не будет
полной, поскольку их носители не имеют точной нижней
грани.
Следующее предложение помогает сравнительно про-
сто распознавать, будет ли данное у. м. полной решеткой.
Теорема 2. У. м. 0 = (Р, ^). является полной решет-
кой тогда и только тогда, когда для любого непустого
множества МсР существует inf,A4 и у. м. fR имеет
наибольший элемент.
25
Доказательство. 1) Предположим, что выпол-
нено условие теоремы. Прежде всего докажем, что для
любого непустого подмножества М с Р существует
sup^JW. Обозначим через Н множество тех элементов
Л е Р, для которых при любом выборе т е Л1 будет
т 1г (таким образом, И состоит из всевозможных
верхних граней множества Л1). Множество Н не пусто,
поскольку наибольший элемент у. м. 53, очевидно, при-
надлежит Н. По предположению, существует
который обозначим через to. Если выберем т е М, то
т /г выполняется для любого /1 е Н. Тогда, согласно
(3i), получаем т to- Так что элемент / о е Р обладает
свойствами (1s) и (2s). Покажем, что он имеет и свой-
ство (3s). Действительно, если т ii для любого
т е М, то ii е Н, а поскольку to является точной ниж-
ней гранью множества Н, свойство (2i) влечет неравен-
ство to^ii, что и означает истинность (3s). Итак, мы
доказали, что ^«sup^Al.
2) Если &— полная решетка, то непосредственно из
определения следует существование упомянутых в усло-
вии точных нижних граней. Поэтому же существует
i = supj,P, а поскольку в следствие (2s) этот элемент
таков, что для любого реР, мы видим, что Ф
имеет наибольший элемент.
Пример 10. Показать, что у. м. ^(Е) = (Р(Е), cz) из
примера 6 является полной решеткой.
Решение. Для решения используем теорему 2.
Наибольшим элементом у. м. SP(E) является, очевидно,
Е. Если М — непустое множество подмножеств А, В, ...
множества Е, то / = inf^ (£)Л4 должно быть подмноже-
ством множества Е, содержащимся во всех подмноже-
ствах А, В, ... (этого требует условие (2i)), и если при
этом подмножество Л множества Е содержится во всех
подмножествах А, В....то Л должно быть подмноже-
ством множества I (этого требует условие (3i)). Этим
требованиям, очевидно, удовлетворяет множество, эле-
ментами которого являются те и только те элементы мно-
жества Е, которые принадлежат всем подмножествам
А, В, ..., т. е. пересечение всех этих подмножеств.
Пример 11. Пусть E(N) обозначает множество всех
эквивалентностей на множестве W #= 0. Требуется дока-
зать, что упорядоченное множество (E(N), с) является
полной решеткой.
26
Решение. Убедимся, что выполняются условия тео-
ремы 2. Наибольшим элементом является такая эквива-
лентность ро, что ПфоПг для любых двух элементов
п.\, ni^N (т. е. ро = УХЛО. Если М — непустое мно-
жество эквивалентностей р, а, ... на множестве N, то су-
ществует inf(£(W) С)Л1. Действительно, определим отно-
шение х на М так, что «ixn2 тогда и только тогда, когда
для любых эквивалентностей р, а, ... из М истине»
П1РП2, Я1ОЯ2, ••*)• Легко заметить, что х будет эквива-
лентностью. Например, транзитивность отношения х про-
веряется так: если «ixn2 и п2хп3, то для всех отношений
р, о, ... одновременно /iipn2, n2pn3, «1<тп2, л2<тп3, ... а
поскольку р, <т, ... — транзитивные отношения, то
rtipn3, пхвпз, ..., откуда и следует njxn3. Условие (2i)
для х перепишется следующим образом: должно
тер, т со........Но что означает, например, включение
х сс р? Оно означает, что из соотношения (tti, л2)ет
всегда следует соотношение (ni, п2) е р. В другой за-
писи: П1хя2 влечет nipn2, но это сразу следует из опреде-
ления х. Перепишем теперь условие (3i): если одновре-
менно Xi az р, Xi с: а...то должно быть xi с х. Выбе-
рем п3, так, чтобы (я3, я4)е хь Нужно доказать,
что необходимо (л3, гц) е х. Но из соотношений
(п3, л4) <= х и xi с: р следует, что (я3, п4)е р, т. е. /13рп4,
и аналогично получим, что л3ал4, ..., т. е. л3тл4. Итак,
мы доказали, что х является точной нижней гранью мно-
жества М в у. м. (E(N), сс)**).
Упражнения
1.	Начертите диаграмму у. м. (Nt 6) (см. стр. 9).
2.	Используя результат упражнения 1 из главы 1, постройте
диаграмму у. м., носителем которого является множество всех от-
ношений на двухэлементном множестве (а, Ь}, а упорядочением —
включение.
3.	Докажите, что всевозможные отношения на множестве Af,
будучи упорядочены включением, образуют полную решетку.
4.	Установите, будут ли при упорядочении включением обра-
зовывать полную решетку
*) Другими словами, т определяется как пересечение всех экви-
валентностей из М, рассматриваемых как подмножества множества
N X.N. — Прим. ред.
**) Интересно заметить, что sup(£(W) С)М, хотя и существует,
но не совпадает с объединением эквивалентностей из М, рассмат-
риваемых как подмножества множества N X.N. Покажите это на
примерах. — Прим. ред.
2/
а)	все рефлексивные;
b)	все симметричные;
с) все антисимметричные;
d) все транзитивные
отношения на данном множестве М.
5.	Выясните, будут ли
а)	вес квазиупорядочения;
Ь)	все упорядочения
па данном множестве образовывать при упорядочении включением
полную решетку.
6.	Используя результаты упражнения 5 из первой главы, по-
стройте диаграмму решетки (£(V),c:) в случае, когда
b) N — {a, b, c,d}.
7.	Пусть / обозначает множество всех рациональных чисел из
замкнутого интервала [1, 2]. У. м. (/, не является полной ре-
шеткой. Докажите.
Глава 3
ПРИМЕРЫ РЕШЕТОК
В этой главе мы пополним основные сведения о ре-
шетках и рассмотрим некоторые примеры, которые мож-
но отнести к школьной математике.
В предыдущей главе мы определили решетку как
упорядоченное множество ^=(Р, ^), в котором для
любых двух элементов a, b е Р существуют sup^{a, b}
и inf^{a, b}. Обе эти записи достаточно ясно выра-
жают, какие элементы соответствуют паре а, Ь, но они
неудобны своей громоздкостью. Поэтому в теории реше-
ток принято соглашение вместо sup^{a, Ь} писать aV6,
а вместо inf^{a, b} писать а ЛЬ. В том случае, когда
а = 6, эти определения расширяют, полагая а V а =
= а Л а = а. Запись с = а V Ь (соответственно d =
= а Л Ь) читаем: «с равно объединению а и 6» (соот-
ветственно «d равно пересечению а и 6»). Элемент с на-
зывается объединением элементов а и 6, элемент d назы-
вается их пересечением.
Пример 12. Пусть Е обозначает трехмерное простран-
ство, L(E)—множество, элементами которого являются
Е, 0 и всевозможные плоскости, прямые и точки про-
странства Е. При этом прямые, плоскости и простран-
ство понимаются как множества точек, а точка как одно-
элементное множество точек. Нужно доказать, что
(L(E), cz) является полной решеткой.
Решение. Снова используем теорему 2. Очевидно,
что Е является наибольшим элементом рассматривае-
28
мого у. м. Если М — некоторое множество геометриче-
ских объектов из Е, то обозначим через Д множество
всех точек, которые принадлежат всем множествам из
М. Мы хотим показать, что ЬеЦЕ). Это очевидно,
если Д = 0 или Д содержит единственную точку. Если Д
Рис. 6.
содержит две различные точки Л и В, то эти точки со-
держатся в каждом из геометрических объектов, принад-
лежащих М, а поэтому каждый такой объект содержит
и прямую р, определяемую ими. Далее, если Д содержит
еще одну точку С, не лежащую
на р, то Д содержит, как мож-
но увидеть, рассуждая анало-
гично, и все точки плоскости а,
определяемой точкой С и пря-
мой р. Если же в Д содержит-
ся точка D, которая не лежит
на плоскости а, то Д содержит
и все точки пространства Е.
В каждом из этих случаев
Де£(£), и легко заметить,
что Д = inf(L (£)> с) М. Согласно
теореме 2 (£(Е), с) будет
полной решеткой.
В только что рассмотрен-
ном примере обратим внима-
ние на то, что объединение Л V В
рис. 5) есть прямая р, пересечение прямых р и q совпа-
дает с точкой В и т. д. Этот пример иллюстрирует гео-
метрическое истолкование используемых терминов.
В решетке, диаграмма которой изображена на
рис. 6, выполняются, например, соотношения с /\f = g,
точек А и
В
(см.
39
6V Л = 1. Вообще пересечения и объединения в этой
решетке задаются следующими таблицами:
V Oabcdefghl
О Oabcdefghl
a aabchhlbhl
b	b	b	b	с	1	1	1	b	1	1
с	с	с	с	с	1	1	1	с	1	1
d	d	h	1	1	d	e	f	f	h	1
e ehlleeffhl
f	f	1	1	1	f	f	f	f	1	1
Л	h	h	1	1	h	h	1	1	h	1
1 1111111111
Oabcdefghl
0 0000000000
a 0aaa0000aa
b OabbOOggab
c OabcOOggac
dOOOOdddOdd
e OOOOdeeOee
fOOggdefgef
g OOggOOggOg
h OaaadeeOhh
1 Oabcdefghl
Задача 12. В каждой решетке 5’=(Р, sC) для всех
a. b, се Р истинны следующие соотношения:
a)	aVb = b\/a, аЛЬ = ЬЛа;
b)	(а V &)V с = а V (6 V с), (а Л b) Л с = а Л
Л{Ь Л с) ♦);
с)	если а Ь, то а Л b = а и b = а V Ь',
d)	аЛ b а, а а V Ь;
е)	а V(а Л Ь)= а, а Л(а V Ь) — а;
f)	если а Л b = а У Ь, то а = Ь.
[Указание. В доказательстве е) используйте d) и
с), а свойство f) выведите с помощью d).]
Пример 13. Пусть С(р) будет множество всех откры-
тых кругов на плоскости р. При этом пустое множество
также будем считать открытым кругом. Нужно вы-
яснить, будет ли у. м. (С(р), с) решеткой.
Решение. Собственно решению предпошлем сна-
чала следующие рассуждения. Пусть М, N будут два
круга (см. рис. 7) и пусть Н, D — круги, ограниченные
окружностями, касающимися одновременно окружностей
обоих кругов М и N. Очевидно, что N с Н и М cz Н;
аналогично РсдЛ! и Dai\. Отсюда следует, что Н яв-
ляется верхней гранью множества {М, N}, a D — нижней
гранью этого множества. Рассмотренный рисунок на пер-
вый взгляд настолько убедителен, что можно было бы
подумать, будто Н является наименьшей верхней гранью
*) Доказательство см. в «Приложении», предложение 1.
30
множества {At, N}, a D — его наибольшей нижней
гранью, т. е. можно было бы подумать, что у. м.
(С(р), cz) является решеткой. Поучительно, что рассмо-
трение этого рисунка ввело в заблуждение даже извест-
ного популяризатора современной математики профес-
сора Папи ([10], стр. 130, упр. 5). Заметим, что на са-
мом деле для упомянутых кругов М, N точная верхняя
грань множества {At, N} в у. м. (С(р), с) не существует.
Рис. 8.
Если бы некоторый круг S был точной верхней гранью
множества {М, N}, то каждая его точка должна была
бы лежать внутри острого угла, определяемого касатель-
ными 6 и /г (рис. 8). Чтобы это доказать, обозначим
31
через С и D точки пересечения касательной ti с окруж-
ностью h круга Н, а через Е и F точки пересечения каса-
тельной ti с той же окружностью. Пусть Oi (соответ-
ственно 02) обозначает перпендикуляр, восставленный
из середины отрезка CD (соответственно EF), Pi (соот-
ветственно Р2)—точку пересечения окружности h с пря<
мой Oi (соответственно 02), Si (соответственно S2)—се-
редину отрезка CD (соответственно EF). Возьмем точку
X (соответственно Y) на отрезке Pi$i (соответственно
P2S2). Окружность определяемая точками С, X, D
(соответственно окружность т|г, определяемая точками Е,
Y, F), ограничивает круг Кх (соответственно Lr), кото-
рый содержит круги М и N и потому должен содержать
круг S. Таким образом, круг S должен принадлежать
кругам Кх н Ly при любом выборе точки X на отрезке
Pi$i и точки Y на отрезке P2S2, а значит, и пересечению
всех таких кругов. Нетрудно доказать (докажите!), что
для всякой точки Z, не лежащей внутри острого угла
СРЕ, можно подобрать точки X и Y так, чтобы точка Z
не попала в пересечение кругов Кх и Ly. Следовательно,
пересечение всех таких кругов, а значит, и лежащий в
этом пересечении круг S, лежит внутри острого угла СРЕ.
Это, однако, не совместимо с тем, что круг S должен со-
держать круги М и N.
Задача 13. Опишите множество точек, которые принад-
лежат всем кругам, содержащим оба круга М, N, на рис. 8-
[Это будут в точности те точки, которые лежат в за-
штрихованной области.]
Пример 14. Пусть снова р— некоторая плоскость, ко-
торую мы будем рассматривать как множество точек.
Подмножество М плоскости р называется выпуклым то-
гда и только тогда, когда для любой пары точек X, Y из
М весь отрезок XY лежит в М *). Обозначим через К(р)
множество всех выпуклых подмножеств плоскости р. Ну-
жно доказать, что (К(р), с:) является полной решеткой.
Решение. Проверим, что выполняются условия тео-
ремы 2. Наибольшим элементом у. м. (К(р), с) яв-
ляется, очевидно, вся плоскость р. Если М — некоторое
непустое множество выпуклых подмножеств А, В, ..., то
их пересечение состоит из тех точек плоскости р, кото-
рые принадлежат всем подмножествам А, В, ... . Так
как эти подмножества все являются выпуклыми, то из
*) Детальное изучение понятия выпуклого множества читатель
найдет в интересной книжке И. М. Яглома и В. Г. Болтянского [8].
32
принадлежности точек X, Y их пересечению следует, что
отрезок XY принадлежит всем подмножествам А, В.........
а значит, и их пересечению. Отсюда уже легко получает-
ся, что упомянутое пересечение является точной нижней
гранью множества М.
Пример 15. Доказать, что у. м. {No, oj из задачи 1
является полной решеткой.
Решение. Используем теорему 2. При упорядоче-
нии Oi число 0 является наибольшим элементом у. м.
(No, Oi). Пусть М — некоторое непустое подмножество
множества No, а С обозначает множество всех тех чисел
из No, которые делят все числа из М. Конечно, С =/= 0,
поскольку 1 е С. Если М = {0}, обозначим число 0 бук-
вой d. Если М — подмножество, которое содержит по
крайней мере одно натуральное число, скажем а, то
буквой d обозначим наибольшее из чисел, принадлежа-
щих С (наибольшее в смысле обычного упорядочения ^);
d существует, поскольку мы должны делать выбор
из делителей числа а, а их конечное число. Мы утверж-
даем, что d является точной нижней гранью множества
М при упорядочении сть Прежде всего, по определению
d, имеем daitn, каким бы ни было т е М. Если для не-
которого di также имеем diOi/n при любом me М, то
каждое me М будет кратным наименьшего общего
кратного k чисел d и d\. Поэтому d k, а так как мы
только что видели, что k е С, то согласно выбору d
имеем d — k. Поскольку всегда d\Q\k, мы получаем, что
d\ts\d, а потому имеет место (3i), чем и завершается до-
казательство существования в (ЛГ0, oi) точной нижней
грани множества М.
Теперь рассмотрим два способа, которые позволяют
превратить данную плоскость в упорядоченное множе-
ство. Будем предполагать, что на этой плоскости задана
прямоугольная система координат. Каждой точке пло-
скости она сопоставляет упорядоченную пару (п, гз),
составленную из координат и, гз этой точки.
Пример 16. Для двух пар (и, r2), (si, 5г) действитель-
ных чисел пишем (ri, r2)	($i, s2) тогда и только тогда,
когда имеет место одна из следующих ситуаций:
(i)	(и, r2) = (si, «г)*);
(ii)	ri < Si;
(iii)	г। = si и r2 < s2.
*) Это равенство означает, что n = Si и одновременно п = s2
33
Исследовать так определенное отношение С.
Решение. Согласно (i) отношение рефлексивно.
Это отношение и антисимметрично. Действительно, если
(И, Гг) (si, $2) и одновременно (Si, S2)<^Ui, гг), то ка-
кие бы из ситуаций (i) — (iii) ни имели места — всегда
Л и Si л, откуда Si = rt. При этом случай (Hi)’
не может одновременно появиться в обоих рассматри-
ваемых неравенствах, поскольку тогда было бы r2 < s2
и s2 < г2, что невозможно. Значит, представляется един-
ственная возможность — случай (i). Отношение <С тран-
зитивно. В самом деле, если (п, г2) (si, s2) и (si, s2) С
С (6, h), то при (г1( г2) = ($1, $2) или при (Si, s2) =
— (ti, h) будет (л, г2)«С(Л, /2). Если же (и, г2)^($ь s2)
и (<st, s2) ф (Л. 6), то либо, по крайней мере, одно из чи-
сел t\ — si, Si — ri положительно, и тогда — п —
= (6 — $1)4-($i — п)> 0, что вследствие (ii) дает
(п, г2) <(6, /2), либо оба эти числа равны нулю, откуда
6 = П, но t2 — т2 = (t2 — s2) + (s2 — г2) будет суммой
двух положительных чисел, т. е. t2 > г2, и потому
(И, r2)<^(tit t2). Так как вследствие (i)—(iii) при любом
выборе (л, r2), (st, s2) всегда будет (п, r2)^(si, $2) или
($i, s2)	(л, гг) , то получается цепь, которая по тео-
реме 1 является решеткой.
Упорядочение С называется лексикографическим.
Задача 14. Пусть обозначает лексикографическое
упорядочение точек плоскости и пусть А = (а, Ь) есть не-
которая точка этой плоскости. Найдите множество всех
таких точек X = (х, у), которые удовлетворяют неравен-
ству A <g. X.
[Это те точки X, для которых а < х, и точки луча
х = а, b у.]
Задача 15. Опишите множество точек X, которые од-
новременно удовлетворяют неравенствам А X и
X В, где А = (а, Ь), В =(с, d) суть две произвольно
выбранные точки.
[Указание. Выделите случаи а = с, а <. с.]
Задача 16. Пусть Л=(а, Ь)—данная точка плоско-
сти р. Определите все прямые р плоскости р, которые об-
ладают тем свойством, что для любой их точки В вы-
полняется В А.
[Это будут в точности все прямые, параллельные оси
у и имеющие уравнение х = е, где е < а.]
Задача 17. Для двух пар (гь г2). ($1, $2) действитель-
ных чисел определим (и, r2)^(si, «2) тогда и только
34
тогда, когда и и одновременно г2 С $2. Докажите,
что отношение задает на множестве всех пар (гь г2)
упорядочение и что получающееся у. м. является решет-
кой, в которой
(И, r2) V (sb $2) = (тах(гь $i), max(r2, $2)),
(гь г2) Л ($ь s2) = (min(ri, $0, min(r2, s2)).
Пример 17. Обозначим через Q множество всех квад-
ратных трехчленов х2 + рх + q с действительными коэф-
фициентами, для которых дискриминант А = п2— 4q
неотрицателен. Для двух квадратных трехчленов
х2 + pix + qi, i = 1, 2, принадлежащих Q, будем писать
Л'2 + PiX 4- <72 < х2 + ррс + qi
тогда и только тогда, когда
Р1 — Р2>| V^l
V Л2 |>
где А. = р? — 4q.. Исследуем отношение «С.
Решение. Сначала докажем, что отношение «С яв-
ляется упорядоченностью множества Q. Сразу отметим,
что это отношение очевидным образом рефлекспвно._Оно
также_симметрично, поскольку_если Pi — р2 I
— д/Д21 и р2 — Pj >| УД2 — д/Ai |, то pi — р2 0 и
Р2 — Pi 0, т. е. pi = р2, и потому — д/А2 = О, от-
куда следует, что q\ = q^_ Отношение транзитивно,
так как из Pi — р2 I — V^21 и р2 — Рз I V^2_—
—У&з| получается, nropi—Рз=(Р1—Р2ЖР2—Рз)>1
— л/Дг1 + I УДг — УДз Is^l V^i — УДз |; на последнем
шаге применяется неравенство треугольника.
Получим еще следующую наглядную характериза-
цию отношения неравенство х2 + Рг* + <7г	& +
+ р\х + qi выполняется тогда и только тогда, когда для
корней al Pj многочлена х2 + р\х + q\ и корней
а2 р2 многочлена х2 + Ргх + qz имеют место неравен-
ства а2 ой и р2 Рь Чтобы доказать это, заметим, что
соотношение Pi — р2^ I	1 равносильно одно-
временной выполнимости неравенств
Pl —Р2> 7^2— VAt
И Pl — Р2> УД1 — л/Дг,
35
т. е. равносильно одновременной выполнимости соотно-
шений
ai =
Р1
— Pi — УД? — рг — УДд „
2	2
и
— Р\ + Уд? — РъЛ- УД7
2^2
₽2.
Используя результат задачи 17, получаем, что и
здесь упорядоченное множество является решеткой.
В ней для трехчленов № 4- р3х 4- q3, х2 4- р4х 4- q4 с кор-
нями аз ₽з и а4 гС ₽4 объединение
x2+p3x + q3 V x2 + pix + q4
(соответственно пересечение х2 4- Рзх 4- <7з Л х2 4- р4х4-
4- qfi будет совпадать с трехчленом х2 4- р3х 4- qs (соот-
ветственно х2 4- рзх 4- <7в), имеющим корни аз =
= тах(а3, а4) Ps = max(p3, р4) (соответственно имею-
щим корни а6 = min (а3, а4) Ре = min (Р3, Р4)).
Значит,
а заменяя в этих формулах символ max символом min,
получим формулы для рб, q&-
Упражнения
1.	Для кругов М, W на рис. 7 в у. м. (С (р),=>) точная нижняя
грань множества {MtN} не существует. Докажите.
2.	Докажите, что если Къ Хг —два круга в смысле примера 13»
причем К\ =£ 0 и Кг Ф 0, то существует в точности один круг X»
который содержит К\ и Кг и имеет наименьший радиус.
3.	Докажите: если К\, Кг — два круга из примера 13, пересече-
ние которых не пусто, то существует в точности один круг К, ко-
торый содержится в Ki и Кг и который имеет наибольший
радиус.
36
4.	Выяснить, образует ли решетку (соответственно полную ре*
шетку) множество &(р, р) всех кругов, центры которых лежат на
данной прямой р (включая пустое множество), упорядоченное вклю-
чением (ср. с примером 13).
5.	Подмножество М некоторой плоскости назовем звездчатым
тогда и только тогда, когда оно удовлетворяет следующему условию
(см. рис. 9): в М существует по крайней мере одна точка S такая,
что вместе с каждой точкой X из М в М
лежит и весь отрезок SX. Например, фигу-
ра ABCGFED представляет собой звездча-
тое множество. Обозначим через Я(р) мно-
жество всех звездчатых множеств плоско-
сти р. Установите, будет ли (Я(р),с=)
а) упорядоченным множеством, Ь) решет-
кой, с) полной решеткой.
6.	Обозначим через F(R) множест-
во, элементами которого являются всевоз-
можные последовательности аь аг, ...
... ал, ... действительных чисел (краткая
запись последовательности {а,}). Для двух
последовательностей а = {oj, b — {bi} будем
писать а b тогда и только тогда, когда
сц bi для любого i е N. Выясните, будет
рядочеиным множеством, Ь) решеткой, с) полной решеткой.
7.	Докажите, что в каждой решетке 0* = (Р, ^):
а)	если k h и п гп, то k V п h V tn\
b)	если h и d2 ht то d{ X/ d2 h;
с)	если c d, то для любого g^ P будет с V g d V g-t
d)	если k	h и n	m, to k Л n	h А
e)	если d	h{ и d	Л2, to d	A h2\
f)	если c d, то для любого g e P будет c A g d A g.
8.	Докажите, что в каждой решетке 0* для любых элементов
а, Ь, с е Р:
а)	а V (6 А с) (а V Ь) А (а X/ с);
Ь)	а А (6 V с) >(а А Ь) V(а А с);
с)	если а с, то а У (Ь А с) (а V Ь) Ас.
Глава 4
ОСНОВНЫЕ КЛАССЫ РЕШЕТОК
В задаче 12 мы установили, что в каждой решетке
9 = (Р, для любых а, Ь, с из Р выполняются
условия
(SI)	а у Ь = ЬУ
(S2)	(а V b) V с = а V (& V с);
(S3)	аУ (а/\Ь) = а;
(Р1)	адЬ = Ьда;
(Р2)	(а Д Ь) Д с = а Д (Ь Д с);
(РЗ)	а Д (а УЬ) = а.
37
Можно доказать*) и обратное: если на некотором
непустом множестве Р определены две операции Л, V
так, что выполняются условия (S1)—(S3) и (Р1) — (РЗ),
и если ввести отношение полагая а b тогда и
только тогда, когда а Л b = а, то это отношение упо-
рядочивает множество Р и (Р, ^) оказывается решет-
кой. Учитывая это, часто о решетке Ф=(Р, ^) говорят
как о решетке !Р=(Р, V, Л). Например, в решетке
<Р=(Р(Е), cz) операциями являются U, Л (объединение
и пересечение), и ее записывают так же как тройку
<Р(Е)==(Р(Е),и,Л)-
Если возьмем в решетке 0>(E) = (P(E), U, Л) три
множества А, В, С, принадлежащие Р(Е), то
лл(вис)=(ллв)и(ллс)
и
Ли(ВЛС) = (ЛиВ)Л (Лис)
(приведем краткое доказательство первого соотношения:
элемент х принадлежит множеству А Л (В U С) тогда и
только тогда, когда он принадлежит А и одновременно
принадлежит В или С, т. е. когда он принадлежит Л Л В
или 1 Л С- Впоследствии мы увидим, что второе соотно-
шение является следствием первого и того факта, что
^Р(Е) является решеткой).
Решетка 0—(Р, \/, А) называется дистрибутивной
тогда и только тогда, когда в 0 для любых а, b, с е Р
(4) а Д (ft V с) = (а Д 6) V (а А с)
н
(5)	aV(&Ac) = (aV&)A(aVc).
Согласно этому определению ^(Е) = (Р(Е), U. Л) яв-
ляется дистрибутивной решеткой.
Будем говорить, что непустое подмножество М
носителя Р решетки Ф замкнуто относительно операций
V и А тогда и только тогда, когда для любых т, п, при-
надлежащих М, этому подмножеству принадлежат так-
же т \/ п и т А п. Упорядоченная тройка (Л4, \/, Л) в
этом случае называется подрешеткой решетки (Р, V, А)
(или решетки (Р, ^)). Множество М называется носи-
телем этой подрешетки. Поскольку для любых трех эле-
ментов а, Ь, с из М выполняются условия (S1) — (S3) и
*) См. «Приложение», предложение 2.
38
(Pl) — (РЗ), каждая подрешетка является и решет-
кой.
Пример 18. Пусть Е обозначает некоторое непустое
множество. Обозначим через F(E) множество всех тех
подмножеств множества Е, которые имеют конечное чи-
сло элементов. Нужно доказать, что (F(E), J, П) являет-
ся подрешеткой решетки 0(E).
Решение. Очевидно, 0&F(E), и потому F(E) не
пусто. Если Ft, F2— два множества, принадлежащие
F(E), то множества Fi U F2, F\ П F2 имеют конечное чи-
сло элементов, т. е. принадлежат F(E).
Задача 18. Пусть & есть решетка с диаграммой, изо-
браженной на рис. 10. Установите, будет ли множество
а)	М1 = {0, е, f, g, h};
b)	M2 = {0, a, b, c, d, 1};
c)	Af3 = {0, e, f, 1}
носителем какой-либо подрешетки решетки f?.
(а), Ь) да, с) нет, поскольку ft = eV f ф. Л13.]
Пример 19. Пусть р— некоторая плоскость трехмер-
ного пространства Е (см. пример 12) и пусть Л(р; 7)
обозначает множество, элементами которого являются,
Рис. 11.
в том же смысле как и в примере 12, плоскость р, любая
заданная точка Г плоскости р и все те прямые р плоско-
сти р, которые проходят через точку Г (рис. 11). Нужно
39
доказать, что /?(р; 7) является носителем подрешетки
решетки (L(E), с).
Решение. Пересечение и объединение элементов
непустого множества /?(р; 7) снова будет элементом
этого множества.
Пример 20. Доказать, что если в решетке Ф тожде-
ство (4) выполняется для всех а, b, с е Р, то в Ф выпол-
няется и (5).
Решение. В самом деле,
(а V 6) Л (« V [(а V Ь) Л а) V [(а V Ь) Л с] — (согласно (4))
= а V 1(<1 V t) Л с] =	(согласно (РЗ)
н (Р1>)
= а V [(« Л г) V (4 Л с)]—	(согласно (4))
= (а V (а Л c)J V (4 Л с) “	(согласно (S2))
= а V (6 Л ()	(согласно (S3))
Замечание. Если мы в списке условий (S1) — (S3) и
(Р1) — (РЗ) заменим символ V на Л и обратно, то по-
лучится снова тот же список. Отсюда следует, что если
мы произведем такую замену в некотором утверждении,
истинном во всех решетках, то получим снова истинное
утверждение. Эта замена называется дуализацией ис-
ходного утверждения. Например, дуальным для утверж-
дения из примера 20 будет утверждение о том, что в
любой решетке тождество (4) является следствием тож-
дества (5).
Пример 21. Нужно доказать, что если решетка Ф со-
держит подрешетку с диаграммой, подобной одной из
двух диаграмм, изображенных на рис. 12, а и 12, Ь, то ф
не дистрибутивна.
Решение. Действительно, а V (b 'Л с) — а V 0 = а,
но (а V Ь) Л(а V с) — i Л(а V с) = а V а.
40
Замечание. Можно доказать*), что если решетка 9
не дистрибутивна, то она содержит подрешетку с диа-
граммой, подобной одной из двух диаграмм на
рис. 12, а, Ь.
Пример 22. Доказать, что каждая цепь является дис-
трибутивной решеткой.
Решение. По теореме 1 цепь является решеткой.
Вследствие примера 20 достаточно установить, что
а Л(Ь V с) = (а Л 6) V (а Л с) для любых трех элемен-
тов а, Ь, с цепи. Пример 9 сводит это к доказательству
того, что элемент I ==min(a, max(Ь, с)) равен элементу
р = max (min (a, b), min (а, с)). При этом из определе-
ния минимума и максимума, очевидно, что I есть один из
элементов а, Ь, с. Если I — а, то а max(b, с) (см.
»---------------1
I
I
I
I
С^тах(Ь'С)____ |
Рис. 11
рис. 13), а тогда будет а Ь или а с. Но в обоих
случаях по крайней мере один из элементов min (а, Ь),
min (а, с) равен а, а другой меньше или равен а, т. е.
р= а.
Если I = Ь, то будет Ь = а и р = max(b, min(b, с)),
либо b = тах(&, с) и одновременно b а. Но это озна-
чает, что с b а, и тогда р = max (6, с)= Ь. Подоб-
ным образом поступаем и в случае I = с.
Задача 19. Два элемента а, Ь решетки 9=(Р, ^)
называются сравнимыми тогда и только тогда, когда
а Ь или Ь а. Не используя примера 22, докажите,
что если один из трех элементов а, Ь, с решетки 9
сравним с каждым из двух остальных элементов, то
а Л (6 V с)—(а Л Ь) \/ (а Л с) и а \/(Ь Лс]=(а \/Ь)Л
7\(а V с).
[Указание. Докажите, что наименьшая подрешет-
ка решетки 9, которая содержит элементы а, Ь, с,
должна иметь такую же диаграмму, как решетка
9({а, Ь}) — (Р({а, Ь}), с:), либо должна быть цепью и
*) См. «Приложение», предложение 6.
41
иметь диаграмму такую же, как подрешетка решетки
&({а, Ь}) с носителем {0, {а}, {а, 6}}. Подрешетка дис-
трибутивной решетки дистрибутивна.]
Задача 20. Используя результат задачи 19, дайте
другое доказательство утверждения примера 22.
Пример 23. Выяснить, будет ли решетка (No, Oi) из
задачи 1 дистрибутивной.
Решение. В примере 7 мы доказали, что точная
верхняя (соответственно точная нижняя грань) двух-
элементного множества а, Ь чисел из N совпадает с их
наименьшим общим кратным (соответственно с их наи-
большим общим делителем). Для доказательства дис-
трибутивности согласно примеру 20 достаточно прове-
рить истинность (4). К тому же можем предположить,
что каждое из чисел а, Ь, с отлично от нуля. [Число 0
является наибольшим элементом у. м. (No, оч), и поэто-
му сравнимо с любым элементом из No, так что, ввиду
задачи 19, (4) выполняется, если одно из чисел а, Ь, с
равно 0.] Обозначим l = a A(6Vc), p=(oAJ)V
V (а Л с) и запишем
я = р№ ••• Р?’ гДе
Ь = Р*'Р22 •••	гДе
с = Р?Р? ••• Р?» где
a,, aj, ..., akf=N0;
Рр Рг» • • • > Ра ЛГ0;
Ур У2.
(Во всех этих выражениях можем писать одни и
те же простые числа pt, р?, ..., рк, поскольку мы до-
пускаем и степени с показателем 0.) Как известно, наи-
больший общий делитель а ЛЬ чисел а, Ь есть число
Р?'Р22 • • • Рал» где 6i = min(a,-, р,)’ для i = 1, 2.k и,
аналогично, наименьшее общее кратное а V b чисел а, b
есть число pppj2 ••••Р**’ где Vz = max(az, Pz). Тогда I
равно числу Pj’Pj* ... р^к, где Xj = m>n(ap тах (Рр V,)),
а р — числу Pt'Р2г • • • Ркк> где показатели я, —
= max (min (az, Pz), min (az, у,)). Но теперь примем во
внимание, что показатели az, Pz, yz являются элементами
цепи (No, ^). Отсюда и из решения примера 22 выте-
кает, что Xz = nz для любого i=l, 2, k, т. е. что
/ = р.
42
Пример 24. Нужно доказать, что решетка
(Я(р; Т), с) из примера 19:
а)	не дистрибутивна;
Ь)	удовлетворяет для любых a, b, c^R(ptT) сле-
дующему условию: если а с, то aV (b Л с) =
= (а Vb)Ac*).
Решение, а) Если р2, рз —три разные прямые
из /?(р; Т), то множество {Т, рь р2, р3, р} является носи-
телем подрешетки с диаграммой на рис. 14. Согласно
примеру 12 решетка (/?(р; Т), cz) не дистрибутивна.
Ь) Для доказательства указанного соотношения пре-
жде всего заметим, что оно выполняется каждый раз,
когда можно применить тожде-
ство (5), поскольку o,V(4Ac) =
= (а V b) Л (а V с) = (а V Ь) А с,
если учесть, что а\/с = с при
а с. Если а=с, то а V (Ь Л с) =
= а \/ (Ь Ла) = а вследствие
(Р1) и (S3). С другой стороны,
(аУЬ)Лс = (а\/Ь)Ла = а
вследствие (РЗ) и (Р1). Для
дальнейшего можем предполо-
жить, что а < с. Это означает,
Рис. 14-
что (i) а есть точка Т, а с — некоторая прямая из
/?(р; Т), либо (ii) а есть прямая из /?(р; Т), а с совпа-
дает с р. В обоих случаях один из трех элементов будет
наименьшим или наибольшим из элементов у. м. /?(р; Т),
а потому сравним с любым элементом из R(p; Т). Учи-
тывая вводное замечание и задачу 19, заключаем, что и
в этих случаях доказываемое соотношение истинно.
Решетка ^ = (Р, V, Л), в которой при любых
а, Ь, се Р из а с следует, что а V(Ь Л с) =
= (а V Ь) Л с, называется модулярной.
Задача 21. Каждая дистрибутивная решетка моду-
лярна.
Пример 25. Нужно доказать, что если решетка
&>=(Р, V, Л) содержит подрешетку с диаграммой, по-
добной диаграмме на рис. 12,Ь, то эта решетка не моду-
лярна.
Решение. С одной стороны, а V (Ь Л с) = а, а с
другой — (а V Ь) Л с = с а.
•) Другими словами, условие (5) выполняется, если a sg с. —
Прим. ред.
43
Замечание. Можно доказать *), что если решетка не
модулярна, то она содержит подрешетку с диаграммой,
подобной диаграмме рис. 12, Ь.
В дальнейшем мы выведем в качестве типичного об-
разца методов, применяемых в теории решеток, характе-
ризацию дистрибутивных и модулярных решеток. Но
сначала введем еще некоторые новые понятия.
Если а <2 с— два элемента некоторого у. м. 9, то
множество тех элементов х из Р, для которых одновре-
менно а х и х с, обозначается [а, с] и называется
интервалом решетки 9. Под относительным дополнением
элемента b е [а, с] в интервале [я, с] понимаем каждый
элемент Ь\ такой, что b A bi = а и вместе с тем b V bi =
= с. Если решетка 9 имеет наибольший элемент 1 и
наименьший элемент 0, то относительное дополнение эле-
мента а в интервале [0, 1] называется дополнением эле-
мента а.
Пример 26. В решетке с диаграммой рис. 10 найдите
интервал [0, Л] и определите все дополнения элемента
а, а также все относительные дополнения элемента е в
интервале [0, h].
Решение. [0, Л]= {0, е, f, g, h}. Элементами е, f,
g, h, b, d исчерпываются все дополнения элемента а. Ис-
комыми относительными дополнениями элемента е слу-
жат f и g.
Задача 22. Если bi — относительное дополнение эле-
мента b е[а, с] в интервале [а, с] такое, что bi = с, то
а = Ь. Докажите.
Задача 23. Докажите, что если [а, с] — интервал дис-
трибутивной решетки 9 и если b е[а, с], то для элемен-
та b существует не более одного относительного допол-
нения в интервале [а, с].
[Указание. Если Ь\ и bi — относительные дополне-
ния элемента b и если	j — числа 1 и 2, то bf = Ь/ Л
/\(bVbi)=bi А
Задача 24. Пусть 9—модулярная решетка, а) Про-
верьте, что (см. рис. 15)
(6) если элементы а, Ь, с, Л, В, С таковы, что
и
6VB = C,	Ь/\В = А,
*) См. «Приложение», предложение 4.
44
то существует относительное дополнение Ь\ элемента Ь
в интервале [а, с], для которого с Л(Ь\ V 5)=&г,
Ь) если с — С, то bi В.
Рис. 15.
[Указание, а) Положите bi = (а V В) Л с и дока-
жите, что bi = а \/(В Ас). Ь) Используйте задачу 22.|
Теорема 3. Решетка 9 моду л яр на тогда и только то-
гда, когда в ней выполняется условие (6).
Доказательство. 1) Из результата задачи 24
следует, что в модулярной решетке условие (6) выпол-
няется. 2) Пусть &—решетка, в которой имеет место
(6). Покажем, что она необходимо модулярна. С этой
целью возьмем элементы	Р, причем так, чтобы
Рис. 16.
а у. Согласно упражнению 8, с) из третьей главы,
имеет место соотношение а V (0 А у) (а V 0) А у.
Обозначим левую и правую части этого неравенства со-
ответственно через а п b (см. рис. 16).
45
Обозначим, далее, Р Л у = Л, р = В, а V Р = С = с
и проверим, что элементы а, Ь, с, А, В, С удовлетворяют
условию (6). Прежде всего, очевидно, что А а b
С, и потому
РА у = Л = Д Лр<аЛр<6Лр =
= [(aVP) Ау]АР = Р Ay-
Аналогично
aVP = [a A Y)1 Vp = a VP<6 VP<C VP = a V3.
Отсюда получаем, что а \/ В = ЬУ В = С и
Ь Л В — А. По предположению условие (6) выполнено,
и поэтому существует относительное дополнение bi эле-
мента b в интервале [я, С]. Согласно задаче 24,Ь),
Ь\ В и, значит, i, > a VB = C, откуда Ь\ = С. Из
результата задачи 22 вытекает, что в таком случае
а — Ь, т. е. a V (Р А у) = (a V Р) Л у. и решетка дей-
ствительно, модулярна.
Задача 25. Пусть 9>— дистрибутивная решетка. То-
гда в ней выполняется следующее условие:
(7) если элементы а, Ь, с. А, В, С таковы, что
Л<а<й<с<С, Л<В<С
и
ЬУ В = С, Ь/\В = А,
то существует в точности одно относительное дополнение
bi элемента b в интервале [а, С].
[Указание. Используйте результаты задач 21,
23 и 24.]
Теорема 4. Решетка 9* дистрибутивна тогда и только
тогда, когда в ней выполняется условие (7).
Доказательство. I) Согласно результату за-
дачи 25, в любой дистрибутивной решетке имеет ме-
сто (7).
2) Предположим, что 9*—решетка, в которой выпол-
няется условие (7). Поскольку прямое доказательство
слишком длинно (см. упр. 8—12 этой главы), исполь-
зуем результат замечания к примеру 21. Если 91 содер-
жит подрешетку с диаграммой, изображенной на
рис. 12, а или 12, Ь, то обозначим элементы этих реше-
ток в соответствии с обозначениями из (7) (рис. 17, 18).
46
Для элемента Ь в обоих случаях существует два разных
относительных дополнения (Ь\ и Ь2) в интервале [а, с].
Это несовместимо с предположением об истинности (7),
и полученное противоречие доказывает, что решетка 9*
дистрибутивна.
Решетка 9* с наименьшим элементом 0 и наибольшим
элементом 1, в которой для любого элемента существует
хотя бы одно дополнение, называется решеткой с допол-
нениями. Дистрибутивная решетка с дополнениями на-
зывается булевой решеткой.
Задача 26. Докажите, что в любой булевой решетке
для каждого элемента Ь с] существует единствен-
ное относительное дополнение в интервале [а, с].
[Указание. Используйте результат задачи 25.]
Теорема 5. Решетка 9* с наименьшим и наибольшим
элементами тогда и только тогда является булевой ре-
шеткой, когда для любых ее элементов a, Ь, с таких, что
а b с, существует в точности одно относительное
дополнение элемента Ь в интервале [а, с].
Доказательство. Ввиду результата задачи 26
достаточно доказать, что решетка 9* с указанным свой-
ством дистрибутивна, а это вытекает из теоремы 4, и что
она является решеткой с дополнениями, что непосред-
ственно следует из условия, если выбрать в качестве а
наименьший, а в качестве с наибольший элемент ре-
шетки 9*.
Задача 27. Докажите, что решетка 9*(Е) всех под-
множеств множества Е, упорядоченная включением, яв-
ляется булевой решеткой.
47
[Указание. Для МсЕ дополнением будет мно-
жество Е \ М, элементами которого являются те и толь-
ко те элементы из Е, которые не принадлежат Af.]
Из задачи 26 следует, что для любого элемента бу-
левой решетки i? = (P, V, Л) существует в точности
одно дополнение, как правило, обозначаемое а'. Это по-
зволяет определить на Р еще и операцию «взятия допол-
нения», которая каждому элементу а сопоставляет его
дополнение. Упорядоченная четверка (Р, V, Л, ') назы-
вается булевой алгеброй.
Упражнения
1.	Укажите все множества, которые в решетке из упражие-
ния 6, а) второй главы являются носителями подрешеток.
2.	Докажите, что носители всех подрешеток данной решетки Ф
вместе с пустым .множеством образуют при упорядочении включе-
нием полную решетку, и изобразите диаграмму этой решетки для
решетки JT5 из упражнения 6, а) второй главы. Будет ли это диа-
грамма модулярной решетки?
3.	Решетка	) из упражнения 6 третьей главы дистри-
бутивна. Докажите.
4.	Докажите, что решетка Ф модулярна тогда и только тогда,
когда для любых a, Ь, с е Ф,
(а Л с) V [Ь Л (а V с)]«[(а Л с) V Ь] А (а V с).
5.	Установите, будет ли решетка (С(р;р),с:) из упражнения 4
третьей главы а) дистрибутивной, Ь) модулярной.
6.	Будет ли решетка (К(р), cz) из примера 14 а) дистрибутив-
ной, Ь) модулярной?
7.	Пусть в некоторой решетке Ф имеют место неравенства
Пусть, далее, будет относительным допол-
нением элемента b в интервале [а, с],	— относительным дополне-
нием элемента с в интервале pi, С], а а+— относительным допол-
нением элемента а в интервале [Д, с+]. Тогда а+ является относи-
тельным дополнением элемента b в интервале [Л, С].
8.	Если в решетке Ф выполняется условие (7) и элементы
Д^а^Ь^с^С, В, Ь[ обладают свойствами одноименных эле-
ментов из (7), то а) сЛр! V В) = bh b) ^ — модулярная решетка.
Докажите.
9.	Докажите, что для любых трех элементов a, bt с дистрибу-
тивной решетки Ф справедливо равенство
(8) [6 А (а V с)1 V (а Л с) = [с V (а Л 6)] А (а V Ъ).
10.	Решетка Ф дистрибутивна тогда и только тогда, когда для
любых a, bt с е Р выполняется равенство (8). Докажите.
48
11.	а) Пусть ^ — модулярная решетка. Для о, Ь, с^.Р обо-
значим d = aA(bVc), р = [d V (а А с)]Л(а V с), у » [с V
V(a Л Ь)] Л (а V о). Тогда
d Л Р = d. Л Y = (а Л Ь) V (а Л с)\
d V Р = d V № (« V b) Л (а V с) Д (b V с);
Р = [Ь Л (а V с)] V (а Л с).
Ь) Если 9 — модулярная решетка, в которой выполняется усло-
вие (7), то в обозначениях из а) будет р = у.
12.	Не используя замечания следующего за примером 21, до-
кажите, что решетка, в которой выполняется условие (7), дистри-
бутивна.
13.	а) Докажите, что в решетке (NQ, <yj) из задачи 1 для трех
чисел а, о, с из No таких, что aolbt Ьсцс, ие существует относитель-
ного дополнения элемента b в интервале fa, с].
Ь) Докажите, что решетка (/?(р;Т), с) из примера 19 яв-
ляется решеткой с дополнениями, но не является булевой решеткой.
РЕШЕНИЯ И ОТВЕТЫ К УПРАЖНЕНИЯМ
Глава 1
1. Речь идет о всевозможных подмножествах декартова произ-
ведения {a, b} X {<*, Ь}, и мы получаем следующие отношения: pi =
= 0. Р2={(а,а)}, рз = {(а. &)}, р4 = {(&. а)}, р3 = {(М)},
Ре = {(а.а), (й,6)}, р7= {(а,а),(Ь,а)}, р8 = {(а,а), (Ь,6П, р9 =
— {(а, &),(&,а)}, рю = {(а, 6), ри = {(6, а), (b,b)}, р|2 =
= {(«. а). (а,Ь), (Ь,а)),	р,8 = {(а, а), (а, Ь), (Ь, Ь)},	р|4 =
= {(<*, а), (Ь, а), (Ь, &)},	р15 = {(а, Ь), (Ь, а), (Ъ, Ь)},	р>8 =
= {(а, а), (а,Ь), (Ь, а), (Ь, Ь)}.
a) Ре> Pis, Pi*, Pie; b) Pi, Рг, ps, Ps, pe, P12, pis. Pie! c) Pt, P2,
Рз, Pl, Рз, Ре, P7, Ps, Pio, Pit, Pis, Ри; d) Pl, p2, Ps, P4, PS. P«, P7,
P8, P10, Plh P13, P14, pie*
3.	Например, ph p2, p5.
4.	a) p8, pig, pl4, pi6; b) ps, pi3» pul c) ps, pie*
5.	a) 8i = {(a,a), (b,b), (c,c)}t e2 = {(a,a), (btb), (b,c), (c, b),
83 = {(a, a), (a,c), (b,b), (c,a), (c, c)}, e4 = {(ata), (a,b),
(b,a)t (b,b), (cfc)}, e5 = {(a, a), (a, b), (a, c), (bta), (b,b)t (b, c),
(c, a), (c, b), (ct c)} «= {a, b, с} X {a, b, c}\
d) П1 == {(a, a), (b,b), (c, c), (d,d)},	t]2 = {(«,«), (b,b)t(c,c),
(ctd}t (d,c), (d,d)},	i]3 == {(a, a), (btb}t (btd)t (c,c)t (dtb)t (dtd)}t
T)4 = {(a, a), (6, b)t (6, c), (c, b), (c, c), (d, d)}, qs = {(a, a), (a, d)t
(b,b), (c,c), (d,a)t (d,d)},	i]6 = {(«,«), (btb), (c,a), (ctc),
(d,d)}, t]7= {(a,a), (a,b), (bta)t (b,b), (c.c), (d,d)}t t]8 = {(a,a).
(a> b), (b, a), (b, b)t (c, c), (c, d), (d, c), (d, d)}, q9 = {(a, a), (a, c),
(bt b)t (b, d), (c, a), (c,c), (d, 0), (d, d)}, Пю = {(a,a). (^,d), (btb),
c,b), (c, c), (d,a), (d, d)}, т]ц = {(a, a), (b, b), (b,c), (b, d),
c, c), (c, d), (d, b), (d, c), (d, d)}, qi2 = {(a,a), (a, c), (a, d),
ct a), (c, c), (c, d), (d, a), (d,c), (d, d)},	П13 e {(a»a). (a, b),
>b, a), (b, b), (b, d), (c, c), (d, a), (d, b), (d, d)}, qt4 = {(a, a),
a, c), (b,a), (b, b), (b, c), (c,a), (c, b), (c,c), (d, d)}, t])5 =
(b.b),
(a, d),
(M),.........................
— {a. b, c, d) X {a< b, c, d}.
Глава 2
1.	См. диаграмму на рис. 19.
2.	См. диаграмму на рис. 20 — при обозначениях, принятых в
решении упражнения 1 главы 1.
3.	Здесь речь идет о у. м. (Р(М X М), cz), которое согласно
примеру 10 является полной решеткой.
50
4.	Из теоремы 2 вытекает положительный ответ в случаях а),
b), d). Из результата упражнения 2 этой главы и упражнения 2.0
первой главы следует, что не существует точной верхней грани
множества {ре, р?} в у. м. всех антисимметричных отношений на
Рис. 19.	Рис. 20.
{a, b}t так что такие отношения при упорядочении включением в
общем случае не образуют решетки.
5.	а) С помощью теоремы 2 получаем положительный ответ.
Ь) Из упражнения 4, Ь) первой главы вытекает, что не существует
точной верхней грани множества {pis, Рн} в упорядоченном включс-
Рис. 22.
нием множестве всех упорядочений на двухэлементном множестве
{а, Ь}, так что здесь вообще не будет решетки.
6.	а) При обозначениях, принятых в решении упражнения 5, а)
первой главы, получаем диаграмму решетки (рис. 21). Ь) При
обозначениях, принятых в решении упражнения 5, Ь) первой главы,
получаем диаграмму, изображенную на рис. 22.
51
7.	Обозначим Do = D П 1 (см. пример 8). Если бы существовал
Do, то существовал бы н infD, что — как мы уже
знаем — не имеет места.
Глава 3
1.	Любой круг, который является нижней гранью для {М, N},
должен содержаться в пересечении кругов М и N. Если бы среди
этих нижних граней существовала наибольшая, она должна была
бы содержать всякий круг, который содержится в пересечении
обоих кругов М, N, а потому эта наибольшая нижняя грань со-
держала бы каждую внутреннюю точку пересечения и в то же
время сама, как было сказано в начале, содержалась бы в пересе-
чении. Это невозможно ни для какого круга.
2.	Обозначим через R радиус, а через S центр некоторого круга,
который содержит оба круга Къ Кг, ограниченные окружностями
^i=('Si>fi), ^2 = (^2, гг). Обозначим через Mt (соответственно DJ
точку пересечения луча SS/ с окружностью ki (соответственно с
окружностью (5;/?)) (рис. 23). Положим MD/== р/. Конечно, pi >
> 0. Тогда для i‘=l,2 будет R » р/ + п + 53/, откуда
п___и + Г2 . SSi + SS2 t Pi + Р2
2	+	2	+	2
Выражение, стоящее в правой части, не меньше, чем
/?о= ~фГ2 +	• (Это следует из того, что pi + р2 > 0, а со.
гласно неравенству треугольника SSi + SS2 Зр$2.) При этом
R = Ro тогда и только тогда, когда pi = р2 = 0 и одновременно S
лежит на отрезке, соединяющем Si и S2. Но это означает, что в
данном случае речь идет об окружности, внешне касающейся обеих
окружностей ki и k2*
52
3.	Обозначим через г радиус, а через S центр некоторого круга,
который содержится в кругах Ки Кг, ограниченных окружностями
Обозначим через Nt (соответственно через точку
пересечения луча &S с окружностью kt (соответственно с окруж-
ностью (S, г)) (рис. 24). Пусть р/ обозначает длину отрезка EtMi.
Тогда ri = р/ + г + SS*, откуда
— И ~1~ га _ pi -h Рг___SSi ~t~ ES2
T~ 2	2	2
Рассуждениями, аналогичными тем, которые были проведены
в предыдущем примере, получаем, что
и что равенство г = г0 имеет место тогда и только тогда, когда
pi = рг = 0 и одновременно S лежит на отрезке, соединяющем Si
и S2. Это означает, что речь идет о круге, ограниченном окруж-
ностью, касающейся изнутри обеих окружностей klt k2.
4.	Поскольку 0 является наименьшим элементом у. м. С(р; р),
то существование как верхней, так и нижней точной грани любого
двухэлементного множества {Ki, К2} очевидно в случае, когда хотя
бы один элемент равен пустому множеству. Точно так же очевидно,
что 0 является точной нижней гранью множества {/G, К2} в случае,
когда Ki 0 К2 = 0. Если же Ki, К2 — такие круги, что их пересе-
чение Ki Л К2 не пусто, возьмем круг К, ограниченный окружностью,
касающейся изнутри окружностей ki и k2. Любой другой круг /<з,
который содержится как в Ки так и в К2, и центр которого лежит
на прямой р, определяет на р точки пересечения С|, С2 такие, что
отрезок является частью отрезка, определяемого точками ка-
сания граничных окружностей кругов JG, К2, К. Но тогда и весь
круг Кз содержится в круге К. Аналогично можно использовать
упражнение 2, чтобы доказать существование точной верхней грани
множества {/Q, К2}, где Ki, К2 е С(р; р) — непустые круги. Поэтому
С(р;р) является решеткой. Но это не полная решетка, поскольку,
53
например, множество всех кругов из С(р;р) не имеет в этом у. м.
точной верхней грани.
5.	Проверкой рефлексивности, транзитивности и антисимметрич-
ности установим, что (Я(р), с) является у. м. Но это не решетка,
а тем более не полная решетка, поскольку фигура ABCGFED и фи-
гура EFGC являются звездчатыми множествами, а их пересечение
состоит из отрезков EF, FG и GC и не является звездчатым мно-
жеством. Отсюда видно, что для множества, состоящего из двух
упомянутых фигур, в	нижними гранями будут как EFG,
так и FGC, но наибольшей нижней грани (принадлежащей Я(р))
это множество не имеет. Так что для двухэлементного множества
{ABCGFED, EFGC} в (Н(р),с) точной нижней грани нс суще-
ствует.
6.	Речь идет об у. м., являющемся даже решеткой. В ней
{Ф} V {AJ = {с/}, где Ci = max (а/, bi), и {aj Л {bt} = {di}, где
dt == min (а/, bi). Но это не полная решетка, поскольку если мы
возьмем за М множество всех последовательностей вида п, п, п, ...
(для п = 1, 2, ...), то увидим, что в решетке (F(R), <С) не суще-
ствует верхней грани множества М.
7.	а) Поскольку k h и п т и поскольку А V т является
верхней гранью множества {Л, т}, то А < ft V т и аналогично т
А V т. Вследствие транзитивности отношения также будет
А Л V т и п Л V т, так что А V т является верхней гранью
множества {А, п}; ввиду (3s) тогда А V п А V т. Ь) В а) поло-
жите A = dlt т = Аь n — d2 и примите во внимание, что А V h = h.
с) В а) положите Л = d, k = с и т = п = g. d)—f) выводятся
аналогично.
8.	а) Всегда а < а V b н а < а V с. Поэтому ввиду упражне-
ния 7, е) будет а (а V Ь)Л(а V с). Далее, AAc^A^aVA и
аналогично А Л с с а V с. То же упражнение дает нам А Л
Л с (а V А) А (а V с). Из упражнения 7, Ь) вытекает, что а V
V (А Л с) (а V А) Л (а X/ с). Ь) Будем исходить из соотношений
а ЛЬ, а^аЛс и действовать, как в случае а), с) Если а
с, то а V с = с и уверждение в с) является следствием а).
Глава 4
1.	Любое одноэлементное множество 17/»{е/} является носи-
телем подрешетки. Из двухэлементных множеств образуют подре-
шетки в точности следующие (см. рис. 21):
-в {8Ь 82), В2 = {8Ь 83), В3 = {8|, е4), В4 =» {8Ь 85},
= {82, 85}, Be ==» {вз, 8б}, Вт = {84, 85}.
Трехэлементные: 7\ = {eb е2, е6}, Т2 s {81, е3,8б}, Тз » {вь 84, е5}.
Четырехэлементные:
<?! я {8|. 82, 83, еБ}, Q2 = {81, 82, 84, еБ}, Q3 я {81, 83, 84, е5}.
И само множество Мб = {еь е2| е3, е4,85}, конечно, является носите-
лем подрешетки.
54
2.	Используем теорему 2: Р есть наибольший элемент этого у. м.
и если Л1 — некоторое непустое множество носителей подрешетки
решетки то их пересечение будет либо пустым множеством, либо
носителем подрешетки.
Диаграмма этой решетки для решетки Хе представлена па
рис. 25.
Эта диаграмма согласно примеру 25 не модулярна (т. е. не
является диаграммой модулярной решетки), поскольку {0,3?»
Q2} является носителем подрешетки с диаграммой, подобной диа-
грамме на рис. 12, Ь.
Рис. 25.
3.	Используем описание пересечения и объединения двух эле-
ментов решетки (F(R)t <С), данное в упражнении 6 третьей главы,
и из решения примера 22 получаем истинность тождества (4), что
вследствие примера 20 означает истинность и (5), т. е. дистрибу-
тивность рассматриваемой решетки.
4.	1) Если а с и если выполняется указанное условие, то
прежде всего a f\c ~ а и а V с = с. Отсюда видно, что если- пере-
писать условие упражнения 4, то получится модулярный закон.
2) Если, с другой стороны, Ф — модулярная решетка, то достаточно
вспомнить, что в каждой решетке а /\с с а V с и, значит,
а /\ с а V с. Используя определение модулярной решетки, полу-
чаем рассматриваемое в упражнении условие.
5.	Эта решетка не модулярна и тем более, ввиду задачи 21, не
дистрибутивна. Чтобы убедиться, что эта решетка не модулярна,
возьмем на плоскости р прямоугольную систему координат и за
прямую р примем ось х. Если А обозначает открытый круг, ограни-
ченный окружностью с центром в точке (0,75; 0) и радиусом 0,25,
С — круг с окружностью, имеющей центр в точке (0,5; 0) н радиус
0.5, а В — круг, ограниченный окружностью с центром в точке
(—0,5: 0) и радиусом 0,5, то В V С = В V А = Z, где Z обозначает
круг, ограниченный окружностью с центром в начале координат и
радиусом, равным 1, а ВЛС = ВЛА = 0. Поэтому А с С и
Д, В, С, Z, 0 определяют носитель подрешетки с диаграммой на
рис. 12, Ь, а тогда согласно примеру 25 рассматриваемая решетка
не модулярна.
6.	Эта решетка не дистрибутивна, поскольку она даже пе мо-
дулярна. Чтобы убедиться в этом, рассмотрим прилагаемый рису-
55
яок 26. В качестве выпуклых множеств A. Bt С возьмем соответ-
ственно квадраты KLMN, RSTUt PVWN, Очевидно, А с С. В ре-
шетке (К(р),с) наименьшим выпуклым множеством, содержащим
как А, так и В, является Л V В. Очевидно, это будет прямоуголь-
ник NRSM. Если Ki, К2 —два выпуклых подмножества плоскости р,
то, как следует из замечания к примеру 14, А /<2 = Ki П К2.
Тогда (4 V В)Л С равно пересечению прямоугольника NRSM с
квадратом NPVW, т. е. совпадает с прямоугольником MNPQ. Рас-
смотрим теперь выражение А V (В Л С). Здесь В /\С = В П С = 0.
а наименьшее выпуклое множество, содержа-
С	щее как 4, так и пустое множество, есть мно-
\	жество А. Это означает, что А V (ВЛС)=1
\	7. Так как b Л а+ с Л с+ = bi (см.
\	рис. 27), то b Л а+ b Л Ь\ = а. Отсюда
st \	b А а+ аАа+ = А и, так как А b и
\	\>г'г	4	а+, то А Ъ Л а+, — и А = b А а+. Да-
\ / \	лее, 6 V а+ > а V а+ = с+ > н потому
V а+> Z? V 6| = а Аналогично ftVa+>
Т / 7 /	с V с+ — С. Поскольку b С и а+ с+
/	/	С, будет b V а+ Ct и отсюда необходимо
\/	/ ЬУ а+ = С.
° Y /	8. а) Если применить (7) к 43 = Дз =
/	= В Ac, b$ = Bt Сз = Сз = С,
/	^В3 =Ь У (В Л с) и к 44 = а4 == 4, 64 =
— Bf\c, с4 = С4 = а V (В Л с), В'4=ЬЛ
г»	пт	Л Га V (В А с)1 > В" « а, то получается
Рис. 27.	6| = а V (В Ас) и аналогично Ьх — с/\ (ВУа).
Поэтому с A (bi V В) == с А {[а V (В Л c)J V
V В} = с А (а V В) — bi, b) Ввиду а) выполняется условие (6),
и теперь достаточно применить теорему 3.
9. Используя дистрибутивность, получаем
[fc Л (а V е)] V (а Л с)«[(а Л b) V (b Л с)] V (а Д с);
k V (а Л Ь)] Л(ау Ь)^(с Л(ау b)] V
V [(а ЛЬ) Л (а У Ь)] = [(а Л Ь) У (Ь Л с)] У (а Л с),
10. Предположим, что н (8) b с; тогда получаем
lb Л (а V с)] V (а Д с) «= b V (а Л с),
[с V (а Л Ь)] Л (а V Ь) = с Л (а V b)t
56
и потому решетка Ф модуляриа. Вследствие модулярности
V “ (fl A ft) V (а А с) = а A [ft V (а А с)] — а Л (fl V с) А
Л [ft V (а Л «Н
Из модулярности же
[b Л (а V с)] V (а Л с) = [b V (а Л *)] Л (а V с)
н тогда ввиду (8)
[6 V (а Л с)] Л (а V с) =» [с V (а Л Ь)] Л (а V Ь).
Если заменим здесь а на с, с на а, а b оставим без изменения, то
V (а Л *)] Л (а V с) — [а V (с Л Ь)] Л (с V Ь),
и потому V = а Л [о V(cA6)] Л(с V Ь)=» а Д(с V Ь).
11.	а) Используя модулярность и тот факт, что b V>c > b V
V (а Л с), получаем
dAp«aA(b Vc) Л[Ь V (а Ле)] Л (а V с)«
— а Л (а V с) Л [6 V (а Л с)] = а Л [6 V (а Л с)]»
«(а Л b) V (а Л с),
d V Р «[а Л (b V с)] V {[Ь V (а Л с)] Л (а V с)} =»
=» [а Л (b V с)] V lb Л (а V с)] V [(а Л с) л (а V
Поскольку a/\(b V с)> а/\с «(аЛс)А(а V с), имеем
d V р «[а Л (Ь V с)1 V [Ь Л (а V с)]
= {[а Л (b V с)] V Ь] Л (а V с) «= (а V b) Л (b V с) А (а V с)
Подобные соотношения для у получаются заменой с на bt b иа с
с сохранением а. Что касается выражения для Р, то мы уже полу-
чили его в решении примера 10. Ь) Вследствие а), Р и у оба яв-
ляются относительными дополнениями (в одном и том же интерва-
ле) элемента d, а потому ввиду (7) Р « у.
12.	Согласно упражнению 8, Ь) Ф является модулярной решет-
кой, а из упражнений 11, Ь) и 10 следует, что она дистрибутивна.
13.	а) Достаточно, например, выбрать а = 3, b — 6, с=12.
Ь) В примере 24, а) мы показали, что эта решетка не дистрибутивна,
так что тем более она не является булевой решеткой. Однако это
решетка с дополнениями: дополнением точки Т является плоскость р
и обратно; дополнением данной прямой р, проходящей через точ-
ку Г, будет любая прямая pit проходящая через точку Т и отлич-
ная от р.
ПРИЛОЖЕНИЕ
Предложение 1. В каждой решетке (Р, ^) справедливы ра-
венства
(а V b) V с = а V (Ь V с)
U
(а М) А с = а А (Ь А с).
Доказательство. Положим w = v = bVc, р =
= и V с и р = а V о. Надо убедиться, что р = Я- Но согласно
свойству (2s) из определения точной верхней грани имеем р > и,
р с, и^а и и^Ь. Учитывая транзитивность порядка, получаем
р > а, р > b и р > с, т. е. р оказывается верхней гранью множе-
ства {а,Ь,с}. Если х — какая-либо другая верхняя грань этого мно-
жества, то х > а, х b п х > с. Согласно свойству (3s) из опре-
деления точной верхней грани, получаем х и, что вместе с х > с
приводит к х > р. Таким образом, р — наименьшая верхняя грэчь
множества {а,Ь,с}. т. е. р = sup {а, Ь, с). Далее, используя (2s),
получаем, что q a, q^ v, v b и v с, откуда, как и раньше,
приходим к выводу, что q — верхняя грань множества {а, Ь, с).
Если же х — какая-то другая верхняя грань этого множества, то
ввиду (3s) имеем х а н х и, откуда х q. Следовательно,
q—наименьшая верхняя грань множества {а, 6, с}, т. е. q =
= sup {а, b, с) = р. Второе равенство доказывается аналогично.
Предложение 2. Если на некотором непустом множестве Р опре-
делены операции V и А, обладающие свойствами (S1) — (S3) и
(Р1) — (РЗ), и если ввести отношение полагая а b тогда и
только тогда, когда а — а /\ bt то это отношение упорядочивает
множество Р и (Р,^) оказывается решеткой, причем а/\Ь =
.= inf {а, Ь} и а V b » sup {а, Ь}.
Доказательство. Ввиду (S3) а = а V (а А а), откуда, ис-
пользуя (РЗ), получаем
а А а = а A (а V (а а)) = а.	(*)
Таким образом, а — а А а, а значит, а а, т. е. отношение
рефлексивно. Если а b н b с, то а = а /\Ь н b = b /\с. Учи-
тывая (Р2), получаем
а = а А 6 = а А № А = (a A fe) A = а А
Отсюда а	с, т. е. отношение оказывается транзитивным. Если
а < Z? и b	а, то а, — а /\Ь и b = b А а, откуда
а = а /\ b = b/\а = Ь
58
в силу (Pl). Этим доказана антисимметричность отношения
Таким образом, это отношение упорядочивает множество Р, Из
равенств
(а Л Ь) Л а а Л (& Л а) = а Л (а Л Ь) = (а Л а) Л 6 = а Л 6
и
(а Л b) Л b = а Д (b A b) = а Л Ь,
вытекающих из (Pl), (Р2) н (♦), получаем, что а/\Ь^.а и а Л
A b Ь. т. е. аЛ Ь оказывается нижней гранью множества {а,Ь}.
Если х — какая-либо другая нижняя грань этого множества, то
х fl и х т. е. х = х Л а и х = х /U, Отсюда
х А (а Д Ь) — (х Л а) Л b = х А b = х,
т. е. х а Л Ь. Следовательно, а А b — наибольшая нижняя грань
множества {а, Ь}, т. е. а Л b — inf {а, Ь}.
Далее, из (S1) и (РЗ) вытекает
а Л (а V Ь) « а
и
b Л (а V Ь) - b A (b V а) = Ь.
Следовательно, а^аУЬнЬ^аУЬ, т. е. аУЬ оказывается верх-
ней гранью множества {а, Ь}. Если х —какая-либо другая верхняя
грань этого множества, то а < х и b х, откуда а аЛх и b ~
— b Ах. Теперь, используя (S3) и (Р1), получаем
x = xV(xAa)«xV(aAx) = xVa
и
X « X v (х Л Ь) = х V (b Л X) «з X v ь.
Но тогда, учитывая (РЗ) и (S3), получаем
х у/ х = х V (х Д (х V х)) = х,
после чего, используя (SI), (S2) и (РЗ), приходим к
а V Ь) Д х « (а V Ь) Д (х V b) = (а V b) Л ((х V а) V Ь) =
= (а V Ь) Д (х V (a V6)) = (a V b) Д ((а V b) V х)=а V Ь.
Следовательно, а V b х. Таким образом, fl V b оказывается наи-
меньшей верхней гранью множества {а, 6}, т. е. а V b * sup {а, ft}.
Предложение 3. Решетка (Р. ^) модулярна тогда и только то-
гда, когда для любых a, b, с Р из справедливости соотношений
а <6, аУ с = b У с и а Ас = b Ас вытекает. что а = Ь.
Доказательство. Если решетка модулярна, а элементы а,
b и с удовлетворяют указанным в формулировке соотношениям, то
учитывая (Р1), (S3), (РЗ) и модулярность, получаем
b = b Д (b V с) b Д (а V с) = (а V с) Л b == а V (с Л Ь) =
— а V (Ь Д с) = а У (а Д с) == а
59
Допустим теперь, что a, b, с е Р, а с и указанное в формулировке
свойство выполнено. Из упражнения 7 гл. 3 вытекает
о V К [(а V 6) М) V Кй V *
н
b Л с < [а V (Ь Л с)] Л b < [с V (b Л с)] Л b -= с Л b =* b Л л
Отсюда
((а V Ь) А с] V b V b = а V l(b Л с) V Ь] =[а V (Ь Д с)] V b
и
Г(а V Ь) Д с] Л b - b Л с = fa V (Ь Л с)] Л Ъ.
Согласно упражнению 8, с) из гл. 3
а V (b Л с)<(а V Ь) Л с.
Таким образом, элементы a У(Ь Л с), (а V 6) Л с и b удовлетворяют
данному условию и, следовательно,
а V (Ь Д с) == (а V Ь) Д с.
Модулярность решетки Р доказана.
Предложение 4. Если решетка Р не модулярна, то она содер-
жит под решетку с диаграммой, изображенной на рис. 12, Ь.
Доказательство. Если решетка Р не модуляриа, то со-
гласно предложению 3 она содержит такие элементы а, b и с, что
ЛфС, аУ b =* с У b н а b sss с /\ Ь. Эти элементы и образуют
искомую подрешетку.
Предложение 5. Модулярная решетка Р дистрибутивна тогда
и только тогда, когда для любых а, Ь, сеР справедливо равенство
(а ЛЬ) У [с Д (а V Ь)]« (а Д с) V [b A (а V <?)].	(*♦)
Доказательство. Согласно задаче 12, d) ас а q V с.
Поэтому из (SI), (Р1) и модулярности вытекает
(а А с) V [Ь Д (а V с)] = (а V с) Д [b V (а Л c)J.
Таким образом, равенство (♦♦) имеет место тогда и только тогда,
когда имеет место равенство (8). Остается воспользоваться упраж-
нением 10 из гл. 4.
Предложение 6. Если решетка Р не дистрибутивна, то она со-
держит или подрешетку с диаграммой, изображенной на рис. 12, о,
или подрешетку с диаграммой, изображенной на рис. 12, Ь.
Доказательство. Допустим, что Р ие содержит подреше-
ток, изображенных иа рис. 12, Ь. Тогда согласно предложению 4
решетка Р модулярна. Далее положим
р=*(аЛЬ) VkA(aVW
<7«(аДс) VfbA(aVc)]
и
г=*(Ь Лс) У [а Л (Ь У с)].
Поскольку Р не дистрибутивна, то по предложению 5 существуют
а, Ь, с^Р такие, что р # д. Ввиду (Р1) задач 12,с) и 12,d) и
упражнения 7, с) из гл. 3, [с Л (а У 6)] V (а Л с) = с Л (а У Ь),
60
[ftA(e V с)] V(aAft)=ftA(aVc), с/\(а V b) < с < а V с и
Ь а V Ь. Поэтому, используя (SI), (S2), (Р1), задачу 12, с) и
модулярность решетки, получаем
р yq = \(aA b) У [с Л (а у ft)]] V [(а Ac) V [6 А (а V с)]] =
= [(« Л ft) V ([с А (а V ft)] V (а Л <?)]] V [ft Л (а V с)1 —
= [ft Л (а V с)] V [(а Л 6) V [с Л (a V 6)]] =
= [[ft Л (а V с)] V (а Л ft)] V [с Л (а V ft)] —
-[ft Л (а V с)] V [с Л (а V 6)] =
— (а у с) Л [6 V [с Л (а V ft)]] —
= (а V с) Л [(а V ft) Л (ft V «)].
Аналогично выводим, что
р V r = (ft V с) Л [(ft V а) А (а V с)]
и
q У г = (с V ft) Л [(с V а) Л (а V &)]•
Учитывая (S1) и (S2), получаем
pyq = pyr = qyr.
Ввиду задач 12, с) и 12, d) упражнения 7, с) из гл. 3 и свойства
(Р1).
а \Ъ<Ъ К (aVc)<(sAc)V[6 А (а V с)]
и
а Л с < с Л (а V ft).
Поэтому модулярность вместе со свойствами (SI), (S2) и (S3) дает
Р Л q = [(а Л 6) V [с Л (а У 6)]] А [(а Л с)	V [ft Л (а V с)]]	-
= (а	Л ft) V [[с	Л (а У 6)] Л [(а Л с)	V [6 Л (а V	с)1П	-
= (а	Л ft) V [(а	Л с) V [[с Л (а V ft)]	Л [6 Л (а V	с)]Ц	=
= (а	Л 6) V [(а	Л с) V (ft Л с)].
Аналогично выводим, что
Р Л г = (ft Л а) V [(ft Л с) V (а Л с)]
и
<7 Л г = (с Л а) V [(с Л 6) V (а Л ft)].
Учитывая (PI) и (Р2), получаем
рЛр — рЛг — рЛг.
Если р = г, то
pVp = pVr—P = pAr = pA'7.
Отсюда p — q в силу задачи 12,1), что противоречит выбору эле-
ментов а, b и с. Таким образом, р г. Аналогично устанавливается,
что <7 ¥ г. Следовательно, элементы р A q, р, q, г и р V q образуют
искомую подрешетку, изображенную на рис. 12, а.
61
ЛИТЕРАТУРА
1.	Виленкин Н. Я. Рассказы о множествах. — М.: Наука, 1969.
2.	Владимиров Д. А. Булевы алгебры. — М.: Наука, 1969.
3.	Сикорский Р. Булевы алгебры. — М.: Мир, 1969.
4.	Скорняков Л. А. Элементы теории структур. — М.: Наука,
1969.
5.	Скорняков Л. А. Элементы алгебры. — М.: Наука, 1980.
6.	Фрид Э. Элементарное введение в абстрактную алгебру. — Мл
Мир, 1979.
7.	Яг лом И. М. Необыкновенная алгебра. — М.: Наука, 1968.
8.	Я г лом И. М., Болтянский В. Г. Выпуклые фигуры.—
М.— Л.: ГИТТЛ, 1951.
9.	Beran L. Grupy a svazy — Praha: SNTL 1974.
10.	Papy G. Mathematique moderne (Arithmetique). — Paris: Didier,
1966.
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Алгебра булева 48	Подмножество замкнутее 38 Подрешетка 38
Грань верхняя 19 	 точная 19 — ннжняя 19 	 точная 19	Решетка 24, 38 — булева 47 — дистрибутивная 38 —	модулярная 43 —	полная 24
Дополнение 44 — относительное 44	— с дополнениями 47 У. м. 12 Упорядочение 12
Интервал 44	— лексикографическое 34
Квадрат декартов 10 Квазиупорядочение 18	Цепь 25 Эквивалентность 18 Элемент единичный 24
Множество звездчатое 37 — упорядоченное 12	— наибольший 24 — наименьший 24 — нулевой 24
Носитель 12, 38	а/\Ь 28 a ЧЬ 28
Объединение множеств 20 — элементов решетки 28 Отношение 10 —	антисимметричное 11 —	«делит» 9 —	рефлексивное 11 —	симметричное 12 —	транзитивное 11	E(N) 26 19 К(Р) 32 max^»(a, b) 24 min^(a, b) 24 N 23 Vo 15 (Vo, ci) 15 P(E) 16 Q 21
Пересечение множеств 20 — элементов решетки 28 Подмножество выпуклое 32	R 11 sup^M 19 Z 17
Ладислав Беран
УПОРЯДОЧЕННЫЕ МНОЖЕСТВА
(Серия: «Популярные лекции по математике»)
М., 1981 г., 64 стр. с илл.
Редактор Г. А. Панькова
Техн, редактор Н. В. Вершинина
Корректор В. П. Сорокина
ИВ № 11716
Сдано в набор 10.09.80. Подписано к печати 26.03.81.
Бумага 84х 1О8’/3«. Тнп. № 1. Литературная
гарнитура. Высокая печать. Условн. печ. л. 3,36.
Уч-изд. л. 3,44$ Тираж 100 000 экз. Заказ 803.
Цена книги 15 коп.
Издательство «Наука»
Главная редакция
физико-математической литературы
117071, Москва, В-71, Ленинский проспект, 15
Ленинградская типография Хе 2 головное пред-
приятие ордена Трудового Красного Знамени Ле-
нинградского объединения «Техническая книга»
им. Евгении Соколовой Союзполиграфпрома при
Государственном комитете СССР по делам изда-
тельств, полиграфии и книжной торговли.
198052, Ленинград, Л-52, Измайловский про-
спект» 29.
15 коп.
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
Вып. 1. А. И. Маркушевнч. Возвратные последовательности.
Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.
Вып. 3. И. С. Соминский. Метод математической индукции.
Вып. 4. А. И. Маркушевнч. Замечательные кривые.
Вып. 5. П. П. Коровкин. Неравенства.
Вып. 6. Н. Н. Воробьев. Числа Фибоначчи.
Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных сте-
пеней.
Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.
Вып. 9. А. И. Маркушевнч. Площади и логарифмы.
Вып. 10. А. С. Смогоржевский. Метод координат.
Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.
Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.
Вып. 13. А. И. Маркушевнч. Комплексные числа и конформные ото-
бражения.
Вып. 14. А. П. Фетисов. О доказательствах в геометрии.
Вып. 15. И. Р. Шафаревич. О решении уравнений высших стененей.
Вып. 16. В. Г. Шерватов. Гиперболические функции.
Вып. 17. В. Г. Болтянский. Что такое дифференцирование?
Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.
Вып. 19. Л. А. Люстерник. Кратчайшие линии.
Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных
фигур.
Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.
Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фи-
гуры.
Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.
Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные тео-
ремы.
Вып. 25. А. С. Смогоржевский. Линейка в геометрических постро-
ениях.
Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.
Вып. 27. В. А. Успенский. Некоторые приложения механики к мате-
матике.
Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифро-
вые машины.
Вып. 29. А. Н. Костовзкий. Геометрические построения одним цир-
кулем.
Вып. 30. Г. Е. Шилов. Как строить графики.
Вып. 31. А. Г. Дорфман. Оптика конических сечений.
Вып. 32. Е. С. Вентцель. Элементы теории игр.
Вып. 33. А. С. Барсов. Что такое линейное программирование.
Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.
Вып. 35. Н. Я. Виленкин. Метод последовательных приближений.
Вып. 36. В. Г. Болтянский. Огибающая.
Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной
шкалы).
Вып. 38. Ю. А. Шрейдер. Что такое расстояние?
Вып. 39. Н. Н. Воробьев. Признаки делимости.
Вып. 40. С. В. Фомин. Системы счисления.
Вып. 41. Б. Ю. Коган. Приложение механики к геометрии.
Вып. 42. Ю. И. Любич и Л. А. Шор. Кинематический метод в геомет-
рических задачах.
Вып. 43. В. А. Успенский. Треугольник Паскаля.
Вып. 44. И. Я. Бакельман. Инверсия.
Вып. 45. И. М. Яглом. Необыкновенная алгебра.
Вып. 46. И. М. Соболь. Метод Монте-Карло.
Вып. 47. Л. А. Калужнин. Основная теорема арифметики.
Вып. 48. А. С. Солодовников. Системы линейных неравенств.
Вып. 49. Г. Е. Шилов. Математический анализ в области рациональ-
ных функций.
Вып. 50. В. Г. Болтянский, И. Ц. Гохберг. Разбиение фигур на
меньшие части.
Вып. 51. Н. М. Бескин. Изображения пространственных фигур.
Вып. 52. Н. М. Бескин. Деление отрезка в данном отношении.
Вып. 53. Б. А. Розенфельд и Н. Д. Сергеева. Стереографическая
проекция.
Вып. 54. В. А. Успенский. Машина Поста.
Вып. 55. Л. Беран. Упорядоченные множества.