Associativity of addition

Question

This question is about addition of positive integers with more than one digit, a topic covered in second grade. But it's not really elementary.

But first we need to introduce the positive integers $\mathbb N$ the way a second grader conceives them. Of course they will not think of $\mathbb N$ as the set defined by the Peano axioms. Instead, we start with the 10 symbols $A=\{0,1,2,\ldots,9\}$ and we $\bf define$ a positive integer to be a finite string $a_na_{n-1}\cdots a_1a_0$ where each $a_i\in A$ (and they are not all zero). Then we define the operation of addition by the usual algorithm involving carries that is taught in second grade. Here is my question: prove that this operation is associative. Disclaimer: I know how to prove it, but surely my proof could not be explained to a second grader. I would like to know if there is a really elementary proof.

Answer 1

The addition algorithm involving carries should be a theorem, not a definition, even for a 2nd grader. Addition should be defined semantically, and the obvious way to do it at the 2nd grade level makes associativity obvious: if Alice, Bob, and Carol have $a, b, c$ apples, and they pool their apples together, they have $a + b + c$ apples.

I write this without parentheses because this operation does not involve any parentheses: "pool their apples together" is an $n$-ary operation that immediately makes sense without any reference to a binary operation. Other intuitive forms of counting and addition could be used here: for example, Alice, Bob, and Carol might be carrying three sticks of lengths $a, b, c$, and then I'd tell you to line those sticks up to produce a bigger stick of length $a + b + c$ (note that this makes commutativity a little less obvious). Or Alice, Bob, and Carol might be carrying three rocks of weight $a, b, c$, etc.

Then it is, again, a theorem that this operation reduces to binary addition, and that either parenthesization works. Alice, Bob, and Carol can pool their apples together either by having Alice and Bob pool their apples together first, then Carol, or by having Bob and Carol pool their apples together first, then Alice. This gives

$$a + b + c = (a + b) + c = a + (b + c)$$

as desired. The point of presenting the argument this way is that $(a + b) + c$ and $a + (b + c)$ are equal because they are equal to a third operation, which is "add three things." Other associativity arguments in mathematics can be written to work exactly the same way (e.g. associativity of the tensor product).

Answer 2

(Extending my comment into an answer)

I would like to argue that the difficulty lies in the way integers are defined, not in associativity by itself.

Young children conceive integers first as a property of real life objects: their cardinal. They learn to count by enumerating objects; and enumeration is the essence of $\mathbb{N}$.

In math language we call "property" an equivalence class, and we formalize enumeration by various means, e.g. the successor function used in Peano axioms.

Children have an immediate understanding of enumeration, and of the sequence of integers. They do not have an immediate understanding of base-$10$ encoding. That comes soon, because the name of integers reflects this encoding after some language-dependent limit (typically $10$ or $16$ or $20$). But enumeration comes first.

Actually, the very fact that we write math sentences on a sheet of paper has a prerequisite: the sheet of paper enables to put symbols one after the other, as many as we want. So enumeration comes even before axioms. This is also true when using a proof assistant such as Coq or Agda or Lean: one relies on a virtually infinite enumeration of memory cells. And this is also true of the infinite sequence of cells in the Turing machine.

So which encoding of integers reflects the most this intuitive concept of enumeration? Unary encoding, the unary numeral system. Which is: an integer is encoded into as many $1$'s; $5$ is encoded as $11111$.
This is what we use when counting things one by one; I remember doing that in a vote place, before we got voting machines. We count with sticks.

This uses the definition of integers as cardinal of objects sets. And the good thing is: in this encoding, addition is obvious (that's just appending two sets of $1$'s), as well as commutativity and associativity.

(By the way, I learned to use unary encoding in complexity theory; this is explained in the Wikipedia page).
A drawback of unary encoding is that zero cannot be represented without a separate symbol (unless using blank space to represent an empty set of $1$'s, which is akward).

There is a well-known argument that groups are so important in maths and physics because they represent actions, and actions in real life are associative and have a neutral element (i.e. doing nothing). By having a very limited kind of actions (appending sequences of $1$'s) we rely on that.

On the other hand, base-$10$ encoding is difficult to use, for the reasons you mention: addition is a nightmare to define and to prove its properties.

There are other drawbacks to using base-$10$ encoding as a definition of integers:

• That gives too much importance to one encoding among many; i.e. one can use other bases, notably base-$2$.
• There are other encodings which do not follow this principle of making packets of $N$, $N^2$, $N^3$ etc. objects.
• "Why can't I put a leading zero?" is a frequent question; with unary encoding this question does not exist.
• This problem repeats itself when defining real numbers. The layman definition of a real number is an integer followed by a comma followed by a finite or infinite sequence of digits. Which poses the same problem of defining addition and multiplication and their properties, plus the non-uniqueness of encoding.

So the easiest way to define integers with addition and its properties for second graders, in my opinion, is to:

• Define integers as a property of objects sets - putting objects visually in bijection, i.e. saying their number is the same if you can make pairs of objects and there is none left in either set.
• Defining addition as grouping two sets together.
• Showing visually that this is obviously commutative and associative.
• Showing unary encoding as an example of such sets.
• Then defining base-$10$ encoding.
• Showing (if you feel this is necessary) that each base-$10$ encoded number has a unique unary encoded representant, and the other way round.
• Deriving addition for base-$10$ encoding from addition of sets of $1$'s. Then addition properties that have already been proven in unary encoding are transferred into base-$10$ encoding (which actually uses an intuitive property of bijections).

The last two steps are the most difficult ones, but I believe they are less difficult, and more intuitive, than doing all the work with base-$10$ encoding from the beginning.

All that being said, perhaps you just have to define integers by their base-$10$ encoding because that is officially prescribed in the place where you teach.