# Playing Sudoku

([home](https://github.com/alexhkurz/introduction-to-numbers/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/SkABF8ajI) ... [next](https://hackmd.io/@alexhkurz/S1xSrvwjL))

In a previous [sessions](https://hackmd.io/@alexhkurz/r1Gdg_EoU) we used a computer program to check that the table

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3|0
| 2|3 |0 |1
| 3|0| 1|2

satisfies the laws of an addition, or, to be more precise, that the operation defined by the table, written as $+$ for convenience,

- is associative: $x+(y+z)= (x+y)+z$
- has a neutral element: $0+x=x+0=x$
- has inverses: for all $x$ there is a number $-x$ such that $x+(-x)=0$ and $-x+x = 0$
- is commutative: $x+y=y+x$

In mathematical parlance, the table represents an **abelian group**. Here group refers to the first three axioms and abelian means that the group is commutative.

Moreover we have seen already that the existence of inverses means that in the table of a group in each row each element appears exactly once. Let us prove this.

(A lemma is an auxiliary useful result, a stepping stone to where you want to go.)

**Lemma:** In the table of a finite group, each column contains each element exactly once.

*Proof:* Assume that an arbitary column $x$ contains the same element $a$ in two different rows $y$ and $z$. Check that this means
\begin{align}
y+x & = a \\
z+x & = a \\
y & \not = z
\end{align}

It follows $y+x=z+x$ and taking $-x$ on both sides yields $y=z$. Hence any element $a$ can not appear twice in a column. It now follows from finiteness that it must appear exactly once. QED

**Exercise:** Reformulate the proof to show that every *row* contains each element exactly once.

**Exercise:** It always pays in mathematics to list exactly the assumptions needed for an argument. Which axioms of a group did we use in the proof of the lemma?

We can use this lemma to show that the table above is the only one with $1+1=2$. Let us start.

It works like a sudoku.

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | |
| 2| | |
| 3|||

We pick a square, say $1+2$ and think about what happens when we fill it in. Can we have the $1+2=0$:

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | **0** |
| 2| | |
| 3|||

No, because then we must also have (why?)

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | **0** | 3
| 2| | |
| 3|||

contradicting the lemma that no column can contain the same element twice.

Now, as we do for Sudoko, if we know that something is impossible, we may draw some postivie conclusions. For example, here we know that $1+2=3$

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3 |
| 2| | |
| 3|||

after which we can fill in

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3 | 0
| 2| | |
| 3|||

and (why?)

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3 | 0
| 2|3 | |
| 3|0||

Note how each step is either directly based on an axiom or on a conclusion drawn from the axioms.

Next, we have two possibilities for $2+2$. If we try $2+2=1$ we get

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3 | 0
| 2|3 | 1 | 0
| 3|0||

again contradicting the lemma. So all we have left is

|0| 1| 2| 3|
|:---:|:---:|:---:|:---:|
| 1 |2 | 3 | 0
| 2|3 | 0 | 1
| 3|0| 1 | 0

This table does not contradict the lemma. But that does not mean that we are finished.
Unlike in a Sudoku, we still need to check that all axioms are satisfied, but this we can easily do with the program.