3

I’ve been looking for some time for a book that rigorously builds up arithmetic from basic axioms, like the Peano axioms for example, and ends up showing why our classic algorithms for additions, subtraction, multiplication and division, the ones learned in primary school, work. So far the only arithmetic books I’ve been able to find limit themselves to stating the steps of the algorithms (for addition, first align the numbers such that their rightmost digits concur, then add up each digit individually and carry if necessary), or they don’t even mention the algorithms such as this book, which is really nice and shows properties of arithmetic operations such as commutative law, but doesn’t show the correctness of the algorithms typically used to perform such operations. How can we know that the algorithms produce the desired result? I’m looking for a book that answers this question in a rigorous way. Here is an example of what I mean. Thanks in advance!

Bill Dubuque
  • 272,048
zlaaemi
  • 1,037
  • 2
    It might be in some computer science books about algorithms (as in data structures and algorithms) or computer hardware design. Maybe it’s in Knuth’s Art of Computer Programming books somewhere. – littleO Jul 10 '22 at 17:49
  • 1
    Please, don't give us links! If you have a question, ask it. That said: a book founding digital expansions on Peano axioms would have quite a few pages, most of them rather boring. Or did your "classical" mean Roman numerals? There were algorithms for arithmetic with those. – wasn't me Jul 10 '22 at 17:51
  • To multiply $73$ by $59$, you can do $73 \times (50 + 9) = 73 \times 50 + 73 \times 9$, and so on. You can probably convince yourself that the standard algorithm to multiply by hand is just breaking down the problem like this. Similar explanations could be given for other algorithms like long division. – littleO Jul 10 '22 at 17:53
  • It's not exactly what you are asking for, but J.P. Serre's A Course in Arithmetic is wonderful. Aspire to master it, instead of the Peano axioms and so on. – kimchi lover Jul 10 '22 at 18:20
  • @wasn'tme FYI: The term "Classical Algorithms" is specifically used for the rules of performing arithmetic on positional number systems, that is, conventional arithmetic that you learned in grade school starting at around the age of 5 or 6 or around then, depending on where you live in the world. Nothing to do with Roman numerals, which there is very little reason for teaching nowadays beyond their existence and how to represent them. – Prime Mover Jul 10 '22 at 18:37

3 Answers3

3

Two different things going on here.

Treatment of the Peano axioms is very much in Fundamentals of Mathematics, which often starts with axiomatic set theory and works towards the establishment of the rules of commutativity and associativity. There are many such books on this, although all take the subject slightly differently from every other such book. Perhaps you would get on with Keith Devlin's "The Joy of Sets".

The "classical algorithms", on the other hand, are a different thing altogether. By this time, the construction of the standard number systems, along with commutativity and associativity, are already assumed to be proven.

What we are now about is the exercise of arithmetic on numbers expressed in basis representation form (i.e. a string of digits whose values depend on the position in the string). This is the stuff which you learn at age 6. Not so many books on this. As suggested in a comment, Knuth covers them in detail in his The Art Of Computer Programming Volume 2: Seminumerical Algorithms, Chapter 4 - Arithmetic: 4.3.1 The Classical Algorithms.

Prime Mover
  • 5,005
0

I would check out Set Theory: The Structure of Arithmetic by Hamilton and Landin. I love this book. They define addition formally and prove the addition tables and all the usual properties of addition. Unfortunately they do not go into algorithm, but I think you will find the content very enlightening and interesting. It’s very close to what you are looking for I believe.

user1035015
  • 77
0

I'd recommend Understanding Numbers in Elementary School Mathematics by Hung-Hsi Wu. Be sure to reference the errata listing on Wu's website.

blargoner
  • 2,968