Лемма Линденбаума и аксиома выбора

[Ираклий]

AGu в сообщении #264134 писал(а):

тут даже эффективность нумерации не нужна

Согласен. Фиксируем просто какую-нибудь нумерацию. Чтобы выбрать элемент из непустого множества, АС не нужна.

[hurtsy]

Ираклий

Цитата:

Пронумеруем эффективно вообще все формулы: $A_m=\{A_0,A_1,...\}$

А здесь, может быть пригодится AC С уважением,

Кажется AGu уже все "проник", но откуда знать, что подразумевал "спешащий лектор".
Ираклий

Цитата:

Чтобы выбрать элемент из непустого множества, АС не нужна.

А из пустого множества, без АС, ну никак. С уважением.

[Ираклий]

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

[Someone]

Ираклий в сообщении #264080 писал(а):

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

А, Вы об аксиоме выбора... Прошу прощения, я думал о другом:

Ираклий в сообщении #263409 писал(а):

Построение последовательности $\Gamma_n$ мне кажется совершенно конструктивным.

Я здесь "конструктивность" понял в смысле существования алгоритма.

-- Вс ноя 22, 2009 00:52:51 --

(Оффтоп)

hurtsy в сообщении #264143 писал(а):

А из пустого множества, без АС, ну никак.

А из пустого множества и с АС никак.

[Ираклий]

Someone в сообщении #264289 писал(а):

Я здесь "конструктивность" понял в смысле существования алгоритма.

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

[Nik_Nikols]

Цитата:

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

Не достаточно.

[AGu]

Nik_Nikols в сообщении #264322 писал(а):

Цитата:

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

Не достаточно.

Значит, я таки глючу. Было бы интересно узнать, где именно.

Если в стартовом сообщении удалить слово «эффективно», то, как мне кажется, мы получим доказательство (без аксиомы выбора) утверждения о том, что для произвольной нумерации $(A_n)_{n\in\omega}$ языка существует максимальное расширение. Если язык счетен, то нумерация существует (по определению счетности). Значит, существует и расширение. Где тут прокол?

[Someone]

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

[AGu]

Someone в сообщении #264412 писал(а):

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

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

[Someone]

Я, может быть, неправильно понимаю предмет обсуждения.

Как я понял, ненужность аксиомы выбора аргументируется тем, что можно написать некую (мета)формулу, определяющую $\Gamma_n$. Однако, если нумерация не задана конструктивно, такую формулу мы вряд ли напишем.

[AGu]

Someone в сообщении #264419 писал(а):

Как я понял, ненужность аксиомы выбора аргументируется тем, что можно написать некую (мета)формулу, определяющую $\Gamma_n$. Однако, если нумерация не задана конструктивно, такую формулу мы вряд ли напишем.

Мне по-прежнему кажется, что для доказательства существования максимального расширения такая формула не требуется. Достаточно существования биекции $f:\omega\to{\rm Fm}$, из которого все дальше и выводится. При этом, пожалуй, единственным неочевидным моментом является существование рекурсивно определяемой последовательности $(\Gamma_n)_{n\in\omega}$. Ее существование следует из принципа рекурсии, который, в свою очередь, опирается на аксиому подстановки. Множества $\Gamma_n$ определяются посредством $f$, но, к счастью, аксиома подстановки допускает использование формул «с параметрами» (т.е. с дополнительными свободными переменными). Вот наше $f$ и используется в качестве параметра.

Я хочу подчеркнуть следующее: для рекурсивного определения функции (в нашем случае — последовательности) не обязательно задавать рекурсивное правило формулой без параметров. Наличие параметров лишает определяемую функцию «конструктивности» (определимости без параметров), но не лишает ее существования (коль скоро параметры с нужными свойствами существуют).

P.S. Извините за сумбур. Просто нет времени все четко расписать через аксиомы.

[Ираклий]

Someone в сообщении #264419 писал(а):

Как я понял, ненужность аксиомы выбора аргументируется тем, что можно написать некую (мета)формулу, определяющую $\Gamma_n$.

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

[tori]

Проясните следующий вопрос об этом лемме. Она выполняется и для теорий со счётной мощностью. Так вот если взять одну из формулировок теоремы Гёделя о неполноте, а именно
Каждое непротиворечивое конечно аксиоматизируемое расширения арифметической формальной системы S есть неполная система.
Если я правильно помню конечно аксиоматизируемое это теория с конечным числом аксиом. Так вот если построить такую цепочку $\Gamma_{n+1}$ над формальной арифметикой, разве мы не получим противоречие теоремы Гёделя?.

[AGu]

tori в сообщении #279818 писал(а):

если построить такую цепочку $\Gamma_{n+1}$ над формальной арифметикой, разве мы не получим противоречие теоремы Гёделя?

Такое расширение не будет конечно аксиоматизируемым. Оно даже не будет порождаться рекурсивно перечислимым множеством аксиом (по теоремам Гёделя и Крейга).