Виленкин Рассказы о множествах. Рассказы о множествах 3е издание
 Скачать 9.06 Mb.
|
|
Брить или не брить? Брить или не брить? 13 Известны и другие примеры, когда множество, на первый взгляд вполне определенное, оказывается определенным очень плохо, а луч- ше сказать — совсем неопределенным. Например, пусть множество A состоит из всех рациональных чисел, которые можно определить при помощи не более чем двухсот русских слов (включая сюда и слова «нуль», «один», «два» и т. д.). Так как множество всех русских слов конечно (для простоты будем считать, что берутся лишь слова из словаря Ожегова и их грамматические формы), то и множество таких чисел конечно. Пусть это будут числа r 1 , r 2 , . . . , r N . Определим теперь рациональ- ное число r следующим образом: r = 0, n 1 n 2 . . . n N , где n i (i-й десятичный знак числа r) равен 1, если i-й десятич- ный знак числа r i отличен от единицы, в противном же слу- чае n i = 2. Число r не совпадает с r 1 , так как отличается от него первым десятичным знаком, не совпадает с r 2 , так как отличается от него вторым десятичным знаком, и т. д. Поэтому число r не входит в множество A. Между тем это число определено нами при помощи не более чем двухсот слов. С этим парадоксом тесно связан следующий: Каково то наименьшее целое число, которое нельзя определить при помощи фразы, имеющей менее ста русских слов? Такое число существует, поскольку число слов в русском языке конечно, а значит, есть числа, которые нельзя определить фразой, имеющей менее ста слов. Но тогда среди этих чисел есть наименьшее. С другой стороны, такого числа не существует, ибо оно опреде- ляется фразой из менее чем ста слов, напечатанной выше курсивом, а по смыслу этой фразы оно не может быть определено подобным образом. А вот более сложный пример конечного множества, относи- тельно которого оказывается невозможным сказать, содержит ли оно данный элемент. Разделим все прилагательные в русском язы- ке на два класса. К первому классу отнесем все прилагательные, для которых выражающее их слово само обладает свойством, опи- сываемым этим прилагательным, а ко второму — прилагательные, не обладающие описываемым им свойством. Например, прилагатель- ное «русское» отнесем к первому классу, так как слово «русское» принадлежит к словарному запасу русского языка. К тому же классу 14 Глава I. Множества и действия над ними отнесем и прилагательное «пятисложное», так как в слове «пяти- сложное» именно пять слогов. А прилагательное «немецкое» отнесем во второй класс, так как слово «немецкое» входит в словарный со- став русского, а не немецкого языка. Во второй класс попадет и слово «односложное», так как в этом слове не один, а пять слогов. Туда же попадет и слово «синее», так как это слово само цветом не обладает, а только выражает некоторый цвет. Казалось бы, все в полном порядке и каждое прилагательное на- шло свое место. Но для того, чтобы отличить полученные два класса друг от друга, введем еще два прилагательных. Назовем все при- лагательные первого класса «автологичными» (от греческих слов «авто» — сам и «логос» — смысл, закон), а прилагательные второго класса «гетерологичными» («гетерос» — другой). Слова «автологич- ный» и «гетерологичный» являются прилагательными, и их надо разместить по нашим классам. Слово «автологичный» можно от- править в первый класс, и тогда оно будет обладать именно тем свойством, которое само выражает, — ведь в первом классе собра- ны именно автологичные слова. Но и во втором классе оно будет смотреться неплохо (не обладая «гетерологичностью»). А вот сло- во «гетерологичный», напротив, относить некуда — оно доставляет те же трудности, что и взводный цирюльник. Его нельзя отнести в класс автологичных слов, так как тогда слово «гетерологичный» должно было бы само обладать свойством, выражаемым этим словом, а это свойство заключается в том, что ему надо быть не в первом, а во втором классе. Нельзя его отнести и во второй класс, так как тогда оно должно было бы не обладать выражаемым им свойством гетерологичности, а потому быть авто- логичным, второй же класс автологичных слов не содержит. В теории множеств накопилось много таких случаев, когда опре- деление множества было внутренне противоречивым. Изучение во- проса, при каких условиях это может иметь место, привело к глубо- ким исследованиям в области логики, совершенно изменившим лицо этой науки. Многие из этих исследований впоследствии были исполь- зованы для построения теории быстродействующих вычислительных машин, теории автоматов и т. д. Но эти исследования относятся уже к математической логике, и мы оставим их в стороне. Мы будем в дальнейшем рассматривать лишь множества, кото- рые определены точно и без противоречий и состав которых не вызы- вает сомнений (такие, как множество всех натуральных чисел, всех квадратов на плоскости и т. д.). Пустое множество 15 Пустое множество Само название «множество» наводит на мысль, что каждое мно- жество должно содержать много (по крайней мере два) элементов. Но это не так. В математике приходится рассматривать и множества, содержащие только один элемент, и даже множество, не имеющее ни одного элемента. Это множество называют пустым и обозна- чают ∅. Примерами пустых множеств могут служить множество лоша- дей, пасущихся на Луне, множество десятиногих млекопитающих, множество трехлетних гроссмейстеров, множество действительных корней уравнения x 4 + 16 = 0, множество решений системы урав- нений 2x − 5y = 1, 4x − 10y = 6. Зачем же вводят пустое множество? Во-первых, отметим, что когда множество задано своим характеристическим свойством, то не все- гда заранее известно, существует ли хоть один элемент с таким свойством. Например, пусть множество A состоит из всех четырех- угольников таких, что а) все их углы прямые, б) диагонали имеют различную длину. Для человека, не знающего геометрии, ничего противоречивого в этих требованиях нет. Однако из теоремы о равенстве диагоналей прямоугольника следует, что множество таких четырехугольников пусто. Пусто и множество треугольников, сумма углов которых от- лична от 180 ◦ . Множество квадратных трехчленов, имеющих более двух корней, тоже пусто. Вообще многие математические утвержде- ния можно сформулировать как утверждения о пустоте некоторого множества (попробуйте сформулировать так теорему Пифагора). Не решая уравнения x 4 − 7x 2 − 6x + 26 = 0, было бы трудно установить, пусто или нет множество его действительных корней. Впрочем, если переписать это уравнение в виде (x 2 − 4) 2 + (x − 3) 2 + 1 = 0, то станет ясно, что оно не имеет действительных корней. Иногда бывает трудно сказать, пусты ли те или иные множества нематематической природы. Если кто-нибудь плохо знает зоологию, 16 Глава I. Множества и действия над ними он не сможет ответить на вопрос, пусто ли множество акул, живущих в Байкале, или множество тигров, живущих на свободе в Австралии. Долго было неизвестно, пусто ли множество всех натуральных чисел n таких, что n > 2, а уравнение x n + y n = z n имеет поло- жительные целочисленные решения (в этом состояла знаменитая проблема Ферма). Лишь в 1995 г. Э. Уайлс установил, что это мно- жество пусто. До сих пор неизвестно, пусто ли множество цифр, входящих лишь конечное число раз в десятичное разложение чис- ла π (хотя это число и вычислено с точностью до многих тысяч десятичных знаков, неизвестно, все ли цифры входят в его деся- тичное разложение бесконечно много раз или какая-нибудь цифра встречается лишь конечное число раз). До сих пор не выяснено, пусто ли множество целых решений уравнения x 3 + y 3 + z 3 = 30 (при этом допускаются как положитель- ные, так и отрицательные целые решения; то, что множество ре- шений этого уравнения в натуральных числах пусто, совершенно очевидно). Неизвестно и то, пусто ли множество всех живых плезиозавров на земном шаре, — если чудовище озера Лох-Несс действительно окажется плезиозавром, то это множество не пусто. Теория множеств и школьная математика Множества могут состоять из самых различных элементов — рыб, домов, квадратов, чисел, точек и т. д. Именно этим объясняется чрез- вычайная широта теории множеств и ее приложимость к самым разным областям знания (математике, механике, физике, биологии, лингвистике и т. д.). Для математики особо важную роль играют множества, составленные из «математических» объектов — геомет- рических фигур, чисел, алгебраических выражений, функций и т. д. С некоторыми такими множествами имеют дело в школьной мате- матике, но там обычно избегают самого слова «множество» (за ис- ключением школ и классов с углублённым изучением математики). На самом же деле школьная математика имеет дело с множества- ми на каждом шагу. Особенно часто встречаются числовые множе- ства, то есть множества, составленные из чисел. Примерами таких множеств могут служить: а) множество всех натуральных чисел, б) множество всех целых чисел (положительных, отрицательных и нуля), Теория множеств и школьная математика 17 в) множество всех рациональных чисел, г) множество всех действительных чисел, д) множество всех комплексных чисел, е) множество площадей правильных многоугольников, вписан- ных в данный круг, и т. д. С каждым уравнением связаны два числовых множества. Пер- вым из них является множество чисел, при которых выражения, входящие в уравнение, имеют смысл. Это числовое множество на- зывается областью допустимых значений неизвестного. Например, для уравнения x x 2 − 4 + x − 1 x 2 − 9 = − 1 3 область допустимых значений состоит из всех чисел x, для кото- рых x 2 − 4 = 0 и x 2 − 9 = 0, то есть из всех чисел, кроме чисел мно- жества {2, −2, 3, −3}. А для уравнения −x 2 + x + 12 + x = 2 + √ 10 область допустимых значений состоит из чисел, для которых −x 2 + x + 12 0. Это неравенство выполняется, если −3 x 4. Вторым множеством, связанным с данными уравнением или неравенством, является множество его решений. Например, для уравнения x 2 − 7x + 12 = 0 множество корней состоит из двух чисел {3, 4}, а для уравнения sin πx = 0 — из бесчисленного множества чисел, а именно из всех целых чисел. Когда уравнение задано, мно- жество M его корней определено характеристическим свойством — тем, что числа x, входящие в M , удовлетворяют данному урав- нению. После того, как уравнение решено, множество M задано списком (если оно конечно) или более простым характеристическим свойством (если оно бесконечно), например, свойством, что все его элементы — целые числа. В то время как множество решений уравнения состоит обычно из нескольких чисел или (для большинства тригонометрических уравнений) из нескольких последовательностей чисел, множество решений неравенства, как правило, сплошь заполняет некоторые участки множества действительных чисел. Например, неравенство 4 − x 2 0 выполняется на отрезке −2 x 2, обозначаемом [−2; 2], а неравенство (4 − x 2 )(x − 3)(x − 5) 0 18 Глава I. Множества и действия над ними — на отрезках −2 x 2 и 3 x 5. Если вместо нестрогих взять строгие неравенства, то получатся отрезки с отброшенными конца- ми, так называемые числовые промежутки. Например, множество решений неравенства (4 − x 2 )(x − 3)(x − 5) > 0 состоит из промежутков −2 < x < 2 и 3 < x < 5, обозначаемых (−2; 2) и (3; 5). Концы −2, 2, 3, 5 этих промежутков не удовлетворяют нера- венству. Встречаются в качестве решений неравенства и более слож- ные множества. Например, решением неравенства x − 1 4 − x 0 является множество чисел x таких, что 1 x < 4, обозначаемое [1; 4). Здесь один конец отрезка (а именно 1) принадлежит множеству решений, а другой — число 4 — не принадлежит ему. Так как каждое действительное число изображается точкой на числовой оси, числовые множества можно изображать как неко- торые множества точек на прямой. Например, на рис. 3 а изображено множество чисел x таких, что −4 x 1, а на рис. 3 б изображено множество таких чисел x, что −2 < x < 3. а) б ) Рис. 3 Особенно удобно геометрическое изображение множеств, состо- ящих из пар или троек чисел. Например, уравнение x 2 + y 2 = 25 задает множество M пар чисел (x; y), при подстановке которых урав- Рис. 4 нение обращается в тождество. Пары чисел (−5; 0), (3; −4) принадлежат множеству M , так как (−5) 2 + 0 2 = 25, 3 2 + (−4) 2 = 25, а па- ра чисел (1; 6) не принадлежит множеству M , так как 1 2 + 6 2 = 37 = 25. Однако такое описа- ние множества M не очень наглядно. Чтобы описать это множество нагляднее, воспользу- емся методом координат. Выберем на плос- кости систему декартовых координат (это те самые координаты, которые изучаются в шко- ле). Тогда каждой паре чисел (x; y) соответ- ствует точка A на плоскости с координатами x и y, а каждой точке плоскости — пара x и y ее координат (рис. 4). Теория множеств и школьная математика 19 Если изобразить на плоскости все пары чисел (x; y), для которых x 2 + y 2 = 25, то легко заметить, что они ложатся на одну и ту же линию, а именно на окружность радиуса 5 с центром в начале коор- динат (рис. 5). Если вспомнить теорему Пифагора, то сразу станет ясно, что множество всех точек A(x; y), для которых x 2 + y 2 = 25, совпадает с множеством точек этой окружности (рис. 6). Рис. 5 Рис. 6 Неравенства, содержащие два неизвестных, обычно задают не линии, а целые области на плоскости. Например, неравенство x 2 + y 2 25 задает на плоскости множество точек, расстояние которых от начала координат не превосходит 5, то есть множе- ство точек круга радиуса 5 с центром в начале координат. При этом сама окружность входит в указанное множество. А неравен- ство x 2 + y 2 < 25 задает тот же круг, но без граничной окруж- ности. В геометрии мы сталкиваемся с двумя типами множеств. Во- первых, теоремы геометрии обычно говорят о свойствах некоторого множества геометрических фигур. Например, теорема о том, что диагонали параллелограмма делят друг друга пополам, касается множества всех параллелограммов. Во-вторых, сами геометриче- ские фигуры являются множествами, состоящими из входящих в них точек. Мы можем поэтому говорить о множестве всех точек данного круга, о множестве всех точек данного конуса и т. д. В алгебре мы встречаемся с такими множествами, как множество всех многочленов от двух переменных, множество всех квадратных уравнений, множество всех алгебраических уравнений и т. д. Одним словом, почти каждый раздел школьной математики так или иначе связан с теорией множеств. 20 Глава I. Множества и действия над ними Подмножества Введение понятия множества в математику оказалось очень по- лезным. Из-за того, что элементами множеств могут быть вещи са- мой различной природы, одни и те же утверждения, касающиеся множеств, можно истолковать и как утверждения о точках геомет- рических фигур, и как утверждения о натуральных числах, и как утверждения о животных или растениях, и как утверждения об ато- мах или молекулах. Понятия и теоремы теории множеств облада- ют очень большой общностью. Мы расскажем сейчас о некоторых из них. В первую очередь познакомимся с понятием подмножества. Оно возникает каждый раз, когда приходится рассматривать некоторое множество не самостоятельно, а как часть другого, более широкого множества. Именно, говорят, что множество B является подмноже- ством другого множества A, если каждый элемент x из B является вместе с тем и элементом множества A. В этом случае пишут B ⊂ A. Например, если взять какую-нибудь среднюю школу, то множе- ство учеников десятых классов этой школы является подмножеством Рис. 7 в множестве всех учеников данной школы. В свою очередь множество учеников этой шко- лы является подмножеством в множестве всех школьников. Множество всех лис является подмноже- ством в множестве всех хищных зверей, множе- ство хищных зверей — подмножеством в мно- жестве млекопитающих, а множество млекопи- тающих — подмножеством в множестве позвоночных. Если геомет- рическая фигура X является частью геометрической фигуры Y , то множество точек фигуры X есть подмножество множества точек фигуры Y (рис. 7). В геометрии также часто приходится иметь дело с подмножества- ми некоторых множеств геометрических фигур. Возьмем, например, следующие множества: множество A состоит из всех четырехуголь- ников; множество B состоит из всех трапеций; множество C состоит из всех параллелограммов; множество D состоит из всех прямоуголь- ников; множество E состоит из всех квадратов. В этом списке фи- гура каждого следующего типа является частным случаем фигуры предыдущего типа (трапеция — частный случай четырехугольника, Подмножества 21 параллелограмм — частный случай трапеции 1 и т. д.). Но это и озна- чает, что каждое следующее множество является подмножеством предыдущего: A ⊃ B ⊃ C ⊃ D ⊃ E. Точно так же в следующем списке каждое следующее множество является подмножеством предыдущего: множество всех комплекс- ных чисел; множество всех действительных чисел; множество всех рациональных чисел; множество всех целых чисел; множество всех натуральных чисел. Во многих случаях, чтобы выделить в данном множестве некоторое подмножество, добавляют к характеристиче- скому признаку множества то или иное дополнительное условие. На- пример, подмножество натуральных чисел выделяется в множестве целых чисел добавлением условия n > 0, а подмножество равносто- ронних треугольников в множестве всех треугольников — добавле- нием условия a = b = c. Мы уже говорили, что многие теоремы формулируются как теоремы о совпадении двух множеств. Наряду с ними встречают- ся и теоремы, в которых речь идет лишь о том, что одно множество является частью другого. Например, в теореме «Диагонали четырех- угольника с равными сторонами (ромба) взаимно перпендикулярны» речь идет о двух множествах: A — множество всех ромбов, B — множество всех четырехугольников с взаимно перпендикулярными диагоналями. И теорема состоит в том, что A ⊂ B. Если множество A является подмножеством множества B, A ⊂ B, то принадлежность множеству A является достаточным условием принадлежности к множеству B, а принадлежность к множе- ству B — необходимым условием принадлежности множеству A. Например, пусть B — множество всех четных положительных чисел, а A — множество натуральных чисел, последней цифрой которых является 4. Ясно, что A ⊂ B. Поэтому для того, чтобы целое число n было четным, достаточно, чтобы его последней цифрой было 4. С другой стороны, для того чтобы последней цифрой целого числа было 4, необходимо, чтобы это число было четным. В случае, когда множества A и B совпадают, принадлеж- ность к A необходима и достаточна для принадлежности к B. Иными словами, теоремы о том, что некоторое условие является 1 Хотя в некоторых курсах геометрии параллелограмм не считается трапе- цией. 22 Глава I. Множества и действия над ними необходимым и достаточным, — это теоремы о совпадении двух множеств. Так, для того чтобы целое число n делилось на 10, необходимо и достаточно, чтобы его последней цифрой был 0. Иными словами, множество A чисел, кратных 10, совпадает с множеством B целых чисел, последней цифрой которых является 0. Точно так же множество всех ромбов совпадает с множеством па- раллелограммов, имеющих взаимно перпендикулярные диагонали. Поэтому для того, чтобы параллелограмм был ромбом, необходи- мо и достаточно, чтобы его диагонали были взаимно перпендику- лярны. Теория множеств и комбинаторика Подсчитаем, сколько подмножеств имеет конечное множество (в число подмножеств мы включаем и пустое множество, и само множество). Множество, состоящее из одного элемента a, имеет два подмножества: ∅ и {a}. Множество, состоящее из двух элементов a и b, имеет уже четыре подмножества: те же подмножества ∅ и {a} и еще {b} и {a, b}. Если прибавить к множеству третий элемент c, то кроме уже найденных четырех подмножеств ∅, {a}, {b} и {a, b} появятся еще четыре подмножества: {c}, {a, c}, {b, c} и {a, b, c}, получаемые добавлением элемента c к каждому из имевшихся ранее подмножеств. Ясно, что каждый раз добавление нового элемента удваивает число подмножеств. Поэтому множество, содержащее n элементов, имеет 2 n подмножеств. Подмножества конечного множества можно расклассифициро- вать по числу входящих в них элементов. Если множество содер- жит n элементов, то его подмножества, состоящие из k элементов, называются сочетаниями из n по k. Их число обозначается C k n . Так как общее число подмножеств равно 2 n , то справедливо равенство C 0 n + C 1 n + . . . + C k n + . . . + C n n = 2 n Для чисел C k n существует немало любопытных соотношений, многие из которых удается вывести, рассматривая некоторые подмножества с определенными свойствами. Докажем, например, соотношение C k n = C k−1 n−1 + C k n−1 (1) в предположении 1 k < n. С этой целью среди всех сочетаний из n элементов a 1 , . . . , a n по k выберем сочетания, содержащие Теория множеств и комбинаторика 23 элемент a n . Остальные k − 1 мест в сочетании могут занимать любые из n − 1 элементов a 1 , . . . , a n−1 . Поэтому число выбран- ных сочетаний равно C k−1 n−1 . Теперь подсчитаем, сколько сочетаний из элементов a 1 , . . . , a n по k не содержат элемента a n . Эти соче- тания составлены из элементов a 1 , . . . , a n−1 . Так как в сочетание входят k элементов, то число таких сочетаний равно C k n−1 . Посколь- ку в каждое из C k n сочетаний либо входит, либо не входит элемент a n , то должно выполняться равенство (1). Отметим еще, что C 0 n = 1 при любом n 0, так как каждое множе- ство имеет лишь одно пустое подмножество. Точно так же очевидно, что C n n = 1. Пользуясь сделанными замечаниями, можно последовательно подсчитывать числа C k n сначала при n = 0, потом при n = 1, потом при n = 2 и т. д. Таблица чисел C k n записывается обычно в виде C 0 0 C 0 1 C 1 1 C 0 2 C 1 2 C 2 2 C 0 3 C 1 3 C 2 3 C 3 3 (так называемый треугольник Паскаля). Так как C 0 n = C n n = 1, то на сторонах треугольника Паскаля стоят единицы. А остальные числа последовательно вычисляем, учитывая, что в силу соотношения (1) каждое число равно сумме чисел, сто- ящих в предыдущей строке слева и справа от него. В результате получаем следующую таблицу: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Существует формула для непосредственного вычисления чи- сел C k n . Она имеет вид C k n = n! k!(n − k)! , 24 Глава I. Множества и действия над ними где k! = 1 · 2 · . . . · k и 0! = 1. Предоставляем читателю проверить, что определяемые этой формулой числа действительно удовлетворяют соотношению (1) и равенствам C 0 n = C n n = 1. Универсальное множество Крайне редко может встретиться случай, когда в одном и том же рассуждении пойдет речь и о множестве всех комплексных чисел и о множестве всех китов в океане (хотя, конечно, не исключено, что методы теории функций комплексного переменного будут при- лагаться к изучению движения кита в воде). Обычно все множества, с которыми имеют дело в том или ином рассуждении, являются под- множествами некоторого фиксированного множества I. Мы будем называть в этом случае множество I универсальным множеством. Например, все числовые множества являются подмножествами множества действительных чисел, множество точек любой геометри- ческой фигуры — подмножеством в множестве всех точек геометри- ческого пространства, множество сторон плоского многоугольника — подмножеством в множестве всех отрезков на плоскости и т. д. Пересечение множеств В сентябре 1887 года знаменитому сыщику Шерлоку Холмсу по- надобилось выяснить название одного парусного судна 1 . Он знал об этом корабле не слишком много: в январе или феврале 1883 го- да оно было в Пондишери, в январе 1885 года — в Данди, а сейчас стояло в Лондонском порту. Пользуясь этими данными, он все-таки установил название корабля. Для этого достаточно было сравнить три множества: множество парусников, бывших в указанное вре- мя в Пондишери, множество парусников, находившихся в январе 1885 года в Данди, и множество парусников, находившихся сейчас в Лондоне. Оказалось, что только одно судно входило во все три множества — американский корабль «Одинокая звезда». А так как Шерлок Холмс полагал к тому же, что преступники родом из Аме- рики, то круг замкнулся и преступление было раскрыто. Искать общие элементы множеств приходится не только сыщи- кам. Ученый-бактериолог, ищущий возбудителя болезни, наблюдает 1 Отсылаем читателя за подробностями к рассказу Конан Дойля «Пять апель- синовых зернышек». |