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

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

На диаграмме кругов Эйлера видно, что [math]\displaystyle{ A }[/math] является подмножеством [math]\displaystyle{ B }[/math], а [math]\displaystyle{ B }[/math] является надмножеством [math]\displaystyle{ A. }[/math]

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

Определение

Множество [math]\displaystyle{ A }[/math] называется подмножеством множества [math]\displaystyle{ B }[/math], если все элементы, принадлежащие [math]\displaystyle{ A }[/math], также принадлежат [math]\displaystyle{ B }[/math]. Формальное определение:

[math]\displaystyle{ (A \subset B) \Leftrightarrow \left ( \forall x (x \in A \Rightarrow x \in B )\right)\, }[/math]

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

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

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

Множество [math]\displaystyle{ B }[/math] называется надмно́жеством множества [math]\displaystyle{ A }[/math], если [math]\displaystyle{ A }[/math] является подмножеством множества [math]\displaystyle{ B }[/math].

То, что [math]\displaystyle{ B }[/math] является надмножеством множества [math]\displaystyle{ A }[/math], записывают [math]\displaystyle{ B \supset A }[/math], то есть [math]\displaystyle{ (A \subset B) \Leftrightarrow (B \supset A)\, . }[/math]

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

Множества [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] называются равными [math]\displaystyle{ A = B }[/math], только когда они состоят из одних и тех же элементов, то есть [math]\displaystyle{ A \subseteq B }[/math] и [math]\displaystyle{ B \subseteq A }[/math].

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

Любое множество [math]\displaystyle{ B }[/math] среди своих подмножеств содержит само себя и пустое множество. Само множество [math]\displaystyle{ B }[/math] и пустое множество называют несобственными подмножествами, остальные подмножества называют собственными.

То есть, если мы хотим исключить само [math]\displaystyle{ B }[/math] и пустое множество из рассмотрения, мы пользуемся понятием со́бственного подмножества, которое определяется так:

множество [math]\displaystyle{ A }[/math] является собственным подмножеством множества [math]\displaystyle{ B }[/math], только если [math]\displaystyle{ A \subset B }[/math] и [math]\displaystyle{ A \ne B }[/math], [math]\displaystyle{ A \ne \varnothing }[/math].

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

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

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

множество [math]\displaystyle{ A }[/math] является нетривиальным подмножеством множества [math]\displaystyle{ B }[/math], если [math]\displaystyle{ A }[/math] является собственным подмножеством (proper subset) [math]\displaystyle{ B }[/math] и [math]\displaystyle{ A \ne \varnothing }[/math].

Примеры

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

Свойства

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

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

    [math]\displaystyle{ B \subset B }[/math]

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

    [math]\displaystyle{ (A \subset B \; \land \; B \subset A) \Leftrightarrow (A = B) }[/math]

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

    [math]\displaystyle{ (A \subset B \;\land \; B \subset C ) \Rightarrow ( A \subset C ) }[/math]

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

  [math]\displaystyle{ \varnothing \subset B }[/math]

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

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

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

Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у [math]\displaystyle{ n }[/math]-элементного множества существует [math]\displaystyle{ 2^n }[/math] подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет [math]\displaystyle{ n }[/math]-кратным произведением двоек. Если же рассматривать только подмножества [math]\displaystyle{ n }[/math]-элементного множества из [math]\displaystyle{ k\le n }[/math] элементов, то их количество выражается биномиальным коэффициентом [math]\displaystyle{ \textstyle\binom{n}{k} }[/math]. Для проверки этого факта можно выбирать элементы подмножества последовательно. Первый элемент можно выбрать [math]\displaystyle{ n }[/math] способами, второй [math]\displaystyle{ n-1 }[/math] способом, и так далее, и, наконец, [math]\displaystyle{ k }[/math]-й элемент можно выбрать [math]\displaystyle{ n-k+1 }[/math] способом. Таким образом мы получим последовательность из [math]\displaystyle{ k }[/math] элементов, и ровно [math]\displaystyle{ k! }[/math] таким последовательностям соответствует одно подмножество. Значит, всего найдётся [math]\displaystyle{ \textstyle\frac{n(n-1)\dots(n-k+1)}{k!}=\binom{n}{k} }[/math] таких подмножеств.

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.. — 3-е изд., стереотип. — М.: МЦНМО, 2008. — 128 с. — ISBN 978-5-94057-321-0.
• Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976. — 400 с.

Ссылки

• Weisstein, Eric W. Subset (англ.) на сайте Wolfram MathWorld.