Как найти собственное подмножество множества - Исправление недочетов и поиск решений вместе с Examum.ru

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

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

Пример 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. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Источник

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

Рассмотрим операции над множествами, которые позволяют из уже имеющихся множеств образовывать новые множества.

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

Acup B={xcolon, xin Alor xin B} — объединение,
Acap B={xcolon, xin Aland xin B} — пересечение,
Asetminus B={xcolon, xin Aland xnotin B} — разность,
A,triangle, B=(Asetminus B)cup (Bsetminus A) — симметрическая разность,

т.е. объединение и есть множество всех таких , что является элементом хотя бы одного из множеств A,B ; пересечение и — множество всех таких , что — одновременно элемент и элемент ; разность A setminus B — множество всех таких , что — элемент , но не элемент ; симметрическая разность A,triangle, B — множество всех таких , что — элемент , но не элемент или — элемент , но не элемент .

Кроме того, фиксируя универсальное множество , мы можем определить дополнение overline{A} множества следующим образом: overline{A}=Usetminus A . Итак, дополнение множества — это множество всех элементов универсального множества, не принадлежащих .

Полезно разобраться в том, как операции над множествами, введенные выше, соотносятся с логическими операциями. Пусть A={xcolon, P(x)} и B={xcolon, Q(x)} , т.е. множество задано посредством характеристического предиката , а множество — посредством характеристического предиката .

Легко показать, что

Acup B=bigl{xcolon, P(x)lor Q(x)bigr},qquad Acap B=bigl{xcolon, P(x)land Q(x)bigr},qquad Asetminus B=bigl{xcolon, P(x)landlnot Q(x)bigr}.

Следующие процедуры получения новых множеств связаны с понятием подмножества. Говорят, что есть подмножество множества , если всякий элемент есть элемент . Для обозначения используют запись: Bsubseteq A . Говорят также, что содержится в или включено в , или включает (имеет место включение ). Считают, что пустое множество есть подмножество любого множества и, если фиксировано некоторое универсальное множество, каждое рассматриваемое множество есть его подмножество. Нетрудно проверить, что если A={xcolon, P(x)} и B={xcolon, Q(x)} , то Bsubseteq A тогда и только тогда, когда высказывание Q(x)Rightarrow P(x) тождественно истинно.

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

A=Bquad Leftrightarrowquad bigl((Asubseteq B)land (Bsubseteq A)bigr).

(1.2)

Формула (1.2) является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств и , т.е. что X=Y , достаточно доказать два включения X subseteq Y и Y subseteq X «, т.е. доказать, что из предположения xin X (для произвольного ) следует, что xin Y , и, наоборот, из предположения xin Y следует, что xin Y . Такой метод доказательства теоретико-множественных равенств называют методом двух включений. Примеры применения этого метода мы дадим позже.

Замечание. Равенство множеств {xcolon,P(x)} и {xcolon Q(x)} означает, что предикаты Р(х) и Q(x) эквивалентны, т.е. предикат Р(х) О Q{x) является тождественно истинным.

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

Если B subseteq A , но Bne A , то пишут B subset A и называют строгим подмножеством (или собственным подмножеством) множества , а символ subset — символом строгого включения.

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

$2^A=bigl{Xcolon~ Xsubseteq Abigr}.$

Для булеана используют также обозначения mathcal{P}(A),~mathcal{B} и exp(A) .

Пример. а. Булеан множества {a,b} состоит из четырех множеств

varnothing,~ {a},~ {b},~ {a,b} , то есть $2^{{a,b}}=bigl{varnothing,, {a},, {b},, {a,b}bigr}.$ .

б. Булеан $2^{mathbb{N}}$ состоит из всех возможных, конечных или бесконечных, подмножеств множества . Так, $varnothingin 2^{mathbb{N}}$ и ${5}in 2^{mathbb{N}}$ , вообще для любого множество ${n}in 2^{mathbb{N}}$ , множество

${1,2,ldots,n}in 2^{mathbb{N}},~ {ncolon, n=2k,~ k=1,2,ldots}in 2^{mathbb{N}}$ и т.д.

Для булеана 2^A мы можем рассматривать произвольные его подмножества. Таким подмножеством, например, будет Одноэлементное множество {B} , где — произвольное подмножество . Подчеркнем, что единственным элементом множества {B} является, в свою очередь, некоторое множество. Вообще же образование булеана открывает путь для построения множеств, элементами которых являются множества, элементами которых, в свою очередь, являются некоторые множества, и т.д. Так можно определить множества $2^{2^A},~ 2^{2^{2^A}}$ и т.д.

Свойства операций над множествами

Введенные выше операции над множествами обладают следующими свойствами:

$begin{array}{ll} bold{1)}quad Acup B=Bcup A; &qquad bold{12)}quad Acup U=U;\[2pt] bold{2)}quad Acap B=Bcap A; &qquad bold{13)}quad Acup overline{A}=U;\[2pt] bold{3)}quad Acup (Bcup C)= (Acup B)cup C; &qquad bold{14)}quad Acap overline{A}= varnothing;\[2pt] bold{4)}quad Acap (Bcap C)= (Acap B)cap C; &qquad bold{15)}quad Acup A=A;\[2pt] bold{5)}quad Acap (Bcup C)= (Acap B)cup (Acap C); &qquad bold{16)}quad Acap A=A;\[2pt] bold{6)}quad Acup (Bcap C)= (Acup B)cap (Acup C); &qquad bold{17)}quad overline{overline{A}}=A;\[2pt] bold{7)}quad overline{Acup B}= overline{A}cap overline{B}; &qquad bold{18)}quad A setminus B=Acap overline{B};\[2pt] bold{8)}quad overline{Acap B}= overline{A}cup overline{B}; &qquad bold{19)}quad A,triangle,B=(Acup B)setminus (Acap B);\[2pt] bold{9)}quad Acup varnothing=A; &qquad bold{20)}quad (A,triangle,B),triangle,C= A,triangle,(B,triangle,C);\[2pt] bold{10)}quad Acap varnothing=varnothing; &qquad bold{21)}quad A,triangle, B=B,triangle,A;\[2pt] bold{11)}quad Acap U=A; &qquad bold{22)}quad Acap (B,triangle,C)= (Acap B),triangle,(Acap C). end{array}$

Каждое из написанных выше равенств, верное для любых входящих в них множеств, часто называют теоретико-множественным тождеством. Любое из них может быть доказано методом двух включений. Докажем этим методом тождество 19.

Пусть xin A,triangle,B . Тогда, согласно определению симметрической разности, xin (A setminus B)cup (B setminus A) . Это означает, что или xin(B setminus A) . Если , то xin A и xnotin B , то есть xin Acup B и при этом xnotin Acap B . Если же xin (B setminus A) , то xin B и , откуда и . Итак, в любом случае из xin (A setminus B)cup (B setminus A) следует и , то есть xin (Acup B)setminus (Acap B) . Таким образом, доказано, что

A,triangle,B subseteq (Acup B)setminus (Acap B).

Покажем обратное включение (Acup B)setminus (Acap B)subseteq A,triangle,B .

Пусть xin (Acup B)setminus (Acap B) . Тогда xin Acup B и xnotin Acap B . Из следует, что xin A или xin B . Если xin A , то с учетом имеем xnotin B , и поэтому xin Asetminus B . Если же xin B , то опять-таки в силу получаем, что и xin Bsetminus A . Итак, xin A setminus B или xin B setminus A , то есть xin (Asetminus B)cup (Bsetminus A) . Следовательно,

(Acup B)setminus (Acap B)subseteq A,triangle,B,.

Оба включения имеют место, и тождество 19 доказано.

Метод двух включений является универсальным и наиболее часто применяемым методом доказательства теоретико-множественных тождеств. Помимо метода двух включений для доказательства теоретико-множественных тождеств могут быть использованы другие методы, например метод характеристических функций.

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

Докажем этим методом тождество 22, пользуясь тождествами 1-19. Преобразуем левую часть к правой:

$begin{aligned} (Acap B),triangle,(Acap C)&= bigl((Acap B)cup (Acap C)bigr)cap overline{(Acap B)cap (Acap C)}=\[2pt] &= bigl(Acap (Bcup C)bigr)cap bigl(overline{Acap B}cup overline{Acap C}bigr)=\[2pt] &= bigl(Acap (Bcup C)bigr)cap bigl(overline{A}cup overline{B}bigr)cup bigl(overline{A}cup overline{C}bigr)=\[2pt] &=bigl(Acap (Bcup C)bigr)cap bigl(overline{A}cup (overline{B}cup overline{C})bigr)=\[2pt] &= bigl(bigl(Acap (Bcup C)bigr)cap overline{A}bigr)cup bigl((Acap (Bcup C))cap (overline{B}cup overline{C})bigr)=\[2pt] &= varnothingcup bigl(bigl(Acap (Bcup C)bigr)cap bigl(Acap (overline{B}cup overline{C})bigr)bigr)=\[2pt] &= bigl(Acap (Bcup C)bigr)cap bigl(Acap overline{Bcap C}bigr)=\[2pt] &=Acap bigl((Bcup C)cap overline{Bcap C}bigr)=\[2pt] &=Acap bigl((Bcup C) setminus (Bcap C)bigr)=\[2pt] &= Acap (B,triangle,C). end{aligned}$

Таким образом, тождество доказано.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

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

Источник

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

Два множества 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
#
#
#

Источник

Множество — это набор элементов, которые обладают общим свойством. В каждом неупорядоченном множестве существует определенное количество подмножеств, которые можно рассчитать при помощи онлайн-калькулятора.

Множество

Множество представляет собой набор элементов, сгруппированных по определенному признаку. В математике это может быть множество натуральных, целых или рациональных чисел. В природе это множества яблок на дереве, песчинок в пустыне или звезд в космосе. На практике множество может представлять собой набор данных, массивы результатов измерений или входных воздействий. Множество — это простейший математический объект, поэтому с ним можно осуществлять простые арифметические действия, то есть складывать, вычитать или разбивать на составляющие — подмножества.

Несобственные подмножества

Каждое множественный объект имеет два несобственных подмножества: само множество и пустое. Согласно канторовской теории, любое множество считается подмножеством самого себя. Пустое множество — это своеобразный нуль теории множеств, и такой набор не содержит ни одного элемента. Потребность в пустом множестве обусловлена аксиомой, что любой результат операции между множествами также должен быть множеством. Пустой набор элементов также считается подмножеством для любого набора чисел.

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

Помимо самого себя и пустого множества, набор чисел может иметь определенное количество собственных подмножеств. Их численность определяется мощностью множества, то есть количеством его элементов. Для объекта A, которое состоит из n-ного числа элементов, существует количество собственных подмножеств, которое определяется по формуле:

N = 2ⁿ — 2.

Из этого следует, что для набора из 3 элементов существует 2³ — 2 = 6 собственных подмножеств, из 4 членов — 2⁴ — 2 = 14 собственных подмножеств и так далее. К примеру, для множества {X, Y, Z} существуют следующие подмножества:

{X};
{Y};
{Z};
{XY};
{XZ};
{ZY}.

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

N = 2ⁿ,

где n — количество элементов.

Это означает, что для того же набора {X, Y, Z} добавятся также пустое множество и оно само.

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

Канторовская теория множеств зашла в тупик, когда ее постулаты породили парадоксы. Наиболее известной проблемой наивной теории множеств считается парадокс Рассела. Известный британский философ и ученый Бертран Рассел рассмотрел бесконечные множества как абстрактные объекты. Если любое множество считается подмножеством самого себя, то верно выражение A Î A. Допустим, существует глобальное множество S, содержащее в себе все наборы объектов, которые не включают самих себя.

Далее возникает вопрос, верно ли, что S Î S? Если верно, то выходит, что S не содержит самого себя, так как изначально набор S содержит все множества, не содержащие себя, следовательно, S Î S. Если неверно, значит, набор S не соответствует первичному определению, следовательно, S Î S.

Данный парадокс так же известен как проблема цирюльника. Некий брадобрей заявляет, что будет брить только тех, кто не бреет сам себя. Тех, кто сами справляются с бритвой, цирюльник брить отказывается. Возникает парадокс: кто побреет цирюльника? Если он бреется сам, то он не должен себя брить, а если не бреется, то брить себя обязан. Для решения подобных парадоксов в теорию множеств была внесен раздел о типах объектов. Согласно теории типов, подмножества всегда должны быть низшего порядка по отношению к своему надмножеству.

Наша программа позволяет сгенерировать все возможные подмножества для любого заданного набора чисел. Для этого вам достаточно ввести числа через запятую в форму онлайн-калькулятора, после чего программа рассчитает все подмножества для выбранного набора, включая собственные и несобственные. Рассмотрим пример генерации подмножеств.

Пример работы калькулятора

Допустим, у нас есть множество последовательных натуральных чисел мощностью 4. Это означает, что наш объект выглядит как А = {1, 2, 3, 4,}. Согласно формуле, для A существует 2⁴ = 16 подмножества: 14 собственных и 2 несобственных. При помощи калькулятора рассчитаем эти составляющие. Мы получим:

пустое множество — {};
одноэлементные наборы — {1}, {2}, {3}, {4};
двухэлементные — {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4};
трехэлементные — {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4};
само множество — {1, 2, 3, 4}.

Точно также вы можете рассчитать количество подмножеств для множества произвольной мощности.

Заключение

Множество — это элементарный математический объект, с которым можно осуществлять разные арифметические операции. Используйте наши онлайн-калькуляторы для работы с множественными объектами.

Источник

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

– множества.

Множество — подмножество (англ. subset, нем. Teilmenge) множества , если любой элемент множества является элементом множества :

Обозначим .

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

– множества

Множество – собственное подмножество (англ. proper subset, нем. echte Teilmenge) множества , если множество является подмножеством множества и существует элемент множества , не принадлежащий множеству :

${displaystyle Upsilon (a,b) {stackrel {mathrm {def} }{=}} asubseteq b;land ;{bigl (}exists cquad cin b;land ;^{neg }(cin a){bigr )}}$

Обозначим .

Подмножество топологического пространства[]

Множество — подмножество (англ. subset, нем. Teilmenge) топологического пространства , если множество является подмножеством носителя топологического пространства :

Собственное подмножество топологического пространства[]

Множество – собственное подмножество (англ. proper subset, нем. echte Teilmenge) топологического пространства , если множество является собственным подмножеством носителя топологического пространства :

Подмножество метрического пространства[]

Множество — подмножество (англ. subset, нем. Teilmenge) метрического пространства , если множество является подмножеством носителя метрического пространства :

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

Множество – собственное подмножество (англ. proper subset, нем. echte Teilmenge) метрического пространства , если множество является собственным подмножеством носителя метрического пространства :

Источник