Now, you might say, there's that definition symbol that we haven't defined, right? Peano himself famously asked "How do you define a definition?" But Bengt thinks this is a stupid question, because obviously you don't. The definition symbol is not part of the system, it's outside the system, so it's fine.
We've also sort of skipped over the issue of precedence - unless of course you decided to deal with that in your answer to the last problem, in which case, good on you - but that's not a problem either, because we could just express "x+y" as "+(x, y)" instead, that is, use only prefix operators.
No, what Bengt has a problem with is all those variables. What is x? Well, it varies, obviously, that's kind of the point of variables, but Bengt is not happy with that. Also we're assuming that there are functions, which takes arguments, and all that. And what about all those definitions of numbers? That's a great many definitions, isn't it? So either we have to make an infinite number of definitions, or we're stuck writing numbers as s(s(s(s(s(...
Bengt would like to sort out all that stuff and make everything simple. In the new system, every rule has to contain an exact sequence of symbols on each side.
Decimal numbers would be a little cumbersome to define, so we might resort to binary - once we've got that down, it's easy enough to do the same with any other base. Alternatively, we could use unary numbers, which would probably make things even easier to define, but is a pretty messy way of writing numbers. Also, to make sure we know where a number starts and ends, we'll enclose them in brackets. So eleven is written as [1011] in binary, or [•••••••••••] in unary.
Furthermore, it's probably a good idea to write the operators prefix instead of infix, so we don't have to worry about precedence and parentheses and all that. So 1+1=2 could be written (in binary) as =+[1][1][10].
As a warm-up, we could start with logical expressions. We might define true and false as... oh, it doesn't matter, really, let's just say T and F. We can always define those as something else later. If we let for example the & symbol stand for "and" (which makes sense, since that's what it means) we could write
&TT:T
&TF:F
&FT:F
&FF:F
The trickiness appears of course when we want to deal with numbers, since we can't just spell out all possibilities. But that doesn't mean it can't be done. If we take our old pal the successor function, for example, it could be written (for unary) as
s[:[•
Now all that remains is to go from there to a complete arithmetic system, not using any variables or anything else that isn't a literal sequence of symbols.
- Define the "or" operator.
- Define addition for unary numbers. There are various ways, with or without using the successor function - feel free to try out more than one. Note that this function (and the others) should be able to handle any natural numbers.
- And multiplication.
- Define the successor function for binary numbers.
- Define addition for binary numbers.
- And multiplication.
- Define binary numbers in terms of unary. This obviously solves (e) and (f) automatically, so it's nice if you've got some other solution to those as well.
- What can't you do in this type of system that you can do in Peano's? You might want to look up "Peano's axioms" if you're not familiar with them.
Posts
