Set of Integers

The set of integers can be constructed from the Natural Numbers.

We can define the set of integers as the set NxN where "x" is the Cartesian Product.

In set theory, the Cartesian Product is the combination of all the elements of one set with all the elements of the other set forming pair.

So, if N = { 1, 2, 3 ... }, then NxN = { (1,1), (1,2), (1,3), ..., (2,1),(2,2), ..., }

Here is the definition for integers:

Definition 1: Set of Integers: Z is the set NxN where (a,b) is the same number as (c,d) if and only if a + d = b + c.

NOTE: Z stands for Zahlen which is German for number.

From this perspective, each number corresponds to the set of all values (a,b) where a-b is equal to the number.

So 0 for example corresponds to { (1,1), (2,2), .... }

And -1 corresponds to { (1,2), (2,3), ... }

We can use the definition to show that (1,1) ~ (2,2) in that 1 + 2 = 1 + 2.

From this, we can now define addition, multiplication, and subtraction.

Definition 2: (a,b) + (c,d) = (a + c, b + d)

Example:

-1 + -3 = (2,3) + (5,8) = (2+5,3+8) = (7,11) = -4

Definition 3: (a,b) * (c,d) = (ac + bd, ad+bc)

Example:

-1 * -1 = (1,2)*(1,2) = (1*1 + 2*2,1*2 + 2*1) = (1 + 4,2 + 2) = (5,4) = 1

-1 * 3 = (1,2)*(4,1) = (1*4 + 2*1,1*1 + 2*4) = (4 + 2,1 + 8) = (6,9) = -3

Definition 4: (a,b) - (c,d) = (a + d, b + c)

Example:

4 - 3 = (5,1) - (4,1) = (5 + 1, 1 + 4) = (6, 5) = 1

(-3) - (-5) = (2,5) - (1,6) = (2 + 6, 5 + 1) = (8, 6) = 2

3 - 4 = (4,1) - (5,1) = (4 + 1, 1 + 5) = (5,6) = -1

Definition 5: (a,b) is less than (c,d) if and only if a + d is less than b + c

Example:

-3 is less than 4 since (2,5) is less than (5,1) since 2+1=3 is less than 5 + 5=10.

Lemma 1: Z is closed under addition.

(1) (a,b) + (c,d) = (a + c, b + d)

(2) a + c is a natural number and b + d is a natural number (since addition is closed for natural numbers, see here)

QED

Lemma 2: Z is closed under multiplication

(1) (a,b) * (c,d) = (ac + bd, ad + bc)

(2) ac, bd, ad, bc are all natural numbers since N is closed under multiplication (see here)

(3) ac + bd, ad + bc are natural numbers since N is closed under addition (see here)

QED

Lemma 3: Z is closed under subtraction

(1) (a,b) - (c,d) = (a + d, b + c)

(2) a + d, b + c are both natural numbers since N is closed under addition (see here)

QED

Lemma 4: Z has 0 as the identity element for addition

n + 0 = (n+1,1) + (1,1) = (n + 2,2) = n

QED

Lemma 5: Z has 1 as the identity element for multiplication

n * 1 = (n + 1, 1)*(2,1) = (2*(n+1) + 1*1, (n+1)*1 + 2) = (2n + 3,n + 3) = n

QED

Lemma 6: Each element of Z has an inverse element for addition that is determined by reversing the pairs (b,a) is the inverse element for (a,b)

n + (-n) = (n+1,1) + (1,n+1) = (n + 1 + 1, 1 + n + 1) = (n+2,n+2) = 0

QED

Lemma 7: Z is commutative on addition: a + b = b + a

a + b = (a+1,1) + (b+1,1) = (a + b + 2,2)
b + a = (b+1,1) + (a+1,1) = (b + a + 2,2) = (a + b + 2,2) [Since natural numbers are commutative on addition, see here]

QED

Lemma 8: Z is commutative on multiplication: a*b=b*a

a*b = (a+1,1)*(b+1,1) = ((a+1)(b+1) + 1*1,(a+1)*1 + 1*(b+1)) =
= (ab + a + b + 1 + 1, a + 1 + b + 1) =
= (ab + a + b + 2,a + b + 2) = ab

b*a = (b+1,1)*(a+1,1) = ((b+1)(a+1) + 1*1,(b+1)*1 + 1*(a+1)) =
= (ba + a + b + 2, a + b + 2) =
= (ab + a + b + 2, a + b + 2) = ab [Since natural numbers are commutative on multiplication, see here]

QED

Lemma 9: Z is associative on addition

(a+b) + c = [(a+1,1) + (b+1,1)] + (c+1,1) = (a+b+2,2) + (c+1,1) = (a+b+c+3,3)=
= a+b+c

a + (b+c) = (a+1,1) + [(b+1,1) + (c+1,1)] = (a+1,1) + (b+c+2,2) = (a+b+c+3,3) =
= a+b+c

QED

Lemma 10: Z is associative on multiplication

(a*b)*c = [(a+1,1)*(b+1,1)]*(c+1,1)=
= [(a+1)(b+1) + (1)(1),(a+1)(1) + 1(b+1)](c+1,1) =
= (ab + a + b + 2, a+1+b+1)(c+1,1) = (ab+1,1)(c+1,1) =
= ((ab+1)(c+1) + (1)(1), (ab+1)(1)+(1)(c+1)) =
= (abc + ab + c + 1 + 1, ab + 1 + c + 1) =
= (abc + ab + c + 2, ab + c + 2) = abc

a*(b*c) = (a+1,1)[(b+1,1)(c+1,1)] =
= (a+1,1)((b+1)(c+1) + (1)(1),(b+1)(1)+(1)(c+1)) =
= (a+1,1)(bc + b + c + 1 + 1,b+1+c+1) =
= (a+1,1)(bc+b+c+2,b+c+2)=(a+1,1)(bc+1,1)=
= ((a+1)(bc+1) + (1)(1),(a+1)(1) + (1)(bc+1)) =
= (abc + a + bc + 1 + 1,a + 1 + bc + 1) =
= (abc + 1, 1) = abc

QED

Lemma 11: Z is distributive: (a+b)c =ac + bc.

(a+b)c = [(a+1,1)+(b+1,1)](c+1,1) = [(a + b + 2,1+1)](c+1,1) = (a+b+1,1)(c+1,1) =
= ((a+b+1)(c+1) + (1)(1),(a+b+1)(1) + (1)(c+1)) =
= (ac + bc +c + a + b + 1 + 1,a + b + 1 + c + 1) =
= (ac + bc + 1, 1) = ac + bc.

QED

References

• Integers, Wikipedia
• Integer, PlanetMath
• Integer, Dr. Noach Dana Picard's Page

Natural Numbers

The natural numbers are the numbers that are most familiar to us; they are the counting numbers that usually begin at 1 (some mathematicians hold that the natural numbers include 0). This also matches with the history of mathematics where the use of 0 was a major innovation.

The mathematician Kronecker once said:
"God made the natural numbers. Everything else is the work of man." (Quoted from here)

At the same time, this leads us to an interesting question. Is it possible to define the natural numbers in terms of a set of axioms similiar to what Euclid did for geometry?

The successful definition of natural numbers was done by two men: Richard Dedekind in his book What is a Number and the logician Guiseppe Peano. Today, these axioms are known as Peano's Axioms.

Here are a set of postulates based on Peano's Axioms:

I. The natural numbers is a set of numbers starting with 1 where each number has a unique successor which we will characterize by S(a) where a is a natural number.

II. All numbers but 1 have are themselves successors to a unique number.

III. a = b if and only if S(a) = S(b)

IV. If a property is possessed by 1 and possession by a value a implies it is also true of S(a), then we say it is true of all numbers. (Axiom of Induction)

Definition 1: m + n

m + 1 = S(m)
m + S(n) = S(m + n)

Example:

1 + 2 = S(1 + 1) = S(S(1)) = S(2) = 3

Definition 2: m * n

m * 1 = m
m * S(n) = m + (m * n)

Example:

2 * 2 = 2 + (2*1) = 2 + 2 = 4

Definition 3: m is less than n

m is less than n if there exists a natural number d such that m + d = n.

Definition 4: m - n

S(m) - 1 = m
S(m) - S(n) = m - n

If m is less than or equal to n, then it is undefined.

Lemma 1: Natural numbers are closed under addition.

(1) m+1 = S(m)
(2) Assume that there exists a value n such that m + n is a natural number.
(3) m + S(n) = S(m+n)
(4) Which must also be a natural number by Axiom I.

QED

Lemma 2: Natural numbers are closed under multiplication

(1) m*1 = m
(2) Assume that there exists a value n such that m * n is a natural number
(3) m*S(n) = m + (m*n)
(4) Which is a natural number by Lemma 1 above.

QED

Lemma 3: Natural numbers are not closed under subtraction.

m - n is undefined for the case where m ≤ n.

QED

Lemma 4: 1 + m = S(m)

(1) Case n=1:

1 + 1 = S(1)

(2) Assume that it is true up to n.

(3) 1 + (n+1) = 1 + S(n) = S(n+1)

(4) So, it is true by Axion IV.

QED

Lemma 5: Natural numbers are commutative under addition: m + n = n + m

(1) For case n=1:

m + 1 = S(m)

(2) From Lemma 4, 1 + m = S(m)

(3) Assume it is true up to n so that m+n=n+m

(4) m + (n+1) = m + S(n) = S(m+n)

(5) (n+1) + m = S(n) + m = S(n+m) = S(m+n)

(6) So, we apply Axiom IV and we are done.

QED

Lemma 6: 1*m = m*1

(1) 1*1 = 1*1

(2) S(m)*1 = S(m) [By Definition 2 above]

(3) 1*S(m) = 1 + m = m + 1 = S(m)

(4) We are done since all numbers are either 1 or a successor to another number. (by Axion II)

QED

Lemma 7: Distributive Law: (a + b)m = am + bm

(1) Case m = 1:

(a + b)1 = a + b [By Definition 2]

a(1) + b(1) = a + b [By Definition 2]

(2) So we assume that it is true up to n so that (a+b)n = an + bn.

(3) (a+b)S(n) = (a + b) + (a+b)n = a + b + an + bn = a + an + b + bn

(4) a(S(n)) + b(S(n)) = a + an + b + bn

(5) So by the Axiom of Induction we are done (see Axiom IV)

QED

Lemma 8: Natural numbers are commutative under multiplication: m * n = n * m

(1) Case n=1:

m * 1 = 1 * m [From Lemma 6 above]

(2) Assume that it is true up to n so that we have m*n=n*m

(3) m*(n+1) = m + mn [By definition 2]

(4) (n+1)*m = nm + m = m + nm = m + mn

(5) So we are done by the Axion of Induction (Axiom IV above)

QED

Lemma 9: Natural numbers are associative under addition:
(a + b) + n = a + (b + n)

(1) Case n = 1

(a + b) + 1 = S(a + b)

a + (b + 1) = a + S(b) = S(a + b)

(2) (a + b) + S(n) = S(a + b + n)

(3) a + (b + S(n)) = a + S(b + n) = S(a + b + n)

(4) It is true now in all cases since all numbers are either 1 or are a successor (by Axiom II above)

QED

Lemma 10: Natural numbers are associative under multiplication:
(a*b)*n = a*(b*n)

(1) Case n = 1

(a*b)*1 = a*b

a*(b*1) = a*b

(2) (ab)*S(n) = S(n)(ab) = (n+1)(ab) = abn + ab

(4) a*(b*S(n)) = a*(b*(n+1)) = a*((n+1)*b) = a*(bn+b) = (bn+b)*a = abn+ab

QED

References

• Peano Axioms, Wikipedia
• Peano Arithmetic, Planet Math
• Natural Numbers, Dr. Noach Dana Picard's Page