о чем тут речь?

после того как в конце XVII в. Ньютон и Лейбниц создали дифференциальное и интегральное исчисление, довольно долго среди математиков не утихали споры и оставались расхождения во мнениях по поводу его основных понятий. такие понятия, как "бесконечно малая величина" и "предел бесконечной последовательности", были окутаны таинственностью, и некоторые из утверждений тех лет выглядят довольно странно с современной точки зрения (например, "величина, которая бесконечно мало возрастает или убывает, не возрастает и не убывает" (Я.Бернулли)). в XIX в. этот предмет стал, наконец, строго обоснованным, первоначально благодаря вкладу Коши, точно определившему понятие "предела" и "сходимости". затем последовала принадлежащая Вейерштрассу и др. "арифметизация матанализа", что привело к чисто алгебраической трактовке системы натуральных чисел. важным следствием этого было начало отделения анализа от физической интуиции как основания (см. доказательство Вейерштрасса существования (вопреки интуиции?) непрерывной всюду недифференцируемой функции). это наряду с другими факторами, такими, как развитие неевклидовой геометрии, внесло существенный вклад в признание того, что математические структуры обладают абстрактной концептуальной реальностью, совершенно независимой от физического мира

столь же важными в это время явились работы Дедекинда и Пеано о числовых системах. вещественные числа строились по рациональным, рациональные - по целым, а целые - по натуральным. затем аксиомы Пеано дали абстрактное описание природы самих натуральных чисел. такая редукция привела к развитию идеи, что в основе всей математики должна лежать одна аксиоматическая система, которая в свою очередь должна базироваться на небольшом числе понятий и принципов. с тех пор эта концепция стала центральной в исследовании оснований математики. свою крайнюю форму она принимает в логистическом тезисе Фреге и Рассела, что математика есть часть логики и что математические истины выводимы из чисто логических принципов. она присутствует и в работах Гильберта, пытавшегося аксиоматизировать математику и доказать непротиворечивость этой аксиоматики финитными методами

к тому времени, когда на сцене появился Кантор, было признано, что упоминания о бесконечности, как, например, в случае "последовательности n², стремящейся к бесконечности при n, стремящемся к бесконечности", можно рассматривать как наглядные выражения точных, хотя и сложных, утверждений о свойствах вещественных чисел ("для всякого ε найдется δ, такой что ..." и т.д.)

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

позиция Кантора заключалась в том, что всякое грамматически правильное и логически корректно выведенное утверждение имеет концептуальное значение, даже если оно выходит за рамки нашей основной интуиции о конечных числах и совокупностях

эта теория множеств имела громадный успех, хотя и не обошлось без критики

Кронекер, известный своим высказыванием: "Бог создал целые числа, все остальное - творение человека", отрицал такие понятия, как "бесконечное множество" и "иррациональное число", считая их мистическими, а не математическими. он утверждал, что из логической правильности теории не вытекает существование объектов ее описания - они не имеют никакого значения, если их нельзя построить на самом деле. как сказал Кронекер, "числа и операции над ними должны быть интуитивно обоснованы, определения и доказательства должны быть конструктивными в буквальном смысле этого слова. определения должны показывать явно, как построить определяемый объект по объектам, существование которых уже установлено"

в классической математике "доказательство существования" часто состоит в установлении того, что несуществование объекта некоторого определенного вида приводит к противоречию. с точки зрения конструктивиста это ни в коей мере не есть доказательство существования, и, для того чтобы узаконить последнее, необходимо явно установить существование данного объекта. Кронекер был уверен, что для натуральных чисел можно найти такое обоснование, а для вещественных - нет. с этой точки зрения он предпринял попытку переработать некоторые части математики

концепция "вещей как сущностей, построенных из уже данных сущностей", выразилась также в реакции Пуанкаре на парадоксы теории множеств. его точка зрения состояла в том, что источник противоречия - в употреблении непредикативных определений. это - определения, включающие самоотнесение, содержащие "круг", т. е. задающие некоторый объект X при помощи множеств, существование которых зависит от самого объекта X. Пуанкаре считал, что такие определения - недопустимы и что множество не определено, пока не определен каждый из его элементов. одна из половин парадокса Рассела состоит в констатации принадлежности ℝ⊆ℝ. значит, с этой точки зрения определение класса ℝ содержит "круг", поскольку его можно точно задать лишь тогда, когда он сам уже определен. Пуанкаре считал, что математика должна развиваться без использования непредикативных определений на основе системы натуральных чисел. поэтому класс Рассела ℝ даже и не должен возникать как объект законного изучения. при этом оказывается, что урон очень ощутим, поскольку значительная часть классического анализа для вещественной числовой системы связана с непредикативными определениями

конструктивистская позиция, проявившаяся во взглядах Кронекера и Пуанкаре, нашла свое выражение в философии интуиционизма, пионером которой в начале этого века явился датский математик Брауэр. он не признавал неконструктивных рассуждений и понятия бесконечных совокупностей как "вещей в себе". более того, Брауэр отрицал, что традиционная логика дает правильное представление математического рассуждения. и в доказательствах существования так называемый "аргумент от противного : X истинно, так как в противном случае возникает противоречие") конструктивистски неприемлем. для Брауэра же он неприемлем как принцип рассуждения вообще. то же самое относится к закону "исключенного третьего : X V ~X"

в классическом описании истинности, предложения всегда рассматриваются как истинные или ложные независимо от того, знаем ли мы, что имеет место на самом деле. более того, предложение ~X считается истинным, только если ложно предложение X. поэтому формулу "X V ~X" можно интерпретировать высказыванием "X или истинно, или ложно", а это последнее предложение истинно в классической логике. однако для интуициониста всякое утверждение представляет обой запись конструкции. для него заявление об истинности X равноценно высказыванию: "я выполнил построение того, что описывается предложением X". аналогично предложение ~X есть запись конструкции, которая показывает, что X не имеет места. с этой точки зрения закон исключенного третьего формулируется следующим образом: "либо я конструктивно доказал истинность X, либо я конструктивно доказал ложность X"

если мы теперь в качестве X возьмем некоторое неразрешенное утверждение, то предложение "X V ~X" не истинно. действительно, про данное утверждение неизвестно, верно он или нет. следовательно, по Брауэру мы не можем утверждать, что "X истинно" или "X ложно", пока конструктивно не установлено, который из этих случаев имеет место. высказывание, что "X не истинно", подразумевает только, что в настоящий момент X не установлено конструктивно, а это не совпадает с высказыванием "X ложно" - может быть, завтра конструкция будет найдена

точка зрения Брауэра на историю логики заключается в том, что все известные логические законы были получены абстрагированием структуры математических выводов в то время, когда ее применение ограничивалось миром конечных объектов. впоследствии этим принципам логики приписали а priori независимое существование. по этой причине они применялись во всем последующем развитии, включающем манипулирование и с бесконечными множествами. поэтому современная математика имеет основания и использует процедуры, значимые только для более ограниченной области. чтобы достичь подлинного математического знания и определить правильные способы рассуждения, необходимо вернуться к первоисточнику математической истины

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

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

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

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

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

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

топологические аспекты интуиционистской логики были обнаружены независимо Альфредом Тарским и Маршаллом Стоуном. они показали, что открытые множества топологического пространства образуют "алгебру множеств", операции которой удовлетворяют законам, соответствующим Аксиомам системы интуиционисткой логики . Маккинси и Тарский обратились к разработке этой темы в своих исследованиях по алгебре топологии. в этих работах появляются "алгебры с замыканием", которые представляют собой булевы алгебры с одной дополнительной операцией, свойства которой абстрагированны от операции образования замыкания множества в топологическом пространстве. в каждой "алгебре с замыканием" имеется множество специальных элементов, допускающее операции ∪ , ∩ , => , ¬ которые подчиняются интуиционистским принципам. Маккинси и Тарский привлекли особое внимание к этим алгебрам, дали им независимую аксиоматизацию и назвали их алгебрами Брауэра


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

термин "рекурсивный" в качестве стандартного широко используется со времени публикации книги Клини "Введение в метаматематику". рекурсивные определения сложения и умножения были использованы уже Дедекиндом в 1888 г. Гильберт использовал термин "рекуррентный" в 1905 г., а в 1923 г. употребляет уже термин "рекурсия". Сколем в своей программе обоснования математики в 1923 г. говорил о рекурсивном способе мышления и в техническом плане доказал примитивно-рекурсивный характер многих известных функций. в своей знаменитой статье о бесконечности 1926 г. Гильберт расширил сферу действия термина, говоря о более общих формах рекурсии с многими переменными. Аккерман в 1928 г. доказал, что это ведет к функциям, которые в современной терминологии не являются примитивно-рекурсивными. в своей известной статье 1931 г. Гедель точно определил функции, названные им "рекурсивными", для которых Петер в 1934 г. предложила название "примитивно-рекурсивных". в переписке 1931 г. с Геделем Эрбран предложил определение общерекурсивных функций. Гедель развил его предложение в своей лекции в Принстоне в 1934 г. Клини придал термину более удобную форму, используя терминологию Петер для более узкого класса функций

Гильберт хотел решить проблемы, связанные с бесконечностью посредством доказательств непротиворечивости такими методами, которые избегают бесконечности. при подобном подходе бесконечность может быть свободно допущена в математику. но финитизм понимается и более "скромным" образом. так, Тейт полагает, что финитизм состоит в ограничении математических методов и формализмов примитивно-рекурсивными функциями. есть и другие понимания финитизма, среди которых следует отметить отождествление его с конструктивистскими тенденциями

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

например, с точки зрения компьютерных программ особая значимость примитивно-рекурсивных функций состоит в том, что эти функции есть точно те программы, которые не имеют команды "GOTO"

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

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

вводится новый символ функции, скажем, φ, и соответствующая функция определена двумя уравнениями. в простейшем случае эти уравнения таковы:

      φ (1) = а
      φ (n + 1) = ψ (φ (n), n)
здесь а есть цифра и ψ есть функция, которая образуется из уже известных функций через композицию, так что ψ(b,c) могут быть вычислены для данных цифр b и c, и дает другую цифру в качестве значения

сразу и не понять, какой смысл может быть приписан этому методу определения

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

        пусть m будет некоторая цифра
        если m = 1, пусть m приписывается цифра а
        в противном случае m имеет форму b + 1
            схематически пишется: ψ (φ (b), b)
        теперь, если b = 1, можно заменить φ (b) на а
        в противном случае b опять имеет форму с + 1
        тогда φ (b) заменяется на φ (φ (с), с)
        опять либо с = 1 или же с имеет форму d + 1
        в первом случае φ (с) заменяется на а
        а в последнем - на ψ (φ (d), d) 

повторение этого процесса в любом случае оканчивается. потому что цифры b, c, d, ... которые мы получаем друг за другом, развиваются через диссемблирование цифры m, и это должно закончиться точно так же, как заканчивается ассемблирование m. когда мы прибываем к 1 в этом процессе диссемблирования, тогда φ(1) заменяется на а; знак φ больше не фигурирует в результирующей фигуре. скорее, единственный оставшийся символ функции, возможно, в множественной суперпозиции, есть ψ, а его внутренние аргументы есть цифры. таким образом, мы прибываем к вычислимому выражению, потому что предполагается, что функция ψ уже известна. таким образом, вычисление должно производиться изнутри наружу, и цифры, получаемые таким образом, будут приписаны цифре m