Способ задания множества порождающая процедура

II. Порождающая процедура

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

1) Описание множества (множество всех чисел вида ), где исходные объекты для построения множества — натуральные числа, а порождающая процедура для вычисления описана формулой .

2) Множество

Порождающая процедура определяется двумя правилами:

а) ; б) если , то .

Правила, описанные таким образом, называются индуктивными или рекурсивными.

3) Множество , заданное следующим образом.

Пусть имеется процедура вычисления цифр разложения числа  в бесконечную десятичную дробь

По мере вычисления будем образовывать из последовательности цифр данной десятичной дроби трехзначные числа

314, 159, 265 и т. д.

Множество всех таких чисел образует множество .

4) Распространенная порождающая процедура — образование новых множеств из других множеств с помощью операций над множествами.

III. Задание множества описанием его элементов (разрешающая процедура)

— множество всех натуральных чисел (N).

— множество всех решений уравнения .

— множество всех действительных чисел.

— множество всех чисел , где можно интерпретировать как описание свойства его элементов, заключающегося в возможности представить их в виде .

— заданное как “множество всех целых чисел, являющихся степенью двойки”, . Такой способ задания множества применяется, когда свойство элементов М может быть описано коротким выражением. Например, P(x) читается: «х обладает свойством Р», то М задается при помощи обозначения читается: «М — множество элементов х, обладающих свойством Р».

1) .

2) .

Требования к описанию свойств — точность и недвусмысленность.

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

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

Для , то есть для свойства, быть степенью двойки разрешающей процедурой является любой метод разложения целых чисел на простые множители. Здесь разрешающая процедура не является порождающей. Но ее нетрудно таковой сделать: например, порождающая процедура может быть таковой. Берем последовательно все натуральные числа и каждые из них разлагаем на простые множители: те числа, которые не содержат множителей, отличных от двойки, включаем в .

С другой стороны порождающая процедура может не быть разрешающей. Например, при получении действует порождающая процедура. Но с ее помощью нельзя определить, будет ли произвольное трехзначное число принадлежать или нет, т. е. множество бесконечно, и если при построении n — чисел множества некоторое (проверяемое) число не встретилось, то еще нельзя утверждать, что оно не принадлежит .

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

Суть разрешающей процедуры в том, что она разрешает (или не разрешает) предложенному для проверки объекту быть или не быть элементом данного множества в зависимости от его свойств.

Понятие “точно заданное множество” нуждается в уточнении. Одна из основных трудностей задания множества (даже из множеств, точность описания которых не вызывает сомнения) с помощью вполне, казалось бы, законных средств — в том, что можно сконструировать описание множеств, которые приводят к противоречиям — “парадоксам теории множеств”. Например, множество всех подмножеств по смыслу своего описания этого множества должно содержать все мыслимые множества. Но оно само содержится в множестве своих подмножеств в качестве элемента.

Перед дальнейшим изложением будет удобно определить два специальных множества.

Определение: Пустое множество (обозначается ) есть множество, обладающее свойством:

при любом х.

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

Определение: Универсальное множество (обозначается U) есть множество всех рассматриваемых в данной задаче элементов.

Рассмотрим теперь множество. Оно имеет n элементов. Будем говорить, что мощность этого множества есть n.

Определение: Мощностью (длиной, размерностью) множества называется число элементов этого множества. Обозначим .

Далее любое множество В, которое имеет то же число элементов, что и А, имеет такую же мощность, и естественно, эти элементы не надо пересчитывать. Для небольших множеств достаточно легко пересчитать элементы, но для других множеств, например N, это может быть невозможно. Далее следует строгое, но неформальное определение количества элементов.

Определение: Говорят, что множество Х конечно, если или для некоторого существует множество такое, что оно имеет то же самое число элементов, что и X. Если и никакого n не может быть найдено, то Х называют бесконечным.

Источник

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

Множество считается заданным, если о каждом элементе можно однозначно сказать, принадлежит он этому множеству или нет.

А) Простейший способ задания множества состоит просто в перечислении всех элементов данного множества.

Если множество A конечное, состоящее из элементов A1, A2, …, AN, то пишут A = <A1, A2, …, AN> . В частности, <A> — множество, состоящее из одного элемента A.

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

Б) Другой, универсальный способ: задание множества A С помощью характеристического свойства элементов данного множества, то есть такого свойства, которым обладают все элементы множества A и не обладают другие элементы, не принадлежащие A.

Если P(X) — такое свойство, то пишут: .

Например, для конечного множества A = <A1, A2,…, AN> можно записать: A = <X | x = A1, или X = a2, или …, или X = AN>. Множество всех депутатов парламента можно задать тьак: D = <X | X — депутат>. Множество всех студентов S = <x | X — студент>.

В) Еще один способ — это задание множества с помощью порождающей процедуры, или алгоритмический способ.

Например, пусть M = <1, 2, 4, 8, 16,…>— множество степеней числа 2. Тогда его можно задать так:

1) ; 2) если , то .

Другой пример: множество МP = <314, 159, 256, 358, …>задается как последовательность троек подряд идущих цифр десятилетней записи числа p = 3,141592653589793238462… . (В действительности, учитывая трансцендентность числа p, множество МP содержит все целые числа от 0 до 999.)

Г) Четвертый способ — задание множеств с помощью операций над уже известными множествами.

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

Надежный способ точного описания множества — распознающая (разрешающая) процедура. Например, для множества степеней двойки М2N разрешающей процедурой может служить разложение числа на простые множители.

Задание множества М4 нельзя отнести ни к одному из перечисленных способов; оно по сути совсем не задано, а только названо. Задать его можно списком футболистов, или описанием: М4 есть множество лиц, имеющих удостоверение футболиста клуба «Динамо-Минск». В этом случае разрешающая процедура — это проверка документов.

Источник

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

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

Начнём с того, что же, собственно, понимать под словом «множество». На интуитивном уровне под множеством понимают некую совокупность объектов, именуемых элементами множества. Например, можно говорить о множестве груш на столе, множестве букв в слове «множество» и так далее. Георг Кантор (немецкий математик, основатель современной теории множеств) писал, что под «множеством я понимаю вообще всё то многое, которое возможно мыслить как единое, т.е. такую совокупность определённых элементов, которая посредством одного закона может быть соединена в одно целое». Некоторое время понятие множества, введённое Кантором, полагалось довольно очевидным и не требующим дополнительных пояснений. Казалось, что появление работ Больцано, а затем и Кантора в конце 19 — начале 20 века, положит конец многим вопросам (например, окончательно разрешит апории Зенона, разрешит проблему бесконечности и т.д.) и станет началом новой математики. Гениальный немецкий математик Давид Гильберт отмечал, что «Никто не изгонит нас из рая, созданного Кантором».

Однако появление парадоксов (Рассел, Бурали-Форти) положило конец «канторовскому раю». Одна из формулировок парадокса Рассела, известная под названием «парадокс брадобрея» звучит так: в некотором селе брадобрей бреет тех и только тех жителей села, которые не бреются сами. Кто же тогда бреет самого брадобрея? Допустим, он бреет себя самостоятельно. Т.е. он принадлежит к тем жителям села, которые бреются сами, – а ведь согласно условию этих жителей брадобрей не имеет права брить. Следовательно, допущение о том, что брадобрей бреется сам, приводит к противоречию. Попробуем иначе: пусть брадобрей не бреется сам. Если он сам не бреется, то согласно условию его обязан брить брадобрей – вновь противоречие! Были предприняты попытки разрешить противоречия теории множеств, предложенной Кантором. Саму канторовскую теорию множеств математики назвали «наивной». Целью многих математических трудов стало построение такой системы аксиом, в которой подобные парадоксы были бы невозможны. Но задача оказалась не столь уж проста. На данный момент, насколько мне известно, единой аксиоматики теории множеств нет. Наиболее распространенной считается система аксиом Цермело-Френкеля (ZFC), в которой особняком стоит так называемая «аксиома выбора». Есть и вариации этой системы: например, автор B-метода Жан-Раймонд Абриал предложил типизированную теорию множеств, на основании которой создал формальный метод разработки программ.

Обозначение множеств. Принадлежность элемента множеству. Пустое множество.

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

А множество всех целых целых чисел, больших 8, но меньших 15, будет таким:

Множество может вообще не содержать ни одного элемента. В этом случае его именуют пустым множеством и обозначают как $\varnothing$.

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

Есть и устоявшиеся обозначения определённых множеств. Например, множество натуральных чисел принято обозначать буквой $N$; множество целых чисел – буквой $Z$; множество рациональных чисел – буквой $Q$; множество всех действительных чисел – буквой $R$. Есть и иные устоявшиеся обозначения, но к ним мы станем обращаться по мере необходимости.

Например, указанное выше множество $A=\<0, 5, 6, -9 \>$ – конечное множество, ибо содержит 4 элемента (т.е. конечное число элементов). Множество натуральных чисел $N$ является бесконечным. Вообще говоря, мы не всегда можем сразу с уверенностью сказать, бесконечно некое множество или нет. Например, пусть $F$ – множество простых чисел.

Простыми числами именуют такие натуральные числа большие 1, которые делятся лишь на 1 или на самое себя. Например, 2, 3, 5, 7 и так далее. Для сравнения: число 12 не является простым числом, так как оно делится не только на 12 и 1, а ещё и на иные числа (например, на 3). Число 12 является составным.

Возникает вопрос: бесконечно множество $F$ или нет? Существует ли наибольшее простое число? Для ответа на этот вопрос понадобилась целая теорема, доказанная Эвклидом, о том, что множество простых чисел – бесконечно.

Например, так как конечное множество $A=\<0, 5, 6, -9 \>$ содержит 4 элемента, то мощность множества $A$ равна 4, т.е. $|A|=4$.

Если нам известно, что некий объект $a$ принадлежит множеству $A$, то записывают это так: $a\in A$. Например, для вышеуказанного множества $A$ можно записать, что $5\in A$, $-9\in A$. Если же объект $a$ не принадлежит множеству $A$, то обозначается это следующим образом: $a\notin A$. Например, $19\notin A$. Кстати, сказать, элементами множеств могут быть и иные множества, например:

Элементами множества $M$ являются числа -9, 1, 0, а также множество $ \< a,\; g\>$ и пустое множество $\varnothing$. Вообще, для упрощения восприятия множество можно представлять как портфель. Пустое множество – пустой портфель. Эта аналогия пригодится чуть далее.

Подмножество. Универсальное множество. Равенство множеств. Булеан.

Например, рассмотрим множества $K=\< -9,5\>$ и $T=\<8,-9,0,5,p, -11\>$. Каждый элемент множества $K$ (т.е. -9 и 5) является также элементом множества $T$. Следовательно, множество $K$ есть подмножество множества $T$, т.е. $K\subseteq T$.

Так как все элементы любого множества $A$ принадлежат самому множеству $A$, то множество $A$ является подмножеством самого множества $A$. Пустое множество $\varnothing$ является подможеством любого множества. Т.е. для произвольного множества $A$ верно следующее:

$$A\subseteq A; \; \varnothing\subseteq A.$$

Введём ещё одно определение – универсальное множество.

Иными словами, универсум содержит в себе элементы всех множеств, которые рассматриваются в рамках некоей задачи. Например, рассмотрим такую задачу: проводится опрос студентов некоей академгруппы. Каждому студенту предлагается указать мобильных операторов РФ, сим-карты которых он использует. Данные этого опроса можно представить в виде множеств. Например, если студент Василий использует сим-карты от МТС и Life, то можно записать следующее:

Подобные множества можно составить для каждого студента. Универсумом в этой модели будет множество, в котором перечислены все операторы России. В принципе, в качестве универсума можно взять также множество, в котором перечислены все операторы СНГ, а также множество всех мобильных операторов мира. И это не будет противоречием, ибо любой оператор России входит в множество операторов как СНГ, так и всего мира. Итак, универсум определяется только в рамках некоей конкретной задачи, при этом зачастую можно рассмотреть несколько универсальных множеств.

Определение равенства множеств можно записать и по-иному: если $A\subseteq B$ и $B\subseteq A$, то $A=B$.

Рассмотрим пару множеств: первое будет $\<\Delta, k \>$, а второе – $\$. Каждый элемент первого множества (т.е. $\Delta$ и $k$) является также элементом второго множества. Каждый элемент второго множества (т.е. $k$ и $\Delta$) является также элементом второго множества. Вывод: $\<\Delta, k \>=\$. Как видите, порядок записи элементов в множестве роли не играет.

Рассмотрим ещё пару множеств: $X=\$ и $Y=\<\Delta, k \>$. Каждый элемент множества $X$ является также элементом множества $Y$; каждый элемент множества $Y$ является также элементом множества $X$. Следовательно, $\=\<\Delta, k \>$. С учётом подобных равенств в теории множеств принято одинаковые элементы не повторять в записи дважды. Например, множество цифр числа 1111111555559999 будет таким: $\<1,5,9\>$. Есть, конечно, исключения: так называемые мультимножества. В записи мультимножеств элементы могут повторяться, однако в классической теории множеств повторения элементов не допускаются.

Используя понятие равенства множеств, можно классифицировать подмножества.

Если же некое подмножество множества $A$ совпадает с самим множеством $A$, то это подмножество называют несобственным. Иными словами, множество $A$ является несобственным подмножеством самого множества $A$.

Например, для рассмотренных выше множеств $K=\< -9,5\>$ и $T=\<8,-9,0,5,p, -11\>$ имеем: $K\subseteq T$, при этом $K\neq T$. Следовательно, множество $K$ является собственным подмножеством множества $T$, что записывается как $K\subset T$. Можно сказать и так: множество $K$ строго включено в множество $T$. Запись $K\subset T$ более конкретна, нежели $K\subseteq T$. Дело в том, что записывая $K\subset T$ мы гарантируем, что $K\neq T$. В то время как запись $K\subseteq T$ не исключает случая равенства $K=T$.

Примечание относительно терминологии: показать\скрыть

Вообще говоря, тут есть некая путаница в терминологии. Приведённое выше определение несобственных множеств принято в американской и части отечественной литературы. Однако в другой части отечественной литературы есть несколько иная трактовка понятия несобственных множеств.

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

Пусть множество $A$ содержит $n$ элементов. Булеан множества $A$ содержит $2^n$ элементов, т.е.

Рассмотрим пару примеров на использование введённых выше понятий.

Из предложенного списка выберите те утверждения, которые являются верными. Ответ аргументируйте.

1. Нам заданы два множества: $\<-3,5, 9 \>$ и $\<-3, 9, 8, 5, 4, 6 \>$. Каждый элемент первого множества является также элементом второго множества. Следовательно, первое множество есть подмножество второго, т.е. $\<-3,5, 9 \>\subseteq \<-3, 9, 8, 5, 4, 6 \>$. Утверждение первого пункта – верное.
2. В первом пункте мы выяснили, что $\<-3,5, 9 \>\subseteq \<-3, 9, 8, 5, 4, 6 \>$. При этом данные множества не равны между собой, т.е. $\<-3,5, 9 \>\neq \<-3, 9, 8, 5, 4, 6 \>$. Значит, множество $\<-3,5, 9 \>$ является собственным (в иной терминологии строгим) подмножеством множества $\<-3, 9, 8, 5, 4, 6 \>$. Этот факт записывается как $\<-3,5, 9 \>\subset \ <-3, 9, 8, 5, 4, 6 \>$. Итак, утверждение второго пункта истинно.
3. Множество $\<-3,5, 9 \>$ не является элементом множества $\<-3, 9, 8, 5, 4, 6 \>$. Утверждение третьего пункта ложно. Для сравнения: утверждение $\<-3,5, 9 \>\in \<9, 8, 5, 4, \<-3,5,9\>, 6 \>$ истинно.
4. Пустое множество является подможеством любого множества. Поэтому утверждение $\varnothing \subseteq \varnothing$ истинно.
5. Утверждение ложно. Множество $\varnothing$ не содержит элементов, а множество $\<\varnothing \>$ содержит один элемент, посему равенство $\varnothing=\<\varnothing \>$ неверно. Чтобы это было нагляднее, можно обратиться к той аналогии, что я описал выше. Множество – это портфель. Пустое множество $\varnothing$ – пустой портфель. Множество $\<\varnothing \>$ – портфель, внутри которого лежит пустой портфель. Естественно, что пустой портфель и непустой портфель, внутри которого нечто есть – разные портфели 🙂
6. Пустое множество не содержит элементов. Ни единого. Поэтому утверждение $\varnothing \in \varnothing$ ложно. Для сравнения: утверждение $\varnothing\in\<\varnothing \>$ истинно.
7. Множество $A$ содержит 4 элемента, а именно: 9, -5, 8 и $\<7, 6 \>$. Поэтому мощность множества $A$ равна 4, т.е. $|A|=4$. Следовательно, утверждение о том, что $|A|=5$ – ложно.

Ответ: Утверждения в пунктах №1, №2, №4 – истинны.

Записать булеан множества $A=\<-5,10,9\>$.

Множество $A$ содержит 3 элемента. Иными словами: мощность множества $A$ равна 3, $|A|=3$. Следовательно, множество $A$ имеет $2^3=8$ подмножеств, т.е. булеан множества $A$ будет состоять из восьми элементов. Перечислим все подмножества множества $A$. Напомню, что пустое множество $\varnothing$ является подмножеством любого множества. Итак, подмножества таковы:

Напомню, что подмножество $\<-5, 10, 9 \>$ является несобственным, так как совпадает с множеством $A$. Все остальные подмножества – собственные. Все записанные выше подмножества являются элементами булеана множества $A$. Итак:

Булеан найден, остаётся лишь записать ответ.

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

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

Часто в литературе можно встретить обозначения такого характера: $T=\<0,2,4,6,8, 10, \ldots \>$. Здесь множество задаётся не перечислением элементов, как кажется на первый взгляд. Перечислить все чётные неотрицательные числа, которые и составляют множество $T$, невозможно, ибо этих чисел бесконечно много. Запись вида $T=\<0,2,4,6,8, 10, \ldots \>$ допускается только тогда, когда не вызывает разночтений.

Второй способ – задать множество с помощью так называемого характеристического условия (характеристического предиката) $P(x)$. В этом случае множество записывается в таком виде:

Запись $\$ читается так: «множество всех элементов $x$, для которых высказывание $P(x)$ истинно». Что именно значит словосочетание «характеристическое условие» проще пояснить на примере. Рассмотрим такое высказывание:

$$P(x)=»x\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$

Подставим в это высказывание вместо $x$ число 27. Мы получим:

$$P(27)=»27\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$

Это истинное высказывание, так как 27 действительно является натуральным числом, последняя цифра которого равна 7. Подставим в это высказывание число $\frac<2><5>$:

$$P\left(\frac<2><5>\right)=»\frac<2><5>\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$

Это высказывание ложно, так как $\frac<2><5>$ не является натуральным числом. Итак, для некоторых объектов $x$ высказывание $P(x)$ может быть ложно, для некоторых – истинно (а для некоторых вообще не определено). Нас будут интересовать лишь те объекты, для которых высказывание $P(x)$ будет истинно. Именно эти объекты и образуют множество, заданное с помощью характеристического условия $P(x)$ (см. пример №3).

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

Записать множество $A=\$ перечислением элементов.

Множество $A$ теперь задано с помощью перечисления элементов.

Описать элементы множества $M$, которое задано такой порождающей процедурой:

1. $3\in M$;
2. Если элемент $x\in M$, то $3x\in M$.
3. Множество $M$ – является подмножеством любого множества $A$, удовлетворяющего условиям №1 и №2.

Давайте пока оставим в покое условие №3 и посмотрим, какие элементы входят в множество $M$. Число 3 туда входит согласно первому пункту. Так как $3\in M$, то согласно пункту №2 имеем: $3\cdot 3\in M$, т.е. $9\in M$. Так как $9\in M$, то согласно пункту №2 получим: $3\cdot 9\in M$, т.е. $27\in M$. Так как $27\in M$, то по тому же пункту №2 имеем: $81\in M$. Короче говоря, построенное множество 3, 9, 27, 81 и так далее – это натуральные степени числа 3.

$$3^1=1; \; 3^2=9; \; 3^3=27; \; 3^4=81;\; \ldots$$

Итак, кажется, что искомое множество задано. И выглядит оно так: $\<3,9,27,81,\ldots \>$. Однако действительно ли условия №1 и №2 определяют только это множество?

Рассмотрим множество всех натуральных чисел, т.е. $N$. Число 3 – натуральное, посему $3\in N$. Вывод: множество $N$ удовлетворяет пункту №1. Далее, для любого натурального числа $x$ множество $N$ содержит также и число $3x$. Например, 5 и 15, 7 и 21, 13 и 39 и так далее. Значит, множество $N$ удовлетворяет условию №2. И, кстати сказать, не только множество $N$ удовлетворяет условиям №1 и №2. Например, множество всех нечётных натуральных чисел $N_1=\<1,3,5,7,9,11, \ldots\>$ тоже подходит под условия пунктов №1 и №2. Как же указать, что нам нужно именно множество $\<3,9,27,81,\ldots \>$?

Вот тут на помощь приходит пункт №3. Говоря огрублённо, он означает, что множество $M$ – наименьшее из всех возможных множеств. Так как множества $N$ и $\<3,9,27,81,\ldots \>$ удовлетворяют пунктам №1 и №2, но $N\nsubseteq \<3,9,27,81,\ldots \>$, то множество $N$ не удовлетворяет третьему пункту. Аналогично, так как $N_1\nsubseteq \<3,9,27,81,\ldots \>$, то множество $N_1$ также не удовлетворяет пункту №3. Можно показать (если это необходимо, отпишите мне на почту, я распишу подробнее), что всем трём пунктам удовлетворяет лишь множество $\<3,9,27,81,\ldots \>$, т.е.

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

Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).

Источник