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

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

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

Определение

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

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

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

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

«$A$ является подмножеством $B$» обозначается	«$A$ является собственным подмножеством $B$» обозначается	Примечание
$A \subseteq B$	$A \subset B$	Внешний вид символа $\subseteq$ намекает, что если $A=B$, то $A \subseteq B$.
$A \subset B$	$A \subsetneq B$	Для понятия «подмножество» используется более простой символ, так как это понятие является более «фундаментальным».

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

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

Множество всех подмножеств множества $A$ обозначается $\mathcal{P}A$ и называется множеством-степенью.

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

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

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

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

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

Примеры

• Множества $\varnothing, \{0\}, \{1,3,4\}.$ являются подмножествами множества $\{ 0,1,2,3,4,5\}$
• Множества $\{ \varnothing, \uparrow, moose \}, \{ $,%,*,\uparrow \}, \{\varnothing\}, \varnothing$ являются подмножествами множества $\{ $, %, \varnothing, \uparrow, *, moose \}$
• Пусть $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$.

Свойства

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

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

    $B \subset B$

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

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

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

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

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

  $\varnothing \subset B$

• Для любых двух множеств $A$ и $B$ следующие утверждения эквивалентны:
  • $A \subset B.$
  • $A \cap B = A.$
  • $A \cup B = B.$
  • $B^{\complement} \subset A^{\complement}.$

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

Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у $n$-элементного множества существует $2^n$ подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет $n$-кратным произведением двоек. Если же рассматривать только подмножества $n$-элементного множества из $k\le 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}$ таких подмножеств.

См. также

• Булеан