Перейти к содержимому
Topos Uranos
Русский

Основные операции с натуральными числами и отношения порядка

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

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

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

  1. Формулировать теорему о рекурсии и записывать с её помощью определения по рекурсии сложения, умножения и возведения в степень натуральных чисел.
  2. Доказывать по индукции свойства операций, исходя из их определений.
  3. Определять порядок на натуральных числах через сложение и применять его свойства трихотомии, транзитивности и монотонности.
  4. Распознавать, когда существуют разность и частное двух натуральных чисел, и выполнять с ними действия, не выходя за пределы натуральных чисел.

Сложение

Действия с натуральными числами известны со школы; здесь речь идёт о том, чтобы обосновать их с математической точностью. В уроке об аксиомах Пеано натуральные числа были определены исходя из 11 и операции следования, которая сопоставляет каждому натуральному числу nn следующее за ним, S(n)S(n). Сложение определяется через функцию следования двумя правилами: прибавить 11 значит взять последователя, а прибавить последователя числа mm значит взять последователя суммы с mm.

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

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

Факт, принимаемый без доказательства (теорема о рекурсии). Пусть XX есть множество и cc есть элемент XX, и пусть для каждого натурального nn дано правило gng_n, сопоставляющее каждому элементу XX некоторый элемент XX. Тогда существует функция ff из N\mathbb{N} в XX, такая что f(1)=cf(1) = c и f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) для всякого натурального nn, и эта функция единственна.

Существование принимается в этом курсе без доказательства. Его доказательство требует построить функцию ff как множество пар: наименьшее множество пар, которое содержит (1,c)(1, c) и вместе с каждой парой (n,x)(n, x) содержит (S(n),gn(x))(S(n), g_n(x)); а затем убедиться по индукции, что каждому натуральному числу в нём соответствует единственный второй элемент. Это построение относится к теории множеств и ничего не добавляет к последующей арифметике. Единственность же есть прямое следствие пятой аксиомы Пеано.

ЛеммаЕдинственность функции, определённой по рекурсии

Если две функции ff и hh из N\mathbb{N} в XX удовлетворяют обоим условиям теоремы о рекурсии, то они равны. Рисунок изображает значения обеих функций на первых натуральных числах.

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

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

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

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    Число 11 принадлежит AA, поскольку обе функции принимают значение cc в 11.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    Если kk принадлежит AA, то и S(k)S(k): обе функции применяют одно и то же правило gkg_k к одному и тому же значению.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    По пятой аксиоме Пеано AA есть множество всех натуральных чисел: обе функции равны.

Сложение получается из теоремы, если зафиксировать первое слагаемое nn и взять X=NX = \mathbb{N}, c=S(n)c = S(n) и для всякого mm правило gmg_m, сопоставляющее каждому натуральному числу его последователя: функция ff, которую даёт теорема, сопоставляет каждому mm число n+mn + m, а два правила сложения суть два условия теоремы. Точно так же при c=nc = n и правиле, прибавляющем nn, получается умножение, а при c=bc = b и правиле, умножающем на bb, возведение в степень. Прибавить mm означает, в конечном счёте, применить mm раз функцию следования.

ПримерДва плюс два равно четырём

Самое известное утверждение арифметики есть теорема, которая доказывается с помощью двух правил сложения и обозначений 2=S(1)2 = S(1), 3=S(2)3 = S(2) и 4=S(3)4 = S(3).

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

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    Записываем второе слагаемое как последователя 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

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

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    По первому правилу прибавить 11 значит взять последователя.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Так как S(2)=3S(2) = 3 и S(3)=4S(3) = 4, получаем результат.

Из правил сложения по индукции выводятся его свойства. Для всех натуральных aa, bb и cc:

  1. Коммутативность: a+b=b+aa + b = b + a.
  2. Ассоциативность: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). Поэтому можно писать a+b+ca + b + c без скобок.
  3. Закон сокращения: если a+c=b+ca + c = b + c, то a=ba = b.

Коммутативность была доказана в решённой задаче 5 урока об аксиомах Пеано, а ассоциативность составляет там одну из задач для самостоятельного решения. Закон сокращения доказывается в решённой задаче 1 этого урока.