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

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

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

Определения

• Множество $A$ является подмножеством множества $B$, если любой элемент, принадлежащий $A$, также принадлежит $B$. Пишут: $A \subset B$ или $A \subseteq B$. Таким образом,

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

• Множество $B$ в таком случае называется надмно́жеством множества $A$, и этот факт часто записывают: $B \supset A$ или $B \supseteq A.$

Множество $A$ называется подмножеством множества $B,$ если все элементы $A$ являются также элементами $B.$ Любое множество является своим подмножеством: $A \sub A.$ Если при этом $A \ne B$, то $A$ называется собственным подмножеством $B.$ По определению полагают, что пустое множество является подмножеством любого множества: $\forall A: \varnothing \sub A$.

Множество всех подмножеств множества $A$ обозначается $\mathcal{P}A$ или $2^A$, так как оно соответствует множеству отображений из $A$ в $2 = \{ 0,1\}.$ Иногда его называют множеством-степенью (англ. power set) для $A$. Мощность множества-степени, по теореме Кантора, всегда больше, чем у исходного множества. В категории множеств $\mathcal{P}$ в это контравариантный функтор, отображающий функцию $f\colon A\to B$ в $\mathcal{P}f\colon \mathcal{P}B \to \mathcal{P}A,$ при этом отображение $\mathcal{P}f$ ставит в соответствие каждому подмножеству $B$ его полный прообраз в $A.$

Примеры:

• Множества $\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\} \}.$

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

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

$\varnothing \subset B,\; B \subset B \quad \forall B$.

Если $A \subset B$, и $A \ne \varnothing$, $A \ne B$, то $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$

• Таким образом отношение подмножества является отношением частичного порядка на булеане $2^{M}$ в семействе всех подмножеств любого объемлющего множества $M.$
• Для любых двух множеств $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}$ таких подмножеств.

Пример

• Пусть

$A = \{1,2,3,4,5\},\; B = \{1,2,3\},\; C = \{4,5,6,7\}.$

Тогда

$B \subset A,\; C \not\subset A.$

См. также

• Булеан