Противоречие Рассела

[alex55555]

Из выражения $\exists$Y \forall$$x (x\in$Y \leftrightarrow P(x))$, по общепринятому мнению, вытекает следующее:

Пусть $P(x)$ есть формула $x \notin$ $x$, тогда найдётся множество, для которого $ \forall$$x (x\in$Y \leftrightarrow x \notin$ $x)$. Так как это верно для любого $x$, то верно и для $x = $Y$. То есть $ $Y\in$Y \leftrightarrow $Y\notin$Y$.

Так рассуждают в википедии и в учебниках (например Куратовский, Мостовский Теория множеств).

Вопрос - почему при подстановке нового значения икса не учитываются внутренние связи выражения?

Похожий пример:

Пусть $x + y^2 - x^2 = z$, после замены $y^2 - x^2$ на $u$ имеем - $x + u = z$. Далее имеем право заменить $x$ на что-то другое, ну и заменяем его на $u$, получаем - $ u + u = z$. Далее раскрываем - $y^2 - x^2 + y^2 - x^2 = z$.

В чём отличие общепринятого подхода к подстановке в случае противоречия Рассела от предложенного подхода к подстановке в уравнение в предыдущем абзаце?

[mihaild]

Какие "внутренние связи" и что это вообще такое?
В неограниченной аксиоме выделения $P(x)$ должно быть формулой с одной свободной переменной $x$ (т.е. все остальные переменные должны стоять под кванторами, а по $x$ квантора быть не должно). $x \in x$ такой формулой является.

[alex55555]

mihaild в сообщении #1380194 писал(а):

Какие "внутренние связи" и что это вообще такое?

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

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

mihaild в сообщении #1380194 писал(а):

В неограниченной аксиоме выделения $P(x)$ должно быть формулой с одной свободной переменной $x$ (т.е. все остальные переменные должны стоять под кванторами, а по $x$ квантора быть не должно). $x \in x$ такой формулой является.

А как это относится к рассматриваемому случаю?

[mihaild]

alex55555 в сообщении #1380247 писал(а):

А как это относится к рассматриваемому случаю?

Ну раз это непонятно - напишите подробнее формально, как вы понимаете парадокс Рассела.

[Someone]

alex55555 в сообщении #1380247 писал(а):

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

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

[arseniiv]

alex55555 в сообщении #1380189 писал(а):

Пусть $x + y^2 - x^2 = z$, после замены $y^2 - x^2$ на $u$ имеем - $x + u = z$. Далее имеем право заменить $x$ на что-то другое, ну и заменяем его на $u$, получаем - $ u + u = z$. Далее раскрываем - $y^2 - x^2 + y^2 - x^2 = z$.

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

[george66]

Там есть ограничение "$Y$ не должно входить в $P(x)$ в качестве свободной переменной". Вопрос правильный, но зелёные палки ни при чём. В "контрпримере" $x$ входит в формулу два раза, вместо одного подставляете, а вместо второго нет, от этого ошибка.

[alex55555]

mihaild в сообщении #1380262 писал(а):

напишите подробнее формально, как вы понимаете парадокс Рассела.

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

-- 07.03.2019, 16:17 --

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

В теории множеств нет зелёных палок. Это ведь не теория зелёных палок, а теория множеств. В ней есть только множества.

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

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

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

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

-- 07.03.2019, 16:19 --

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

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

В рассматриваемом выражении ясно указано - икс входит в игрек, но замены икса в игреке никто не делает, значит они нарушают законы логики (по вашем определению).

-- 07.03.2019, 16:22 --

george66 в сообщении #1380330 писал(а):

В "контрпримере" $x$ входит в формулу два раза, вместо одного подставляете, а вместо второго нет, от этого ошибка.

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

[mihaild]

alex55555 в сообщении #1380389 писал(а):

Так я его как раз не понимаю.

Ну тогда берите стандартную формализацию.
У нас есть неограниченная схема аксиом выделения: для любой формулы $P(x)$, в которую $x$ входит свободно, и никакие другие переменные свободно не входят (т.е. нет кванторов по $x$, а все остальные встречающиеся в формуле переменные стоят под кванторами) формула $\exists Y \forall x: (x \in Y \leftrightarrow P(x))$ является аксиомой. Возьмем в качестве $P(x)$ формулу $x \in x$. Получаем аксиому $\exists Y: \forall x (x \in Y \leftrightarrow x \in x)$. Что-то непонятно на этом этапе или дальше?

alex55555 в сообщении #1380389 писал(а):

Как понимать теорию множеств без элементов?

В теории множеств элементами множеств являются множества. И никакого понятия "делимости" тут нет.

alex55555 в сообщении #1380389 писал(а):

Но точно так же икс входит и в игрек

В схеме аксиом выделения $x$ и $Y$ - это переменные. Переменные не могут входить или не входить друг в друга.

[arseniiv]

alex55555 в сообщении #1380389 писал(а):

Как понимать теорию множеств без элементов?

Как уже написали, всем как правило хватает теории множеств, где нет каких-то отдельных «первоэлементов» (urelement). Хотя существуют теории и с первоэлементами, ничего существенно нового они не дают, а сложность вносят: во-первых, усложняется язык и аксиомы, потому что состав множеств теперь гетерогенный; потом если мы хотим, чтобы можно было говорить о каких-то определённых свойствах первоэлементов, надо будет добавлять в теорию множеств аксиомы об этом (например если мы хотим, чтобы первоэлементы были натуральными числами, надо будет добавить какие-то аксиомы арифметики, аккуратно модифицированные под такой язык). И тому подобное.

По тем же причинам в распространённые (в первую очередь ZF) теории множеств не входит упорядоченная пара как примиивная конструкция — опять же выразительности теории, говорящей только о множествах, оказывается достаточным, чтобы выражать нужное.

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

[alex55555]

mihaild в сообщении #1380390 писал(а):

Ну тогда берите стандартную формализацию.
У нас есть неограниченная схема аксиом выделения: для любой формулы $P(x)$, в которую $x$ входит свободно, и никакие другие переменные свободно не входят (т.е. нет кванторов по $x$, а все остальные встречающиеся в формуле переменные стоят под кванторами) формула $\exists Y \forall x: (x \in Y \leftrightarrow P(x))$ является аксиомой. Возьмем в качестве $P(x)$ формулу $x \in x$. Получаем аксиому $\exists Y: \forall x (x \in Y \leftrightarrow x \in x)$. Что-то непонятно на этом этапе или дальше?

Здесь всё понятно. Сама подмена $P(x)$ на выражение есть очень привычная замена переменной на её значение (хоть и расширенная необходимостью следить за "судьбой" ещё и передающегося в функцию параметра), поэтому здесь претензий нет. Но дальше начинаются проблемы.

Вот вы сказали:

mihaild в сообщении #1380390 писал(а):

В схеме аксиом выделения $x$ и $Y$ - это переменные. Переменные не могут входить или не входить друг в друга.

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

-- 07.03.2019, 19:47 --

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

Как уже написали, всем как правило хватает теории множеств, где нет каких-то отдельных «первоэлементов» (urelement).

В принципе понятно. Видимо я этот момент упустил в Куратовском, надо будет начало перечитать именно на предмет проверки как он там это дело подаёт.

[iifat]

alex55555 в сообщении #1380189 писал(а):

Похожий пример:

Имхо, таки не похожий. Если сильно интересно, попробуйте записать явно, с кванторами и доказательствами — сами увидите.

[mihaild]

Не путайте переменные и обозначаемые ими объекты. Зафиксируем $Y$ (чтобы лишний квантор не мешался) - получили что верна формула $\forall x: (x \in Y \leftrightarrow x \notin x)$.
Формально, в исчислении высказываний есть схема аксиом: $\forall x: P(x) \rightarrow P(t)$, где $P$ - формула, а $t$ - терм, не содержащий переменных, по которым в $P$ есть кванторы. Подставим в эту схему $t = Y$, $P(x) = x \in Y \leftrightarrow x \notin x$. Получим $\forall x: (x \in Y \leftrightarrow x \notin x) \rigtharrow (Y \in Y \leftrightarrow Y \notin Y)$. Ну и т.к. левая часть импликации у нас уже есть, выводим отсюда $Y \in Y \leftrightarrow Y \notin Y$.

Неформально, мы знаем, что для любого $x$ выполнено некоторое свойство. Ну раз выполнено для любого - то в частности выполнено и для $Y$.

Если следить за порядком кванторов, то дополнительно помнить "что от чего зависит" уже не нужно (правда даже в хороших курсах по например мат. анализу за порядком кванторов следить не любит, что порождает монстров вида "существует $\delta$ зависящее только от $\varepsilon$").

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

[arseniiv]

alex55555 в сообщении #1380427 писал(а):

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

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

alex55555 в сообщении #1380427 писал(а):

Так же как в обычном уравнении некий икс может входить во вложенные выражения (например - выделенные скобками)

Ну и ничего особенного и здесь из такого не следует.

[Someone]

alex55555 в сообщении #1380427 писал(а):

Сама подмена $P(x)$ на выражение есть очень привычная замена переменной на её значение

Речь идёт о схеме аксиом, то есть, о способе записи бесконечного множества аксиом. Здесь для каждой высказывательной функции $P(x)$ определяется своя аксиома. Схема аксиом формулируется не в языке предметной теории (здесь — теории множеств), а в метаязыке, в котором определяется язык предметной теории (чаще всего это просто естественный язык). Поэтому к предметной теории эти замены отношения не имеют.

alex55555 в сообщении #1380389 писал(а):

Да, конечно, но сам логический вывод имеет место быть и для палок

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

alex55555 в сообщении #1380389 писал(а):

Вообще в изложении того же Куратовского и Мостовского фигурируют два понятия - элемент и множество.

Тяжёлый случай. Я не понимаю, как можно было вычитать такое в тексте данной книги. Фраза "$x$ является элементом множества $y$" является словесной записью формулы $x\in y$, то есть, слово "элемент" — это ссылка на символ "$\in$" в формуле. Теория, излагаемая в книге Куратовского и Мостовского — это ZFC минус аксиома регулярности и плюс аксиома реляционных типов. В ней нет никаких "элементов", кроме множеств.

alex55555 в сообщении #1380427 писал(а):

в выражении указано обязательное условие - икс принадлежит игрек

Нет там никакого "обязательного условия". В этом месте доказательства происходит консервативное расширение языка теории множеств: вводится постоянная "$Y$", и для этой постоянной формулируется аксиома

$$\forall x(x\in Y\Leftrightarrow x\notin x),$$

которая служит определением множества $Y$ (словами: произвольно взятое множество $x$ является элементом множества $Y$ тогда и только тогда, когда $x$ является элементом самого себя). Сокращённо это записывается как

$$Y=\{x:x\notin x\}$$

(словами: $Y$ — множество всех таких множеств, каждое из которых является элементом самого себя). Делается это просто для удобства. В свою очередь, запись аксиомы также является сокращением, а полная запись может выглядеть, например, так:

$$\forall x(((x\in Y)\Rightarrow\neg(x\in x))\wedge(\neg(x\in x)\Rightarrow (x\in Y))).$$

alex55555 в сообщении #1380389 писал(а):

В рассматриваемом выражении ясно указано - икс входит в игрек

alex55555 в сообщении #1380389 писал(а):

Но точно так же икс входит и в игрек.

Это какое-то недоразумение. "$Y$" и "$x$" — это просто символы. Они "входить" друг в друга не могут. В данном случае они используются как имена некоторых множеств (постоянная "$Y$" является именем некоторого вполне определённого множества, а переменная $x$ — именем произвольно взятого множества).

Вы явно перепутали два совершенно разных понятия: «буква "$x$" входит в формулу $\Phi$» (это означает, что если мы посмотрим на запись формулы, например, "$z=x+y^2-x^2$", то в этой записи найдём букву "$x$") и «число $x$ входит в число $z$» (никакое число ни в какое другое не входит; не надо придумывать какой-нибудь специальный смысл для этого "входит"; множества тоже не "входят" друг в друга).