Арифметика порядковых типов.

 

Следующие два определения раскрывают содержание понятий суммы и произведения упорядоченных множеств.

Определение 3.1.

 

Определение 3.2.

 

Легко видеть, что условие:

определяет отношение R₁, которое упорядочивает множество А+В, если только А·В=0.

Сходным образом условие

определяет отношение S₁, которое упорядочивает множество А·В. Таким образом, сумма и произведение упорядоченных множеств являются упорядоченными множествами.

Заметим далее, что отношение R упорядочивает множество А+В так, что прежде всего идут все элементы множества А^о в неизменном порядке, а за ними – все элементы множества В^о также в неизменном порядке.Пусть множества А^о и В^о – множества всех действительных чисел, упорядоченных отношением «меньше». Таким образом, имеют место следующие равенства:

А^о=В^о=áN,<ñ.

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

 

 

     А₂         А₃                               

  ½           ½

                               А₁                 

                                     ½  

                                             

       

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

Следующая лемма аналогична лемме 7.5а в разделе I:

Лемма 3.1.

а)

b)

Доказательство. Мы приведем лишь доказательства части b) леммы, потому что доказательство части а) аналогично доказательству леммы 7.5а раздела I. Допустим, что отношение R устанавливает подобие множеств А^о и В^о, а отношение R₁ – подобие множеств А^о₁ и В^о₁. легко видеть, что отношение S, определяемое эквивалентностью

множеств А^о₁ и В^о₁. легко видеть, что отношение S, определяемое эквивалентностью  устанавливает подобие множеств А^о·А^о₁ и В^о·В^о₁.

Определим теперь сумму и произведение порядковых типов:

Определение 3.3.

Определение 3.4.

Заметим, что определений 3.3 и 3.4 мы могли бы более точно записать так:

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

По теореме 2.2с существуют упорядоченные множества А^о и В^о, такие что  и  Пусть  и  – произвольные упорядоченные множества, удовлетворяющее условиям:

, .

На основании леммы 2.1 можем допустить, что . Отсюда и из леммы 3.1 следует, что .

Отсюда в свою очередь мы получаем на основании аксиомы 2.1 и определения 3.3:

Таким образом, может существовать лишь одна сумма двух данных порядковых типов. То, что такая сумма всегда существует, следует из леммы 2.1, определения 3.3, теоремы 2.2b и замечания о том, что сумма двух упорядоченных множеств есть упорядоченное множество.

Сходным образом можно показать корректность D 3.4

Теорема 3.1. а) (a+b)+g=a+(b+g)

            b) (a·b)·g=a·(b·g)

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

Доказательство. Докажем лишь формулу а).

Пусть А^о, В^о, С^о – упорядоченные множества, удовлетворяющие условиям:

(1) , ,

Существование таких множеств гарантирует теорема 2.2с. На основании леммы 2.1 мы можем допустить, что

(2) А·В=А·С=В·С=0

Введем обозначения:

(3) D^о=А^о+В^о, Е^о=В^о+С^о;

Х^о=(А^о+В^о)+С^о, Y^о=А^о+(В^о+С^о)

Из определения 3.1, (2) и (3) следуют равенства:

Х = (А+В)+С, Y=А+(В+С)

Отсюда:

(4) Х=Y

Из определения 3.1, (2) и (3) следует ниже равенство:

 ;

       

.

Отсюда:

(5)

Из определения 2.4, а также из (4) и (5) следует, что отношение тождества, ограниченное множеством Х, устанавливает подобие множеств Х^о и Y^о. Отсюда, из определения 2.5 и аксиомы 2.1 следует

(6)  

C другой стороны, из определения 3.3, (2) и (3) следует равенство:

 ,  

Из этих равенств, а также из формул (6) и (1) следует формула а). Приведем еще следующую теорему:

Теорема 3.2. а)  

               b)

Таким образом, умножение порядковых типов дистрибутивно относительно сложения. Некоммуникативность умножения порядковых типов приводит к тому, что фигурируют два закона дистрибутивности.

Доказательство теоремы 3.2 опускаем.