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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 июня 2018)

В математике говорят, что множество ${\displaystyle A}$ есть подмно́жество множества ${\displaystyle B}$, если все элементы первого множества являются и элементами второго множества.

Множество ${\displaystyle A}$ называется подмножеством множества ${\displaystyle B}$, если все элементы, принадлежащие ${\displaystyle A}$, также принадлежат ${\displaystyle B}$^[1]. Формальное определение:

${\displaystyle (A\subset B)\Leftrightarrow \left(\forall x(x\in A\Rightarrow x\in B)\right)\,}$

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

«${\displaystyle A}$ является подмножеством ${\displaystyle B}$ (нестрогим)» обозначается	«${\displaystyle A}$ является строгим подмножеством ${\displaystyle B}$» обозначается	Примечание
${\displaystyle A\subseteq B}$	${\displaystyle A\subset B}$	Символ ${\displaystyle \subseteq }$ является аналогом ${\displaystyle \leq }$, то есть в случае ${\displaystyle A\subseteq B}$ допускается равенство ${\displaystyle A=B}$ множеств; символ ${\displaystyle \subset }$ является аналогом ${\displaystyle <}$, то есть в случае ${\displaystyle A\subset B}$ в ${\displaystyle B}$ есть элементы, которых нет в ${\displaystyle A}$.
${\displaystyle A\subset B}$	${\displaystyle A\subsetneq B}$	Для понятия «(нестрогое) подмножество» используется более простой символ, так как оно считается более «фундаментальным».

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

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

То, что ${\displaystyle B}$ является надмножеством множества ${\displaystyle A}$, записывают ${\displaystyle B\supset A}$, то есть ${\displaystyle (A\subset B)\Leftrightarrow (B\supset A)\,.}$

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

Множества ${\displaystyle A}$ и ${\displaystyle B}$ называются равными ${\displaystyle A=B}$, только когда они состоят из одних и тех же элементов, то есть ${\displaystyle A\subseteq B}$ и ${\displaystyle B\subseteq A}$.^[2]

Любое множество ${\displaystyle B}$ среди своих подмножеств содержит само себя и пустое множество. Само множество ${\displaystyle B}$ и пустое множество называют несобственными подмножествами, остальные подмножества называют собственными^[3].

То есть, если мы хотим исключить само ${\displaystyle B}$ и пустое множество из рассмотрения, мы пользуемся понятием со́бственного подмножества, которое определяется так:

множество ${\displaystyle A}$ является собственным подмножеством множества ${\displaystyle B}$, только если ${\displaystyle A\subset B}$ и ${\displaystyle A\neq B}$, ${\displaystyle A\neq \varnothing }$.

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

В этом случае, если вдобавок нужно исключить из рассмотрения пустое множество, нужно использовать понятие нетривиа́льного подмножества, которое определяется так:

множество ${\displaystyle A}$ является нетривиальным подмножеством множества ${\displaystyle B}$, если ${\displaystyle A}$ является собственным подмножеством (proper subset) ${\displaystyle B}$ и ${\displaystyle A\neq \varnothing }$.

• Множества ${\displaystyle \varnothing ,~\{0\},~\{1,3,4\},~\{0,1,2,3,4,5\}}$ являются подмножествами множества ${\displaystyle \{0,1,2,3,4,5\}.}$
• Множества ${\displaystyle \varnothing ,~\{0,1,2,3,4,5\}}$ являются тривиальными (несобственными) подмножествами множества ${\displaystyle \{0,1,2,3,4,5\},}$ все остальные подмножества из элементов множества — нетривиальными или собственными.
• Множества ${\displaystyle \{\varnothing ,\uparrow ,{\mbox{oca}}\},~\{\$,\%,*,\uparrow \},~\{\varnothing \},~\varnothing }$ являются подмножествами множества ${\displaystyle \{\$,\%,\varnothing ,\uparrow ,*,{\mbox{oca}}\}.}$
• Пусть ${\displaystyle A=\{a,b\}.}$ Тогда ${\displaystyle {\mathcal {P}}(A)=\{\varnothing ,\{a\},\{b\},\{a,b\}\}.}$
• Пусть ${\displaystyle A=\{1,2,3,4,5\},\;B=\{1,2,3\},\;C=\{4,5,6,7\}}$. Тогда ${\displaystyle B\subset A,\;C\not \subset A,}$ а также ${\displaystyle \neg (C\subsetneq A)}$ (то есть C не является ни строгим, ни нестрогим подмножеством A).

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

• Отношение подмножества является отношением частичного порядка:
  • Отношение подмножества рефлексивно:

    ${\displaystyle B\subset B}$

  • Отношение подмножества антисимметрично:

    ${\displaystyle (A\subset B\;\land \;B\subset A)\Leftrightarrow (A=B)}$

  • Отношение подмножества транзитивно:

    ${\displaystyle (A\subset B\;\land \;B\subset C)\Rightarrow (A\subset C)}$

• Пустое множество является подмножеством любого другого, поэтому оно является наименьшим множеством относительно отношения подмножества:

  ${\displaystyle \varnothing \subset B}$

• Для любых трёх множеств ${\displaystyle A}$, ${\displaystyle B}$ и ${\displaystyle X}$ таких, что ${\displaystyle A,B\subset X}$, равносильны все следующие утверждения:^[5]
  • ${\displaystyle A\subset B;}$
  • ${\displaystyle A\cap B=A;}$
  • ${\displaystyle A\cup B=B;}$
  • ${\displaystyle X\setminus B\subset X\setminus A;}$
  • ${\displaystyle (A\cap X)\setminus B=\varnothing ;}$
  • ${\displaystyle A\cap (X\setminus B)=\varnothing ;}$
  • ${\displaystyle (X\setminus A)\cup B=X;}$
  • ${\displaystyle B^{\complement }\subset A^{\complement }}$

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

	В Викисловаре есть статья «подмножество»

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

• Weisstein, Eric W. Subset (англ.) на сайте Wolfram MathWorld.