Существуют ли неразрешимые множества натуральных чисел?

[arseniiv]

Skipper в сообщении #1321759 писал(а):

Или как то оно может "и существовать и не существовать" одновременно?

Никак. Есть неполные теории, которые просто ничего вам не скажут о существовании некоторых объектов. Подходя к тому же с другого конца, есть теории, у которых есть по нескольку неизоморфных интерпретаций. Это значит, что теория не описывает какую-то одну «математическую реальность» (в которой интересующий вас объект существует либо не существует), она описывает несколько неразличимых с помощью выбранного языка, но разных. И ZF (если непротиворечива) описывает кучу таких, из которых в одних верна C и неверна AD, в других верна AD и неверна C, и ещё будут и те, где неверны и C, и AD.

Можно, конечно, попробовать найти среди всего этого разнообразия что-то «естественное». Но на это предложение разные математики дадут разные ответы, у кого какой вкус (конечно, обычно вариантов предпочтений не очень много, но достаточно). Например, для классической математики C часто полезна, как уже замечалось.

[Someone]

Skipper в сообщении #1321759 писал(а):

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

Конкретно это из аксиомы выбора не следует. Это утверждение называется континуум-гипотезой (CH). Есть модели, в которых континуум гипотеза истинна, и есть модели, в которых она ложна.

Но если какая-то формула выводится из аксиомы выбора (вместе с другими аксиомами теории, конечно), то во всякой модели, в которой AC истинна, любое из её следствий тоже будет истинно.

Skipper в сообщении #1321759 писал(а):

Ну так всё таки - такое множество либо существует либо нет. Третьего же не дано.

Почему "либо/либо"? В одной модели одно, в другой модели другое. Вовсе не вместе.

Skipper в сообщении #1321759 писал(а):

Или как то оно может "и существовать и не существовать" одновременно?

Ну почему "одновременно"? В разных моделях.

Skipper в сообщении #1321759 писал(а):

Ну я вот и не могу понять. Кто то придумал интерпретацию, в которой аксиома истинна, а кто то - интерпретацию в которой она ложна?
А ест ьли примеры, чтобы сравнить эти "интерпретации" ?

Коэн П.Дж. Теория множеств и континуум-гипотеза. М.: Мир, 1969. Мостовский А. Конструктивные множества и их приложения. М.: Мир, 1973.

[mihaild]

Давайте вместо теории множеств возьмем что-нибудь попроще - например, теорию групп. Всего три символа в сигнатуре - константный $e$, функциональный $\cdot$ и предикатный $=$. И всего три аксиомы: $\forall x: x \cdot e = e \cdot x = x$, $\forall x,y,z : x\cdot(y\cdot z) = (x \cdot y) \cdot z$, $\forall x\exists y: xy = yx = e$.
Назовем "аксиомой существования элемента порядка 2" (сокращенно АСЭП2) утверждение $\exists x: x \neq e \wedge x\cdot x = e$.
АСЭП2 истинна или ложна?
Ответ: этот вопрос бессмысленен. Ни АСЭП2, ни ее отрицание не выводятся из остальных аксиом теории групп. И существуют как удовлетворяющие ей группы, так и не удовлетворяющие.

С теорией множеств ровно та же ситуация. Отличие только в том, что существование разных групп интуитивно понятно, а существование разных моделей ZF - нет.

[Skipper]

Цитата:

АСЭП2 истинна или ложна?

А здесь действительно, не хватает интерпретации модели, чтобы утверждать об истинности или ложности.

Цитата:

Есть модели, в которых континуум гипотеза истинна, и есть модели, в которых она ложна.

Цитата:

Ну почему "одновременно"? В разных моделях.

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

[Someone]

Skipper в сообщении #1322234 писал(а):

Допустим, мы примем модель, в которой она ложна. А потом кто-нибудь возьмет, да и построит такое множество?

Континуум-гипотеза утверждает, что множеств промежуточной мощности между $\aleph_0$ и $2^{\aleph_0}$ нет. Поэтому её ложность означает, что такое множество есть.
Насчёт "построит" ждёт облом: построить множество промежуточной мощности, используя только аксиомы ZFC, невозможно, даже если континуум-гипотеза ложна. Если нам такое множество зачем-то понадобилось, мы просто говорим "пусть $A$ — такое множество, что $\aleph_0<\lvert A\rvert<2^{\aleph_0}$", и далее им пользуемся.

Skipper в сообщении #1322234 писал(а):

кажется, должна быть некая абсолютная истина

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

[Skipper]

Цитата:

Насчёт "построит" ждёт облом: построить множество промежуточной мощности, используя только аксиомы ZFC, невозможно,

Это доказано? Ну значит, если построить такое множество невозможно , значит континуум-гипотеза - истинна?
Как можно говорить о существовании чего-то, что принципиально нельзя построить?

[Someone]

Skipper в сообщении #1322268 писал(а):

если построить такое множество невозможно , значит континуум-гипотеза - истинна?

Нет. Я сказал — построить невозможно. То есть, явно описать, как его получить, используя, скажем, множество натуральных чисел, множество действительных чисел и другие известные множества, и пользуясь при этом только аксиомами ZFC. Именно потому, что существуют модели ZFC, в которых множества промежуточной мощности нет. Это не означает, что его нельзя получить, используя средства, выходящие за рамки ZFC.

Skipper в сообщении #1322268 писал(а):

Как можно говорить о существовании чего-то, что принципиально нельзя построить?

Вероятно, надо отказаться от идеи, что мы можем построить всё, что захотим. Это касается не только необозримых "миров" ZFC. Достаточно обратиться к хорошо знакомым действительным числам: подавляющее большинство из них мы точно так же не можем построить, однако в их существовании не сомневаемся. Потому что рассуждения, используемые при построении поля действительных чисел, однозначно приводят к их существованию.

Впрочем, в математике есть довольно большая область, именуемая конструктивной математикой. Она как раз считает существующим только то, что можно явно построить. Правда, термин "построить" в разных направлениях конструктивизма толкуется по-разному. И, кроме того, появляются "странные" обороты типа "не может не существовать", что у конструктивистов означает вовсе не то же самое, что "существует". Можете для примера поразбираться в книге Кушнер Б.А. Лекции по конструктивному математическому анализу. М.: Наука, 1973.

[Skipper]

Цитата:

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

С какими числами мы имеем дело? Рациональные, иррациональные, трансцендентные и т.д. Корень из 2, число пи, и т.д. Но для всех этих чисел есть ОПРЕДЕЛЕНИЕ конечной длины (по описанию), благодаря которому мы МОЖЕМ найти любую цифру после запятой, у этого числа.

Вопрос - СУЩЕСТВУЮТ ли вещественные числа, которые мы НЕ МОЖЕМ описать никаким ОПРЕДЕЛЕНИЕМ конечной длины? Если они и существуют, то мы с ними никогда не можем столкнуться ни в каком анализе, а значит, остаётся только принять как аксиому. 1) "они существуют", либо 2) "они не существуют".

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

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

Цитата:

Я сказал — построить невозможно.

Если его построить невозможно, иначе как

Цитата:

просто говорим "пусть $A$ — такое множество, что $\aleph_0<\lvert A\rvert<2^{\aleph_0}$", и далее им пользуемся.

то меня такое построение не устраивает, я могу сказать, что такого множества и вовсе не существует.

[eugensk]

Skipper в сообщении #1323282 писал(а):

Вопрос - СУЩЕСТВУЮТ ли вещественные числа, которые мы НЕ МОЖЕМ описать никаким ОПРЕДЕЛЕНИЕМ конечной длины? Если они и существуют, то мы с ними никогда не можем столкнуться ни в каком анализе, а значит, остаётся только принять как аксиому. 1) "они существуют", либо 2) "они не существуют".

По этой логике, если у вас такой произвол выбора, и вы принимаете "не существует", то

Раз вы можете "столкнуться" только со счетным множеством чисел (по числу конечных определений), то существет только счетное множество чисел. Контиинуума нет.
или, вульгарнее, Раз у вас никогда не будет триллиона денег, то триллиона и больше чисел не бывает. Бесконечности нет.

Наверное, у вас всё же нет такого произвола (в обычной, теоретико-множественной математике).

Skipper в сообщении #1323282 писал(а):

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

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

[Someone]

Skipper в сообщении #1323282 писал(а):

Вопрос - СУЩЕСТВУЮТ ли вещественные числа, которые мы НЕ МОЖЕМ описать никаким ОПРЕДЕЛЕНИЕМ конечной длины? Если они и существуют, то мы с ними никогда не можем столкнуться ни в каком анализе, а значит, остаётся только принять как аксиому. 1) "они существуют", либо 2) "они не существуют".

К сожалению, мы не можем по собственному произволу выбрать "существует" или "не существует" некоторый математический объект. Существование "невычислимых" чисел доказуемо, поэтому мы обязаны считать их существующими. Есть даже примеры.
По поводу множества промежуточной (между $\aleph_0$ и $2^{\aleph_0}$) мощности: доказуемо, что его можно считать существующим, и доказуемо, что его можно считать не существующим. "Можно" в том смысле, что оба варианта непротиворечивы.

Skipper в сообщении #1323282 писал(а):

меня такое построение не устраивает, я могу сказать, что такого множества и вовсе не существует

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

Skipper в сообщении #1323282 писал(а):

Но для всех этих чисел есть ОПРЕДЕЛЕНИЕ конечной длины (по описанию), благодаря которому мы МОЖЕМ найти любую цифру после запятой, у этого числа.

К сожалению, наличие определения некоторого числа не означает, что это число вычислимо.

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

[Sycamore]

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

К сожалению, нестрогое многословие Феликса и нехватка (в отличие от критиков) основательного знания предмета как-то напрашиваются.

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

Итак, показалось, что Феликс настаивал на "объективной истинности" тех арифметических предложений/гипотез (наподобие простых-близнецов или Гольдбаха, скажем), к которым как-бы применим закон исключённого третьего: мы уверены, что лишь одно из возможных двух решений может быть - и в конце концов окажется - истинным, хотя пока не знаем какое именно из двух УЖЕ верно, так сказать.

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

Полагаю, что стандартную модель арифметики Пеано РА легко отличить от остальных нестандартных (поскольку РА 1-порядковая) моделей.

Совпадает ли РА с теорией/моделью арифметики в теории множеств ZFC?

Можно ли ожидать неразрешимых в ZFC арифметических предложений? Вопреку тому, что такие (неразрешимые в РА) предложения как Париса-Харрингтона, Гудстейна, Канамори–Макалуна, дерева Краскала и пр. уже разрешили в ZFC.

У самой 1-порядковой ZFC тоже должно быть разных/нестандартных моделей, кто они (счётные модели, нестандартный анализ?)?

Можно ли в ZFC строить по желанию, at will (как в РА), аналоги Гёделевых недоказуемых в РА предложений G/~G?

[Jnrty]

Sycamore в сообщении #1447292 писал(а):

Феликс

Jnrty:

Предупреждение за искажение псевдонима участника форума. Пока без занесения в личное дело. Псевдоним должен быть написан точно так, как это предусмотрено его владельцем и правилами форума, включая выделение шрифтом и, желательно, цветом: Феликс Шмидель.

[arseniiv]

Грубо говоря ZFC даже хуже, чем PA, но это я сейчас не аргументирую. Оставлю часть вопросов другим желающим, кто скорее всего расскажет лучше.

Sycamore в сообщении #1447292 писал(а):

Полагаю, что стандартную модель арифметики Пеано РА легко отличить от остальных нестандартных (поскольку РА 1-порядковая) моделей.

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

Sycamore в сообщении #1447292 писал(а):

Совпадает ли РА с теорией/моделью арифметики в теории множеств ZFC?

Теория, PA, с моделью точно совпадать не может, и что значит «теория в теории»?

Стандартная модель PA это как раз $\mathbb N$ (иначе известное как $\omega$, ну и с понятно определёнными операциями и отношениями), определяемое в ZFC как пересечение всех индуктивных множеств, существование которых постулирует аксиома бесконечности.

Sycamore в сообщении #1447292 писал(а):

Можно ли в ZFC строить по желанию, at will (как в РА), аналоги Гёделевых недоказуемых в РА предложений G/~G?

Разумеется. Кодировать формулы в ZFC может быть даже проще, чем в PA. У нас есть довольно удобно выразимые упорядоченные пары, тройки и т. д. (нужно лишь конечное количество арностей), про которые не очень сложно доказывать, и любое конечное число множеств, не являющихся такими парами, тройками и т. п. для представления алфавита. Можно собирать из тех и других деревья, представляющие формулы. Это даже удобнее, чем со строками, хотя можно и строками обойтись, получая их как односвязные списки из пар и законченные символом, отличным от остальных.

[Sycamore]

arseniiv в сообщении #1447319 писал(а):

Вопрос, с помощью какого языка это легко (или как вы собрались отличать?)

может тем, что за $\mathbb N$/$\omega$ не будет других "нестандартных" натуральных, как подсказали некоторые статьи 50-60ых годов?

Sycamore в сообщении #1447292 писал(а):

Можно ли в ZFC строить по желанию, at will (как в РА), аналоги Гёделевых недоказуемых в РА предложений G/~G?

arseniiv в сообщении #1447319 писал(а):

Разумеется. Кодировать формулы в ZFC может быть даже проще

в смысле G/~G будут недоказуемыми в ZF(C) и необязательно будут предложениями о натуральных числах?

[arseniiv]

Sycamore в сообщении #1447588 писал(а):

может тем, что за $\mathbb N$/$\omega$ не будет других "нестандартных" натуральных, как подсказали некоторые статьи 50-60ых годов?

Честно не понял. Что значит «за» и как предполагается распрощаться с доказательством того, что нестандартные модели PA есть?

Sycamore в сообщении #1447588 писал(а):

в смысле G/~G будут недоказуемыми в ZF(C) и необязательно будут предложениями о натуральных числах?

В моём предложении как я его представлял — нет, о множествах, но по идее не должно быть проблем сделать для натуральных.