Конечные упорядоченные множества.

Порядковые типы ω, η, λ. Обратные типы.

Будем говорить, что упорядоченное множество А^о имеет мощность m тогда и только тогда, когда запас данного множества есть множество мощности m, то есть когда .

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

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

Лемма 5.1. Любое конечное упорядоченное множество имеет первый элемент.

Доказательство. Пусть натуральное число n – мощность упорядоченного множества А^о. (Доказательство по индукции).

Если n=1, то первый элемент множества А^о есть его единственный элемент (Базис индукции).

Допустим, что лемма верна для натурального числа k и что

Пусть а – произвольный элемент множества А^о. Обозначим через А^о, подмножество множества А^о, запас которого – разность множества А и одноэлементного множества {а}. Очевидно, что .

Значит, по индуктивному предположению существует первый элемент а₁ множества . Первым элементом множества А^о будет тот элемент из пары а,а₁, который предшествует другому.

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

Теорема 5.1. Если конечные упорядоченные множества А^о и В^о равночисленны, то данные множества подобны.

Доказательство. Допустим, что , .

Определим индуктивно конечную последовательность.

(1) а₁, а₂, ….. а_n.

Пусть первым членом последовательности (1) будет первый элемент множества А^о. Существование такого элемента гарантирует лемма 5.1.

Будем считать, что мы определил члены:

(2) а₁, а₂, ….. а_k, где k<n из последовательности (1).

Обозначим через А₁ разность множества А и запаса последовательности (2).

Пусть а_k+1 – первый элемент подмножества  множества А^о, который существует в силу леммы 5.1.

Таким способом, последовательность (1) полностью определена.

Аналогично мы определяем последовательность

(3) b_1, b_{2, ……..,}b_n,

Члены которой – элементы множества В.

Пусть отношение R имеет место между членами последовательности (1) и (3) тогда, и только тогда, когда индексы данных членов равны. Легко показать, что

             I – см. стр. 82

Таким образом, R устанавливает подобие множеств А^о и В^о.

Из теоремы 5.1. следует:

Следствие 5.1. Любое упорядоченное n – элементное множество подобно множеству всех натуральных чисел £ n, упорядоченных отношением «меньше».

Из теоремы 5.1. следует, что конечные и равночисленные упорядоченные множества имеют тот же самый порядковый тип. Эти типы будем обозначать символами, которыми мы обозначали натуральные числа. Так, например, порядковый тип пятиэлементного множества обозначим символом «5». Этот символ в соответствии с соглашениями предыдущего раздела (раздела общей теории множеств) одновременно обозначает мощность пятиэлементного множества.

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

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

В качестве иллюстрации сделанных выше замечаний мы приводим следующую теорему:

Теорема 5.2.  

Если m и n – порядковые типы конечных множеств, то

(1) m+n=n+m

(2) m×n=n×m

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

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

(3)  , , .

Очевидно, что множества А^о+В^о и В^о+А^о конечны и равночисленны. Данное замечание относится равным образом и к множествам А^о×В^о В^о×А^о. Отсюда из определений 3.3., 3.4 и формул (3) следуют формулы (1) и (2).

Рассмотрим теперь более подробно множества, удовлетворяющие следующим трем условиям:

 

а) Упорядоченное множество Х^о имеет первый элемент;

b) Упорядоченное множество Х^о не имеет последнего элемента;

с) Любое сечение множества Х^о есть скачок.

Теорема 5.3. Если упорядоченные множества А^о и В^о удовлетворяют условиям а)-с), то данные множества подобны.

Доказательство. Определим индуктивно бесконечную последовательность.

(1) а₁, а₂, а₃, …..

Член а₁ есть первый элемент множества А^о. Существование этого элемента гарантируется тем, что множество А^о удовлетворяет условию а).

Допустим, что уже определены члены а₁, а₂, ……а_k последовательности (1). Следующие эквивалентности определяют два подмножества упорядоченного множества А^о:

Из того, что множество А^о удовлетворяет условию b), следует, что множество .

Легко проверить, что упорядоченная пара есть сечение множества А^о.

Из того, что данное множество удовлетворяет условию с) следует, что множество  имеет первый элемент. Пусть этот элемент будет (k+1)-м членом последовательности (1).

Сходным образом мы определим бесконечную последовательность

(2) b₁, b₂, b₃…….,

члены которой – элементы множества В^о.

Определим еще отношение R.

(3)

Покажем прежде всего, что

(4)

Из (3) следует, что множества D_ℓ(R) равно запасу последовательности (1).

Очевидно также, что любой член этой последовательности есть элемент множества А^о.

Для доказательства формулы (4) достаточно поэтому показать, что любой элемент множества А^о есть один из членов последовательности (1).

Допустим – вопреки тому, что мы хотим доказать, - что некоторый элемент а множества А^о отличен от любого члена последовательности (1). Отсюда легко следует, что элемент а удовлетворяет одному из трех условий:

a)

b)

g)

Но случай a) невозможен, потому, что а₁ – первый элемент множества А^о.

Если бы имел место случай b), то – как легко видеть – элемент а не принадлежал бы ни одному из множеств  и , определенных в начале доказательства, что невозможно, так как пара  есть сечение множества А^о.

Допустим теперь, что имеет место случай g).

Следующие эквивалентности определяют два подмножества упорядоченного множества А^о:

;

Легко видеть, что пара есть сечение множества А^о, причем множество не имеет последнего элемента.

Однако данное заключение противоречит допущению, что А^о удовлетворяет условию с). Поэтому случай g) также не может иметь места. Таким образом, формула (4) верна.

Доказательство того, что D_р(R)=В аналогично.

Доказательство того, что отношение R удовлетворяет остальным условиям I), сформулированным в доказательстве теоремы 5.1, сделать самостоятельно.

Из того, что отношение R удовлетворяет этим условиям, и из D 2.4 следует: А^о@_RВ^о. Отношение R устанавливает подобие упорядоченных множеств А^о и В^о. Отсюда и из D 2.5 следует теорема.

Определение 5.1.   удовлетворяет условиям  а) ¸ с).

Очевидно, что множество áN,< ñ удовлетворяет условиям а) ¸ с). Отсюда:

Следствие 5.2.

Эта формула может играть роль определения порядкового типа w.

Таким образом, любое упорядоченное множество, удовлетворяющее условиям а) ¸ с) счетно.

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

Далее рассмотрим множества, удовлетворяющие условиям:

а') упорядоченное множество Х^о не имеет ни первого, ни последнего элемента;

b') упорядоченное множество Х^о счетно;

с') упорядоченное множество Х^о плотно.

Теорема 5.4. Если упорядоченные множества А^о и В^о удовлетворяют условиям а) ¸ с), то данные множества подобны.

Доказательство. Из допущения, что множества А^о и В^о удовлетворяют условию b'), и из теоремы 7.3 раздела I следует существование бесконечных последовательностей.

(1) а₁, а₂, а₃……..

(2) b₁, b₂, b₃……..

удовлетворяющих условиям:

1) запасы последовательностей (1) и (2)–соответственно множества А и В;

2) если i≠j, то а_i≠а_j и b_i≠b_j.

Определим индуктивно бесконечную последовательность

(3) , , ,…

Пусть член = . Допустим, что члены , , …,  уже определены.

Допустим также, что для произвольных натуральных чисел m и n, не превосходящих k, имеет место соотношение:

(4) a_{m A} a_n ≡ _B .

Очевидно, что член а_k+1 последовательности (1) должен удовлетворять одному из условий:

α) а_{k+1 A} a_j;

β) a_{j A} a_{k+1 A} a_j+1, 1≤ j < k;

γ) а_{j A} a_k+1.

Пусть в каждом из этих случаев член последовательности (3) равен члену b_ℓ - первому члену последовательности (2), которая удовлетворяет соответственно условиям:

α') b_{ℓ B} ;

β') _B b_{i B} ;

γ')   _B b_ℓ.

Существование члена b_ℓ следует:

1) в случае α') и γ') из того, что множество B⁰ удовлетворяет условию а').

2) в случае β') из того, что множество B⁰ удовлетворяет условию с'), и из соотношения (4).

Очевидно, что соотношение (4) остается верным, когда m и n примут значение k+1.

Таким образом данное соотношение (4) верно для всех членов последовательностей (1) и (3).

Следующая эквивалентность определяет отношение :

a b ≡ (a=a_k  b= ).

Покажем, что любой член последовательности (2), а потому и каждый элемент множества В является одним из членов последовательности (3). Временно будем полагать, что это неверно, и пусть b_ℓ - первый член последовательности (2), который не вошел в последовательность (3).

Таким образом, каждый из членов b₁,…, b_ℓ-1 совпадает с некоторым членом последовательности (3). Обозначим через член этой последовательности, удовлетворяющий условию: =  b_t, где t {1,…, ℓ-1}.

Пусть k – наибольшее из чисел r₁,…,r_ℓ-1. Допустим далее, что b_ℓ - удовлетворяет условию α') и что a_s – первый член последовательности (1), предшествующий в множестве А⁰ каждому из членов

(5) a₁,…, a_k

последовательности (1).

Поэтому каждый из членов a_k,…, a_S-1 следует хотя бы за одним из членов (5).

Значит a_S предшествует каждому из членов a₁,…, a_S-1.

Из того, что соотношение (4) выполняется для всех членов последовательностей (1) и (3), заключаем:

Каждый из членов ,…,  следует в множестве B⁰ хотя бы за одним из членов ,…, .

Поэтому член b_ℓ предшествует каждому из членов ,…, ; причем b_ℓ - первый член последовательности (2), удовлетворяющий данному условию, потому что каждый из членов b₁,…,b_ℓ-1 совпадает с каждым из членов ,…, .

Отсюда и из определения последовательности (3) следует, что b_ℓ= .

Аналогичные доказательства того, что b_ℓ является одним из членов последовательности (3) в случае, когда данный член удовлетворяет условиям β' или γ' сделать самостоятельно.

Из предшествующего рассмотрения уже легко следует, что D_P(R)=B.

Установление того, что имеют место остальные из условий I, сформулированные в доказательстве теоремы 5.1, не представляет трудностей.

Таким образом, отношение R устанавливает подобие множеств A⁰ и B⁰. Отсюда уже следует теорема 5.4.

Доказанная теорема позволяет принять следующее определение:

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

η = Ā⁰  множество A ⁰ удовлетворяет условиям a ') – c ').

Очевидно, что множество áB,<ñ удовлетворяет условиям a ') – c ').

 (B - множество рациональных чисел.)

  Следствие 5.3.

η= áB,<ñ.

Эта формула может служить определением порядкового типа η.

Теперь рассмотрим множества, удовлетворяющие условиям:

 

a"). Упорядоченное множество X⁰ не имеет ни первого, ни последнего  элемента.

b"). Упорядоченное множество X⁰ непрерывно.

c"). {W⁰ X⁰ = [ x _X y (x _{x x} y)]}  

₀ – алеф 0.

Словесно условие c" формулируется так: существует счетное подмножество W⁰ множества X⁰, такое, что для любых двух (различных) элементов множества X⁰ существует средний элемент, принадлежащий подмножеству W⁰.

Теорема 5.5. Если упорядоченные множества A ⁰ и B ⁰ удовлетворяют условиям a ") – c "), то данные множества подобны.

Доказательство (сокращенное). Пусть  и  - соответственно счетные подмножества множеств A⁰ и B⁰, удовлетворяющие условиям:

(1)

[ x _A y (x _{A A} y)].

[ x _B y (x _{B B} y)].

Существование таких подмножеств гарантируется допущением, что множества A⁰ и B⁰ удовлетворяют условию c").

Легко выявить, что множества  и  удовлетворяют условиям     a')–c'). Таким образом по теореме 5.4 они подобны.

Пусть отношение S устанавливает подобие множеств  и .

Пусть x будет произвольным элементом множества A⁰. Обозначим через  подмножество множества A⁰, которому принадлежат все элементы данного множества, предшествующие в нем элементу x, через  - подмножество множества A⁰, которому принадлежат все остальные элементы данного множества.

Легко видеть, что упорядоченная пара á , ñ есть сечение множества A⁰ и что x – первый элемент множества .

Обозначим через C⁰ произведение множеств  и , через – подмножество множества B⁰, такое, что  содержит любой элемент a, который принадлежит множеству B⁰ и для которого существует элемент множества S (C), следующий во множестве B⁰ за a.

Обозначим еще через  подмножество множества B⁰, такое, что  содержит все элементы множества B⁰, которые не принадлежат множеству . Легко видеть, что упорядоченная пара á , ñ есть сечение множества B⁰ и что множество  не имеет последнего элемента.

Поэтому и в множестве S (C), которое есть подмножество множества B⁰, также нет последнего элемента.

Отсюда уже легко следует, что множество  не имеет последнего элемента.

Отсюда и из допущения, что множество B⁰ удовлетворяет условию b", следует существование первого элемента множества . Обозначим через y этот элемент и приведем его в соответствие элементу x. Таким путем каждому элементу A⁰ приведен в соответствие точно один элемент множества B⁰. Если данное соответствие, которое, очевидно, есть некоторое отношение, обозначить через R, то получим формулы:

(2) D_ℓ(R)=A.

(3) R  функц.

Сходным образом можно привести в соответствие произвольному элементу y множества B⁰ точно один элемент множества A⁰. Легко видеть, что приведенные в данное соответствие элементы x и y находятся в отношении R. Отсюда:

(4) D_P(R)=A.

(5)  функц.

Из формул (3) и (5) следует, что R 1-1. Проверку того, что выполняется также третье из условий I, сформулированных в доказательстве теоремы 5.1, сделать самим.

Таким образом, множества A⁰ и B⁰ подобны.

Доказанная теорема позволяет принять следующее определение:

Определение 5.3.   A⁰   множество A ⁰ удовлетворяет условиям a ") – c ").

Легко видеть, что множество  á ñ удовлетворяет условиям a") – c"), причем множество W, о котором говорится в условии c"), есть множество B всех рациональных чисел.

Отсюда:

Следствие 5.4. á ñ (R – действительные числа)

Эта формула может играть роль определения порядкового типа .

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

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

Устраним из множества всех сечений множества A⁰ те принадлежащие к только что охарактеризованным парам сечения, в которых нижний класс имеет последний элемент. Полученное таким путем множество будем называть множеством всех собственных сечений множества A⁰.

Из этого определения и определения 4.4а следует:

Следствие 5.5. Ни в одном из сечений, принадлежащих множеству собственных сечений плотного множества, нижний класс не имеет последнего элемента.

Легко видеть, что отношение, определяемое формулой

(II) á , ñ R á , ñ

упорядочивает множество всех собственных сечений множества A ⁰.

Лемма 5.2.

Если упорядоченное множество A ⁰ плотно, то множество U ⁰ всех его собственных сечений, упорядоченное отношением , которое определяется формулой II, также плотно.

Доказательство.  Нужно показать, что ни одно сечение á ,B ñ множества U⁰ не есть скачок. Пусть – вопреки тому, что требуется доказать,- сечение á , ñ множества A⁰ есть последний элемент класса , а сечение á , ñ множества A⁰ – первый элемент класса .

Очевидно, что

á , ñ _U á , ñ.

Отсюда и из формулы II следует, что .

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

(1) .

Из следствия 5.5. мы выводим также, что существует элемент a ₁, удовлетворяющий условию

(2) .

Следующие формулы определяют подмножества множества A⁰:

(3) x  x _A a₁.

x  a_{1 A} x  x = a₁.

Очевидно, что упорядоченная пара á , ñ не принадлежит ни классу , ни классу .

Данное заключение противоречит допущению, что упорядоченная пара á , ñ есть сечение множества U⁰.

Таким образом данное множество плотно.

Теорема 5.6. Если упорядоченное множество А⁰ плотно, то множество U ⁰ всех его собственных сечений, упорядоченных отношением R, которое определяется условием II, непрерывно.

Доказательство. Пусть упорядоченная пара á , ñ - произвольное сечение множества U⁰. Допустим, что данное сечение есть пробел. Следующие эквивалентности определяют подмножества  и  упорядоченного множества A⁰:

(1) x (áX⁰,Y⁰ñ)  x X);

(2) y (áX⁰,Y⁰ñ)  x Y).

Легко видеть, что упорядоченная пара á , ñ есть собственное сечение множества A⁰. Допустим, что á , ñ . Из допущения, что сечение á , ñ есть пробел, следует существование такого сечения á , ñ множества A⁰, что

á , ñ á , ñ _Uá , ñ.

Отсюда и из условия II следует . Однако данное заключение противоречит (1). Сходным образом можно показать, что данное сечение не принадлежит классу . Поэтому ни одно сечение класса U⁰ не есть пробел.

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

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

Условие II определяет отношение «меньше» для так понимаемых действительных чисел.

Из теоремы 5.6. следует, что множество всех действительных чисел, упорядоченных отношением «меньше», непрерывно.

Определение 5.4.    β = α^* (α=<X,R>  β=<X,R^-1>).

Это определение короче можно записать в виде:

α=<X,R>  α^*=<X,R^-1>.

или же в виде:

(<X,R>)^*=<X,R^-1>.

Порядковый тип α^* называется обратным к порядковому типу α.

Если α - порядковый тип множества X, упорядоченного отношением R, то α^* - порядковый тип множества X, упорядоченного отношением, обратным к R, или конверсией отношения R.

Из определения 5.4. и следствия 5.2. следует, что

w^*=á ñ.

Таким образом, порядковый тип w^* - это порядковый тип упорядоченных множеств, которые не имеют первого элемента, имеют последний элемент и каждое сечение которых есть скачок.

Как легко заметить, это – порядковый тип отрицательных целых чисел, упорядоченных отношением á.

На этом примере мы видим, что тип α^* может не совпадать с типом α. Однако в некоторых случаях тип, обратный порядковому типу α, тождествен типу α. Так, например, из теоремы 5.1. следует, что n^*=n (где n – порядковый тип конечного множества);

Из теорем 5.4. и 5.5. следует, что ^*= , ^*= . Можно также показать, что

(w^*+w)^*=w^*+w.

Порядковый тип w^*+w – это порядковый тип множества целых чисел, упорядоченных отношением .

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