Number Systems and Arithmetic

We spend a lot of time in school learning about numbers and arithmetic, and your concept of what a number is changes. But one thing that is always there is that you can do arithmetic. What unifies all of these is that we can "do" addition and multiplication, which means that, in any of these number systems, any two numbers can be added or multiplied together and we get another number in the same system. 
	Ask students: What about subtraction in these systems?  What about division?

Integers - our starting point

Briefly explain that mathematicians distinguish between "axioms", i.e. the things we have to just accept as true, and the consequences, the things we can prove as true by deducing them from the axioms. They try to find the smallest set of axioms and deduce as much as possible from them. We are not going to really do that, but we should set our our "axioms" so we know what properties need proving vs. what properties we just accept.

Obviously you all know a lot of things about the integers, here are the things we will start with the fact that we can do arithmetic (whatever that means). There are some other things (like < and the way there is nothing between 1 and 0) that make the integers different from other number systems in which we can "do" arithmetic, which we will see later.

  1. Rings - number systems that allow us to really "do" arithmetic We can do arithmetic with the integers (and $\mathbb{Q}$,$\mathbb{R}$, $\mathbb{C}$ ), and mathematicians have put together a list of the fundamental properties required to do arithmetic, and any number system that has those properties is called a *ring*. To be able to really do arithmetic you need two binary operators, that we will call + and *, and they need to work individually and in combination in the following ways (recall that the equality properties all still apply, e.g. a=a, substitutivity of equality):
    1. addition properties - you know all these! (note: can write informally as well as in first-order syntax)
      1. associative $\forall x,y,z[ (x+y)+z = x+(y+z) ]$
      2. commutative $\forall x,y[ x+y = y+x ]$
      3. additive identity $\exists x [ \forall y[ x + y = y ]]$ ← Note: the counting numbers don't have this, so they are not a ring!
        Note: Take a second to read this axiom and recognize the identity of this mysterious $x$! Let's do existential instantiation and choose the name "0" for our new constant! This gives us ...
        additive identity (alternate version) $\forall y[ 0 + y = y ]$
        ACTIVITY
        The additive identity is unique.
        The way we usually prove that something is unique, i.e. that no other object has the property we are talking about, is to show that if two objects have the property, then they are equal. In this case, we will let x and z be arbitrary but fixed and show that if x and z are both additive identities, then x = z. 
        A1: ∀y[x + y = y] ∧ ∀y[z + y = y]  [Assumption A - i.e. assuming x and z both are "additive identitites"]
A2: ∀y[x + y = y]                  [and elimination on A.1]
A3: ∀y[z + y = y]                  [and elimination on A.1]
A4: x + z = z                      [specialization to y in A.2 to z]
A5: z + x = x                      [specialization to y in A.3 to x]
A6: z + x = x + z                  [ring axiom ii (def'n of commutativity of +) and specialization]
A7: x = z                          [subst. of equality on 6 using 5 and 4]
1: ∀y[x + y = y] ∧ ∀y[z + y = y] => x = z  [close assumption A]
        Since x and z are arbitrary but fixed, we deduce that for all x and z, if x and z are both additive identities, then x = z. Thus the addititive identity is unique.

        Note: Since we have $\exists x [ \forall y[ x + y = y ]]$ we can use existential instantiation to replace the variable $x$ with a new constant - just make sure it's a new name. We could call it "george", but let's call it 0 instead! Now we know that zero is unique! This means we can treat axiom 1.iii as stating ∀y[0 + y = y].

      4. additive inverse $\forall x[ \exists y[ x + y = 0 ] ]$ ← Note:the natural numbers don't have this, so not a ring!
        The additive inverse is unique. I.e. ∀x,y,y'[x + y = 0 ∧ x + y' = 0 => y = y'] 
        0:                              [let x, y and y' be arbitrary but fixed]
A1: x + y = 0 ∧ x + y' = 0      [Assumption]
A2: y + 0 = y + 0               [reflexivity of equality]
A3: y + (x + y) = y + (x + y')  [substitutivity of equality into 2 using the two equalities in 1]
A4: (x + y) + y = (x + y) + y'  [associativity and commut of +]
A5: 0 + y = 0 + y'              [substitutivity of equality on line 4 using the equalities in line 1]
A6: y = y'                      [by def of zero / additive identity]
1: x + y = 0 ∧ x + y' = 0 => y = y'           [close assumption]
2: ∀x,y,y'[x + y = 0 ∧ x + y' = 0 => y = y']  [arbitrary but fixed arguments become forall's]

        Note: This is a nice example of something that we don't make an axiom, because it is a consequence of the axioms (i.e. we can give a proof).
        Note: now we can say there is a function -(.) that takes an element as input and returns its (unique!) additive inverse as output. I.e. "-x is *the* additive inverse of x". This is, of course, the unary negation operator
        Note: write this proof on the board but after lines 0 and 1, do not give the justifications. Ask them to come up with the justifications as an exercise

        $\forall x,y[ x + y = y \Rightarrow x = 0 ]$ , i.e. there are no part-time zeros. 
        0:                           [Let x and y be arbitrary but fixed]
A1: x + y = y                [assumption A]
A2: y + -y = 0               [additive inverse]
A3: (x + y) + -y = 0         [substitutivity of equality into 2 using equation 1]
A4: x + (y + -y) = 0         [assoc of + in line 3]
A5: x + 0 = 0                [additive inverse applied to 4]
A6: x = 0                    [additive identity applied to line 5]
1: x + y = y => x = 0        [closing assumption A]
2: ∀x,y[x + y = y => x = 0]  [arbitrary but fixed arguments become foralls]
    2. multiplication properties - you know these too
      1. associative $\forall x,y,z[ (x*y)*z = x*(y*z) ]$
      2. commutative $\forall x,y[ x*y = y*x ]$ ← IMPORTANT! not required to be a ring, but is an axiom for integers!
      3. multiplicative identity - we have a constant called 1 such that $\forall x[ 1*x = x ]$ and $\forall x[ x*1 = x ]$ NOTE: if multiplication is commutative we only need the first one!
      4. (multiplicative inverse not required ... which is good since almost all integers do not have a multiplicative inverse!)
    3. How multiplication and addition interact
      1. distributivity: $\forall a,b,c[a*(b+c) = a*b + a*c]$ and $\forall a,b,c[(b+c)*a = b*a + c*a]$ NOTE: if multiplication is commutative we only need the first kind!
      4. PAUSE: now that addition and multiplication are connected, we can prove some things about multiplying by 0 and how -1 connects to addition:

      ∀z[z*0 = 0] and ∀z[0*z = 0]
      1: z*(0 + 0) = z*0 + z*0 [distributive property specializing a=z, b=0, c=0] 2: z*0 = z*0 + z*0 [additive identity applied to 1] 3: z*0 + z*0 = z*0 [symmetric property of equality () on line 3] 4: z*0 + z*0 = z*0 => z*0 = 0 [No part-time zeros () specializing x and y to z*0] 5: z*0 = 0 [Modus ponens on lines 4 and 3] ------ the other direction ----- 1: (0 + 0)*z = 0*z + 0*z [distributive property (2nd kind) specializing a=z, b=0, c=z] 2: 0*z = 0*z + 0*z [additive identity applied to 1] 3: 0*z + 0*z = 0*z [symmetric property of equality () on line 3] 4: 0*z + 0*z = 0*z => 0*z = 0 [No part-time zeros () specializing x and y to 0*z] 5: 0*z = 0 [Modus ponens on lines 4 and 3]
      Note: we know z is "arbitrary but fixed" so this really proves $\forall z[z*0 = 0]$ and that's really what this theorem is stating. But we no longer bother to say that explicitly.

      Recall from above, "-x" is how we denote the additive inverse of x.

      For all $x$, $-x = -1*x$. [Note: it is also true that $-x = x*-1$, though we don't prove the second version here.]
      0: (1 + -1)*x = 1*x + -1*x [distributitivity (2nd kind)] 1: 0*x = 1*x + -1*x [additive inverse] 2: 0 = 1*x + -1*x [] 3: 0 = x + -1*x [Mulitiplictive identity applied to line 2] 4: x + -1*x = 0 [symmetric property of equality] 5: x + -x = 0 [definition of additive inverse (not based on any previous line)] 6: x + -x ∧ x + -1*x [and introduction applied to 5 and 4] 7: x + -x ∧ x + -1*x => -x = -1*x [Uniquenes of additive inverse specializing x = x, y = -x, y' = -1*x ] 8: -x = -1*x [Modus ponens on 7 and 6]
      Note: We proved this for $x$ which is "arbitrary but fixed", i.e. a constant with no restrictions on it, so we've shown that the theorem holds "for all $x$".

Note: All of the theorems on this page apply to any ring. None of their proofs rely on multiplication being commutative or on the existence of multiplicative inverses.

Christopher W Brown