Материал на экзамен

Теория множеств

Определение и понятие

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

Частично упорядоченное множество — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определенной последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».

В качестве абстрактного примера можно привести совокупность под-

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

Отношение частичного порядка обычно обозначают символом , по аналогии с отношением «меньше либо равно» на множестве действи-

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

Если и , то пишут , и говорят, что меньше , или что строго подчинен .

Иногда, чтобы отличить произвольный порядок на некотором множе-

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

Конечное множество — множество, количество элементов которого конечно, то есть, существует неотрицательное целое число k, равное количеству элементов этого множества. В противном случае множество называется бесконечным. Например,

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

Бесконечное множество — множество, не являющееся конечным. Можно дать ещё несколько эквивалентных определений бесконечного множества:

•Множество, в котором для любого натурального числа найдётся конечное подмножество из элементов.

•Множество, в котором найдётся счётное подмножество.

•Множество, в котором найдётся подмножество, равномощное некоторому (ненулевому) предельному ординалу.

•Множество, для которого существует биекция с некоторыми его собственными подмножествами.

Для любого бесконечного множества существует множество с ещё большей мощностью — таким образом, не существует бесконечного множества наибольшей мощности. Мощности бесконечных множеств

называются алефами и обозначаются где индекс пробегает все порядковые числа. Мощности бесконечных множеств составляют вполне упорядоченный класс — наименьшей мощностью бесконеч-

Над множествами определены следующие операции:

•объединение, обозначается как — множество, содержащее все элементы из и ,

•разность, обозначается как , реже — множество элементов , не входящих в ,

•дополнение, обозначается как или — множество всех элементов, не входящих в (в системах, использующих универсальное множество),

•пересечение, обозначается как — множество из элементов, содержащихся как в , так и в ,

•симметрическая разность, обозначается как , реже

— множество элементов, входящих только в одно из множеств — или .

Объединение и пересечение также часто рассматривают над семей-

ствами множеств, обозначаются и и составляют, соответственно, объединение всех множеств, входящих в семейство и пересечение всех множеств, входящих в семейство.

Объединение и пересечение коммутативны, ассоциативны и идемпотентны. В зависимости от выбора системы аксиом и наличия дополнения алгебра множеств (относительно объединения и пересечения) может образовывать дистрибутивную решётку, полную дистрибутивную решётку, булеву алгебру. Для визуализации операций над множествами использу-

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

Произведение двух множеств

Пусть даны два множества и . Прямое произведение множества и множества есть такое множество , элементами кото-

рого являются упорядоченные пары для всевозможных и .

Отображения произведения множеств в его множители — и

— называют координатными функциями.

Аналогично определяется произведение конечного семейства множеств.

не имеет места, но в силу существования естественного взаимно однозначного соответствия между

множествами и этим различием можно зачастую пренебречь.

Декартова степень

-я Декартова степень множества определяется для целых неотрицательных , как -кратное Декартово произведение на себя:

Обычно обозначается как или .

При положительных Декартова степень состоит из всех упорядоченных наборов элементов из длины . Так вещественное

пространство (множество кортежей из трех вещественных чисел), есть 3 степень множества вещественных чисел

При , Декартова степень по определению, содержит единственный элемент — пустой кортеж.

Прямое произведение семейства множеств

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

Отображения называются проекциями.

В частности, для конечного семейства множеств лю-

бая функция с условием эквивалентна некоторому кортежу длины , составленному из элемен-

тов множеств , так, что на -ом месте кортежа стоит элемент множества . Поэтому декартово (прямое) произведение конечного

числа множеств может быть записано так:

Проекции определяются следующим образом:

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

Симметрическую разность можно ввести двумя способами:

•симметрическая разность двух заданных множеств и — это такое множество , куда входят все те элементы первого множества, которые не входят во второе множество, а, также те элементы второго множества, которые не входят в первое множество:

•симметрическая разность двух заданных множеств и — это такое множество , куда входят все те элементы обоих множеств, которые не являются общими для двух заданных множеств.

Понятие симметрической разности можно обобщить на число множеств, большее двух.

Симметрическая разница является бинарной операцией на любом булеане;

• Симметрическая разность коммутативна:

•Симметрическая разность ассоциативна:

•Пересечение множеств дистрибутивно относительно симметрической разности:

•Пустое множество является нейтральным элементом симметрической разности:

•Любое множество обратно само себе относительно операции симметрической разности:

•В частности, булеан с операцией симметрической разности является абелевой группой;

•Булеан с операцией симметрической разности также является векторным пространством над полем

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

•

•

•

•Если роль «суммы» играет операция симметрической разности, а роль «произведения» — пересечение множеств, то множества образуют кольцо без единицы. Причем другие основные опера-

ции теории множеств, разность и объединение, можно выразить через них:

•Объединение симметрической разности с пересечением двух множеств равно объединению исходных множеств

Пусть

Тогда

Соответствием между множествами X и Y называется всякое подмножество декартова произведения этих множеств. Соответствия принято обозначать буквами P, S, T и др. Если xSy — соответствие между элементами множеств X и Y, то, согласно определению, SXY.

Поскольку соответствие — это подмножество, то его можно задать как любое множество, т. е. либо перечислив все пары элементов, находящихся в данном соответствии, либо указав характеристическое свойство элементов этого подмножества. Например, соответствие между множествами X={1, 2, 4, 6} и Y={3, 5} можно задать: 1) при помощи предложения с двумя переменными: a<b при условии, что aX, bY;

2) перечислив пары чисел, принадлежащих подмножеству декартова произведения XY: {(1, 3),(1, 5), (2, 3), (2, 5), (4, 5)}.

Отображение множеств.

Пусть X и Y — два произвольных множества.

Определение. Соответствие, при котором каждому из элементов множества X сопоставляется единственный элемент из множества Y, называется отображением.

Обозначение отображения из множества X в множество Y: X fY.

Множество X называется областью определения отображения и обозначается X=D(f).

E(f) называется множеством значений отображения, и E(f)={y Y|

x X,y=f(x)}.

Множество Γ(f) называется графиком отображения.

Γ(f)={(x,y) X×Y,y=f(x), x X,y Y}.

Пусть f — некоторое отображение из множества X в множество Y. Если x при этом отображении сопоставляется y, то y=f(x). При этом y называется образом x, или значением отображения f в точке x. А x, соответственно, прообразом элемента y.

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

Пример.

Даны два множества X={с,е,н,т,я,б,р,ь} и Y={1,2,3,4,5,9,10,11}

Отображение из множества X в множество Y имеет следующий вид: