WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 20 июня 2018 года.

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

Определение

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

${\displaystyle (A\subset B)\Leftrightarrow \left(\forall x(x\in A\Rightarrow x\in B)\right)\,}$ .

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

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

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

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

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

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

Примеры

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

Свойства

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

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

    ${\displaystyle B\subset B}$

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

    ${\displaystyle (A\subset B\;\land \;B\subset A)\Leftrightarrow (A=B)}$

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

    ${\displaystyle (A\subset B\;\land \;B\subset C)\Rightarrow (A\subset C)}$

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

  ${\displaystyle \varnothing \subset B}$

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

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

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