Натуральные числа: введение

Краткое содержание

Этот урок открывает раздел, посвящённый натуральным числам. Он представляет десять уроков раздела и дедуктивную нить, которая их связывает, от языка множеств и аксиом Пеано до бинома Ньютона; прослеживает историю этих идей, от доисторического счёта и арифметики Евклида до аксиоматизации Дедекинда и Пеано в конце XIX века; точно формулирует задачу, из которой они родились, а именно доказать утверждение о бесконечном множестве чисел, не перебирая их по одному; и указывает, где они снова используются в этом курсе, в других курсах сайта, в науке и технике.

Цели обучения

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

Входная проверка

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

Содержание раздела

В учебном плане отмечалось, что курс строит свои объекты, а не предполагает их известными. Этот первый раздел служит фундаментом этой постройки: он исходит из немногих аксиом о числах, которыми мы считаем, и выводит из них всю арифметику натуральных чисел. То немногое, что он принимает сверх этого, явно оговаривается в своём месте: правила наивной теории множеств и отрицания кванторов; существование функций, определённых по рекурсии, которое гарантирует теорема Дедекинда о рекурсии; единственность числа элементов конечного множества и конечность его подмножеств, на которых основан счёт; обобщённая коммутативность конечных произведений; и элементарные правила целых, рациональных и действительных чисел, которые некоторые примеры и задачи используют заранее и которые строит следующий раздел. Его десять уроков образуют цепь, в которой каждое звено опирается на предыдущие.

Множества, отношения и функции. Закрепляет язык, на котором написан весь курс: множества и операции над ними, отношения, в частности отношения эквивалентности и порядка, и функции. Отношения эквивалентности снова появятся в следующем разделе, где целые и рациональные числа строятся как классы пар.
Натуральные числа и аксиомы Пеано. Определяет натуральные числа с помощью $1$ , операции следования и пяти аксиом, последняя из которых есть принцип математической индукции. Всё дальнейшее в разделе вытекает из этих аксиом и из того немногого, что принимается явно.
Основные операции и отношения порядка. Формулирует теорему о рекурсии, определяет с её помощью сложение, умножение и возведение в степень, доказывает по индукции их свойства и основывает порядок на сложении. Показывает, что вычитание и деление не всегда выполнимы в натуральных числах, что предвещает следующий раздел.
Суммы, прогрессии и индукция. Вводит знак суммирования, телескопические суммы и прогрессии и доказывает, что обычная индукция влечёт сильную индукцию и принцип вполне упорядоченности, а также в каком смысле они ей равносильны. Последний, принцип вполне упорядоченности, станет инструментом почти всех доказательств существования в разделе.
Делимость и деление с остатком. Доказывает с помощью принципа вполне упорядоченности, что всякое целое число имеет единственные неполное частное и остаток, и тем самым классифицирует целые числа по остатку и обосновывает признаки делимости.
Простые числа и основная теорема арифметики. Доказывает, что простых чисел бесконечно много и что всякое натуральное число, большее $1$ , раскладывается на простые множители единственным образом, и выводит отсюда, среди прочего, что квадратный корень из натурального числа, не являющегося полным квадратом, иррационален.
Наибольший общий делитель и наименьшее общее кратное. Излагает алгоритм Евклида, который вычисляет наибольший общий делитель без разложения на множители, выводит из него соотношение Безу и полностью решает линейные диофантовы уравнения.
Сравнения и модульная арифметика. Превращает деление с остатком в исчисление: два целых числа сравнимы по модулю $n$ , когда дают одинаковый остаток, а сравнение согласовано со сложением и умножением, так что многие задачи о делимости решаются действиями над одними остатками.
Позиционные системы счисления. Доказывает, что всякое натуральное число записывается единственным образом в любом основании, объясняет, почему школьные способы вычислений верны и почему компьютеры работают в системе с основанием $2$ .
Комбинаторика и бином Ньютона. Определяет число элементов конечного множества, доказывает правила суммы и произведения, учит с их помощью считать без перечисления, определяет биномиальные коэффициенты и доказывает формулу бинома Ньютона, которая объединяет индукцию, суммы и подсчёт.

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

Историческая предыстория

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

В Греции, начиная с VI века до нашей эры, пифагорейцы изучали числа сами по себе, а не только как орудия вычисления. Они классифицировали фигурные числа, например треугольные $1$ , $3$ , $6$ , $10$ , которые являются суммами $1 + 2 + \cdots + n$ , и отличали чётные числа от нечётных. Около 300 года до нашей эры Евклид собрал в книгах с VII по IX Начал арифметику своего времени, упорядоченную дедуктивно: алгоритм, носящий его имя; лемму, согласно которой простое число, делящее произведение, делит один из его множителей; доказательство того, что простых чисел бесконечно много; и построение чётных совершенных чисел. В III веке до нашей эры Эратосфен Киренский придумал своё решето для простых чисел, а в III веке нашей эры, по всей вероятности, Диофант Александрийский изучал в своей Арифметике уравнения, решения которых должны были быть целыми или рациональными числами.

Десятичная система счисления с нулём в качестве цифры сложилась в Индии, была изложена в IX веке аль-Хорезми и попала в Европу, среди прочих путей, через Liber Abaci Фибоначчи, в 1202 году. Треугольник биномиальных коэффициентов был известен в Индии, Персии и Китае за века до того, как Паскаль посвятил ему в середине XVII века трактат, благодаря которому треугольник получил на Западе имя Паскаля. Однако рассуждение по индукции как явный метод доказательства появляется поздно: Франческо Мавролико применил его в труде, опубликованном в 1575 году, чтобы доказать, что сумма первых нечётных чисел есть квадрат, а Паскаль ясно сформулировал его в своём трактате об арифметическом треугольнике. В том же веке Ферма придумал метод бесконечного спуска, одну из форм принципа вполне упорядоченности, а около 1665 года Ньютон распространил формулу бинома на дробные и отрицательные показатели. В 1801 году Гаусс опубликовал свои Disquisitiones Arithmeticae, благодаря которым арифметика стала систематической теорией; в них содержится первое явное доказательство единственности разложения на простые множители.

В течение XIX века математический анализ был перестроен на арифметической почве: действительные числа были определены через рациональные, как это сделал Дедекинд в 1872 году с помощью своих сечений, рациональные через целые, а целые через натуральные. Если это так, всё построение опиралось на натуральные числа, и оставалось ответить, что они такое и из каких принципов выводится их арифметика. В 1861 году Герман Грассман уже показал, что сложение и умножение можно определить рекурсивно, исходя из следования, и что их свойства доказываются по индукции. В 1888 году Рихард Дедекинд опубликовал свой очерк Что такое числа и для чего они служат?, в котором натуральные числа характеризуются следованием и индукцией, а в 1889 году Джузеппе Пеано опубликовал на латыни свои Arithmetices principia, nova methodo exposita со списком аксиом, который принимает этот курс и который, как и там, начинается с $1$ .

Задача, из которой родилась теория

Натуральных чисел бесконечно много, и почти всё, что о них интересно утверждать, есть утверждение обо всех сразу: что сложение коммутативно, что всякое натуральное число, большее $1$ , раскладывается на простые множители, что сумма $n$ первых нечётных чисел равна $n^2$ . Никакое утверждение такого рода нельзя установить, перебирая случаи один за другим, потому что перебор никогда бы не закончился; и, что ещё серьёзнее, подтверждение многих случаев, сколь бы многочисленны они ни были, не позволяет заключить ничего об остальных. Итак, задача такова: дано свойство $P$ натуральных чисел; с помощью каких принципов можно доказать, что им обладает всякое натуральное число?

(\forall n \in \mathbb{N})\,P(n)

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

ПримерМногочлен, который как будто даёт только простые числа

Эйлер заметил в XVIII веке, что выражение $n^2 + n + 41$ даёт простое число при каждом из значений $n = 1, 2, \ldots, 39$ . Естественно спросить, даёт ли оно простое число при всяком натуральном $n$ .

Доказательство

$1^2 + 1 + 41 = 43, \quad 2^2 + 2 + 41 = 47, \quad 3^2 + 3 + 41 = 53$
Первые значения простые, в чём можно убедиться, пробуя делить их на простые числа, квадрат которых их не превосходит.
$39^2 + 39 + 41 = \resaltar{1601}$
Перебор можно с терпением продолжить до $n = 39$ : все тридцать девять значений простые, и последнее из них равно $1601$ .
$40^2 + 40 + 41 = \resaltar{40 \cdot 41} + 41 = \resaltar{41 \cdot 41}$
При $n = 40$ первые два слагаемых имеют общий множитель $40$ , и результат равен $41$ , взятому $41$ раз.
$41^2 + 41 + 41 = 41 \cdot \resaltar{43}$
При $n = 41$ неудача ещё нагляднее, потому что все три слагаемых кратны $41$ .
$1 + 3 + 5 + \cdots + (2n - 1) = n^2$
Тридцати девяти благоприятных подтверждений было недостаточно: утверждение ложно. Напротив, формула суммы первых нечётных чисел, которую Мавролико доказал по индукции, верна для всякого натурального числа, и не потому, что она подтверждена во многих случаях, а потому, что она выводится из принципа, охватывающего все числа.

Ответ, данный Дедекиндом и Пеано, состоит в том, чтобы объявить аксиомой принцип, позволяющий перейти от конечного к бесконечному: если свойство верно для $1$ и передаётся от каждого натурального числа к его последователю, то оно верно для всех. Отсюда вытекает точная программа, и это программа данного раздела: определить операции так, чтобы каждый случай сводился к предыдущему, и доказать по индукции или с помощью одного из равносильных ей принципов каждое из их свойств. Однако у задачи есть вторая сторона, проходящая через весь раздел: обратные операции. Вычитание и деление не всегда выполнимы в натуральных числах, и вопрос о том, когда они выполнимы, ведёт к делимости, простым числам и наибольшему общему делителю; вопрос о том, как это исправить, ведёт к следующему разделу, который расширяет натуральные числа вплоть до комплексных.

Значение натуральных чисел

Внутри этого курса результаты раздела встречаются постоянно. Урок о целых числах строит их как пары натуральных, а урок о рациональных числах строит их как пары целых; деление многочленов в уроке о корнях многочленов высших степеней подражает делению с остатком, а правило Горнера происходит от позиционной записи. Оценка из бинома Ньютона для $\left(1 + \frac{1}{n}\right)^n$ подготавливает урок о числе $e$ . Продолжение этого курса, «Алгебра и геометрия II», продолжает пользоваться ими: в его разделе о комплексных числах в тригонометрической форме формула Муавра доказывается по индукции, а в его разделе о матрицах и алгебраических структурах урок об алгебраических структурах превращает остатки от деления на $n$ в кольцо, которое является полем ровно тогда, когда $n$ простое.

Вне этого курса последовательности и суммы курса «Математический анализ I» изучаются с помощью знака суммирования и индукции, а производная степени находится с помощью бинома Ньютона. В курсе «Основы механики» закон, опубликованный Галилеем в 1638 году, согласно которому тело, падающее из состояния покоя, проходит за равные промежутки времени расстояния, пропорциональные последовательным нечётным числам $1, 3, 5, 7, \ldots$ , превращается, благодаря сумме первых нечётных чисел, в пропорциональность пройденного пути квадрату времени. Простые и сложные проценты курса «Финансовая математика» являются арифметическими и геометрическими прогрессиями; программы курса «Программирование на C++ I» представляют числа в системе с основанием $2$ , вычисляют остатки и применяют алгоритм Евклида, а их рекурсия есть та же идея, что и рекурсивные определения сложения и умножения. Курс «Математическая логика I: логика высказываний» изучает правила вывода, которыми пользуются доказательства раздела.

В науке и технике основание $2$ служит языком всякого компьютера, а арифметика остатков лежит в основе контрольных цифр, с помощью которых обнаруживаются ошибки при переписывании номеров документов, счетов или книг. Криптографическая система, опубликованная в 1977 году Ривестом, Шамиром и Адлеманом, на которой держится значительная часть безопасности связи, основана на контрасте, который этот раздел позволяет понять: алгоритм Евклида быстро вычисляет наибольший общий делитель чисел из сотен цифр, тогда как никакого быстрого способа разложить их на множители не известно. Наконец, комбинаторика есть основа исчисления вероятностей, а через него статистики и значительной части физики и биологии.