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

Запрос «Подкласс (теория множеств)» перенаправляется сюда. На эту тему нужно создать отдельную статью.

Подмно́жество в теории множеств — это понятие части множества.

На диаграмме кругов Эйлера видно, что $A$ является подмножеством $B$, а $B$ является надмножеством $A.$

Определение

Множество $A$ называется подмножеством множества $B$, если все элементы, принадлежащие $A$, также принадлежат $B$. Формальное определение:

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

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

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

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

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

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

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

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

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

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

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

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

Зарубежная литература

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

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

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

Примеры

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

Свойства

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

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

    $B\subset B$

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

    $(A\subset B\;\land \;B\subset A)\Leftrightarrow (A=B)$

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

    $(A\subset B\;\land \;B\subset C)\Rightarrow (A\subset C)$

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

  $\varnothing \subset B$

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

являются равносильными.

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

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