Задача из учебн. Куратовского, Мостовского "Теория множеств"

[realeugene]

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

И так далее, пока не перестанут появляться новые множества.

Это и есть математическая индукция. Когда новые множества перестали появляться, шаг индукции состоит в том, что они не появляются, следовательно, раз среди них нет (и никогда не было) объединения для более коротких выражений, объединение не появится никогда. И индукция должна проводиться по длине выражения, так как длина выражений аргументов короче длины полного выражения. Если бы это было не так (из-за какой-нибудь хитрости с рекурсивными функциями), то всё стало бы грустно.

[Someone]

realeugene в сообщении #1239289 писал(а):

Это и есть математическая индукция.

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

В общем, не пугайте 3dmnozhestvotochek, он только-только начал изучать теорию множеств.

[3dmnozhestvotochek]

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

realeugene в сообщении #1239165 писал(а):

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

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

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

Задача состоит в том, чтобы выразить одну операцию через две другие. Использовать в выражении ту операцию, которую нужно выразить, нельзя по смыслу задачи. Разрешены только те операции, которые указаны в условии задачи. И никакие аксиомы тут ни при чём. Они могут использоваться только при обосновании решения.

-- Вт авг 08, 2017 21:24:08 --

realeugene в сообщении #1239228 писал(а):

Если вы не знаете, что такое "математическая индукция", боюсь, доказательства вам даже для подобных задач недоступны.

Не нужна тут никакая математическая индукция.

Спасибо Вам, Someone, что Вы разобрались в самой задаче из учебника!

Вот именно - надо дать определение одного понятия через два других, а не через одно из двух. Я тоже думаю, что это важное замечание.

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

-- 08.08.2017, 23:21 --

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

3dmnozhestvotochek, думаю, никто не будет против, если я напишу решение похожей задачи.
Можно ли выразить $\setminus$ через $\cap$ и $\cup$?
Ответ: нельзя.
Доказательство: докажем, что любое множество, которое можно получить из $A$ и $B$ с помощью $\cap$ и $\cup$ содержит все элементы, содержащиеся в $A \cap B$.
Будем доказывать индукцией по числу операций в выражении.
База: $0$ операций - наше выражение либо $A$ либо $B$, для него утверждение выполнено.
Шаг: пусть нельзя выразить формулой, содержащей меньше чем $n$ операций. Рассмотрим какую-нибудь формулу, содержащую $n$ операций. Последняя (внешняя) операция - либо $\cap$, либо $\cup$. Если это $\cap$, то формула имеет вид $X \cap Y$, где $X$ и $Y$ получены из $A$ и $B$ с помощью менее чем $n$ операций. Следовательно, $X$ и $Y$ содержат $A \cap B$ как подмножество, и то же выполнено для $X \ cap Y$. Аналогично для формулы $X \cup Y$.
Рассмотрим теперь $A = B = \{\varnothing\}$. Тогда $A \cap B \nsubset A \setminus B$. Следовательно, выразить $A \setminus B$ с помощью $\cap$ и $\cup$ нельзя.

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

Не нужна тут никакая математическая индукция.

Если расписывать строго, то индукция по длине формулы / числу операций нужна.

Спасибо, спасибо, спасибо! Это очень интересно!
Мне очень приятно пообщаться с человеком, который разбирается в этой области. И по теме. Разбираю Ваш пример.
Куратовскому было бы, наверное, приятно... если он не был зануда.

-- 08.08.2017, 23:26 --

В принципе, задача Куратовского практически решена! Если не полностью, то уже практически полностью.
Спасибо!

[popolznev]

(Оффтоп)

3dmnozhestvotochek в сообщении #1239321 писал(а):

В принципе, задача Куратовского практически решена!

А вдруг это задача Мостовского.

[realeugene]

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

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

Тут, всё же, ПРР(М), а не ПРР(Ф). Учебник, кстати, серьёзный, немного не школьного уровня. Это была задача номер 2 из второго параграфа. В первом параграфе задач нет. Её, конечно, можно решать нестрого и рисованием диаграмм на бумажке, но без умения строить сложные индуктивные доказательства дальнейшие параграфы не прогрызть, как мне кажется.

[realeugene]

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

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

Кстати, если определить $M$ как произвольное надмножество обоих множеств (которое существует хотя бы одно в силу аксиоматики теории множеств), то этот цикл разрывается. Надмножество может быть найти гораздо проще, чем объединение, тем более, что заданное априорно "универсальное множество" (в некотором смысле) используется во многих структурах, построенных на основе теории множеств. (Disclaim: я, конечно, прекрасно понимаю, что хотели авторы задачи учебника, но не заглянуть в более глубокий её слой было бы скучно).

[Someone]

realeugene в сообщении #1239446 писал(а):

Кстати, если определить $M$ как произвольное надмножество обоих множеств

О, боже!… Вы обязаны выразить это "надмножество", используя только множества $A$ и $B$ и операции $\cap$ и $\setminus$. Смысл задачи именно в этом.

realeugene в сообщении #1239379 писал(а):

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

Индукция по натуральным числам — в главе III. Трансфинитная индукция — в главе VII. Успокойтесь, ради бога, и не пихайте индукцию туда, где она не нужна.

[mihaild]

(Оффтоп)

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

Индукция по натуральным числам — в главе III

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

[Someone]

Да нет в теории множеств индукции по длине формулы. Такие "индукции" относятся к метаматематике.

Мы убеждаемся, что заданные операции не позволяют расширить полученное семейство множеств, и всё. Нет никакой нужды использовать индукцию.

[realeugene]

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

Такие "индукции" относятся к метаматематике.

Вся задача относится к метаматематике. Потому что в теории множеств и "выражений" точно так же нет.

-- 09.08.2017, 22:43 --

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

и всё

Не доказано.

[Someone]

realeugene в сообщении #1239558 писал(а):

Вся задача относится к метаматематике.

Только метаматематики в самом начале учебника не хватало. Это задача из теории множеств.

Это что, коллективный троллинг? Я устраняюсь.

[realeugene]

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

Только метаматематики в самом начале учебника не хватало. Это задача из теории множеств.

Сможете формализовать её утверждение в логике первого порядка?

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

Это что, коллективный троллинг?

Нет.

[Someone]

realeugene в сообщении #1239562 писал(а):

Сможете формализовать её утверждение в логике первого порядка?

Пусть $\Phi(A,B,x)$ есть формула

$$A\in x\wedge B\in x\wedge\forall y\forall z((y\in x\wedge z\in x)\Longrightarrow(y\cap z\in x\wedge y\setminus z\in x)).$$

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

$$(\Phi(A,B,C)\wedge\forall D(\Phi(A,B,D)\Longrightarrow C\subseteq D))\Longrightarrow\neg(A\cup B\in C).$$

(Все латинские буквы обозначают множества независимо от шрифта.)

[realeugene]

Хорошо. Спасибо.
Прежде всего, ваше доказываемое предложение некорректно записано. В нём присутствуют свободные символы. Если позволите, я вашу запись поправлю и немного нормализую, для ясности:

$$\Phi(A,B,x):= \forall y\forall z \; A\in x\wedge B\in x\wedge((y\in x\wedge z\in x)\Longrightarrow(y\cap z\in x\wedge y\setminus z\in x))$$

$$\forall A \forall B \forall D \; (\Phi(A,B,C)\wedge(\Phi(A,B,D)\Longrightarrow C\subseteq D))\Longrightarrow\neg(A\cup B\in C)$$

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

Это именно то, что вы хотели записать? Ваша мысль мне всё ещё не понятна. Например, легко заметить, что из первой формулы можно легко вынести предикат относительно $x$, не зависящий от $A$ и $B$. Это именно то, что вы хотели записать?

Но самое главное, что мне не понятно. В исходной задаче спрашивалось про существование или несуществование выражения. А где у вас в предложении это выражение?

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

[Someone]

realeugene в сообщении #1239573 писал(а):

Прежде всего, ваше доказываемое предложение некорректно записано. В нём присутствуют свободные символы.

Свободные переменные по умолчанию интерпретируются с квантором "$\forall$", написанным перед началом формулы. Но неточность действительно есть. Нужны некоторые условия на $A$ и $B$, о которых я писал ранее.

Пусть $\Phi(A,B,x)$ есть формула

$$A\in x\wedge B\in x\wedge\forall y\forall z((y\in x\wedge z\in x)\Longrightarrow(y\cap z\in x\wedge y\setminus z\in x)).$$

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

$$(\neg(A\subseteq B)\wedge\neg(B\subseteq A)\wedge\Phi(A,B,C)\wedge\forall D(\Phi(A,B,D)\Longrightarrow C\subseteq D))\Longrightarrow\neg(A\cup B\in C).$$

realeugene в сообщении #1239573 писал(а):

я вашу запись поправлю и немного нормализую, для ясности

Обойдётесь. Не разрешаю ничего переставлять.

realeugene в сообщении #1239573 писал(а):

Это именно то, что вы хотели записать?

Я хотел написать то, что написал. Но не то, что написали Вы.

realeugene в сообщении #1239573 писал(а):

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

Разумеется, неформальное. Но вряд ли с помощью двух овалов.

realeugene в сообщении #1239573 писал(а):

Но самое главное, что мне не понятно. В исходной задаче спрашивалось про существование или несуществование выражения. А где у вас в предложении это выражение?

Поищите.

realeugene в сообщении #1239573 писал(а):

Но мы сейчас обсуждаем строгое доказательство.

Если Вы имеете в виду формальное доказательство, то это без меня. Я себе более интересное занятие найду. Например, "Косынку" разложу.