2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 О возможности упорядочения множества в ZFC и акс. фундирован
Сообщение19.03.2015, 15:56 


08/03/11
270
Необходима ли аксиома фундирования для возможности упорядочения множества в ZFC ?

 Профиль  
                  
 
 Re: О возможности упорядочения множества в ZFC и акс. фундирован
Сообщение04.04.2015, 12:00 
Заслуженный участник
Аватара пользователя


20/08/14
5172
Нет, не необходима. В книге
К. Куратовский, А. Мостовский. Теория множеств. М.: Мир, 1970
основные теоремы ZFC доказываются без использования аксиомы фундирования.

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

 Профиль  
                  
 
 Re: О возможности упорядочения множества в ZFC и акс. фундирован
Сообщение04.04.2015, 13:54 
Заслуженный участник


09/05/08
1155
Новосибирск
В рамках древней-придревней dxdy-темы возникло пожелание
увидеть достаточно строгое и подробное доказательство (в ZFC)
теоремы Цермело о вполне упорядочении. В ответ на это пожелание
был сочинен один из возможных вариантов такого доказательства.
(Следует отметить, что при этом ничего нового изобретено не было.
Это всего лишь слегка осовремененное и чуть-чуть оптимизированное
доказательство, изложенное в монографии П.С.Александрова
«Введение в теорию множеств и общую топологию», глава 3, §5.)

Текст доказательства можно скачать в виде PDF-файла.
По традиции этот текст дублирован ниже в теле сообщения.
Итак...

Теорема Цермело
Любое множество может быть вполне упорядочено
Подробное доказательство в ZFC

Пусть $s$ — произвольное непустое множество.
По аксиоме выбора существует такая функция $f:\mathcal P(s)\backslash\{\varnothing\}\to s$,
    что $f(x)\in x$ для всех $x\in\mathcal P(s)\backslash\{\varnothing\}$.
Для $x\in\mathcal P(s)\backslash\{s\}$ положим $\sigma_x:=f(s\backslash x)$. Заметим, что $\sigma_x\notin x$.
Для $x\in\mathcal P(s)\backslash\{s\}$ положим $x^+:=x\cup\{\sigma_x\}$.
Введем обозначение $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$ для отношения сравнимости: $(x\subseteq y$ или $y\subseteq x)$.

Лемма 1. Пусть $x,y\in\mathcal P(s)\backslash\{s\}$, $x\subseteq y^+$, $y\subseteq x^+$. Тогда $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.

    Итак, пусть $x\subseteq y\cup\{\sigma_y\}$ и $y\subseteq x\cup\{\sigma_x\}$.
    Наша цель — показать, что $x\cup\{\sigma_x\}\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y\cup\{\sigma_y\}$.
    Если $\sigma_x\in y$, то $x\cup\{\sigma_x\}\subseteq y\cup\{\sigma_y\}\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.
    Если $\sigma_y\in x$, то $y\cup\{\sigma_y\}\subseteq x\cup\{\sigma_x\}\cup\{\sigma_y\}=x\cup\{\sigma_x\}$.
    Пусть теперь $\sigma_x\notin y$ и $\sigma_y\notin x$.
      Поскольку $x\subseteq y\cup\{\sigma_y\}$ и $\sigma_y\notin x$, мы имеем $x\subseteq y$.
      Поскольку $y\subseteq x\cup\{\sigma_x\}$ и $\sigma_x\notin y$, мы имеем $y\subseteq x$.
      Следовательно, $x=y$, а значит, $x\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.

Положим $\mathbb S:=\bigl\{X\subseteq\mathcal P(s):\varnothing\in X,\,(\forall\,Y\subseteq X)({\cup}Y\in X),\,(\forall\,x\in X\backslash\{s\})(x^+\in X)\bigr\}$.
Заметим, что $\mathbb S\ne\varnothing$, так как, например, $\mathcal P(s)\in\mathbb S$.
Положим $S:={\cap}\mathbb S$.
Как легко видеть, $\varnothing\in S,\ (\forall\,Y\subseteq S)({\cup}Y\in S),\ (\forall\,x\in S\backslash\{s\})(x^+\in S)$.
Иными словами, $S\in\mathbb S$.
Следовательно, $S$ — наименьший по включению элемент $\mathbb S$, т.е. $S=\min\mathbb S$.
Для $x\in S$ обозначим через $[x]$ множество всех элементов $S$, сравнимых с $x$,
    т.е. положим $[x]:=\{y\in S : x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y\}$.
Для $X\subseteq S$ обозначим через $[X]$ множество всех элементов $S$,
    сравнимых со всеми элементами $X$, т.е. положим
    $[X]\,:=\,\bigcap_{x\in X}[x]\,=\,\bigl\{y\in S : (\forall\,x\in X)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)\bigr\}\,=\,\{y\in S : X\subseteq [y]\}$.
Отметим, что $[x]=[\{x\}]$ для всякого $x\in S$.

Лемма 2. Пусть $X\subseteq S$ и $Y\subseteq [X]$. Тогда ${\cup}Y\in [X]$.

    Положим $\bar y:={\cup}Y$ и покажем, что $\bar y\in [X]$.
    Поскольку $Y\subseteq [X]\subseteq S$, мы имеем ${\cup}Y\in S$, т.е. $\bar y\in S$.
    Пусть $x\in X$. Покажем, что $\bar y\in [x]$, т.е. $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,\bar y$.
      Поскольку $Y\subseteq [X]\subseteq [x]$, мы имеем $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$ для всех $y\in Y$.
      Если $y\subseteq x$ для всех $y\in Y$, то $\bar y\subseteq x$.
      Если же $y\nsubseteq x$ для некоторого $y\in Y$, то $x\subseteq y$, а значит, $x\subseteq\bar y$.

Лемма 3. Пусть $x\in [S]\backslash\{s\}$, $y\in [x^+]\backslash\{s\}$. Тогда $y^+\in [x^+]$.

    Поскольку $y\in [x^+]\backslash\{s\}\subseteq S\backslash\{s\}$, мы имеем $y^+\in S$.
    Покажем, что $y^+\in [x^+]$, т.е. $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.
      Поскольку $x\in [S]$ и $y^+\in S$, мы имеем $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.
      Если $y^+\subseteq x$, то, очевидно, $y^+\subseteq x^+$.
      Пусть теперь $x\subseteq y^+$.
        Поскольку $y\in [x^+]$, мы имеем $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$.
        Если $x^+\subseteq y$, то, очевидно, $x^+\subseteq y^+$.
        Если же $y\subseteq x^+$, то $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$ по лемме 1.

Лемма 4. Справедливо включение $[S]\in\mathbb S$.

    По определению $[S]=\bigl\{y\in S : (\forall\,x\in S)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)\bigr\}=\{y\in S : [y]=S\}$.
    Ясно, что $\varnothing\in [S]$.
    Условие $(\forall\,Y\subseteq [S])({\cup}Y\in [S])$ следует из леммы 2 (для $X=S$).
    Осталось показать, что $(\forall\,x\in [S]\backslash\{s\})(x^+\in [S])$.
      Итак, пусть $x\in [S]\backslash\{s\}$. Покажем, что $x^+\in [S]$.
      Поскольку $x\in [S]\backslash\{s\}\subseteq S\backslash\{s\}$, мы имеем $x^+\in S$.
      Покажем, что $[x^+]\in\mathbb S$.
        Ясно, что $\varnothing\in [x^+]$.
        Условие $(\forall\,Y\subseteq [x^+])({\cup}Y\in [x^+])$ следует из леммы 2 (для $X=\{x^+\}$).
        Условие $(\forall\,y\in [x^+]\backslash\{s\})(y^+\in [x^+])$ следует из леммы 3.
      Поскольку $[x^+]\in\mathbb S$ и $[x^+]\subseteq S=\min\mathbb S$, мы имеем $[x^+]=S$, т.е. $x^+\in [S]$.

Лемма 5. Множество $S$ вполне упорядочено отношением $\subseteq$.

    Покажем линейность порядка: $(\forall\,x,y\in S)(x\subseteq y$ или $y\subseteq x)$.
      По лемме 4 мы имеем $[S]\in\mathbb S$. С другой стороны, $[S]\subseteq S=\min\mathbb S$.
      Следовательно, $[S]=S$, т.е. $(\forall\,x,y\in S)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)$.
    Покажем, что всякое непустое подмножество $S$ имеет наименьший элемент.
      Итак, пусть $\varnothing\ne Z\subseteq S$. Покажем, что $Z$ имеет наименьший элемент.
      Положим $Y:=\{y\in S : (\exists\,z\in Z)(z\subseteq y)\}$.
      Достаточно показать, что $Y$ имеет наименьший элемент.
      Положим $X:=S\backslash Y$.
      Как легко видеть, $X=\{x\in S : (\forall\,y\in Y)(x\subset y)\}$.
      Положим $\bar x:=\cup X$.
      Поскольку $(\forall\,y\in Y)(\forall\,x\in X)(x\subset y)$, мы имеем $(\forall\,y\in Y)(\bar x\subseteq y)$.
      Поскольку $X\subseteq S$, мы имеем $\cup X\in S$, т.е. $\bar x\in S$.
      Если $\bar x\in Y$, то с учетом $(\forall\,y\in Y)(\bar x\subseteq y)$ мы имеем $\bar x=\min Y$.
      Пусть теперь $\bar x\notin Y$, т.е. $\bar x\in X$.
        Заметим, что $\bar x=\max X$ и $(\forall\,y\in Y)(\bar x\subset y)$.
        Поскольку $\bar x\notin Y$ и $s\in Y$, мы имеем $\bar x\ne s$.
        Поскольку $\bar x\in S\backslash\{s\}$, мы имеем $\bar x^+\in S$.
        Поскольку $\bar x=\max X$, мы имеем $\bar x^+\notin X$, т.е. $\bar x^+\in Y$.
        Покажем, что $\bar x^+=\min Y$.
          Если бы нашелся $y\in Y$ такой, что $y\subset\bar x^+$, то мы бы
          имели $\bar x\subset y\subset\bar x\cup\{\sigma_{\bar x}\}$, что, очевидно, невозможно.

Лемма 6. Функция $x\mapsto\sigma_x$ является биекцией $S\backslash\{s\}$ на $s$.

    Пусть $x,y\in S\backslash\{s\}$, $x\ne y$. Покажем, что $\sigma_x\ne\sigma_y$.
      Не нарушая общности, будем считать, что $x\subset y$.
      Поскольку $x\in S\backslash\{s\}$, мы имеем $x^+\in S$.
      Ясно, что $x^+=x\cup\{\sigma_x\}=\min\{z\in S : x\subset z\}$.
      Следовательно, $x\cup\{\sigma_x\}\subseteq y$, а значит, $\sigma_x\in y$.
      С другой стороны, $\sigma_y\notin y$ и поэтому $\sigma_x\ne\sigma_y$.
    Пусть $\sigma\in s$. Покажем, что $(\exists\,x\in S\backslash\{s\})(\sigma_x=\sigma)$.
      Положим $Y:=\{y\in S : \sigma\notin y\}$ и $x:=\cup Y$.
      Поскольку $Y\subseteq S$, мы имеем $\cup Y\in S$, т.е. $x\in S$.
      По определению $x$ мы имеем $\sigma\notin x$. В частности, $x\ne s$.
      Поскольку $x\in S\backslash\{s\}$, мы имеем $x^+\in S$.
      Покажем, что $\sigma_x=\sigma$.
        Действительно, если бы $\sigma_x\ne\sigma$, то с учетом $\sigma\notin x$
        мы бы имели $\sigma\notin x\cup\{\sigma_x\}=x^+\in S$ и тем самым $x^+\in Y$,
        что противоречит соотношениям $x=\cup Y$ и $x\subset x^+$.

Из лемм 5 и 6 следует, что множество $s$ может быть вполне упорядочено.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group