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

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

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

Определение. Отношение 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. Докажите, что или P_b = Р_с, или P_b Ì Р_с, или Р_с Ì P_b.

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

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

2) если а, b Î L, то, a f b Û a f₂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. (Критерий продолжения порядка) . Пусть á А, +, ×, > ñ и á А₁, Å, Ä, > ₁ñ – линейно упорядоченные кольца и á А, +, × ñ – подкольцо кольца á А₁, Å, Ä ñ. Пусть А⁺– множество положительных элементов системыА, а А₁⁺– системы А₁. Порядок > ₁тогда и только тогда продолжает порядок >, если А⁺Í А₁⁺.

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

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

Пример 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 имеет вид

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

aÎ F⁺ Û a_mb_n > 0.

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

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒