- Утверждения
-
Утверждения, эквивалентные аксиоме выбора
В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений:
- Аксиома выбора
- Теорема Цермело
- Принцип максимума Хаусдорфа
- Лемма Куратовского-Цорна
Эквивалентность этих предложений следует понимать в том смысле, то любое из них, вместе с системой аксиом Цермело — Френкеля (ZF) для теории множеств достаточно, чтобы доказать остальные.
Содержание
Лемма Цорна и принцип максимума Хаусдорфа
Формулировки леммы Цорна (англ. Zorn's Lemma).
Частично упорядоченное множество, в котором любая цепь имеет верхную грань, содержит максимальный элемент.
Если всякая цепь в частично упорядоченном множестве M имеет верхнюю грань, то всякий элемент из M подчинен некоторому максимальному.
Пусть семейство множеств обладает тем свойством, что объединение любой цепи множеств из есть снова множество этой семейства. Тогда содержит максимальное множество.
Формулировки принципа максимума Хаусдорфа (англ. Hausdorff Maximal Principle):
В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество
В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.
Будем доказывать эквивалентность этих предложений по следующей схеме:
Ясно, что следует из , поскольку в утверждается большее: существует максимальный элемент, больший заданного a. Обратно, пусть M — частично упорядоченное множество, в котором всякая цепь имеет верхную грань, и пусть . Применим к множеству . Его максимальный элемент также является и максимальным элементом M, и кроме того, удовлетворяет условию .
Семейство множеств частично упорядочено по теоретико-множественному отношению включения . Любая цепь множеств {Mα} имеет верхнюю грань — ей является множество , которое по предположению принадлежит системе . В силу в семействе есть максимальный элемент, то есть максимальное по включению множество.
Пусть M — частично упорядоченное множество, C0 — цепь в M, — множество всех цепей в M, содержащих C0, упорядоченных по отношению включения. Существование максимальной цепи, содержащей C0 теперь вытекает из , примененительно к , и того факта, что объединение всех множеств цепи в («цепи цепей»), снова есть множество из .
Очевидно. — частный случай , когда исходная цепь — пустое множество .
Пусть M — частично упорядоченное множество в условии . Рассмотрим максимальную цепь C в M, существование которой вытекает из . По условию эта цепь имеет верхнюю грань . Тогда является максимальным элементом M, и кроме того, принадлежит цепи. Предположив противное, мы придем к противоречию с условием максимальности C.
Эти рассуждения доказывают эквивалентность принципа максимума Хаусдорфа и леммы Цорна.
Теорема Цермело
Формулировка теоремы Цермело (англ. Well Ordering Principle)
Любое множество можно вполнеупорядочить.
Пусть M — произвольное данное множество. Покажем, что его можно вполне упорядочить.
Рассмотрим совокупность всех пар , где , а — отношение вполнеупорядочивания на A. На множестве введем естественное отношение порядка: следует за , если есть начальный отрезок , то есть если для некоторого и на множестве A отношения совпадает с .
Далее докажем два утверждения.
I. В существует максимальный элемент. Это следует из и того факта, что если — цепь в , то объединение всех элементов есть также элемент , который является верхней гранью цепи .
II. Если — максимальный элемент, то A = M. Если бы было непусто, то взяв какой-нибудь элемент , и положив b > a для любого , мы получили бы вполнеупорядоченное множество , начальным отрезком которого является A. Это противоречит предположению о максимальности .
Таким образом, мы имеем вполне упорядоченное множество . Что и требовалось доказать.
Пусть — частично упорядоченное множество. В силу теоремы Цермело множество M можно вполне упорядочить. Пусть — отношение вполнеупорядочивания на M.
Определим разбиение множества M на два подмножества C и индукцией по вполнеупорядоченному множеству (такой способ также называется транфинитной рекурсией).
Пусть и все элементы b < a уже отнесены либо к C, либо к . Отнесем a к C, если он сравним со всеми элементами C; в противном случае отнесем его к .
Проводя таким образом индуктивное построение по вполнеупорядоченному множеству мы получим множества C и . Как видно из построения C — цепь в . Кроме того ясно что она является максимальной. Таким образом, мы доказали принцип максимума Хаусдорфа.
Аксиома выбора
Формулировка аксиомы выбора (англ. Axiom of Сhoice).
Для всякого семейства непустых множеств существует функция выбора f, то есть
Достаточно доказать, эквивалентность одному из предложений . Однако ниже приведены несколько доказательств.
См. книгу Хаусдорфа, или Куроша
Рассуждение аналогичное тому, что использовалось при доказательстве .
Упорядочим каждое {Sα}, и затем определим функцию выбора как минимальный элемент множества:
- f(α) = minSα
См. книгу Куроша
Литература
- Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — 368 с.
- Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — 572 с. — ISBN 5-9221-0266-4
- Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М.: «НАУКА», 1973. — 400 с.
- Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2
Wikimedia Foundation. 2010.
Утверждения, эквивалентные аксиоме выбора — В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений: Аксиома выбора Теорема Цермело Принцип максимума Хаусдорфа Лемма Куратовского Цорна Эквивалентность этих предложений следует понимать в… … Википедия
Утверждения о себе — (self statements) согласно некоторым когнитивным теоретикам, это утверждения о себе, иногда совершенно непродуктивные, которые приходят в голову во время стрессовых ситуаций … Общая психология: глоссарий
ГОСТ Р 41.10-99: Единообразные предписания, касающиеся официального утверждения транспортных средств в отношении электромагнитной совместимости — Терминология ГОСТ Р 41.10 99: Единообразные предписания, касающиеся официального утверждения транспортных средств в отношении электромагнитной совместимости оригинал документа: 42 Ветровое стекло и другие стекла 43 Краткое описание… … Словарь-справочник терминов нормативно-технической документации
испытание для утверждения типа — 3.3 испытание для утверждения типа: Вид государственного метрологического контроля вновь разработанного трансформатора, проводимого в целях обеспечения единства измерений, утверждения типа трансформатора и занесения его в Государственный реестр… … Словарь-справочник терминов нормативно-технической документации
Процедуры официального утверждения типа — 4.1 Процедуры официального утверждения типа 4.1.1 Официальное утверждение типа транспортного средства По усмотрению предприятия изготовителя транспортного средства могут использоваться указанные ниже альтернативные процедуры для официального… … Словарь-справочник терминов нормативно-технической документации
ГРИФ УТВЕРЖДЕНИЯ ДОКУМЕНТА — 1) согласно ГОСТ Р 51141–98 «Делопроизводство и архивное дело. Термины и определения», – реквизит официального документа, придающий нормативный или правовой характер его содержанию; 2) согласно ГОСТ Р 6.30–2003 УСД «Унифицированная система… … Делопроизводство и архивное дело в терминах и определениях
ГОСТ Р 41.7-99: Единообразные предписания, касающиеся официального утверждения передних габаритных огней, задних габаритных (боковых) огней, сигналов торможения и контурных огней механических транспортных средств (за исключением мотоциклов) и их прицепов — Терминология ГОСТ Р 41.7 99: Единообразные предписания, касающиеся официального утверждения передних габаритных огней, задних габаритных (боковых) огней, сигналов торможения и контурных огней механических транспортных средств (за исключением… … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р 41.13-99: Единообразные предписания, касающиеся официального утверждения транспортных средств категорий M, N и O в отношении торможения — Терминология ГОСТ Р 41.13 99: Единообразные предписания, касающиеся официального утверждения транспортных средств категорий M, N и O в отношении торможения оригинал документа: 2.11 автоматическое торможение: Торможение одного из нескольких… … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р 41.9-99: Единообразные предписания, касающиеся официального утверждения транспортных средств категорий L2, L4 и L5 в связи с производимым ими шумом — Терминология ГОСТ Р 41.9 99: Единообразные предписания, касающиеся официального утверждения транспортных средств категорий L2, L4 и L5 в связи с производимым ими шумом оригинал документа: 2.1 официальное утверждение транспортного средства:… … Словарь-справочник терминов нормативно-технической документации
ГОСТ Р 41.13-Н-99: Единообразные предписания, касающиеся официального утверждения легковых автомобилей в отношении торможения — Терминология ГОСТ Р 41.13 Н 99: Единообразные предписания, касающиеся официального утверждения легковых автомобилей в отношении торможения: 2.1. антиблокировочная система: Элемент системы рабочего тормоза, который во время торможения… … Словарь-справочник терминов нормативно-технической документации