Как найти подмножество если дано множество

Как найти все подмножества множеств

На простом примере напомним, что называется подмножеством, какие бывают подмножества (собственные и несобственные), формулу нахождения числа всех подмножеств, а также калькулятор, который выдает множество всех подмножеств.

Пример 1.  Дано множество А = {а, с, р, о}. Выпишите все подмножества
данного множества.
Решение:

Собственные подмножества: {а} , {с} , {р} , {о} , {а, с} , {а, р} , {а, о}, {с, р} , {с, о } ∈, {р, о}, {а, с,р} , {а, с, о}, {с, р, о}.

Несобственные: {а, с, р, о}, Ø.

Всего: 16 подмножеств.

Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.

• пустое множество ∅ является подмножеством любого множества, называется несобственным;
• любое множество является подмножеством самого себя, также называется несобственным;
• У любого n-элементного множества ровно 2ⁿ подмножеств.

Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.

Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ …∙2=2ⁿ

Для математиков сформулируем теорему и приведем строгое доказательство.

Теорема . Число подмножеств конечного множества, состоящего из n элементов, равно 2ⁿ .

Доказательство. Множество, состоящее из одного элемента a, имеет два (т.е. 2¹ ) подмножества: ∅ и {a}. Множество, состоящее из двух элементов a и b, имеет четыре (т.е. 2² ) подмножества: ∅, {a}, {b}, {a; b}.
Множество, состоящее из трех элементов a, b, c, имеет восемь (т.е. 2³ ) подмножеств:
∅, {a}, {b}, {b; a}, {c}, {c; a},{c; b}, {c; b; a}.
Можно предположить, что добавление нового элемента удваивает число подмножеств.
Завершим доказательство применением метода математической индукции. Сущность этого метода в том, что если утверждение (свойство) справедливо для некоторого начального натурального числа n₀ и  если  из  предположения,  что  оно  справедливо  для  произвольного  натурального n = k ≥ n₀ можно доказать его справедливость для числа k + 1, то это свойство справедливо для всех натуральных чисел.

1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.

2.  Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2^k .

3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2^k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B {b}. Оно содержит k элементов. Все подмножества множества A – это подмножества множества B, не содержащие элемент b и, по предположению, их 2^k штук. Подмножеств множества B, содержащих элемент b, столько же, т.е. 2^k
штук.

Следовательно, всех подмножеств множества B: 2^k + 2^k = 2 ⋅ 2^k = 2^k+1 штук.
Теорема доказана.

В примере 1 множество А = {а, с, р, о} состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 2⁴=16.

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

Пример 2. Eсть множество {a b c}, в соответствие ставятся следующие числа:
000 = {0} (пустое множество)
001 = {c}
010 = {b}
011 = {b c}
100 = {a}
101 = {a c}
110 = {a b}
111 = {a b c}

Калькулятор множества всех подмножеств.

В калькуляторе уже набраны элементы множества А = {а, с, р, о}, достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Подмножества множеств. Алгебра подмножеств

Два множества A и
B равны, если они состоят из одних и тех
же элементов.

Из этого принципа
следует, что для любых двух различных
множеств всегда найдется некоторый
объект, являющийся элементом одного из
них и не являющийся элементом другого.
Так как пустые совокупности не содержат
элементов, то они не различимы и поэтому
пустое множество – единственно.

Подмножества. Определение
равенства множеств можно сформулировать
иначе, используя понятие подмножества.

Определение. Множество
A называется подмножеством множества
B
,
если каждый элемент A является элементом
B.

.

Следствие 1. Очевидно,
для любого множества A, т.к. каждый элемент
из A есть элемент из A.

Следствие 2. Для
любого множества A,
,
ибо если бы пустое множество не являлось
подмножеством A, то в пустом подмножестве
существовали бы элементы, не принадлежащие
A. Однако пустое множество не содержит
вообще ни одного элемента.

Если
,
то пишут,
и если,
то A – собственное подмножество B.

Понятие подмножества
множеств позволяет легко формализовать
понятие равенства двух множеств.

Утверждение. Для
любых A и B

. (1.1)

Логическую
эквивалентность, определяемую выражением
(1.1) используют как основной способ
доказательства равенства двух множеств.

Замечание. Отношение
включения 
обладает рядом очевидных свойств:

(рефлексивность);

(транзитивность).

Для любого
множества X можно определить специальное
множество всех подмножеств множества
X, которое называется булеаном ℬ,
которое включает в себя само множество
X, все его подмножества и пустое множество
.

Пример. Пусть
– это множество, состоящее из трех
элементов. Тогда булеанℬ(X)
это множество:

ℬ

Собственными
подмножествами ℬ(X)
являются следующие множества:

{a},{b},{c},{a,b},{b,c},{a,c}.

В общем случае,
если множество X содержит n элементов,
то множество его подмножеств ℬ(X)
состоит из

элементов.

Операции на множествах.

Пусть U – универсальное
множество,
.
Тогда для множеств X,Y можно определить
операции.

Определение. Объединением
множеств X и Y называется множество
,
состоящее из элементов, входящих хотя
бы в одно из множеств (X или Y):

. (1.2)

Рис.
1.1 – Объединение
множеств Рис.
1.2 – Пересечение
множеств

Определение. Пересечением
множеств X и Y называется множество
,
состоящее из элементов, входящих в X и
в Y одновременно:

. (1.3)

Определение. Разностью
множеств X и Y называется множество
,
состоящее из элементов, входящих в
множество X, но не входящих в Y:

. (1.4)

Рис.
1.3 – Разность
множеств
Рис.
1.4 –
Симметрическая

разность
множеств

Определение. Симметрической
разностью двух множеств X и Y называется
множество
,
состоящее из элементов множества X и
элементов множества Y, за исключением
элементов, являющихся общими для обоих
множеств:

. (1.5)

Определение. Для
любого множества
дополнением множествадо U называется такое множество,
что:

. (1.6)

Рис.
1.5 – Дополнение
множества X до U

На рис. 1.1 
1.5 представлены диаграммы Венна, наглядно
демонстрирующие результаты операций
.

Дополнение множества
иногда обозначается
.
Операциисвязаны между собой законами де Моргана:

, (1.7)

. (1.8)

В справедливости
законов де Моргана легко убедиться
самостоятельно.

В таблице 1.1
представлены основные свойства операций
над множествами.

Таблица 1.1

№	Свойства операций	Объединение, пересечение, дополнение
1	коммутативность	,
2	ассоциативность	,
3	дистрибутивность	,
4	идемпотентность	, ,,,,
5	теоремы де Моргана	,
6	инволюция

Операции объединения
и пересечения можно обобщить. Пусть
– множество индексов,– семейство подмножеств множества X.

Определение. Семейство
подмножеств
множества X, для которых,
называетсяразбиением
множества
X, если выполняются следующие два условия:

,

.

Определение. Семейство
подмножеств
множества X называетсяпокрытием
множества X, если:
.

Будем, как и ранее,
считать, что все рассматриваемые
множества являются подмножествами
некоторого универсального множества
U. Тогда имеет место следующее определение.

Определение. Класс
K подмножеств из U называется алгеброй,
если:

1. ;

2. из
того, что
следует, что;

3. из
того, что
следует, что.

Пример. Пусть
,
тогда классобразует алгебру.

Определение. Класс
F подмножеств из U образует
-алгебру,
если:

1. ;

2. из
того, что
следует;

3. из
того, что
,следует, что.

Пример. Множество
всех подмножеств U образует
-алгебру,
т.е.ℬ(U)
–
-алгебра.

Соседние файлы в папке ЛЕКЦИИ АиГ

• #
• #
• #

  14.04.2015904.7 Кб67Копия ЛЕКЦИЯ 14.wbk

• #
• #
• #

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

Определение[править | править код]

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

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

« является подмножеством (нестрогим)» обозначается	« является строгим подмножеством » обозначается	Примечание
		Символ является аналогом , то есть в случае допускается равенство множеств; символ является аналогом , то есть в случае в есть элементы, которых нет в .
		Для понятия «(нестрогое) подмножество» используется более простой символ, так как оно считается более «фундаментальным».

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

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

То, что является надмножеством множества , записывают , то есть

Множество всех подмножеств множества обозначается .

Множества и называются равными , только когда они состоят из одних и тех же элементов, то есть и .^[2]

Собственное и несобственное подмножество[править | править код]

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

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

множество является собственным подмножеством множества , только если и , .

Зарубежная литература[править | править код]

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

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

множество является нетривиальным подмножеством множества , если является собственным подмножеством (proper subset) и .

Примеры[править | править код]

Свойства[править | править код]

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

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

Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у -элементного множества существует подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет -кратным произведением двоек. Если же рассматривать только подмножества -элементного множества из элементов, то их количество выражается биномиальным коэффициентом . Для проверки этого факта можно выбирать элементы подмножества последовательно. Первый элемент можно выбрать способами, второй способом, и так далее, и, наконец, -й элемент можно выбрать способом. Таким образом мы получим последовательность из элементов, и ровно таким последовательностям соответствует одно подмножество. Значит, всего найдётся таких подмножеств.

Примечания[править | править код]

Литература[править | править код]

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

Ссылки[править | править код]

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

Понятие множества

Что такое «множество», мы понимаем интуитивно. В этом смысле это понятие первично, так же как «точка» или «плоскость».

Создатель теории множеств Г.Кантор описывал множество как «многое, мыслимое нами как единое».

Приведём примеры множеств:

Конечное, бесконечное и пустое множества

Людей в салоне самолёта легко посчитать, это множество конечно.

С деревьями в парке, планетами и электронами – сложней. Скорее всего, мы не сможем назвать точное количество элементов этих множеств в данный момент времени. Однако, и эти множества конечны.

Натуральное число – это идеальный объект, абстракция. Множество натуральных чисел бесконечно. Как оказалось, человек может оперировать и абстракциями, и бесконечностями.

Можно себе представить даже то, «чего на свете вообще не может быть». Поскольку таких объектов нет, их множество будет пустым. Пустое множество является частью любого другого множества.

Способы задания множеств

1) Перечисление – в списке задаются все элементы множества.

Например:

Множество всех континентов Земли:

{Евразия,Северная Америка,Южная Америка,Африка,Австралия,Антарктида}

Множество букв слова «математика»: {м,а,т,е,и,к}

Множество натуральных чисел меньших 5: {1,2,3,4}

2) Характеристическое свойство – указывается особенность элементов множества.

Например:

A = ${x|x gt 0, x in Bbb R}$ – множество всех действительных положительных x

B = ${n|n⋮5,n in Bbb N}$ – множество всех натуральных n, кратных 5

C = ${(x,y)|x^2+y^2 ge 1,x in Bbb R,y in Bbb R}$ – множество всех действительных точек координатной плоскости (x,y), расстояние от которых до начала координат не больше 1 (круг с центром в начале координат, радиусом 1).

D = {k|k-материк Земли} – множество всех материков планеты Земля

3) Графическое изображение – визуальное моделирование с помощью различных диаграмм (круги Эйлера, интервалы, графики и т.п.)

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

Знак $subseteq$ является аналогом $ge$, т.е. «нестрогим» неравенством. Это значит, что множества A и B могут и совпадать (любое множество является подмножеством самого себя).

Между множествами можно также ввести отношение «строгое подмножество», $A subset B$, в котором B заведомо «шире» множества A (аналог строгого неравенства $lt$).

Примеры подмножеств:

Множество людей является подмножеством приматов, живущих на Земле.

Множество натуральных чисел меньших 5 является подмножеством натуральных чисел меньших $10: A = {n|n lt 5, n in Bbb N}, B = {m|m lt 10, m in Bbb N}, A subseteq B$

Множество квадратов является подмножеством прямоугольников.

Множество полосатых летающих слонов – как пустое множество – является подмножеством чего угодно: приматов, чисел, прямоугольников. Что удобно для размышлений о смысле всего.

Примеры

Пример 1. Запишите данное множество с помощью перечисления элементов:

а) $A = {x|x^2 lt 5, x in Bbb Z}$

Задано множество целых чисел, квадрат которых меньше 5. Перечисляем:

A = {-2;-1;0;1;2}

б) $B = {x||x| ge 3, x in Bbb Z}$

Задано множество целых чисел, модуль которых не больше 3. Перечисляем:

B = {-3;-2;-1;0;1;2;3}

в) $ C = {x|(x-1)(2x+5) = 0, x in Bbb Q}$

Задано множество рациональных чисел, являющихся корнями уравнения

(x-1)(2x+5) = 0. Перечисляем:

C = {1;-2,5}

г) $D = {n|9 lt n ge 12, n in Bbb N}$

Задано множество натуральных чисел, входящих в полуинтервал $9 lt n le 12$.

Перечисляем:

D = {10;11;12}

Пример 2. Запишите данное множество с помощью характеристического свойства:

а) Множество всех натуральных чисел меньше 10

$$ A = {n|n lt 10, n in Bbb N} $$

б) Множество всех действительных чисел, кроме 0

$$ B = {x|x neq 0, x in Bbb R} $$

в) Множество всех точек с целыми координатами, принадлежащих прямой y = 2x+1

$$C = {(x,y)|y = 2x+1, x in Bbb Z, y in Bbb Z}$$

г) Множество всех целых решений уравнения $x^3+x^2+4 = 0$

$$ D = {x|x^3+x^2+4 = 0, x in Bbb Z} $$

Пример 3. Изобразите на графике в координатной плоскости данное множество:

а) $A = {(x,y)|y = x+2, x le 3, x in Bbb N}$

Задано конечное множество точек, которое можно представить перечислением:

A = {(1;3);(2;4);(3;5) }

На графике:

б)$ B = {(x,y)|y = frac{4}{x},-4 le x le -1, x in Bbb R}$

Задано бесконечное множество точек, принадлежащих данной гиперболе $y = frac{4}{x}$ в данном интервале $-4 le x le -1$. На графике:

Пример 4. Укажите и запишите с помощью перечисления одно из непустых конечных подмножеств для данного множества:

а) A = {k|k-электронное устройство}

$B subseteq A, B$ = {компьютер, смартфон, планшет}

б) A = {m|m-четырёхугольник}

$B subseteq A, B$ = {квадрат, ромб, прямоугольник}

в) A = {p|p-музыкальный инструмент}

$B subseteq A, B$ = {пианино, скрипка, виолончель}

г) A = {t|t-средство передвижения}

$B subseteq A, B$ = {автомобиль,автобус,поезд}

Пример 5*. Найдите булеан данного множества:

а) A = {5;10;27}

$$ P(A) = {{varnothing},{5},{10},{27},{5;10},{5;27},{10;27},{5;10;27} } $$

Исходное множество состоит из n = 3 элементов, булеан состоит из $2^3 = 8$ элементов.

б) B = {1;{2;16} }

$$ P(B) = {{varnothing},{1},{2;16},{1;{2;16} } } $$

Исходное множество состоит из n = 2 элементов, булеан состоит из $2^2 = 4$ элементов.