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

[sceptic]

Это так. Но глаз режет .

[AGu]

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

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

И тем не менее, можно ли зафиксировать какую-нибудь конкретную теорию (например, ZF) и соответствующую метатеорию (например, тоже ZF), четко сформулировать цитированное утверждение и строго его доказать? Т.е. доказать, что "всякий раз... можно доказать..."? Иначе какое-то бездоказательное утверждение получается. ("Четко" и "строго" -- разумеется, в современном понимании этих слов.)

Если же формализм тут не предполагается, то мой вопрос снимается. (Впрочем, тогда цитированное утверждение так и останется недоступным моему пониманию. Я, к своему стыду, не умею рассуждать "содержательно", не владея формальными определениями и четко заданными доказательными средствами.)

[Инт]

AGu писал(а):

И тем не менее, можно ли зафиксировать какую-нибудь конкретную теорию (например, ZF) и соответствующую метатеорию (например, тоже ZF), четко сформулировать цитированное утверждение и строго его доказать? Т.е. доказать, что "всякий раз... можно доказать..."? Иначе какое-то бездоказательное утверждение получается. ("Четко" и "строго" -- разумеется, в современном понимании этих слов.)

Если же формализм тут не предполагается, то мой вопрос снимается. (Впрочем, тогда цитированное утверждение так и останется недоступным моему пониманию. Я, к своему стыду, не умею рассуждать "содержательно", не владея формальными определениями и четко заданными доказательными средствами.)

Плохо, что не умеете рассуждать содержательно. Именно реальным содержательным знанием руководствуется обычно математик. Как выразить это знание в той или иной теории - вторичный вопрос. Формальная теория может рассматриваться как та или иная "система счисления" или "система координат", не более.

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

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

[AGu]

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

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

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

[Инт]

AGu писал(а):

Это было неформальное ("содержательное"?) высказывание?

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

Someone писал(а):

В "содержательной", то есть, неформализованной теории средства доказательства не зафиксированы. Вы просто можете взять, допустим, некоторое обобщение метода индукции, которое обычно применяется, и сказать, что он не использует аксиомы выбора. Смысла в этом утверждении не будет, потому что в неформализованной теории аксиомы не зафиксированы, и невозможно определить, какие из них используются. В ZF этот метод будет неформализуем и, следовательно, его применение запрещено, а в ZFC он будет формализоваться с помощью аксиомы выбора.

Я согласен с Someone в том, что пренебрегать аксиомой выбора при общем, не конкретном описании множеств вряд ли стоит. Аксиома достаточно полезна. Но утверждать, что эту аксиому с необходимостью требуется использовать в рассуждениях, доказывающих теорему по-существу, неверно. Возможно больше поймёт меня тот, кто пытался решить или решил какую-нибудь трудную задачу теории множеств, когда однозначная опора на ту или иную теорию означает неоправданное ограничение на реальную логику.

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

[AGu]

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

Высказывание всегда можно формализовать в какой-нибудь формальной достаточно богатой теории.

Было бы любопытно понаблюдать за этим процессом. (Впрочем, не настаиваю.)

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

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

Интересно, но пока "бездоказательно". Опять-таки, было бы интересно взглянуть на попытку доказательства. Что-нибудь в таком роде: Будем говорить, что множество X является конкретным, если... Допустим, существует конкретное X такое, что... Тогда... Следовательно... Противоречие. (Впрочем, опять-таки, не настаиваю.)

P.S. На всякий случай: я, конечно, лукавлю, но не "наезжаю". В сущности, я искренне интересуюсь. Мне лично было бы очень приятно, если бы возникающие здесь "содержательные" заявления оказались адекватно формализуемыми и даже доказуемыми.

[Инт]

AGu писал(а):

Интересно, но пока "бездоказательно". Опять-таки, было бы интересно взглянуть на попытку доказательства. Что-нибудь в таком роде: Будем говорить, что множество X является конкретным, если... Допустим, существует конкретное X такое, что... Тогда... Следовательно... Противоречие. (Впрочем, опять-таки, не настаиваю.)

Очевидность является достаточным основанием для доказательства. Но кроме того, если такие множества будут предъявлены, то это противоречит ZFC = ZF + аксиома выбора.

[Someone]

Извините, Инт, но Вы нас зовёте в прошлое, причём, по меньшей мере на 100 лет назад.

Я в курсе, что интуиционисты отрицательно относятся к формализации своей области математики, оставляя за собой право произвольно расширять арсенал средств доказательства и считая возможным использовать любые средва, которые кажутся "интуитивно убедительными". Как показывает история, это потенциально опасный путь. Конечно, есть выдающиеся примеры успешности такого подхода (например, Л.Эйлер ухитрился не надоказывать кучи ошибочных утверждений, несмотря на весьма вольное обращение с рядами и бесконечными произведениями, хотя наделать ошибок тут было легче лёгкого), но по мере развития теории опасность наткнуться на противоречие постепенно увеличивается. С чем математики и столкнулись при появлении теории множеств.

Что касается аксиомы выбора, то, как пишет А.С.Трулстра (Справочная книга по математической логике. Часть IV. Теория доказательств и конструктивная математика. Мрсква, "Наука", 1983), в интуиционистской математике аксиома выбора

$$\forall x\exists yA(x,y)\rightarrow\exists a\forall xA(x,a(x))$$

верна, так как доказательство $\forall x\exists yA(x,y)$ должно содержать метод, который по каждому $x$ даёт некоторый $y$, для которого $A(x,y)$, а этот метод и есть функция $a$, заданная законом.

Однако это не имеет ни малейшего отношения к ZF, так как здесь подход совершенно другой. Прежде всего, здесь не предполагается, что имеется какое-то доказательство высказывания $\forall x(x\in A\rightarrow\exists y(y\in x))$ (здесь $A$ - множество множеств, для которого мы хотим получить функцию выбора). Это высказывание является просто ограничением на $A$. А если такое доказательство имеется, то никакого метода нахождения $y$ для каждого $x\in A$ оно содержать не обязано.
Это относится и к теореме об объединении счётного множества счётных множеств. Здесь просто задано, что множества счётны, не предполагая при этом никакого доказательства, а если доказательство имеется, то оно не обязано состоять в построении некоторой конкретной нумерации каждого множества.

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

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

Ситуация здесь является ещё более тонкой, чем Вам кажется. Пусть $A=\{x_i:i\in\mathbb N\}$. Мы знаем, что для каждого $i\in\mathbb N$ существукт взаимно однозначное отображение $\varphi_i\colon\mathbb N\to x_i$. Однако ниоткуда не следует, что совокупность этих $\varphi_i$, $i\in\mathbb N$, является множеством. И даже аксиома выбора не утверждает, что всякая такая совокупность будет множеством. Аксиома выбора утверждает лишь, что найдётся совокупность такого рода, являющаяся множеством.

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

Очевидность является достаточным основанием для доказательства.

Профессор читает лекцию. Написав некое длинное выражение, он говорит: "Совершенно очевидно, что...", - и пишет другое выражение, нисколько не похожее на предыдущее. Он смотрит на написанное, и на лице его появляется некоторое сомнение. Профессор что-то бормочет и покидает аудиторию. Проходит 10 минут, 20, 30... Наконец профессор возвращается и говорит: "Я был прав, это действительно совершенно очевидно!"

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

Но кроме того, если такие множества будут предъявлены, то это противоречит ZFC = ZF + аксиома выбора.

Множества, предъявленные в ZF, не имеют никакого отношения к ZFC.

Вообще, я согласен с AGu: Ваши утверждения носят бездоказательный характер и содержат неопределённые термины вроде "конкретных" множеств.

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

Плохо, что не умеете рассуждать содержательно.

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

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

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

Какие аргументы и где их искать? Уточните.

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

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

Это что, секретные знания? Или просто не умеете писать формулы на форуме? Студенты первого курса и даже школьники легко осваивают: http://dxdy.ru/topic183.html, http://dxdy.ru/topic8355.html.

[Инт]

Someone писал(а):

Вообще, я согласен с AGu: Ваши утверждения носят бездоказательный характер и содержат неопределённые термины вроде "конкретных" множеств.

Похоже, можно дать более чёткий ответ Someone и более полный для AGu. Фактически передо мной ставится задача выразить в формальной теории то, что я утверждаю, исходя из интуиции.

Рассмотрим формулировку условия:

(В) «Для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M, y принадлежит множеству m, причём, каждому n' соответствует единственное m. И для каждой пары <m, y> такой, что m принадлежит множеству M и y принадлежит множеству m, найдётся единственная пара <n', n''> из NxN, причём, каждому m соответствует единственный n'».

(В*) «Н - функция, и для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M, y принадлежит множеству m, и <<n', n''>, <m, y>> принадлежит H, причём, каждому n' соответствует единственное m. И для каждой пары <m, y> такой, что m принадлежит множеству M и y принадлежит множеству m, найдётся единственная пара <n', n''> из NxN такая, что <<n', n''>, <m, y>> принадлежит H, причём, каждому m соответствует единственный n'».

Формулировка следствия такова:

(Г) «существует биекция, отображающая N на объединение всех множеств из M».

Формула, взятая в кавычки вида «…», означает, что она выражается в ZF. N – натуральный ряд. Теорема о том, что «счётное объединение счётных множеств счётно» может быть выражена в форме «(В) влечёт (Г)» или «(В*) влечёт (Г)» .

В формуле (В) или (В*) ни слова не говорится ни о каких функциях, которые надо выбирать от куда-нибудь. Содержательно, в теореме утверждается: “пусть натуральными числами n' перечислены элементы множества M, и при каждом n’, натуральными n’’ перечислены элементы множества m, взятого из M, тогда существует биекция натурального ряда на объединение всех множеств из M”.

Опять же в некоторой содержательной формулировке можно сказать так: “пусть существует (если хотите, конкретное) перечисление (функция) через натуральные числа элементов множества M, для каждого m из M существует (если хотите, конкретное) перечисление через натуральные числа элементов множества m, тогда существует биекция N на объединение множеств, взятых из M”, причём слово “существует” здесь уже не всегда обозначает квантор.

Для доказательства формулы «(В) влечёт (Г)» или «(В*) влечёт (Г)» пользуемся схемой аксиом подстановок.

Что же касается секретных сведений, то примеры "конкретного нарушения аксиомы выбора", о которых я писал, не очень сложные, но для их изложения лучше завести отдельную тему. Так и сделаем. Упоминая их, я хотел лишь сказать о совём мотиве, по которому целесообразно обходить, хотя бы иногда, аксиому выбора.

Кроме того, если хотите, я стою на позиции радикального интуиционизма. Считаю, что всякая формализация инуиционизма, т.е. заведомое очерчивание рамок - ложь. И ссылки на любой "канонический интуиционизм" для меня не имеют никакого значения. Кто решил, что есть интуиционизм? Любая форма - ложь - из-за того, что статична. Дело в том, что когда требуется развивать не академические рассуждения методологического толка, а добывать реальные знания, появляется необходимость становится на разные, в том числе радикальные, позиции, на разные точки зрения, задавать вопрос "что значит" и расшифровывать его. Эти разные позиции позволяют разрешить вопрос по существу, подобно тому, как разные точки зрения телескопов позволяют разрешить удалённые объекты. В частности, профессор с умным видом может никуда не уходить, если его примеры настолько очевидны, что заинтересуют студентов. Пусть даже Эйлер и наделал ошибок, но он же нашёл настолько интересные способы добывания знания, что именно эти способы мы помним больше, а об ошибках забыли.

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

Думать, что теория множеств это законченная теория неправильно. Многие вопросы, которые считаются "решёнными 100 лет назад", думаю, вскроются под влиянием некоторой достаточно эффективной математической практики.

PS. В этом сообщении сделаны исправления с учётом возражений AGu и найденных мною ошибок, добавлена формула (В*).

[AGu]

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

Рассмотрим формулировку условия:
(В) «для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M и y принадлежит множеству m».

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

В формуле (В) ни слова не говорится ни о каких функциях, которые надо выбирать от куда-нибудь.

Подозреваю, что слово "существует" здесь употребляется в каком-то "нетрадиционном" смысле.
Если переписать утверждение (В) с использованием кванторов, то получится
$\bigl(\forall\,\langle n',n''\rangle\in\mathbb N^2\bigr)\bigl(\exists!\,\langle m,y\rangle\bigr)(m\in M\ \&\ y\in m)$.
Странно наблюдать формулу, начинающуюся с $\bigl(\forall\,\langle n',n''\rangle\in\mathbb N^2\bigr)$
и в дальнейшем не включающую ни $n'$, ни $n''$.
У меня на языке вертится некоторая версия осмысления (В),
но она, к сожалению, подразумевает употребление слова "функция".
Текущий итог: увы, не понял.

[Инт]

AGu писал(а):

Текущий итог: увы, не понял.

Да, Вы может быть и правы. Можно так:

(В*) «Н - функция, и для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M, y принадлежит множеству m, и <<n', n''>, <m, y>> принадлежит H, причём, каждому n' соответствует единственное m. И для каждой пары <m, y> такой, что m принадлежит множеству M и y принадлежит множеству m, найдётся единственная пара <n', n''> из NxN такая, что <<n', n''>, <m, y>> принадлежит H, причём, каждому m соответствует единственный n'».

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

Хотя я ещё подумаю, есть ли ошибка, так как в (В) предметы, которые упоминаются под квантором существования, должны зависеть от тех, что под квантором всеобщности, хотя n' и n'' и не употребляются в бесквантороной формуле.

[AGu]

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

(В*) «H функция, и для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M и y принадлежит множеству m, и <<n', n''>, <m, y>> принадлежит H».

По-видимому, (В*) означает существоввание функции $H:\mathbb N^2\to M\times\cup M$ такой, что $H(p)_2\in H(p)_1$ для всех $p\in\mathbb N^2$.
Если я не ошибся, то, боюсь, это опять не то, что подразумевалось.

Скорее всего, я ошибусь, предположив, что Вы хотите формально записать следующее:
существует такая определенная на $\mathbb N^2$ инъективная функция $H$, что $\bigl\{\{H(x,y):y\in\mathbb N\}:x\in\mathbb N\bigr\}=M$.
Отсюда действительно вытекает счетность $\cup M$, так как $\mathbb N^2$ счетно и $\cup M=\{H(x,y): (x,y)\in\mathbb N^2\}$.

Я наверняка ошибся, так как это совсем не то, что я ожидаю увидеть: здесь нет раскрытия понятия "конкретного множества", и все это никак не проясняет сделанные Вами (и заинтересовавшие меня) "содержательные" заявления. Кроме того, мы все, конечно же, прекрасно умеем записывать формализуемые "содержательные" утверждения в виде теоретико-множественных формул. Задача в другом: как формализовать то, что выглядит неформализуемым. А именно такими для меня выглядят (пока) Ваши заявления о "конкретных множествах", "конкретных перечислениях" и т.п.

[Инт]

AGu писал(а):

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

(В*) «H функция, и для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M и y принадлежит множеству m, и <<n', n''>, <m, y>> принадлежит H».

По-видимому, (В*) означает существоввание функции $H:\mathbb N^2\to M\times\cup M$ такой, что $H(p)_2\in H(p)_1$ для всех $p\in\mathbb N^2$.
Если я не ошибся, то, боюсь, это опять не то, что подразумевалось.

Т.е. Вы надеетесь привести меня к формулировке в условии теоремы того, что требуется доказать в теореме. Я уточняю формулировку:

(В*) «Н - множество, и для любой упорядоченной пары натуральных чисел <n', n''> существует единственная упорядоченная пара <m, y> такая, что m принадлежит множеству M, y принадлежит множеству m, и <<n', n''>, <m, y>> принадлежит H, причём, каждому n' соответствует единственное m. И для каждой пары <m, y> такой, что m принадлежит множеству M и y принадлежит множеству m, найдётся единственная пара <n', n''> из NxN такая, что <<n', n''>, <m, y>> принадлежит H, причём, каждому m соответствует единственный n'».

Здесь слова «для любого», «существует» обозначают стандартные кванторы. Об отображении в множество M x U, где U - объединение множеств из M здесь не говорится, т.е. не говорится о множестве, для кажого элемента q которого, найдётся множество m из M такое, что q принадлежит m. Выражение «<<n', n''>, <m, y>> принадлежит H» означает в точности то, что H(<n', n''>) = <m, y>. Можете считать, что символ H и выражает смысл словосочетания "конкретное перечисление". Конечно с точки зрения ZF множество H - функция.

[Someone]

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

Формула, взятая в кавычки вида «…», означает, что она выражается в ZF. N – натуральный ряд. Теорема о том, что «счётное объединение счётных множеств счётно» может быть выражена в форме «(В) влечёт (Г)» или «(В*) влечёт (Г)» .

Не может. Я объяснял.

Вы всё время стремитесь заменить одну теорему другой. Это не выйдет. Вообще, неприлично ходить в чужой монастырь со своим уставом. Доказывая что-либо в теории ZF или ZFC, Вы должны придерживаться правил, принятых в этих теориях. Интуиционизм здесь совершенно ни при чём, и интуиционистские рассуждения не имеют силы в формализованных теориях классической математики.

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

Кроме того, если хотите, я стою на позиции радикального интуиционизма. Считаю, что всякая формализация инуиционизма, т.е. заведомое очерчивание рамок - ложь.

Ну, это как раз то, о чём я писал. Ваш "радикальный интуиционизм" сводится к "что хочу, то и ворочу". В теме о теореме Гёделя Вы уже наворочали.

[Инт]

Someone писал(а):

...Не может. Я объяснял...

Во первых, Вы ничего не объяснили, кроме того, что настаиваете на своей версии подмены теоремы. Особенно по формулам (В) и (В*). Во вторых, если Вы хотите вернуться к теме Гёделя, то давайте вернёмся к ней как-нибудь, причём, радикально. Я, для себя, уже уточнил аргументы по т.н. "теореме Гёделя", по итогам прошедшей дискуссии. То, что наворочил Гёдель, и что наворотите Вы, так же интересно.

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