Докажем что множества включены друг в друга (доказательство «если-то»)

Докажем что первое множество полнь

,

таким образом

В обратную сторону:

таким образом

Так как и , то

Характеристические функции

Докажем что

Характеристическая функции левой части:

Характеристическая функции правой части:

Характеристические функции совпадают, значит и тождество верно.

Мощность объединения множеств (формула включений и исключений):

….

Кортеж (вектор) – упорядоченная последовательность элементов. Элементы вектора – координаты или компоненты. Число компонент – размерность вектора.

Обозначение – в круглых скобках (иногда – в треугольных).

Проекция вектора на ось i – его i-й компонент.

Декартово (прямое) произведение множеств

Называется множество всех векторов (a,b), таких что и :

Мощность прямого произведения n множеств равна произведению мощностей соответствующих множеств.

Доказательство…. (Метод мат. индукции)

Отношения.

n-местным отношением R на множествах называется подмножество прямого произведения .

Если множества совпадают, то говорят что задаёт n-арные отношения.

При n = 2 отношение называется бинарным.

Далее будем рассматривать только бинарные отношения определенные на А.

Отношение может быть записано в виде R(a, b) или aRb.

Так же используется обозначение

Для любого множества А определены отношения:

Тождественное отношение .

Универсальное отношение .

Пустое отношение.

Операции на отношениях:

Пересечение

Объединение

Произведение

Дополнение:

Обратное отношение к R:

Свойства отношений:

Рефлексивность: xRx, для всех x

Симметричность: xRy => yRx

Транзитивность: xRy, yRz => xRz

Антисимметричность: xRy, yRx => x=y

Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности разбивает на семейство подмножеств (классов разбиения). Каждый его элемент принадлежит некоторому из этих подмножеств (именно – R(a)). Совокупность всех классов разбиения обозначается A/R и называется фактор-множеством множества A относительно эквивалентности R.

[a], обозначает класс из A/R к которому принадлежит a. Сам элемент a называют представителем этого класса.

Квазипорядком называют отношение, которое рефлексивно и транзитивно.

Частичным порядком (или просто порядком) называется отношение, которое рефлексивно, антисимметрично и транзитивно.

Порядок обозначается символом .

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

Порядок называется линейным, если для любых либо a либо b .

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

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

Каждое подмножество A’ множества частично упорядоченного множества обладает индуцированным порядком. Если порядок A’ линеен, то множество A’ называется цепью вA.

Максимальный, минимальный, наибольший, наименьший элемент.

Нижняя грань ( , точная нижняя грань , верхняя грань , точная верхняя грань .

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

Функции

Функцией из множества А во множество B называется произвольное соответствие, которое сопоставляет каждому элементу а множества A элемент f(a) множества B.

b = f(a) называется значением f на a.

Если есть и , то g g(f(a))

Образы и прообразы.