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

[3dmnozhestvotochek]

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

просто явно выписать все множества, которые можно получить данными операциями (их не так много).

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

Построить контрпример. Возьмите для $A$ и $B$ в качестве возможных значений множество подмножеств множества $\left\{ 1 \right\}$, постройте функции в виде таблиц для всех возможных сочетаний операций и покажите, что среди этих таблиц нет таблицы, соответствующей таблице объединения ваших множеств.

Не понимаю, как это делается. Можно объяснить, пожалуйста?

[realeugene]

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

Не понимаю, как это делается. Можно объяснить, пожалуйста?

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

Шаг 1. Что вообще такое "определить одну операцию через другие"? Можете написать своё определение этого понятия?

[3dmnozhestvotochek]

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

"определить одну операцию через другие"

Да, вот то как я себе представляю это. Я думаю, что это значит в правой части равенства поставить одну операцию между множествами А и В(например $А\cupВ$), а в левой части - сколько угодно разрешённых условием задачи операций между А и В, любым образом и в любом порядке. А и В можно записывать сколько угодно раз. Вот, как-то так.

[realeugene]

Нет, не так. Выражение - это конечная строка символов с определённым смыслом (и определённой грамматикой). В данном случае, смысл вашему выражению задаётся правилами построения логических выражений и аксиоматикой теории множеств. И из этого всего богатства вам нужно только правила построения термов. Ваше выражение - это терм, который построен только из двух ваших заданных функций, двух символов переменных - аргументов, и одной константы - пустого множества. Впрочем, пустое множество вам не нужно, так как его всегда можно получить, пользуясь выражением $\emptyset = a \setminus a$. Обратите внимание, что термы строятся по индукции (точнее, рекурсивно), следовательно, во-первых, в вашем конечном выражении будет конечное число вхождений каждой функции, и, кроме того, индукция при построении термов намекает на использование индукции при построении опровержения.

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

[3dmnozhestvotochek]

Частично понял, но с такими вещами не знаком. Я такого не учил. А Вы не могли бы на форуме выложить решение (или ссылку дать на документ) с этим способом, хотя бы 1-й половины задачи (про А$\cup$В)? - Не для меня - просто если кто не понимает, то чтобы смогли посмотреть.

[realeugene]

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

А Вы не могли бы на форуме выложить решение (или ссылку дать на документ) с этим способом.

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

[3dmnozhestvotochek]

Я знаю, что такое "математическая индукция" - Вы то что у Вас в голове, запишите.

[realeugene]

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

Вы то что у Вас в голове, запишите.

Без обратной связи мне это не интересно.

[3dmnozhestvotochek]

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

[realeugene]

Кроме того, в ПРР запрещено публиковать готовые решения. В общем, нет, не ко мне.

[3dmnozhestvotochek]

Всё! Решение для меня понятно!
Спасибо большое Someone, provincialka и mihaild за содержательные комментарии.

[Someone]

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

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

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

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

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

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

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

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

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

[realeugene]

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

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

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

[mihaild]

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 писал(а):

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

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

[Someone]

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

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

Нафиг мне его доказывать?

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

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

Начинаем с двух множеств $A$ и $B$, о которых предполагаем, что $A\cap B\neq\varnothing$, $A\setminus B\neq\varnothing$ и $B\setminus A\neq\varnothing$. Выписываем множества, которые можно получить, применяя к всевозможным упорядоченным парам имеющихся множеств разрешённые операции. Получатся ещё $4$ различных множества, и всего в нашем распоряжении будет $6$ различных множеств. Но $A\cup B$ среди них нет. С этими шестью множествами поступаем так же, как с исходными двумя. И так далее, пока не перестанут появляться новые множества. В результате выяснится, что объединение никак не получается.