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

Определение 7.1.     X⁺=A(a)  X⁺ A⁺ (x X x _A a).

Множество A(a) называется начальным отрезком вполне упорядоченного множества, определяемым элементом a этого множества.

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

Из определения 7.1 и теоремы 6.1 следует:

Следствие 7.1. Произвольный начальный отрезок вполне упорядоченного множества есть вполне упорядоченное множество.

Заметим еще, что начальный отрезок, определяемый первым элементом вполне упорядоченного множества A ⁺, есть пустое множество.

Определение 7.2. a₁, A₂  A⁺ [A(a₁)< A(a₂) a_{1 A} a₂].

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

Теорема 7.1. Отношение, сопоставляющее любому элементу a множества начальный отрезок A (a), устанавливает подобие множества A ⁺ и множества всех его начальных отрезков, упорядоченных отношением «меньше».

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

Из теоремы 7.1 и следствия 6.1 непосредственно следует:

Следствие 7.2. Множество всех начальных отрезков множества A ⁺, упорядоченное отношением «меньше», есть вполне упорядоченное множество.

Лемма 7.1. A⁺  B⁺ [A(a) B(b)].

Доказательство. Допустим, что отношение R устанавливает подобие множеств A⁺ и B⁺ и что a – произвольный элемент множества A.

Будем считать также, что b=R (a).

Легко видеть, что A(a) _R B(b).

Таким образом, лемма верна.

В определение, которое мы ниже сформулируем, входит символ Y^X. Определение данного символа – это определение 8.3 предыдущего раздела.

(R Y^X R функц.  D_ℓ(R)=x R(x) Y).

Определение 7.3. R ВФ(A⁺) R  A^A [x _A y R(x) _AR(y)].

Выражение R ВФ(A⁺) читается: R есть возрастающая функция, определенная на множестве A ⁺.

Лемма 7.2. R ВФ(A⁺) ~[R(a) _A a].

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

Доказательство. Пусть – вопреки тому, что требуется доказать, - для некоторого a A⁺

(1) R(a) _A a.

Обозначим через  подмножество множества A⁺;  принадлежат те, и только те, элементы множества A⁺, которые удовлетворяют условию (1).

Поэтому множество  непусто. Пусть a₀ – первый элемент этого множества. Отсюда

(2) R(a₀) _A a₀

а также для любого x

(3) x _A a₀ ~[R(x) _A x].

Полагая, что x=R(a₀), получаем из формул (2) и (3)

(4) ~[R(R(a₀)) _A R(a₀)].

С другой стороны, из формулы (2) и допущения, что функция R возрастающая, получаем

R(R(a₀)) _A R(a₀).

Но данная формула противоречит формуле (4). Таким образом, допущение (1) приводит к противоречию.

Лемма 7.3.  

~[A⁺ A(a)].

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

Доказательство. Пусть, вопреки тому, что требуется доказать, - для некоторого a₁ A⁺ имеет место

(1) A⁺ A(a₁).

Обозначим через R отношение, устанавливающее подобие этих множеств. Из определения 2.4 мы получаем

(2) x _A y R(x) _A(a1) R(y).

Отношение R есть поэтому возрастающая функция, определенная на множестве A⁺. Отсюда и из леммы 7.2 следует, что

(3) ~[R(a₁) _A a₁].

Но, с другой стороны, из того, что A⁺ _R A(a₁) и a₁ A, следует, что     R(a1) _A a₁. Данное следствие противоречит формуле (3).

Таким образом, допущение (1) приводит к противоречию. Следовательно исходная формулировка леммы верна.

Лемма 7.4. a₁, a₂  A⁺  A(a₁)  A(a₂)  a₁=a₂.

Доказательство. Допустим, что a₁ a₂. Отсюда из леммы 7.3 и замечания, что из двух (различных) начальных отрезков одного и того же упорядоченного множества один есть всегда начальный отрезок другого, следует

~[A(a₁)]  A(a₂)].

Таким образом лемма верна.

Лемма 7.5.   

[A(a) B(b)] [A(a) B(b)] A⁺ B⁺.

Таким образом, если для любого начального отрезка множества A ⁺ существует подобные ему начальный отрезок множества B ⁺ и обратно, то множества A ⁺ и B ⁺ подобны.

Доказательство. Покажем, что подобие множеств A⁺ и B⁺ устанавливает отношение R, определяемое эквивалентно

(1) aRb A(a) B(b).

Из условий леммы и формулы (1) легко следует

(2) D_ℓ(R)=A, D_P(R)=B

Допустим, что aRb₁ и aRb₂.

Отсюда и из формулы (1) следуют формулы:

A(a) B(b₁)

A(a) B(b₂).

В свою очередь отсюда и из теоремы 2.1 b,c следует, что B(b₁) B(b₂).

На основании леммы 7.4 мы замечаем, что b₁= b₂.

Сходным образом можно показать, что из допущений a₁Rb и a₂Rb следует, что a₁=a₂. Поэтому отношение R взаимнооднозначно.

Отсюда и из формул (2) следует

(3) A ~_R B.

Допустим теперь, что

(4) a_{1 A} a₂.

а также, что

(5) a₁Rb₁ и a₂Rb₂.

Из формул (1) и (5) следует: (6)   A(a₁) B(b₁)

(7) A(a₂) B(b₂).

Из формулы (4) легко следует, что a₁ A(a₂). Отсюда, из леммы 7.1 и формулы (7) следует существование элемента b', такого, что

(8) b' B(b₂).

(9) A(a₁) B(b').

Из формул (6) и (9) выводим, что B(b₁) B(b').

Следовательно, по лемме 7.4 b₁= b'. Отсюда и из формулы (8) следует, что b₁ B(b₂), а потому

(10) b_{1 B} b₂.

Из того, что из формул (4) и (5) мы получили (10), а также из (3) следует утверждение леммы.

Лемма 7.6. Если в₀ – первый элемент множества B⁺ , удовлетворяет условию

1)

и если а₁ А, b₁  B, а также

2) , то

Доказательство. пусть – вопреки тому, что требуется доказать, -

2) . Отсюда следует, что или b₀= b₁, или b₀<_Bb₁. В первом случае формула (2) принимает вид:

   

Однако эта формула противоречит первому условию леммы. Поэтому допустим, что . Отсюда и из леммы 7.1 и условия (2) следует существование элемента а` множества А(а₁), такого, что  

Данное заключение опять-таки противоречит первому условию леммы.

Таким образом, косвенное доказательство леммы закончено.

Лемма 7.7.

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

(1)

а также существует такой элемент , что

(2)

обозначим через а₀ первый элемент множества А⁺, удовлетворяющий условию (1); через b₀ – первый элемент множества В⁺, удовлетворяющий условию (2).

Допустим, что a₁ A(a₀). Отсюда a₁< a₀. Из определения элемента a₀ следует существование элемента b₁ множества B⁺, такого, что A(a₁) B(b₁).

Отсюда и из леммы 7.6, мы заключаем, что b₁ B(b₀).

Таким образом, мы показали, что

(3) [A(a) B(b)].

 

Сходным образом можно показать, что

(4) [A(a) B(b)].

Из формул (3) и (4), а также леммы 7.5 следует, что A(a₀) B(b₀). Однако это заключение противоречит определению элемента a₀ (также как определению элемента b₀).

Таким образом, косвенное доказательство леммы закончено.

Теорема 7.2. A⁺ B⁺ [A⁺ B(b)] [ B⁺ A(a)].

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

Доказательство. Из леммы 7.7 следует, что выполняется хотя бы одно из следующих условий:

(1) [A(a) B(b)].

(2) [A(a) B(b)].

Если выполняется оба эти условия, то по лемме 7.5

(3)  A⁺ B⁺.

Допустим теперь, что выполняется условие (1), но не выполняется условие (2), а потому существует элемент в множестве B⁺, удовлетворяющий соотношению:

~ [A(a) B(b)].

Обозначим через b₀ первый элемент множества B⁺, удовлетворяющий данному соотношению. Будем также считать, что

(4) C⁺=B(b₀).

Из определения элемента b₀ и формулы (4) легко следует

(5) [A(a) C(c)].

Пусть a₁ A⁺. Из допущения, что выполняется условие (1), следует существование такого элемента b₁ множества B⁺, что

A(a₁) B(b₁).

Отсюда и из леммы 7.6 следует, что b₁ B(b₀). Отсюда и из формулы (4) следует, что b₁ C⁺, а также, что множество B(b₁) – начальный отрезок множества C⁺.

Таким образом, мы показали, что

(6) [A(a) C(c)].

Из леммы 7.5 формул (5), а также (6) следует, что A⁺ C⁺.

Отсюда из формулы (4) получаем

(7)    A⁺ B(b₀).

Сходным образом можно показать, что для некоторого a₀ A⁺

(8) B⁺ A(a₀).

Значит, хотя бы одна из формул (3), (7), (8) верна.

Таким образом, теорема 7.2 доказана.

Лемма 7.8. [A⁺ B(b)] [ B₁(b)].

Доказательство. Пусть отношение R устанавливает подобие множеств и .

Из третьего условия леммы следует существование такого элемента b' множества B, что

(1) A⁺ B(b').

Пусть b₁ – элемент множества B₁ удовлетворяющий условию:

b₁= (b').

Отсюда и из замечания, что отношение  устанавливает подобие множеств и , легко следует

(2) B(b') _R B₁(b₁).

Из первого условия леммы, формул (1) и (2), а также из замечания, что отношение  транзитивно и симметрично, следует

(b₁)

Отсюда уже следует утверждение леммы.

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