Induction and recursion II May 28, 2008

Formal logic provides examples of structures that allow proof by induction, but not necessarily definition by recursion. Let us consider, for example, the propositional logic that is apparently due to Łukasiewicz. We first define the (well-formed) formulas of the logic. We start with some set of so-called propositional variables. Then the set of formulas is the smallest set of strings that contains these variables and is closed under certain formation rules, namely:

1. the singulary operation converting a string S to its negation, ~S;
2. the binary operation converting a pair (S, T) of strings to the implication, (S → T).

The set of theorems of the logic is the smallest set of formulas that contains all of the axioms and is closed under a certain rule of inference. The axioms are the formulas of any of three forms:

1. (F → (G → F))
2. ((F → (G → H)) → ((F → G) → (F → H)))
3. ((~F → ~G) → (G → F))

Here F and G stand for formulas. The rule of inference is detachment (or modus ponens), the binary operation that converts a pair (F, (F → G)) of formulas into the formula G. As stated, this is only a partial operation; we can make it total by having it convert (F, H) to F whenever H does not have the form (F → G) for some formula G.
The “inductive” definition of theorems is thus similar to the inductive definition of formulas. In each case, we start with a set and close under one or more operations. Immediately, proof by induction is possible on the set so defined. For example, we can prove inductively that each formula features as many left as right brackets. A feature of theorems that is proved by induction will be given in a moment.
However, unlike the formation rules for formulas, our rule of inference for theorems is not obviously well-defined. To see that it is well-defined, we must establish “unique readability” of formulas, namely:

1. each formula is exactly one of the following: a variable, a negation, or an implication;
2. the formation rules are injective.

Here injectivity of the formation rules corresponds to injectivity of the successor-operation on the set of natural numbers. The partition of the set of formulas into variables, negations, and implications corresponds to the partition of the set of natural numbers into the successors and the initial number (zero or one, as one prefers).
Unique readability of formulas allows recursive definitions. Indeed, the definition of the rule of detachment can be understood as recursive: If we denote this operation by D, then we have

1. D(F, P) = F for all propositional variables P;
2. D(F, ~G) = F;
3. D(F, (F → G)) = G;
4. D(F, (H → G)) = F if H is not F.

Another example of a recursively defined function on formulas is a truth-assignment. Consider the set {true, false} as the two-element field {1, 0}. Given a function φ from the set of propositional variables into the this field, we have a unique function Φ on the set of all formulas that agrees with φ on the variables, that takes ~F to 1 + Φ(F), and that takes (F → G) to 1 + Φ(F) + Φ(F)Φ(G).
By induction, every theorem takes the value 1 under every truth-assignment. But the truth-assignment is not recursively defined on the set of theorems: it is recursively defined on the set of formulas. Since the rule of detachment is not injective, we do not automatically have recursively defined functions on the set of theorems.
As far as I know, we do not have an efficient algorithm to determine whether a given formula is indeed a theorem: this lack of an algorithm would appear to be connected to the non-injectivity of the rule of detachment. A formula carries within itself the method of its construction; but a theorem does not carry within itself its proof, and indeed it will have infinitely many proofs.

The Border of Kingdom May 4, 2008

I bring my apologies for a Russian text quoted below — I promise to try to find an English translation, but so far I failed in my quest. This fable by Roerich came to my mind when I started to think about David Pierce’s induction/recursion opposition in terms of practicalities of “black box” computing in a very big residue ring with modulus of unknown prime decomposition (and this is a VERY practical issue since it is a setup for the RSA cryptosystem). As David Pierce observed, a standard recursion scheme for exponentiation is inconsistent on finite rings like .

What is a black box calculation? I’ll give you a toy example concerned with the RSA setup. Assume that you are given a calculator which has only buttons for digits, two operations , and return . To make it worse, the calculator returns the answers modulo for a very large — and unknown to you — number which is a product of two very large primes which are also unknown to you. On the bright side, you can save any number of intermediate results in the memory and re-use them. To guide yourself through the labyrinth of modular arithmetic, you can do auxiliary calculations with a pencil on paper.

I make a (semi-mathematical) claim that, playing with such a calculator for the rest of your life, you will never notice inconsistency in the recursive definition of exponentiation. Also, if has 100 digits, the calculator will be quite usable for many everyday needs.

My argument is based on a semi-philosophical premise that calculations (no matter how clever they are) with unknown modulus are in effect random manipulations with buttons with known .

But to find a random concrete instance of inconsistency of exponentiation in , that is, natural numbers and such that means getting at least a 1/4 chance to factorise and thus break the RSA scheme based on modulus : this is the probability with which is even and

.

Notice that  we can compute by a square-and-multiply method. Now let us repeat a trick from Simmons’ attack on (a lousy implementation of) RSA:

hence ,

and, computing (with a pencil on paper, using Euclid’s algorithm) the greatest common divisors of and , we easily find and — which exactly means to break the scheme.

I am pleased to say that David Corfield’s quest for instances of when the infinite is simpler is answered in this simple example in a stronger form: sometimes, infinite is not just simpler, it is safer.

What follows is Nicholas Roerich‘s fable The Border of Kingdom:

Н.К. Рерих

ГРАНИЦА ЦАРСТВА

В Индии было.

Родился у царя сын. Все сильные волшебницы, как знаете, принесли царевичу свои лучшие дары. Самая добрая волшебница сказала заклятие:

Не увидит царевич границ своего царства.

Все думали, что предсказано царство, границами безмерное.

Но вырос царевич славным и мудрым, а царство его не увеличилось.

Стал царствовать царевич, но не водил войско отодвинуть соседей.

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

В волнах облачных устилались новые дали. Клубились облака высокими грядами.

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

Вот три ненавистника старые зашептали:

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

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

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

Три ненавистника, три старые повели царя на высокую гору. Только перед вечером достигли вершины, и там все трое сказали заклятие. Заклятие о том, как прекратить силу:

Бог пределов человеческих!

Ты измеряешь ум. Ты наполняешь реку разума земным течением.

На черепахе, драконе, змее поплыву. Свое узнаю. На единороге, барсе, слоне поплыву. Свое узнаю. На листе дерева, на листе травы, на цветке лотоса поплыву. Свое узнаю.

Ты откроешь мой берег! Ты укажешь ограничение! Каждый знает, и ты знаешь! Никто больше. Ты больше. Чары сними.

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

Отвратили лицо ненавистники. Поклонились.

Вот, царь, граница твоя.

Но летела уже от богини доброго земного странствия лучшая из волшебниц.

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

Полетело над градом огневое воинство. Заиграли знаки самые премудрые.

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

1910