avva | вести с логического фронта: Виттгенштейн Гёдель

вести с логического фронта: Виттгенштейн Гёдель

Между тем в рассылке FOM (Foundations of Mathematics) уже две недели, оказывается, идут ожесточённые споры о Виттгенштейне и Гёделе (у меня эта рассылка складывается автоматически в отдельную папку, и я иногда забываю её читать).

Виттгенштейн немало написал о философии математики; большинство написанного им на эту тему собрано в опубликованном посмертно сборнике Remarks on the Foundations of Mathematics (1956). Надо отметить, что существует мнение (которого придерживаются и многие из тех, кто ценят у уважают труды Виттгенштейна в других областях), согласно которому взгляды Виттгенштейна на философию математики особого интереса не представляют, потому что В. очень плохо знал математику, и его рассуждения полны элементарных технических и математических ошибок и заблуждений (мне это мнение кажется более или менее верным). Другие считают, что, несмотря на математические ошибки (некоторые из которых они считают не ошибками, а неправильной интерпретацией слов В.), в рассуждениях В. на эти темы есть очень много важного и полезного.

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

Вот это высказывание:

I imagine someone asking my advice; he says: "I have constructed a
proposition (I will use 'P' to designate it) in Russell's symbolism, and by
means of certain definitions and transformations it can be so interpreted
(or clarified) that it says: 'P is not provable in Russell's system'. Must I
not say that this proposition on the one hand is true, and on the other hand
is unprovable? For suppose it were false; then it is true that it is
provable. And that surely cannot be! And if it is proved, then it is proved
that it is not provable. Thus it can only be true but unprovable.

Just as we ask: "'provable' in what system?", so we must also ask: "'true'
in what system?" 'True in Russell's system' means, as was said: proved in
Russell's system; and 'false in Russell's system' means: the opposite has
been proved in Russell's system. Now what does your "suppose it is false"
mean? In the Russell sense it means 'suppose the opposite is proved in
Russell's system'; if that is your assumption, you will now presumably give
up the interpretation that it is unprovable. And by 'this interpretation' I
understand the translation into this English sentence.—if you assume that
the proposition is provable in Russell's system, that means it is true in
the Russell sense, and the interpretation "P is not provable" again has to
be given up. If you assume that the proposition is true in the Russell
sense, the same thing follows. Further: if the proposition is supposed to be
false in some other than the Russell sense, then it does not contradict this
for it to be proved in Russell's system. (What is called "losing" in chess
may constitute winning in another game.) (RFM, I, Appendix III, §8)

Первый абзац здесь — относительно нормальный пересказ одной из версий "неформального" аргумента первой теоремы о неполноте Гёделя; со вторым абзацем плохо — там идёт густой туман, который, кажется, можно объяснить только тем, что В. не очень понимает, что такое "истинность" в формальной логике и чем она отличается от доказуемости (не различает синтаксис и семантику, одним словом).

Так вот, оказывается, Floyd & Putnam (имя первой мне раньше не встречалось, второй — очень известный философ, специалист в области философии науки/математики/логики) опубликовали статью пару лет назад, в которой они утверждают, что в этом отрывке из Виттгенштейна скрывается глубокая, технически нетривиальная мысль, которую все проглядели. Вокруг этой статьи и развивается сейчас дискуссия в FOM, с периодическим участием Floyd.

Статья Флойд и Патнема есть в сети (формат PDF). Она не слишком длинна и хорошо написана. Моё первичное впечатление вот какое:

Изобретательность, с какой авторы статьи впихивают нетривиальное содержание в слова Виттгенштейна — поразительна; тем не менее,
всё же это слишком неубедительно — как то, что Виттгенштейн мог сам дойти до этого (не слишком сложного, но технически нетривиального) результата в области, в которой он, судя по другим его рассуждениям вокруг и около, очень мало понимал; так и то, что если бы он хотел именно это сказать, то записал бы так, как он написал. Кроме того,
сам аргумент, приписываемый В., вызывает у меня подозрения; точнее, его можно разделить на математическую и философскую части, и то, что философская интерпретация (а именно: нам нужно будет отказаться от представления о том, что наша формула передаёт неформально утверждение о том, что её невозможно доказать в PM) следует из математического результата (а именно: нестандартные модели у теории, которая не омега-консистентна). Мне кажется, что Floyd & Putnam совершенно необоснованно переходят от синтаксической репрезентации соответствующих предикатов "x — натуральное число" итп. к их семантической репрезентации. Доказательство теоремы Гёделя использует синтаксическую арифметизацию, в рамках которой не очень важно, какие именно члены какой-нибудь модели будут выполнять нашу формулу "x — натуральное число"; важно, чтобы сама теория T, для которой мы доказываем неполноту, доказывала нужные свойства наших арифметизированных предикатов.

Впрочем, насчёт третьего возражения я пока не уверен, это только набросок мысли; но это возражение, с другой стороны — самое существенное с точки зрения собственно аргумента Floyd & Putnam (а не вопроса о том, что думал или не думал Виттгенштейн). Если смогу ещё подумать над этим и уточнить как следует мысль, напишу в FOM по этому поводу.

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

Flat | Top-Level Comments Only

ИМХО герр Виттгенштейн действительно не понял разницы между доказуемостью и истиной, а именно, что из доказуемости следует истина утверждения, но не наоборот. Об этом свидетельствует предложение "'True in Russell's system' means, as was said: proved in
Russell's system"
Формальной логикой я не занимался уже лет 8, но сдается мне, что путаница находится именно тут. Ежели Флойд и Патнем видят там еще какой-то глубокий смысл, то ИМХО это потому, что они шибко умные и склонны видеть глубокие смыслы во всем :)

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

Это, конечно, так. Тем не менее, есть некие естественные пределы, за которыми лежит уже довольно очевидное "вчитывание" смысла в слова W. Мне кажется, что Флойд и Патнем эту границу в данном случае перешли.

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

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

Спасибо.

Первичный набросок моего аргумента по-английски.

F&P's claim is that our claim that the Godel sentence P formalises an informal description "P is not provable" is dubious, in the light of the possibility that PA proves not(P) (which is at least conceivable). If PA proves not(P), then it is necessarily the case that PA is not omega-consistent (this follows directly from Goedel's proof). If PA is not omega-consistent, then it only has nonstandard models, i.e. N is not its model. PA is unsound. In that case,
any model of PA we might care to take will have its own interpretations on what a "natural number" is and those interpretations won't be isomorphic to N. Since our original understanding of P as saying "P is not provable" rested on arithmetical properties of "real" +, * etc. in N,
this understanding is no longer relevant.

First of all, let us observe that this argument only depends on PA being unsound. The part where we start by assuming that PA proves not(P), from which it follows that PA is not omega-consistent, from which it follows that it only has models which are not isomorphic to N -- all of this is the interpretation F&P suggest for Wittgenstein's wording. Their *conclusion* - that we must abandon our claim that P formalises "P is not provable" - only depends on the assumption that no model of PA is isomorphic to N, which is to say, PA is unsound. We can get to "PA is unsound" by assuming that PA proves not(P), or we could just assume that PA is unsound - it won't make any difference as far as discussing the conclusion goes.

Yet we know that Goedel's proof nowhere depends on PA being sound. It works for unsound theories T as well as for sound theories, and soundness is nowhere used in Goedel's proof. So if P&F's claim is correct, it surely must follow that when we apply Goedel's proof to an unsound theory T which satisfies all the usual requirements (for a specific example, think of T = PA + not(Con(PA)) ), and build a Goedel's sentence P(T) for such a theory T, it is improper in such a case to claim that P(T) formalises "P(T) is unprovable".

Why is it improper, though? We can still prove that P(T) is true in N if and only if there is no proof of P(T) in T, right? Formulas that we build for T, such as Proof(x,y), serve both as representations of the relevant concepts inside T, *and* as definitions of the relevant concepts inside N. If x codes a proof of y in T, it is true that T proves Proof(x,y) *and* Proof(x,y) is true in N, as an assertion about natural numbers. Why should we feel compelled to pass to some particular *model of T* in order to judge whether Proof(x,y) (or P(T)) is true?

It seems clear that we should not feel compelled to do that. Our judgement that P(T) is true iff P(T) is unprovable in T was always a judgement about truth of an arithmetical sentence in a particular model: our canonical model N. The fact that N might not be a model of T is of no consequence to us when we speak of P(T) as a true sentence about natural numbers; we're just *studying* the theory T. It's the same with PA: the fact that we thought it was sound but it turns out (as we assumed) not to be, should not compell us to change our understanding of what it means, for a sentence in the language of arithmetics, to be true. It is a different matter how we *show* it to be true, of course. For that,we might use informal arguments (after all, Goedel's proof doesn't need this), or we might use ZFC and prove it rigorously.
[to be cont'd]

Вопрос (который выдает меня с головой как полного дилетанта в области логики). Если система Principia Mathematica (или ZFC. Выбор конкретной системы вроде бы не влияет на аргумент)*не* описывает N, то тогда как мы вообще определим само N?

И совсем маленький вопросец - почему Вы расселовскую систему обозначаете PA? Она ж вроде Principia Mathematica?

Мы можем определить N в ZFC, и мы можем определить в ZFC, что значит для утверждения φ быть истинным в N. Но это само по себе не гарантирует, что для любого возможного φ мы сможем либо доказать, что оно истинно в N, либо опровергнуть (т.е. доказать противоположное).

Выбор - ZFC или PA (Peano's Arithmetic, аксиоматическая система для арифметики; почему не PM - об этом ниже) здесь довольно важен, и непонимание различий приводит часто к путанице.

Очень важно понять, что теорема Гёделя сама по себе не нуждается в семантике - ей не нужно ни N, ни понятие "истинности" утверждений. Она сугубо синтаксична. Если есть некоторая теория, достаточно сложная (могущая доказать некоторые свойства натуральных чисел) и рекурсивная (множество аксиом конечно или бесконечно, но описывается алгоритмом), то эта теория неполна: неверно, что она может доказать или опровергнуть любое утверждение. Здесь речь идёт только о возможности доказать/опровергнуть, т.е. о существовании каких-то формальных последовательностей символов (формальных доказательств из аксиом данной теории).

Если наша теория T сформулирована в языке арифметики (константа 0, функции + и * итп.), то гёделево утверждение G, к-е мы для него построим, будет утверждением о натуральных числах, являющимся в некотором неформальном смысле формализацией утверждения "меня невозможно доказать". Если мы теперь обратим внимание на семантику, т.е. рассмотрим стандартную модель арифметики N и истинность в ней, окажется, что утверждение G истинно. Само по себе это неудивительно, т.к. в некотором смысле (очень и очень неформальном) истинность G "встроена" в него на метаматематическом уровне (математический уровень - наши формальные доказательства в формальной системе T; метаматематический уровень - рассуждения о таких формальных доказательствах в T). По сути дела, в процессе доказательства теоремы Гёделя мы берём всякого рода метаматематические понятия (напр. доказуемость в T), и вталкиваем их в математическую вселенную путём их арифметизации (путём кодирования формул и доказательств числами, и составления утверждений об этих числах, соответствующих метаматиматическим свойствам исходных формул/доказательств).

Следует различать использование слов, подобных слову "истинность", на метаматематическом и математическом уровнях. На метаматематическом уровне такое использование неизбежно, неформально и ограниченно (например, на этом уровне мы говорим: система T доказывает утверждение φ . Это высказывание может быть истинным или ложным. Эта истинность или ложность - метаматематического характера). На математическом уровне мы рассматриваем истинность данного формального утверждения φ, например, в модели N (например, на этом уровне мы говорим: формула вида Thm_T('φ') верна в N, где Thm_T(x) предикат, который мы построили для отображения в арифметике понятия доказуемости в T, а 'φ' - число, код формулы φ). Этот вид истинности незаменим в теории моделей и в логике вообще, но он не нужен для доказательства теоремы Гёделя, это док-во не пользуется семантикой на математическом уровне.

Из того, что теория T неполна (синтаксическое доказательство Гёделя), мы можем мгновенно заключить, что она не "описывает" N, т.к. для "описывания" N ей пришлось бы доказывать все истинные в N утверждения и опровергать все ложные; т.к. любое утверждение либо истинно в N, либо ложно, T должна была бы быть полной теорией.

Теперь про ZFC.
[to be cont'd]

[cont'd]
У ZFC просто нет канонической модели, в том смысле, в каком она есть у арифметики. Когда мы говорим, что что-то "истинно" в ZFC, это всегда означает формальное доказательство из ZFC и ничего другого. К ZFC, однако, тоже можно применить теорему Гёделя, т.к. она мощнее чем, скажем, PA, для которой мы провели полностью док-во Гёделя, и PA можно в ней "интерпретировать". Для ZFC можно построить утверждение G, к-е не будет ни доказуемо, ни опровергаемо в ZFC. Но говорить о его истинности мы можем теперь только с неформальной, метаматематической точки зрения.

Или вот ещё один способ посмотреть на то же самое. Гёделево утверждение G для PA верно в N (неформальный аргумент), и мы это можем формально доказать, но не в самой PA (она это не может доказать, потому что внутри неё вообще нельзя определить "истинность в N"), а в куда более мощной ZFC. ZFC мощна, и потому мы можем определить нашу семантическую "вселенную" N в ней в качестве синтаксического объекта-множества N, и свести любое семантическое утверждение об истинности в N к синтаксическому утверждению о доказуемости соответствующего утверждения о множествах. Гёделево утверждение G для ZFC в каком-то неформальном смысле тоже "истинно", но формализовать эту "истинность" нам уже просто негде.

Я, кажется, сильно увлёкся и ушёл в сторону от Вашего вопроса. Поэтому попробую к нему вернуться.
Разница между PA и ZFC вот в чём. И та и другая - формальные теории, некий набор аксиом. Однако для первой N не является частью теории, а является моделью, какой-то канонической моделью, которую мы выбрали, и в которой мы проверяем истинность или ложность утверждений PA или любых других утверждений в том же языке арифметики, когда нам это удобно. Для ZFC же N - это объект, описываемый теорией, это множество, как любое другое множество, о котором ZFC что-то может доказать. Если мы посмотрим на какую-то модель ZFC (очень гипотетически, т.к. существование такой модели мы не можем доказать вследствие 2-й теоремы Гёделя о неполноте), то N в ней будет *элементом*, а не самой моделью. N для ZFC - это как натуральное число для PA. И в контексте теоремы Гёделя ZFC выступает в двух очень разных ролях. С одной стороны, мы используем ZFC как некий универсальный формализатор всех математических методов: мы можем формализовать в нём само доказательство теоремы Гёделя, например, используя, в частности, его видение N как всего лишь множества, одного из рассматриваемых объектов. С другой стороны, мы можем к самой ZFC применить теорему Гёделя и найти в ней недоказуемое и неопровержимое утверждение; это возможно за счёт достаточнной внутренней сложности ZFC, рассматриваемой даже как "бессмысленная" система аксиом, вне зависимости от того факта, что на самом деле это та самая ZFC, к-ю мы используем для формализации всей математики.

Прошу прощения, если слишком сумбурно вышло. Наконец, про PA/PM. Система Principa Mathematica просто слишком громоздка и устарела, ей неудобно пользоваться. Поэтому обычно пользуются PA (Peano's Arithmetics) или другими формальными теориями арифметики; док-во Гёделя работает для них практически без изменений (даже с некоторыми упрощениями). PA - это теория в формальном языке, включающем в себя константный символ 0, функциональные символы +, *, S(x) (successor function). PA включает в себя следующие аксиомы:

S(x)=S(y) => x=y
(forall x)(x!=0 <==> (exists y)(S(y)=x))) (у каждого числа, кроме 0, есть предыдущее)
x+0=x
x+S(y)=S(x+y) (рекурсивное определение сложения)
x*0=0
x*S(y)=x*y+x (рекурсивное определение сложения)

и схема индукции: для каждой формулы вида φ(x) вводится аксиома

(φ(0) and (forall x)(φ(x)=>φ(S(x)))) ===> (forall x)φ(x).

[cont'd]
In a way, P&F's mistake is a weak echo of what the traditional interpretation of W's words says W's mistake was: trying to make semantics improperly follow syntax's orders. W., according to the traditional interpretation, ignorantly identified truth of a statement with its provability, but since the informal argument for Goedel's Theorem he has recounted specifically needs "real" semantic truth, different from provability, his remarks stop making any sense. Floyd and Putnam do not agree with this analysis or with the thought it ascribes to W.; they argue that we *need* real semantics to make sense of the informal "translation" of P as "P is unprovable". But the semantics they give stays improperly subservient to syntax: if the theory PA changes it status and it turns out it doesn't have N as a model, we suddenly must change our semantics to some other model of PA. There is no real reason to do it, though. PA is a theory under our investigation, and when we talk about the truth of a statement P about natural numbers, we use N not because N is a model of PA (what of it? plenty of other structures are models of PA too, but we don't use them), but simply because it's our canonical model which provides us with the very notion (the very fixed notion) of arithmetical truth.

Философия математики - наука гуманитарная ?
Я как-то читал формулировку различий между методологиями естественных и гуманитарных наук:
естественные ищут истинну, опираясь на соотвествие опыта и логики;
гуманитарные, отвергают единственность истины и скорее ищут единство смысла
рассматриваимых текстов и явлений , например высказывания идут не только в контексте
соотвествия опыту/консистентности/доказуемости, а и в их отношении к тому, что сказал или имел виду
Витгенштейн,Гёдель а также другие философы.

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

На полке лежит, впрочем, "Consilience" Уилсона, ждет своего часа.

не по теме, но вдруг подойдет - шоттер о выготском и витгенштейне.

Спасибо!

Как говорят "Умом Россию не понять".
Теорема Геделя кажется очевидным из обычных умозрительных рассуждений (в стиле того что "если бы было все так просто - то сършенно непонятно почему вдруг все так сложно). На эту тему вполне могут рассуждать не только философы, но и пьяницы за кружкой пива.
Вот объявили бы конкурс на самую простую в житейском смысла формулировку утверждения, эквивалентного Теореме Гёделя. Нашлось бы немало. Вообще не понимаю, длячего чтобы рассуждать о философии неполноты, следует пройти от начала до конца путь Геделя.

Я не читал "Remarks" и не видел раньше этой цитаты. Насколько я понимаю сейчас "Философские исследования", Витгенштейн отказывается принять на веру абсолютность логики и "объективной реальности" и тем более допустить обычный математический платонизм. Поэтому он "не различает синтаксис и семантику" не так, как плохой студент. Те кто "понимают" семантику в обычном смысле кажутся ему находящимися во власти иллюзии. Для него понятие истинности утверждения должно быть определено через действия человека. Один из возможных вариантов такого определения и есть отождествление истинности с доказуемостью. (Вопрос лишь насколько оправданно здесь употребление выражения "in sense of Russel".) В этом отрывке он, мне кажется, спорит не с теоремой Гёделя, а с утверждением "недоказуемое предложение Гёделя истинно." Речь идет о понятии истинности. Я не думаю что Витгенштейн думал здесь о нестандартных моделях.

Вряд ли мне удастся объяснить эти вещи лучше, чем это удалось Витгенштейну и сам я, наверное, не слишком ясно понимаю это.

Извините, у меня нет желания с Вами общаться.

Да, если Вы так задеты, я был явно неправ, извините.

Авва, когда-то довольно давно (в 2003 г.?) у Вас была запись, кажется, о Витгенштейне, но могу ошибаться. Кто-то (тоже неточно) назвал его "гением", а тот сказал что-то (опять неточно) типа: "Даже если бы это было так, он (говорящий) не мог бы об этом судить [не понял бы это]". В этой записи была полемика с Митей. Насколько я помню, он там подписывался именем "Фаина" (без журнала). Мне бы очень хотелось найти эту запись, а также любые другие записи, в которых Вас комментировала Фаина. Понимаю, что у Вас тысячи записей и корреспондентов, но, возможно, Вы вспомните хотя бы ту запись о Витгенштейне. Мити больше нет. 8 сентября он покончил с собой. Его журнал vasisualiy был "deleted and purged". Не знаю, можно ли восстановить его. Это было бы большим счастьем для многих людей.

Алиса (lublu, ptitza)

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

Если Вы помните эту ссылку и можете мне её сообщить, я буду очень признателен.

Flat | Top-Level Comments Only

вести с логического фронта: Виттгенштейн Гёдель

no subject

no subject

Re:

no subject

no subject

no subject

Re:

Re:

no subject

Любопытно, да.

Re: Любопытно, да.

&

по ассоциации имен

Re: по ассоциации имен

no subject

no subject

Re:

no subject

Re:

Генцен