Гедель у falcao

[fregimus]

falcao пишет о Геделевой теореме о полноте (обсуждать здесь). Мне было интересно коснуться логики и полноты формальных систем только в прикладном (к вопросам о сознании) аспекте; falcao же — математик-теоретик и наиопытнейший преподаватель, и, несомненно, его математическое изложение будет одновременно и глубже, и проще для понимания, чем мое.

Comments

[(Anonymous)]

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

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

[(Anonymous)]

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

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

принцип компактности

[falcao.livejournal.com]

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

Если Вы хотите комментировать, то проще всего завести аккаунт в ЖЖ. Это пятиминутное дело.

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

Если у Вас есть бесконечный набор аксиом, и Вы из него вывели противоречие, то имеется доказательство, в котором цитировалось конечное число аксиом. Это как раз прямо следует из того, что "доказательство представляет собой текст конечной длины". Если мы из нашего бесконечного набора оставим только то, на что мы ссылались в нашем выводе противоречия, то получим конечный набор аксиом, из которого противоречие выводится в точности тем же способом. То есть в основе своей лежит совсем простой эффект.

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

Например, если имеется замкнутый отрезок [a,b] на числовой прямой, и его как-то покрыли бесконечным числом открытых интервалов (не содержащих своих "концов"), то из такого покрытия можно всегда выделить конечное подпокрытие. Это одна из стандартных теорем, излагаемая обычно в курсах математического анализа. Но если бы мы сделали то же самое с открытым интервалом (a,b), то компактности здесь уже нет: легко привести пример такого бесконечного покрытия, из которого конечного подпокрытия выделить нельзя.

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

Re: принцип компактности

[(Anonymous)]

Напрасно вы так боитесь анонимуса, вот внизу мне ответили даже короче и лучше ;)

[(Anonymous)]

Спасибо, теперь понял.
(первый анонимус).

предпочтительность неанонимности

[falcao.livejournal.com]

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

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

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

Так и хочется закончить этот коммент чем-то вроде "социальной рекламы": "Заведите аккаунт!" :)