Тема 4. Ряд натуральных чисел. Рекуррентные формулы и функция следования. Принцип индукции. Примеры доказательств в формальной арифметике.

Интересно, что и ряд натуральных чисел может быть описан образом аналогичным тому, как описывается множество всех степеней некотрого отношения по композиции. Положим, на некотором множестве Nзадана функцияsN^N (и соответствующее отношение равенства, обозначаемое символом =, требуемое для укзания его свойства функциональности). Также положим наличие элемента 1N, с которого начнём построение ряда, используяsв качестве функции следования. На неё наложим следующие ограничения:

1. s – инъективная функция:xN yN (( s(x)=s(y) ) → ( x=y ))

2. Элемент 1 не покрыт значениями s:xN (s(x)=1)

В этом случае s(1)1 по свойству (2). То есть уже имеем два разных элемента.s(s(1))1 также по свойству (2). Ноs(s(1))s(1) по свойству (1), иначе быs(1) был бы сопоставлен сразу, как уже показано, разным аргументам 1 иs(s(1)). Рассуждая аналогично, можно показать, что и другие элементы ряда все различны. Начало графа такой функции выглядит так:

Собственно такой ряд отражает (моделирует) процесс счета. Он подобен унарной системе записи: число «один» обозначается как 1, число «два» обозначается какs(1), число «три» какs(s(1)) и так далее. То есть основной формой представления чисел здесь является их выражение через элемент 1 и функцию следованияs. Каждому числу соответствуетединственнаятакая формула.

На этом ряду далее можно определить арифметические операции рекуррентными соотношениями, подобно тому, как ранее была определена степень для бинарных отношений. Покажем, как определить бинарную операцию сложения, обозначаемую символом +. Задаются начальные условия (A) – что означает прибавление 1 (переход к следующему в ряду элементу) и рекуррентная формула (B) – как, зная как прибавить некоторое число, прибавить следующее (это будет следующее за суммой):

(правило A) x+1 = s(x)

(правило B) x+s(y) = s(x+y)

Покажем, как применять эти правила для вычисления результата операции +. Вычислим результат сложения чисел «два» и «три». Необходимо найти представление для выражения s(1)+s(s(1)) только через символы 1 иs, применяя правила (A) и (B):

Над знаками = надписаны названия правил, по которым производится замена: если справа от символа + стоит формула вида s(…), применяется правило (B), если справа от символа + стоит символ 1, применяется правило (A). Процесс заканчивается, когда в формуле остаются только символы 1 иs. В данном примереs(s(s(s(1)))) является представлением для числа «пять», единственным в данной системе записи. Сам термин «формальная арифметика» используется для данной модели счета именно потому, что элементы множества натуральных чисел представлены в виде правильно построенных формул с предметной константой 1 и одноместным функциональным символомs.

Конечно, такой способ вычислений (в унарном коде) неэффективен. Использование привычной позиционной системы (десятичной или двоичной) существенно выгоднее. Но такая унарная форма с рекуррентными определениями операций позволяет доказывать многие свойства существенно проще, а главное, с минимальным набором первичных представлений.

Доказательства утверждений о произвольных таких натуральных числах (формул вида xNP(x) ) невозможно выполнить просто перебирая все элементы, строя их по рекуррентной формуле (в отличие от рассматривавшихся ранее конечных множеств, например, логических значений). Видно, что процесс построения всех натуральных чисел (формул видаs(s(s(…)))) не может быть закончен за конечное число шагов – натуральный ряд не может иметь точек повторения, аналогичныхⁱ=^j. Поэтому, если формулу не удаётся доказать методами вывода логических исчислений (найти конечную цепочку подстановок по некоторым правилам, переводящим одну формулу в другую), прибегают к выводу на основепринципа индукции.

Допустим, необходимо доказать истинность высказывания вида xNP(x). ЗдесьP – некоторое свойство для натурального числа. ФормулуxNP(x) считаем доказанной, если возможно доказать истинности следующих утверждений:

1. База индукции: P(1)

2. Шаг индукции (индукционный переход):xN(P(x) →P(s(x)) )

То есть, мы как бы добавили новое правило вывода

( P(1) & ( xN ( P(x) → P(s(x)) ) ) )  ( xN P(x) )

Само утверждение P(x) на шаге индукции называют индукционным предположением.

Докажем, например, что определённая выше операция сложения натуральных чисел + является ассоциативной: (a+b)+c=a+(b+c). Сформулируем задачу так, чтобы увидеть, в чем заключается в данном случае свойствоP. Определим предикатPследующим образом:

P(x) = ( (a+b)+x=a+(b+x) )

Тогда база индукции превратится в P(1) = ( (a+b)+1=a+(b+1) ), а шаг индукции будет иметь вид:

( P(x)  P(s(x)) ) = ( (a+b)+x=a+(b+x)  (a+b)+s(x)=a+(b+s(x)) )

Докажем сначала первое утверждение (a+b)+1=a+(b+1), используя правила, определяющие операцию+:

По правилу (A) (a+b)+1 = s(a+b).

По правилу (A) a+(b+1) = a+s(b).

По правилу (B) a+s(b) = s(a+b).

Получили, что и левая и правая части равенства равны s(a+b).

Теперь аналогично докажем второе утверждение

(a+b)+x=a+(b+x)  (a+b)+s(x)=a+(b+s(x))

Для левой части получаем (над символами = надписаны названия правил, по которым производится замена текста в формулах): .

Для правой части .

Но аргументы sв левой и правой частях равны по индукционному предположению: (a+b)+x=a+(b+x). Следовательно, должны быть равны и результаты:s((a+b)+x)= s(a+(b+x)).

Тем самым доказана формула xNP(x) =xN ( (a+b)+x=a+(b+x) ).

Аналогично можно дать рекуррентное определение для умножения как многократного сложения и для возведения в степень, как многократного умножения:

x·1=x

x·s(y)=(x·y)+x

x¹=x

x^s(y)=x^y·x

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

Принцип индукции в математике трактуется двояко: если в системе рассуждений принято говорить о таких бесконечных объектах, как, например, рассмотренный ряд натуральных чисел, как о готовых объектах (хотя ясно, что его невозможно построить за конечное число шагов), его можно рассматривать как дополнительное правило вывода к логическим исчислениям. Такой подход известен как абстракция актуальной бесконечности. Другая трактовка может быть пояснена так: несмотря на то, что мы не можем построить подобное бесконечное множество целиком, укажем, как выполнять те или иные действия для их произвольных элементов. Например, приведённое доказательство по индукции для свойства ассоциативности можно рассматривать как набор правил для выписывания доказательства в виде конечного набора подстановок для любого числаc, представленного в указанной форме (через 1 иs). Дляc=s(1)будем иметь

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

Множество натуральных чисел в дальнейшем будем обозначать символом ℕ, а его элементы в любой удобной системе счисления, позиционной или унарной.

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

Вернёмся теперь к конечным множествам и отношениям на них. Конечное множество можно представить как множество, эквивалентное некоторому отрезку натурального ряда от начального элемента 1 до некоторого конечного числа. Под эквивалентностью множеств имеется в виду возможность построить взаимнооднозначное соответствие (биективную функцию) из одного множества в другое (и обратно). Будем в этом случае говорить, что множество занумеровано. Его элементы будем тогда символически обозначать в виде символа с нижним индексом. Фактически это есть просто форма представления той самой функции, взаимнооднозначно ставящей в соответствие натуральному числу элемент конечного множества. Следующая схема поясняет это представление:

Здесь в A– три элемента. Числам 1, 2, 3 взаимнооднозначно сопоставлены элементы множестваA. Пусть для индексации элементов множества выбран символа. Тогда для данной функцииf, нумерующей элементы множеств, обозначимa_i=f(i). То естьa₁=p,a₂=q, a₃=r.K = {1, 2, 3} здесь множество индексов,Kℕ,f A^K, A~K. Будем также записыватьA={a₁, a₂, a₃}. Для конечного, но не оговоренного числа элементовnбудем записыватьA={a₁, a₂, … a_n} и говорить, множествоAсодержитnэлементов.

На основе такого приписывания индексов элементам множеств рассмотри ещё одну удобную форму представления бинарных отношений (и, соответственно, ориентированных графов) – представление при помощи матриц. Пусть ABиA={a₁, a₂, … a_n} иB={b₁, b₂, … b_m}. Матрицей отношенияназывается прямоугольная матрица изnстрок иmстолбцов из логических значений высказываний вида (а_i, b_j)в строкеiи столбцеj. Матрицу отношениябудем обозначать символомC^:

Номера строк соответствуют элементам множества A. Номера столбцов соответствуют элементам множестваB. ЕслиAA, то матрица будет квадратной.

Например, для уже рассматривавшегося примера отношения, заданного ориентированным графом

при нумерации элементов A={a₁, a₂, a₃, a₄},a₁=a, a₂=b, a₃=c, a₄=d, матрица отношения будет

В матричной форме удобно выполнять рассмотренные операции над отношениями.

Теоретико-множественные операции над отношениями на одних и тех же множествах выполняются покомпонентно:

,,и т.д.

Обращение заключается в транспонированииматрицы (замена строк на столбцы)

или более кратко

Вычисление композиции заключается в логическом умноженииматриц. Обозначим эту операцию символом • и определим ее следующим образом:

Тогда матрица для композиции будет строиться так:

Смысл этой операции в том, что перебираются все элементы общего для данных отношений множества и проверяется, может ли такой элемент kбыть промежуточным на пути из двух шагов от элементаiк элементуj.

Вычислим степенной ряд для отношения из примера, используя матричную форму:

Степени отношений выражают возможность достичь одну вершину из другой ровно за определенное число шагов. Чаще интереснее узнать, можно ли вообще за какое-либо число шагов перейти из одной вершины в другую. Запишем условие такого перехода из вершины xв вершинуy:

(x, y)¹  (x, y)²  (x, y)³ …

То есть по всем возможным kнеобходимо объединить по операции ЛОГИЧЕСКОЕ ИЛИ kстепени отношения. Это есть представление фразы «достижимо за 1 шаг ИЛИ достижимо за 2 шага ИЛИ достижимо за 3 шага ИЛИ …». Соединению высказываний через связкусоответствует объединение соответствующих множеств –степеней отношения. Объединение ведется по всем возможным степеням – натуральным числам. Результат можно назвать отношениемдостижимости, обозначается символом ^ над обозначением отношения. По определению

Но перебирать все натуральные числа невозможно, а достижимость надо вычислять. Оказывается для конечных множеств Аизnэлементов, на которых задано отношение(АА) достаточно объединить первыеnстепеней. Символически будем записывать это так:

Это объясняется тем, что если между вершинами есть путь за сколько-нибудь шагов, и этот путь длиннее числа вершин, то промежуточные вершины вместе с конечной вершиной не могут все быть различными. Это означает наличие цикла в маршруте и путь можно сократить на длину указанного цикла. Новый, эквивалентный путь, если он окажется длиннее числа вершин можно аналогично сократить. Иначе мы уже нашли путь длины не более n. Процедуру же сокращения можно выполнять, пока длина пути не перестанет превосходитьn.

Более формально,

(x, y) k (x, y)^k

Если k≤nто условие выполнено, (x, y)

Иначе для k>nвыписываем условие наличия пути длинойk

(x, y)^k  u₁u₂…u_k1 (x, u₁) & (u₁, u₂) & … & (u_k1, y).

Обозначим u_k = y. Тогда i j>i u_i= u_j. Получаем новый путь

(x, u₁)& (u₁, u₂)& … & (u_i1, u_i) & (u_j, u_j+1) & … & (u_k1, y).

Место, где удалён цикл, подчеркнуто.

Длина этого цикла =k(ji)<k.(x, y).

Продолжая эту процедуру необходимое число раз, можно показать, что

m≤n (x, y)^m  (x, y)

Для вычисления достижимости в матричной форме используется сочетание матричного произведения для вычисления степеней и объединения результатов при помощи поэлементного ЛОГИЧЕСКОГО ИЛИ.

Обратите внимание, что это существенно меньше действий, чем верхняя оценка для числа разных значений степени (). Конечно, реальные длины рядов степеней короче, может быть даже меньшеn. В рассмотренном примере приn=4 было только три разных степени. В примере, где⁴=², можно вычислить как =¹²³.

В матричной форме для рассмотренного примера получим

Граф для этого отношения будет иметь вид

Для натуральных чисел достижимость по функции следования представляет собой отношение «меньше»:

={(x, y) | xℕ & yℕ & x<y}

Фактически, это могло бы быть определением для отношения < на ℕ:

x<y (x, y)

Пример (2<4):

(s(1), s(s(1)))s & (s(s(1)), s(s(s(1))))s  (s(1), s(s(s(1)))) ss  (s(1), s(s(s(1)))) .

Так можно формализовать конечное множество натуральных чисел, меньших или равных заданного числа x(например, множество индексов для нумерации):

K_x = { y | yℕ & ((y, x)  (x=y)) }

Можно тогда сказать, «множество Aимеетnэлементов» какA~K_n(множествоAэквивалентно множествуK_n).

В параллель с рекуррентно определяемыми операциями (степень, сумма, произведение) можно говорить и о рекуррентно определяемых предикатах (свойствах). Например, имея функциональное отношение следования sс соответствующим двухместным предикатомS(x, y) = (y=s(x)) рекуррентно определим свойство «быть натуральным числом»N(x) = (xℕ):

N(1) & xy( (N(x)& S(x, y)) → N(y))

То есть N(y) = (y=1)  (y=s(x) & N(x)) или

Правило 1: N(1)=1

Правило 2: N(s(x))=N(x)

Тогда вычислим, например N(s(s(1))):

N(s(s(1))) = N(s(1))  = N(1)  = 1