Основные определения. Множество – это некоторый набор объектов, называемых элементами
Множество – это некоторый набор объектов, называемых элементами. Оно обозначается следующим образом
А={a1,a2,…,an},
где А – множество, a1, a2,…, an - его элементы. Например, множество А может состоять из натуральных чисел 1, 2,…,6 при этом его элементами будут a1=1, a2=2, …, a6=6.
Любой набор, каждый элемент которого принадлежит множеству А, является его подмножеством, так В={1, 2, 3} – подмножество А={1, 2, 3, 4, 5, 6} обозначается ВÌА. Любое множество по этому определению является собственным подмножеством.
Все рассматриваемые в дискретной математике множества содержат элементы, принадлежащие наибольшему множеству S, называемому пространством элементов. Следовательно, все рассматриваемые множества являются подмножествами S.
Пример. Пусть S={1, 2, …, 6}. Рассмотрим формирование подмножеств множества S. С учетом пустого подмножества Æ в рассматриваемом множестве S может быть выделено в общей сложности 26=64 подмножества:
Æ, {1}, …, {6}, {1, 2},……,{1,2,6},…, S.
В общем случае если множество S содержит n элементов, в нем можно выделить 2n подмножеств.
Одной из причин применения теории множеств в дискретной математике является то, что для множеств определены важные преобразования, которые имеют простое геометрическое представление. Это представление носит название диаграммы Эйлера-Венна и в ней пространство S изображается в виде квадрата, а различные множества в виде плоских фигур, ограниченных замкнутыми линиями. Использование таких диаграмм рассмотрим на примере описания подмножеств
С Ì В Ì А
S
А
С
В
Обычно каждое натуральное число воспринимается как то общее, что присуще любой совокупности М, состоящей из m предметов ; об этом делают запись вида m = |М|. Если все m предметов из совокупности М попарно различны, то совокупность эту именуют множеством, а также m-элементным множеством, при этом число m называют кардинальным числом, а также мощностью множества М.
Если |М| = 0, то говорят, что М - пустое множество, и пишут М = Æ. Если среди предметов, входящих в совокупность М, имеются одинаковые, то такую совокупность называют мультимножеством.
Говоря о множестве М, подразумевают, что М состоит из элементов. Множество, состоящие из конечного числа элементов, т.е. имеющие конечную мощность называют конечным. Множество, не являющееся конечным, называют бесконечным. Если x есть элемент множества М, то этот факт записывают в виде x М и говорят « принадлежит М». Запись означает, что рассматривается множество, состоящее из элементов, обладающим свойством Р, а запись М1 =íx ÎМ: P(x) ý и аналогичная запись М1 = íx Î М | P(x)ý означают, что рассматривается часть множества М, причем x Î М1 Û (x Î М & Р(x)). (Обозначения: АÞВ - из утверждения А следует утверждение В; АÛВ - из А следует В и наоборот ).
Возможно, что М1 = 0, либо М1 = М. В любом случае о множестве М1 говорят, что оно суть подмножествомножества М, и пишут М1 Í М. Если М1 Í М и М Í М1, то пишут М1 = М и называют М1 и М равными множествами. Если М1 Í М, но М1 ¹ М, то пишут М1 Ì М, т.е. М1 строго включено в М. Если же просто М1 Í М, то говорят о включенииМ1 в М.
Пусть А Í R . Тогда в дальнейшем А+ = í x Î А : x > 0 ý, так что R+ = í x Î R : x > 0ý, Z+ = íx Î Z : x > 0ý = í1,2,...,ý = N+.
Если хотя бы одним способом можно пронумеровать (пересчитать) с помощью всех натуральных чисел n Î N все элементы бесконечного множества М, то говорят, что М имеет счетную мощность или является счетным множеством, и пишут |М| = |N| . Вместо |N| пишут иногда одну букву a (готическое а). Например, множество Z счетно, ибо это легко усматривается в следующей записи чисел друг под другом :
Z = í...,-3,-2,-1,0,1,2,3,...ý,
N = í...,6,4,2,0,1,3,5,...ý.
В общем случае если между элементами множеств X и Y можно установить взаимно однозначное соответствие (т.е. каждому элементу x Î X поставить в соответствие один и только один элемент y Î Y, но так, чтобы при этом каждому y Î Y также будет поставлен в соответствие некоторый элемент x Î X), то говорят, что множества X и Y имеют одно и то же кардинальное число, или имеют одинаковую мощность, или равномощны, и пишут |X| = |Y|. Запись |X| < |Y| означает, что |X| ¹ |Y|, но для некоторого подмножества Y1 Ì Y выполнятся |X| = =|Y1|. Например, множество Q имеет счетную мощность, а множество R имеет более высокую мощность (континуальную мощность c ), так что а = |N| = |Q| < |R| = c, где c - готическое С. Итак, 0,1,2,... - все конечные кардинальные числа, а, с - два бесконечных кардинальных числа ; отметим, что бесконечных кардинальных чисел существует сколь угодно много.
Дата добавления: 2015-10-05; просмотров: 517;