Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии 


Упорядоченные алгебраические системы




Упорядоченные множества

Напомним основные определения, связанные с отношением порядка.

Определение.Отношение f («выше») на множестве М называется отношением порядка, или просто порядком, если это отношение транзитивно и антисимметрично. Система áМ, fñ при этом называется упорядоченным множеством.

Определение.Отношение порядка f называется отношением строгого порядка, если оно антирефлексивно, и нестрогого порядка, если рефлексивно.

Определение.Отношение порядка f называется отношением линейного порядка, если оно связно, то есть a ¹ b Þ a f b Ú b f a. Порядок, не являющийся линейным, называется частичным.

Определение.Пусть áМ, fñ – упорядоченное множество, А – подмножество М. Элемент т множества А называется наименьшим, если он меньше всех других элементов множества А, то есть

("хÎА)(х ¹ т® х f т).

Определение.Пусть áМ, fñ – упорядоченное множество, А – подмножество М. Элемент т множества А называется минимальным, если в множестве А нет меньшего элемента, то есть ("хÎА)(х ¹ т® Øт f х).

Аналогично определяются наибольший и максимальный элементы.

Упражнения

1.Докажите, что транзитивное и антирефлексивное отношение является отношением порядка.

2.Докажите, что отношение делимости M на множестве N есть отношение частичного порядка.

3.Докажите, что в множестве может быть не более одного наибольшего и не более одного наименьшего элемента.

4.Найдите все минимальные, максимальные, наибольшие и наименьшие элементы в множестве {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} для отношения делимости.

5.Докажите, что если в множестве есть наименьший элемент, то он является единственным минимальным.

6.Сколькими способами можно определить линей­ный порядок на множестве из трех элементов? линейный и строгий? линейный и нестрогий?

7.Пусть áМ, fñ – линейно упорядоченное множество. Докажите, что отношение >, определяемое условием

a > b Û a f b & a ¹ b

есть отношение строгого линейного порядка.

8.Пусть áМ, fñ – линейно упорядоченное множество. Докажите, что отношение ³, определяемое условием

a ³ b Û a f b Ú a = b,

есть отношение нестрогого линейного порядка.

Определение.Линейно упорядоченное множество áМ, fñ, в котором каждое непустое подмножество имеет наименьший элемент, называется вполне упорядоченным. Отношение f в этом случае называется отношением полного порядка.

Согласно теореме 1.4.6, система натуральных чисел – вполне упорядоченное множество.

Определение.Пусть áМ, fñ – вполне упорядоченное множество. Интервалом, отделенным элементом а, называется множество Ра всех элементов, лежащих ниже а и отличных от а, то есть

Ра = {x Î Mïa fx, x ¹ a}.

В частности, если а – минимальный элемент, то Ра = Æ.

Теорема 1. (Принцип трансфинитной индукции). Пусть áМ, fñ – вполне упорядоченное множество и А Í М. Пусть для каждого элемента а из М из принадлежности к А всех элементов интервала Ра следует, что а Î А. Тогда А = М.

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

Пусть А' = М \ А есть теоретико-множест­венная разность множеств М и А. Если А' = Æ, то А = М, и утверждение теоремы выполняется. Если А' ¹ Æ, то, так как М – вполне упорядоченное множество, то множество А' содержит наименьший элемент т. В таком случае, все элементы, предшествующие т и отличные от т, не принадлежат А' и, значит, принадлежат А. Таким образом, Рm Í А. Поэтому по условию теоремы т Î А, и, следо­вательно, т Ï А', в противоречие с предположением.

Пусть áА; fñ – упорядоченное множест­во. Мы будем предполагать, что А – конечное множество. С каж­дым элементом а множества А сопоставим какую-нибудь точку Т (а) данной плоскости так, что если элемент а непосредственно следует за элементом b, то точку Т (a) будем располагать выше точ­ки Т (b) и соединять их отрезком. В результате мы получим граф, отвечающий данному упорядоченному множеству.

Упражнения

9.Пусть áМ, fñ – вполне упорядоченное множество, b Î M, с Î M. Докажите, что или Pb = Рс, или Pb Ì Рс, или Рс Ì Pb.

10.Пусть áМ, f1ñ и áL, f2ñ – вполне упорядо­ченные множества такие, что
M Ç L = Æ. Во множестве M È L определим бинарное отношение f следующими условиями:

1) если а, b Î M, то, a f b Û a f1 b;

2) если а, b Î L, то, a f b Û a f2 b;

3) если аÎ M, bÎ L, то, a f b.

Докажите, что система áМÈL, fñ – вполне упорядоченное множество.



Упорядоченные полугруппы

Определение.Полугруппой называется алгебра áА, *ñ, где * – ассоциативная бинарная операция.

Определение.Полугруппа áА, *ñ называется полугруппой с сокращением, если в ней выполняются свойства

a*c = b*c Þ a = b; c*a = c*b Þ a = b.

Определение.Упорядоченной полугруппой называется си­стема áА, +, fñ, где:

1) система áА, +ñ – полугруппа;

2) система áА, fñ – упорядоченное множество;

3) отношение f монотонно относительно полугрупповой операции, то есть
a f b Þ a + c f b + c, c + a f c + b.

Упорядоченную полугруппу áА, +, fñ называют упорядочен­ной группой, если система áА, +ñ – группа.

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

Теорема 1. В упорядоченной полугруппе áА, +, fñ неравенства можно складывать, то есть a f b, c f d Þ a + c f b + d.

Доказательство. Имеем

a f b Þ a + c f b + c, с f d Þ b + c f b + d,

откуда по транзитивности a + c f b + d. Теорема доказана.

Упражнение 1. Докажите, что система натуральных чисел – частично упорядоченная полугруппа относительно умножения и отношения делимости.

Легко видеть, что система áN, +, >ñ – строго упорядоченная полугруппа, áN, +, ³ñ – нестрого упорядоченная полугруппа. Можно привести пример такого упорядочивания полугруппы áN, +ñ, в которой порядок не является ни строгим, ни нестрогим.

Упражнение 2. Определим порядок f в системе натуральных чисел следующим образом: a f b Û a ³ b & a ¹ 1. Докажите, что áN, +, fñ – упорядоченная полугруппа, в которой порядок не является ни строгим, ни нестрогим.

Пример 1.Пусть А – множество натуральных, чисел, не равных единице. Определим отношение f в А следующим образом:

a f b Û ($kÎN)(a = b + k) & b ¹ 3.

Доказать, что система áА, +, fñ – частично и строго упорядоченная полугруппа.

Доказательство. Проверим транзитивность:

a f b, b f c Þ a = b + k, b ¹ 3, b = c + l, c ¹ 3 Þ a = c + (k + l), c ¹ 3 Þ a f c.

Так как a f b Þ a > b, то выполняется антирефлексивность. Из упражнения 2.1.1 следует, что f – отношение строгого порядка. Порядок частичный, так как элементы 3 и 4 не находятся ни в каком отношении.

Монотонность отношения f относительно сложения выполняется. Действительно, условие a f b Þ a + c f b + c могло бы нарушиться, только когда
b + c = 3. Но сумма может быть равна 3, так как в можестве А нет единицы.

Группу из двух элементов линейно и строго упорядочить нельзя. В самом деле, пусть 0 и 1 – ее элементы (0 – нуль группы). Предположим, что 1 > 0. Тогда получим 0 = 1 + 1 > 0 + 1 = 1.

Теорема 2. Всякую линейно упорядоченную по­лугруппу с сокращением можно линейно и строго упорядочить.

Доказательство. Пусть áА, +, fñ – упорядоченная полугруппа. Отношение строгого порядка > определяется, как в упражнении 2.1.5: a > b Û a f b & a ¹ b. Покажем, что выполняется условие 3) из определения упорядоченной полугруппы.

a > b Þ a f b, a ¹ b Þ a + c f b + c.

Если a + c = b + c то, сокращая, получим a = b, что противоречит условию
а > b. Значит, a + c ¹ b + c, и a + c > b + c. Аналогично проверяется вторая часть условия 3), что доказывает теорему.

Теорема 3. Если áА, +, fñ – линейно и строго упорядо­ченная полугруппа, то:

1) а + с = b + с Û a = b Û с + a = с + b;

2) а + с f b + с Û а f b Û с + a f с + b.

Доказательство. Пусть а + с = b + с. Если a ¹ b, то в силу связности а f b или
b f a. Но тогда соответственно а + с f b+ с или b + с f a+ с, что противоречит условию а + с = b + с. Аналогично разбираются другие случаи.

Итак, всякая линейно и строго упорядоченная полугруппа – полугруппа с сокращением.

Определение.Пусть áА, +, fñ – упорядоченная полу­группа. Элемент а множества А называют положительным (отри­цательным), если а + а ¹ а и a + a f а (соответственно а f а + а).

Пример 2.Доказать, что элемент упорядоченной коммутативной полугруппы с сокращением, больший положительного элемента, не обязательно положителен.

Решение. Воспользуемся примером 1. Имеем 2 + 2 f 2, значит, 2 – положительный элемент. 3 = 2 + 1, значит, 3 f 2. В то же время соотношение 3 + 3 f 3 не выполняется, значит, 3 не является положительным элементом.

Теорема 4. Сумма положительных элементов коммута­тивной полугруппы с сокращением положительна.

Доказательство. Если а + а f а и b + b f b, то по теореме 1

а + а + b + b f а + b Þ (а + b)+ (a + b)f а + b.

Остается проверить, что (а + b)+ (a + b а + b. Имеем:

b + b f b Þ a + b + b f a + b (1)

Предположим, что (а + b)+ (a + b)= а + b. Подставив в (1), получаем

a + b + b f a + b + a + b Þ a f a + a.

В силу антисимметричности а = а + а. Это противоречит тому, что элемент а положительный.

Теорема 5. Если а – положительный элемент линейно и строго упорядоченной полугруппы, то для любого b имеем a + b f b, b + a f b.

Доказательство. Имеем а+ а fа Þ а+ а+ b f а+ b. Если неверно, что a+ b f b, то в силу линейности выполняется a + b = b или b f a+ b. Прибавляя слева а, получаем соответственно а+ а+ b = а+ b или а+ b f а+ а + b. Эти условия противоречат антисимметричности и строгости отношения порядка.

Теорема 6. Пусть áА, +, fñ – линейно и строго упорядо­ченная полугруппа, аÎА и а + а ¹ a. Тогда элементы:

а, 2*а, 3*а, ...

все различны. Если при этом система áА, +, fñ – группа, то различны и все элементы:

0, а, а, 2*а, –2*a, 3*a, –3*а, ...

(под k*a, kÎ N, aÎA, понимается сумма а+ …+ а, содержащая k слагаемых)

Доказательство. Если a + а f а, то a + а + а f а + а, и т.д. В итоге получаем цепочку … f ka f… f 4а f3а f2а f а. В силу транзитивности и антисимметричности все элементы в ней различны. В группе цепочку можно продолжить в другую сторону, прибавляя элемент –а.

Следствие. Конечную полугруппу с сокращением, если чис­ло ее элементов не меньше 2, нельзя линейно упорядочить.

Теорема 7. Пусть áА, +, fñ – линейно упорядоченная группа. Тогда

a f a Û b f b.

Доказательство – в качестве упражнения.

Таким образом, всякая линейно упорядоченная группа либо строго, либо нестрого упорядочена. Для обозначения этих порядков будем пользоваться знаками > и ³ соответственно.

Упражнения

3.Докажите, что сумма положительных элементов линейно и строго упорядоченной полугруппы положительна.

4.Доказать, что всякий элемент линейно и строго упорядо­ченный полугруппы, больший положительного элемента, сам явля­ется положительным.

5.Докажите, что упорядоченная полугруппа линейно упоря­дочена в том и только в том случае, если любое конечное множество ее элементов имеет и только один наибольший элемент.

6.Докажите, что множество положительных элементов ли­нейно упорядоченной группы не пусто.

7.Пусть áА, +, fñ – линейно и строго упорядочен­ная группа. Докажите, что элемент а системы А тогда и только тогда положителен, если а > 0.

8.Докажите, что существует и только один линейный и стро­гий порядок в аддитивной полугруппе натуральных чисел, в кото­ром множество положительных элементов не пусто.

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

Упорядоченные кольца

Определение.Система áА, +, ×, fñ называется упорядоченным полукольцом, если

1) система áА, +, ×ñ – полукольцо;

2) система áА, +, fñ – упорядоченная полугруппа с непустым множеством А+ положительных элементов;

3) выполняется монотонность относительно умножения на положительные элементы, то есть если сÎА+ и а f b, то ac f bc, ca f cb.

Положительным элементом упорядоченного полукольца А называ­ется любой положительный элемент упорядоченной полугруппы áА, +, fñ.

Упорядоченное полукольцо áА, +, ×, fñ называ­ется упорядоченным кольцом (полем), если полукольцо áА, +, ×ñ – кольцо (соответственно поле).

Определение.Пусть áА, +, ×, fñ – упорядоченное полукольцо. Порядок f системы А называется архимедовым, а система Аархимедовски упорядоченной, если, каковы бы ни были по­ложительные элементы а и b системы А, можно указать такое на­туральное число п, что na f b.

Пример 1.Полукольцо натуральных чисел с отношением > (больше) – линейно, строго и архимедовски упорядоченное полукольцо.

Для линейно упорядоченного кольца áА, +, ×, 0, fñ система áА, +, 0, fñ – линейно упорядоченная группа. Отсюда следует согласно теореме 2.2.7, что порядок f либо строгий, либо нестрогий. Во мно­жестве А можно ввести (упражнения 2.1.5. и 2.1.6) новый линейный порядок, который будет строгим, если порядок f нестрогий, и нестрогим, если порядок f – строгий. В связи с этим замечанием в линейно упорядоченном кольце А обычно рассматривают два бинарных отношения порядка, одно из которых, строгое, обозначают знаком>, а второе, нестро­гое, знаком ³.

Для дальнейшего полезно напомнить, что в линейно упорядо­ченном кольце элемент а положителен тогда и только тогда, если а > 0 (упражнение 2.2.7).

Теорема 1. Пусть система áА, +, ×, 0, >ñ – линейно упоря­доченное кольцо. Тогда для любого элемента а из А либо а = 0, либо а > 0, либо –а > 0.

Доказательство. В силу линейности и строгости между элементами
а+ а и а имеет место одно и только одно из соотношений a+ a >a, a+ a = a, a+ a < a. В первом случае а – положительный элемент. Во втором прибавляем к обеим частям –а и получаем а = 0. В третьем случае прибавляем к обеим частям –а – а – а и получаем –a < –a – a, откуда –a – положительный элемент.

Теорема 2. Сумма и произведение положительных элементов линейно упорядоченного кольца положительны.

Доказательство – в качестве упражнения.

Теорема 3. В линейно упорядоченном кольце квадрат любого ненулевого элемента положителен.

Доказательство – в качестве упражнения.

Теорема 4. В линейно упорядоченном поле если a > 0, то a–1 > 0.

Доказательство – в качестве упражнения.

Теорема 5. (Критерий порядка). Кольцо áА, +, ×, 0ñ тогда и только тогда можно линейно и строго упорядочить (т. е. ввести линейный и строгий порядок), если множество А имеет подмножест­во А+, удовлетворяющее условиям:

1) аÎА+ Þ а ¹ 0 & –аÏА+;

а ¹ 0 Þ аÎА+ Ú –аÎА+;

2) а, bÎА+ Þ а+ bÎА+ & аbÎА+.

Доказательство. Пусть сначала áА, +, ×, 0, >ñ – линейно упорядоченное кольцо. В роли искомого подмножества А+ в таком случае в силу теорем 1 и 2 может выступить множество положительных элементов системы А.

Пусть теперь А+ – подмножество кольца áА, +, ×, 0ñ, удов­летворяю­щее условиям теоремы. Попробуем ввести линейный по­рядок > в кольце áА, +, ×, 0ñ. Определим это отношение так:

а > b Û а – b Î А+.

Легко проверяется, что введенное нами от­ношение связно, антирефлексивно, антисимметрично, транзитивно, монотонно относительно сложения и умножения на любой элемент из А+.

Множество А+ с упомянутыми в условии теоремы 4 свойст­вами называют положительной частью кольца áА, +, ×, 0ñ. В даль­нейшем при введении порядка в каком-нибудь кольце мы будем искать в нем «положительную часть». Если такая часть в кольце существует, то кольцо можно упорядочить, если нет, то нельзя, если таких несовпадающих положительных частей несколько, то можно упорядочить несколькими способами.

Из сказанного следует, что при определении линейно упорядо­ченного кольца в качестве основного отношения вместо бинарного отношения > можно брать унарное отношение «положительная часть».

Теорема 6. (Критерий однозначности линейного порядка). Пусть А+ и А++ – положительные части кольца áА, +, ×, 0ñ. Тогда

А+ = А++ Û А+Í А++.

Доказательство. Пусть А+Í А++ и аÎА++. В таком случае а ¹ 0. Поэтому аÎА+ или –аÎА+. Во втором случае получаем –аÎА++. Но этого не может быть, так как уже аÎА++.

Теорема 7. (Критерий продолжения порядка). Пусть áА, +, ×, >ñ и áА1, Å, Ä, >1ñ – линейно упорядочен­ные кольца и áА, +, ×ñ – подкольцо кольца áА1, Å, Äñ. Пусть А+– множество положительных элементов системыА, а А1+– системы А1. Порядок >1 тогда и только тогда продолжает порядок >, если А+Í А1+.

Доказательство. Пусть А+Í А1+. Если а, b Î А и а > b, то а – b Î А+. Отсюда следует, что а – b Î А1+ и a>1 b.

Пусть a>1 b. Тогда а ¹ b и a – b Î А1+. Если а – b Ï А+, то –(а – b) Î А+и, следовательно, – (ab) Î А1+. Но этого нет.

Пример 2.(Поле с не единственным архимедовым линейным порядком).

Пусть R – система действительных чисел. Рассмотрим подмножество М множества R, состоящее из чисел вида a + b , где а и b – любые рациональные числа. Можно проверить, что áM, +, ×ñ – поле. Полагаем:

M+ = { a + b ïa, b Î Q, a + b > 0};

M++ = { a + b ïa, b Î Q, a – b > 0}.

Легко видеть, что М+ и М++ положительные части поля áM, +, ×ñ. А между тем они не совпадают. В архимедовости по­рядков, определяемых с помощью этих частей, убедиться нетрудно.

Пример 3.(Поле с неархимедовым линейным порядком).

Рассмотрим поле F = Q(x) – поле частных для кольца многочленов Q[x]. Его элементы представляют собой формальные дроби вида , где f и g – многочлены с рациональными коэффициентами, g ¹ 0. Формальность рассмотрения дробей заключается в том, что они рассматриваются не в функциональном аспекте: игнорируются ограничения, накладываемые на область определения.

Введем порядок в поле F указанием положительной части. Пусть aÎF,
a ¹ 0. a имеет вид

,

где am и bn – старшие коэффициенты многочленов в числителе и знаменателе. Полагаем по определению

F+ Û ambn > 0.

Легко проверить, что F+ действительно удовлетворяет определению положительной части. Порядок, определенный этой положительной частью, не является архимедовским. Элементы 1 и х положительные, но ни при каком натуральном п условие
п > x выполниться не может.





Рекомендуемые страницы:


Читайте также:



Последнее изменение этой страницы: 2016-03-22; Просмотров: 1280; Нарушение авторского права страницы


lektsia.com 2007 - 2022 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.045 с.) Главная | Обратная связь