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

Материал из Википедии — свободной энциклопедии

A

является подмножеством

B

, а

B

является надмножеством

A .

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

Содержание

1 Определения
2 Собственное подмножество
3 Свойства
4 Подмножества конечных множеств
5 Пример
6 Ссылки

[править] Определения

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

Примеры:

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

Таким образом отношение подмножества является отношением частичного порядка на булеане $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}$ таких подмножеств.