Sunday, August 03, 2008

Short note on Wittgenstein and Church

In the Tractatus, Wittgenstein gives a definition of number as the exponent of an operation. In something I read recently, although for the life of me I cannot figure out what it was, the author pointed out that the basic idea in the Tractatus is the same as that of Church numerals. The definition of number in TLP has seemed somewhat obscure to me in the context of the TLP, so this comparison helped clarify things. The definition of number in TLP comes at 6.02. Lets call the basic operation S and name an element x. The number 0 is x, 1 is Sx, n is Snx and n+1 is SSnx. While not in lambda notation, this is fairly close to Church's definition for addition.

Together with some of Michael Kremer's remarks on Tractarian views of math, it makes the TLP seem concerned with computation as opposed to just structural concerns, which one would expect of something in the broadly logicist vein. (This may not be fair to all logicists. There did not seem to be a comparable concern with computation in Frege or Russell. The distinction I'm using here is the one drawn by Jeremy Avigad between math as a theory of structure and of computation in his "Response to Questionnaire" on his website. Although, Avigad points out that before the 20th century mathematicians were concerned with computational aspects of proof more than structural.) In Russell's preface to the TLP, he criticizes Wittgenstein's definition of number for not being able to handle transfinite numbers. If computation is supposed to be an important theme in the TLP, then this would not be bad. The transfinite numbers would not be the sort of thing that we would be computing with recursively. An interesting historical question is whether there were any reviews written of Church's work which pointed out that his definition only worked for finite numbers, echoing Russell's criticism of the TLP. Since the TLP was written before Church's, Turing's or Goedel's work on computability made it a more precise mathematical notion, it seems likely that it would remain implicit in the book rather than being made explicit as a main theme.


N. N. said...

Don't know anything about Church, but here is a paper that (judging by the title) may be of interst:

Noam said...

> An interesting historical question is whether there were any reviews written of Church's work which pointed out that his definition only worked for finite numbers, echoing Russell's criticism of the TLP.

That's an interesting question, but the criticism itself is incorrect. It is possible to define transfinite numbers by augmenting the definition of Church numerals. Church and Kleene did this in Formal Definitions in the Theory of Ordinal Numbers. The basic idea is to represent limit ordinals as (lambda-calculus) maps from Church numerals to Church numerals. There is a short description here (non-free link).

Shawn said...

The article looks like it could be good. I don't know how much it bears on this topic, but I have been wanting to read something on Wittgenstein's thoughts on Turing.

The summary you linked to was good. It is clear that Russell's criticism wouldn't be a good criticism of Church. I don't think there is an abstraction function in TLP, so it might still have some bite on Wittgenstein, if it was a good criticism originally. There might be another way to do the same thing in the notation of TLP. Was the unaugmented definition of Church numerals published or known before the definition extended to transfinite numbers? I'm not familiar with Church's work except insofar as others have told me about it.

Noam said...

I just read Russell's criticism, and don't think it's a criticism so much as pointing out future work. He writes that TLP's theory of number "as it stands, is only capable of dealing with finite numbers", but also, "I do not think there is anything in Mr Wittgenstein's system to make it impossible for him to fill this lacuna [of transfinite numbers]." The same could have been said about Church numerals before the Church-Kleene paper (I am not sure what the history was there), but also about any representation of the natural numbers, before it is extended to the ordinals.