Аксиоматическая теория натуральных чисел

ГОУВПО

Тульский государственный педагогический университет

Имени Л.Н.Толстого

ЧИСЛОВЫЕ СИСТЕМЫ

Тула 2008

Числовые системы

Пособие предназначено для студентов математических специальностей педагогического вуза и разработано в соответствии с госстандартом по курсу «Числовые системы». Изложен теоретический материал. Разобраны решения типовых заданий. Приведены упражнения для решения на практических занятиях.

Составитель -

кандидат физико-математических наук, доцент кафедры алгебры и геометрии ТГПУ им. Л. Н. Толстого Ю. А. Игнатов

Рецензент -

кандидат физико-математических наук, профессор кафедры математического анализа ТГПУ им. Л. Н. Толстого И. В. Денисов

Учебное издание

Числовые системы

Составитель

ИГНАТОВ Юрий Александрович

ЧИСЛОВЫЕ СИСТЕМЫ

Настоящий курс относится к основаниям математики. В нем дается строгое аксиоматическое построение основных числовых систем: натуральных, целых, рациональных, действительных, комплексных, а также кватернионов. В основе лежит теория формальных аксиоматических систем, рассмотренная в курсе математической логики.

В каждом пункте нумерация теорем ведется сначала. При необходимости ссылки на теорему из другого пункта используется ступенчатая нумерация: перед номером теоремы ставится номер пункта. Например, теорема 1.2.3 – это теорема 3 из пункта 1.2.

Натуральные числа

Аксиоматическая теория натуральных чисел

Аксиоматическуя теорию определяют следующие элементы:

- набор констант;

- набор функциональных символов для обозначения операций;

- набор предикатных символов для обозначения отношений;

- список аксиом, связывающих указанные выше элементы.

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

В настоящем курсе строятся содержательные теории основных числовых систем.

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

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

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

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

Константа: 1 (единица).

Функциональный символ: «¢ ». Обозначает унарную операцию «следовать за», то есть а¢ – число, следующее за а. При этом число а называется предшествующим для а¢.

Специальных предикатных символов нет. Используются обычное отношение равенства и теоретико-множественные отношения. Аксиомы для них указываться не будут.

Множество, на котором строится теория, обозначается N.

Аксиомы:

(N1) (" a) a¢ ¹ 1 (единица не следует ни за каким числом).

(N2) (" a)(" b) (a¢ = b¢ ® a = b) (у каждого числа есть не более одного предшествующего).

(N3) M Í N, 1Î M, (" a)(aÎ M ® a¢ Î M) Þ M = N (аксиома математической индукции).

Приведенная аксиоматика была предложена (с незначительными изменениями) итальянским математиком Пеано в конце XIX века.

Из аксиом нетрудно вывести некоторые теоремы.

Теорема 1. (Метод математической индукции). Пусть Р(n) – предикат, определенный на множестве N. Пусть истинно Р(1) и (" n)(P(n)®P(n¢ )). Тогда Р(n) – тождественно истинный предикат на N.

Доказательство. Пусть М – множество натуральных чисел n, для которых Р(n) истинно. Тогда 1Î M по условию теоремы. Далее, если nÎ M, то P(n) истиннопо определению М, P(n¢ ) истинно по условию теоремы, и n¢ Î M по определению М. Выполняются все посылки аксиомы индукции, следовательно, M = N. Согласно определению М, это значит, что Р(n) истинно для всех чисел из N. Теорема доказана.

Теорема 2. Любое число а ¹ 1 имеет предшествующее, и притом только одно.

Доказательство. Пусть М – множество натуральных чисел, содержащее 1 и все числа, имеющие предшествующее. Тогда 1Î M. Если aÎ M, то a¢ Î M, так как a¢ имеет предшествующее (здесь даже не используется условие aÎ M). Значит, по аксиоме индукции M = N. Теорема доказана.

Теорема 3. Любое число отлично от следующего за ним.

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

Упражнение. Определив натуральные числа 1¢ = 2, 2¢ = 3, 3¢ = 4, 4¢ = 5, 5¢ = 6, докажите, что 2 ¹ 6.

Сложение натуральных чисел

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

Определение. Сложением натуральных чисел называется бинарная операция, которая натуральным числам а и b ставит в соответствие число a + b, обладающая свойствами:

(S1) а + 1 = а¢ для любого а;

(S2) a + b¢ = (a + b)¢ для любых а и b.

Требуется доказать, что это определение корректно, то есть операция, удовлетворяющая заданным свойствам, существует. Эта задача кажется очень простой: достаточно провести индукцию по b, считая а фиксированным. При этом требуется выделить множество М значений b, для которых операция a + b определена и удовлетворяет условиям (S1) и (S2). Выполняя индуктивный переход, мы должны предположить, что для b операция выполняется, и доказать, что она выполняется для b¢. Но в свойстве (S2), которое должно выполняться для b, уже есть ссылка на a + b¢. Значит, это свойство автоматически предполагает существование операции и для a + b¢, а значит, и для последующих чисел: ведь для a + b¢ тоже должно выполняться свойство (S2). Можно подумать, что это только облегчает задачу, делая индуктивный переход тривиальным: доказываемое утверждение просто повторяет индуктивное предположение. Но сложность здесь в доказательстве для базы индукции. Для значения b = 1 тоже должны выполняться свойства (S1) и (S2). Но свойство (S2), как показано, предполагает существование операции для всех значений, следующих за 1. Значит, проверка базы индукции предполагает доказательство не для единицы, а для всех чисел, и индукция теряет смысл: база индукции совпадает с доказываемым утверждением.

Приведенное рассуждение не означает, что рекурсивные определения некорректны или требуют каждый раз тщательного обоснования. Для их обоснования нужно использовать свойства натуральных чисел, которые на данном этапе только устанавливаются. Когда они будут установлены, можно будет доказать законность рекурсивных определений. Пока же докажем существование сложения индукцией по а: в формулах (S1) и (S2) нет связи между сложением для а и а¢.

Теорема 1. Сложение натуральных чисел всегда выполнимо, причем однозначно.

Доказательство. а) Сначала докажем единственность. Зафиксируем а. Тогда результат операции a + b есть функция от b. Предположим, что есть две такие функции f(b) и g(b), обладающие свойствами (S1) и (S2). Докажем, что они равны.

Пусть М – множество значений b, для которых f(b) = g(b). По свойству (S1)
f(1) = а + 1 = а¢ и g(1) = а + 1 = а¢, значит, f(1) = g(1), и 1Î М.

Пусть теперь bÎ M, то есть f(b) = g(b). По свойству (S2)

f(b¢ ) = a + b¢ = (a + b)¢ = f(b)¢, g(b¢ ) = a + b¢ = (a + b)¢ = g(b)¢ = f(b¢ ),

значит, b¢ Î М. По аксиоме индукции M = N. Единственность доказана.

б) Теперь индукцией по а докажем существование операции a + b. Пусть М – множество тех значений а, для которых операция a + b со свойствами (S1) и (S2) определена для всех b.

Пусть а = 1. Приведем пример такой операции. Полагаем по определению 1 + b = = b¢. Покажем, что для этой операции выполняются свойства (S1) и (S2). (S1) имеет вид 1 + 1 = 1¢, что соответствует определению. Проверяем (S2): 1+ b¢ =(b¢ )¢ =
= (1+ b)¢, и (S2) выполняется. Значит, 1Î М.

Пусть теперь аÎ М. Докажем, что а¢ Î М. Полагаем по определению
a¢ + b = (a+ b)¢. Тогда

a¢ + 1 = (a+1)¢ = (а¢ )¢,

a¢ + b¢ = (a+ b¢ )¢ = ((a+ b)¢ )¢ = (a¢ + b)¢,

и свойства (S1) и (S2) выполняются.

Таким образом, M = N, и сложение определено для всех натуральных чисел. Теорема доказана.

Теорема 2. Сложение натуральных чисел ассоциативно, то есть

(a + b) + c = a + (b + c).

Доказательство. Зафиксируем а и b и проведем индукцию по с. Пусть М – множество тех чисел с, для которых равенство справедливо. Имеем по свойствам (S1) и (S2):

(a + b) + 1 = (a + b)¢ = (a + b¢ ) = a + (b + 1) Þ 1Î M.

Пусть теперь сÎ M. Тогда

(a + b) + c¢ = ((a + b) + c)¢ = (a + (b + c))¢ = a + (b + c)¢ = a + (b + c¢ ),

и c¢ Î М. По аксиоме (N3) М = N. Теорема доказана.

Теорема 3. Сложение натуральных чисел коммутативно, то есть

a + b = b + а. (1)

Доказательство. Зафиксируем а и проведем индукцию по b.

Пусть b = 1, то есть требуется доказать равенство

а + 1 = 1 + а. (2)

Это равенство доказываем индукцией по а.

При а = 1 равенство тривиально. Пусть оно выполняется для а, докажем его для а¢. Имеем

а¢ + 1 = (а + 1) + 1 = (1 + а) + 1 = (1 + а)¢ = 1 + а¢.

Индуктивный переход завершен. По принципу математической индукции равенство (2) верно для всех а. Тем самым доказано утверждение базы индукции по b.

Пусть теперь формула (1) выполняется для b. Докажем ее для b¢. Имеем

a + b¢ = (a + b)¢ = (b + a)¢ = b + a¢ = b + (a + 1) = b + (1 + a) = (b + 1) + a = b¢ + a.

По принципу математической индукции теорема доказана.

Теорема 4. a + b ¹ b.

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

Теорема 5. Для любых чисел а и b имеет место один и только один из случаев:

1) a = b.

2) Существует число k такое, что a = b + k.

3) Существует число l такое, что b = a + l.

Доказательство. Из теоремы 4 следует, что имеет место не более чем один из этих случаев, так как, очевидно, случаи 1) и 2), а также 1) и 3) не могут иметь место одновременно. Если бы одновременно имели место случаи 2) и 3), то a = b + k =
= (а + l) + k = а + (l + k), что снова противоречит теореме 4. Докажем, что хотя бы один из этих случаев всегда имеет место.

Пусть выбрано число а и М – множество тех b, для каждого из которых при данном a имеет место случай 1), 2) или 3).

Пусть b = 1. Если a = 1, то имеем случай 1). Если а ¹ 1, то по теореме 1.1.2 имеем

a = k' = k + 1 = 1 + k,

то есть имеем случай 2) для b = 1. Значит, 1 принадлежит М.

Пусть b принадлежит М. Тогда возможны случаи:

- а = b, значит, b' = b + 1 = а + 1, то есть имеем случай 3)для b';

- а = b + k, и если k = 1, то а = b + 1 = b', то есть имеет место случай 1) для b';

если же k ¹ 1, то k = т' и

а = b + т' = b + (т + 1) = b + (1 + m) = (b + 1) + m = b¢ + m,

то есть имеет место случай 2) для b';

- b = a + l, и b' =(а + l)¢ = а + l¢, то есть имеем случай 3) для b'.

Во всех случаях b' принадлежит М. Теорема доказана.

Упражнение. Докажите на основании определения суммы, что 1 + 1 = 2, 1 + 2 = 3, 2 + 2 = 4, 2 + 3 = 5, 2 + 4 = 3 + 3 = 6.

Умножение натуральных чисел

Определение. Умножением натуральных чисел называется бинарная операция, которая натуральным числам а и b ставит в соответствие число ab (или a× b), обладающая свойствами:

(P1) а× 1 = а для любого а;

(P2) аb' = ab + а для любых а и b.

Относительно определения умножения сохраняют силу все замечания, которые были сделаны в предыдущем пункте по поводу определения сложения. В частности, из него еще неясно, что соответствие с данными в определении свойствами существует. Поэтому большое принципиальное значение имеет следующая теорема, аналогичная теореме 1.2.1.

Теорема 1. Умножение натуральных чисел существует и притом только одно. Иными словами, умножение всегда выполнимо и однозначно.

Доказательство вполне аналогично доказательству теоремы 1.2.1 и предлагается в качестве упражнения.

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

Теорема 2. (Правый закон дистрибутивности): (a + b)c = ac + bc.

Теорема 3. Умножение коммутативно: ab = ba.

Теорема 4. (Левый закон дистрибутивности): c(a + b) = сa + сb.

Теорема 5. Умножение ассоциативно: a(bc) = (ab)c.

Определение. Полукольцом называется система , где + и × – бинарные операции сложения и умножения, удовлетворяющие аксиомам:

(1) – коммутативная полугруппа, то есть сложение коммутативно и ассоциативно;

(2) – полугруппа, то есть умножение ассоциативно;

(3) выполняется правая и левая дистрибутивность.

С алгебраической точки зрения система натуральных чисел относительно сложения и умножения образует полукольцо.

Упражнение. Докажите на основании определения произведения, что
2× 2 = 4, 2× 3 = 6.

Упражнения

Докажите тождества:

1. 1² + 2² +... + n² = .

2. 1³ + 2³ +... + n3 = .

Найдите сумму:

3. .

4. .

5. .

6. 1× 1! + 2× 2! +... + n× n!.

Докажите неравенства:

7. n² < 2n для n > 4.

8. 2ⁿ < n! для n ³ 4.

9. (1 + x)ⁿ ³ 1 + nx, где x > –1.

10. при n > 1.

11. при n > 1.

12. .

13. Найдите ошибку в доказательстве по индукции, что все числа равны между собой. Доказываем равносильное утверждение: в любом множестве из n чисел все числа равны между собой. При n = 1 утверждение верно. Пусть оно верно для n = k, докажем его для n = k + 1. Возьмем множество из произвольных
(k + 1) чисел. Удалим из него одно число а. Осталось k чисел, по индуктивному предположению они равны между собой. В частности, равны два числа b и с. Теперь удалим из множества число с и включим а. В получившемся множестве по-прежнему k чисел, значит, они тоже равны между собой. В частности, a = b. Значит, a = b = c, и все (k + 1) числа равны между собой. Индуктивный переход завершен, и утверждение доказано.

14. Докажите усиленный принцип математической индукции:

Пусть A(n) – предикат на множестве натуральных чисел. Пусть А(1) истинен и из истинности A(k) для всех чисел k < m следует истинность A(m). Тогда A(n) истинен для всех n.

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

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

Определение. Отношение 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ñ. Тогда

12 3 4 5 6 7 Следующая ⇒