Об аксиоме выбора и конструктивных решениях.

[Сергей Маркелов]

Можно ли покрасить плоскость в 2 цвета так, чтобы любая окружность радиуса 1 содержала ровно 2009 чёрных точек?

Вопрос непростой. Если число 2009 заменить на любое чётное, ответ положителен, и существует явный пример (параллельные линии). При n=2009 придумать явный пример как-то ни у кого не получается. Между тем, с помощью аксиомы выбора несложно доказать, что так покрасить плоскость можно.

Вопрос: может ли так быть, что в этой или аналогичной задаче с помощью аксиомы выбора доказать можно, а явный пример построить нельзя?

Задач такого рода много. Например, можно ли всё пространство R^3 разбить на окружности? Ответ да, есть и решение через аксиому выбора, и явный пример. А вот можно ли разбить R^3 на окружности радиуса 1 ? Верящим в аксиому выбора нет проблем, можно -- а вот явного примера как-то не приводится.

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

Этого понять не могу, это взрывает мозг. Спрашивается, а как же на самом деле обстоят дела? Меня, собственно, больше интересуют не конкретно эти задачи, а принципиальная возможность. Если такая ситуация наблюдается, то как же понять -- на самом-то деле можно разбить пространство на окружности радиуса 1, или нельзя? Например так, чтобы про любую пару точек можно было сказать, находятся ли они на одной окружности, или на разных?

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

Спасибо!
Сергей Маркелов

Также обсуждается здесь: http://community.livejournal.com/ru_math/724912.html

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

Сергей Маркелов в сообщении #234332 писал(а):

Спрашивается, а как же на самом деле обстоят дела?

Ну а что значит "на самом деле"?

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

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

-- Вт авг 11, 2009 19:01:58 --

P. S. Тему, наверное, стоит перенести в "дискуссионный" раздел.

[Lyoha]

Я себе это представляю так.

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

Фишка в том, что аксиома выбора идёт в дело для множеств мощности большей счётной. И первый же шаг решения - полное упорядочивание нашего множества - делает его сугубо неконструктивным. Т.е. действительные числа и точки пространства декларируются вполне упорядочиваемыми, но конструктивной процедуры нет. А она равнозначна предъявлению конструктивного решения таких задач.

[AGu]

Сергей Маркелов в сообщении #234332 писал(а):

Вопрос: может ли так быть, что в этой или аналогичной задаче с помощью аксиомы выбора доказать можно, а явный пример построить нельзя?

Я лишь добавлю к толковому ответу Профессора Снэйпа свое банальное «ага, так бывает». Именно такая бяка приключилась с неизмеримыми подмножествами $\mathbb R$. В ZFC можно доказать, что такие множества существуют, но в той же ZFC (ну, почти) можно также доказать, что привести пример такого множества нельзя. Разумеется, под «примером» здесь понимается нечто вполне формальное. В частности, для всякой теоретико-множественной формулы $\varphi(x)$ (с одной свободной переменной) можно доказать, что $\{x\in\mathbb R : \varphi(x)\}$ — измеримое множество.