Деление множеств: Разность множеств | Теория множеств

Python и теория множеств / Хабр

В Python есть очень полезный тип данных для работы с множествами – это set. Об этом типе данных, примерах использования, и небольшой выдержке из теории множеств пойдёт речь далее.

Следует сразу сделать оговорку, что эта статья ни в коем случае не претендует на какую-либо математическую строгость и полноту, скорее это попытка доступно продемонстрировать примеры использования множеств в языке программирования Python.

• Множество
• Множества в Python
  
  • Хешируемые объекты
• Свойства множеств
  
  • Принадлежность множеству
  • Мощность множества
  • Перебор элементов множества
• Отношения между множествами
  
  • Равные множества
  • Непересекающиеся множества
  • Подмножество и надмножество
• Операции над множествами
  
  • Объединение множеств
  • Добавление элементов в множество
  • Пересечение множеств
  • Разность множеств
  • Удаление элементов из множества
  • Симметрическая разность множеств
• Заключение
• Полезные ссылки

Множество

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

Множество – это не более чем неупорядоченная коллекция уникальных элементов.

Что значит неупорядоченная? Это значит, что два множества эквивалентны, если содержат одинаковые элементы.

Элементы множества должны быть уникальными, множество не может содержать одинаковых элементов. Добавление элементов, которые уже есть в множестве, не изменяет это множество.

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

Множества в Python

Множество в Python можно создать несколькими способами. Самый простой – это задать множество перечислением его элементов в фигурных скобках:

fruits = {"banana", "apple", "orange"}

Единственное ограничение, что таким образом нельзя создать пустое множество. Вместо этого будет создан пустой словарь:

wrong_empty_set = {}
print(type(wrong_empty_set))
# Вывод
<class "dict">

Для создания пустого множества нужно непосредственно использовать set():

correct_empty_set = set()
print(type(correct_empty_set))
# Вывод
<class "set">

Также в set() можно передать какой-либо объект, по которому можно проитерироваться (Iterable):

color_list = ["red", "green", "green", "blue", "purple", "purple"]
color_set = set(color_list)
print(color_set)
# Вывод (порядок может быть другим):
{"red", "purple", "blue", "green"}

Ещё одна возможность создания множества – это использование set comprehension. Это специальная синтаксическая конструкция языка, которую иногда называют абстракцией множества по аналогии с list comprehension (Списковое включение).

numbers = [1, 2, 2, 2, 3, 3, 4, 4, 5, 6]
# Единственное отличие со списковыми включениями - это
# использование фигурных скобок вместо квадратных
even_numbers = {
    number for number in numbers
    if number % 2 == 0
}
print(even_numbers)
# Вывод (порядок может быть другим):
{2, 4, 6}

Хешируемые объекты

Существует ограничение, что элементами множества (как и ключами словарей) в Python могут быть только так называемые хешируемые (Hashable) объекты.

Это обусловлено тем фактом, что внутренняя реализация set основана на хеш-таблицах. Например, списки и словари – это изменяемые объекты, которые не могут быть элементами множеств. Большинство неизменяемых типов в Python (int, float, str, bool, и т.д.) – хешируемые. Неизменяемые коллекции, например tuple, являются хешируемыми, если хешируемы все их элементы.

# Множество кортежей (tuple)
records = {
    ("Москва", 17_200_000), 
    ("Санкт-Петербург", 5_400_000), 
    ("Новосибирск", 1_600_000),
    ("Москва", 17_200_000),
}
for city, population in records:
    print(city)
# Вывод (порядок может быть другим):
Москва
Новосибирск
Санкт-Петербург

Объекты пользовательских классов являются хешируемыми по умолчанию. Но практического смысла чаще всего в этом мало из-за того, что сравнение таких объектов выполняется по их адресу в памяти, т.е. невозможно создать два «равных» объекта.

class City:
    def __init__(self, name: str):
        self. name = name
    def __repr__(self) -> str:
        """ Определим метод __repr__ для наглядности следующих примеров
        """
        return f'City("{self.name}")'
print(City("Moscow") == City("Moscow"))
# Вывод:
False
cities = {City("Moscow"), City("Moscow")}
print(cities)
# Вывод
{City("Moscow"), City("Moscow")}

Скорее всего мы предполагаем, что объекты City("Moscow") должны быть равными, и следовательно в множестве cities должен находиться один объект.
Этого можно добиться, если определить семантику равенства для объектов класса City:

class City:
    def __init__(self, name: str):
        # Атрибут name не должен изменяться, пока объект существует
        # Для простоты пометим этот атрибут как внутренний
        self._name = name
    def __hash__(self) -> int:
        """ Хеш от объекта
        """
        return hash((self._name, self.__class__))
    def __eq__(self, other) -> bool:
        """ Определяем семантику равентсва (оператор ==)
        """
        if not isinstance(other, self.  __class__):
            return False
        return self._name == other._name
    def __repr__(self) -> str:
        """ Определим метод __repr__ для наглядности следующих примеров
        """
        return f'City("{self._name}")'

Чтобы протокол хеширования работал без явных и неявных логических ошибок, должны выполняться следующие условия:

• Хеш объекта не должен изменяться, пока этот объект существует
• Равные объекты должны возвращать одинаковый хеш

moscow = City("Moscow")
moscow_again = City("Moscow")
print(moscow == moscow_again and hash(moscow) == hash(moscow_again))
# Вывод:
True
# Теперь множество городов работает более логично и интуитивно
cities = {City("Moscow"), City("Kazan"), City("Moscow")}
print(cities)
# Вывод (порядок может быть другим):
{City("Kazan"), City("Moscow")}

Свойства множеств

Тип set в Python является подтипом Collection (про коллекции), из данного факта есть три важных следствия:

• Определена операция проверки принадлежности элемента множеству
• Можно получить количество элементов в множестве
• Множества являются iterable-объектами

Принадлежность множеству

Проверить принадлежит ли какой-либо объект множеству можно с помощью оператора in.

Это один из самых распространённых вариантов использования множеств. Такая операция выполняется в среднем за O(1) с теми же оговорками, которые существуют для хеш-таблиц.

tremendously_huge_set = {"red", "green", "blue"}
if "green" in tremendously_huge_set:
    print("Green is there!")
else:
    print("Unfortunately, there is no green...")
# Вывод:
Green is there!
if "purple" in tremendously_huge_set:
    print("Purple is there!")
else:
    print("Unfortunately, there is no purple...")
# Вывод:
Unfortunately, there is no purple...

Мощность множества

Мощность множества – это характеристика множества, которая для конечных множеств просто означает количество элементов в данном множестве. Для бесконечных множеств всё несколько сложнее.

even_numbers = {i for i in range(100) if i % 2 == 0}
# Мощность множества
cardinality = len(even_numbers)
print(cardinality)
# Вывод:
50

Перебор элементов множества

Как уже было отмечено выше, множества поддерживают протокол итераторов, таким образом любое множество можно использовать там, где ожидается iterable-объект.

colors = {"red", "green", "blue"}
# Элементы множества можно перебрать с помощью цикла for
for color in colors:
    print(color)
# Вывод (порядок может быть другим):
red
green
blue
# Множества можно использовать там, где ожидается iterable-объект
color_counter = dict.fromkeys(colors, 1)
print(color_counter)
# Вывод (порядок может быть другим):
{"green": 1, "red": 1, "blue": 1}

Отношения между множествами

Между множествами существуют несколько видов отношений, или другими словами взаимосвязей. Давайте рассмотрим возможные отношения между множествами в этом разделе.

Равные множества

Тут всё довольно просто – два множества называются равными, если они состоят из одних и тех же элементов. Как следует из определения множества, порядок этих элементов не важен.

my_fruits = {"banana", "apple", "orange", "orange"}
your_fruits = {"apple", "apple", "banana", "orange", "orange"}
print(my_fruits == your_fruits)
# Вывод:
True

Непересекающиеся множества

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

even_numbers = {i for i in range(10) if i % 2 == 0}
odd_numbers = {i for i in range(10) if i % 2 == 1}
# Очевидно, что множества чётных и нечётных чисел не пересекаются
if even_numbers.isdisjoint(odd_numbers):
    print("Множества не пересекаются!")
# Вывод:
Множества не пересекаются!

Подмножество и надмножество

Подмножество множества S – это такое множество, каждый элемент которого является также и элементом множества S. Множество S в свою очередь является надмножеством исходного множества.

# Множество чисел Фибоначчи меньших 100
fibonacci_numbers = {0, 1, 2, 3, 34, 5, 8, 13, 21, 55, 89}
# Множество натуральных чисел меньших 100
natural_numbers = set(range(100))
# Множество чисел Фибоначчи является подмножеством множества 
# натуральных чисел
if fibonacci_numbers.issubset(natural_numbers):
    print("Подмножество!")
# Вывод:
Подмножество!
# В свою очередь множество натуральных чисел является
# надмножеством множества чисел Фибоначчи
if natural_numbers.
  issuperset(fibonacci_numbers):
    print("Надмножество!")
# Вывод:
Надмножество!

Пустое множество является подмножеством абсолютно любого множества.

empty = set()
# Методы issubset и issuperset могут принимать любой iterable-объект
print(
    empty.issubset(range(100))
    and empty.issubset(["red", "green", "blue"])
    and empty.issubset(set())
)
# Вывод:
True

Само множество является подмножеством самого себя.

natural_numbers = set(range(100))
if natural_numbers.issubset(natural_numbers):
    print("Подмножество!")
# Вывод:
Подмножество!

Операции над множествами

Рассмотрим основные операции, опредяляемые над множествами.

Объединение множеств

Объединение множеств – это множество, которое содержит все элементы исходных множеств. В Python есть несколько способов объединить множества, давайте рассмотрим их на примерах.

my_fruits = {"apple", "orange"}
your_fruits = {"orange", "banana", "pear"}
# Для объединения множеств можно использовать оператор `|`,
# оба операнда должны быть объектами типа set
our_fruits = my_fruits | your_fruits
print(our_fruits)
# Вывод (порядок может быть другим):
{"apple", "banana", "orange", "pear"}
# Также можно использовать ментод union. 
# Отличие состоит в том, что метод union принимает не только
# объект типа set, а любой iterable-объект
you_fruit_list: list = list(your_fruits)
our_fruits: set = my_fruits.union(you_fruit_list)
print(our_fruits)
# Вывод (порядок может быть другим):
{"apple", "banana", "orange", "pear"}

Добавление элементов в множество

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

colors = {"red", "green", "blue"}
# Метод add добаляет новый элемент в множество
colors.add("purple")
# Добавление элемента, который уже есть в множестве, не изменяет
# это множество
colors.add("red")
print(colors)
# Вывод (порядок может быть другим):
{"red", "green", "blue", "purple"}
# Метод update принимает iterable-объект (список, словарь, генератор и т.п.)
# и добавляет все элементы в множество
numbers = {1, 2, 3}
numbers. update(i**2 for i in [1, 2, 3])
print(numbers)
# Вывод (порядок может быть другим):
{1, 2, 3, 4, 9}

Пересечение множеств

Пересечение множеств – это множество, в котором находятся только те элементы, которые принадлежат исходным множествам одновременно.

def is_prime(number: int) -> bool:
    """ Возвращает True, если number - это простое число
    """
    assert number > 1
    return all(number % i for i in range(2, int(number**0.5) + 1))
def is_fibonacci(number: int) -> bool:
    """ Возвращает True, если number - это число Фибоначчи
    """
    assert number > 1
    a, b = 0, 1
    while a + b < number:
        a, b = b, a + b
    return a + b == number
# Множество простых чисел до 100
primes = set(filter(is_prime, range(2, 101)))
# Множество чисел Фибоначчи до 100
fibonacci = set(filter(is_fibonacci, range(2, 101)))
# Множество простых чисел до 100, которые одновременно являются
# числами Фибоначчи
prime_fibonacci = primes.intersection(fibonacci)
# Или используя оператор `&`, который определён для множеств
prime_fibonacci = fibonacci & primes
print(prime_fibonacci)
# Вывод (порядок может быть другим):
{2, 3, 5, 13, 89}

При использовании оператора & необходимо, чтобы оба операнда были объектами типа set. Метод intersection, в свою очередь, принимает любой iterable-объект. Если необходимо изменить исходное множество, а не возращать новое, то можно использовать метод intersection_update, который работает подобно методу intersection, но изменяет исходный объект-множество.

Разность множеств

Разность двух множеств – это множество, в которое входят все элементы первого множества, не входящие во второе множество.

i_know: set = {"Python", "Go", "Java"}
you_know: dict = {
    "Go": 0.4, 
    "C++": 0.6, 
    "Rust": 0.2, 
    "Java": 0.9
}
# Обратите внимание, что оператор `-` работает только
# для объектов типа set
you_know_but_i_dont = set(you_know) - i_know
print(you_know_but_i_dont)
# Вывод (порядок может быть другим):
{"Rust", "C++"}
# Метод difference может работать с любым iterable-объектом,
# каким является dict, например
i_know_but_you_dont = i_know.difference(you_know)
print(i_know_but_you_dont)
# Вывод:
{"Python"}

Удаление элементов из множества

Удаление элемента из множества можно рассматривать как частный случай разности, где удаляемый элемент – это одноэлементное множество. Следует отметить, что удаление элемента, как и в аналогичном случае с добавлением элементов, изменяет исходное множество. Удаление одного элемента из множества имеет вычислительную сложность O(1).

fruits = {"apple", "orange", "banana"}
# Удаление элемента из множества. Если удаляемого элемента
# нет в множестве, то ничего не происходит
fruits.discard("orange")
fruits.discard("pineapple")
print(fruits)
# Вывод (порядок может быть другим):
{"apple", "banana"}
# Метод remove работает аналогично discard, но генерирует исключение,
# если удаляемого элемента нет в множестве
fruits.remove("pineapple")  # KeyError: "pineapple"

Также у множеств есть метод differenсe_update, который принимает iterable-объект и удаляет из исходного множества все элементы iterable-объекта. Этот метод работает аналогично методу difference, но изменяет исходное множество, а не возвращает новое.

numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
even_numbers_under_100 = (i for i in range(1, 101) if i % 2 == 0)
numbers. , также существует два специальных метода – symmetric_difference и symmetric_difference_update. Оба этих метода принимают iterable-объект в качестве аргумента, отличие же состоит в том, что symmetric_difference возвращает новый объект-множество, в то время как symmetric_difference_update изменяет исходное множество.
non_positive = {-3, -2, -1, 0}
non_negative = range(4)
non_zero = non_positive.symmetric_difference(non_negative)
print(non_zero)
# Вывод (порядок может быть другим):
{-1, -2, -3, 1, 2, 3}
# Метод symmetric_difference_update изменяет исходное множество
colors = {"red", "green", "blue"}
colors.symmetric_difference_update(["green", "blue", "yellow"])
print(colors)
# Вывод (порядок может быть другим):
{"red", "yellow"}

Заключение
Я надеюсь, мне удалось показать, что Python имеет очень удобные встроенные средства для работы с множествами. На практике это часто позволяет сократить количество кода, сделать его выразительнее и легче для восприятия, а следовательно и более поддерживаемым. Я буду рад, если у вас есть какие-либо конструктивные замечания и дополнения.

Полезные ссылки
Множества (Статья на Википедии)
Документация по типу set
Iterable-объекты (Глоссарий Python)
Hashable-объекты (Глоссарий Python)
Sets in Python
Set Theory: the Method To Database Madness
Страница не найдена — ПриМат
По данному адресу ничего не найдено. Попробуйте воспользоваться поиском.
 Искать:
© 2012-2016: Нохум-Даниэль Блиндер  (11), Анастасия Лозинская  (10), Елизавета Савицкая  (8), Игорь Любинский  (8), Юлия Стерлянко  (8), Денис Стехун  (8), Валентин Малявко  (8), Константин Берков  (7), Олег Шпинарев  (7), Александр Базан  (7), Анна Чалапчий  (7), Кирилл Волков  (6), Татьяна Корнилова  (6), Влад Радзивил  (6), Максим Швандт  (6), Людмила Рыбальченко  (6), Даниил Радковский  (5), Влад Недомовный  (5), Александр Онищенко  (5), Андрей Метасов  (5), Денис Базанов  (5), Александр Ковальский  (5), Александр Земсков  (5), Марина Чайковская  (5), Екатерина Шибаева  (5), Мария Корень  (5), Анна Семененко  (5), Мария Илларионова  (5), Сергей Черкес  (5), Алиса Ворохта  (5), Валерия Заверюха  (5), Елизавета Снежинская  (5), Вадим Покровский  (5), Руслан Авсенин  (4), Екатерина Фесенко  (4), Дмитрий Заславский  (4), Алина Малыхина  (4), Андрей Лисовой  (4), Полина Сорокина  (4), Кирилл Демиденко  (4), Дмитрий Стеценко  (4), Александр Рапчинский  (4), Святослав Волков  (4), Иван Мясоедов  (4), Владислав Стасюк  (4), Алёна Гирняк  (4), Николай Царев  (4), Валентин Цушко  (4), Павел Жуков  (4), Роман Бронфен-Бова  (4), Артём Романча  (4), Анна Шохина  (4), Иван Киреев  (4), Никита Савко  (4), Кондрат Воронов  (4), Алина Зозуля  (4), Иван Чеповский  (4), Артем Рогулин  (4), Игорь Чернега  (4), Даниил Кубаренко  (4), Ольга Денисова  (4), Татьяна Осипенко  (4), Яков Юсипенко  (4), Ольга Слободянюк  (4), Стас Коциевский  (3), Елизавета Севастьянова  (3), Павел Бакалин  (3), Антон Локтев  (3), Андрей-Святозар Чернецкий  (3), Николь Метри  (3), Евелина Алексютенко  (3), Константин Грешилов  (3), Марина Кривошеева  (3), Денис Куленюк  (3), Константин Мысов  (3), Мария Карьева  (3), Константин Григорян  (3), Колаев Демьян  (3), Станислав Бондаренко  (3), Ильдар Сабиров  (3), Владимир Дроздин  (3), Кирилл Сплошнов  (3), Карина Миловская  (3), Дмитрий Козачков  (3), Мария Жаркая  (3), Алёна Янишевская  (3), Александра Рябова  (3), Дмитрий Байков  (3), Павел Загинайло  (3), Томас Пасенченко  (3), Виктория Крачилова  (3), Таисия Ткачева  (3), Владислав Бебик  (3), Илья Бровко  (3), Максим Носов  (3), Филип Марченко  (3), Катя Романцова  (3), Илья Черноморец  (3), Евгений Фищук  (3), Анна Цивинская  (3), Михаил Бутник  (3), Станислав Чмиленко  (3), Катя Писова  (3), Дмитрий Дудник  (3), Дарья Кваша  (3), Игорь Стеблинский  (3), Артем Чернобровкин  (3), Виктор Булгаков  (3), Дмитрий Мороз  (3), Богдан Павлов  (3), Игорь Вустянюк  (3), Андрей Яроцкий  (3), Лаура Казарян  (3), Екатерина Мальчик  (3), Анатолий Осецимский  (3), Иван Дуков  (3), Дмитрий Робакидзе  (3), Вячеслав Зелинский  (3), Данила Савчак  (3), Дмитрий Воротов  (3), Стефания Амамджян  (3), Валерия Сиренко  (3), Георгий Мартынюк  (3), Виктор Иванов  (3), Вячеслав Иванов  (3), Валерия Ларикова  (3), Евгений Радчин  (3), Андрей Бойко  (3), Милан Карагяур  (3), Александр Димитриев  (3), Иван Василевский  (3), Руслан Масальский  (3), Даниил Кулык  (3), Андрей Данилов  (2), Даниил Крутоголов  (2), Наталия Писаревская  (2), Дэвид Ли  (2), Александр Коломеец  (2), Александра Филистович  (2), Евгений Рудницкий  (2), Олег Сторожев  (2), Евгения Максимова  (2), Алексей Пожиленков  (2), Юрий Молоканов  (2), Даниил Кадочников  (2), Александр Колаев  (2), Александр Гутовский  (2), Павел Мацалышенко  (2), Таня Спичак  (2), Радомир Сиденко  (2), Владислав Шиманский  (2), Илья Балицкий  (2), Алина Гончарова  (2), Владислав Шеванов  (2), Андрей Сидоренко  (2), Александр Мога  (2), Юлия Стоева  (2), Александр Розин  (2), Надежда Кибакова  (2), Майк Евгеньев  (2), Евгений Колодин  (2), Денис Карташов  (2), Александр Довгань  (2), Нина Хоробрых  (2), Роман Гайдей  (2), Антон Джашимов  (2), Никита Репнин  (2), Инна Литвиненко  (2), Яна Юрковская  (2), Гасан Мурадов  (2), Богдан Подгорный  (2), Алексей Никифоров  (2), Настя Филипчук  (2), Гук Алина  (2), Михаил Абабин  (2), Дмитрий Калинин  (2), Бриткариу Ирина  (2), Никита Шпилевский  (2), Алексей Белоченко  (2), Юлиана Боурош  (2), Никита Семерня  (2), Владимир Захаренко  (2), Дмитрий Лозинский  (2), Яна Колчинская  (2), Юрий Олейник  (2), Кирилл Бондаренко  (2), Елена Шихова  (2), Татьяна Таран  (2), Наталья Федина  (2), Настя Кондратюк  (2), Никита Гербали  (2), Сергей Запорожченко  (2), Николай Козиний  (2), Георгий Луценко  (2), Владислав Гринькив  (2), Александр Дяченко  (2), Анна Неделева  (2), Никита Строгуш  (2), Настя Панько  (2), Кирилл Веремьев  (2),
 Набор операций 
 Объединение   двух множеств — это множество, содержащее все элементы из обоих этих множеств.
 Написано \(A\чашка B\) и определено
 \[A\cup B = \{x \mid x\in A\vee x\in B\}\,.\]
 Например,
 \[\{1,2,3,4\}\чашка\{3,4,5,6\} = \{1,2,3,4,5,6\}\,\\
 \mathbf{R} = \mathbf{Q} \cup \overline{\mathbf{Q}}\,.\]
 Пересечение   двух множеств — это множество, содержащее элементы, которые входят в оба этих множества.
 Написано \(A\cap B\) и определено
 \[A\cap B = \{x \mid x\in A\клин x\in B\}\,\\
 \mathbf{Q} \cap \overline{\mathbf{Q}}=\emptyset\,.\]
 Например,
 \[\{1,2,3,4\}\cap\{3,4,5,6\} = \{3,4\}\,.\]
  Разница  между двумя наборами — это набор значений в одном, но не в другом:
 \[A-B = \{x \mid x\in A\text{ и } x\notin B\}\,.\]
 Например,
 \[\{1,2,3,4\}-\{3,4,5,6\} = \{1,2\}\,\\
 \overline{\mathbf{Q}} = \mathbf{R}-\mathbf{Q} \,.\]
 Также иногда пишут \(A\setminus B\).
  Теорема:  Для любых множеств \(|AB|\le|A|\).
  Доказательство:  Предположим, что \(|A-B|>|A|\). Тогда должен быть элемент \(x\) с \(x\in(AB)\), но \(x\не в A\). Таким образом, \(AB\not\subseteq A\).
 Но из определения разности множества мы видим, что
\[ A-B = \{x \mid x\in A\text{ и } x\notin B\} \subseteq \{x \mid x\in A\} =A\,. \]
Это противоречие, поэтому \(|AB|\le|A|\).∎
 С подобными доказательствами мы могли бы доказать следующее:
  Теорема:  Для любых множеств \(|A\cap B|\le|A|\) и \(|A\cap B|\le|B|\).
  Теорема:  Для любых множеств \(|A\cup B|\ge|A|\) и \(|A\cup B|\ge|B|\).
 При выполнении операций над множествами нам часто нужно определить универсальный набор   , \(U\).
 Как и домен для квантификаторов, это набор всех возможных значений, с которыми мы работаем.
 Часто не определяется явно, а подразумевается в зависимости от проблемы, которую мы рассматриваем.
 напр. когда мы работаем с действительными числами, вероятно, \(U=\mathbf{R}\).
  дополнение  набора \(S\) записывается как \(\overline{S}\) и представляет собой набор всех значений , а не  в \(S\):
 \[\overline{S} = \{x\mid x\notin S\} = U-S \,.\]
 Стандартная запись иррациональных чисел теперь должна иметь большой смысл: с универсальным набором \(\mathbf{R}\) иррациональные числа (\(\overline{\mathbf{Q}}\)) являются дополнением рациональные числа (\(\mathbf{Q}\)).
  Теорема:  Для любого множества \(S\cap\overline{S}=\emptyset\).
  Доказательство:  Предположим противное, что существует элемент \(x\in S\cap\overline{S}\). Тогда по определению операторов
 \[
 х\in S\cap\overline{S}\\
 х\in S \клин х\in\overline{S} \\
 х\in S \клин х\notin{S}\,.
 \]
 Это противоречие, поэтому мы должны иметь \(S\cap\overline{S}=\emptyset\).∎
 Обратите внимание на сходство между соответствующим набором и логическими операторами: \(\vee,\cup\) и \(\wedge,\cap\) и \(\overline{\mbox{S}},\neg\).
 Это больше, чем похожие символы.
 Вот несколько важных наборов идентификаторов:
 Имя
 Идентификация
 Идентификация
 \(A\cap{U}= A\\A\cup\emptyset= A\)
 Доминирование
 \(А\чашка{U} = {U}\\A\cap\emptyset= \emptyset\)
 Идемпотент
 \(A\cap A= A\\A\cup A= A\)
 Двойное отрицание
 \ (\overline{(\overline{A})}= А\)
 Коммутативный
 \(A\чашка B = B\чашка A\\A\крышка B = B\крышка A\)
 Ассоциативный
 \((A\чашка B)\чашка C = A\cup(B\cup C)\\(A\cap B)\cap C = A\cap(B\cap C)\)
 Распределительный
 \(A\cup(B\cap C) =(A\чашка B)\крышка(A\чашка C)\\A\крышка(B\чашка C) = (A\крышка B)\чашка(A\крышка B)\)
 Закон де Моргана
 \(\overline{A\cap B}=\overline{A} \cup \overline{B}\\\overline{A\cup B}= \overline{A} \cap \overline{B}\)
 Поглощение
 \(A\чашка(A\крышка B) = A \\ A\крышка(A\чашка B) = A\)
 Отрицание
 \(A\cup\overline{ A} = {U}\\A\cap\overline{A} = \emptyset\)
 Выглядит знакомо? Это таблица логических эквивалентов с некоторым поиском и заменой.
 В качестве примера мы можем доказать один из законов Де Моргана (книга доказывает другой).
 Мы будем осторожны с этим и будем манипулировать нотацией построителя наборов.
  Теорема:  Для любых множеств \(\overline{A\cup B}= \overline{A} \cap \overline{B}\).
  Доказательство:  По определению операций множества,
 \[\начать{выравнивать*}
 \overline{A\чашка B}
 &= \{x\mid x\notin (A\cup B)\} \\
 &= \{x\mid \neg(x \in (A\cup B))\} \\
 &= \{x\mid \neg(x \in A\vee x\in B)\} \\
 &= \{x\mid\neg(x\in A)\клин \neg(x\in B)\} \\
 &= \{x\mid x \in \overline{A}\wedge x \in \overline{B} )\} \\
 &= \{x\mid x \in (\overline{A}\cap\overline{B}))\} \\
 &= \overline{A}\cap\overline{B}\,.\quad{}∎
 \конец{выравнивание*}\]
 Можно было бы привести и менее формальное доказательство. (Для этого см. раздел 2.2, пример 10.)
 Это тот случай, когда, вероятно, проще быть более формальным: писать все детали в предложениях настолько мучительно, что семь шагов в этом доказательстве приятнее читать. (См. также пример 10.)
 Это доказательство может подсказать, почему таблицы эквивалентностей и множественных тождеств так похожи.
 Для любой из операций над множествами мы можем использовать нотацию построителя множеств, а затем использовать логические эквивалентности для управления условиями.
 Так как мы проделываем те же манипуляции, то и таблицы у нас получились одинаковые.
 Будьте осторожны с другими операциями. То, что это сработало для них, не означает, что вы можете считать, что все одинаково. Не существует логической версии установленного различия или установленной версии исключающего или (по крайней мере, насколько мы определили).
  Теорема:  Для любых множеств \(AB = A\cap\overline{B}\).
  Менее формальное доказательство:  Набор \(A-B\) представляет собой значения из \(A\) с удаленными значениями из \(B\).
 Набор \(\overline{B}\) — это набор всех значений, не входящих в \(B\). Таким образом, пересечение с \(\overline{B}\) приводит к тому, что остаются только значения, не входящие в \(B\). То есть \(A\cap\overline{B}\) - это \(A\) со всеми удаленными значениями из \(B\). Таким образом, мы видим, что эти множества содержат одни и те же элементы. ∎
  Более формальное доказательство:  По определению операций над множествами
 \[\начать{выравнивать*}
 А-Б
 &= \{х\середина х\в А \клин х\не в В\} \\
 &= \{x\mid x\in A \wedge x\in \overline{B}\} \\
 &= \{x\mid x\in (A \cap \overline{B})\} \\
 &= A\cap\overline{B}\,.\quad{}∎
 \конец{выравнивание*}\]
 Я думаю, что любое из этих доказательств является действительным.
 «Менее формальная» версия должна быть написана достаточно тщательно, чтобы убедить читателя (или ТА в вашем случае).
 В «более формальной» версии больше шагов и отсутствует интуитивная причина (она может помочь вам вспомнить почему).
 Мы можем использовать тождества множеств для доказательства других фактов о множествах. Например:
  Теорема:  \(A-(B\чашка C)= (A-B)\cap(A-C)\).
  Доказательство:  Для множеств \(A,B,C\) из приведенной выше теоремы имеем
 \[\начать{выравнивать*}
 А-(В\чашка С)
 &= A\cap \overline{B\cup C} \\
 &= A\cap \overline{B}\cap \overline{C} \\
 &= A\cap \overline{B}\cap A\cap \overline{C} \\
 &= (A-B)\cap (A-C)\,.\quad{}∎
 \конец{выравнивание*}\]
 Эти тождества должны убедить вас в том, что порядок объединения и пересечения не имеет значения (точно так же, как сложение, умножение, конъюнкция и дизъюнкция: все они являются коммутативными операциями).
 Таким образом, мы можем написать их кучу без скобок, как сложение/умножение/соединение/дизъюнкция:
 \[A\чашка B\чашка C \чашка D\,\\A\крышка B\крышка C \крышка D\,.\]
 Если нам нужно выполнить объединение/пересечение множества вещей, иногда используется такое обозначение, как суммирование.
 Например, предположим, что в этом семестре ZJU предлагает \(n\) курсов. {n} S_i\,.\]
 Студенты берут 92\,.\]
 Теория множеств | Символы, примеры и формулы 
 Ключевые люди:
 Георг Кантор
Пол Эрдёш
Джон фон Нейман
Сол Крипке
Станислав Улам
 Похожие темы:
 аксиома выбора
Диаграмма Венна
Лемма Цорна
гипотеза континуума
Теорема Кантора
 Просмотреть весь связанный контент →
  теория множеств  , раздел математики, изучающий свойства четко определенных наборов объектов, которые могут иметь или не иметь математическую природу, например, числа или функции. Теория менее ценна в прямом применении к обычному опыту, чем в качестве основы для точной и гибкой терминологии для определения сложных и изощренных математических понятий.
 Между 1874 и 1897 годами немецкий математик и логик Георг Кантор создал теорию абстрактных множеств сущностей и превратил ее в математическую дисциплину. Эта теория выросла из его исследований некоторых конкретных проблем, касающихся определенных типов бесконечных множеств действительных чисел. Множество, писал Кантор, есть совокупность определенных, различимых объектов восприятия или мысли, рассматриваемых как единое целое. Объекты называются элементами или членами множества.
 Революционный аспект теории заключался в том, что бесконечные множества рассматривались как математические объекты, равноправные с теми, которые можно построить за конечное число шагов. Со времен античности большинство математиков старательно избегали введения в свои рассуждения актуальной бесконечности (т. е. множеств, содержащих бесконечность объектов, мыслимых как существующие одновременно, по крайней мере, в мыслях). Поскольку такое отношение сохранялось почти до конца XIX века, работы Кантора подвергались многочисленной критике в том смысле, что они касались вымыслов, более того, что они посягали на область философов и нарушали принципы религии. Однако как только начали находить применение анализу, отношение стало меняться, и к 189 г.Идеи и результаты Кантора получили признание. К 1900 году теория множеств была признана отдельной отраслью математики.
 Однако именно тогда были обнаружены некоторые противоречия в так называемой наивной теории множеств. Чтобы устранить такие проблемы, была разработана аксиоматическая основа теории множеств, аналогичная той, которая была разработана для элементарной геометрии. Степень успеха, достигнутого в этом развитии, а также нынешний статус теории множеств хорошо отражены в трудах Николя Бурбаки.0034 Éléments de mathématique  (начало 1939 г.; «Элементы математики»): «В настоящее время известно, что можно логически вывести практически всю известную математику из одного источника, Теории множеств».
 Викторина "Британника"
 Числа и математика
 Введение в наивную теорию множеств 
 Фундаментальные концепции множеств 
 В наивной теории множеств множество представляет собой совокупность объектов (называемых членами или элементами), которые рассматриваются как единый объект. Чтобы указать, что объект  x  является элементом множества  A  пишется  x  ∊  A  , тогда как  x  ∉  A  указывает, что  x  не является элементом 9003 4 А  . Набор может быть определен правилом членства (формулой) или перечислением его членов в фигурных скобках. Например, множество, заданное правилом «простые числа меньше 10», также может быть задано как {2, 3, 5, 7}. В принципе, любое конечное множество может быть определено явным списком его элементов, но для определения бесконечных множеств требуется правило или шаблон для указания членства; например, многоточие в {0, 1, 2, 3, 4, 5, 6, 7, …} указывает, что список натуральных чисел ℕ можно продолжать бесконечно. Пустой (или недействительный, или нулевой) набор, обозначенный {} или Ø, вообще не содержит элементов. Тем не менее, он имеет статус набора.
 Набор  A  называется подмножеством набора  B  (обозначается  A  ⊆  B  ), если все элементы  A  также являются элементами  B  . Например, любое множество является подмножеством самого себя, а Ø является подмножеством любого множества. Если оба  A  ⊆  B  и  B  ⊆  A  , то  A  и  B  имеют точно такие же члены.
No related posts.