2918

Доказательство эквивалентности условий минимальности, индуктивности и обрыва убывающих цепей

Курсовая

Математика и математический анализ

Одной из наиболее важных и принципиальных аксиом математики является аксиома математической индукции. Как правило, она формулируется и применяется для упорядоченного множества натуральных чисел N. Наиболее распространенная ее форма имеет вид: Если ...

Русский

2012-10-21

1.19 MB

15 чел.

Одной из наиболее важных и принципиальных аксиом математики является аксиома математической индукции. Как правило, она формулируется и применяется для упорядоченного множества натуральных чисел N. Наиболее распространенная ее форма имеет вид: «Если некоторое предложение   истинно при  равном 1 и из истинности  при всех n, меньших чем k  вытекает истинность  при n, равном k, тогда  истинно при любом натуральном n». [1]

Вместе с тем, некоторые тонкие и сложные вопросы требуют обобщения этой аксиомы на другие упорядоченные множества. К ним относятся упорядоченные множества с условием минимальности, в частности, вполне упорядоченные множества. Применительно к ним аксиома индукции принимает вид: «Если некоторое предположение , где х принадлежит упорядоченному множеству А с условием минимальности, истинно при всех минимальных элементах множества А и из истинности  при всех х, меньших k () вытекает истинность  при х, равном k, то истинно при любом х из множества А». [2]

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

Рассматривается одна из аксиоматик системы натуральных чисел [2], находится и доказывается последовательность утверждений, из которых вытекает условие минимальности для упорядоченного множества натуральных чисел. Это позволяет доказывать истинность предложений   для любого натурального n, указанным выше способом.

Отметим также, что одной из фундаментальных аксиом математики является аксиома выбора, которая гласит, что существует функция  из множества , состоящая  из всех непустых подмножеств множества  М во множестве М такая, что

.

Другая, упрощенная ее формулировка, имеет вид: «Существует функция, которая отмечает (выбирает) в каждом непустом подмножестве М некоторый элемент».

Оказывается (теорема Цермело), что из аксиомы выбора вытекает возможность построения полного порядка на любом непустом множестве. Доказательство этого факта содержится в [1]. В работе проводится подробный анализ этого доказательства. Находятся и устраняются некоторые имеющиеся там недостатки. Например, при определении порядка на объединении отмеченных подмножеств не доказывается его корректность.

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


§1. Основные понятия пи  примеры теории упорядоченных множеств.

Напомним, что декартовым произведением двух множеств А и В (обозначается ) называется множество, состоящее из всевозможных упорядоченных пар (х, у), где  и . Аналогично доказываем, что произведением  трех множеств А, В и С (обозначается ) называется множество, состоящее из всевозможных упорядоченных троек (х, y, z), где ,  и .

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

Всякое подмножество  декартова квадрата  называется бинарным отношением на множестве А, а всякое подмножество декартова куба  - тернарным отношением на множестве А. Наконец, всякое подмножество множества А называется унарным отношением на А. Если пара (а, b) принадлежит бинарному отношению , то пишут  или .

Бинарное отношение  на множестве А называется порядком, если  обладает следующими свойствами:

1) - рефлексивно, т.е.

2) - транзитивно, т.е.

 

3)  - антисимметрично, т.е.

Пример 1. Пусть  и , тогда  является порядком на А. Действительно,. Пусть  и , тогда из строения  вытекает, что  и . Значит,  и . Следовательно,  - транзитивно. Наконец, если  и , то , поэтому  - антисимметрично.

Указанный в Примере 1 порядок называется тривиальным.

2.  - также является порядком на . Из строения  следует, что - рефлексивно. Далее, если  и , то либо , либо , , , либо ,  , . В каждом из этих случаев , значит  - транзитивно. Наконец, если  и , то из строения  вытекает, что , значит  - антисимметрично.

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

В соответствии со сказанным, укажем графы порядков из примера 1 и 2.


3. Пусть  и  задается так:  делится нацело на х в N, т.е.  (обозначается ).

Покажем, что  является порядком на .

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

Пусть  и  (), тогда, по определению , существуют такие  и  из N, что  и , отсюда,   и  , поэтому . Следовательно, . Это означает транзитивность .

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


Фрагментом графа этого порядка будет

На этом графе отмечены лишь члены от 1 до 10.

4. Пусть А – произвольное множество,  - множество всех непустых подмножеств множества А. Определим на  бинарные отношения  так, что

.

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

Пусть  и , тогда  и . Поэтому , поэтому , значит . Следовательно,  - транзитивно. Наконец, если  и , то  и , что, по определению равенства множеств, обозначает . Следовательно,  - антисимметрично, поэтому является порядком на .

Определение. Множество А вместе с заданным на нем бинарным отношением порядка  называется упорядоченным множеством и обозначается .

Для обозначения порядка на множестве А часто используются символы «»; «» - если ясно на каком множестве определен порядок, «», «». При этом, если , то пишут  и говорят, то «а больше или равно b» или «b меньше или равно а». Если  и , то говорят, что «а строго больше b» или «b строго меньше а».

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

Пусть М – произвольное непустое подмножество упорядоченного множества . Тогда на М также можно определить порядок следующим образом:

и .

Этот порядок  называется порядком, индуцированным порядком  на множестве М.

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

обозначается: .

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

Действительно, отображение  такое, что ; ;  и  является биективным и   имеем:

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

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

Всякое упорядоченное множество  изоморфно упорядоченному множеству, состоящему из некоторых подмножеств множества А с отношением порядка .

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

.

Назовем  нижним отрезком, порожденным элементом а.

Через  обозначим множество всех нижних отрезков, порожденных  элементами множества А.

Покажем, что

Каждому элементу а из А поставим в соответствие  нижний отрезок , порожденный элементом а, т.е.

.

Если  и , то .Действительно, предположим противное. Тогда . Так как , то , значит . Аналогично, так как , то , значит, . Ввиду антисимметричности отсюда следует, что . Получаем противоречие, значит - инъективно.

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

Пусть теперь  и , тогда . Действительно, если , то , но , поэтому . Следовательно, .

Таким образом, если , то . Верно и обратное. А именно, если , то . Так как , то , значит .

Теорема доказана.

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

Определение. Элемент а упорядоченного множества  называется минимальным, если выполняется следующее условие:

Примеры. 1. В упорядоченном множестве  минимальными элементами являются: 2, 3, 5, 7, а 6 не является минимальным, так как  (т.е. ) и .

2. В упорядоченном множестве, состоящем из всех непустых подмножеств множества А с отношением порядка  минимальными элементами будут одноэлементные подмножества множества А.

Определение. Элемент с упорядоченного множества   называется наименьшим, если выполняется следующее условие:

.

Например, в упорядоченном множестве  наименьшего нет, а в упорядоченном множестве  наименьшим будет число 1, так как   (т.е. ).

Как следует из предыдущих примеров, минимальных элементов может быть несколько. Но наименьший элемент, если он есть, единственен. Действительно, если  и  - наименьшие, то . Так как  - наименьший и , так как  - наименьший. Поэтому, ввиду антисимметричности  получаем, что .

Определение. Элементы  и  упорядоченного множества  называются сравнимыми, если для этих элементов выполняется хотя бы одно из условий:  или .

Например, в упорядоченном множестве  3 и 6 сравнимы, так как , но 3 и 8 не сравнимы, так как 38 и 83. В упорядоченном множестве, состоящем из подмножеств некоторого множества с порядком  сравнимыми будут лишь такие множества, что одно из них является подмножеством в другом.

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

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

Примером линейно упорядоченного множества является любое множество действительны чисел с отношением порядка, совпадающим со сравнением числе по величине:

; ; ; ; ; …

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

Наиболее известным примером вполне упорядоченного множества (этот факт будет установлен выше) является множество натуральных чисел  с отношением порядка  определенным тем, что

или

Множество  не является вполне упорядоченным, так как например, во всем множестве Z нет наименьшего элемента.


§2. Условия минимальности, индуктивности и обрыва убывающий цепей, их эквивалентность.

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

Пример. Покажем, что упорядоченное множество натуральных чисел  (см.§1) обладает свойством минимальности. При этом будем считать, что все свойства натуральных чисел уже известны.

Пусть В – произвольное непустое подмножество множества натуральных чисел . Будем считать, что натуральное число а находится на К-том этаже , если в разложении числа а на простые сомножители содержится  штук простых множителей. Ясно, что число 1 находится на нулевом этаже. Отметим также, что если а находится на -том этаже, b находится на -том этаже,  и , то . Действительно, все простые сомножители из разложения b входят в разложение а. Так как , то простых сомножителей в разложении b будет меньше, чем в разложении а.

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

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

Например, пусть  и В состоит из чисел, больших 11, т.е. .

Тогда 12 находится на 3-ем этаже, так как , 13 находится на   1-ом этаже, так как 13 – простое число, 14 находится на 2-ом этаже, так как . Так как , то наименьший этаж, на котором находятся элементы из В будет первым. Поэтому минимальными в В элементами будут числа 13, 17, 19 …, т.е. все простые числа, содержащиеся в В.

Определение. Говорят, что упорядоченное множество  является упорядоченным множеством с условием обрыва убывающих цепей (обладает свойством обрыва убывающих цепей), если для любой цепи элементов  из множества А существует такой номер S (), что    (т.е. цепочка, начинающаяся с  стабилизируется).

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

Прокомментируем свойство индуктивности ввиду его громоздкости и сложности. В нем утверждается, что произвольное подмножество В множества А совпадает с А если выполняются два условия:

  1.  Все минимальные элементы множества А содержатся в В.
  2.  Из того, что все элементы меньше, чем  (где   - произвольный элемент из А) содержатся в В следует, что и сам элемент  также содержится в В.

Обозначим, соответственно, свойства индуктивности, обрыва убывающих цепей и минимальности через , О и М.

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

Доказательство проведем по следующей схеме:

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

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

Пусть теперь любой элемент, меньший чем   принадлежит В. Покажем, что тогда и сам элемент  принадлежит В.

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

.

Но тогда и цепочка, начинающаяся с  так же стабилизируется, значит, .

Если же для любого  , то цепочка будет  , поэтому стабилизируется.

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

И так далее, получаем цепочку элементов

которая, по построению, не стабилизируется.

3. Доказательство проведем методом от противного. Предположим, что существует такое подмножество В множества А, что для него выполнены оба условия 1 и 2 свойства индуктивности, но . Обозначим тогда .

Так как А обладает свойством минимальности, то в С есть по крайней мере один минимальный элемент . Так как , то . Так как для В выполняется условие 1 индуктивности, то  не является минимальным в А.

Покажем тезис, что если  и  строго меньше , то . Действительно, если бы , то  принадлежал бы С. Так как  , то в С нашелся бы элемент , который строго меньше чем его минимальный элемент. Это противоречит определению минимального элемента, поэтому . Так как для подмножества В выполняется условие 2 индуктивности, то и .

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


§3. Об условии минимальности в аксиоматической теории натуральных чисел.

Пусть  - тернарное отношение на множестве А (см.§1), тогда символ , где  означает:

Например, пусть

,

тогда ; ,

Если Х и Y – произвольные непустые подмножества множества А, то символ  означает:

Пример. , , тогда

Определение. Множество  вместе с заданными на нем двумя тернарными отношениями «» и «»и одним унарным отношением  называется множеством натуральных числе, если выполняются следующие условия (аксиомы):

1)  и

2) (а + 1 состоит из одного элемента)

3)  

4)

5)

6)

7) Если М такое подмножество N, что

1.

2. , то М=N

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

Предложение 1. (а + b состоит из одного элемента).

Доказательство. Возьмем произвольное  и через  обозначим такое множество, что

содержит 1, так как по аксиоме 1)  состоит из одного элемента. Пусть теперь , т.е.  состоит из одного элемента, тогда . Согласно аксиоме 4)  получаем, что  и .

По условию  состоит из одного элемента, значит, по аксиоме 2)  так же состоит из одного элемента. Так как  и , то  так же состоит из одного элемента. Это значит, что . Итак, из того, что  следует, что . Выполнены оба условия аксиомы 7) для множества , значит, . Это означает, что  состоит из одного элемента . Но ведь и а было выбрано произвольно, поэтому  состоит из одного элемента .

Из доказанной теоремы следует, что  определено однозначно, поэтому  называют суммой элементов а и b, а бинарную операцию «+»  сложением.

Отметим также, что выше установлено, что .

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

.

Доказательство. Возьмем произвольные натуральные числа а и b и обозначим:

.

Для доказательства теоремы достаточно доказать, что .

Согласно вышесказанному замечено , поэтому .

Пусть теперь  , тогда . Покажем, что .

согласно вышесказанному.

Но  по условию. Поэтому

.

Но  по той же причине. Поэтому

Таким образом,

, значит .

Согласно аксиоме 7) .

Предложение 3. 

Доказательство. Через  обозначим такое множество, что . Покажем, что .

Ввиду однозначности сложения, имеем , поэтому . Далее, пусть , т.е. . Тогда  благодаря условию и ассоциативности сложения. Поэтому , но тогда по аксиоме 7) получаем, что .

Предложение 4. , т.е. сложение натуральных чисел коммутативно.

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

По предыдущей теореме . Пусть , т.е. . Тогда  благодаря условию и доказанной выше теоремы. Благодаря аксиоме 7) делаем вывод, что .

Предложение 5. .

Доказательство. Определим множества  и  так, что , . Обозначим  и покажем, согласно аксиоме 7), что . Этим и будет доказана теорема.  содержит 1, т.к. .

Пусть , покажем, что . Так как , то либо , либо . Если , то  и , но  по определению , значит . Если же , то . Тогда , поэтому . В любом случае, из того, что  следует, что , поэтому .

Единственность n, указанная в теореме следует из аксиомы 3). Действительно, если , и ., то . Тогда , поэтому по аксиоме 3) получаем, что .

Предложение 6. .

Доказательство. Возьмем произвольное  и обозначим через . Покажем, что .

, так как согласно аксиоме 1) . Пусть , т.е. . Покажем, что . Отсюда, ввиду ассоциативности и коммутативности сложения получаем . Тогда по аксиоме 3) . Получаем противоречие, поэтому , значит .

Предложение 7. Для любых двух натуральных чисел выполняется одно и только одно из трех условий:

1.

2.

3.

Доказательство. Покажем сначала, что два из перечисленных условий 1)-3) не могут выполняться одновременно. Если а = b и а = b + k, что невозможно согласно предыдущему предложению. Аналогично, не может быть а = b и b = a + s. Если а = b + k и b = a + s, то опять a = b + k = (a + s) + k = a + (s + k), что невозможно согласно предыдущему предложению.

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

Пусть . Если мы покажем, что , то это и будет означать справедливость теоремы.

Покажем сначала, что . Действительно, если  а = 1, то , но . Если же , то по предыдущему предложению 5) существует такое , что а = 1 + k, значит . В любом случае получаем, что .

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

1. ;   2. ;  3.

В случае 1 имеем , поэтому , значит .

В случае 2 имеем  . Если , то , значит . Если , то . Тогда . Значит .

Наконец, в случае 3 имеем  . Тогда , поэтому .

В любом случае получаем, что из того, что  следует, что . Значит .

Определение. Пусть , тогда будем считать, что  и считать, что , если  или .

Тогда множество  будет упорядоченным множеством. Действительно, отношение  рефлексивно, так по определению  для любого . Отношение  транзитивно. Действительно, пусть  и , тогда возможны 4 случая:

1)  и

2)  и

3)  и

4)  и

В случае 1) , значит . В случаях 2 и 3 , поэтому . В случае 4 существует такие  и , что , , значит . Это означает, что , т.е.  .

Наконец, убедимся, что  антисимметрично. Пусть  и , тогда возможны 4 случая

1) и ;

2)  и ;

3)  и ;

4) и .

В случае 1) имеем . Случаи 2), 3) и 4) невозможны, так как в случаях 2) и 3) получаем, что либо  , либо , что невозможно согласно предложению 6. В случае 4) получаем  по транзитивности, что опять невозможно согласно определению > и предложению 6.

Таким образом,  антисимметрично, значит является порядком на N.

Отметим, что отношение , согласно предложению 7, является линейным порядком.

Предложение 8.

1. (если , то )

2. (если , то ).

Доказательство 1. Так как , то либо , либо . Покажем, что случай  невозможен. Действительно, если , то . Так как , то . Отсюда получаем:

.

Если s = 1, то b + 1 = b + 1 + k, что невозможно по определению 6.

Если , то . Тогда b + 1 = b + 1 + t + k, что опять невозможно по предложению 6.

Аналогично доказывается 2.

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

.

Непустое множество натуральных чисел А назовем ограниченным, если .

Предложение 9. Всякое непустое ограниченное множество А натуральных чисел имеет наибольший элемент.

Доказательство. По условию . Покажем, что при любом натуральном n А имеет наибольший элемент.

Обозначим через

, так как если , то , поэтому 1 и будет наибольшим в А.

Пусть , т.е. если , то А имеет наибольший элемент.

Покажем, что , т.е. если , то А имеет наибольший элемент.

Пусть . Покажем, что . Действительно, если , то . Если , то . Если же , то , значит . Значит . Если , то , поэтому , значит . Если , то , поэтому . Отсюда следует, что , поэтому , значит , поэтому .

Наоборот, если , то либо , либо . Если , то , тогда , значит . Если же , то опять .

Отсюда следует, что .

Если , то . Тогда в А есть наибольший элемент по условию. Если же , то наибольший в А будет с + 1. Действительно, пусть , тогда либо , либо . Если, , то . Если же , то . Это означает, что с + 1 является наибольшим в А в этом случае.

Предложение 10. Всякое непустое подмножество В множества натуральных чисел имеет наименьший элемент.

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

Пусть .

Так как  , то . Действительно, если  и , то . Если же , то , т.е.е . В любом случае . Таким образом .

Кроме того множество D ограничено, т.к. , поэтому , где b – произвольный элемент В.

По предыдущему предложению D имеет наибольший элемент, который обозначим через d.

Так как d – наибольший элемент в D, то . Поэтому существует такой элемент , что . Значит  и . Согласно предложению 7) отсюда следует, что .

Итак, получаем:

.

Отсюда, согласно предложению 8, получаем, что b = d, поэтому  . Кроме того, так как , то . Это и означает, что d является наименьшим в В, что и требовалось доказать.

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


§4. Аксиома выбора и ее роль для построения полного порядка на произвольном непустом множестве, теорема Цермело.

Одной из основополагающих аксиом математики является аксиома выбора, которая гласит:

«Если M – произвольное непустое множество, то существует функция , которая в каждом непустом подмножестве А множества М «выбирает» некоторый вполне определенный элемент».

Другими словами: «Для любого непустого множества М существует отображение  множеств и  всех непустых подмножеств множества М во множества М такое, что ».

Используя эту аксиому Цермело доказал, что всякое непустое множество можно вполне упорядочить.

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

Пусть  - произвольное вполне упорядоченное множество. Для любого  введем обозначение:

Назовем  истинным отрезком множества А, порожденным элементами а. Пусть множество также будем считать истинным отрезком, порожденным наименьшим элементом самого множества А.

Утверждение 1. Объединение любой совокупности истинных отрезков вполне упорядоченного множества А либо совпадает с А, либо снова является истинным отрезком А.

Доказательство. Пусть  - объединения произвольной совокупности истинных отрезков множества А.

Покажем, что если , то В является истинным отрезком, порожденным некоторым элементом из А.

Пусть А\В = С, тогда . Так как  вполне упорядоченно, то в С есть наименьший элемент, который обозначим через . Тогда  и .

Покажем, что . Сначала покажем, что

(*)

Предположим противное, тогда . Так как  является линейным порядком, то

.

Это означает, что , но , поэтому . Получаем противоречие, поэтому (*) истинно.

Пусть теперь , тогда , поэтому  и . Согласно (*) отсюда следует, что либо , либо . Если , то , поэтому . Если же  (), то  и , . Если бы при этом , то , поэтому , что не так, поэтому  и . Это означает, что .

Пусть . Покажем, что  от противного.

Предположим, что , тогда . Поэтому , т.е. .

Это значит, что . Кроме того  и  и . Получим противоречие с выбором , поэтому . Тем самым доказано равенство .

Пусть  - вполне упорядоченное множество и . Рассмотрим новое множество  и определим на D отношения так, что

х  y  либо  и , либо x = b, , либо x = y.

Тогда будет вполне упорядоченным множеством. Действительно, х  х  по определению. Пусть х  y и y  z, тогда априори возможны 9 случаев:

1. , ,  и

2. , , y = b,

3. ,  и y = z

4. x = a, ,  и

5. x = b, , y = b,

6. x = b, , y = z

7. x = y, ,

8. x = y, y = b,

9. x = y, y = z.

Случаи 2 и 5 невозможны, т.к.  и y = b.

В случае 1  и , поэтому х  z.

В случае 3  и , поэтому х  z.

В случае 4 x = b, , поэтому х  z.

В случае 6 x = b, , поэтому х  z.

В случае 7  и , поэтому х  z.

В случае 8 x = b, , поэтому х  z.

В случае 9 х = z, поэтому х  z.

Поэтому  транзитивно.

Пусть теперь x  y и у х, поэтому опять, аналогично случаям 1-9 возможны случаи 1)-9), в которых z = x.

В случае  1)   и , поэтому x = y. В случаях 3), 6), 7), 8) и 9) , а случаи 2), 4) и 5) невозможны.

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

Если , то либо , либо , , либо , , либо x = y = b; y  x, x  y, x  y.

Значит,   является линейным порядком.

Пусть теперь  М – произвольное непустое подмножество множества D, тогда либо , либо .

Если , то либо , либо . Если , то наименьшим в М будет b, а если , и  - наименьший элемент для  в А, то  будет наименьшим для М в D, так как b   по определению .

Если же , то М является подмножеством А. Пусть  - наименьший элемент для М в А, тогда  будет наименьшим для М в D, так как b  .

Отсюда следует, что будет вполне упорядоченным. Назовем упорядоченным множеством, полученным из   простым присоединением одного элемента.

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

Доказательство. Согласно аксиоме выбора присутствует такое отображение  в М, что

.

Назовем далее подмножество А множества М отмеченным, если выполняются следующие два условия:

  1.  А можно вполне упорядочить, т.е. на А существует полный порядок А
  2.  , где  - истинный отрезок, порожденный элементом из а из А относительно полного     порядка А.

Отметим, что М содержит отмеченные подмножества. А именно, отмеченным подмножеством будет одноэлементное подмножество  . Полный порядок на одноэлементном множестве единственен и совпадает с тривиальным порядком (=). Кроме того,

.

Пусть теперь А и В два произвольных отмеченных подмножества,  и  их наименьшие элементы, тогда  и . Отсюда, ввиду отмеченности множество А и В имеем

.

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

Непустое подмножество D назовем общим непустым истинным отрезком для А и В, если

( и порядок А на  совпадает с порядком В на ).

Обозначим через С объединение всех общих истинных для А и В отрезков. Тогда, как указано выше возможны 4 случая:

  1.  С = А и С = В;
  2.  С является истинным отрезком в А, С = В;
  3.  С = А и С является истинным отрезком в В.
  4.  С является истинным отрезком в А и С является истинным отрезком в В.

В случае 1 получаем, что А = В. В случае 2 А является истинным отрезком в В. В случае 3 В является истинным отрезком в А.

Рассмотрим случай 4. Тогда  и . Ввиду отмеченности множеств А и В получаем, что

Пусть , тогда   и  (t А х и t В х).

В случае 4 возможны 4 случая:

4.1 ;

4.2 ;

4.3 ;

4.4 ;

В случае 4.1 А = В. В случае 4.2 обозначим через  наименьший элемент разности  относительно порядка В . Тогда  и В t.

Покажем, что , т.е.  или .

Пусть , тогда либо , либо х = t. Если х = t, то, учитывая что В t и  получаем .

Пусть  и , тогда В и В х и . Так как , то , так как . Таким образом, х и . Это означает, что .

Наоборот, пусть , тогда  y и . Если y = t, то . Пусть  В y, тогда , значит .

Если же  и y В t, то , поэтому . Но  - наименьший элемент в , поэтому y  . Но по условию  y, поэтому , но по  условию . Получили противоречие, значит случай  и y  В невозможен. Таким образом,  и . Значит в случае 4.2 А является истинным отрезком в В. Аналогично, в случае 4.3 В является истинным отрезком А.

Покажем теперь, что случай 4.4 невозможен.

При рассмотрении случаев 4.2 и 4.3 было установлено, что  и , но , поэтому . Значит А и В имеют еще один общей истинный отрезок, больший чем объединение всех истинный отрезков (он содержит на один элемент «t» больше элементов). Получаем противоречие.

Таким образом во всех случаях получаем, что либо А = В, либо А является истинным отрезком в В, либо В является истинным отрезком в А.

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

(  такие отмеченные подмножества А и В, что ,  и либо а B b, если А = В, либо а A b и В является истинным отрезком в А).

Докажем, что определение  корректно. Пусть ,  ( и  - отмеченные подмножества) и либо а B1 b, если =, либо а А1 b и  является истинным отрезком .

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

1.  В  А

2. В    А

3.   В  А  

4. В    А  

5. В  А    

6. В      А

В случае 1)  в одном случае означает, что а A b, а в другом а А1 b, но   А, поэтому а A b и а А1 b совпадают.

В случае 2)  в одном случае означает, что а A b, а в другом а А1 b, но   А.

Аналогично устанавливается, что  не зависит от того, в каких отмеченных подмножествах находятся а и b в остальных случаях 3)-6).

Пусть теперь  и , где А – некоторое отмеченное множество, тогда а A а, поэтому , значит  - рефлексивно.

Пусть  и , , , , тогда С  В  А и при этом а A b и b A c, значит а A с. Учитывая, что С  А получаем, что . Значит  транзитивно.

Пусть, наконец,  и ,  и , тогда В  А и А  В и при этом а A b и b В a. Но  А  В, поэтому имеем а A b и b A a, значит а = b. Это означает, что  антисимметрично.

Таким образом  - упорядоченное множество.

Пусть теперь , . Тогда либо А = В, либо А В, либо В  А. Если А = В то либо а A b либо b A a, поэтому либо  в Т, либо  в Т.

Если А В, то  и опять либо а В b либо b В a, что означает, что  или .

Аналогично получаем, что либо  или  если В  А. Следовательно  является линейным порядком.

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

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

Итак, пусть  произвольная невозрастающая цепочка элементов из Т, , тогда из определения  следует, что

А1А1А1А1 …

Так как А1 - вполне упорядочено, то оно обладает свойством минимальности, поэтому

.

Таким образом  - вполне упорядоченно.

Покажем теперь, что .

Действительно, пусть , где А – отмеченное подмножество, тогда .

Пусть , тогда а A х и , значит а Т х и . Значит .

Наоборот, пусть , тогда  и . Так как , то , В  А и а A y, т.е.  и . Отсюда следует, что

, так как А – отмеченное подмножество.

Итак  - отмеченное подмножество.

Покажем, что Т = М, предположим противное, тогда , ,  и .

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

Поэтому, если  , то либо , либо а =  и если , то , тогда . Если же , то  и , т.е. .

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

Таким образом , значит М – вполне упорядочено.


Литература.

[1] А.Г.Курош  Лекции по общей алгебре М., Наука, 1973 г. стр. 20-28

[2] В.И.Негиев  Числовые системы М., Просвещение, 1975 г. стр. 70-88

[3] В.М.Кривенко  О строгих линейных стабильных порядках на свободных коммутативных полугруппах. Математические модели физических процессов. (сб.научных трудов 9-ой международной конференции), Таганрог, ТГПИ 2003 г. стр. 115-120


Z

X

M(a,b,c)

a

b

1

1

Y

c

1

Y

X

M(a,b)

a

b

1

1

2

1

3

4

Пример 2

2

1

3

4

Пример 1

1

2

4

8

6

9

3

1

5

7

1.

2.

;

;

;

;

;

3.

;

;

;

;

;

4.

;

;

;

;

;

;

;

;

d

a

b

c

(2)

х

y

t

z

(1)

U

O

М

U

1

2

3


 

А также другие работы, которые могут Вас заинтересовать

3677. Методические основы оценки ущерба от чрезвычайных ситуаций 135.5 KB
  Методические основы оценки ущерба от чрезвычайных ситуаций При оценке ущерба от чрезвычайных ситуаций (ЧС) необходимо опираться на существующий нормативный аппарат анализа экономических ущербов от негативного влияния хозяйственной деятельности. Важн...
3678. Техническое обслуживание и ремонт пускового карбюраторного двигателя ПД-10У. № 866 597.5 KB
  Техническое обслуживание и ремонт пускового карбюраторного двигателя ПД-10У. № 866 Введение Карбюраторными двигателями называют двигатели, в которых основная часть процесса приготовления рабочей смеси жидкого топлива с воздухом осуществляется вне ци...
3679. Методы расчета сложных электрических цепей 209 KB
  Методы расчета сложных электрических цепей Расчетное задание Для заданной электрической цепи, в которой, а остальные параметры указаны в таблице, требуется рассчитать: все токи и напряжения методом контурных токов все токи и напряжен...
3680. Проектирование многокаскадного усилителя на БПТ 652 KB
  Аннотация В данной курсовой работе поэтапно рассматривается пример проектирования многокаскадного усилителя на БПТ. Производится расчет входного, согласующего каскадов и каскадов предварительного усиления. Также конструируется печатная плата усилите...
3681. Автономная эволюция минералов 287.5 KB
  Автономная эволюция минералов В природе найдено несколько сот тысяч различных видов молекул, более полумиллиона их создано искусственно. Минералы относятся к числу первых. Их определяют по химическому составу и по кристаллической структуре. По соста...
3682. Эпителиальные и соединительные ткани 1.72 MB
  Классификация тканей. Ткань – это исторически (филогенетически) сложившаяся система клеток и неклеточных структур, обладающих общностью строения, специализирующаяся на выполнении определенных функций. Каждая ткань происходит из опре...
3683. Нормативно-правовая база принятия управленческих решений в области безопасности 125 KB
  Обеспечение безопасности, как, собственно, все функции любого государства, подвергается нормативно-правовому регулированию. В объективном смысле понятие безопасность можно определить как состояние защищенности жизненно-важных интересов госу...
3684. МЕТОДИКА РАЗВИТИЯ ОБЩЕЙ И СПЕЦИАЛЬНОЙ ВЫНОСЛИВОСТИ ХОККЕИСТОВ 13-14 ЛЕТ 104.87 KB
  Выносливость – это способность человека к длительному выполнению какой-либо работы без заметного снижения работоспособности. А уровень выносливости обычно определяется временем, в течение которого человек может выполнять заданное физическое упражнение. Чем продолжительнее время работы, тем больше выносливость
3685. Проверка второго закона Ньютона на машине Атвуда 82 KB
  Проверка второго закона Ньютона на машине Атвуда ЦЕЛЬ: установить зависимость ускорения системы от действующей силы; определить из полученной зависимости массу системы. ОБОРУДОВАНИЕ: экспериментальная установка FRM, электронный секундомер с фотоэлек...