Подмножество
Шаблон:Нет ссылок Шаблон:Falseredirect
В математике говорят, что множество <math>A</math> есть подмно́жество множества <math>B</math>, если все элементы первого множества являются и элементами второго множества.
Определение
Множество <math>A</math> называется подмножеством множества <math>B</math>, если все элементы, принадлежащие <math>A</math>, также принадлежат <math>B</math>Шаблон:Sfn. Формальное определение:
- <math>(A \subset B) \Leftrightarrow \left ( \forall x (x \in A \Rightarrow x \in B )\right)\,</math>
Существует две системы символических обозначений для подмножеств:
| «<math>A</math> является подмножеством <math>B</math> (нестрогим)» обозначается | «<math>A</math> является строгим подмножеством <math>B</math>» обозначается | Примечание |
|---|---|---|
| <math>A \subseteq B</math> | <math>A \subset B</math> | Символ <math>\subseteq</math> является аналогом <math>\leq</math>, то есть в случае <math>A\subseteq B</math> допускается равенство <math>A=B</math> множеств;
символ <math>\subset</math> является аналогом <math> < </math>, то есть в случае <math>A \subset B</math> в <math>B</math> есть элементы, которых нет в <math>A</math>. |
| <math>A \subset B</math> | <math>A \subsetneq B</math> | Для понятия «(нестрогое) подмножество» используется более простой символ, так как оно считается более «фундаментальным». |
Обе системы обозначений предусмотрены стандартом ISO 31-11, но используют символ <math>\subset</math> в разных смыслах, что может привести к путанице. В данной статье мы будем использовать последнюю систему обозначений.
Множество <math>B</math> называется Шаблон:Видимый якорь множества <math>A</math>, если <math>A</math> является подмножеством множества <math>B</math>.
То, что <math>B</math> является надмножеством множества <math>A</math>, записывают <math>B \supset A</math>, то есть <math>(A \subset B) \Leftrightarrow (B \supset A)\, .</math>
Множество всех подмножеств множества <math>A</math> обозначается <math>\mathcal{P}(A)</math>.
Множества <math>A</math> и <math>B</math> называются равными <math>A = B</math>, только когда они состоят из одних и тех же элементов, то есть <math>A \subseteq B</math> и <math>B \subseteq A</math>.<ref name="Mel">Мельников О. В., Ремеслеников В. Н., Романьков В. А. Общая алгебра. Том 1. — М., Наука, 1990. — с. 11</ref>
Собственное и несобственное подмножество
Любое множество <math>B</math> среди своих подмножеств содержит само себя и пустое множество. Само множество <math>B</math> и пустое множество называют несобственными подмножествами, остальные подмножества называют собственными<ref>Подмножество. // Математический энциклопедический словарь. / ред. Ю. В. Прохоров. — М., Советская энциклопедия, 1988. — с. 465</ref>.
То есть, если мы хотим исключить само <math>B</math> и пустое множество из рассмотрения, мы пользуемся понятием со́бственного подмножества, которое определяется так:
- множество <math>A</math> является собственным подмножеством множества <math>B</math>, только если <math>A \subset B</math> и <math>A \ne B</math>, <math>A \ne \varnothing</math>.
Зарубежная литература
В зарубежной литературе несобственные подмножества в вышеуказанном смысле (само множество B и пустое множество) называют тривиальными, а собственные — нетривиальными, а термин «собственное подмножество» (proper subset) применяется в значении «строгое включение A в B» или «подмножество A, строго входящее в множество B, то есть такое, которому не принадлежит как минимум один элемент множества B», то есть здесь понятие «собственное подмножество» уже, наоборот, включает пустое множество.
В этом случае, если вдобавок нужно исключить из рассмотрения пустое множество, нужно использовать понятие нетривиа́льного подмножества, которое определяется так:
- множество <math>A</math> является нетривиальным подмножеством множества <math>B</math>, если <math>A</math> является собственным подмножеством (proper subset) <math>B</math> и <math>A \ne \varnothing</math>.
Примеры
- Множества <math>\varnothing,~ \{0\},~ \{1,3,4\},~ \{0,1,2,3,4,5\}</math> являются подмножествами множества <math>\{ 0,1,2,3,4,5\}.</math>
- Множества <math>\varnothing,~ \{0,1,2,3,4,5\}</math> являются тривиальными (несобственными) подмножествами множества <math>\{ 0,1,2,3,4,5\},</math> все остальные подмножества из элементов множества — нетривиальными или собственными.
- Множества <math>\{ \varnothing, \uparrow, \mbox{oca} \},~ \{ \$,\%,*,\uparrow \},~ \{\varnothing\},~ \varnothing</math> являются подмножествами множества <math>\{ \$, \%, \varnothing, \uparrow, *, \mbox{oca} \}.</math>
- Пусть <math>A = \{a,b\}.</math> Тогда <math>\mathcal{P}(A) = \{\varnothing, \{a\}, \{b\}, \{a,b\} \}.</math>
- Пусть <math>A = \{1,2,3,4,5\},\; B = \{1,2,3\},\; C = \{4,5,6,7\}</math>. Тогда <math>B \subset A,\; C \not\subset A,</math> а также <math>\neg(C\subsetneq A)</math> (то есть C не является ни строгим, ни нестрогим подмножеством A).
Свойства
Отношение подмножества обладает целым рядом свойств<ref name="ilyin">Шаблон:Книга</ref>.
- Отношение подмножества является отношением частичного порядка:
- Отношение подмножества рефлексивно:
- <math>B \subset B</math>
- Отношение подмножества антисимметрично:
- <math>(A \subset B \; \land \; B \subset A) \Leftrightarrow (A = B)</math>
- Отношение подмножества транзитивно:
- <math>(A \subset B \;\land \; B \subset C ) \Rightarrow ( A \subset C )</math>
- Отношение подмножества рефлексивно:
- Пустое множество является подмножеством любого другого, поэтому оно является наименьшим множеством относительно отношения подмножества:
- <math>\varnothing \subset B</math>
- Для любых трёх множеств <math>A</math>, <math>B</math> и <math>X</math> таких, что <math>A,B\subset X</math>, равносильны все следующие утверждения:<ref>Шаблон:Книга</ref>
- <math>A \subset B;</math>
- <math>A \cap B = A;</math>
- <math>A \cup B = B;</math>
- <math>X \setminus B \subset X \setminus A;</math>
- <math>(A \cap X) \setminus B = \varnothing;</math>
- <math>A\cap(X\setminus B) = \varnothing;</math>
- <math>(X \setminus A) \cup B = X;</math>
- <math>B^{\complement} \subset A^{\complement}</math>
Подмножества конечных множеств
Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у <math>n</math>-элементного множества существует <math>2^n</math> подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет <math>n</math>-кратным произведением двоек. Если же рассматривать только подмножества <math>n</math>-элементного множества из <math>k\le n</math> элементов, то их количество выражается биномиальным коэффициентом <math>\textstyle\binom{n}{k}</math>. Для проверки этого факта можно выбирать элементы подмножества последовательно. Первый элемент можно выбрать <math>n</math> способами, второй <math>n-1</math> способом, и так далее, и, наконец, <math>k</math>-й элемент можно выбрать <math>n-k+1</math> способом. Таким образом мы получим последовательность из <math>k</math> элементов, и ровно <math>k!</math> таким последовательностям соответствует одно подмножество. Значит, всего найдётся <math>\textstyle\frac{n(n-1)\dots(n-k+1)}{k!}=\binom{n}{k}</math> таких подмножеств.