Search This Blog

Wednesday, February 03, 2010

Recursive roots

Here is a (wildly) speculative consequence of what I'm saying:

There's a relationship between inductive mathematical proofs and recursion - recursive functions can have their values determined by a definite finite algorithm, and by demonstrating that a function is recursive we are demonstrating that such an algorithm exists (whether or not it is practicable).

Inductive proofs depend upon the induction axiom in formalisations of arithmetic. By showing that zero has a certain property, and that the successor of any number with this property must also have it, we show that all numbers have it. This is an axiom of arithmetic (and it needs to be formaly stated in a way which avoids talk of 'properties'). The 'numerical' root of induction - zero - is also defined axiomatically as the cardinality of the empty set. Many proofs for the whole of arithmetic must depend upon this inductive principle, and its stipulated root.

It is this formalised arithmetic - which establishes induction and zero as axiomatic - which can represent axiomatic systems and theorem generation in general and so its own axiomatisation a` la Gödel.

If I have the right picture of a natural language, then the recursive roots of empricial demonstration will comprise the statements which must be true for the language - and so for argument - to be possible. These roots are not arbitrary, though, since they appear directly as statements about the possibility of language and argument (which cannot be rendered 'formally' - i.e. stripped of semantic content).

Could we write down a specification for a 'naturalised' arithmetic which took the possibility of arithmetic and of computation as its recursive roots, rather than a specific set of (semi-arbitrary?) generative rules?

Some might say: but these rules just are arithmetic. No conception of arithmetic is possible without them.

Maybe this is a place where we are deceived by our intuitions. Can we ask questions like 'Is arithmetic fundamentally about counting, about succession?' or 'Is arithmetic fundamentally about computation, about argument?'. And we have reasons for thinking a certain kind of computation (algorithmic, recursive) goes along with the possibiltiy of counting, of enumeration.

Suppose, however, that we started with a different number: not the cardinality of the empty set, but the Gödel representation of the statement that there is some statement x such that x is a theorem of arithmetic. On the face of it, this does not require completeness, but it does require consistency (since otherwise ~x would also be a theorem). This number must exist in any arithmetic (I think?), and must allow the generation of other numbers (or it wouldn't be arithmetic?) in a way similar to the way zero and succession work in Peano arithmetic.

The value of x (and so also its representation) is a function of the axiomatic system and rules selected, and the coding system used to Gödelise them (as Chaitin's Omega number is a function of the actual structure of the machine it describes). This is true of the theorems of arithmetic generally, of course, but these depend upon a definition of zero that is not open to further interpretation, that 'has no semantic content'.

(Maybe we should think of the value, representation, and 'meaning' of zero as being generated by the rules and coding system as well. But zero is also a word in our natural langauge...)

Anyhow: If there is some number which is the code for a statement that there is some theorem of arithmetic (in the syntax of the axiomatisation that is being encoded), then is that number (or its isomorphs in differently coded and axiomatised, but 'semantically equivalent' systems ... can this make any sense?) a candidate for a general recursive root for a 'natural' arithmetic?

Could its 'existence' be more 'necessary' than the unique cardinality of the empty set?

No comments: