WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
— математические кружки для школьников при механиБиблиотека МАЛЫЙ ко-математическом факультете МГУ. Занятия проходят «Математическое просвещение» по субботам в главном здании МГУ на Воробьёвых гоМЕХМАТ рах для учащихся 6—8 классов с 1600 до 1800, для учащихся 9—11 классов с 1800 до 2000. С вопросами обращайтесь по адресу электронной почты mmmf@mmmf.mccme.ru или по телефону 939 39 43.

ПРИГЛАШАЮТСЯ ВСЕ ЖЕЛАЮЩИЕ! Каждую субботу сотни школьников стекаются в главное здаИ. В. Ященко ние МГУ на Воробьёвых горах на занятия Малого мехмата. Здесь школьники учатся решать задачи и математически строго излагать найденные решения. Каждый школьник получает в начале занятия листок ПАРАДОКСЫ ТЕОРИИ МНОЖЕСТВ с задачами, которые, как правило, объединены одной темой. Свои решения школьники рассказывают преподавателям — студентам и аспирантам «большого» мехмата.

Основные принципы кружков:

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

Участие в кружке не даёт никаких льгот при поступлении в вузы и других формальных преимуществ.

Поэтому сюда приходят только те, кому интересен сам процесс решения задач, кто действительно хочет почувствовать красоту математики.

А это, по большому счёту, оказывается значительно существеннее всевозможных льгот.

ISBN 5 94057 003 8 Издательство Московского центра непрерывного математического образования 9 785940 570035 Москва • 2002 M Y K Фото М. Ю. Панова.

Библиотека «Математическое просвещение» Выпуск 20 И. В. Ященко Научно- редакционный совет серии:

В. В. Прасолов, А. Б. Сосинский, В. М. Тихомиров (гл. ред.), И. В. Ященко.

ПАРАДОКСЫ ТЕОРИИ МНОЖЕСТВ Серия основана в 1999 году.

Издательство Московского центра непрерывного математического образования • Москва 2002 УДК 510.2 ЧТО ТАКОЕ МНОЖЕСТВО ББК 22.12 Когда мы собираемся что-то изучать, возникает потребность Яочертить круг объектов, с которыми мы будем работать: например, Аннотация «Возьмём всех учеников 9-го класса…», «Рассмотрим все вершины треугольника…», «Рассмотрим все буквы русского алфавита…».

При развитии теории множеств, на которой б азируется вся современная математика, возникали парадоксы. Например, параСобственно, именно это множеством и называется: множество — докс брадобрея, формулируемый следующим образом:

это коллекция (совокупность) объектов, определённая некоторым Бреет ли себя брадобрей, если он бреет тех правилом1. Можно представлять итолькотех, кто сам себя не бреет Хотя на самом деле никто толком и себе множества коробками, в коне знает, что такое множество.

В брошюре рассказывается о том, как теория множеств обхоторых лежат элементы.

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

В приложении 3 приведены задачи, самостоятельное решение МНОЖЕСТВО.

которых поможет читателю более полно разобраться в материале брошюры.

Что из себя представляет множество букв этого слова Наверняка вы Текст брошюры представляет собой обработанные записи лекуже знаете, что множество записывают так: в фигурных скобках — ций, прочитанных автором 8 апреля 2000 года на Малом мехмате список элементов, из которых это множество состоит. Итак, пишем:

для школьников 9—11 классов (запись Е. Н. Осьмовой) и в июле 2001 года в рамках летней школы «Современная математика» {М, Н, О, Ж, Е, С, Т, В}.

для школьников 10—11 классов и студентов 1—2 курса (запись Ю. Л. Притыкина).

Вот и возникла первая проблема: в русском алфавите одна буква Брошюра рассчитана на широкий круг читателей, интересуО, а в слове МНОЖЕСТВО две. Почему вторую букву О писать не надо, ющихся математикой: школьников старших классов, студентов можно объяснить, произнеся такое заклинание:

младших курсов, учителей.

множество определяется своими элементами, т. е. каждый элемент в множестве встречается только один раз. ТеИздание осуществлено при поддержке перь можно сказать, что вторая буква О не нужна, поскольку буква О Московской городской Думы и Московского комитета образования.

в нашем множестве уже есть.

Но что делать, если нам всё-таки нужны две буквы О Например, ISBN 5-94057-003-8 © Ященко И. В., 2002.

мы играем в такую игру: составляем слова из букв слова МНОЖЕ© МЦНМО, 2002.

СТВО. Понятно, что если букву О можно использовать два раза, то мы составим больше слов. Значит, надо как-то различать эти две буквы О, например, назвать их О1 иО2. Тогда множество букв в слове Ященко Иван Валериевич.

МНОЖЕСТВО будет выглядеть так:

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

{М, Н, О1, Ж, Е, С, Т, В, О2}.

(Серия: «Библиотека „Математическое просвещение“»).

Теперь с точки зрения русского языка всё в порядке: букв О две, и мы М.: МЦНМО, 2002. —40с.: ил.

можем спокойно составлять слова с двумя буквами О. С точки зреРедактор Ю. Л. Притыкин. Техн. редактор М. Ю. Панов.

ния теории множеств тоже всё хорошо: двух одинаковых элементов в одном множестве нет.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 7/X 2002 года.

Итак, эту проблему мы решили.

Формат бумаги 60 88 /. Офсетнаяб умага №1. Офсетнаяпечать. Физ. печ. л. 2,50.

Вторая, более серьёзная проблема возникает из-за того, что нам Усл. печ. л. 2,44. Уч.-изд. л. 2,31. Тираж 3000 экз. Заказ 3424.

хочется рассматривать большие и непонятно как определённые мноИздательство Московского центра непрерывного математического образования.



жества, вроде множества всех людей или множества всех деревьев, и 121002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

в фигурных скобках не выписывать, например, список всех учеников школы, а просто писать Отпечатано в ФГУП «Производственно-издательский комбинат ВИНИТИ».

140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86. {все ученики школы}.

Но прежде чем рассказать об этой проблеме, обсудим одно замеча- приказал ему брить тех и только тех, кто не бреется сам5. Брадобрей, тельное множество. получив приказ, сначала обрадовался, потому что многие солдаты умели бриться сами, побрил Приказ довольно разумный: если солтех, кто бриться сам не умел, а ПУСТОЕ МНОЖЕСТВО дат бреется сам, то зачем тратить на непотом сел на пенёк и задумалго время полковому парикмахеру Наверся: а что ему с собой-то делать Что значит, что множество A является подмножеством множеное, полк был большой, и брадобрей проВедь если он будет брить себя, ства B Это значит, что все элементы множества A принадлежат и сто не справлялся.

то нарушит приказ командира множеству B. Если представлять себе множества в виде коробок, то не брить тех, кто бреется сам. Брадобрей уже решил было, что брить множество B — это большая коробка, а множество A — коробка посебя не будет. Но тут его осенила мысль, что если он сам себя брить меньше, в которой лежат некоторые из элементов, лежащих в коробке не будет, то окажется, что он сам не бреется, и по приказу командира B. Обозначение: A B.

он должет всё-таки себя побрить… Например, множество всех чётных чисел является подмножеЧто с ним стало, история умалчивает.

ством множества всех целых чисел, а множество {0, 1, 2} — подмноПричём же здесь теория множеств А вот причём: командир пыжеством множества {0, 1, 2, 3}.

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

таким образом:

{все летающие крокодилы} и {все участники олимпиады}.

{те и только те, кто не бреется сам}.

Является ли одно из них подмножеством другого Казалось бы, обычное множество, описывается несколькими русскиКак вообще доказать, что A B Можно проверить, что любой ми словами, чем оно хуже, например, множества элемент a множества A лежит в B. А можно применить метод от противного2: еслиA не является подмноже{все ученики школы} Противного, мерзкого, ством B,тонайдётсяэлементa A,такойчто Но с этим множеством тут же возникает проблема: непонятно, пригадкого… a / B, а если такого a нет, то A B.

надлежит ли этому множеству брадобрей.

Но можно ли найти летающего крокодила, не участвующего в Вот другая версия этого парадокса.

олимпиаде Да где вообще найдёшь летающего крокодила… Поэтому Прилагательное русского языка назовём рефлексивным,еслионо {все летающие крокодилы} {все участники олимпиады}3.

обладает свойством, которое определяет. Например, прилагательное «русский» — рефлексивное, а прилагательное «английский» — Множество летающих кроЧто же получается: все летающие кро- нерефлексивное, прилагательное «трёхсложный» — рефлексивное кодилов — это пустое множекодилы участвуют в олимпиаде (это слово состоит из трёх слогов), а прилагательное «четырёхсложство: в нём нет элементов. Это ный» — нерефлексивное (состоит из пяти множество настолько важное, А программисты стащили этот симИнтересно, а прилагатель- слогов)6. Вроде бы ничто не мешает нам вол и используют для обозначения нуля. что для него даже придумали ное «трудновыговариваемое» определить множество особый символ:. Символдля является рефлексивным пустого множества только один, потому что пустое множество един{все рефлексивные прилагательные}.

ственно. В самом деле, предположим, что существуют два разных Но давайте рассмотрим прилагательное «нерефлексивный». Оно репустых множества. Но что значит, что множества разные Это знафлексивное или нет чит, что в одном из них найдётся элемент, который не принадлежит Можно заявить, что прилагательное «нерефлексивный» не являдругому. Но в пустых множествах вообще элементов нет! ется ни рефлексивным, ни нерефлексивным. Но как тогда быть с таИтак, мы доказали, что пустое множество единственно и являетким заклинанием:

ся подмножеством любого другого множества.

верно либо утверждение, либо его отрицание (Это заклинание называется законом исключённого третьего; на нём, ПАРАДОКС БРАДОБРЕЯ собственно, и основан метод от противного.) Наконец, третья версия парадокса. Рассмотрим множество Это довольно известная история, и у неё есть много версий.

M={множества A, такие чтоA / A} В одном полку жил-был полковой парикмахер, которого по историческим причинам называют брадобреем. Однажды командир —мы включаем во множество M только те множества A, которые 4 принадлежат сами себе. Бывают же множества, которые содержат 1. Аксиома объёмности. Мно- 1. z (z x z y) другие множества. Например, пусть жество определяется своими элементами: x=y.

множества, состоящие из одних и тех же A={1, 2, 3}, B={{1, 2}, 3}, элементов, равны.

множеству A принадлежат числа 1, 2, 3, а множеству B — два элемен2. Аксиома объединения. Объ- 2. Set{z: y x (z y)}.

та: множество {1, 2} и число 3. Возвращаясь к коробкам, это можно единение всех элементов множества есть сказать так: одни коробки можно класть в другие коробки. (Оказымножество.

вается, что в каждой такой последовательности вложенных коробок всегда конечное число элементов — этому есть глубокие причины.) 3. А к с и о м а в ы д е л е н и я. Для 3. x (f(x) x y) Рассмотренное множество M — это своего рода «брадобрей». Ескаждого множества A и каждого усло- Set{x: f(x)}.





ли предположить, что M M, сразу приходим к выводу, что M / M.

вия f существует множество Если же предположить, что M / M —получаем, чтоM M.

B={x: x A, f(x)} — подмножество элементов множества A, Столкнувшись с этими парадоксами, создатели теории множеств удовлетворяющих условию f.

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

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

ведущие к парадоксам. Идея в следующем: разрешается работать со множествами, которые «встречаются в природе», также разрешает- 4. А к с и о м а с т е п е н и. Множест- 4. Set{y: y x}.

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

A={множество учащихся школы}, 5. Аксиома подстановки. 5. y ! z f(y, z) B={множество непрерывных функций} Пусть X —множество, а f(y, z) —про- Set{z: y x f(y, z)}.

извольная формула. Тогда если для каж(эти множества «встречаются в природе»), из них можно получить дого y существует и единственен z, такой объединение A B, пересечение A B. Можно даже умножить множечто истинно f(y, z), то существует множество A на множество B: по определению ство всех z, для которых найдётся y X, A B={(a, b): a A, b B} такой что f(y, z) истинно.

— множество пар, в которых первый элемент из первого множества, 6. А к с и о м а ф у н д и р о в а н и я. 6. y (y x) а второй — из второго. В нашем случае A B — это множество пар, Не существует бесконечной последова- y x z y (z / x).

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

цепочка множеств Другой способ— аксиоматический. Этот способпреодоления парадоксов развивали Цермело и Френкель (система аксиом Цермело— A1 A2 A3 … Френкеля), Гёдель и Бернайс (система аксиома Гёделя—Бернайса).

конечна.

Согласно этой теории, множество — это нечто, удовлетворяющее ак7. А к с и о м а бе с к о н е ч н о с т и. 7. x (( y x z (z / y)) сиомам, например, следующим*).

Существуют бесконечные множества, y x z x (w z т. е. такие множества A, чтоA равномощ- w y w=y)).

*) Справа приведены записи аксиом на «языке кванторов». Вот значения испольно A {A}.

зованных кванторов: x — для любого x; x — существует x; ! x — существует единственный x; Set{…} — {…} является множеством; {x: f(x)} — множество тех и толь8. А к с и о м а в ы бо р а. Ещё одна очень сложная, но и очень ко тех x, которые удовлетворяют условию f(x); — логическое «или»; —логическое «и». Подробнее об аксиоматике теории множеств см. книгу [4]. очевидная аксиома — о ней позже.

6 РАВНОМОЩНОСТЬ МНОЖЕСТВ Обозначим через P(A) множество всех подмножеств множества A.

Примеры P(A) для некоторых множеств A приведены в табл. 1. (EстеРассмотрим два множества A и B.

ственно, подмножествами множества A являются и пустое множестОтображение f из A в B (обозначается f: A B) —этоправило, ко во, и само множество A.) торое каждому элементу множества A ставит в соответствие элемент Подмножества множества A={1, 2, 3} не будем выписывать в множества B, причём ровно один. (При этом не запрещается двум строчку (так недолго запутаться), а перечислим при помощи табэлементам множества A ставить в соответствие один и тот же элемент лицы: если элемент i входит в подмножество с номером j, то на множества B, рис. 1, а.) пересечении i-й строки и j-го столбца ставится плюс, если не входит — минус (табл. 2). Например, первый столбец, в котором стоит f f A A B B три плюса, соответствует подмножеству {1, 2, 3}.

Если составить такую же таблицу для множества из n элементов, каждое подмножество будет определяться столбцом из n символов (по числу элементов), и каждый символ можно выбрать двумя спосоа) б) б ами—либ о «+», либ о « ». Поэтому всего получится 2n различных Рис. столбцов. Итак, если в множестве A содержится n элементов, то в множестве P(A) содержится 2n элементов — существенно больше, чем в Отображение f называется взаимно однозначным, есликаждый множестве A.

элемент множества B поставлен в соответствие ровно одному элементу Но если подмножества конечного множества мы можем просто множества A (рис. 1, б).

сосчитать, то как же быть с бесконечными Например, подмножеств Множества A и B называются равномощными, если существумножества натуральных чисел бесконечно много, и самих натуральет взаимно однозначное отображение f: A B. Понимать это мож ных чисел бесконечно много. Оказывается, но так: множества равномощны, если в них одинаковое количество Вообще, всё, что можчто в множестве P(N) «бесконечно больше» элементов.

но доказать, можно доэлементов, чем в множестве N.

Например, множества {0, 1, 2} и {лошадь, корова, телевизор} рав- казать от противного.

Поэтому на всякий слуномощны, а множества {0, 1, 2} и {лошадь, корова} неравномощны7.

Теорема. Каково бы ни было множество чай будем доказывать А равномощны ли множества и {} НеA, множество его подмножеств P(A) неравот противного.

Телевизор был по делу… равномощны: в множестве нет ни одного номощно самому множеству A.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.