Стабильные порядки на мультипликативной полугруппе натуральных чисел
ART 86510
Авторы:
Н.
Н. Кабиров, Н.
Е. Ляхова
Н.
Н. Кабиров, Н.
Е. Ляхова Библиографическое описание статьи для цитирования:
Кабиров
Н.
Н.,
Ляхова
Н.
Е. Стабильные порядки на мультипликативной полугруппе натуральных чисел // Научно-методический электронный журнал «Концепт». –
2016. – Т. 11. – С.
2401–2405. – URL:
http://e-koncept.ru/2016/86510.htm.
Аннотация. Статья посвящена описанию всевозможных способов задания порядка на полугруппе натуральных чисел по умножению или сложению, обладающих свойством стабильности.
Текст статьи
Кабиров Николай Николаевич,студент второго курса факультета физики, математики, информатики Таганрогского института имени А.П.Чеховафилиала) ФГБОУ ВО «Ростовский государственный экономический университетРИНХ)», г.Таганрогnikolaykabirov@gmail.com
Ляхова Наталья Евгеньевна,кандидат физикоматематических наук, заведующий кафедрой математикиТаганрогского института имени А.П.Чехова филиала) ФГБОУ ВО «Ростовский государственный экономический университет РИНХ)», г.Таганрогlyahova_ne@mail.ru
Стабильные порядки на мультипликативной полугруппенатуральных чисел
Аннотация.Статьяпосвящена описанию всевозможных способов заданияпорядка наполугруппе натуральных чисел по умножению или сложению, обладающих свойством стабильности.Ключевые слова: отношение порядка, универсальная алгебра натуральных чисел, стабильное отношение.
В даннойработе рассматриваются алгебраические системы, в которых основным множеством является множество натуральных чисел, операциями являются сложение и умножение, а отношением является отношение порядка, которое связано с операциямисвойством стабильности. Возникает естественная задача описать все возможные способы задания порядка в универсальнойалгебре натуральных чисел по умножению или сложению, которые обладали бы свойством стабильности. Известными примерами указанных отношений порядка являются отношения сравнения чисел по величине и отношение делимости. Оказывается,они не единственные, имеется бесконечное множество таких порядков. Вработе в явном виде указываются все стабильные порядки в мультипликативной и аддитивной полугруппах натуральных чисел.В качестве примера таких порядков приводятся порядки, порожденные множеством взаимно простых пар.
1. Основные определения
Под бинарным отношением на множестве понимаетсяподмножество декартового произведения . Если , где , то будем писать и говорить, “что находится в отношении с ”.Важным типом бинарных отношений являются отношения частичной упорядоченности, т.е.бинарные отношения, обладающие свойствами рефлексивности, транзитивности и антисимметричности. Множество с заданной в нем частичной упорядоченностью называется частично упорядоченным. Для записи упорядоченности обычно употребляется символ ; если и , то, в зависимости от обстоятельств, говорится, что меньше или равно , содержится в , предшествует b.Пусть в множестве задана частичная упорядоченность. Элементы и этого множества будут называться сравнимыми, если или . Далеко не всякие два элемента из обязаны быть сравнимыми –именно по этой причине можно говоритьо ”частичной” упорядоченности. Так получается тривиальная частичнаяупорядоченность множества , если положить, что лишь при то есть различные элементы из будут несравнимыми.Частично упорядоченное множество, в котором любые два элемента сравнимы, называется упорядоченным множеством или линейно упорядоченным множеством или цепью.В различных разделах математики упорядоченные и частично упорядоченные множества встречаются чрезвычайно часто. В качестве примеровупорядоченных множеств можно указать множество натуральных чисел и множество действительных чисел, оба в их естественной упорядоченности. Примерами частично но не линейно) упорядоченных множеств служатследующие множества:–множество
всех подмножеств некоторого данного множества с отношением теоретикомножественного включения вкачестве отношения частичной упорядоченности;–множество всех непрерывных действительных функций, определенных на отрезке , если означает, что для всех ;–множество всех натуральных чисел, если понимать в том смысле, что делится нацело на .Частичным порядком на полугруппе называется частичный порядок, удовлетворяющий условию стабильности
Полугруппа, в которой определенстабильный относительно операции частичный порядок, называется упорядоченной полугруппой. Очевидно, всякую полугруппу можно считать упорядоченной относительно тривиального порядка. В качестве примеров частичных стабильных порядков можно привести уже указанные выше порядки наполугруппе и на полугруппе .Как следует из определений,порядок есть бинарное отношение, т.е. множество пар. Отсюда возникает метод описания всех частичных порядков наполугруппе. Будем называть порядок порожденным некоторым множеством пар, если он является минимальным порядком, содержащим это множество пар. Если удастся найти общий вид порядка, порожденного произвольным множествопар, то это и будет решение поставленной задачи. Ясно, что не для каждого множества пар существует порядок, порожденный .Очевидно множество не может породить порядок.
2. Порядки наN,·, порожденные конечным множеством пар
Легко видеть, что каждую пару натуральных чисел можно представить в виде , где n–натуральное число, а q–положительная дробь. Например,пару можно записать . Пусть
произвольное конечное подмножество декартова квадрата . Тогда согласно вышесказанному можно представить в виде:
Определение. Множество пар будем называть антисимметричным если для любого набора чисел из множества
, одновременно не равных нулю, .Ясно, что определение является обобщением известного понятия антисимметричности.
Определение.Пусть
антисимметричное множество пар. Всякое натуральное число , для которого существует две такие последовательности, где и , где такие что ,,
,где первое число пары из множества , назовем числом, а числа
числами множества .
Теорема1. Если
конечное антисимметричное множество пар, то бинарное отношение, такое, что тогда и только тогда, когда или является числом, а является числом множества , есть порядок, порожденный этим множеством.
Доказательство. Для доказательства теоремы необходимо показать, что, вопервых, отношение порядка, а, вовторых,
совпадает с порядком, порожденным множеством .
Докажем первую часть теоремы, т.е. докажем, что
рефлексивно, транзитивно, антисимметрично и стабильно относительно умножения.1) Рефлексивность следует из определения отношения .2) Пусть
и . Из условия имеем,,
,.А из условия имеем,,
,.Таким образом, для можно указать две последовательности
и, такие, что,,
,,,.
Т.е. —число, а —число множества . Следовательно . Случаи, когда или являются очевидными. Транзитивность доказана.3) Пусть и .Из условия следует,что .Из условия следует, что.Выше доказана транзитивность, следовательно,
и при этом.Так как все , эти равенстваможно записать в виде
.Из последнего равенства следует, что . Но это возможно лишь при , так как множество антисимметрично. Учитывая, что и , получаем . Следовательно . Антисимметричность доказана.4) Стабильность относительно умножения,очевидно,следует из стабильности отношения равенства, которое используется для определения и чисел множества .Докажем вторую часть теоремы. Обозначим через порядок порожденныймножеством . Необходимо показать, что .Пусть произвольная пара из , тогда , т.к. существует последовательности и, такие что , ,т.е. число, а
число множества . Следовательно является порядком, содержащим множество , но
минимальный порядок, содержащий , значит .
Пусть , т.е. является числом, а —числом множества . Это значит, что
, (1) , (2)
, . (3)Покажем, что пара .Так как ,то.Поэтому, согласно 1) . ()Учитывая,что
,получим.Значит, согласно 2), . ()Из ) и ) будет следовать, что .И так далее,продолжая этот процесс, получим .Или, учитывая 3), , т.е. .Таким образом,показали, что .
Теорема доказана.
Теорема2. Для того, чтобы конечное множество пар было порождающим множествомнекоторого порядка необходимо и достаточно, чтобы оно являлось антисимметричным.
Доказательство.Если множество пар является антисимметричным, то по теореме 1оно будет порождающим множеством порядка .Покажемобратное. Пусть множество пар
порождает порядок . Покажем, чтооно является антисимметричным. Доказательство проведем от противного. Допустим, что не является антисимметричным, т.е. существует набор чисел
из множества , одновременно не равных нулю, такой что.Легко видеть, что если пара принадлежит некоторому отношению порядка, то ему должны принадлежать пары , , а,значит,и пара . Аналогично,любая пара будет принадлежатьэтому порядку.На основании этого замечания, пары
принадлежат порядку . Тогда.
Если некоторый порядок содержит пары , , то он содержит и пары , .Следовательно, он содержит пару Применяя этот факт к порядку, можно записать .Следовательно,
или ,т.к.
Получили, что порядок одновременно содержит пары
и .А это противоречит тому, что является отношением порядка.Полученное противоречие доказывает теорему.
3. Порядки, порожденные множеством взаимно простых пар
В некоторых случаях, в зависимости от выбора порождающего множества, конструкция порядка, рассмотренного в предыдущем параграфе,значительно упрощаетсяи становится более наглядной. Рассмотрим один из таких случаев.
Определение.Множество пар таких,что , где ,,называется множеством взаимно простых пар.
Теорема3.Пусть дано некоторое множество взаимно простых пар.Обозначим , где . Тогда и представляются в виде,.Бинарное отношение
,,где является частичным порядком.
Доказательство.Для доказательства теоремы нужно показать рефлексивность, транзитивность, антисимметричность и стабильность указанного бинарного отношения. 1. Условие выполнено, т.к.существуют, такие,что . Рефлексивность доказана.2. Пусть . Из условия следует, что ,,аиз условия следует, что,,тогда
Для определенности будем полагать, что все и все . Тогда можно записать, что .Отсюда
Так как,
Выражая и , получим ,.Подставляя значения
и в исходные равенства, находим, что,.Следовательно,
и транзитивность доказана. В случае, когда некоторые
или
пользуемся тем, что , и доказательство будет аналогичным.3. Пусть и . Покажем, что . Изусловия следует, что,.Из условия следует, что,.Замкнем эти пары транзитивно, получим , и по доказанному выше .Но так как ,.Следовательно,,и антисимметричность доказана.4. Стабильность очевидна. Теорема доказана.
Теорема4. Для того, чтобы порядок был порожден множеством взаимно простых пар необходимо и достаточно, чтобы он был порядком , описанным в теореме 3.
Доказательство. Обозначим порядок, порожденный множеством взаимно простых пар .Нужно доказать, что .
1. —минимальный
порядок, содержащий пары .В то же время , т.к.,.Следовательно,
2. Пусть , тогда
,.Покажем, что эта пара принадлежит . Для этого достаточно показать, что из того что
следует, что
.Пара
принадлежит , следовательно,.Из этого следует, что .Таким образом, включение выполняется для . Пусть включение выполняется для , т.е. .Тогда.Так как, то .Следовательно,, т.е. данное включение выполняется и пары принадлежат .Отсюда,,азначит и .Таким образом, доказано, что .
Итак, получено и , следовательно,
и теорема доказана.
Легко видеть, что порядок, порожденный произвольной парой,является частным случаем порядка, порожденного множеством взаимно простых пар.
4. Стабильные порядки на аддитивной полугруппе натуральных чисел, их связь с порядками на мультипликативной полугруппе натуральных чисел.
Рассмотрим порядкина полугруппе натуральных чисел по сложению.
Произвольную пару натуральных чисел можно представить в виде либо, либо , либо , где . Рассмотрим произвольное множество пар, представимых в виде
и расположим их в порядке возрастания . Такое множество обозначим , т.е. ,
где .
Теорема5. Для того, чтобы порядок был порожден множеством пар необходимо и достаточно, чтобы он был бинарным отношением
.
Доказательство. Докажем, что бинарное отношение является отношением порядка. Для этого нужно показать четыре свойства.1.Рефлексивнсть следует из определения .2.Докажем транзитивность. Пусть и .Из условия следует,что
,,
,.Из условия следует,что,,
,.Из этих равенствполучаем
.Т.е. и транзитивность доказана.3.Антисимметричность. Пусть
и . Тогда имеют место равенства , (1) . (2)Подставим 1) в 2) и получим.А это значит, что .Но
и , следовательно,. Тогда , т.е. .Таким образом,
антисимметрично.4. Стабильность очевидна.
Следовательно,
отношение порядка. Осталось показать, что является для порождающим множеством.
Обозначим
порядок, порожденный множеством пар . Докажем, что совпадает с .1. Произвольная пара из множества принадлежит . В то же время, согласно определению
можно записать,,
,,
,т.е. .Следовательно,и произвольная пара из будет содержаться в , т.к. в содержаться все пары порождающего множества порядка .Получили, что .2. Покажем обратное. Пусть , т.е.,,
,.Нужно показать, что .Учитывая записанные равенства, проделаем следующие рассуждения.
Из того, что ,следует, что .Тогда,пары принадлежат . Отсюда .Изтого, что , следуетчто , то есть .Проделывая рассуждения аналогичные предыдущим, получим .Продолжая этот процесс, мы придем к следующему результату:, т.е. , а значит, .
Получаем, что,, следовательно,.
Теорема доказана.Аналогично теорему можно доказать для множества пар, двойственного множеству .
Теорема6. Для того, чтобы множество пар порождало порядок на аддитивной полугруппе натуральных чиселнеобходимо и достаточно, чтобы оно являлось множеством или двойственным емумножеством .
Доказательство. 1. Если множество имеет один из указанных видов, то по теореме 5онопорождает порядок.
2.Пусть порождает порядок . Покажем, что оно является
множеством или двойственным ему. Доказательство проведем методом отпротивного. Пусть множество содержит пары ,. Тогда эти пары принадлежат и порожденному порядку .,,,
.Следовательно
,,.С помощью рассуждений, аналогичных предыдущим, получаем.Итак, содержит одновременно пары
и ,аэто противоречит тому, что порядок. Следовательно в не может бытьодновременно пар и , т.е. является множеством или двойственным ему.
Теорема доказана.
Легко видеть, что порядки стабильные на аддитивной полугруппе натуральных чисел, являются стабильными и на мультипликативной полугруппе натуральных чисел. Действительно, пусть
стабильный порядокна .Изусловия следуют равенства,,
,.Тогда, умножив обе части каждого равенства на произвольное натуральное числои сделав простые преобразования, получим,,
.Следовательно, .
Таким образом, множество всех стабильных порядков на аддитивной полугруппе натуральных чисел содержится в множестве всех стабильных порядков на мультипликативной полугруппе натуральных чисел. Возникает вопрос о порождающем множестве этих порядков в полугруппе
Рассмотрим, например,порядокна, порожденный парой. Это будет обычный порядок. Заметим, что кроме него и двойственному ему порядка
, других линейных порядков на
нет. Минимальным порождающим множествомпорядка в
будет множество пар.Это следует из того, что любая пара, содержащаяся в порядке, может быть получена изпаруказанного множества, и,в то же время,ни одна из этих пар не может быть получена из других с помощью транзитивного или стабильного замыкания. Таким образом,на порядок
имеет бесконечное порождающее множество. Нетрудно заметить, что все порядки на, порожденные конечным множеством пар, имеют на
бесконечные порождающие множества.
5. Порядки, порожденные бесконечным множеством пар
Теорема7.Бесконечное множество пар
порождает порядок
на некоторой алгебре
тогда и только тогда, когда любое его конечное подмножество
порождает некоторый порядок
на этой алгебре. При этом определяется следующим образом:
тогда и только тогда, когда существует конечное, такое что.
Доказательство. Пусть порождает порядок. Выберем произвольное конечное подмножество
множества. Тогда минимальный подпорядок
порядка , содержащий множество, и будет порядком, порожденным этим множеством.
Покажем обратное. Пустьпроизвольноеконечное подмножество
множества
порождает порядок. Рассмотрим отношение, такое что.1. , т.к. . Следовательно рефлексивно.2. Пусть
и .Тогда, ,такое что
и , такое что .Рассмотрим . Тогда можно записать, что
и . Получаем. Из этого следует. Таким образом, транзитивно.3. Пусть и . Тогда, , такое что и , такое что .Но существует , что ,, и получаем. Следовательно антисимметрично.4.Пусть тогда , такое что . Следовательно,, откуда.Т.е. стабильно.
Итак, удовлетворяет свойствам рефлексивности, транзитивности, антисимметричности и стабильности. Значит,
отношение порядка.Докажем, что есть порядок, порожденный бесконечным множеством . Обозначим
порядок, порожденный . Нужно показать, что.1. Произвольная пара содержится в , т.к. , что, Следовательно, . Но минимальный порядок, содержащий , следовательно .
2. Пусть–произвольная пара из, следовательно ,что , т.е.
пара содержится в минимальном порядке, порожденном , но, откуда ,и,следовательно,. Значит, .
Получили два включенияи , следовательно , т.е. множество является для порождающим.
Таким образом, доказано, что если каждое конечное подмножество бесконечного множества порождает порядок, то и само бесконечное также порождает порядок, который является указанным порядком.
Теорема доказана.
Из доказанной теоремы вытекают следствия.
Определение. Бесконечное множество пар натуральных чисел называется антисимметричным, если любое его конечное подмножество является антисимметричным.
Следствие. Для того, чтобы бесконечное множество пар
порождало порядок
на мультипликативной полугруппе натуральных чисел, необходимо и достаточно, чтобы оно было антсимметричным.
При этом
тогда и только тогда, когда существует конечное множество такое что,где
–порядок, порожденный антисимметричным множеством, который был описан в пункте 2.
Определение. Бесконечное множество пар натуральных чисел называется–множеством, если любое его конечное подмножество является–множеством.
Следствие. Для того, чтобы бесконечное множество пар
порождало порядок
на аддитивной полугруппе натуральных чисел необходимо и достаточно, чтобы оно являлось –множеством или двойственным ему –множеством. При этом тогда и только тогда, когда существует конечное множество такое что, где порядок, порожденный множеством , описанный в пункте 4.
Ссылки на источники1.Мальцев,А.И. Алгебраические системы/А.И.Мальцев.
М.: Наука, 1970, 393 c.2.Ляпин,Е.С. Упорядоченности в полугруппе преобразований/Е.С. Ляпин //Труды четвертого Всесоюзного математического съезда.Ленинград: Наука.1964.Т.2.С.1314.3.Кривенко, В.М.Соотношения предшествования, определяющие стабильные порядки на мультипликативной полугруппе натуральных чисел/В.М.Кривенко, Н.Е. Ляхова //XIXВсесоюзная алгебраическая конференция: Тезисы сообщений. –Институт прикладных проблем механики и математики АН УССР –Львов, 1987, Ч.1.С.148.
Ляхова Наталья Евгеньевна,кандидат физикоматематических наук, заведующий кафедрой математикиТаганрогского института имени А.П.Чехова филиала) ФГБОУ ВО «Ростовский государственный экономический университет РИНХ)», г.Таганрогlyahova_ne@mail.ru
Стабильные порядки на мультипликативной полугруппенатуральных чисел
Аннотация.Статьяпосвящена описанию всевозможных способов заданияпорядка наполугруппе натуральных чисел по умножению или сложению, обладающих свойством стабильности.Ключевые слова: отношение порядка, универсальная алгебра натуральных чисел, стабильное отношение.
В даннойработе рассматриваются алгебраические системы, в которых основным множеством является множество натуральных чисел, операциями являются сложение и умножение, а отношением является отношение порядка, которое связано с операциямисвойством стабильности. Возникает естественная задача описать все возможные способы задания порядка в универсальнойалгебре натуральных чисел по умножению или сложению, которые обладали бы свойством стабильности. Известными примерами указанных отношений порядка являются отношения сравнения чисел по величине и отношение делимости. Оказывается,они не единственные, имеется бесконечное множество таких порядков. Вработе в явном виде указываются все стабильные порядки в мультипликативной и аддитивной полугруппах натуральных чисел.В качестве примера таких порядков приводятся порядки, порожденные множеством взаимно простых пар.
1. Основные определения
Под бинарным отношением на множестве понимаетсяподмножество декартового произведения . Если , где , то будем писать и говорить, “что находится в отношении с ”.Важным типом бинарных отношений являются отношения частичной упорядоченности, т.е.бинарные отношения, обладающие свойствами рефлексивности, транзитивности и антисимметричности. Множество с заданной в нем частичной упорядоченностью называется частично упорядоченным. Для записи упорядоченности обычно употребляется символ ; если и , то, в зависимости от обстоятельств, говорится, что меньше или равно , содержится в , предшествует b.Пусть в множестве задана частичная упорядоченность. Элементы и этого множества будут называться сравнимыми, если или . Далеко не всякие два элемента из обязаны быть сравнимыми –именно по этой причине можно говоритьо ”частичной” упорядоченности. Так получается тривиальная частичнаяупорядоченность множества , если положить, что лишь при то есть различные элементы из будут несравнимыми.Частично упорядоченное множество, в котором любые два элемента сравнимы, называется упорядоченным множеством или линейно упорядоченным множеством или цепью.В различных разделах математики упорядоченные и частично упорядоченные множества встречаются чрезвычайно часто. В качестве примеровупорядоченных множеств можно указать множество натуральных чисел и множество действительных чисел, оба в их естественной упорядоченности. Примерами частично но не линейно) упорядоченных множеств служатследующие множества:–множество
всех подмножеств некоторого данного множества с отношением теоретикомножественного включения вкачестве отношения частичной упорядоченности;–множество всех непрерывных действительных функций, определенных на отрезке , если означает, что для всех ;–множество всех натуральных чисел, если понимать в том смысле, что делится нацело на .Частичным порядком на полугруппе называется частичный порядок, удовлетворяющий условию стабильности
Полугруппа, в которой определенстабильный относительно операции частичный порядок, называется упорядоченной полугруппой. Очевидно, всякую полугруппу можно считать упорядоченной относительно тривиального порядка. В качестве примеров частичных стабильных порядков можно привести уже указанные выше порядки наполугруппе и на полугруппе .Как следует из определений,порядок есть бинарное отношение, т.е. множество пар. Отсюда возникает метод описания всех частичных порядков наполугруппе. Будем называть порядок порожденным некоторым множеством пар, если он является минимальным порядком, содержащим это множество пар. Если удастся найти общий вид порядка, порожденного произвольным множествопар, то это и будет решение поставленной задачи. Ясно, что не для каждого множества пар существует порядок, порожденный .Очевидно множество не может породить порядок.
2. Порядки наN,·, порожденные конечным множеством пар
Легко видеть, что каждую пару натуральных чисел можно представить в виде , где n–натуральное число, а q–положительная дробь. Например,пару можно записать . Пусть
произвольное конечное подмножество декартова квадрата . Тогда согласно вышесказанному можно представить в виде:
Определение. Множество пар будем называть антисимметричным если для любого набора чисел из множества
, одновременно не равных нулю, .Ясно, что определение является обобщением известного понятия антисимметричности.
Определение.Пусть
антисимметричное множество пар. Всякое натуральное число , для которого существует две такие последовательности, где и , где такие что ,,
,где первое число пары из множества , назовем числом, а числа
числами множества .
Теорема1. Если
конечное антисимметричное множество пар, то бинарное отношение, такое, что тогда и только тогда, когда или является числом, а является числом множества , есть порядок, порожденный этим множеством.
Доказательство. Для доказательства теоремы необходимо показать, что, вопервых, отношение порядка, а, вовторых,
совпадает с порядком, порожденным множеством .
Докажем первую часть теоремы, т.е. докажем, что
рефлексивно, транзитивно, антисимметрично и стабильно относительно умножения.1) Рефлексивность следует из определения отношения .2) Пусть
и . Из условия имеем,,
,.А из условия имеем,,
,.Таким образом, для можно указать две последовательности
и, такие, что,,
,,,.
Т.е. —число, а —число множества . Следовательно . Случаи, когда или являются очевидными. Транзитивность доказана.3) Пусть и .Из условия следует,что .Из условия следует, что.Выше доказана транзитивность, следовательно,
и при этом.Так как все , эти равенстваможно записать в виде
.Из последнего равенства следует, что . Но это возможно лишь при , так как множество антисимметрично. Учитывая, что и , получаем . Следовательно . Антисимметричность доказана.4) Стабильность относительно умножения,очевидно,следует из стабильности отношения равенства, которое используется для определения и чисел множества .Докажем вторую часть теоремы. Обозначим через порядок порожденныймножеством . Необходимо показать, что .Пусть произвольная пара из , тогда , т.к. существует последовательности и, такие что , ,т.е. число, а
число множества . Следовательно является порядком, содержащим множество , но
минимальный порядок, содержащий , значит .
Пусть , т.е. является числом, а —числом множества . Это значит, что
, (1) , (2)
, . (3)Покажем, что пара .Так как ,то.Поэтому, согласно 1) . ()Учитывая,что
,получим.Значит, согласно 2), . ()Из ) и ) будет следовать, что .И так далее,продолжая этот процесс, получим .Или, учитывая 3), , т.е. .Таким образом,показали, что .
Теорема доказана.
Теорема2. Для того, чтобы конечное множество пар было порождающим множествомнекоторого порядка необходимо и достаточно, чтобы оно являлось антисимметричным.
Доказательство.Если множество пар является антисимметричным, то по теореме 1оно будет порождающим множеством порядка .Покажемобратное. Пусть множество пар
порождает порядок . Покажем, чтооно является антисимметричным. Доказательство проведем от противного. Допустим, что не является антисимметричным, т.е. существует набор чисел
из множества , одновременно не равных нулю, такой что.Легко видеть, что если пара принадлежит некоторому отношению порядка, то ему должны принадлежать пары , , а,значит,и пара . Аналогично,любая пара будет принадлежатьэтому порядку.На основании этого замечания, пары
принадлежат порядку . Тогда.
Если некоторый порядок содержит пары , , то он содержит и пары , .Следовательно, он содержит пару Применяя этот факт к порядку, можно записать .Следовательно,
или ,т.к.
Получили, что порядок одновременно содержит пары
и .А это противоречит тому, что является отношением порядка.Полученное противоречие доказывает теорему.
3. Порядки, порожденные множеством взаимно простых пар
В некоторых случаях, в зависимости от выбора порождающего множества, конструкция порядка, рассмотренного в предыдущем параграфе,значительно упрощаетсяи становится более наглядной. Рассмотрим один из таких случаев.
Определение.Множество пар таких,что , где ,,называется множеством взаимно простых пар.
Теорема3.Пусть дано некоторое множество взаимно простых пар.Обозначим , где . Тогда и представляются в виде,.Бинарное отношение
,,где является частичным порядком.
Доказательство.Для доказательства теоремы нужно показать рефлексивность, транзитивность, антисимметричность и стабильность указанного бинарного отношения. 1. Условие выполнено, т.к.существуют, такие,что . Рефлексивность доказана.2. Пусть . Из условия следует, что ,,аиз условия следует, что,,тогда
Для определенности будем полагать, что все и все . Тогда можно записать, что .Отсюда
Так как,
Выражая и , получим ,.Подставляя значения
и в исходные равенства, находим, что,.Следовательно,
и транзитивность доказана. В случае, когда некоторые
или
пользуемся тем, что , и доказательство будет аналогичным.3. Пусть и . Покажем, что . Изусловия следует, что,.Из условия следует, что,.Замкнем эти пары транзитивно, получим , и по доказанному выше .Но так как ,.Следовательно,,и антисимметричность доказана.4. Стабильность очевидна. Теорема доказана.
Теорема4. Для того, чтобы порядок был порожден множеством взаимно простых пар необходимо и достаточно, чтобы он был порядком , описанным в теореме 3.
Доказательство. Обозначим порядок, порожденный множеством взаимно простых пар .Нужно доказать, что .
1. —минимальный
порядок, содержащий пары .В то же время , т.к.,.Следовательно,
2. Пусть , тогда
,.Покажем, что эта пара принадлежит . Для этого достаточно показать, что из того что
следует, что
.Пара
принадлежит , следовательно,.Из этого следует, что .Таким образом, включение выполняется для . Пусть включение выполняется для , т.е. .Тогда.Так как, то .Следовательно,, т.е. данное включение выполняется и пары принадлежат .Отсюда,,азначит и .Таким образом, доказано, что .
Итак, получено и , следовательно,
и теорема доказана.
Легко видеть, что порядок, порожденный произвольной парой,является частным случаем порядка, порожденного множеством взаимно простых пар.
4. Стабильные порядки на аддитивной полугруппе натуральных чисел, их связь с порядками на мультипликативной полугруппе натуральных чисел.
Рассмотрим порядкина полугруппе натуральных чисел по сложению.
Произвольную пару натуральных чисел можно представить в виде либо, либо , либо , где . Рассмотрим произвольное множество пар, представимых в виде
и расположим их в порядке возрастания . Такое множество обозначим , т.е. ,
где .
Теорема5. Для того, чтобы порядок был порожден множеством пар необходимо и достаточно, чтобы он был бинарным отношением
.
Доказательство. Докажем, что бинарное отношение является отношением порядка. Для этого нужно показать четыре свойства.1.Рефлексивнсть следует из определения .2.Докажем транзитивность. Пусть и .Из условия следует,что
,,
,.Из условия следует,что,,
,.Из этих равенствполучаем
.Т.е. и транзитивность доказана.3.Антисимметричность. Пусть
и . Тогда имеют место равенства , (1) . (2)Подставим 1) в 2) и получим.А это значит, что .Но
и , следовательно,. Тогда , т.е. .Таким образом,
антисимметрично.4. Стабильность очевидна.
Следовательно,
отношение порядка. Осталось показать, что является для порождающим множеством.
Обозначим
порядок, порожденный множеством пар . Докажем, что совпадает с .1. Произвольная пара из множества принадлежит . В то же время, согласно определению
можно записать,,
,,
,т.е. .Следовательно,и произвольная пара из будет содержаться в , т.к. в содержаться все пары порождающего множества порядка .Получили, что .2. Покажем обратное. Пусть , т.е.,,
,.Нужно показать, что .Учитывая записанные равенства, проделаем следующие рассуждения.
Из того, что ,следует, что .Тогда,пары принадлежат . Отсюда .Изтого, что , следуетчто , то есть .Проделывая рассуждения аналогичные предыдущим, получим .Продолжая этот процесс, мы придем к следующему результату:, т.е. , а значит, .
Получаем, что,, следовательно,.
Теорема доказана.Аналогично теорему можно доказать для множества пар, двойственного множеству .
Теорема6. Для того, чтобы множество пар порождало порядок на аддитивной полугруппе натуральных чиселнеобходимо и достаточно, чтобы оно являлось множеством или двойственным емумножеством .
Доказательство. 1. Если множество имеет один из указанных видов, то по теореме 5онопорождает порядок.
2.Пусть порождает порядок . Покажем, что оно является
множеством или двойственным ему. Доказательство проведем методом отпротивного. Пусть множество содержит пары ,. Тогда эти пары принадлежат и порожденному порядку .,,,
.Следовательно
,,.С помощью рассуждений, аналогичных предыдущим, получаем.Итак, содержит одновременно пары
и ,аэто противоречит тому, что порядок. Следовательно в не может бытьодновременно пар и , т.е. является множеством или двойственным ему.
Теорема доказана.
Легко видеть, что порядки стабильные на аддитивной полугруппе натуральных чисел, являются стабильными и на мультипликативной полугруппе натуральных чисел. Действительно, пусть
стабильный порядокна .Изусловия следуют равенства,,
,.Тогда, умножив обе части каждого равенства на произвольное натуральное числои сделав простые преобразования, получим,,
.Следовательно, .
Таким образом, множество всех стабильных порядков на аддитивной полугруппе натуральных чисел содержится в множестве всех стабильных порядков на мультипликативной полугруппе натуральных чисел. Возникает вопрос о порождающем множестве этих порядков в полугруппе
Рассмотрим, например,порядокна, порожденный парой. Это будет обычный порядок. Заметим, что кроме него и двойственному ему порядка
, других линейных порядков на
нет. Минимальным порождающим множествомпорядка в
будет множество пар.Это следует из того, что любая пара, содержащаяся в порядке, может быть получена изпаруказанного множества, и,в то же время,ни одна из этих пар не может быть получена из других с помощью транзитивного или стабильного замыкания. Таким образом,на порядок
имеет бесконечное порождающее множество. Нетрудно заметить, что все порядки на, порожденные конечным множеством пар, имеют на
бесконечные порождающие множества.
5. Порядки, порожденные бесконечным множеством пар
Теорема7.Бесконечное множество пар
порождает порядок
на некоторой алгебре
тогда и только тогда, когда любое его конечное подмножество
порождает некоторый порядок
на этой алгебре. При этом определяется следующим образом:
тогда и только тогда, когда существует конечное, такое что.
Доказательство. Пусть порождает порядок. Выберем произвольное конечное подмножество
множества. Тогда минимальный подпорядок
порядка , содержащий множество, и будет порядком, порожденным этим множеством.
Покажем обратное. Пустьпроизвольноеконечное подмножество
множества
порождает порядок. Рассмотрим отношение, такое что.1. , т.к. . Следовательно рефлексивно.2. Пусть
и .Тогда, ,такое что
и , такое что .Рассмотрим . Тогда можно записать, что
и . Получаем. Из этого следует. Таким образом, транзитивно.3. Пусть и . Тогда, , такое что и , такое что .Но существует , что ,, и получаем. Следовательно антисимметрично.4.Пусть тогда , такое что . Следовательно,, откуда.Т.е. стабильно.
Итак, удовлетворяет свойствам рефлексивности, транзитивности, антисимметричности и стабильности. Значит,
отношение порядка.Докажем, что есть порядок, порожденный бесконечным множеством . Обозначим
порядок, порожденный . Нужно показать, что.1. Произвольная пара содержится в , т.к. , что, Следовательно, . Но минимальный порядок, содержащий , следовательно .
2. Пусть–произвольная пара из, следовательно ,что , т.е.
пара содержится в минимальном порядке, порожденном , но, откуда ,и,следовательно,. Значит, .
Получили два включенияи , следовательно , т.е. множество является для порождающим.
Таким образом, доказано, что если каждое конечное подмножество бесконечного множества порождает порядок, то и само бесконечное также порождает порядок, который является указанным порядком.
Теорема доказана.
Из доказанной теоремы вытекают следствия.
Определение. Бесконечное множество пар натуральных чисел называется антисимметричным, если любое его конечное подмножество является антисимметричным.
Следствие. Для того, чтобы бесконечное множество пар
порождало порядок
на мультипликативной полугруппе натуральных чисел, необходимо и достаточно, чтобы оно было антсимметричным.
При этом
тогда и только тогда, когда существует конечное множество такое что,где
–порядок, порожденный антисимметричным множеством, который был описан в пункте 2.
Определение. Бесконечное множество пар натуральных чисел называется–множеством, если любое его конечное подмножество является–множеством.
Следствие. Для того, чтобы бесконечное множество пар
порождало порядок
на аддитивной полугруппе натуральных чисел необходимо и достаточно, чтобы оно являлось –множеством или двойственным ему –множеством. При этом тогда и только тогда, когда существует конечное множество такое что, где порядок, порожденный множеством , описанный в пункте 4.
Ссылки на источники1.Мальцев,А.И. Алгебраические системы/А.И.Мальцев.
М.: Наука, 1970, 393 c.2.Ляпин,Е.С. Упорядоченности в полугруппе преобразований/Е.С. Ляпин //Труды четвертого Всесоюзного математического съезда.Ленинград: Наука.1964.Т.2.С.1314.3.Кривенко, В.М.Соотношения предшествования, определяющие стабильные порядки на мультипликативной полугруппе натуральных чисел/В.М.Кривенко, Н.Е. Ляхова //XIXВсесоюзная алгебраическая конференция: Тезисы сообщений. –Институт прикладных проблем механики и математики АН УССР –Львов, 1987, Ч.1.С.148.
