ПЕРВЫЙ В ИСТОРИИ НАУКИ ОПЫТ
ИНДУКТИВНО-РЕКУРСИВНОГО ПОСТРОЕНИЯ
ДЕДУКТИВНОЙ ТЕОРИИ
Теория, которая имеется в виду, - это арифметика целых чи&сел. Ее построение Г. Грассманом в труде 1861/1862 г. мы называ&ем индуктивным, так как ее объекты - числа вводятся индуктив&ными определениями, и рекурсивным, так как операции над ними задаются рекурсивными определениями; что касается доказа&тельств, то они основываются на принципе «совершенной» (пол&ной математической) индукции[176]. Как справедливо выразился Р. Грассман в 1890 г., «Арифметика» Германа Грассмана «вполне раскрывает - особенно в первых разделах - характер метода, при&менявшегося тогда обоими братьями, и их борьбу за наивысшую строгость формы». Метод этот состоял, говоря современным языком, в индуктивном построении системы величин, называе&мой в книге «основной последовательностью», - системы, на которой задавались некоторые операции. Члены этой последова&тельности (которую мы будем сокращенно именовать «о.п.») порождаются из единственного элемента - он обозначается буквой е, - называемого «положительной единичностью», путем операции прибавления к уже построенным величинам либо этой единичности, либо «отрицательной единичности»[177], -е, так что о.п. приобретает вид потенциально бесконечной «в обе стороны» системы:
..., е + -е + -е + - еу е + -е + - еу е + -е, е, е + е, е + е+ е,...
Величина е + -е получает название нуля и обозначается обыч&ным знаком 0. Элемент е и члены ряда, за ним следующие, соста&вляют положительную часть основной последовательности; они представляют собой суммы положительных единичностей. Члены о.п., предшествующие этому элементу, образуют ее неположи&тельную часть; каждый из них есть сумма, состоящая из е и одной или более отрицательных единичностей. Эта часть включает нуль и члены о.п., ему предшествующие (они образуют отрица&тельную часть основной последовательности). На современном языке это означает следующее индуктивное определение: 1) е есть величина, принадлежащая положительной части основ&ной последовательности; 2) если а есть величина положительной части о.п., то а + е тоже величина этой части о.п.; 3) если а есть е или величина, принадлежащая неположительной части основной последовательности, то а+ -е есть величина той же части этой по&следовательности.
Добавление, что о.п.
есть система, состоящая из положитель&ной части основной последовательности и неположительной ее части, завершает определение[178]. В свете этой «модернизации» Грассманова задания «основной последовательности» приобрета&ет четкий смысл то определение арифметики, которое дается в № 6 анализируемой нами книги: «арифметика рассматривает та&кие величины, которые получаются путем связывания из одной- единственной величины е».
Обе операции прибавления единичностей - положительной и отрицательной - являются унарными и поэтому отличаются от вводимой Г. Грассманом позже бинарной операции сложения ве&личин; это не находит отражения в обозначениях, но четко выра&жается в тексте книги, так как в одном случае говорится о при&бавлении единичности или о соединении с единичностью, а в другом - о сложении величин. Подчеркнем, что (в отличие от приведенной выше «модернизации» грассмановского построения основной последовательности) прибавление положительной еди&ничности представляет собой у Г. Грассмана взаимно-однознач&ную операцию взятия непосредственно следующего члена о.п., определенную на всей о.п. (в принятых ныне обозначениях: если а есть произвольная величина основной последовательности, то а' есть величина, непосредственно за ней следующая), а прибавле&ние отрицательной единичности - аналогичную операцию взятия непосредственно предшествующего члена этой последовательно&сти, также определенную на о.п. (мы будем обозначать эту опера&цию двумя штрихами при формуле, выражающей величину).
Система величин основной последовательности замкнута относительно операции сложения. Последняя определяется ре&курсивно следующим образом. Прежде всего доказывается теорема (она составляет содержание пункта 13 книги), соглас&но которой а = а + е + -е. Доказательство основывается на оп&ределении основной последовательности и операциях прибав&ления единичностей и состоит в следующем. Переход от произ&вольной величины а основной последовательности к величине, за ней непосредственно следующей, дает а + е\ обозначим эту величину через Ь\ это значит, что b = а + е; но тогда а есть ве&личина, непосредственно предшествующая величине Ьу и для перехода от а к ft, надо к а прибавить отрицательную единич&ность: а = b + -е\ подставляя в это равенство значение 6, полу&чаем: а = а + е + - е.
Аналогично доказывается, что я = я + + е (теорема № 14). Далее определяется (№ 15) ре&зультат операции сложения - сумма а + Ьу где аиЬ - произволь&ные величины о.п.; а именно под а + b понимается такой член о.п., для которого справедливо равенство a + (b + e) = a + b + e (формула а + b + е читается по ассоциативности влево[179]), и в особом пункте (№ 16 - «Добавление») поясняется, что а + (Ь + е) есть величина, непосредственно следующая за а + Ь. Далее, на основе №№ 13-15 доказывается теорема 17: а + + = я + +
Нетрудно видеть, что система предложений №№ 3-17 образу&ет рекурсивное определение операции сложения. Проследим, как оно «работает». Рекурсия ведется по величине b (в сумме а + Ь, фигурирующей в № 15), при а - произвольном члене основной по&следовательности - в роли параметра, и ход ее зависит от того, в какой части этой последовательности - положительной или непо&ложительной - лежат ее значения (в первом случае используется определение № 5, во втором - теорема № 17). Вычисление значе&ния суммы величин а н b сводится в конце концов к применению теорем №№ 13 и 14, позволяющих надлежащим образом перера&батывать величину я, могущую принадлежать как положитель&ной, так и неположительной части основной последовательности (конечно, процедура вычисления опирается и на свойства отно&шения равенства - это отношение в книге 1861-1862 гг. определя&ется так же, как и в книге 1844 года, - в частности, на правило за&мены равным).
Приведем пример. Пусть складываются величины е + е ие + -е + -е + -е + -е, т.е. определяется значение суммы
е + е + (е + -е + -е + -е + -е). (*)
Четырехкратное применение теоремы № 17 с использованием в нужных случаях правила замены равным приводит к равенству:
е + е + (е + -е + -е + -е + -е) = е + е + е + -е + -е + -е+-е;
двукратное же применение теоремы 13 (с использованием свойств отношения равенства, что мы в дальнейшем оговаривать не будем) приводит к доказательству равенства формулы (*) фор&муле е + - е + - е, являющейся одной из величин основной после&довательности.
В данном примере рекурсия (относительно Ь) осуществлялась по положительной части о.п.
Но если переставить слагаемые, т.е. вычислять значение суммы
е + -е + -е + -е + -е + (е + е), (**)
то мы должны проводить рекурсию уже по его неположительной части. Применив один раз определение № 15 и два раза теорему № 14, мы получим тот же результат, что и в случае (*).
Определение операций (функций) с помощью рекурсивных процедур можно рассматривать как разновидность неявных опре&делений. Рекурсия - в ее простейшей форме, которой пользова&лись Грассманы, - задает операцию сложения в форме процесса порождения ее результатов для множества, в котором есть на&чальный элемент (е) и на котором задается (строгий) порядок пу&тем «взятия непосредственно последующего» (соответственно, «взятия непосредственно предшествующего») при произвольной величине а в роли параметра. В ходе вычисления значения суммы а + b для любой величины b положительной (неположительной) части о.п. - выделенной величины рекурсии - вычисляются значе&ния сумм величины а со всеми величинами, предшествующими b (следующими за Ь)9 вплоть до е (или 0); при этом в случае непо&ложительной части о.п. порядок на ней берется «справа налево». Таким образом, мы имеем здесь дело, по существу, с «возвратно организованным» порождением сумм вида а + Ь, точнее, с двумя разными порождающими процессами, отдельно для значений b в положительной и в неположительной частях основной последова&тельности.
Следует подчеркнуть, что под вычислением значения величи&ны или формулы, как явствует из текста Г. Грассмана, понимает-
с я нахождение графически равного ей члена основной последо&вательности. Ибо, как особо оговаривает Г. Грассман (№ 71), в о.п. каждый ее член отличен от всех остальных, что вместе с установленным им способом порождения величин как слов в ал&фавите знаков е, +, сводит отношение равенства (а также нера&венства) между членами «основной» (а впоследствии и «число&вой») последовательности к отношению графического равенст&ва (неравенства) между словами упомянутого алфавита (разуме&ется, в естественном предположении того, что ныне называется абстракцией отождествления «одинаковых» слов в смысле А.А.
Маркова[180]).
Взглянем теперь на грассмановское определение с современ&ных позиций. Оставим пока в стороне вопрос о том, чтб опреде&ляется в № 15 - сумма а + Ъ или операция сложения « + » (на не&точность способа выражения Г. Грассмана в этом вопросе обра&тил внимание Г. Фреге, о чем мы еще будем говорить), и укажем на то, что если явно различать операции взятия непосредственно последующего и взятия непосредственно предшествующего чле&на, с одной стороны, и операцию сложения - с другой, то №№ 13-17, с учетом доказанной Г. Грассманом теоремы а + 0 = а (№ 18), приведут, если пользоваться современной записью, к ра&венствам:
задающим операцию сложения[181]. Здесь (1) выражает тривиаль&ное равенство а + е = а + е, (2) есть иная запись определения сум&мы (№ 15), (1°) - запись свойства нуля (№ 18), а (2°) - теоремы № 17. Заметим, что, при таком представлении грассмановской
рекурсивной процедуры, в рассмотренном выше примере сложе&ния величин е + е и е+ - е+ - е+ - е+ - е надлежит учитывать вы&текающее из определения нуля и № 18 равенство а + е + - е = = а + (е + - е). Поскольку (1°) и (2°) доказуемы на основе №№ 13-15, рекурсивное определение сложения можно ограни&чить равенством (1). Однако это определение можно произвести и только с помощью равенств (1°), поскольку нетрудно показать, что в предположении № 17, рассматриваемого в качестве «опре&деления суммы», используя №№ 13 и 14, равенство № 15 доказуе&мо в качестве теоремы.
После обоснования основных свойств сложения (включая ас&социативность и коммутативность) Г. Грассман вводит обратную сложению операцию вычитания членов о.п. Последняя задается уже путем контекстуального определения (№ 28): под разностью а - fc, где аиЬ- произвольные величины основной последователь&ности, понимается такая величина этой последовательности, что а - b + b = а (при этом запись a- b + b читается по ассоциативно&сти влево).
Определение это непосредственно не рекурсивно, од&нако позволяет доказать[182] ряд теорем, таких как теорема 39: а + (-b) = а - Ь, теорема 41: -а + - b = - а - b = - (а + Ь) к другие, которые делают возможным рекурсивную процедуру вычисле&ния разности. Остается добавить, что в силу теоремы (№ 26), сог&ласно которой для любых двух величин а и b из о.п. всегда имеет&ся некоторая величина х такая, что b = а + дг, вычитание оказыва&ется всегда выполнимой операцией, а благодаря теореме (№ 27), согласно которой равенство а + b = а + с влечет равенство b = с, результат этой операции - однозначным.
Только после этого вводится множество всех целых чисел - основной объект грассмановской арифметики. Оно начинается с определения операции умножения (для которой в дальнейшем за&дается обратная ей операция деления), осуществляемого путем замены «единичности», е, на «единицу» (die Eins), 1. А именно «основная последовательность» становится «числовой последо&вательностью» (множеством всех целых чисел) благодаря опре&делению (фигурирующему под № 52): а 1 = а и установлению (определение № 53) того, что числовая последовательность есть такая основная последовательность, единичность которой есть единица. Определение 52 и последующие определения №№ 56-58 задают (с учетом введенного в № 55 понятия противо&положности положительных и отрицательных чисел) процедуру вычисления произведения двух произвольных целых чисел. При этом, в отличие от определения сложения, которое производится для «суммы», Г. Грассман говорит об определении именно (опера&ции) умножения. Последнее имеет следующий вид: 1) рекурсивно определяется умножение произвольного целого числа на положи&тельное число; 2) явно определяется умножение на нуль (№ 57: а • 0 = 0), 3) явно определяется (№ 58) умножение на отрицатель&ное число как приводящее к результату, представляющему собой число, противоположное числу, получающемуся при умножении на соответствующее положительное число: д(~Р) = Чар), где Р есть положительное число, a -р есть противоположное ему от&рицательное. Рекурсия 1) имеет в качестве базиса № 52, а рекур&сивный процесс задается (№ 56) равенством оф' = ар + а (вместо р' Г. Грассман, как мы знаем, пишет Р + 1).
Не останавливаясь на способах введения остальных арифме&тических операций (возведение в степень также задается рекур&сивным определением), отметим лишь, какого рода словами (в алфавите 1, +, -) оказываются целые числа.
«55. Числовой ряд есть ...I-3I-2I-1I0I1I2I3I...,
и каждое его отрицательное число противоположно некоторому положительному», вертикальная черта служит для отделения од&ного числа от другого. Здесь 2 есть сокращение для 1 + 1, 3 - со&кращение для 2+1, т.е. для 1 + 1 + 1, и т.д.; что касается отрица&тельных чисел:..., -3, -2, то теорема 41 позволяет представить их в виде: ..., -(1 + 1 + 1), -(1 + 1). В дальнейшем изложении обнару&живается та цель, ради которой, как можно полагать, понятие «основной последовательности» и было введено в качестве пред- шествующего понятию последовательности числовой: в отличие от последнего первое понятие охватывает также изоморфные чи&словой последовательности системы именованных чисел.
В «Учебнике арифметики» известные свойства сложения (в частности, ассоциативность и коммутативность) и вычитания[183]доказываются для величин основной последовательности; но дока&зательство дистрибутивности умножения относительно операций « + » и «-» ведется уже в применении к последовательности чи- еловой. С алгебраической точки зрения грассмановская о.п., на которой определено сложение и вычитание, представляет собой (аддитивную) коммутативную группу без кручения (т.е. группу, в которой отсутствуют элементы конечного порядка, кроме нуля[184]), переход же к числовой последовательности означает обобщение этой группы до кольца (целых чисел).
Не рассматривая дальнейшего содержания книги 1861/1862 г.[185], обратимся к применяемым в ней доказательствам[186].
Еще по теме ПЕРВЫЙ В ИСТОРИИ НАУКИ ОПЫТ
ИНДУКТИВНО-РЕКУРСИВНОГО ПОСТРОЕНИЯ
ДЕДУКТИВНОЙ ТЕОРИИ
:
- Глава II. Способы обогащения нашего королевства и увеличения количества денег в стране