Вопрос по квантовой механике

[Munin]

Профессор Снэйп в сообщении #538112 писал(а):

Второе.

Тогда такой вопрос. Изначально вы сформулировали похоже на то, что имея две произвольные невычислимые функции, и оракул для одной из них, можно построить машину Тьюринга из одной во вторую. Как более точно?

Профессор Снэйп в сообщении #538112 писал(а):

Она состоит из конечного числа букв. А оракул для невычислимой функции знает ответы о её значениях на бесконечном числе аргументов.

А если её дополнить нулями, то она станет до банальности вычислимой... Приятно, что вы внимательны.

Профессор Снэйп в сообщении #538112 писал(а):

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

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

Профессор Снэйп в сообщении #538112 писал(а):

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

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

Профессор Снэйп в сообщении #538112 писал(а):

3) Любую естественнонаучную теорию станет возможным мгновенно проверить на внутреннюю логическую непротиворечивость. Которая, хоть и не даст гарантии истинности, всё же сразу станет отбрасывать множество заведомо ненужного хлама.

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

Профессор Снэйп в сообщении #538112 писал(а):

Представьте себе мир, в котором все компьютеры производят любые вычисления практически мгновенно.

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

[master]

Профессор Снэйп в сообщении #537849 писал(а):

Обязаны ли электроны в обоих Вселенных попадать в одну и ту же точку экрана

Да

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

Munin в сообщении #538182 писал(а):

Тогда такой вопрос. Изначально вы сформулировали похоже на то, что имея две произвольные невычислимые функции, и оракул для одной из них, можно построить машину Тьюринга из одной во вторую. Как более точно?

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

Вообще, описанная сводимость - это так называемая сводимость по Тьюрингу или $T$-сводимость. Будем рассматривать только всюду определённые функции из $\mathbb{N}$ в $\mathbb{N}$. Скажем, что $f_1$ $T$-сводится к $f_2$ (и будем писать $f_1 \leqslant_T f_2$), если машина Тьюринга с приделанным к ней оракулом для $f_2$ способна вычислять $f_1$.

Эта сводимость упорядочивает множество рассматриваемых нами функций довольно сложным образом; если быть совсем точными, то введённая сводимость - предпорядок, задающий, как и всякий предпорядок, набор классов эквивалентности и частичный полрядок на этих классах. Классы эквивалентности называются $T$-степенями. Порядок на них оказывается верхней полурешёткой, обычно именуемой полурешёткой Тьюринга. Полурешётка же эта - один из самых сложных и в то же время едва ли не самый популярный объект изучения такой дисциплины, как теория вычислимости.

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

На этом все банальности, пожалуй что, заканчиваются. Никакого приемлемого описания эта полурешётка не имеет. Её изучают десятки лет, нарыли про неё кучу разрозненных фактов, которые весьма разнородны по своему содержанию и толком никак не систематизированы. Продолжают нарывать новые. Большинство таких фактов представляют из себя теоремы с простенькой формулировкой в 2-3 строчки и доказательством, зачастую содержащим около сотни страниц. Нехилая такая коробочка с головоломками, каждая из которых простотой формулировки и сложностью доказательства напоминает ВТФ, Куча народу с недоумением вопрошает, почему полурешётка Тьюринга так популярна, и многие тут же сами отвечают на свой риторический вопрос: изучать её невероятно трудно, однако время от времени кое-что сделать всё же удаётся, и это периодическое кое-что не даёт интересу угаснуть.

Вот самый известный пример. Проблема Поста, заключающаяся в вопросе о том, существуют ли промежуточные вычислимо перечислимые $T$-степени (то есть $T$-степени, содержащие характеристическую функцию вычислимо перечислимого множества и отличные как от разрешимой $T$-степени, так и $T$-степени проблемы остановки) была сформулирована в 1944 году и решена лишь в 1956. Решение в напечатанном виде занимает всего полторы странички, однако чтобы его найти, потребовалось целых 12 лет. И не потому, что никто не искал, наоборот, все кто шарил в теме бросились искать. Ну а потом уже телега покатилась с горы, новые результаты стали появляться всё чаще и чаще. Сейчас народ слегка подустал и результаты появляются реже, однако ручеёк полностью пересыхать пока не собирается...

Самое важное прикладное значение $T$-степеней связано, видимо, с арифметикой Пеано, хотя это лично моя оценка. Там вот что. Если взять машину с оракулом $\mathbf{a}$ и сформулировать проблему останоки для неё, то она с данным оракулом разрешима не будет, однако будет разрешима с более мощными оракулами, наименьший из которых обозначается $\mathbf{a}'$. Далее, имеем оракул $\mathbf{0}$ для наименьшей $T$-степени, и вслед за ним порождаемую им последовательность $\mathbf{0}', \mathbf{0}'', \ldots$. Ноль с одним штрихом - это как раз проблема остановки (классической машины без оракула), с двумя штрихами - проблема ответа на вопрос, будет ли классическая машина останавливаться при любых входных данных, с тремя штрихами - будет ли иметь место остановка машины при всех входных данных за исключением, возможно, лишь конечного числа. Далее тоже можно давать интерпритации... И вот интересный факт - ноль с $n$ штрихами - эта минимальный оракул, решающий задачу об истинности на натуральных числах формулы вида $\exists x_1 \ldots \exists x_k \forall y_1 \forall y_n \exists z_1 \ldots (p = 0)$, то есть формулы, у которой $(n-1)$-перемена кванторов (или, эквивалентно, $n$ различных групп кванторов), а бескванторная часть записана как равенство нулю полинома с целыми коэффициентами от всех стоящих за кванторами переменных). Если же брать арифметику в целом, не накладывая заранее никаких ограничений на сложность кванторной приставки, про проблема установления истинности формул не разрешима ни с одним из перечисленных оракулов, а разрешима лишь с оракулом $\mathbf{0}^{(\omega)}$, который следует после всех оракулов вида ноль с конечным числом штрихов. Вот все знают про теорему Гёделя; дескать, элементарная теория арифметики не разрешима. Но эта популярная в народе формулировка - лишь верхушка айсберга, а если глянуть глубже, то минимальный оракул, позволяющий решать вопрос об истинности арифметических формул - это в точности $\mathbf{0}^{(\omega)}$. Следовательно, если ввести естественную кодировку арифметических формул натуральными числами, то истинность формул арифметики в самой арифметике не выразима. Другими словами, теория арифметики имеет неарифметическую сложность

-- Пн фев 13, 2012 19:35:40 --

(Оффтоп)

При этом, как не странно, теория действительной прямой вообще оказалась разрешимой. То есть сложность у неё нулевая. Такой вот факт, известный как теорема Тарского.

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

Хотя это, конечно, шутко :-) Если начать выписывать точные формулировки, касающиеся оценки сложности различных теорий, то весь шокирующий эффект теоремы Тарского сразу пропадёт...

-- Пн фев 13, 2012 19:50:32 --

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

вообще, мне кажется, что квантовая механика - это не то место, где нужно искать Оракулы.

Тогда их вообще станет негде искать

Ну разве что заниматься медитацией и усердно молиться Богу о ниспослание оракулов с неба. Или ждать зелёных человечков на летающем блюдце, у которых оракулы как у нас сотовые телефоны... Или даже не знаю, что ещё, Шамбалу найти, может там что-нибудь завалялось... Одно можно сказать точно: либо существование оракулов допускается непознанными пока физическими законами, либо не допускается, и тогда естественные источники отпадают, надо искать в сверхестественных...

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

[epros]

Профессор Снэйп в сообщении #538262 писал(а):

Тогда их вообще станет негде искать

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

Угу, однозначно.

Профессор Снэйп в сообщении #538262 писал(а):

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

Мне почему-то кажется, что при решении вопроса о существовании "непознанных пока физических законов" без оракула никак не обойтись.

Профессор Снэйп в сообщении #538262 писал(а):

Кстати, последние годы появилась тема про квантовые компьютеры, у которых кубиты вместо битов и что-то там ещё. Я читал Википедию, но так и не понял, что это за хрень такая. Более понятной и обстоятельной литературы по ним увы, не попадалось. Однако!.. слышал от людей, которые сами слышали непосредственно от шарящих в теме, что именно эти компьютеры никаких оракулов дать не могут. Они вычисляют в точности те же функции, что и обычные компьютеры, правда некоторые из функций вычисляются ими чуть быстрее.

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

Профессор Снэйп в сообщении #538262 писал(а):

И когда их наконец реализуют, мало что изменится.

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

Но это, конечно, далеко не оракул.

[Munin]

Профессор Снэйп в сообщении #538262 писал(а):

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

Всё, дальше понимание отключилось :-) Извините, алгебру давно позабыл.

Профессор Снэйп в сообщении #538262 писал(а):

Тогда их вообще станет негде искать

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

Это если на другую чашу весов класть поиск Шамбалов.

Профессор Снэйп в сообщении #538262 писал(а):

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

Ровно до тех пор, пока они работают по уже открытым квантовым законам. Впрочем, именно такими их и проектируют :-)

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

Munin в сообщении #538279 писал(а):

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

Ну нельзя же быть таким утилитарным. Всякое знание имеет ценность, не утилитарную так хотя бы эстетическую.

К тому же математическое знание вообще обходится обществу крайне дёшево. Грантик на еду, грантик для поезки на конференцию... Сколько по сравнению с этим стоит, к примеру, новый радиотелескоп. Который построили, чтобы изучать особенности излучения пульсара в соседней Галактике. Нам бы в ближайшие 100 лет до Марса хотя бы добраться

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

[Munin]

Профессор Снэйп в сообщении #538317 писал(а):

Ну нельзя же быть таким утилитарным. Всякое знание имеет ценность, не утилитарную так хотя бы эстетическую.

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

Профессор Снэйп в сообщении #538317 писал(а):

К тому же математическое знание вообще обходится обществу крайне дёшево.

Ага, я слышал, а философам даже ластики не нужны...

Профессор Снэйп в сообщении #538317 писал(а):

Сколько по сравнению с этим стоит, к примеру, новый радиотелескоп.

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

[Утундрий]

Профессор Снэйп в сообщении #538262 писал(а):

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

Профессор Снэйп в сообщении #537849 писал(а):

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

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

- Сколько будет дважды два?
- Скорее всего 4.

Устроит такой "оракул"?

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

Munin в сообщении #538324 писал(а):

Нет, оно, конечно, имеет ценность, но отсутствие интереса к рядом находящемуся другому подходу - вот это меня удивляет.

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

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

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

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

Матан великолепен своими неожиданными парадоксами, которых не так много, но каждый из которых - огромная чистая жемчужина. Конструкция неизмеримого множества, коврик Серпинского или теорема о том, что шар можно поделить на пять частей, из которых впоследствии складывается шар в два раза большего радиуса. Алгебра поражает неожиданными логическими ходами, когда она нелинейна; однако нет ничего скучнее, чем умножать матрицу на вектор и это, увы, тоже алгебра. ТФКП - удивительно красивая дисциплина, хотя не без ложки дёгтя; оказывается, с его помощью какие-то уравнения с краевыми условиями иногда решают. Функан - одна из самых чудесных дисциплин, пока речь идёт об абстрактных операторах в банаховых пространствах, но как только начинают рассматривать конкретные интегральные операторы, всё очарование куда-то теряется. Дифгем - вообще красотища, хотя нам его и плохо читали. Самый мерзкий предмет на мехмате - исследование операций; какие-то симплексы, задачи о ранце... Ну а матлогика с теорией алгоритмов - это просто чистое очарование ничем не замутнённой бесконечности, сферическая змея в вакууме, извернувшаяся бутылкой Клейна, чтобы укусить собственный хвост изнутри себя. Именно здесь принцип чистого существования доведён до своего последнего предела. Подумайте только: вместо того, чтобы доказывать некоторую теорему $A$, мы доказываем теорему $B$, которая утверждает, что теорема $A$ доказуема! И редко-редко что-нибудь программируем, предпочитая вместо этого доказывать теорему о существовании программы с нужными нам свойствами!

-- Вт фев 14, 2012 00:06:23 --

Утундрий в сообщении #538358 писал(а):

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

- Сколько будет дважды два?
- Скорее всего 4.

Устроит такой "оракул"?

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

[Утундрий]

Профессор Снэйп в сообщении #538367 писал(а):

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

Обычный компьютер в процессе функционирования проходит через определенную последовательность классических состояний. Можно условно сказать, в каждый момент времени - он какое-то определенное число. Квантовый же комп в процессе бытия своея вообще непойми-разбери-что-за-квази-конь, а числом становится, когда ему скажут "тпру!" Причем числом он становится с некоторой не единичной вероятностью. То есть, будучи последовательно приготовляем одинаковым образом (для решения одной и той же задачи) он вполне может каждый раз выдавать разные результаты. Это, насколько я понимаю - плохо. С другой стороны, "функции" в нем копошатся - закачаешься. Такие обычному компу и не снились. Это, как я могу предположить - хорошо.

[Munin]

Профессор Снэйп в сообщении #538367 писал(а):

А всё, что имеет практическое применение, обычно оказывается чем-то грубым, неказистым, да и ещё излишне прямолинейным к тому же.

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

[epros]

Профессор Снэйп в сообщении #538367 писал(а):

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

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

Возвращаясь к теме: Где бы взять такое физическое устройство, которое бы отвечало окончательно и бесповоротно какие из высказываний в языке арифметики второго порядка "семантически истинны", а какие "семантически ложны"? Ясно, что это устройство должно быть чем-то более мощным, чем Машина Тьюринга, так что без оракулов тут никак не обойтись.

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

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

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

Возвращаясь к теме: Где бы взять такое физическое устройство, которое бы отвечало окончательно и бесповоротно какие из высказываний в языке арифметики второго порядка "семантически истинны", а какие "семантически ложны"? Ясно, что это устройство должно быть чем-то более мощным, чем Машина Тьюринга, так что без оракулов тут никак не обойтись.

Хо-хо-хо

Арифметика второго порядка - тот ещё зверь.

Теория натуральных чисел, записанная в арифметике второго порядка, безусловно категорична. Более того, конечно аксиоматизируема. Записываем аксиомы Пеано (на языке первого порядка, но без схемы аксиом индукции) плюс аксиому матиндукции (язык первого порядка не позволяет её записать, а второго порядка - пожалуйста). У полученного списка аксиом одна-единственная модель - натуральный ряд. Вот Вам и категоричность.

А у Вас некая каша в голове наличествует. При чём здесь континуум-гипотеза? Она, во-первых, не относится к арифметике, а во-вторых... в языке теории множеств можно сформулировать континуум-гипотезу как на языке второго порядка, так и на языке первого порядка. Ну и что? От того, что Вы смогли сформулировать гипотезу, она не стала истинной

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

(Оффтоп)

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

Со вторым абзацем согласен. Если начинаем делать высказывания о числах на языке второго порядка, то получаем уже не арифметическую, а аналитическую иерархию. Это ещё "дальше в космос". Оракулы там нужны более "мощные"

[epros]

Профессор Снэйп в сообщении #540103 писал(а):

А у Вас некая каша в голове наличествует ... я даже не знаю, с чего начать, чтобы разгребсти ...

Это точно, не отрицаю. Начните хоть с чего-нибудь, буду благодарен.

Профессор Снэйп в сообщении #540103 писал(а):

При чём здесь континуум-гипотеза? Она, во-первых, не относится к арифметике

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

Профессор Снэйп в сообщении #540103 писал(а):

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

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

Профессор Снэйп в сообщении #540103 писал(а):

У полученного списка аксиом одна-единственная модель - натуральный ряд.

Упс. так весь вопрос в том, почему это так. Вроде бы есть на этот счёт некая теорема, если не ошибаюсь - Дедекинда. Но я что-то в её смысл не въеду. К тому же, что значит "модель - натуральный ряд"? Насколько я понимаю, арифметика второго порядка - это нечто большее, чем просто теория натуральных чисел. Она оперирует не только "натуральными числами", но и "любыми множествами натуральных чисел". В этом смысле, насколько я знаю, её даже считают теорией действительных чисел.

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

Что-то мы далеко ушли от изначальной темы. Если интересно пообсуждать логику второго порядка - предлагаю переместиться куда-нибудь в математику