Доказать ассоциативность симметрической разности

Доказать ассоциативность симметрической разности

1. Разности:

A B = A (A B) и A (B C)=(A B) (A C).

Важно.

Операция разности определяется только для двух множеств. Эта операция двухместная и не коммутативная: .

2. Свойство симметрической разности:

.

Доказательство.

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

Пусть , что по определению симметрической разности означает, что x (AB) (B A). Здесь возможны два варианта: либо x (A B), либо x (B A). В первом случае мы получаем: x (A B) (x A и x B) (x A B и x A B), откуда очевидно следует, что x . Ситуация, когда x (B A), рассматривается аналогично.

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

Пусть x (x A B и x A B). Здесь возможны две ситуации: либо и , либо и . Рассмотрим первый случай: пусть и , . Откуда .Второй случай доказывается аналогично.

Важно.

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

Определение 5.

Множество U, такое, что все рассматриваемые множества являются его подмножествами, называется универсальным.

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

Множества <звездные скопления>, <черные дыры>, <планеты>являются подмножествами универсального множества <вселенная>.

Определение 6.

Множество U A называется дополнением множества A (до универсального множества) и обозначается через .

На кругах Эйлера это определение представлено на рис. 5.

Принцип двойственности

Теорема двойственности

Теорема 1 (двойственности или де-Моргана).

Пусть Ak, k = 1. n – некоторые подмножества универсального множества U, тогда имеют место следующие равенства:

; . (5)

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

Доказательство.

.

Заметим, что в приведенном доказательстве все утверждения об элементе x соединены знаками , что позволяет одновременно строить доказательство утверждения в обе стороны.

Определим следующие множества: A – множество четных натуральных чисел; B – множество нечетных натуральных чисел; C – множество натуральных чисел, не больше 10. В качестве универсального множества мы будем рассматривать множество натуральных чисел N. Наша задача состоит в том, чтобы описать следующие множества:

.

это множество нечетных натуральных чисел, т.е. множество B.

2. Каждое натуральное число является либо четным, либо нечетным, поэтому = .

3. = . Следовательно, = N.

4. A C = < четные натуральные числа 10> = <2, 4, 6, 8, 10>.

Базис операций

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

1. .

2. .

3. .

Определение 7.

Операции < , , > называются булевыми операциями над множествами.

Разностью множеств А – В называется множество всех тех и только тех элементов А, которые не содержатся в В. Или, что есть то же самое, А — В = <х: х принадлежит А и х не принадлежит В>.

В не может быть подмножеством А.

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

Докажежем отсутсвие ассоциативности. Покажем, что (А-В)-С не равно А-(В-С). Множество, стоящее в левой части, состоит из элементов множества А, не являющизся при этом элементами ни множества В, ни множества С, т.е. совпадает со множеством А-(В U C) Множество, стоящее в правой части, состоит из элементов множества А, не являющихся при этом элементами множества В, но при этом элементы, являющиеся пересечением множеств А,В и С, входят в это множество, т.е. это множество совпадает со множетсвом А-ВU(A&B&C) .

5.Симметрическая разность, определения и свойства.

Симметрической разностью двух множеств A и B называется сумма разностей A -B и

B — A .

Это обозначается как C = A /_ B.

Заметим, что A/_ B = (A UB) (B U A), т.к. симметричная разность состоит из тех элементов множеств A и B, которые не принадлежат A и B одновременно. Результатом является множество элементов этих множеств, принадлежащих только одному из них. Увидим, что А /_ B=(AUB)-(A&B), так как симметрическая разность состоит из тех элементов А и В, которые не принадлежат А иВ одновременно.

Доказательство: ⇒ АΔВ⊂(А∪В)(А∩В), ∀x, x∈(АВ)∪(ВА) → x∈AB или х∈ВА → (х∈А и х∉В) или (х∈В и х∉А) → 1) х∈А и х∉А∩В, 2) х∈В и х∉А∩В → х∈(А∪В)(А∩В); в обратную сторону доказывается аналогично.

Заметим, что эта операция является и коммутативной и ассоциативной.

Не знаю, что тут ещё можно написать!

6.Операция дополнения множеств, принцип двойственности.

Дополнение множества А, обозначаемое А’ — это множество элементов универсума, которые не принадлежат А. Следовательно,

Если основное множество обозначить за S, то дополнением множества A называется разность S A (рис. 8). Это обозначается как CA или A с чертой сверху.

Pис. 8 Дополнение множества А

Пример. Если в качестве основного множества S рассмотреть множество всех целых чисел, а в качестве A множество четных чисел, то дополнением множества A будет множество нечетных чисел.

Сформулируем принцип двойственности.

1) дополнение объединения двух множеств равно пересечению дополнений этих множеств:

Не (A UΒ) = (не А) & (не В)

2) дополнение пересечения двух множеств равно объединению дополнений этих множеств:

Не (А & В) = (не А) U(не В)

Докажем равенство (1).

Пусть (x принадлежит (не (А UВ)), т.е. (х не принадлежит (АUB)), таким образом, х не принадлежит ни множеству А, ни множеству В, следовательно (х принадлежит (не А)) и (х принадлежит (не В)), что и означает что (х принадлежит (не А) & (не В)). И так мы доказали.

Читайте также:  Pcm или bitstream телевизор самсунг

Архив

Ещё один пример из теории множеств

Формулировка

В одном из предыдущих постов я выбрал некоторые задачки для того, чтобы на их решениях проиллюстрировать, как работать с Мицаром. Сегодня мы возьмём задачку, где требуется доказать следующую цепочку эквивалентностей:

где — симметрическая разность множеств.

Наброски обычного доказательства

Эквивалентность трёх утверждений доказывается классической цепочкой импликаций

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

Дальше идёт в ход мантра «циклическая перестановка переменных».

Доказательство на Мицар

Что было использовано в ходе «обычного» доказательства? Коммутативность и ассоциативность симметрической разности, то, что пустое множество для неё играет роль, аналогичную нулю при сложении, а также то, что симметрическая разность множества с самим собой есть пустое. Статья XBOOLE_1 содержит доказательства того, что (X + X = <>, теорема 92) и ассоциативность симметрической разности (теорема 91).

Что касается коммутативности симметрической разности, то если приглядеться к её определению, то можно заметить в нём ключевое слово commutativity. Это одно из возможных так называемых свойств (properties), о которых говорится в статье Наумовича и Былинского Improving MIZAR Texts with Properties and Requirements. Суть свойств в том, что будучи однажды доказаны для какой-либо операции (отношения), они могут применяться в дальнейшем без ссылок на определение, то есть, например, утверждение вроде X + Y = Y + X будет принято при проверке статьи на Мицаре без доказательства. К сожалению, пока из свойств бинарных операций реализованы только коммутативность и идемпотентность, поэтому на доказательство ассоциативности придётся ссылаться явно.

Второе усовершенствование — так называемые требования (requirements), рассматриваемые в вышеуказанной статье, аналогичны свойствам в том смысле, что позволяют на этапе проверки принимать какие-то вещи без доказательств при подключенных требованиях. Подключаются требования в разделе environ директивой requirements. Каждое из существующих сейчас в Мицар требований соответствует одноимённой статье в MML, все теоремы в которой понимаются без ссылок. Также некоторые требования существенно обогащают возможности языка Мицар. Нас сегодня будет интересовать требование BOOLE. Легко видеть, что в статье BOOLE содержится ряд различных тождеств, в частности то, что пустое множество играет для симметрической разности ту же роль, что и ноль для сложения.

Теперь можно привести текст статьи, в которой и производится доказательство нашего нашей незамысловатой цепочки эквивалентностей.

Комментарий к доказательству

Используются словарь XBOOLE_0, где хранятся символы для пустого множества и симметрической разности, конструкторы и нотации из XBOOLE_0 для этих символов (а также коммутативность симметрической разноси из определения), теоремы 91 и 92 из статьи XBOOLE_1 и требования BOOLE (последний шаг доказательства, <> + A = A).

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

Новой конструкцией являются доказательства цепочкой равенств с помощью символа .= — надеюсь, интуитивно понятно, как им пользоваться.

Пример доказательства теоретико-множественного тождесва

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

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

Мы используем здесь два остова доказательства: для квантора общности и эквивалентности. Легко заметить, что в блоке hereby и в блоке утверждений, следующем сразу после него, предложения расположены одни и те же, просто в обратном порядке. Ссылки на определения расположены также в обратном порядке. По сути, такое доказательство можно было бы вообще сгенерировать автоматически. Это и неудивительно, потому что сложно представить себе что-то более тривиальное и безыдейное, чем доказательство этого и аналогичных теоретико-множественных тождеств.

Остовы доказательств в Мицар

Остовы доказательств (proof skeletons) играют роль своего рода мантр в Мицар. По сути это некоторые фразы, которые приговариваются в процессе доказательства для пущей убедительности. Я долго пытался понять их логику, но пришёл к выводу, что скорее их нужно запомнить, благо их немного. В любом случае, их можно сгенерировать автоматически.

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

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

В этом посте опять же шапка будет общей для всех примеров. Далее, есть остов для доказательств отрицания (приведением к абсурду):

Здесь вместо ключевого слова thesis используется ключевое слово contradiction, обозначающее тождественную ложь. not contradiction, соответственно, является тождественной истиной, в частности, можно написать примерно следующее

Также есть остов доказательства для конъюкции (пример бессодержательный, иллюстрирующий только сам остов)

Остов для эквивалентности

использует ключевое слово hereby, которое выполняет функции одновременно thus и now (то есть в качестве утверждения после ключевого слова thus выступает целый блок nowend;)

Читайте также:  Вычитание в пятеричной системе счисления

На основе остова для импликации и правил классической логики можно получить остов для дизъюнкции

Есть также остовы для квантифицированных предложений. Простой для всеобщности:

И несколько более сложный (по смыслу) для существования:

В случае доказательства существования предложение, начинающееся с ключевого слова set, не входит в остов доказательства. Оно нужно просто для того, чтобы указать, какое именно x имеется в виду в предложении take x; Вообще, ключевое слово set может быть использовано для введения новых переменных и по сути мало чем отличается от оператора присвоения в обычных языках программирования. О ключевом слове set и разными вещами, с ним связанными, поговорим в следующем посте.

Структура доказательства в Мицар

Общий вид формализованного доказательства

Я помню, как на первом курсе пробовал читать «Элементы теории множеств»་ Николя Бурбаки. Там я и познакомился с первым в своей жизни понятием формализованного доказательства. (Да, я затеял написать этот пост после неудачной попытки описать доказательство одного теоретико-множественного тождества.) По сути, оно сводилось к следующему: формализованное доказательство — это последовательность утверждений (по одному на каждой строке, например) таких, что либо утверждение есть аксиома, либо оно выводимо по определённому правилу из одного или нескольких предыдущих. Фактически то же самое можно сказать и о доказательствах в Мицар. Разница состоит лишь в том, что утверждение может начинаться с метки, например

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

(Все дальнейшие примеры кода на Мицаре можно вставлять просто ниже этого текста — «шапку» менять не придётся. Все они прошли проверку на версии Мицар 7.12.01 и MML версии 4.166.1132.) В принципе, здесь может быть не три строчки, а три тысячи, все в одном и том же стиле, едва ли удобном для прочтения человеком.

Первое усовершенствование

В математических рассуждениях часто ссылают на только что доказанные утверждения или только что сделанные предположения (это делается обычно со словами «следовательно», «тогда» или похожими). В Мицар тоже, если нужно сослаться на непосредственно предшествующее утверждение, нет нужды даже давать ему метку, а можно использовать ключевое слово then. В частности, первые две строчки из предыдущего примера можно заменить на

Означает это ровно то же самое, но чуть более человекочитаемо.

Сначала доказательство, а формулировка… А кому-то ещё непонятна формулировка?

Часто бывает, что в математическом тексте утверждения доказываются походя. Просто что-то предполагается, а потом из этих предположений что-то вытекает. Иногда ввиду простоты утверждения совершенно неважно выделять его формулировку в виде классического «Если A, то B». В Мицар такое тоже бывает. Для этого используются операторные скобки nowend; Между этих скобок вообще можно ничего не писать:

либо сделать какой-нибудь вывод, используя ключевое слово thus:

либо ввести какое-нибудь предположение с использованием ключевого слова assume:

Ну и, наконец, можно сделать предположение, а на его основе всё-таки уж что-нибудь да и доказать:

В данном примере уместно спросить, а нельзя ли написать then thus, чтобы избавиться от необходимости ссылаться на метку B? Можно, конечно, но только вместо двух ключевых слов подряд необходимо использовать одно — hence. Тогда этот же пример перепишется следующим образом:

Стандартный формат лемм

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

В предыдущем параграфе мы нещадно эксплуатировали одно и то же доказательство одного и того же утверждения, вытекающего из аксиомы фундирования (или аксиомы регулярности, если угодно). Только что мы его же переписали, но с использованием других ключевых слов. Здесь есть знакомые уже нам assume и thus. Важно помнить, что точка с запятой после формулировки леммы не ставится. Конечно же, здесь есть место и слову hence:

Более того, какая же классическая лемма без триумфальных «ч. т. д.» или QED? В Мицаре есть некоторый аналог. Вместо того, чтобы писать формулировку леммы, можно просто использовать ключевое слово thesis:

Чем лемма отличается от теоремы?

На этот волнующий всех школьников вопрос в Мицаре даётся вполне прозаический ответ: теорема — это утверждение, перед которым написано ключевое слово theorem. Ключевое слово это нужно, однако, не для красоты, а для того, чтобы выделить те утверждения, которые будут доступны для ссылок извне статьи. Ссылка TARSKI:1 — это ссылка точно на самое первое утверждение в статье с именем TARSKI, которое помечено ключевым словом theorem. TARSKI:10 — соответственно, на десятое такое утверждение в порядке их следования в тексте статьи. Мы тоже можем сделать две теоремы, на которые благодарные потомки, возможно, будут ссылаться как на HELLO:1 и HELLO:2

Как жить дальше?

Дальше нужно составить некоторое представление об остовах доказательств, то есть о том, чем, собственно, заполнять пространство между словами proof и end; кроме бесконечных цепочек ссылающихся друг на друга утверждений. Об этом — следующий пост.

Теория множеств для первокурсников в Мицар

Источник задачек

Подумав, как лучше продолжить рассказ о Мицаре, я решил привести на нём решения некоторых тривиальных задач, которые изначально предназначались для решения людьми. В качестве таковых были выбраны задачки, предлагавшиеся в 2010 году первокурсникам бакалавриата факультета математики ГУ ВШЭ.

Читайте также:  Дом ру код ошибки 2 интернет

Как вообще на ЭТОМ (!) можно писать.

Итак, хотелось бы доказать несложное тождество . Проблема номер один: совершенно непонятно, как в Мицар обозначаются теоретико-множественные операции. На самом деле, это не такая уж проблема. Как вариант, можно поискать в аннотациях журнальных статей нужные нам вещи. По слову «operation» легко находим статью Properties of Subsets, в которой обещают «The text includes theorems concerning properties of subsets, and some operations
on sets.» В тексте статьи обнаруживаем знакомые символы (объединение, пересечение, дополнение) между пунктами 10 и 11. Теперь открываем ту же статью на Мицаре. В ней после метки Th10 : действительно обнаруживаем определения базовых операций. На самом деле, это переопределения. Там же есть пометка :: original: / — если перейти по этой ссылке, то откроется как раз та статья, которую мы ищем. Несложно догадаться, что / — это . Если взглянуть на определение, то это становится совсем понятно:

let X , Y be set ;
func X / Y -> set means : Def3 : :: XBOOLE_0:def 3
for x being set holds ( x in it iff ( x in X or x in Y ) );

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

Почему ничего не компилируется.

Конечно же, статья

хороша всем, кроме ошибки 203. Для того, чтобы Мицар правильно понял какое-то слово, он должен знать две вещи: какой набор символов составляет это слово и какой смысл в него вкладывается. Те слова, которые Мицар в принципе может понимать, хранятся в специальных файлах с расширением voc (от vocabulary). Файлы voc для текущей статьи должны лежать в папке dict (файлы miz лежат в папке text). Файл voc по сути — это просто перечисление слов, их типов (оператор, функциональный символ и прочее) и чисел, задающих порядок предшествования операторов. Одни и те же слова могут использоваться в разных значениях (возможна перегрузка операторов и не только), поэтому словарь — это словарь, а статья — это статья. Сам по себе механизм довольно архаичен, потому что, возможно, какие-то символы могут полностью менять своё значние (например, / для деления и факторизации по подпространству), но он есть и, так или иначе, как-то надо им пользоваться. Для этого есть утилита findvoc. Запускается она из Emacs нажатием Ctrl+C Ctrl+f. После этого лучше указать параметры -ws, а дальше уже, что ищем, например (без кавычек). Найдётся примерно следующее:

vocabulary: XBOOLE_0
O 32

Это означает, что — операция (на это указывает символ O), и что её порядок предшествования — 32, а лежит она в словаре XBOOLE_0. Нам повезло, что это совпало с названием той статьи, в которой лежат определения операций. Могло и не повезти. Итак, в секцию environ нужно добавить директиву vocabularies XBOOLE_0; Тогда статья после проверки примет следующий вид:

То есть теперь Мицар жалуется не на незнакомое слово, а на то, что он не знает, как его трактовать в таком контексте. Для того, чтобы помочь ему, нужно использоваться так называемые конструкторы и нотации. На самом деле, это примерно одно и то же и хранится оно в тех статьях, где словам даются определения. После добавления нужных директив (ссылок на статью XBOOLE_0, которую мы просматривали в предыдущем абзаце; именно на статью, а не одноимённый словарь — это очень важно!) и запуска проверки получаем следующее

То есть теперь Мицар всё понимает, то считает, что вывод безоснователен.

Ну и как это теперь доказывать?

Да, в общем-то, так же, как мы бы стали это доказывать и без Мицара. С помощью определения равенства множеств. В Mizar mode for Emacs есть замечательный сервис генерации остовов доказательств. Чтобы воспользоваться им, нужно просто выделить строчку, для которой нужно получить остов доказательства и нажать Ctrl+C S. Если это проделать с последней строчкой, убрав предварительно с её конца точку с запятой, то получим следующее

Скобки proof … end; обозначают начало и конец доказательства, а слово thus обозначает начало утверждения, которое нужно доказать (или его часть, если утверждение обладает структурой позволяющей его доказывать по частям). После слова thus можно просто написать thesis вместо того, чтобы дублировать доказываемое утверждение, которое предшествует слову proof. Есть ещё несколько полезных сокращений. Вывод

можно заменить на

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

можно заменить на

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

Теперь можно снова вызвать генерацию остова доказательства и получить примерно следующее:

Неожиданно завершение

Дойдя до этого места, пожалуй стоит заметить, что хотя может быть интуитивно понятно, что такое proof и hereby, а также в целом структура доказательства, но всё-таки лучше о формализованных доказательствах поговорить отдельно. Этому и будет посвящён следующий пост.

Ссылка на основную публикацию
Вычитание в пятеричной системе счисления
Рассмотрим два основных арифметических действия: сложение и умножение в различных системах счисления. Пятеричная система счисления Сложение Составим таблицу сложения для...
Восстановить забытый пароль ржд
Если Вы знаете логин и пароль, а войти на сайт РЖД у Вас не получается, то зайдите на сайт РЖД...
Вызов на ivr положительный ноль что это
Положительный ноль — это сервис, позволяющий абонентам МТС оставаться на связи, даже если баланс их лицевого счета отрицателен или равен...
Готика 1 как продавать предметы
Заберитесь в воду. Первое, что стоит знать о воде, это то, что если рядом с вами будут враги, вы не...
Adblock detector