Теория множеств I: наивная теория множеств - Версия для печати +- Aluarium (http://aluarium.net/forum) +-- Форум: Наука и техника (/forum-46.html) +--- Форум: Математика (/forum-49.html) +--- Тема: Теория множеств I: наивная теория множеств (/thread-178.html) Страниц: 1 2 |
|||||||||||||||||||||||||||||||||||||||||
Теория множеств I: наивная теория множеств - arseniiv - 04-10-2012 16:07 Начну с неформального описания теории множеств, а закончу тем, почему этого мало. Привычный многим кусок математики имеет дело с числами (как правило, рациональными: -7, 0,28, 31/7…). Мы можем их умножать, складывать, сравнивать; решать уравнения, да и просто находить числа с нужными свойствами — и много чего ещё. Теория множеств примерно так же обходится с множествами — крутит их по-всякому, в общем. Множество можно для начала понимать как прозрачный пакет, в котором могут находиться вещи: числа, картины, цвета, названия биологических видов, стихотворения Марины Цветаевой, фонемы японского языка в состоянии двумя веками раньше, другие множества… Самих пакетов у нас, предположим, целая упаковка, и они для нас ничего не значат; просто неразличимы — можно пересыпать содержимое из одного пакета в другой, и тот будет представлять собой то же множество. Самое основное, что мы можем сделать с такими пакетами — узнать, находится в данном такой-то предмет или нет. Например, в множестве чётных чисел есть 2, 6794 и нету 1113. Говорят, что 2 принадлежит этому множеству, а 1113 не принадлежит, или, что то же самое, множество чётных чисел содержит 2 и не содержит 1113. А обозначается это так: 2 ∈ ЧётныеЧисла, 1113 ∉ ЧётныеЧисла. Множества можно сравнивать. Два множества A и B равны, если каждый элемент A содержится и в B, а каждый не принадлежащий A объект не принадлежит и B. Иными словами, принадлежность любой вещицы первому множеству эквивалентна принадлежности её второму. Если хоть один элемент одного из множеств отсутствует в другом — они уже не равны — это важное замечание: чтобы доказать, что A и B равны, нужно оперировать общими суждениями, тогда как чтобы показать обратное, достаточно одного частного — контрпримера. Например, легко доказать, что множество смартфонов не равно множеству телефонов (как бы изощрённо мы их не определяли) — Nokia 1112 входит во второе и не входит в первое. Как одно число может быть больше другого, так и множество может включаться в другое. Множество A является подмножеством B, когда все элементы A содержатся также и в B. Например, множества как чётных, так и нечётных чисел — это подмножества множества целых чисел. Записывают это так: ЧётныеЧисла* ⊂ Z, НечётныеЧисла ⊂ Z. Шарфы не входят в множество обуви — Шарфы ⊄ Обувь. «Чаще всего» из двух множеств ни одно не является подмножеством другого — когда как в первом есть элементы, которых нет во втором, так и во втором есть что-то, чего нет в первом, как ЧётныеЧисла и НечётныеЧисла. Однако есть множество, которое входит в любое другое. Что это за множество? Чтобы C входило в любое множество, все его элементы должны быть в этом любом. Рассмотрим снова множества чётных и нечётных чисел. Чтобы наше C было подмножеством каждого из них, в нём не должно быть никаких вещей кроме чисел — иначе оно не будет подмножеством ни чётных, ни нечётных — а также чётных чисел — иначе оно не будет подмножеством первого — да и нечётных оно содержать тоже не должно. Получается, в этом множестве вообще ничего не должно содержаться, что может показаться несоответствующим названию «множество». Что ж, такое название прижилось в русском языке, а полученное нами множество C называется пустым и обозначается ∅. Ещё заметка: равные множества являются подмножествами друг друга, т. к. для них выполняется предыдущее определение. И наоборот, из A ⊂ B и B ⊂ A, оказывается, всегда следует A = B. Это совсем не нужно принимать на веру; вот доказательство того, что если (1) A ⊂ B и (2) B ⊂ A, то A = B: Рассмотрим любой предмет ы. Если ы ∈ A, то по первому условию ы ∈ B. Если ы ∉ A, предположим, что ы ∈ B всё равно. Тогда по второму условию ы ∈ A, что приводит к противоречию. Значит, наше предположение не верно, и ы ∉ B. Получили ровно определение равенства A и B: каждый принадлежащий A элемент принадлежит B, каждый не принадлежащий — не принадлежит B. ◼** Есть несколько операций, которые позволяют получать из одних множеств другие:
Проиллюстрирую их на конечных множествах. Множество конечного размера можно определить, выписав по очереди все его элементы. Этим часто пользуются и пишут {a, b, c, d} для обозначения множества первых 4-х букв латинского алфавита и {-2, 2} для множества корней уравнения x² = 4. Итак, пусть R = {1, 2, 3, 8} и Q = {0, 2, 4, 6, 8}. Тогда Q ∪ R = R ∪ Q = {0, 1, 2, 3, 4, 6, 8}, Q ∩ R = R ∩ Q = {2, 8}, Q \ R = {0, 4, 6}, R \ Q = {1, 3}, Q △ R = R △ Q = {0, 1, 3, 4, 6}. Результат объединения, пересечения и симметрической разности не зависит от порядка операндов всегда. Когда пересечение множеств пусто, их называют не пересекающимися. Множества городов Европы и Америки не пересекаются (хотя множества соответствующих названий пересекаются. Например, в пересечение входит «Афины»). Несколько простых задач:
Пока всё. Пишите письма — у меня нет уверенности, что я написал понятно для целевой аудитории. Например, я чувствую, что следует для начала заняться исчислением высказываний — не могу избавиться от зависимости от некоторых рассматриваемых там относящихся к логике вещей. * Позже я введу несколько способов обозначать эти множества по-другому, а пока пускай так. ** Конец доказательства. RE: Теория множеств I: наивная теория множеств - Quasus - 13-10-2012 19:37 Про пакеты не очень понял. Фактически написано, но ещё раз заострить внимание: каждый если объект входит в множество, то только один раз. Для полноты изложения — изначальное определение Кантора: Под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M). О, в википедии даже по-немецки есть: Unter einer ‚Menge‘ verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objecten m unsrer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von M genannt werden) zu einem Ganzen. Ещё можно про произведения и фактор-множества. И, конечно же, отображения! Чтобы было в теоретико-категориальном духе. RE: Теория множеств I: наивная теория множеств - arseniiv - 13-10-2012 20:43 Да-да, это надо сделать! Правда, я не знаю, получится в духе или нет. Насколько догадываюсь, определение через отношение не в этом духе (но тогда как?)? [Интересно, можно ли построить всё на отображениях?] RE: Теория множеств I: наивная теория множеств - Ickander - 13-10-2012 20:44 О! А я с телефона читал думал что там на месте треугольника ⊕ стоит. ан нет. RE: Теория множеств I: наивная теория множеств - Agrest - 13-10-2012 22:06 (13-10-2012 19:37)Quasus писал(а): Про пакеты не очень понял.+1. По-моему пример с пакетами скорее запутывает, чем помогает. RE: Теория множеств I: наивная теория множеств - arseniiv - 13-10-2012 22:59 Ещё раз повторю, что множества бывают элементами других множеств (такие множества множеств называют ещё семействами, чтобы лишний раз не упражняться в риторике). Например, прямая — это бесконечное множество точек, отрезок — тоже бесконечное множество точек (хотя он и имеет конечную длину — что с этим делать, я дальше расскажу). Множество отрезков, лежащих на данной прямой — это как раз семейство множеств. А ещё семейство — множество прямых, параллельных данной. Итак, дорогие читатели, мы теперь можем немного манипулировать множествами. Сейчас я покажу вам ещё способы. Во-первых, не стоит забывать, что мы можем составлять конечные множества, в которых содержится ровно то, что нам нужно: если x ∈ {a, b, c}, то x = a, или x = b, или x = c. Мы можем также взять множество A, а потом отобрать из него какие-то элементы, которые нам полюбились по какому-нибудь признаку. Например, множество чётных чисел — это множество таких целых, которые делятся на 2. Теперь мы можем сказать, что ЧётныеЧисла = { x | x ∈ Z и x делится на 2 } — слева от черты пишется какой-то элемент, который мы проверяем на принадлежность, а справа — условие, когда эта принадлежность имеет место. (Как вы помните, Z — это множество целых чисел.) Слева в конструкции { … | … } может быть и какое-нибудь выражение. Например, т. к. чётные и нечётные числа чередуются, можно, добавляя к каждому чётному 1, получить каждое нечётное. То бишь, НечётныеЧисла = { x + 1 | x ∈ Z и x делится на 2 }. Хотя это множество с тем же успехом можно обозначить и как { x - 5 | x ∈ ЧётныеЧисла }, и как { x | x ∈ Z и x не делится на 2 }, и ещё много как, точно так же, как записи 1/2, 0,5 и 34/68 задают одно и то же число. Множества не упорядочены — запись {a, b, c} означает ровно то же множество, что и {c, a, b}. Однако часто нам нужно иметь «контейнер», у которого есть первый элемент, второй элемент и т. д.. Например, координаты (x, y) [заметьте, круглость скобок показывает, что это вещь иная нежели {x, y}] точки на плоскости в привычной прямоугольной системе координат задаются двумя числами, и их порядок нельзя менять, т. к. взятые в обратном порядке координаты будут задавать другую точку, если только эти координаты не равны. Для нашего трёхмерного пространства нужны три координаты (x, y, z). Могут понадобиться и наборы из большего числа вещей. Эти наборы называют ещё по числу элементов — двойками, тройками, …, n-ками (так и произносится — /э́нкам'и/), а ещё кортежами — когда «размер» набора не важен, неизвестен либо просто хочется сказать красиво. Давайте теперь представим некую Елену, и что в множестве A — блюда, которые она любит есть на завтрак, в B — на обед, а в C — на ужин (она предпочитает ровно трёхразовое питание, традиционалистка). Из этих блюд можно составлять тройки (a, b, c), где a ∈ A, b ∈ B, c ∈ C — одной такой тройкой однозначно описывается вариант суточных кушаний Елены. Мы можем получить все возможные такие варианты — их множество запишется как { (a, b, c) | a ∈ A и b ∈ B и c ∈ C }. Оказывается, такие вещи довольно часто встречаются, и для них ввели ещё одну операцию над иножествами — прямое (декартово) произведение, которое для упомянутого множества будет включать три множества: A × B × C. Здесь знак умножения нельзя опустить или заменить на точку ⋅ — поймут неправильно. Можно декартово умножить любое число множеств, а ещё заметьте, что, в отличие от умножения чисел, порядок имеет значение: {0, 1} × {4} будет содержать пары (0, 4) и (1, 4), а {4} × {0, 1} будет иметь вид ровно { (4, 0), (4, 1) }. Если бы пары были множествами, обратный порядок их элементов нам не помешал — но тут мы получаем разные результаты. Кстати, почему произведение? Самая близкая к нам сейчас причина — это то, что в A × B × C из примера с Еленой содержится столько вариантов поесть, сколько получится, если умножить число вариантов позавтракать, число вариантов обеда и число вариантов В пустом множестве 0 элементов. Получается, в множестве A × ∅ тоже должно быть 0 — действительно, не найдётся ни одной пары, чтобы вторым элементом её было что-то, сожержащееся в ∅ — там же ничего нет! A × ∅ = ∅, да и ∅ × A = ∅ для любого множества A. Получается похоже на ноль у чисел! Что на него ни умножь, он всё «поглотит», оставив себя в результате. Коль мы уже заговорили о количестве элементов, я покажу вам, как не париться и не писать «количество элементов множества Y». Будем писать это так: |Y|, типа модуль. У бесконечных множеств такое выражение не теряет смысл, но оно уже не будет числом. Потренируемся его вставлять в правильных местах, переписав уже рассмотренные верные утверждения: |∅| = 0 |{a}| = 1 |A × B| = |A| ⋅ |B| |A × … × Z| = |A| ⋅ … ⋅ |Z| Давайте теперь попробуем записать, чему равно |A ∪ B|. Это была бы сумма |A| и |B|, если бы элементы одного не могли содержаться в другом. При наличии таких элементов мы в выражении |A| + |B| каждый сосчитаем по два раза. Тут можно вовремя вспомнить, что A ∩ B как раз содержит эти дважды считающиеся элементы. А |A ∩ B|, получается, их количество! Если вычесть его из |A| + |B|, каждый элемент объединения будет посчитан по разу. Итак, |A ∪ B| = |A| + |B| - |A ∩ B|, или, более симметрично, |A ∪ B| + |A ∩ B| = |A| + |B|. Проверьте это равенство для каких-нибудь двух конечных множеств чисел.* А теперь немного ещё повертим упорядоченные па́ры. Представьте, что в одном множестве мы собрали разные страны, а в другом — разную погоду, которая случается иногда на земле. С помощью пары (страна, погода) можно описать, к примеру, что погода погода встречается в стране страна. Если собрать все подобные описания в одно множество, получим некоторое подмножество R произведения Страны × Погоды. Оно совпадало бы со всем им, если бы в каждой стране бывала всякая погода. (К счастью, это не так.) R может быть достаточно разной структуры в зависимости от Земли и деления на страны и типы погод, но оно всегда останется подмножеством от Страны × Погоды. Так вот, такие подмножества произведений A × B зовут отношениями. Название объясняется тем, что конкретное R ⊂ A × B определяет «связи» элементов A и элементов B, показывая как они относятся друг к другу. Например, на целых числах можно показать кучу отношений, что я щас и покажу. Сперва дополним ещё наш глоссарий. Если (a, b) ∈ R, то говорят, что a и b находятся в отношении R и для разнообразия и удобства записывают это же ещё и как a R b. Кажется несколько странным такое написание, но это станет понятно сразу же после.
Дальше рассказ пойдёт про** одно из самых вездесущих понятий в математике — отображение, у которого из-за вездесущести много имён… Но перед этим будет отступление о кванторах и немного около. * Если не придумывается, возьмите {2, 5, 8, 9} и {5, 4, 3}. ** И не только. Будут уточняться и доописываться и уже введённые вещи. Чтобы понять что-то, часто надо повертеть его в руках, покидать в стену и надкусить. RE: Теория множеств I: наивная теория множеств - Quasus - 13-10-2012 23:08 (13-10-2012 20:43)arseniiv писал(а): Да-да, это надо сделать! Правда, я не знаю, получится в духе или нет. Насколько догадываюсь, определение через отношение не в этом духе (но тогда как?)? [Интересно, можно ли построить всё на отображениях?] Дух теории категорий просто в том смысле, что объекты без морфизмов — деньги на ветер. Определить можно через «правило/закон/отношение», а потом формализовать. Формализация — это же вроде как имплементация. Если есть стандартная формализация, это не значит, что она что-то даёт для понимания сути дела. (Впрочем, обычное определение через отношение — просто большая-пребольшая таблица значений.) Что построить на отображениях? Теорию множеств? В ключе теории категорий можно (конечно, не удастся различать равномощные объекты). Например, объединение формализуется так. Пусть A и B — данные множества. Рассмотрим категорию, в которой объектами являются диаграммы A → X ← B, а морфизмами — такие отображения X → Y, что диаграмма Код: X - arseniiv - 04-11-2012 17:14 Итаг, я заобещался и ничего не пишу. Это нехорошо. Язык математической логики. Он нам понадобится дальше. И мне жалко, что я не ввёл его вначале. Логика рассматривает высказывания — некие сущности, которые могут быть истинными или ложными — обязательно что-то из двух и не оба сразу — и связь истинности разных высказываний. Вначале, будучи веткой философии, логикам приходилось тяжко — как бедным протоалгебраистам, описывающим квадратные уравнения и их решение словами. У последних было целых пять* видов уравнений, так как они ещё и отрицательные числа не любили. Теперь же у нас есть удобный компактный язык. Как и любые вещи, высказывания можно обозначать буквами. Это пригождается, когда мы начинаем строить из одних высказываний другие. Для этого есть операции, похожие даже немного на операции над множествами. Пускай у нас есть высказывания A и B, тогда из них мы можем построить следующее:
Будем писать A = 1, когда A истинно, и A = 0, когда A ложно. Тогда можно говорить о значении A — и это поможет дальше. А пока с помощью этого можно нарисовать таблицу истинности для логических операций, чтобы было явнее, какие высказывания они дают. Сначала простая маленькая табличка для ¬A:
Она читается так: «когда A = 0, ¬A = 1, а при A = 1 значением ¬A будет 0». Таблицы истинности для высказываний A ∨ B, A & B, A ⇒ B, A ⇔ B, A ⊕ B в зависимости от истинности A и B я совмещу в одну широкую. Вместе их, к тому же, удобнее сравнивать.
С помощью таблиц истинности можно сделать много полезных вещей. Например, заметим по предыдущей, что A ⇔ B — это ¬(A ⊕ B) (и наоборот — вообще, отрицание всегда «взаимно»**). Будем писать A = B, если A истинна тогда же, когда B — т. е. если A ⇔ B = 1, а формулы, которыми записаны A и B, называть эквивалентными. С помощью таблицы истинности или по определениям можно показать такие эквивалентности:
Теперь рассмотрим высказывания, зависящие от каких-нибудь вещей. Например, «x < 8» зависит от x, «a + b = c + d» зависит от четырёх переменных. Появляются новые операции, которые можем над ними делать — можно определённым образом исключать из них переменные. Пусть есть у нас какое-то высказывание A[x]. (Квадратные скобки показывают, что оно зависит от x.) Тогда можно взять какое-то множество M и посмотреть, какое значение принимают A[m1], A[m2] и т. д., подставляя в A вместо x элементы M. Получим набор логических значений. Так вот,
Символы ∀, ∃ и ∃! зовутся кванторами. Видим, что новые высказывания уже никак не зависят ни от каких переменных — переменные «связаны» кванторами. Имея высказывание, зависящее от 8 переменных и «повесив» на него 5 кванторов, получим высказывание, азвисящее от 3 переменных. Друг через друга кванторы выражаются так:
Другие соотношения эквивалентности для формул с кванторами я приводить не буду, надеясь на интуицию читателей и свою. P. S. Прошу вас, не пугайтесь. (А задачи мне писать лень.) Следующая запись будет относиться к функциям и далее. * Точно не помню. Желающие могут посчитать сами! ** Построив таблицу истинности для ¬(¬A), вы убедитесь, что истинность этого высказывания совпадает с истинностью A. И если B = ¬A, то ¬B = ¬¬A = A, то бишь, А является отрицанием B, если B является отрицанием A. - arseniiv - 04-11-2012 17:15 Караул! Что-то сбилось в разметке сообщения. Не читайте пока. Я над ним поиздевался, но не смог добиться нужного результата. UPD 04.09.2013: Починил! Ура! - Teilnehmer - 01-01-2013 11:27 (13-10-2012 22:59)arseniiv писал(а): Однако часто нам нужно иметь «контейнер», у которого есть первый элемент, второй элемент и т. д.. … Эти наборы называют ещё по числу элементов — двойками, тройками, …, n-ками (так и произносится — /э́нкам'и/), а ещё кортежами — когда «размер» набора не важен, неизвестен либо просто хочется сказать красиво.Может, сто́ит привести и «имплементацию» n-ок через множетсва, чтобы показать, что они не какие-то сторонние/несводимые, и что можно всё определить с помощью одних только множеств? Заодно, доказательства работоспособности такой имплементации (что, например, {{a, b}, {a}} = {{a', b'}, {a'}} ⇔ a = a' & b = b') послужат примером к материалу первой главы. |