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

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

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

Определение

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

<math>(A \subset B) \Leftrightarrow \forall x. (x \in A \Rightarrow x \in B ).</math>

Множество <math>B</math> называется надмно́жеством множества <math>A</math>, если <math>A</math> — подмножество <math>B</math>.

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

«<math>A</math> является подмножеством <math>B</math>» обозначается	«<math>A</math> является собственным подмножеством <math>B</math>» обозначается	Примечание
<math>A \subseteq B</math>	<math>A \subset B</math>	Внешний вид символа <math>\subseteq</math> намекает, что если <math>A=B</math>, то <math>A \subseteq B</math>.
<math>A \subset B</math>	<math>A \subsetneq B</math>	Для понятия «подмножество» используется более простой символ, так как это понятие является более «фундаментальным».

Обе системы обозначений используют символ <math>\subset</math> в разных смыслах, что может привести к путанице. В данной статье мы будем использовать последнюю систему обозначений.

То, что <math>B</math> называется надмножеством <math>A</math>, часто записывают <math>B \supset A</math>.

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

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

Любое множество <math>B</math> является своим подмножеством. Если мы хотим исключить <math>B</math> из рассмотрения, мы пользуемся понятием со́бственного подмножества, которое определяется так:

Множество <math>A</math> является собственным подмножеством множества <math>B</math>, если <math>A \subset B</math> и <math>A \ne B</math>.

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

Множество <math>A</math> является нетривиальным подмножеством множества <math>B</math>, если <math>A</math> является собственным подмножеством <math>B</math> и <math>A \ne \varnothing</math>.

Примеры

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

Свойства

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

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

    <math>B \subset B</math>

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

    <math>(A \subset B \; \and \; B \subset A) \Leftrightarrow (A = B)</math>

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

    <math>(A \subset B \;\and \; B \subset C ) \Rightarrow ( A \subset C )</math>

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

  <math>\varnothing \subset B</math>

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

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

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

Литература

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

Отрывок, характеризующий Подмножество

– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.
– Вы при офицерах говорите полковому командиру про эту пакость, – продолжал штаб ротмистр. – Богданыч (Богданычем называли полкового командира) вас осадил.
– Не осадил, а сказал, что я неправду говорю.
– Ну да, и вы наговорили ему глупостей, и надо извиниться.
– Ни за что! – крикнул Ростов.
– Не думал я этого от вас, – серьезно и строго сказал штаб ротмистр. – Вы не хотите извиниться, а вы, батюшка, не только перед ним, а перед всем полком, перед всеми нами, вы кругом виноваты. А вот как: кабы вы подумали да посоветовались, как обойтись с этим делом, а то вы прямо, да при офицерах, и бухнули. Что теперь делать полковому командиру? Надо отдать под суд офицера и замарать весь полк? Из за одного негодяя весь полк осрамить? Так, что ли, по вашему? А по нашему, не так. И Богданыч молодец, он вам сказал, что вы неправду говорите. Неприятно, да что делать, батюшка, сами наскочили. А теперь, как дело хотят замять, так вы из за фанаберии какой то не хотите извиниться, а хотите всё рассказать. Вам обидно, что вы подежурите, да что вам извиниться перед старым и честным офицером! Какой бы там ни был Богданыч, а всё честный и храбрый, старый полковник, так вам обидно; а замарать полк вам ничего? – Голос штаб ротмистра начинал дрожать. – Вы, батюшка, в полку без году неделя; нынче здесь, завтра перешли куда в адъютантики; вам наплевать, что говорить будут: «между павлоградскими офицерами воры!» А нам не всё равно. Так, что ли, Денисов? Не всё равно?
Денисов всё молчал и не шевелился, изредка взглядывая своими блестящими, черными глазами на Ростова.
– Вам своя фанаберия дорога, извиниться не хочется, – продолжал штаб ротмистр, – а нам, старикам, как мы выросли, да и умереть, Бог даст, приведется в полку, так нам честь полка дорога, и Богданыч это знает. Ох, как дорога, батюшка! А это нехорошо, нехорошо! Там обижайтесь или нет, а я всегда правду матку скажу. Нехорошо!
И штаб ротмистр встал и отвернулся от Ростова.
– Пг'авда, чог'т возьми! – закричал, вскакивая, Денисов. – Ну, Г'остов! Ну!
Ростов, краснея и бледнея, смотрел то на одного, то на другого офицера.
– Нет, господа, нет… вы не думайте… я очень понимаю, вы напрасно обо мне думаете так… я… для меня… я за честь полка.да что? это на деле я покажу, и для меня честь знамени…ну, всё равно, правда, я виноват!.. – Слезы стояли у него в глазах. – Я виноват, кругом виноват!… Ну, что вам еще?…
– Вот это так, граф, – поворачиваясь, крикнул штаб ротмистр, ударяя его большою рукою по плечу.
– Я тебе говог'ю, – закричал Денисов, – он малый славный.
– Так то лучше, граф, – повторил штаб ротмистр, как будто за его признание начиная величать его титулом. – Подите и извинитесь, ваше сиятельство, да с.
– Господа, всё сделаю, никто от меня слова не услышит, – умоляющим голосом проговорил Ростов, – но извиняться не могу, ей Богу, не могу, как хотите! Как я буду извиняться, точно маленький, прощенья просить?
Денисов засмеялся.
– Вам же хуже. Богданыч злопамятен, поплатитесь за упрямство, – сказал Кирстен.
– Ей Богу, не упрямство! Я не могу вам описать, какое чувство, не могу…
– Ну, ваша воля, – сказал штаб ротмистр. – Что ж, мерзавец то этот куда делся? – спросил он у Денисова.
– Сказался больным, завтг'а велено пг'иказом исключить, – проговорил Денисов.
– Это болезнь, иначе нельзя объяснить, – сказал штаб ротмистр.
– Уж там болезнь не болезнь, а не попадайся он мне на глаза – убью! – кровожадно прокричал Денисов.
В комнату вошел Жерков.
– Ты как? – обратились вдруг офицеры к вошедшему.
– Поход, господа. Мак в плен сдался и с армией, совсем.
– Врешь!
– Сам видел.
– Как? Мака живого видел? с руками, с ногами?
– Поход! Поход! Дать ему бутылку за такую новость. Ты как же сюда попал?
– Опять в полк выслали, за чорта, за Мака. Австрийской генерал пожаловался. Я его поздравил с приездом Мака…Ты что, Ростов, точно из бани?
– Тут, брат, у нас, такая каша второй день.
Вошел полковой адъютант и подтвердил известие, привезенное Жерковым. На завтра велено было выступать.
– Поход, господа!
– Ну, и слава Богу, засиделись.


Кутузов отступил к Вене, уничтожая за собой мосты на реках Инне (в Браунау) и Трауне (в Линце). 23 го октября .русские войска переходили реку Энс. Русские обозы, артиллерия и колонны войск в середине дня тянулись через город Энс, по сю и по ту сторону моста.