Аксиома выбора и конструктивизм

[Someone]

Ende
Выделено из темы «Несуществующие существующие»

mihaild в сообщении #1695618 писал(а):

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

Я тоже не понимаю.
Аксиому выбора можно сформулировать так: для любого семейства $\mathscr F$ непустых множеств множество функций выбора на семействе $\mathscr F$ непусто.
При этом функцией выбора на семействе $\mathscr F$ называется такая функция $\varphi\colon\mathscr F\to\bigcup\mathscr F$, что $\varphi A\in A$ для любого $A\in\mathscr F$.
Таким образом, используя аксиому выбора, мы фактически рассуждаем так: семейство $\mathscr F$ содержит только непустые множества, поэтому существует некоторая функция выбора $\varphi$. И дальше что-то с этой функцией выбора делаем.

Часто используется такое рассуждение: множество $A$ непустое, поэтому существует некоторый элемент $x\in A$. И дальше что-то с этим элементом делаем. Никому не приходилось так рассуждать?

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

[Anton_Peplov]

mihaild в сообщении #1695618 писал(а):

Но в целом я не очень хорошо понимаю, чем аксиома выбора так уж провинилась

Вероятно, своими контринтуитивными следствиями вроде парадокса Банаха-Тарского.

[epros]

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

Степень неконструктивности в обоих случаях одинаковая.

Я могу рассказать, в чём формальная разница "степеней неконструктивности". Есть интерпретация Брауэра-Гейтинга-Колмогорова (BHK), согласно которой объект заданного класса существует тогда и только тогда, когда есть пример такого объекта. Если речь об абстрактных математических объектах, то на первый взгляд кажется, что не во что ткнуть пальцем, чтобы сказать: "Вот пример такого объекта". Тем не менее, в формальных системах есть возможность "ткнуть пальцем" в абстрактный объект. Для этого нужно построить формулу $\psi$ с одной свободной переменной $x$, для которой будет доказуема единственность объекта, удовлетворяющего $\psi(x)$. Эту формулу можно считать "именем собственным" данного объекта. Например, в теории множеств с аксиомой бесконечности легко доказуема единственность минимального индуктивного множества. Таким образом, нетрудно по всем канонам интерпретации BHK "предъявить" бесконечное множество. А вот "предъявить" функцию выбора в общем случае не получается.

[warlock66613]

Anton_Peplov в сообщении #1695713 писал(а):

Вероятно, своими контринтуитивными следствиями вроде парадокса Банаха-Тарского.

А вы знакомы с этим парадоксом вблизи? То есть я имею в виду доказательством. Это -- в основе -- очень простая конструкция, как раз очень интуитивно понятная, прямо-таки осязаемая. Её можно как раз приводить в качестве примера, что аксиома выбора не всегда приводит к интуитивно неконструктивным объектам.

[Anton_Peplov]

warlock66613 в сообщении #1695730 писал(а):

Это -- в основе -- очень простая конструкция, как раз очень интуитивно понятная, прямо-таки осязаемая.

Тем острее парадокс. Берем простую понятную аксиому, совершаем простые понятные действия и получаем два шара радиуса $R$ из одного.

[пианист]

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

[Someone]

epros в сообщении #1695724 писал(а):

Я могу рассказать, в чём формальная разница "степеней неконструктивности".

Боюсь, Вы не совсем меня поняли. Вы мне говорите, что в некоторых случаях мы можем каким-то способом выделить конкретный элемент, если это нам зачем-то нужно. Пусть даже и не конструктивно. Я не об этом. Да и почему Вы думаете, что этот способ не может работать в случае аксиомы выбора? Аксиома выбора сообщает нам, что функции выбора существуют, и мы конструируем формулу, которой удовлетворяет единственная функция выбора. И, кстати, это не отменит обвинений в неконструктивности.
В одном случае у нас есть множество функций выбора, про которое аксиома выбора говорит, что оно не пусто. Пользуясь этим мы говорим "пусть $\varphi$ — некоторая функция выбора".
В другом случае у нас есть некоторое множество $A$, про которое мы знаем, что оно непустое, но не знаем ни одного конкретного его элемента, или нам всё равно, что это за элемент, и мы говорим "пусть $x\in A$ — какой-нибудь элемент".
По-моему, никакой разницы нет.

[mihaild]

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

Аксиома выбора сообщает нам, что функции выбора существуют, и мы конструируем формулу, которой удовлетворяет единственная функция выбора.

А разве можно написать формулу $\varphi(x)$, такую что $\text{ZFC} \vdash \exists! x: \varphi(x) \wedge x\ \text{- функция выбора на}\ \mathcal{P}(\mathbb R)$?

[Someone]

mihaild в сообщении #1695796 писал(а):

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

Аксиома выбора сообщает нам, что функции выбора существуют, и мы конструируем формулу, которой удовлетворяет единственная функция выбора.

А разве можно написать формулу $\varphi(x)$, такую что $\text{ZFC} \vdash \exists! x: \varphi(x) \wedge x\ \text{- функция выбора на}\ \mathcal{P}(\mathbb R)$?

Понятия не имею. А кто говорил, что её всегда можно написать? Я точно не говорил, да и epros тоже. Он говорил, что возможна ситуация, когда конструктивно указать элемент множества нельзя, но можно написать формулу, которой удовлетворяет единственный элемент этого множества.

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

[epros]

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

Да и почему Вы думаете, что этот способ не может работать в случае аксиомы выбора?

Проблема в том, что в некоторых случаях как раз ни одной конкретной функции выбора указать не получается, именно это и означает, что утверждение о её существовании неконструктивно. Например, невозможно определить конкретную нелинейную аддитивную функцию $\mathbb R \to \mathbb R$ и невозможно указать конкретную формулу преобразования для парадокса Банаха-Тарского.

-- Ср июл 30, 2025 11:19:40 --

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

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

Хм, вот это я пропустил. А что тогда значит "конструктивно указать элемент множества"? По-моему, это и значит - написать формулу, которой удовлетворяет единственный элемент. Например, $x=0$.

[Someone]

epros в сообщении #1695821 писал(а):

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

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

epros в сообщении #1695821 писал(а):

А что тогда значит "конструктивно указать элемент множества"?

Конструктивность — понятие тёмное. Оно и у конструктивистов в многих разных смыслах употребляется. У меня нет желания развивать эту тему.

epros в сообщении #1695821 писал(а):

Хм, вот это я пропустил.

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

[epros]

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

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

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

[Someone]

epros в сообщении #1695891 писал(а):

Это зависит от того, каково конкретно это абстрактное множество.

Естественно, зависит. Дык, и в случае множества функций выбора тоже зависит.