Множество а является подмножеством в если. Понятие множества. Подмножества. Элементы комбинаторики: Сочетания

Определение:

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

Если х- элемент множества М, то обозначают: х М { х – принадлежит М}, если не принадлежит, то х ∉ М; Множество не содержащее элементов называется пустым и обозначается ∅

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

Ư. Множества, состоящие из одних и тех же элементов, называются равными и обозначаются А = В.

Если любой элемент множества В является элементом множества А, то множество В называется подмножеством множества А (частью множества А) и обозначается В ⊂ А; Отсюда следует, что любое множество является частью самого себя.

По определению пустое множество ∅ является подмножеством любого множества. Т.о. у любого множества А есть два подмножества:

Они называются несобственными подмножествами множества А. Любое множество В множества А, которое не является несобственными подмножествами А, (т.е. они отличны от А и ∅) и называются собственными подмножествами подмножества А. Множество из одного элемента а обозначается {а}.

Пример: А = {1;2;3} тогда пустое множество ∅ и само множество А является несобственными подмножествами А.

Множества:{1},{2},{3},{1;2},{1;3},{2;3} называются собственными подмножествами множества А. Совокупность всех множеств А называется его булеаном и обозначается – 2 А; В А, означает, что В А, В ≠ А. В этом случае говорят, что В строго включено в А или В является собственным подмножеством А;

В случае В ⊆ А, В = А говорят, что В нестрогое включение в А, т.е. В является несобственным подмножеством А.

Основные логические символы

ХР(х) – квантор общности (означает “для любого х выполняется

ХР(х) – квантор существования (означает “существует х, для которого выполняется Р (х)”.)

Р ⇒ Q – импликация (“из Р следует Q ”)

⟺ - эквивалентность (“тогда и только тогда”)

Р ∧ Q – конъюнкция (“Р и Q”)

Р ∨ Q – дизъюнкция (“Р или Q”)

Не Р или - отрицание Р

: = - символы присвоения (“положим”)

def – (“положим по определению”)

Используя эти символы можно записать:

1) (А = В) ⟺(( х ∈ А ⇒ х ∈ В) ∧ ( х ∈ В ⇒ х ∈ А)

2) (А ⊆ В) ⟺ ( х/х ∈А ⇒ х ∈ В)

3) (А = В) ⟺ (В ⊂ А ∧ А⊂ В)

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

Перечислением элементов: М: = { а 1 ; а 2 ; а 3 ; …; а n }

или характеристическим свойством Р(х)

(предикатом): М: = { х | Р(х) }

Например:

1) В = { х ∈ N | х < 3} означает, что В= { 1; 2}

2) А ={ х ∈ N | х +1=5} означает, что А = {4}

3) В = { х ∈ N | х M5} или {5;10;15…}

т.е. { х | Р(х) }означает, что множество элементов х множества обладает свойством Р(х)

4) М = { х ∈ N | х ­3< 5}={1;2;3;4;5;6;7}

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

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

1 0 . Объединение множеств А и В.

U

А ∪ В = { х/х ∈ А или х ∈ В} – т.е. состоит из элементов, принадлежащих хотя б одному из множеств А или В.

2 0 . Пересечение множеств А и В.

A∩B = {x/x ∈ A и x ∈ B} – т.е. состоят из элементов, принадлежащих одновременно А и В.

3º. Разность множеств А и В.

A/B = {x/x ∈ A и x ∉ B} – т.е. состоит из элементов А, не принадлежащих В.

4º. Симметрическая разность А и В (или кольцевая сумма А и В)

А Ө B = {x/x ∈ A и x ∉ B} ∪ {x/x ∈ В и x ∉ А} или {А\В ∪ В\А}

5º. Дополнение А до универсума

= U\A = {x|x ∈ Uux и x ∉ А}

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

Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которой I элемент из множества А, II элемент – из множества В, т.е. А×В = {(а, в)/а Є А ̂в Є В}

Пример: А={2;5;7;9} и В ={2;4;7},

Тогда А×В = {(2,2) ; (2,4) ; (2,7) ; (5,2) ; (5,4) ; (5,7) ; (7,2) ; (7,4) ; (7,7) ; (9,2) ; (9,4); (9,7)}

А∩В={2,7}; А∪В={2,4,5,7,9}; А/В={5,9}; В/А={4}; А Ө В={4,5,9}

Элементы множества А×В называются точками; В паре (х, у) абсцисса – х и ордината – у точки, соответствующей этой паре.

Множество точек плоскости является прямым произведением вида R×R=R 2 , где R–множество действительных чисел.

R 2 называется декартовым квадратом на R.

Элементы теории графов

Принадлежащие $A$, также принадлежит $B$. Формальное определение:

$(A\; \backslash subset\; B)\; \backslash Leftrightarrow\; \backslash forall\; x.\; (x\; \backslash in\; A\; \backslash Rightarrow\; x\; \backslash in\; B).$

Множество $B$ называется надмно́жеством множества $A$, если $A$ - подмножество $B$.

Существует два символических обозначения для подмножеств:

Обе системы обозначений используют символ $\backslash subset$ в разных смыслах, что может привести к путанице. В данной статье мы будем использовать последнюю систему обозначений.

То, что $B$ называется надмножеством $A$, часто записывают $B\; \backslash supset\; A$.

Множество всех подмножеств множества $A$ обозначается $\backslash mathcal\{P\}(A)$ и называется булеаном .

Собственное подмножество

Любое множество $B$ является своим подмножеством. Если мы хотим исключить $B$ из рассмотрения, мы пользуемся понятием со́бственного

Множество $A$ является собственным подмножеством множества $B$, если $A\; \backslash subset\; B$ и $A\; \backslash ne\; B$.

Пустое множество является подмножеством любого множества. Если мы вдобавок хотим исключить из рассмотрения пустое множество, мы пользуемся понятием нетривиа́льного подмножества, которое определяется так:

Множество $A$ является нетривиальным подмножеством множества $B$, если $A$ является собственным подмножеством $B$ и $A\; \backslash ne\; \backslash varnothing$.

Примеры

• Множества $\backslash varnothing,\; \backslash \{0\backslash \},\; \backslash \{1,3,4\backslash \}.$ $\backslash \{\; 0,1,2,3,4,5\backslash \}$
• Множества $\backslash \{\; \backslash varnothing,\; \backslash uparrow,\; moose\; \backslash \},\; \backslash \{\; \$,\%,*,\backslash uparrow\; \backslash \},\; \backslash \{\backslash varnothing\backslash \},\; \backslash varnothing$ являются подмножествами множества $\backslash \{\; \$,\; \%,\; \backslash varnothing,\; \backslash uparrow,\; *,\; moose\; \backslash \}$
• Пусть $A\; =\; \backslash \{a,b\backslash \}$, тогда $\backslash mathcal\{P\}(A)\; =\; \backslash \{\backslash varnothing,\; \backslash \{a\backslash \},\; \backslash \{b\backslash \},\; \backslash \{a,b\backslash \}\; \backslash \}$.
• Пусть $A\; =\; \backslash \{1,2,3,4,5\backslash \},\backslash ;\; B\; =\; \backslash \{1,2,3\backslash \},\backslash ;\; C\; =\; \backslash \{4,5,6,7\backslash \}$. Тогда $B\; \backslash subset\; A,\backslash ;\; C\; \backslash not\backslash subset\; A$.

Свойства

Отношение подмножества обладает целым рядом свойств .

• Отношение подмножества является отношением частичного порядка :
  • Отношение подмножества рефлексивно : $B\; \backslash subset\; B$
  • Отношение подмножества антисимметрично : $(A\; \backslash subset\; B\; \backslash ;\; \backslash and\; \backslash ;\; B\; \backslash subset\; A)\; \backslash Leftrightarrow\; (A\; =\; B)$
  • Отношение подмножества транзитивно : $(A\; \backslash subset\; B\; \backslash ;\backslash and\; \backslash ;\; B\; \backslash subset\; C)\; \backslash Rightarrow\; (A\; \backslash subset\; C)$
• Пустое множество является подмножеством любого другого, поэтому оно является наименьшим множеством относительно отношения подмножества: $\backslash varnothing\; \backslash subset\; B$
• Для любых двух множеств $A$ и $B$ следующие утверждения эквивалентны:
  • $A\; \backslash subset\; B.$
  • $A\; \backslash cap\; B\; =\; A.$
  • $A\; \backslash cup\; B\; =\; B.$
  • $B^\{\backslash complement\}\; \backslash subset\; A^\{\backslash complement\}.$

Подмножества конечных множеств

Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у $n$-элементного множества существует $2^n$ подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет $n$-кратным произведением двоек. Если же рассматривать только подмножества $n$-элементного множества из $k\backslash le\; n$ элементов, то их количество выражается биномиальным коэффициентом $\backslash textstyle\backslash binom\{n\}\{k\}$. Для проверки этого факта можно выбирать элементы подмножества последовательно. Первый элемент можно выбрать $n$ способами, второй $n-1$ способом, и так далее, и, наконец, $k$-й элемент можно выбрать $n-k+1$ способом. Таким образом мы получим последовательность из $k$ элементов, и ровно $k!$ таким последовательностям соответствует одно подмножество. Значит, всего найдется $\backslash textstyle\backslash frac\{n(n-1)\backslash dots(n-k+1)\}\{k!\}=\backslash binom\{n\}\{k\}$ таких подмножеств.

Напишите отзыв о статье "Подмножество"

Примечания

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.. - 3-е изд., стереотип. - М .: МЦНМО, 2008. - 128 с. - ISBN 978-5-94057-321-0 .

Формальная Математическая (теоретическая, символическая) 2 константы : 0 1 См. также

Отрывок, характеризующий Подмножество

– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.
– Вы при офицерах говорите полковому командиру про эту пакость, – продолжал штаб ротмистр. – Богданыч (Богданычем называли полкового командира) вас осадил.
– Не осадил, а сказал, что я неправду говорю.
– Ну да, и вы наговорили ему глупостей, и надо извиниться.
– Ни за что! – крикнул Ростов.
– Не думал я этого от вас, – серьезно и строго сказал штаб ротмистр. – Вы не хотите извиниться, а вы, батюшка, не только перед ним, а перед всем полком, перед всеми нами, вы кругом виноваты. А вот как: кабы вы подумали да посоветовались, как обойтись с этим делом, а то вы прямо, да при офицерах, и бухнули. Что теперь делать полковому командиру? Надо отдать под суд офицера и замарать весь полк? Из за одного негодяя весь полк осрамить? Так, что ли, по вашему? А по нашему, не так. И Богданыч молодец, он вам сказал, что вы неправду говорите. Неприятно, да что делать, батюшка, сами наскочили. А теперь, как дело хотят замять, так вы из за фанаберии какой то не хотите извиниться, а хотите всё рассказать. Вам обидно, что вы подежурите, да что вам извиниться перед старым и честным офицером! Какой бы там ни был Богданыч, а всё честный и храбрый, старый полковник, так вам обидно; а замарать полк вам ничего? – Голос штаб ротмистра начинал дрожать. – Вы, батюшка, в полку без году неделя; нынче здесь, завтра перешли куда в адъютантики; вам наплевать, что говорить будут: «между павлоградскими офицерами воры!» А нам не всё равно. Так, что ли, Денисов? Не всё равно?
Денисов всё молчал и не шевелился, изредка взглядывая своими блестящими, черными глазами на Ростова.
– Вам своя фанаберия дорога, извиниться не хочется, – продолжал штаб ротмистр, – а нам, старикам, как мы выросли, да и умереть, Бог даст, приведется в полку, так нам честь полка дорога, и Богданыч это знает. Ох, как дорога, батюшка! А это нехорошо, нехорошо! Там обижайтесь или нет, а я всегда правду матку скажу. Нехорошо!
И штаб ротмистр встал и отвернулся от Ростова.
– Пг"авда, чог"т возьми! – закричал, вскакивая, Денисов. – Ну, Г"остов! Ну!
Ростов, краснея и бледнея, смотрел то на одного, то на другого офицера.
– Нет, господа, нет… вы не думайте… я очень понимаю, вы напрасно обо мне думаете так… я… для меня… я за честь полка.да что? это на деле я покажу, и для меня честь знамени…ну, всё равно, правда, я виноват!.. – Слезы стояли у него в глазах. – Я виноват, кругом виноват!… Ну, что вам еще?…
– Вот это так, граф, – поворачиваясь, крикнул штаб ротмистр, ударяя его большою рукою по плечу.
– Я тебе говог"ю, – закричал Денисов, – он малый славный.
– Так то лучше, граф, – повторил штаб ротмистр, как будто за его признание начиная величать его титулом. – Подите и извинитесь, ваше сиятельство, да с.
– Господа, всё сделаю, никто от меня слова не услышит, – умоляющим голосом проговорил Ростов, – но извиняться не могу, ей Богу, не могу, как хотите! Как я буду извиняться, точно маленький, прощенья просить?
Денисов засмеялся.
– Вам же хуже. Богданыч злопамятен, поплатитесь за упрямство, – сказал Кирстен.
– Ей Богу, не упрямство! Я не могу вам описать, какое чувство, не могу…
– Ну, ваша воля, – сказал штаб ротмистр. – Что ж, мерзавец то этот куда делся? – спросил он у Денисова.
– Сказался больным, завтг"а велено пг"иказом исключить, – проговорил Денисов.
– Это болезнь, иначе нельзя объяснить, – сказал штаб ротмистр.
– Уж там болезнь не болезнь, а не попадайся он мне на глаза – убью! – кровожадно прокричал Денисов.
В комнату вошел Жерков.
– Ты как? – обратились вдруг офицеры к вошедшему.
– Поход, господа. Мак в плен сдался и с армией, совсем.
– Врешь!
– Сам видел.
– Как? Мака живого видел? с руками, с ногами?
– Поход! Поход! Дать ему бутылку за такую новость. Ты как же сюда попал?
– Опять в полк выслали, за чорта, за Мака. Австрийской генерал пожаловался. Я его поздравил с приездом Мака…Ты что, Ростов, точно из бани?
– Тут, брат, у нас, такая каша второй день.
Вошел полковой адъютант и подтвердил известие, привезенное Жерковым. На завтра велено было выступать.
– Поход, господа!
– Ну, и слава Богу, засиделись.

Кутузов отступил к Вене, уничтожая за собой мосты на реках Инне (в Браунау) и Трауне (в Линце). 23 го октября.русские войска переходили реку Энс. Русские обозы, артиллерия и колонны войск в середине дня тянулись через город Энс, по сю и по ту сторону моста.

Множество - совокупность любых объектов. Множества обозначают большими буквами латинского алфавита - от A до Z .

Основные числовые множества: множество натуральных чисел и множество целых чисел, всегда обозначаются одними и теми же буквами:

N - множество натуральных чисел

Z - множество целых чисел

Элемент множества - это любой объект, входящий в состав множества. Принадлежность объекта к множеству обозначается с помощью знака ∈ . Запись

читается так: 5 принадлежит множеству Z или 5 - элемент множества Z .

Множества делятся на конечные и бесконечные. Конечное множество - множество, содержащее определённое (конечное) количество элементов. Бесконечное множество - множество, содержащее бесконечно много элементов. К бесконечным множествам можно отнести множества натуральных и целых чисел.

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

L = {2, 4, 6, 8}

означает, что множество L состоит из четырёх чётных чисел.

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

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

Подмножество - это множество, все элементы которого, являются частью другого множества.

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

Рассмотрим два множества:

L = {2, 4, 6, 8} и M = {2, 4, 6, 8, 10, 12}

Каждый элемент множества L принадлежит и множеству M , значит, множество L M . Такое соотношение множеств обозначают знаком ⊂ :

L ⊂M

Запись L ⊂M читается так: множество L является подмножеством множества M .

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

Рассмотрим два множества:

L = {2, 4, 6} и M = {4, 6, 2}

Так как оба множества состоят из одних и тех же элементов, то L = M .

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

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

Например, если

L = {1, 3, 7, 11} и M = {3, 11, 17, 19}, то L ∩M = {3, 11}.

Запись L ∩M читается так: пересечение множеств L и M .

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

Объединением двух множеств называется множество, содержащее все элементы исходных множеств в единственном экземпляре, то есть если один и тот же элемент встречается в обоих множествах, то в новое множество этот элемент будет включён только один раз. Объединение обозначается знаком ∪ .

Например, если

L = {1, 3, 7, 11} и M = {3, 11, 17, 19},

то L ∪M = {1, 3, 7, 11, 17, 19}.

Запись L ∪M читается так: объединение множеств L и M .

При объединении равных множеств объединение будет равно любому из данных множеств:

если L = M , то L ∪M = L и L ∪M = M .

Два множества A и B равны, если они состоят из одних и тех же элементов.

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

Подмножества. Определение равенства множеств можно сформулировать иначе, используя понятие подмножества.

Определение. Множество A называется подмножеством множества B , если каждый элемент A является элементом B.

Следствие 1. Очевидно,
для любого множества A, т.к. каждый элемент из A есть элемент из A.

Следствие 2. Для любого множества A,
, ибо если бы пустое множество не являлось подмножеством A, то в пустом подмножестве существовали бы элементы, не принадлежащие A. Однако пустое множество не содержит вообще ни одного элемента.

Если
, то пишут
, и если
, то A – собственное подмножество B.

Понятие подмножества множеств позволяет легко формализовать понятие равенства двух множеств.

Утверждение. Для любых A и B

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

Замечание . Отношение включения  обладает рядом очевидных свойств:

(рефлексивность);

(транзитивность).

Для любого множества X можно определить специальное множество всех подмножеств множества X, которое называется булеаном ℬ
, которое включает в себя само множество X, все его подмножества и пустое множество
.

Пример. Пусть
– это множество, состоящее из трех элементов. Тогда булеанℬ (X) это множество:

Собственными подмножествами ℬ (X) являются следующие множества:

{a},{b},{c},{a,b},{b,c},{a,c}.

В общем случае, если множество X содержит n элементов, то множество его подмножеств ℬ (X) состоит из элементов.

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

Пусть U – универсальное множество,
. Тогда для множеств X,Y можно определить операции
.

Определение . Объединением множеств X и Y называется множество
, состоящее из элементов, входящих хотя бы в одно из множеств (X или Y):

Рис. 1.1 – Объединение множеств Рис. 1.2 – Пересечение множеств

Определение . Пересечением множеств X и Y называется множество
, состоящее из элементов, входящих в X и в Y одновременно:

Определение . Разностью множеств X и Y называется множество
, состоящее из элементов, входящих в множество X, но не входящих в Y:

Рис. 1.3 – Разность множеств
Рис. 1.4 – Симметрическая

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

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

Определение . Для любого множества
дополнением множествадо U называется такое множество, что:

Рис. 1.5 – Дополнение множества X до U

На рис. 1.1  1.5 представлены диаграммы Венна, наглядно демонстрирующие результаты операций
.

Дополнение множества иногда обозначается
. Операции
связаны между собой законами де Моргана:

, (1.7)

. (1.8)

В справедливости законов де Моргана легко убедиться самостоятельно.

В таблице 1.1 представлены основные свойства операций над множествами.

Таблица 1.1

	Свойства операций	Объединение, пересечение, дополнение
	коммутативность	,
	ассоциативность
	дистрибутивность
	идемпотентность	, , , , ,
	теоремы де Моргана	,
	инволюция

Операции объединения и пересечения можно обобщить. Пусть
– множество индексов,
– семейство подмножеств множества X.

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

,

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

Определение. Класс K подмножеств из U называется алгеброй, если:

1.
;

2. из того, что
следует, что
;

3. из того, что
следует, что
.

Пример. Пусть
, тогда класс
образует алгебру.

Определение. Класс F подмножеств из U образует -алгебру, если:

1.
;

2. из того, что
следует
;

3. из того, что
,
следует, что
.

Пример. Множество всех подмножеств U образует -алгебру, т.е.ℬ (U) – -алгебра.