Основные понятия теории множеств кратко
Обновлено: 05.07.2024
Понятие множества является исходным не определяемым строго понятием. Приведем здесь определение множества (точнее, пояснение идеи множества), принадлежащее Г. Кантору: "Под многообразием или множеством я понимаю вообще все многое, которое возможно мыслить как единое, т.е. такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое".
Множества будем, как правило, обозначать большими буквами латинского алфавита, а их элементы — малыми, хотя иногда от этого соглашения придется отступать, так как элементами некоторого множества могут быть другие множества. Тот факт, что элемент а принадлежит множеству .
В математике мы имеем дело с самыми различными множествами. Для элементов этих множеств мы используем два основных вида обозначений: константы и переменные.
Индивидная константа (или просто константа) с областью значений . Для двух констант , понимая под этим совпадение обозначаемых ими элементов множества понимается так: всякий раз, когда переменное принимает то же самое значение
Обычно константы и переменные, область значений которых есть некоторое числовое множество, а именно одно из множеств и
Логические операции (связки) над множествами
Для образования из уже имеющихся высказываний новых высказываний используются следующие логические операции (или логические связки).
1. Дизъюнкция (читается: " или ") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний и .
2. Конъюнкция : высказывание (читается: " и ") истинно тогда и только тогда, когда истинны оба высказывания и .
3. Отрицание : высказывание
4. Импликация : высказывание (читается: "если , то " или " влечет ") истинно тогда и только тогда, когда истинно высказывание или оба высказывания ложны.
5. Эквивалентность (или равносильность) : высказывание (читается: ", если и только если ") истинно тогда и только тогда, когда оба высказывания и либо одновременно истинны, либо одновременно ложны. Любые два высказывания и , такие, что истинно , называют логически эквивалентными или равносильными.
Записывая высказывания с помощью логических операций, мы предполагаем, что очередность выполнения всех операций определяется расстановкой скобок. Для упрощения записи скобки зачастую опускают, принимая при этом определенный порядок выполнения операций ("соглашение о приоритетах").
Операция отрицания всегда выполняется первой, и потому ее в скобки не заключают. Второй выполняется операция конъюнкции, затем дизъюнкции и, наконец, импликации и эквивалентности. Например, высказывание записывают так: . Это высказывание есть дизъюнкция двух высказываний: первое является отрицанием , а второе — . В отличие от него высказывание есть отрицание дизъюнкции высказываний и .
Например, высказывание после расстановки скобок в соответствии с приоритетами примет вид
Сделаем некоторые комментарии по поводу введенных выше логических связок. Содержательная трактовка дизъюнкции, конъюнкции и отрицания не нуждается в специальных разъяснениях. Импликация истинна, по определению, всякий раз, когда истинно высказывание (независимо от истинности ) или и одновременно ложны. Таким образом, если импликация истинна, то при истинности имеет место истинность , но обратное может и не выполняться, т.е. при ложности высказывание может быть как истинным, так и ложным. Это и мотивирует прочтение импликации в виде "если , то ". Нетрудно также понять, что высказывание равносильно высказыванию и тем самым содержательно "если , то " отождествляется с "не или ".
Равносильность есть не что иное, как "двусторонняя импликация", т.е. равносильно . Это означает, что из истинности следует истинность и, наоборот, из истинности следует истинность .
Пример 1.1. Для определения истинности или ложности сложного высказывания в зависимости от истинности или ложности входящих в него высказываний используют таблицы истинности.
В первых двух столбцах таблицы записывают все возможные наборы значений, которые могут принимать высказывания и . Истинность высказывания обозначают буквой "И" или цифрой 1, а ложность — буквой "Л" или цифрой 0. Остальные столбцы заполняют слева направо. Так для каждого набора значений и находят соответствующие значения высказываний.
Наиболее простой вид имеют таблицы истинности логических операций (табл. 1.1-1.5).
Рассмотрим сложное высказывание . Для удобства вычислений обозначим высказывание через , высказывание через и
Предикаты и кванторы
Сложные высказывания образуются не только посредством логических связок, но и с помощью предикатов и кванторов.
Предикат есть высказывание, содержащее одно или несколько индивидных переменных. Например, "", " и ", "" и т.п. Предикаты будем записывать в виде , полагая, что в скобках перечислены все переменные, входящие в данный предикат.
Подставляя вместо каждого переменного, входящего в предикат , конкретное значение, т.е. фиксируя значения , где — некоторые константы с соответствующей областью значений, получаем высказывание, не содержащее переменных. Например, "2 есть четное число", "Исаак Ньютон есть студент МГТУ им. Баумана, поступивший в 1999 г.", "Иванов есть сын Петрова", "5 делится на 7" и т.п. В зависимости от того, истинно или ложно полученное таким образом высказывание, говорят, что предикат выполняется или не выполняется на наборе значений переменных . Предикат, выполняющийся на любом наборе входящих в него переменных, называют тождественно истинным, а предикат, не выполняющийся ни на одном наборе значений входящих в него переменных, — тождественно ложным.
Высказывание из предиката можно получать не только подстановкой значений его переменных, но и посредством кванторов. Вводят два квантора — существования и всеобщности, обозначаемые и соответственно.
Высказывание ("для каждого элемента ", или, более коротко, "для всех ") истинно, по определению, тогда и только тогда, когда предикат выполняется для каждого значения переменного ("существует, или найдется, такой элемент ", также "для некоторого ") истинно, по определению, тогда и только тогда, когда на некоторых значениях переменного .
Связывание переменных предикатов кванторами
При образовании высказывания из предиката посредством квантора говорят, что переменное предиката связывается квантором. Аналогично связываются переменные в предикатах, содержащих несколько переменных. В общем случае используют формы высказываний вида
где вместо каждой буквы с индексом может быть подставлен любой из кванторов или .
Например, высказывание читается так: "для всякого , такой, что истинно ". Если множества, которые пробегают переменные предикатов, фиксированы (подразумеваются "по умолчанию"), то кванторы записываются в сокращенной форме: или .
Заметим, что многие математические теоремы можно записать в форме, подобной только что приведенным высказываниям с кванторами, например: "для всех и для всех — функция, дифференцируемая в точке непрерывна в точке
Способы задания множеств
Обсудив особенности употребления логической символики, вернемся к рассмотрению множеств.
Два множества . Подчеркнем, что поскольку множество полностью определено своими элементами, то при задании конечного множества порядок, в котором перечислены его элементы, не имеет значения. Поэтому записи и т.д. все задают одно и то же множество. Кроме того, иногда в записи множеств используют повторения элементов. Будем считать, что запись задает то же самое множество, что и запись .
В общем случае для конечного множества используют форму записи . Как правило, при этом избегают повторений элементов. Тогда конечное множество, заданное записью , состоит из элементов. Его называют также n-элементным множеством.
Однако способ задания множества путем непосредственного перечисления его элементов применим в весьма узком диапазоне конечных множеств. Наиболее общим способом задания конкретных множеств является указание некоторого свойства, которым должны обладать все элементы описываемого множества, и только они.
Эта идея реализуется следующим образом. Пусть переменное , выполняющегося тогда и только тогда, когда переменное истинно тогда и только тогда, когда вместо .
Предикат называют в этом случае характеристическим предикатом множества
Например, означает, что "
Термин "коллективизирующее свойство" мотивирован тем, что это свойство позволяет собрать разрозненные элементы в единое целое. Так, свойство, определяющее множество
Если мы вернемся к канторовскому определению множества, то характеристический предикат множества и есть тот закон, посредством которого совокупность элементов соединяется в единое целое. Предикат, задающий коллективизирующее свойство, может быть тождественно ложным. Множество, определенное таким образом, не будет иметь ни одного элемента. Его называют пустым множеством и обозначают Замечание 1.1. Конкретное содержание понятия универсального множества определяется тем конкретным контекстом, в котором мы применяем теоретико-множественные идеи. Например, если мы занимаемся только различными числовыми множествами, то в качестве универсального может фигурировать множество
Свидетельство и скидка на обучение каждому участнику
Зарегистрироваться 15–17 марта 2022 г.
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ
Шандриков А.С.
Витебский государственный политехнический колледж ВГТУ
Термины и определения
Множество – это любая совокупность определённых и различных между собой объектов, мыслимая как единое целое.
Например, резисторы, диоды, конденсаторы образуют совокупность различных между собой объектов, но эта совокупность представляет собой множество РЭК, из которых состоит изделие, и с этой точки зрения такое множество посредством интуиции или интеллекта определяется как единое целое.
Множества обозначаются прописными буквами латинского алфавита – A , B , C и т.д.
Множества состоят из элементов. Элементы множества обозначаются строчными буквами латинского алфавита: a , b , c и т.д.
Множество A , состоящее из элементов a , b и c , записывается в виде
Множество A , содержащее один элемент a , обозначается A = a > и называется одноэлементным .
Множество, которое не содержит элементов, называется пустым и обозначается Ø, например, A = Ø.
Порядок расположения элементов в множестве не имеет значения.
Принадлежность элемента к множеству обозначается символом , а непринадлежность — символом . Запись вида a X означает, что элемент a принадлежит множеству X .
Запись вида b D означает, что элемент b не принадлежит множеству D .
Множество с конечным числом элементов называется конечным . Примеры: множество символов алфавита, множество РЭК в телевизоре и т.д.
Множество называется бесконечным , если число его элементов бесконечно.
Множества A и B называются равными и обозначаются A = B , если они состоят из одних и тех же элементов.
Количество элементов в множестве называется мощностью множества и обозначается | A |. Например, для множества (1) | A | = 3.
Если любой элемент множества X принадлежит множеству Y , то X – это подмножество (часть) множества Y и записывается в виде X Y . Символ обозначает отношение нестрогого включения.
Для любого множества A A .
Если A B и B A , то для любых множеств A и B справедливо A = B .
Если A B и A B , то множество A строго включается в множество B .
Строгое включение обозначается A B .
Система множеств – это множество, элементами которого являются множества. Множество подмножеств (частей) множества X обозначается P ( X ) .
Следует различать отношение принадлежности () и отношение включения (, ). Так, множество A может быть своим подмножеством, т.е. A A , однако множество A не может входить в состав своих элементов, т.е. A A . Отношение включения обладает свойством транзистивности , т.е. если A B и B C , то A C . Отношение принадлежности таким свойством не обладает. Например, множество A = a 1 , a 2 , a 3 >, a 4 > содержит в числе своих элементов множество A = a 2 , a 3 > и поэтому можно записать a 2 , a 3 A и A A . Однако из этого не следует, что элементы a 2 , a 3 A (среди элементов множества A нет элементов a 2 и a 3 ), т.е. a 2 , a 3 A .
Операции над множествами
Объединение (сумма, соединение) множеств A и B — это множество C , состоящее из элементов, принадлежащих или множеству A , или множеству B , или обоим одновременно.
Пример 1 : A = ; B = . C = A B = .
Наглядное представление об объединении даёт графическая иллюстрация с использованием кругов Эйлера (рис. 1). Множества элементов представлены множествами точек внутри кругов A и B .
Рис. 1 – Объединение множеств
Пересечение (логическое произведение) множеств A и B – это множество C , состоящее из элементов, принадлежащих одновременно как множеству A , так и множеству B .
Пример 3 : A = ; B = < 2, 4, 6, 7, 10>. C = A B = .
Пример 4 : A = ; B = . C = A B = .
Пример 5 : A = ; B = . C = A B = Ø.
Графическое множество C – это заштрихованная область на рис. 2.
Рис. 2 – Пересечение множеств
Для операций объединения и пересечения справедливы переместительный, сочетательный и распределительный законы (в высшей математике и в математике логики это законы коммутативности, ассоциативности и дистрибутивности соответственно).
C = A B = B A
C = A B = B A
A (B C) = (A B) C
A (B C) = (A B) C
A (B C) = (A B) (A C)
A ( B C ) = ( A B ) ( A C )
Пересечение множества с самим собой равно исходному множеству: AA = A .
Пересечение некоторого непустого множества с пустым множеством даёт пустое множество: A Ø = Ø.
Разность множеств A и B – это множество C , любой элемент которого принадлежит множеству A и не принадлежит множеству B .
Графическая иллюстрация разности множеств A и B представлена на рис. 3.
Рис. 3 – Разность множеств
Разность в отличие от объединения и пересечения определена только для двух множеств.
Для разности не выполняется переместительный и сочетательный законы, т.е.
Утверждения (2) и (3) не являются очевидными, поэтому проиллюстрируем их на конкретных примерах. Даны три множества
Очевидно, что Ø.
Очевидно , что .
Дополнение множества B по отношению к множеству A – это множество B , элементы которого принадлежат множеству A и одновременно не принадлежат множеству B .
Рис. 3.4. Дополнение B множества B до множества A
Разбиение множества
Разбиение некоторого множества A – это такое множество подмножеств R = A 1 , A 2 , …, A m > , полученных из множества A , которое удовлетворяет следующим условиям:
1) любое из подмножеств A i не является пустым, т.е. не содержит хотя бы один элемент A i = Ø;
2) любое подмножество A i является подмножеством множества A , т.е.
A i A
3) любые два подмножества являются непересекающимися, т.е. A i A j = Ø – пересечение любых двух подмножеств является пустым;
4) каждый элемент исходного множества A обязательно принадлежит какому-либо подмножеству A i , т.е. объединение всех подмножеств A i , входящих в разбиение R , даёт исходное множество A :
Элементы произвольного разбиения называются классами разбиения.
Разбиение R множества A называется поэлементным , если каждый класс разбиения R является одноэлементным множеством.
Разбиение R множества A называется целым , если R = A > .
Целое и поэлементное разбиения множества A называются тривиальными разбиениями, остальные разбиения, если они существуют, — нетривиальными .
Пример 7 : множество A > = Ø имеет единственное разбиение – пустую систему R множеств. Это разбиение является поэлементным, целым оно не является;
Пример 8 : одноэлементное множество A = a > имеет единственное разбиение R = M > = <a >> . Это разбиение одновременно является и целым, и поэлементным;
Пример 9 : двухэлементное множество A = a , b > имеет два разбиения:
R 1 = A > – целое разбиение.
Рис. 3 .5. Разбиения двухэлементного множества
Пример 10 : трёхэлементное множество A = a , b , c > имеет уже пять разбиений (рис. 6):
Рис. 3.6. Разбиения трёхэлементного множества
Разбиение исходного множества на непересекающиеся подмножества применяется, в частности, при решении задач компоновки на начальных этапах проектирования радиоэлектронных средств и технологических процессов их изготовления. Примером компоновки может служить разбиение принципиальной электрической схемы радиоэлектронного средства на отдельные связанные между собой узлы. Решением задачи компоновки в этом случае считается распределение всех радиоэлектронных компонентов, входящих в состав изделия, по заданным узлам.
1. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский М. : Энергоатомиздат, 1988. – 480 с. : ил.
2. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов [и др.] ; М. : Сов. радио, 1978. – 136 с. : ил.
Концепция бесконечности идеологически далека от обычной математической терминологии — ни одна другая тема не выходит за пределы математики так, что превращается из практического, аналитического инструмента в явление мифического порядка. Понятие бесконечности на короткой ноге с такими культурными темами, как религия и философия, и окутана загадочной аурой божественности.
Когда-то давным давно во всех академических дисциплинах было заложено фундаментальное убеждение — существует единственная бесконечность.
С 1874 по 1897 год Кантор неистово публиковал статью за статьёй, разворачивая свою теорию абстрактных множеств в расцветающую дисциплину. Однако она была встречена упорным сопротивлением и критикой; многие педанты считали, что его теории перешли в область философии и нарушили принцип религии.
Однако когда начали находиться практические применения математического анализа, отношение к теории изменилось, а идеи и результаты Кантора начали получать признание. К первому десятилению 20-го века его наблюдения, теории и публикации достигли своей кульминации — признания современной теории множеств новой, совершенно уникальной областью математики:
Теория множеств — это математическая теория о точно определённых наборах (множествах) отдельных объектов, называемых членами или элементами множества.
Сколько чисел есть между 0 и 1?
Первая публикация Кантора, состоящая из четырёх с половиной страниц, является великолепным примером краткости. Она разделена на два отдельных доказательства, совместно приводящих к выводу о существовании по крайней мере двух уникальных видов множеств.
Если говорить вкратце, то набор, или множество всех вещественных алгебраических чисел можно вывести с помощью какого-то теоретического ряда многочленов с различными степенями и коэффициентами; следовательно, множество всех вещественных алгебраических чисел является бесконечным счётным множеством.
Во второй части труда Кантора анализируется роль вещественных комплексных чисел, также называющихся трансцендентными числами. Транцендентные числа (лучшие примеры которых — это пи и e) имеют любопытное свойство: математически невозможно вывести их с помощью многочленной функции — они не являются алгебраическими. Вне зависимости от величин, количества частей, степеней или коэффициентов, никакой ряд никогда не может посчитать пи в своём наборе бесконечного счётного множества.
Затем Кантор указывает, что в любом замкнутом интервале [a,b] существует хотя бы одно транцендентное число, которое никогда нельзя будет подсчитать в бесконечном счётном множестве. Поскольку одно такое число существует, то предполагается, что в семействе вещественных чисел существует бесконечное количество транцендентных чисел.
Таким образом он доказал очень чёткое различие между множеством непрерывных, идущих потоком несчётных чисел и набора счётных чисел, которые можно представить как ряд, например, всех вещественных алгебраических чисел.
Далее: запись и операции
Первая публикация Кантора завершилась на этом потрясающем подтверждении существования по крайней мере двух разных видов бесконечности. После его первой статьи появился шквал дополнений, медленно, но верно прокладывавших путь к современной теории множеств.
Вооружившись базовым пониманием истории множеств и совершив кратковременное погружение в глубины его влияния, мы можем приступать к знакомству с основами системы обозначений теории множеств.
Часть вторая. Краткий обзор операций, обозначений и диаграмм Венна.
Как сказано в предыдущей части, одно из фундаментальных преимуществ теории множеств произрастает не из какой-то конкретной теории, а из созданного ею языка. Именно поэтому основная часть этого раздела будет посвящена обозначениям, операциям и визуальному представлению теории множеств. Давайте начнём с объяснения базовых символов обозначения множества — соответствующих ему элементов. В таблице ниже показан пример одного множества A с тремя элементами:
В первой строке показано множество A с тремя отдельными элементами (A = ); во второй строке показан правильный способ обозначения отдельного конкретного элемента 1, принадлежащего множеству A. Пока всё довольно просто, но теория множеств становится существенно интереснее, когда мы добавляем второе множество — начинается путешествие по стандартным операциям.
Для показанной выше таблицы давайте введём два дополнительных множества B и C, содержащие следующие элементы: B = , C = . Хоть мы и создали три множества (A,B и C), в показанных ниже примерах операции выполняются одновременно только с двумя множествами, поэтому внимательно следите за тем, какие множества указаны в самом левом столбце. В показанной ниже таблице представлено пять самых распространённых операндов множеств:
Операции: пересечение (intersection) — множество элементов, принадлежащих множеству A и множеству B;
объединение (union) — множество элементов, принадлежащих множеству A или множеству B;
подмножество (subset) — C является подмножеством A, множество C включено во множество A;
собственное (истинное) подмножество — C является подмножеством A, но C не равно A;
относительное дополнение (relative complement) — множество элементов, принадлежащих к A и не к B.
Вот и они, самые распространённые операции в теории множеств; они довольно популярны и в областях за пределами чистой математики. На самом деле, высока вероятность того, что вы уже видели подобные типы операций в прошлом, хоть и не совсем с такой терминологией, и даже пользовались ими. Хорошая иллюстрация: попросите любого студента описать диаграмму Венна из двух пересекающихся групп, и он интуитивно придёт к правильному результату.
Ещё раз взгляните на последнюю строку, относительное дополнение — какое необычное сочетание слов, правда? Относительное к чему? Если относительное дополнение A — B определяется как A и не B, то как нам обозначить всё, что не является B?
Универсальное множество — пустое множество
Оказывается, если мы хотим получить значимый ответ, то для начала нужно предоставить генеральной совокупности нашей задачи множеств некий контекст. Он часто явным образом задаётся в начале задачи, когда допустимые элементы множества ограничиваются некоторым фиксированным классом объектов, в котором существует универсальное множество, являющееся общим множеством, содержащим все элементы для этой конкретной задачи. Например, если мы хотели бы работать со множествами только из букв английского алфавита, то наше универсальное множество U состояло бы из 26 букв алфавита.
Для любого подмножества A множества U дополнение множества A (обозначаемое A′ или U − A) определяется как множество всех элементов в генеральной совокупности U, которое не находится в A. Если вернуться к поставленному выше вопросу, то дополнением множества B является всё в пределах универсального множества, что не принадлежит B, в том числе и A.
Диаграммы Венна и остальное
Диаграммы Венна, официально изобретённые в 1880 году Джоном Венном, являются именно тем, что вы и представляете, хотя их научное определение звучит примерно так:
Ниже показано изображение шести самых распространённых диаграмм Венна, и почти во всех показаны недавно изученные нами операнды:
Объединение (union), пересечение (intersection), относительное дополнение (relative complement), симметрическая разность (symmetric difference), собственное множество (proper subset), абсолютное дополнение (universal дополнение).
Начав с очень простых обозначений множества и его элементов, мы узнали затем о базовых операциях, позволивших нарисовать эту визуальную подсказку. Мы рассмотрели все операции, за исключением симметрической разности (внизу слева). Чтобы не оставлять пробелов в знаниях, скажем, что симметрическая разность, также называемая дизъюнктивным объединением — это просто множество элементов, которые находятся в любом из множеств, но не входят в их пересечение.
Закончим мы этот раздел введением понятия мощности (кардинального числа). Мощность множества, обозначаемая символом абсолютного значения — это просто количество уникальных элементов, содержащихся в определённом множестве. Для показанного выше примера мощность трёх множеств равна: |A| = 3, |B| =6, |C| = 2.
Прежде чем двигаться дальше, дам вам пищу для размышлений — какова связь между мощностью и количеством возможных подмножеств?
Часть 3. Мощность и показательные множества
В предыдущих двух частях мы разобрались с основами теории множеств. В третьей части мы укрепим своё понимание, сосредоточившись на самом важном свойстве любого множества: общем количестве содержащихся в нём уникальных элементов.
Количество уникальных элементов во множестве, также известное как мощность, предоставляет нам фундаментальную опорную точку для дальнейшего, более глубокого анализа этого множества. Во-первых, мощность — это первое из рассматриваемых нами уникальных свойств, позволяющее нам объективно сравнивать различные виды множеств, проверяя, существует ли биекция (это, с небольшими оговорками, просто более изысканный термин для function ) одного множества на другое. Ещё один способ применения мощности, а также тема этой части статьи — мощность позволяет оценить все возможные подмножества, существующие в данном множестве. Что достаточно буквально можно применять в повседневных задачах распределения решений, будь то планирование бюджета на поездку в продуктовый магазин или оптимизация портфеля акций.
Примеры мощности множеств
Например, в таблице выше показаны пять отдельных множеств с их указанной справа мощностью. Как мы уже говорили, символ мощности напоминает символ абсолютного значения — значение, заключённое между двумя вертикальными линиями. Все примеры понятны, за исключением, возможно, последней строки, которая подчёркивает тот факт, что на мощность влияют только уникальные элементы множества.
Помните подмножества из предыдущей части статьи? Оказывается, что мощность некоторого множества A и количество возможных подмножеств множества A имеют удивительную связь. Ниже показано, что количество подмножеств, которые можно составить из некоторого подмножества, увеличивается с порядком мощности на предсказуемую величину:
Показательное множество (булеан)
Прежде чем мы вычислим все подмножества для примера множества C, я хотел бы ввести последнее понятие — булеан.
Булеан обозначается заглавной буквой S, за которой в скобках указывается исходное множество S(С). Булеан — это множество всех подмножеств C, включая пустое множество и само множество C. В таблице ниже показан булеан S(С) со всеми перестановками возможных подмножеств для множества C, содержащихся в одном большом множестве.
Для удобства форматирования я убрал запятые между множествами***
Чем может быть полезен булеан? На самом деле, вы скорее всего много раз интуитивно использовали булеаны, даже об этом не догадываясь. Каждый раз, когда вы выбираете подмножество элементов из более крупного множества, вы выбираете элемент булеана. Например ребёнок внимательно изучающий кондитерский магазин с купюрой в 5 долларов — какой элемент булеана множества всех доступных сладостей он выберет? Или если взять более технический пример: вам, как разработчику ПО может потребоваться запросить всех возможных пользователей базы данных, также обладающих свойством X и Y — ещё один случай, в котором одно подмножество выбирается из всех возможных подмножеств.
Эквивалентность и биективная функция
Теперь мы понимаем, что такое мощность множества, почему оно важно, и его связь с булеаном. Поэтому вернёмся ненадолго к тому, что упоминали в самом начале: что конкретно определяет эквивалентность в теории множеств?
Часть 4. Функции.
В этой части мы подробнее расскажем о функциях в пределах теории множеств. Как и в случае с предыдущими понятиями, терминология стандартных функций в теории множеств слегка отличается от других областей математики, а потому требует объяснения. Терминологии довольно много, так что давайте сразу приступим к делу! В первой таблице внизу отражены понятия области определения, области значений и значения функции:
Пока особо ничего сложного, только новый способ задания параметров функций. Далее мы расскажем о том, как описывать поведения этих функций соответствия при помощи обычных типов функций.
Инъекции, сюръекции и биекции
В теории множеств для классификации соответствия множеств обычно используются три понятия: инъекция, сюръекция и биекция. К сожалению, эти понятия имеют несколько разных названий, усиливающих неразбериху, поэтому мы сначала рассмотрим каждое определение, а затем изучим визуальные примеры. Все три термина описывают способ, которым отображаются аргументы на образы:
Прочитайте заново представленный выше список пунктов. Биекция — это просто функция, удовлетворяющая обоим предыдущим требованиям; то есть, функция инъективна и сюръективна. Инъективная функция не должна быть сюръективной, а сюръективная — инъективной. Ниже показан визуальный пример, в котором эти три классификации привели к созданию функций множеств, определяемых четырьмя возможными комбинациями инъективных и сюръективных свойств:
Биекция (инъекция + сюръекция), инъекция (инъекция + не-сюръекция), сюръекция (не-инъекция + сюръеция), без классификации (не-инъекция + не-сюръекция)
Вот и всё! Теперь мы обладаем элементарным пониманием самых часто встречаемых соотношений, встречающихся в мире множеств. Однако это ни в коем случае не конец нашего пути: напротив, это самое начало.
Фундаментальные основы теории множеств — ключ к пониманию более высокоуровневых областей математики. Чтобы продолжить наше движение вверх, к этим различным областям, далее нужно будет, пользуясь своими знаниями о теории множеств, уяснить одну из самых революционных теорий в истории математики: систему аксиом Цермело-Френкеля.
Тема 1. Основные понятия теории множеств. Способы задания множеств. Диаграммы Венна. Операции над множествами. Свойства теоретико-множественных операций. Представление множеств в ЭВМ.
Основные понятия теории множеств. Способы задания множеств
Определение 1.1. Множество – это любая, определенная совокупность объектов. Объекты из которых составлено множество называют его элементами. Элементы множества различны и отличны друг от друга. Множества обозначают прописными буквами латинского алфавита, а их элементы – строчными. Например N, Z, Q, R – множества натуральных, целых, рациональных и действительных чисел.
Если объект х является элементом множества М, то говорят, что хÎМ. Если х не является элементом множества М, то говорят, что хÏМ.
Одно множество равно другому, если выполняется условие: A=B | A B & B A
Множество не содержащее элементов называется пустым. Его обозначают Ø.
Обычно, в конкретных обсуждениях, элементы всех множеств берутся из некоторого одного достаточно широкого множества U (своего для каждого множества), которое называется универсальным множеством или универсумом. В общем случае множества могут быть конечными и бесконечными. Конечное множество – это такое множество, для которого существует натуральное число, равное количеству элементов множества, и называемое мощностью множества и обозначаемое |A|.
Чтобы задать множество нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:
1)перечислением элементов множества А=1, a2,…, an|n=6> (перечислением можно задавать только конечное множество);
2) характеристическим предикатом M=< x | P(x) >, где P(x) – предикат.
Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения, возвращаемое логическое значение. Если для данного элемента условие выполнено, т.е. P(x) = 1, то этот элемент принадлежит определяемому множеству, в противном случае – не принадлежит. Пример 1.1.:
Основные понятия теории множеств. Способы задания множеств
Определение 1.1. Множество – это любая, определенная совокупность объектов. Объекты из которых составлено множество называют его элементами. Элементы множества различны и отличны друг от друга. Множества обозначают прописными буквами латинского алфавита, а их элементы – строчными. Например N, Z, Q, R – множества натуральных, целых, рациональных и действительных чисел.
Если объект х является элементом множества М, то говорят, что хÎМ. Если х не является элементом множества М, то говорят, что хÏМ.
Одно множество равно другому, если выполняется условие: A=B | A B & B A
Множество не содержащее элементов называется пустым. Его обозначают Ø.
Обычно, в конкретных обсуждениях, элементы всех множеств берутся из некоторого одного достаточно широкого множества U (своего для каждого множества), которое называется универсальным множеством или универсумом. В общем случае множества могут быть конечными и бесконечными. Конечное множество – это такое множество, для которого существует натуральное число, равное количеству элементов множества, и называемое мощностью множества и обозначаемое |A|.
Чтобы задать множество нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:
1)перечислением элементов множества А=1, a2,…, an|n=6> (перечислением можно задавать только конечное множество);
2) характеристическим предикатом M=< x | P(x) >, где P(x) – предикат.
Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения, возвращаемое логическое значение. Если для данного элемента условие выполнено, т.е. P(x) = 1, то этот элемент принадлежит определяемому множеству, в противном случае – не принадлежит. Пример 1.1.:
Читайте также: