Аксиомы Цермело-Френкеля и понятие предиката

[Anton_Peplov]

Одной из аксиом Цермело-Френкеля является аксиома степени: "для всякого множества $A$ есть множество всех его подмножеств $SA$".
С подмножествами, однако, не все так просто. Определение «$A \subset B$, если $\forall x\in A$ верно $x\in B$» дает критерий, является ли $A$ подмножеством $B$, но не дает ответа, какие подмножества $B$ существуют. В наивной теории множеств мы полагались на свое интуитивное видение, выраженное в формулировках типа «подмножеством $\mathbb{N}$ является любое множество, состоящее из натуральных чисел». Но наивная теория разбила лоб об антиномии. ТЦФ, дабы не повторить ее судьбы, в своих аксиомах указывает способы, которыми можно получать множества, и предполагается, что других множеств нет. Поэтому, пока не указано, какие существуют подмножества $A$, неясно, из каких элементов состоит $SA$.
Для выделения подмножеств $A$ служит аксиома выделения (вообще, она выводится в качестве теоремы из более сильной аксиомы замены, но здесь это не важно):
Для всякого множества $A$ и предиката $P(x)$ существует множество $B$, состоящее из тех и только тех $x\in A$, для коих $P(x)$ выполняется.
Эта аксиома, однако, ставит вопрос о том, что такое предикат. Этот вопрос не так прост, как кажется. Ведь если, например, потребовать, чтобы предикат описывался конечной фразой какого-то языка, получится, что имеется лишь счетное число предикатов, а значит, из множества $A$ с помощью аксиомы выделения может быть получена не более чем счетная система подмножеств. Получается, что континуальная система подмножеств может быть выделена только с помощью аксиомы выбора. Но с этим еще можно смириться, а вот нельзя ли опровергнуть предположение "множество всех предикатов, определенных на всем $\mathbb{N}$, счетно" с помощью диагональной процедуры Кантора?
Пусть $\Pi$ - любое счетное множество предикатов, определенных на всем $\mathbb{N}$. Занумеруем его и составим предикат $R(n) =\neg P_n(n)$. $R(n)$ отличается от всех элементов $\Pi$ хотя бы в одном числе и, значит, не входит в него. Следовательно, множество всех предикатов, определенных на всем $\mathbb{N}$, несчетно. Я в этом рассуждении ошибки не вижу, хотя это еще не значит, что ее нет.

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

Отсюда два простых вопроса:
1. Какое определение предиката используется (сегодня) при формулировании аксиом Цермело-Френкеля?
2. Корректно ли я опроверг гипотезу о счетности множества всех предикатов, определенных на всем $\mathbb{N}$?

[arseniiv]

Anton_Peplov в сообщении #997762 писал(а):

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

Вот тут вы явно перемешали теорию с метатеорией. И, чтобы особо не страдать, лучше в формулировке аксиомы выделения замените «предикат $P(x)$» на «формулу $P$ с одной свободной переменной $x$». Что такое формула с одной свободной переменной, при описании теории первого порядка, коей ZF(C) является, вполне ясно.

Соответственно,

Anton_Peplov в сообщении #997762 писал(а):

Какое определение предиката используется (сегодня) при формулировании аксиом Цермело-Френкеля?

Никакое.

Anton_Peplov в сообщении #997762 писал(а):

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

Во-первых, никаких способов ZF(C), если имелась в виду она (ни разу не встречался с сокращением «ТЦФ»), не описывает (ну вот на ту же аксиому выбора посмотрите). Во-вторых, ни разу не предполагается, что других множеств нет. Где вы такое прочитали?

[Anton_Peplov]

Anton_Peplov в сообщении #997762 писал(а):

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

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

-- 30.03.2015, 13:54 --

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

Вот тут вы явно перемешали теорию с метатеорией.

В книгах

А. Куратовский, А. Мостовский. Теория множеств М.: Мир, 1970
П. Дж. Коэн. Теория множеств и континуум-гипотеза М.: Мир, 1969
А. Френкель, И. Бар-Хиллел. Основания теории множеств. М.: Мир, 1966

слово "метатеория" не встречается. Как максимум, встречается "метаязык" как язык, на котором излагается теория, и упоминается, что это естественный язык плюс какие-то символы.
Поэтому просьба: порекомендуйте книгу, в которой:
а) разъясняется, что такое метатеория
б) излагается метатеория для построения ZF(C)
в) ZF(C) строится на основе этой метатеории (последнее, впрочем, факультативно, ибо, усвоив первые два пункта, я, наверное, смогу переосмыслить построения, выполненные в вышеупомянутых работах).

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

Во-первых, никаких способов ZF(C), если имелась в виду она (ни разу не встречался с сокращением «ТЦФ»), не описывает (ну вот на ту же аксиому выбора посмотрите). Во-вторых, ни разу не предполагается, что других множеств нет. Где вы такое прочитали?

Я имею в виду, что для всякого множества $A$ можно указать множества $B, C, D...$ из которых оно построено, и аксиомы ZF(C), с помощью которых это построение выполнено. В частности, есть множества любой конечной мощности, которые можно получить из теоремы пары и аксиомы объединения; есть счетное множество, существование которого постулируется в аксиоме бесконечности; есть континуум, который получается, когда из счетного множества выделяется счетная система непересекающихся подмножеств, а потом объединяются их всевозможные сочетания. И т.д.
Аксиоматизация теории множеств была предпринята, чтобы избежать антиномий. Я полагал, что антиномии изгоняются следующим образом: берется некоторый запас множеств и из него строятся другие множества строго по аксиомам и больше никак. Аксиомы таковы, что антиномий (по крайней мере, известных) в построенных множествах не наблюдается. А если я не прав, то тогда каким образом аксиоматика ZF(C) мешает рассматривать множество всех множеств или множество всех множеств, не содержащих самих себя? Аксиома регулярности в стандартный набор ZF(C) не входит.

[gefest_md]

Anton_Peplov в сообщении #997885 писал(а):

каким образом аксиоматика ZF(C) мешает рассматривать множество всех множеств

Если бы множество $M$ всех множеств существовало, тогда, по теореме Кантора, $M<\mathcal{P}(M)$, и нашлось бы множество $A\in \mathcal{P}(M)$, что $A\notin M$ (противоречие).

[AGu]

Anton_Peplov в сообщении #997885 писал(а):

Поэтому просьба: порекомендуйте книгу, в которой:
а) разъясняется, что такое метатеория

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

Anton_Peplov в сообщении #997885 писал(а):

Я имею в виду, что [...]

Боюсь, что из всего сказанного Вами неверно буквально все. И в основном — именно из-за перемешивания теории с метатеорией.

[Anton_Peplov]

gefest_md в сообщении #998079 писал(а):

Если бы множество $M$ всех множеств существовало, тогда, по теореме Кантора...

Я знаю. Вот аксиомы ZF(C), насколько я понимаю, и формулировались таким образом, чтобы такое множество нельзя было построить. Ни такое, ни какое-нибудь еще, приводящее к антиномиям. А для этого ограничивается само понятие множества: допустимо строить только такие множества, для которых можно указать, по каким аксиомам они построены. Но вот уважаемый arseniiv говорит мне, что понимаю я неправильно.

-- 30.03.2015, 20:13 --

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

Боюсь, что из всего сказанного Вами неверно буквально все. И в основном — именно из-за перемешивания теории с метатеорией.

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

[AGu]

Anton_Peplov в сообщении #998106 писал(а):

В таком случае перемешиваю ее не я по своей инициативе, а авторы вышеназванных книг

Охотно верю. Это все оно — отсутствие любви к читателю. Точнее, отсутствие заботы. У них там сплошь и рядом все это дело перемешивается. Где-то из-за небрежности, где-то из-за лени. И правда, скучно все время говорить строго и корректно. Но справедливости ради надо сказать, что такие небрежности бывают вынужденными. Иногда хочется донести очень простую мысль, но стоит начать ее строго оформлять (без недомолвок, четко отделяя мета-мух от предметных котлет), как эта мысль обрастает такими логическими лохмотьями, что чуть ли не теряется в них.

Anton_Peplov в сообщении #998106 писал(а):

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

Я — не возьмусь. Я слишком добрый. Да и не очень в теме, если честно. Могу разве что посоветовать договориться о встрече с каким-нибудь логиком и поболтать с ним часок-другой за чашечкой тепленького.

Собственно говоря, нужно попросту изучить логику. Ее основы. В классике сначала возникает так называемая наивная теория множеств. Это и есть метатеория. В ее рамках вводятся понятия языка, формул, аксиом, теорий, моделей и т.д. и т.п. Т.е. в рамках метатеории множеств дается понятие теории. А теперь — фокус-покус-филипокус (осторожно с извилинами, могут запутаться) — в рамках метатеории множеств возникает понятие теории множеств (как частный случай теории вообще). Вот, собственно и все. Но это надо понять. Даже прочувствовать. И это нелегко. Приобретается с опытом чтения, размышления и общения.

[Mikhail_K]

Anton_Peplov в сообщении #998106 писал(а):

Вот аксиомы ZF(C), насколько я понимаю, и формулировались таким образом, чтобы такое множество нельзя было построить. Ни такое, ни какое-нибудь еще, приводящее к антиномиям. А для этого ограничивается само понятие множества: допустимо строить только такие множества, для которых можно указать, по каким аксиомам они построены. Но вот уважаемый arseniiv говорит мне, что понимаю я неправильно.

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

Пример: используя аксиомы ZFC, любые, нельзя построить подмножество отрезка [0,1], имеющее мощность, промежуточную между счётной и континуальной. Это факт. Однако это не значит, что в рамках ZFC такого множества не существует. Оно, может быть, существует, а может, нет. Нельзя ничего сказать.

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

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

[Anton_Peplov]

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

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

Х. Карри. Основания математической логики. М.: Мир, 1969.
Р. Смальян. Теория формальных систем. М.: Наука, 1981.

Это подойдет?

[arseniiv]

(Про метатеорию.)

Да, мне самому слово «метатеория» куда проще понимать как вольность речи (точнее, как вольность речи понимать «смешивать теорию с метатеорией»), чем определять с точностью и аккуратностью. Вот мы можем в арифметике первого порядка закодировать формулы и конечные последовательности формул арифметики первого порядка числами — факт известный. Представим теперь теорию (ту же арифметику или что-то другое), объектами которой мы закодировали формулы и выводы нашей теории ZFC, и в которой мы можем написать формулы, означающие «$a$ — код не просто последовательности формул, а вывода», «$a$ — код последней формулы в последовательности с кодом $b$» и т. п.. Такую теорию, по моему представлению, и можно звать метатеорией для теории, которую мы «закодировали». Если представление не соответствует обычному смыслу термина, да поправят меня.

[Anton_Peplov]

Mikhail_K в сообщении #998130 писал(а):

Про те множества, которые мы не можем построить с помощью аксиом ZFC, мы просто не можем сказать: то ли они существуют, то ли не существуют.

Это верно. В этом смысл независимости континуум-гипотезы, например.
Принято как поправка.

-- 30.03.2015, 21:22 --

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

Да, мне самому слово «метатеория» куда проще понимать как вольность речи

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

[arseniiv]

Anton_Peplov в сообщении #998150 писал(а):

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

Книгу порекомендовать не могу («метатеория» как раз из тех старых, которые мне тоже не очень внушали радость, пока были силы читать (с монографией Барендрегта про λ-исчисление и то проще ладить!)), а в новых это слово не замечено. Рекомендовать книги остерегаюсь. Потом, я, вроде, выше попытался изложить строго, что понимаю под метатеорией.

Anton_Peplov в сообщении #997885 писал(а):

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

Счётным будет наименьшее возможное пересечение таких множеств $\omega = \{\varnothing,S\varnothing,SS\varnothing,\ldots\},$ где $Sx = x\cup\{x\}$, — их не обязательно одна штука. Например, $\omega\cup\{a, Sa, SSa,\ldots\}$, где $a = \{\{\varnothing\}\}$, ещё есть.

Anton_Peplov в сообщении #997885 писал(а):

Я имею в виду, что для всякого множества $A$ можно указать множества $B, C, D...$ из которых оно построено, и аксиомы ZF(C), с помощью которых это построение выполнено.

Не совсем понятно, что значит «для всякого множества $A$». Вы зафиксировали одну из моделей ZFC, или что? В таком случае, т. к. несчётные модели у неё всё-таки есть, найдутся их элементы, для которых в ZFC нет формулы с одной свободной переменной, истинной лишь на одном этом элементе, и осмысленность пропадает.

Anton_Peplov в сообщении #997885 писал(а):

Аксиома регулярности в стандартный набор ZF(C) не входит.

Разве? (Это так, в порядке оффтопа.)

[AGu]

Пожалуй, рискну рекомендовать одну книгу:

Булос Дж., Джеффри Р. Вычислимость и логика

Метатеория там не выпячивается. Это просто очень хорошая книга. (И современная.)

[Anton_Peplov]

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

Разве?

Ну, "не входит в стандартный набор" - возможно, слишком сильное выражение. Но Куратовский и Мостовский доказывают все основные теоремы без нее. Френкель и Бар-Хиллел ее, кажется, даже не упоминают (и уж точно не вносят в список необходимых в ZF(C) аксиом). Коэн говорит, что включает ее в список аксиом "по техническим причинам".

(Оффтоп)

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

Рекомендовать книги остерегаюсь.

Ох. Со всех сторон мне говорят, что я не разобрался в теме, и никто не может сказать, что же прочитать, чтобы разобраться. Кто там из классиков марксизма-ленинизма советовал, чтобы понять Гегеля, прочесть всего Гегеля?

[AGu]

Anton_Peplov в сообщении #998183 писал(а):

Со всех сторон мне говорят, что я не разобрался в теме, и никто не может сказать, что же прочитать, чтобы разобраться. Кто там из классиков марксизма-ленинизма советовал, чтобы понять Гегеля, прочесть всего Гегеля?

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