Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
Решения 39.1. Фиксируем в данном множестве один элемент x. Подмножества данного множества можно разбить на пары следующим образом берём произвольное подмножество, не содержащее ив качестве второго множества пары берём тоже самое подмножество и добавляем к нему элемент x. В каждой паре одно множество состоит из чётного числа элементов, а другое — из нечётного. 39.2. а) Если x ∈ A ∪ (B ∩ C), то x ∈ A или x ∈ B ∩ C. Если x ∈ то x ∈ A ∪ B и x ∈ A ∪ C, поэтому x ∈ (A ∪ B) ∩ (A ∪ C). Если же B ∩ C, то x ∈ B и x ∈ C, поэтому x ∈ A ∪ B и x ∈ A ∪ C, а значит (A ∪ B) ∩ (A ∪ Если x ∈ (A ∪ B) ∩ (A ∪ C), то x ∈ A ∪ B и x ∈ A ∪ C. Поэтому x ∈ или x ∈ B ∩ C. Значит, x ∈ A ∪ (B ∩ б) Если x ∈ A ∩ (B ∪ C), то x ∈ A и x ∈ B ∪ C. Поэтому x ∈ A ∩ или x ∈ A ∩ Если x ∈ (A ∩ B) ∪ (A ∩ C), то x ∈ A ∩ B или x ∈ A ∩ C. Поэтому A или x ∈ B ∪ C. 39.3. x ∈ A ∪ B ⇔ x 6∈ A ∪ B ⇔ x 6∈ A и x 6∈ B ⇔ x ∈ A ∩ B. x ∈ A ∩ B ⇔ x 6∈ A ∩ B ⇔ x 6∈ A или x 6∈ B ⇔ x ∈ A ∪ B. 39.4. Требуемые диаграммы изображены на рис. Рис. 39.1 Глава 39. Теория множеств. Взаимно однозначное отображение [0, 1] → [0, a] задаётся формулой x 7→ ax. 39.6. Взаимно однозначное отображение (0, 1) → (1, +∞) зада- ётся формулой x 7→ 1/x. 39.7. Функция f(x) = tg “ p x 2 ” задаёт взаимно однозначное отображение интервала (−1, 1) на множество всех действительных чисел. Сопоставим последовательности a 1 , a 2 , . . . множество, состоящее из тех натуральных чисел n, для которых a n = 1. В результате получим взаимно однозначное соответствие между последовательностями указанного вида и множествами натуральных чисел. Выберем бесконечную последовательность попарно различных чисел a 1 , a 2 , . . . , заключённых строго между 0 и 1. Построим отображение f : [0, 1] → [0, 1) следующим образом f(1) = a 1 , f(a i ) = и f(x) = x, если x отлично от 1 и от для всех i. Ясно, что отображение f взаимно однозначно. Действительно, обратное отображение f −1 : [0, 1) → [0, 1] устроено следующим образом 1, f −1 (a i ) = при i > 2 и f(x) = x, если x отлично от для всех i. 39.10. В последовательности 0, 1, −1, 2, −2, 3, −3, . . . каждое целое число встречается ровно один раз. Для каждого натурального k запишем последовательность. Запишем такие последовательности для k = 1, 2, 3, . . . После этого будем идти по полученной последовательности и вычёркивать все те числа, которые уже встретились нам ранее. В результате получим последовательность, в которой каждое рациональное число встречается ровно один раз. З а меча ни е. По поводу другого доказательства см. задачу. Занумеруем элементы данного счётного множества, и пусть элементы данного подмножества имеют номера i 1 < i 2 < < i 3 < . . . Множество этих номеров либо конечно (тогда данное подмножество конечно, либо бесконечно (тогда данное подмножество счётно). 39.13. Пусть е счётное множество состоит из элементов a k1 , a k2 , a k3 , . . . Тогда последовательность элементов a 11 ; a 12 , a 21 ; a 13 , a 22 , a 31 ; a 14 , a 23 , a 32 , a 41 ; . . . содержит все элементы данных множеств. Нужно только вычеркнуть из неё повторяющиеся элементы Решения задач. Множество упорядоченных пар натуральных чисел можно представить как объединение счётного множества счётных множеств (первое число пары можно рассматривать как номер множества. Значит, это множество счётно (задача 39.13). Занумеруем пары натуральных чисел. Тройку натуральных чисел можно рассматривать как пару натуральных чисел и ещё одно натуральное число. Поэтому множество троек натуральных чисел является объединением счётного множества счётных множеств и т. д. Непосредственно следует из задачи. Множество всех многочленов с целыми коэффициентами, имеющих данную степень n, счётно. Каждый из них имеет не более n различных корней, поэтому множество корней многочленов степени n с целыми коэффициентами счётно (многочлены вида показывают, что оно бесконечно. Поэтому множество алгебраических чисел является объединением счётного множества счётных множеств. Каждый из отрезков содержит рациональную точку, причём для непересекающихся отрезков эти точки разные. Каждый из кругов содержит точку, обе координаты которой рациональны, причём для непересекающихся кругов эти точки разные. Можно считать, что X и Y не пересекаются. Действительно, вместо Y можно взять множество Y ′ , состоящее из тех элементов Y, которые не принадлежат X. Множество является подмножеством Y, поэтому оно конечно или счётно. Пусть X 1 — счётное подмножество в X, а X 2 — дополнение кв. Множество X 1 ∪ Y равномощно X 1 , поскольку объединение счётного множества с конечным или счётным счётно. Установим взаимно однозначное соответствие множеств X 1 ∪ Y и X 1 . Вместе с естественным взаимно однозначным соответствием множеств X 2 и каждый элемент соответствует самому себе) оно даёт требуемое взаимно однозначное соответствие множеств X ∪ Y и X. 39.20. а) Это легко выводится из задачи б) Можно воспользоваться такими же рассуждениями, как и при решении задачи 39.9. 39.21. а) Достаточно доказать, что множество точек отрезка, 1] равномощно множеству всех бесконечных последовательностей, где a i = 0 или 1. Сопоставим такой последовательности число 2 + a 2 2 2 + a 3 2 3 + . . . Это представление числа из [0, неоднозначно. Например, двоичные дроби 0,01111 . . . и 0,1000 . . представляют одно и тоже число. Но если мы отбросим все дво- Глава 39. Теория множеств ичные дроби с единицей в периоде, кроме дроби 0,1111 . . . , то оставшиеся дроби будут находиться во взаимно однозначном соответствии с точками отрезка [0, 1]. Выброшенные дроби образуют счётное множество, поскольку каждая из них задаётся конечной последовательностью из нулей и единиц. Пусть X — множество оставшихся дробей, Y — множество выброшенных дробей. Тогда X имеет мощность континуума, поэтому согласно задаче 39.19 рассматриваемое множество X ∪Y тоже имеет мощность континуума. б) Следует из задачи аи задачи 39.8. 39.22. Точку квадрата можно представить как пару точек отрезка. Согласно задаче 39.21 множество точек отрезка равномощ- но множеству бесконечных последовательностей a 1 , a 2 , . . . , где 0 или 1. Поэтому достаточно доказать, что множество упорядоченных пар таких последовательностей равномощно множеству таких последовательностей. Сопоставим паре последовательностей, a 2 , a 3 , . . . и b 1 , b 2 , b 3 , . . . последовательность a 1 , b 1 , a 2 , b 2 , a 3 , b 3 , . . . В результате получим требуемое взаимно однозначное соответствие. Предположим, что удалось установить взаимно однозначное соответствие f : X → P(X). Пусть Y — множество тех элементов x ∈ X, для которых x 6∈ f (x). Докажем, что этому подмножеству не соответствует никакой элемент множества X. Действительно, предположим, что Y = f (y). Тогда Y ⇔ y 6∈ f (y) ⇔ y 6∈ Первая эквивалентность вытекает из определения множества а вторая — из того, что f (y) = Замечание. Обратите внимание, что если X = ∅, то множество состоит из одного элемента. Согласно задаче 39.21 б) множество P(X) всех подмножеств счётного множества X имеет мощность континуума. Согласно теореме Кантора P(X) не равномощно X, те. множество, имеющее мощность континуума не равномощно счётному множеству ДОПОЛНЕНИЕ. Рациональная параметризация окружности Чтобы найти все точки окружности x 2 + y 2 = 1, обе координаты которых рациональны, можно воспользоваться следующей конструкцией. Возьмём на окружности произвольную точку A с рациональными координатами и прове- дм через неё всевозможные прямые. Например, в качестве точки A можно взять точку (1, 0) или точку (3/5, Мы проведём вычисления для точки (1, 0), хотя для любой другой точки с рациональными координатами вычисления будут аналогичны. Прямая, проходящая через точку (1, 0), задаётся либо уравнением y = t(x − 1), либо уравнением x = 1 (уравнение 1 можно получить из уравнения y = t(x − 1), положив поэтому удобно считать, что t принимает также значение ∞). Чтобы найти точки пересечения прямой t(x − 1) и окружности x 2 + y 2 = 1, нужно решить квадратное уравнение x 2 + t 2 (x − 1) 2 = 1, те Одна точка пересечения прямой и окружности, соответствующая, известна. Поэтому координату x второй точки пересечения можно найти с помощью теоремы Виета. В результате получим 1 t 2 + 1 , y = t(x − 1) = − 2t t 2 + 1 540 Дополнение Таким образом, точка пересечения окружности x 2 + y 2 = и прямой y = t(x − 1) имеет координаты 1 t 2 + 1 , −2t t 2 + Это означает, что точка окружности имеет рациональные координаты тогда и только тогда, когда она соответствует рациональному значению параметра t. В самом деле, если число t рационально, то числа x = t 2 − 1 t 2 + и y = −2t t 2 + рациональны. А если числа x и y рациональны, то число t = y x − тоже рационально. Значение t = ∞, соответствующее точке, 0), удобно при этом тоже считать рациональным. С помощью рациональной параметризации окружности можно получить описание пифагоровых троек, те. таких троек натуральных чисел (a, b, c), что a 2 +b 2 =c 2 . А именно, b, c) — пифагорова тройка тогда и только тогда, когда существуют такие натуральные числа m и n, что a = m 2 −n 2 , b = 2mn, c = m 2 + или a = 2mn, b = m 2 − n 2 , c = m 2 + Доказательство этого утверждения начнём с того, что избавимся от общих делителей. Если два из трёх чисел a, b, делятся на d, то третье число тоже делится на d. Поэтому можно считать, что a/c и b/c — несократимые дроби. Точка, b/c) лежит на окружности x 2 + y 2 = 1 и обе координаты этой точки рациональны. Следовательно ± t 2 − 1 t 2 + 1 , b c = ± 2t t 2 + где t — рациональное число. Пусть t = m/n — несократимая дробь. Тогда ± m 2 − n 2 m 2 + n 2 , b c = ± 2mn m 2 + Дробь m/n несократимая, поэтому числа m и n не могут быть оба чётными. Если одно из этих чисел чётно, а другое нечётно, то дроби n 2 m 2 + и+ несократимые. Если же 1. Рациональная параметризация окружности 541 оба числа m и n нечётны, те и n = 2q + 1, то, как легко проверить ± 2m 1 n 1 m 2 1 + n 2 1 , b c = ± m 2 1 − n 2 1 m 2 1 + n 2 где m 1 =p+q+1 и n 1 =p−q. Мы получаем несократимые дроби, так как одно из чисел и n 1 чётно, а другое нечётно. Как мы уже говорили, взяв любую другую рациональную точку окружности, можно повторить аналогичные вычисления и получить аналогичную параметризацию окружности параметром t, причём рациональным значениям параметра будут соответствовать рациональные точки окружности. Более того, аналогичным образом можно параметризовать произвольную кривую второго порядка+ bxy + cy 2 + dx + ey + f = Для этого нужно взять произвольную точку кривой и провести через неё всевозможные прямые. Предположим, что выполняются следующие условия коэффициенты a, b, . . . , f рациональны выбранная точка кривой имеет рациональные координаты кривая (1) содержит бесконечно много точек. Тогда в результате получим такую параметризацию кривой, что рациональным значениям параметра t соответствуют точки кривой, обе координаты которых рациональны. Напомним, что мы пользовались тем, что кривая (содержит хотя бы одну точку с рациональными координатами. Но такая точка есть не всегда. Самый простой пример — кривая x 2 + y 2 = Более интересен пример кривой 2x 2 + 5y 2 = 1. Проверим, что на ней нет рациональных точек. Предположим, что, y) — рациональная точка этой кривой. Можно считать, что x = p 1 /q и y = p 2 /q, причём у чисел p 1 , p 2 , q нет общего делителя тенет числа d, на которое делятся все эти три числа 542 Дополнение Числа p 1 , p 2 , q удовлетворяют соотношению 2p 2 1 + 5p 2 2 = = q 2 . Поэтому числа 2p 2 и при делении надают одинаковые остатки. Но число при делении на 5 может давать лишь остатки ±1 и 0. Поэтому число 2p 2 при делении на дат остаток ±2 или 0, а число дат остаток ±1 или Следовательно, оба числа 2p 2 и делятся на 5, а значит, они делятся на 25. Но тогда число 5p 2 делится на 25, а значит, число делится на 5. В результате получаем, что числа p 1 , p 2 , q делятся на 5, а это противоречит предполо- жению. Рациональная параметризация кривой второго порядка, отличной от окружности, применяется, например, при решении следующей задачи: описать все кубические многочлены, у которых корни как самих многочленов, таки их производных, рациональны. Мы ограничимся случаем, когда один из корней равен 0 и старший коэффициент равен 1 (общий случай легко сводится к этому случаю). В этом случае P(x) = x(x + a)(x − b), где a и b — рациональные числа, и P ′ (x) = 3x 2 + 2(a − b)x − ab. Требуется, чтобы дискриминант D = 4((a −b) 2 + 3ab) = 4(a 2 + b 2 + ab) был квадратом рационального числа. Эквивалентное условие таково+ b 2 + ab = c 2 , где c — рациональное число. Положим x = a/c и y = b/c. Нас интересуют точки с рациональными координатами на кривой x 2 + y 2 + xy = 1. Одна такая точка очевидна x = 1 и y = 0. Проведём через неё всевозможные прямые y = t(x − 1). Подставим это выражение для y в уравнение кривой+ t 2 (x 2 − 2x + 1) + tx(x − 1) − 1 = те У этого квадратного уравнения есть корень x = 1. Нас интересует второй корень x = t 2 − 1 1 + t + t 2 . При этом y = t(x − 1) = = − t 2 + 2t 1 + t + t 2 . Итак, общее решение этой задачи выглядит 2. Суммы квадратов многочленов 543 следующим образом. Пусть c и t — произвольные рациональные числа. Тогда a = c t 2 − 1 1 + t + и b = −c t 2 + 2t 1 + t + t 2 . Отметим, что если мы возьмём a = t 2 − 1 и b = −(t 2 + где t — целое число, то получим кубический многочлену которого корни как самого многочлена, таки корни его производной, — целые числа. Суммы квадратов многочленов Нетрудно доказать, что любой многочлен p(x) с действительными коэффициентами, принимающий неотрицательные значения при всех действительных x, можно представить в виде суммы квадратов двух многочленов с действительными коэффициентами. Прежде всего заметим, что если p(z)=0 и p — многочлен с действительными коэффициентами, тот. е. z — тоже корень многочлена Поэтому корни многочлена с действительными коэффициентами разбиваются на действительные корни и пары комплексных корней. Следовательно a s Y j=1 (x − z j )(x − где числа a k действительные. Предположим теперь, что p(x) > 0 при всех действительных. Если x — достаточно большое положительное число, то z j )(x − поэтому a > 0. Кроме того, все числа m k чётны. В самом деле, пусть некоторые из чисел m k нечётны. Можно считать, что нечётны лишь числа m 1 , . . ., и при этом a 1 < . . . Тогда при a s −1 < x выполняется неравенство Дополнение те. (Если s = 1, то это неравенство выполняется при всех x Таким образом, действительные корни тоже разбиваются на пары. Следовательно z j ) √ a l Y j=1 (x − где некоторые из чисел могут быть действительными. Пусть √ a l Y j=1 (x − z j ) = q(x) + где q и r — многочлены с действительными коэффициентами. Тогда z j ) = q(x) − В итоге получаем p(x) = (q(x)) 2 + Но для многочленов от нескольких переменных аналогичное утверждение уже не всегда верно, те. существуют многочлены (так мы будем называть многочлены с действительными коэффициентами, которые при всех действительных значениях переменных принимают неотрицательные значения, которые нельзя представить в виде суммы квадратов многочленов с действительными коэффициентами. Первым это доказал немецкий математик Давид Гильберт в 1888 г, но он не привёл явный пример такого многочлена. Первый простой пример привёл Т. Моцкин в 1967 г. А именно, он показал, что многочлен, y) = x 2 y 2 (x 2 + y 2 − 3) + неотрицателен, но его нельзя представить в виде суммы квадратов многочленов с действительными коэффициентами. Основная трудность заключалась, конечно, в том, чтобы 2. Суммы квадратов многочленов 545 найти этот многочлена само доказательство его свойств, как мы сейчас увидим, несложно. Неотрицательность многочлена F следует из того, что, y) = (1 − x 2 y 2 ) 2 + x 2 (1 − y 2 ) 2 + x 2 (1 − x 2 ) 2 y 2 1 + Предположим теперь, что F(x, y) = P f j (x, y) 2 , где многочлены с действительными коэффициентами. Тогда, 0) 2 = F(x, 0) = 1. Если хотя бы один из многочленов) от переменной x отличен от константы, то f j (x, 0) 2 — многочлен, степень которого в два раза больше наибольшей из степеней многочленов f j (x, 0). Следовательно некоторая константа, а значит, y) = c j + yg j (x, y). Аналогичные рассуждения показывают, что f j (x, y) =c ′ j +xg ′ j (x, y). Ясно, что и f j (x, y) =c j + + xyh j (x, y), причём deg h j = deg f j − 2 6 1 2 deg F − 2 = здесь deg f — степень многочлена f. Таким образом+ y 2 − 3) + 1 = x 2 y 2 X h 2 j + те Все одночлены, встречающиеся в правой части этого равенства, имеют степень не больше 3, а все одночлены, встречающиеся в левой части этого равенства, имеют степень не меньше 4. Следовательно, x 2 y 2 (x 2 y 2 − 3) − x 2 y 2 P h 2 j = а значит, x 2 + y 2 −3 = P h 2 j . Получено противоречие, так как+ y 2 − 3 < 0 при x = y = Мы обсудили здесь лишь наиболее простые из известных фактов о суммах квадратов. Сейчас на эту тему известно весьма многое, но многие вопросы остаются пока без ответа. Гильберт высказал предположение, что любой Дополнение неотрицательный многочлен от многих переменных можно представить в виде суммы квадратов не многочленов, а рациональных функций. Вопрос о том, верно это или нет, он включил под номером 17 в свой знаменитый список проблем. Семнадцатая проблема Гильберта была решена в 1927 г. Э. Артином. Он доказал, что любой неотрицательный многочлен можно представить в виде суммы квадратов некоторого количества рациональных функций. В 1967 г. А. Пфистер уточнил теорему Артина; он доказал, что любой неотрицательный многочлен от n переменных можно представить в виде суммы квадратов рациональных функций. Но до сих пор неизвестно, можно ли заменить на меньшее число. Лишь при n = 2 известно, что число 2 n = в данном случае минимально. А именно, в 1971 г. Касселс, Эллисон и Пфистер показали, что тот самый многочлен, y), который мы рассмотрели выше, нельзя представить в виде суммы квадратов трёх рациональных функций. Их доказательство весьма сложно оно опирается на глубокие результаты из теории эллиптических кривых. Представление чисел в виде суммы двух квадратов В одном из своих писем Пьер Ферма в 1658 г. сообщал, что он получил неопровержимые доказательства того, что любое простое число вида 4k+1 является суммой двух квадратов, а любое число является суммой не более чем четырёх квадратов. Никаких записей этих доказательств Ферма не оставил. Прошло почти сто лети этими теоремами заинтересовался Леонард Эйлер. Первую из них он доказал в 1747 га через два года он нашёл другое изящное и сравнительно простое доказательство той же теоремы. Вторая теорема была доказана лишь в 1770 г. Лагранжем, после чего Эйлер сумел значительно упростить его доказательство. В дальнейшем были найдены другие интересные доказательства теоремы о представлении простых чисел p = 4k + в виде суммы двух квадратов некоторые из них приведе- 3. Представление чисел в виде суммы двух квадратов 547 ны в решениях задачи а. Но все они, как и доказательство Эйлера, былине вполне элементарны. И лишь совсем недавно было получено очень изящное и вполне элементарное доказательство этой теоремы. Центральное место в этом доказательстве занимает простое, но важное понятие инволюции. Пусть M — некоторое множество. Отображение s : M → M называют инволюцией, если s ( s (m)) = m для любого элемента m множества Примером инволюции служит любая симметрия. Инволюция позволяет разбить точки (элементы множества M) на пары {m, s (m)} симметричных точек. Для элемента получается та же самая пара, что и для элемента m, так как s ( s (m)) = m. Пара элементов не возникает лишь в том случае, когда s (m) = m такие точки m называют неподвижными. Поэтому если наконечном множестве M задана инволюция, то чётность количества элементов M совпадает сч тностью количества неподвижных точек инволюции (остальные элементы разбиваются на пары, поэтому их количество чётно). Общая схема доказательства такова. Рассмотрим множество всех решений уравнения x 2 + 4yz = p в натуральных числах. Достаточно доказать, что если p = 4k + 1, то у этого уравнения есть решение, для которого y = z. В самом деле, тогда p = x 2 + (2y) 2 . Решение, для которого y = z, — это неподвижная точка инволюции s (x, y, z) = (x, z, y). Поэтому достаточно доказать, что общее количество решений нечётно. Для этого строится совсем другая инволюция имеющая ровно одну неподвижную точку. Вот эта инволюция если x < y − z; (1) t (x, y, z) = (2y − x, y, x − y + z), если y − z < x < 2y; (2) (x − 2y, x − y + z, если 2y < x. (3) * D. Z a g i e r. A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares // Amer. Math. Monthly. 1990. V. 97. P. 114. 548 Дополнение Отметим сначала, что x 6= 2y итак как иначе x 2 + 4yz = 4(y 2 + yz) или p = (y − z) 2 + 4yz = (y + Проверим, далее, что любое решение уравнения x 2 + 4yz = инволюция действительно переводит в решение. Это следует из тождеств+ 2z) 2 + 4z(y − x − z) = x 2 + 4yz, (x − 2y) 2 + 4y(x − y + z) = x 2 + Пусть t (x, y, z) = (x ′ , y ′ , z ′ ). Если x < y − z, тот. е. точка типа (1) переходит в точку типа (Аналогично проверяется, что точка типа (3) переходит в точку типа (1), а точка типа (2) — в точку типа (2). После этого уже легко проверить, что t — инволюция. Точка типа (1) не может быть неподвижной, так как x + 2z > x; для точки типа (3) x ′ = x − 2y < x. Поэтому неподвижной может быть лишь точка типа (2), причём для неё должно выполняться соотношение z = z ′ = x − y + те. В таком случае p = x 2 + 4yz = x(x + 4z), а значит (здесь мы используем простоту числа p). Если 4k + 1, то (1, 1, k) — неподвижная точка (здесь мы используем то, что число p имеет вид 4k + 1). Доказательство завершено. Сделаем ещё некоторые замечания по поводу представления чисел в виде суммы двух квадратов. Прежде всего отметим, что простое число вида 4k + 3 нельзя представить в виде суммы двух квадратов. В самом деле, квадрат числа равен 4(m 2 + m) + 1, поэтому остаток отделения его на 4 равен 1. Следовательно, остаток отделения суммы двух квадратов на 4 равен 0, 1 или 2, но никак не Условие простоты числа p = 4k + 1 тоже существенно. Например, число 21 нельзя представить в виде суммы двух квадратов. Отметим также, что если m = a 2 + и n = c 2 + d 2 , то (ac + bd) 2 + (ad − bc) 2 — тоже сумма двух квадратов. Поэтому произведение простых чисел вида 4k + 1 можно 4. Построение правильного 17-угольника 549 представить в виде суммы двух квадратов. Если же в ка- кое-то натуральное число простой множитель вида 4k + входит в нечётной степени, то это число нельзя представить в виде суммы двух квадратов. Это следует из того, что если+ делится на простое число p = 4k + 3, то оба числа a и делятся на p задача 31.2). |