Счётное объединение счётных множеств без аксиомы выбора

[Someone]

Инт в сообщении #151736 писал(а):

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

Будьте любезны привести полное доказательство в системе ZF (без аксиомы выбора).

P.S. Этот пункт удалён автором из первоначального сообщения. Цитата сохранилась здесь: http://dxdy.ru/post151786.html#151786.

[Профессор Снэйп]

Someone писал(а):

Инт в сообщении #151736 писал(а):

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

Будьте любезны привести полное доказательство в системе ZF (без аксиомы выбора).

Я слышал, что это не доказуемо.

[Xaositect]

А чем не проходит такое доказательство:
Возьмем рекурсивную взаимно однозначную функцию $p\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, например $p(x,y) = \frac{(x+y-1)(x+y)} 2 + y+1$.
Пересчитаем $\bigcup_i U_i$ следующим образом: $k$-му элементу множества $U_n$ поставим в соответствие номер $p(n,k)$. Таким образом получается некоторое отображение $\mathbb{N}\to \bigcup_i U_i$, не обязательно взаимно-однозначное. Чтобы сделать из него взаимно-однозначное, надо для каждого элемента пройтись по всем до него(конечное множество), сдвигая нумерацию на 1 влево, если элемент уже встречался.

[Профессор Снэйп]

Xaositect писал(а):

А чем не проходит такое доказательство:
Возьмем рекурсивную взаимно однозначную функцию $p\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, например $p(x,y) = \frac{(x+y-1)(x+y)} 2 + y+1$.
Пересчитаем $\bigcup_i U_i$ следующим образом: $k$-му элементу множества $U_n$ поставим в соответствие номер $p(n,k)$. Таким образом получается некоторое отображение $\mathbb{N}\to \bigcup_i U_i$, не обязательно взаимно-однозначное. Чтобы сделать из него взаимно-однозначное, надо для каждого элемента пройтись по всем до него(конечное множество), сдвигая нумерацию на 1 влево, если элемент уже встречался.

А не проходит оно вот чем.

Когда Вы говорите "$k$-му элементу множества $U_i$", то тем самым подразумеваете, что все множества $U_i$ занумерованы неким "равномерным" образом. То есть что для любого $i \in \mathbb{N}$ выбрана функция $u_i : \mathbb{N} \to U_i$, такая что $U_i = \{ u_i(1), \ldots, u_i(k), \ldots \}$.

То, что для каждого конкретного $U_i$ функция $u_i$ существует, можно утверждать, не привлекая никакой аксиомы выбора, ибо существование такое функции равносильно счётности множества $U_i$, которая у нас есть по условию. Однако для того, чтобы установить существование семейства $\{ u_i : i \in \mathbb{N} \}$, аксиома выбора уже нужна. Вы же в предложенном Вами доказательстве используете именно наличие семейства.

[Someone]

Профессор Снэйп писал(а):

Someone писал(а):

Инт в сообщении #151736 писал(а):

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

Будьте любезны привести полное доказательство в системе ZF (без аксиомы выбора).

Я слышал, что это не доказуемо.

Я в курсе.

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

[Профессор Снэйп]

Someone писал(а):

Я в курсе.

Я в курсе, что Вы в курсе. Отвечал не Вам, а Xaositect.

А вот что мне интересно, так это следующие два вопроса:

1) Насчёт того, что объединение счётного семейства счётных множеств будет счётным... Доказано ли, что этот факт не доказуем в ZF без аксиомы выбора, или просто неизвестно, как его без аксиомы выбора доказывать?

2) Мы говорим, что $|A| \leqslant |B|$, если существует инъективная функция из $A$ в $B$. С аксиомой выбора легко доказать следующее утверждение:

$|A| \leqslant |B|$ тогда и только тогда, когда $A = \varnothing$ или существует сюрьективная функция $g$ из $B$ в $A$.

Можно ли доказать этот факт, не используя аксиому выбора? Если в общем случае нельзя, то можно ли это сделать в случае, когда $B$ счётно, или когда $B$ вполне упорядочено?

Добавлено спустя 13 минут 56 секунд:

P. S. Насчёт Инт... Это который тему о теореме Гёделя завёл? Я посмотрел на название, подумал "ну вот, ещё один ниспровергатель основ в стиле a-la Давидюк" и даже не стал туда залазить. Someone, скажите, там есть что-нибудь ценное, или просто 3 страницы бреда, читать который --- только время зря тратить?

[Xaositect]

Профессор Снэйп в сообщении #152431 писал(а):

А не проходит оно вот чем.

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

Добавлено спустя 1 час 1 минуту 30 секунд:

В параграфе 10 главы IV книги Коэна "Теория множеств и континуум-гипотеза"(http://lib.mexmat.ru/books/911) рассматривается модель ZF, в которой континуум является счетным объединением счетных множеств.

[Someone]

Профессор Снэйп в сообщении #152453 писал(а):

Насчёт того, что объединение счётного семейства счётных множеств будет счётным... Доказано ли, что этот факт не доказуем в ZF без аксиомы выбора, или просто неизвестно, как его без аксиомы выбора доказывать?

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

Профессор Снэйп писал(а):

Мы говорим, что $|A| \leqslant |B|$, если существует инъективная функция из $A$ в $B$. С аксиомой выбора легко доказать следующее утверждение:

$|A| \leqslant |B|$ тогда и только тогда, когда $A = \varnothing$ или существует сюрьективная функция $g$ из $B$ в $A$.

Можно ли доказать этот факт, не используя аксиому выбора? Если в общем случае нельзя, то можно ли это сделать в случае, когда $B$ счётно, или когда $B$ вполне упорядочено?

Мне кажется, аксиома выбора не нужна. Пусть $A\neq\varnothing$ и пусть $f\colon A\to B$ - инъективное отображение. Выберем любой элемент $a_0\in A$ и определим отображение $g\colon B\to A$ так:

$$gb=\begin{cases}f^{-1}b\text{, если }b\in fA\text{,}\\ a_0\text{, если }b\in B\setminus fA\text{.}\end{cases}$$

Профессор Снэйп в сообщении #152453 писал(а):

P. S. Насчёт Инт... Это который тему о теореме Гёделя завёл? Я посмотрел на название, подумал "ну вот, ещё один ниспровергатель основ в стиле a-la Давидюк" и даже не стал туда залазить. Someone, скажите, там есть что-нибудь ценное, или просто 3 страницы бреда, читать который --- только время зря тратить?

Безусловно, это "ниспровержение основ". Я посмотрел начало и пришёл к выводу, что Инт путает теорию и метатеорию. Очень похоже, что он считает теорему Гёделя теоремой арифметики, в то время как она, видимо, всё-таки метатеорема. Однако я не специалист в математической логике, с деталями доказательства теоремы Гёделя не знаком, поэтому ввязываться в спор не стал. Но было бы неплохо, если бы специалист эту тему посмотрел и высказал своё мнение. Не столько для Инта, сколько для других неспециалистов, которые читают эту тему.

P.S. У меня есть некоторое подозрение, что Инт здесь на мои вопросы отвечать не будет.

[Инт]

Господа. Насколько я вижу у Вас исчерпаны аргументы в пользу т.н. "теоремы Гёделя".
Что же касается указанной темы, то так как я обещал ответить на все вопросы, и сейчас свободен, то обязательно на них отвечу. Всем привет. Ждите ответа.

[Someone]

Инт писал(а):

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

В этой теме никто не собирался обсуждать теорему Гёделя.

Someone в сообщении #152584 писал(а):

Утверждение, что объединение счётного множества (не более, чем) счётных множеств будет (не более, чем) счётным, слабее счётной аксиомы выбора, но из него следует существование функции выбора для счётного множества (не более, чем) счётных множеств

И даже несколько более. Если множество $U=\bigcup\{A_k:k\in\mathbb N\}$ не более чем счётно, то есть, существует отображение $f\colon\mathbb N\xrightarrow{\text{на}}U$, то это даёт не только полное упорядочение множеств $U$ и $A_k$, $k\in\mathbb N$, что позволяет определить функцию выбора на семействе множеств $\{A_k:k\in\mathbb N\}$, но также позволяет определить отображения $f_k\colon\mathbb N\xrightarrow{\text{на}}A_k$, $k\in\mathbb N$, что даёт функцию выбора на счётном семействе множеств $\{A_k^{\mathbb N}:k\in\mathbb N\}$, $k\in\mathbb N$, которые несчётны, если $A_k$, $k\in\mathbb N$, содержит больше одного элемента ($A_k^{\mathbb N}$ - множество всех отображений множества $\mathbb N$ в множество $A_k$). Но, разумеется, это не является счётной аксиомой выбора в полном объёме.

[Инт]

Цитата:

Очень похоже, что он считает теорему Гёделя теоремой арифметики, в то время как она, видимо, всё-таки метатеорема.

Цитата:

было бы неплохо, если бы специалист эту тему посмотрел и высказал своё мнение.

Может кто-нибудь упросит, например, Успенского?

Теорема Гёделя - метатеорема. Это не "видимо", это точно. Подтверждаю.

А если тему Гёделя здесь не обсуждаем, то просьба и не обсуждать.

Добавлено спустя 6 минут 17 секунд:

Xaositect-у

Цитата:

А чем не проходит такое доказательство:
Возьмем рекурсивную взаимно однозначную функцию...

На самом деле Xaositect почти правильно привёл предварительное рассуждение.
Ясно, что необходим строгий вывод из аксиом теории множеств.

[Xaositect]

Инт в сообщении #152932 писал(а):

На самом деле Xaositect почти правильно привёл предварительное рассуждение.
Ясно, что необходим строгий вывод из аксиом теории множеств.

Как тут уже сказали, этот вывод не переводится на формальный язык без акситомы выбора, потому что мы можем доказать, что $\forall i \exists f\colon \mathbb{N}\leftrightarrow u_i$, но для того, чтобы перейти от этого к двойной нумерации($\exists F\colon\mathbb{N}\times\mathbb{N}\to \bigcup_i u_i \& \forall i F(i)\colon \mathbb{N}\leftrightarrow u_i)$ необходима аксиома выбора(счетная, или даже чуть слабее), необходимо выбрать конкретную нумерацию из существующих для каждого множества.

[Инт]

Xaositect-у

Цитата:

Как тут уже сказали...

Пока я по существу не отвечал на вопрос.

[Профессор Снэйп]

Someone писал(а):

Профессор Снэйп писал(а):

Мы говорим, что $|A| \leqslant |B|$, если существует инъективная функция из $A$ в $B$. С аксиомой выбора легко доказать следующее утверждение:

$|A| \leqslant |B|$ тогда и только тогда, когда $A = \varnothing$ или существует сюрьективная функция $g$ из $B$ в $A$.

Можно ли доказать этот факт, не используя аксиому выбора? Если в общем случае нельзя, то можно ли это сделать в случае, когда $B$ счётно, или когда $B$ вполне упорядочено?

Мне кажется, аксиома выбора не нужна. Пусть $A\neq\varnothing$ и пусть $f\colon A\to B$ - инъективное отображение. Выберем любой элемент $a_0\in A$ и определим отображение $g\colon B\to A$ так:

$$gb=\begin{cases}f^{-1}b\text{, если }b\in fA\text{,}\\ a_0\text{, если }b\in B\setminus fA\text{.}\end{cases}$$

А в другую сторону почему нет доказательства? В утверждении ведь сказано "тогда и только тогда". И вот когда начнёте доказывать в обратную сторону, то аксиома выбора сразу и вылезет наружу

[Инт]

Цитата:

Доказательство истинно только для самого себя; оно не свидетельствует ни о чём, кроме наличия доказательств, а это ничего не доказывает.

Интересная философская позиция. Удобная.

Скоро буду. Только хотел Вам написать. Снова серьёзно отвлекли по другой теме.
Всё. Сосредотачиваюсь на этой теме.