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

Множество ${\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)\,}$ 

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

Обе системы обозначений предусмотрены стандартом 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.