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

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

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

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

ОпределениеПравить

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

$(A\subset <!--\; \subset \; -->B)\iff <!--\; \iff \; -->\left(\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\Rightarrow <!--\; \Rightarrow \; -->x\in <!--\; \in \; -->B)\right)$$(A\subset B)\Leftrightarrow \left(\forall x(x\in A\Rightarrow x\in B)\right)\,$ 

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

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

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

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

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

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

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

Собственное и несобственное подмножествоПравить

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

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

множество $A$$A$  является собственным подмножеством множества $B$$B$ , только если $A\subset <!--\; \subset \; -->B$$A\subset B$  и $A\ne <!--\; \ne \; -->B$$A\neq B$ , $A\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$A\neq \varnothing$ .

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

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

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

множество $A$$A$  является нетривиальным подмножеством множества $B$$B$ , если $A$$A$  является собственным подмножеством (proper subset) $B$$B$  и $A\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$A\neq \varnothing$ .

ПримерыПравить

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

СвойстваПравить

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

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

    $B\subset <!--\; \subset \; -->B$$B\subset B$ 

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

    $(A\subset <!--\; \subset \; -->B\wedge <!--\; \wedge \; -->B\subset <!--\; \subset \; -->A)\iff <!--\; \iff \; -->(A=B)$$(A\subset B\;\land \;B\subset A)\Leftrightarrow (A=B)$ 

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

    $(A\subset <!--\; \subset \; -->B\wedge <!--\; \wedge \; -->B\subset <!--\; \subset \; -->C)\Rightarrow <!--\; \Rightarrow \; -->(A\subset <!--\; \subset \; -->C)$$(A\subset B\;\land \;B\subset C)\Rightarrow (A\subset C)$ 

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

  $\mathrm{\varnothing <!--\; \varnothing \; -->}\subset <!--\; \subset \; -->B$$\varnothing \subset B$ 

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

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

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

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