Счётное подмножество вещественных чисел

[mihaild]

Pustovoi в сообщении #1560970 писал(а):

В качестве возражения выступают два тезиса:
1. Нет четкого определения "описания".

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

Например, является ли текст "наименьшее число, кодирующее доказательство теоремы Ферма в ZFC [тут описание способа кодирования, я могу его выписать, но можете поверить, что тут никакого подвоха нет]" описанием числа? А текст "наименьшее число, кодирующее доказательство гипотезы Римана"? Текст "наименший контрпример к проблеме Гольдбаха"?

Pustovoi в сообщении #1560970 писал(а):

Есть только числа, имеющие конечное или бесконечное определение

Что такое "бесконечное определение"?

Pustovoi в сообщении #1560970 писал(а):

И в самом его начале пропишем следующее: все математические объекты используемые в дальнейшем, должны иметь конечное определение (описание).

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

[EminentVictorians]

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

Например, является ли текст "наименьшее число, кодирующее доказательство теоремы Ферма в ZFC [тут описание способа кодирования, я могу его выписать, но можете поверить, что тут никакого подвоха нет]" описанием числа?

Я бы сказал, что является. Каждому доказательству ставится в соответствие натуральное число, его кодирующее. Образ этого отображения - некоторое непустое подмножество натуральных чисел. Любое непустое подмножество натуральных чисел ограничено снизу, следовательно искомое наименьшее число существует и единственно. (Все это справедливо, если теорема Ферма вообще может быть доказана в ZFC, что не очевидно).

Заменить теорему Ферма на какую-то открытую проблемы типа гипотезы Римана нельзя (потому что тогда мы не можем гарантировать непустоту образа того отображения из доказательств в натуральные числа). Так ведь нередко бывает, когда прежде чем вводить какое-то определение, надо доказать его корректность. Пока корректность не доказана, вводить определение нельзя. Здесь на мой взгляд все то же самое.

[mihaild]

EminentVictorians в сообщении #1561003 писал(а):

Все это справедливо, если теорема Ферма вообще может быть доказана в ZFC, что не очевидно

Вот именно в этом и проблема. Получается, что для проверки, задает ли текст число, нужно уметь проверять, доказуемо ли какое-то утверждение в ZFC.

[EminentVictorians]

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

Вот именно в этом и проблема. Получается, что для проверки, задает ли текст число, нужно уметь проверять, доказуемо ли какое-то утверждение в ZFC.

Бремя доказывать корректность определения лежит на том, кто это определение вводит. Если кто-то ввел определение так, как в примере с теоремой Ферма выше, то он, разумеется, должен доказать существование хотя бы одного формального доказательства теоремы Ферма в ZFC. Тут тонкий момент: достаточно доказать наличие, а явно это доказательство можно и не предъявлять.

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

[Droog_Andrey]

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

[mihaild]

EminentVictorians в сообщении #1561010 писал(а):

Я не понимаю, чем этот случай выделяется из общей математической практики.

Сам по себе ничем (кроме того, что демонстрирует, кто описуемые объекты "потрогать" не сильно проще, чем стандартные).
Главная проблема чуть дальше - если мы хотим ограничиться описуемыми объектами, то и биекции для определения, является ли множество счетным, логично рассматривать только описуемые, так? И вот оказывается, что описуемой биекции между описуемыми вещественными числами и натуральными, нет.

Droog_Andrey в сообщении #1561042 писал(а):

Отсюда и нефизичность несчётных множеств

А $BB(10^5)$ чем-то "физичнее" $\mathbb R$?

[EminentVictorians]

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

Главная проблема чуть дальше - если мы хотим ограничиться описуемыми объектами, то и биекции для определения, является ли множество счетным, логично рассматривать только описуемые, так?

Не знаю, я тот длинный пост про описуемые/неописуемые не осилил Я примерно понял, что Pustovoi не любит неконструктивные объекты, но у меня то такой проблемы нету. Я и аксиому выбора люблю, и к косвенным доказательствам существования (без непосредственного предъявления) отношусь спокойно. А так да, я понимаю, что если хотеть конструктивности, то надо быть последовательным и хотеть ее для всего, в том числе и для определения счетности. То, что при этом найдутся всякие "по обычному" счетные множества, но про которые мы не можем (или нам сильно затруднительно) доказать их "конструктивную счетность", я не сомневаюсь.

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

[mihaild]

EminentVictorians в сообщении #1561061 писал(а):

То, что при этом найдутся всякие "по обычному" счетные множества, но про которые мы не можем (или нам сильно затруднительно) доказать их "конструктивную счетность", я не сомневаюсь

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

EminentVictorians в сообщении #1561061 писал(а):

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

Это очень философский вопрос. К тому же например если брать не анализ, а теорию меры, то там тут же возникает принципиально не имеющий аналогов в классическом случае результат - существует максимальное (по включению) множество эффективно нулевой меры.

[EminentVictorians]

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

А еще у счетных множеств бывают несчетные подмножества.

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

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

К тому же например если брать не анализ, а теорию меры, то там тут же возникает принципиально не имеющий аналогов в классическом случае результат - существует максимальное (по включению) множество эффективно нулевой меры.

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

[mihaild]

EminentVictorians в сообщении #1561063 писал(а):

Я сначала хотел спросить "Как такое может быть?", но потом подумал, что в ZF без аксиомы выбора какой только фигни нету, так что даже это меня бы не удивило

В ZF такого не бывает: хотя и могут существовать бесконечные (не равномощные никакому натуральному числу) конечные по Дедекинду (не содержащие счетного подмножества, или, что то же самое, не равномощные собственному подмножеству) множества, но у счетного множества любое подмножество либо конечно, либо счетно.
Тут дело в понятии конструктивной счетности. Множество всех программ конструктивно счетно. А вот множество всех программ, не останавливающихся на пустом входе, конструктивно счетным не является (нет вычислимой биекции между ним и натуральными числами).

EminentVictorians в сообщении #1561063 писал(а):

А это дает какой-то профит для теории?

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

[EminentVictorians]

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

В ZF такого не бывает

Я просто на автомате прочитал и подумал, что речь идет про более-менее обычную счетность, а не конструктивную. Если иметь в виду конструктивную, то данный факт тем более не удивляет: конструктивная счетность, по крайней мере в моем интуитивном понимании, очень далека по смыслу от обычной счетности.

Вообще, я не очень понимаю это стремление конструктивистов непременно заменить "классические" построения на конструктивные. Я бы рассматривал конструктивный случай как дополнение к обычной теории. Например, я не делал бы вид, что все числа - это КДЧ, а просто воспринимал бы КДЧ как обычное подмножество $\mathbb R$. Но у меня есть смутное подозрение, что у них проблемы не с конструктивизмом, а прямо непосредственно с логикой. А я даже на классическую логику смотрю со скепсисом (как и на весь формальный метод в целом), так что куда уж мне там до еще более экстремальной позиции.

[Droog_Andrey]

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

Droog_Andrey в сообщении #1561042 писал(а):

Отсюда и нефизичность несчётных множеств

А $BB(10^5)$ чем-то "физичнее" $\mathbb R$?

Ну здесь хотя бы за уши притянуть можно.

(Оффтоп)

Мне, правда, больше нравится $SSCG(13)$, стартующая с графа Хивуда :)

[Someone]

В качестве примера конструктивизма можно рассмотреть советскую школу конструктивизма — конструктивный рекурсивный анализ (надо сказать, что рекурсивный анализ, то есть, теория алгоритмически вычислимых функций, существует и в неконструктивном варианте). Конструктивное действительное число (КДЧ) — это либо рациональное число, либо пара алгоритмов, из которых первый определяет фундаментальную последовательность рациональных чисел $r_k$, $k\in\mathbb N$, а второй по заданному натуральному $n$ определяет такой номер $k_n$, что для всех $m_1,m_2\in\mathbb N$, удовлетворяющих условиям $m_1>k_n$ и $m_2>k_n$, выполняется неравенство $\lvert r_{k_1}-r_{k_2}\rvert<2^{-n}$. Далее речь идёт только о таких вычислимых числах. Что там у интуиционистов, я не в курсе, но они не считают, что вычислимость сводится к алгоритмической вычислимости.

Подробности можно посмотреть в книге
Б. А. Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973.

EminentVictorians в сообщении #1561061 писал(а):

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

Хуже: множество конструктивных действительных чисел эффективно несчётно: существует алгоритм, который каждую конструктивную последовательность КДЧ перерабатывает в КДЧ, не принадлежащее этой последовательности. Доказательство этого повторяет одно из доказательств Кантора теоремы о несчётности $\mathbb R$ (диагональный метод не используется), естественно, с конструктивистскими заморочками. В книге Кушнера это доказывается в § 4 главы 3.

EminentVictorians в сообщении #1561061 писал(а):

Я и аксиому выбора люблю

Я тоже не понимаю, чего к ней прицепились. По-моему, большинство математиков, не вникающих в теорию множеств, этой аксиомой пользуются, даже не подозревая об этом. А без неё происходят ещё более крутые "чудеса", чем с ней. Например, без аксиомы выбора может оказаться, что в отображении $f\colon X\xrightarrow{\text{на}}Y$ не выполняется неравенство $\lvert X\rvert\geqslant\lvert Y\rvert$. И в конструктивной математике аксиома выбора также может выполняться: если у нас конструктивно определено семейство конструктивных множеств, непустых в конструктивном смысле (это означает, что в каждом множестве из этого семейства можно конструктивно указать некоторый элемент), то почему бы не существовать конструктивно определённой функции выбора? Об этом можно прочесть, например, в главе 5 книги
Справочная книга по математической логике. Часть IV. Теория доказательств и конструктивная математика. Москва, "Наука", 1983.

EminentVictorians в сообщении #1561066 писал(а):

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

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

[kotenok gav]

Pustovoi в сообщении #1560970 писал(а):

Думаю, ни у кого не вызывает сомнения, что приведенные тексты однозначно определяют числа

Доказательство, что каждое из этих описаний однозначно определяет число, нетривиально.