Chapter 3

Introduction to Axioms,

Mathematical Systems,

Arithmetic,

The Peano Axioms,

and Mathematical Induction.

§ 3.1 BASIC RATIONALE FOR AXIOMS AND AN INTRODUCTION TO MATHEMATICAL SYSTEMS.

The theories of arithmetic, geometry, logic, sets, calculus, analysis, algebra, number theory, etc. were developed by many different mathematicians over centuries, but reached a rigorous level by the nineteenth and early twentieth centuries. A group of mathematicians at the University of Göttengen in Germany undertook the task of attempting to reduce the concepts in various fields to the simplest statements they could possibly assume such that the theory of a designated area must follow from said assumptions.

They took their example from Euclid and his series of books, Elements, in which Euclid proposed or collated proposals such that certain assumptions were made about geometry which all other facts about geometry could be deduced from those assumptions. Indeed, if memory serves me correctly (I will check and not rely solely on my rather imperfect memory) Euclid’s fifth postulate was proposed but was not stated such that it was necessarily a postulate. He included it in the list so that it could be considered and left it to others to determine if indeed it was a postulate (something that had to be assumed) or followed from the other postulates. The fifth postulate was that for every line l and every point p not lying on l there exists a line m containing p such that m is parallel to l.[1]

The Germans were led by the mathematician, David Hilbert, and worked fervently on questions of axiomatics (as well as other things). They were known as reductionists for they were attempting to reduce the mathematical claims of the time to rigorous systems. Another great mathematician, George Boole, also worked on such questions. It is not to be assumed that such investigations met with universal acclaim, indeed Bertrand Russell and others thought the exercise rather ridiculous. They thought there was a need to study logic in its pure form and forgo such endeavours. Other mathematicians and logicians thought both the school to which we consider Russell a member, the logicians, and Hilbert, the axiomaticians, were wrong and that mathematics should be considered from an intuitive perspective. Such intuitionists as Kurt Gödel viewed mathematics as art. Thus, the discussion of the basic rationale for axiom systems does not imply that there is but one way to view mathematics, but we are in this course considering and examining mathematics from an axiomatic perspective.

The axiomatic approach to sets, logic, analysis, etc. is one of the most impressive accomplishments of modern mathematics. Concepts which were vague or indistinct took on the property of clarity. Precise meanings replaced quasi-definitions. Adequate axioms established the foundation of modern mathematics for they provided clear, unambiguous, and understandable premises for theories which before were sound but people didn’t know why they were sound.

This is not to say that the original work of mathematicians was always without its problems. Around the turn of the twentieth century, Bertrand Russell proposed a construction which allowed for a paradox to be derived from the axioms system of the day proposed for set theory. There was an axiom, called the ‘axiom’ of abstraction, proposed by Frege which stated that given any property there exists a set whose members are those entities. Russell defines a set such that it was the set of all things which have the property of not being members of themselves. Suppose there was a universal ‘set.’ Let us call it U. Let us call Russell’s ‘set’ R. Now, what is R? R = {S Î U : S Ï S}. Now, the rub! Does R belong to itself?

Suppose R Î R. Then since R Î R, it must be the case that R Ï R! Which is (of course) a contradiction.

Suppose R Ï R. Since R Ï R, it must be the case that R Î R! Which is (of course) a contradiction.

So, the absolutely hideous situation exists such that R Î R Û R Ï R! So, the ‘set’ the set of all sets (the idea of a universal ‘set’) cannot exist. This of course, implies that the ‘axiom’ of abstraction is not an axiom of set theory (unfortunately for Frege, but fortunately for us).

This should illustrate for you, the reader, that one can call something a rule, a definition, an axiom, a postulate, a theorem, a lemma, or a corollary but that does not mean it is. It can only be such under the conditions that the axioms must be consistent (e.g.: they do not contradict each other) and all else follows from the axioms.

Nonetheless, it has been shown in the twentieth century that no system is compleat. So, one must pay careful attention to the axioms. Careless claims made that are intuitively appealing but are not derived from the axioms cannot be allowed.

Now recall that with a logic claim from chapter one that we proved we began by declaring what we were assuming (the premises) and deduced that the conclusion followed from those premises. We may have used a direct argument or indirect; but the important point is that the conclusion was derived from the premises. Note the premises did not contradict each other (so they were consistent) for if any subset of the set of premises were inconsistent, then we could not deduce a conclusion (since F Þ T is true and F Þ F is true.

Likewise, each branch of mathematics starts with a set of premises - - assumptions that are to be agreed are going to be assumed. These premises are the postulates or axioms[2]. Statements deduced from these assumptions are lemmas, theorems, or corollaries while the processes of deduction leading to these statements are the proofs themselves. Examples, definitions, and illustrations adjoin the lemmas, theorems, and corollaries in order to illuminate the concepts, to illustrate the principle, or to create new ideas.

The basic rules of language that is employed is the syntax whilst the meaning assigned to the symbols, words, etc. are the semantics of the language. We have already introduced much of the mathematical syntax in chapter one and two and we have introduced many of the semantics of logic and set theory in those chapters. Each branch of mathematics has its peculiarities (I warn you) - - so there is not necessarily a semantic standard. For example, in real analysis a function is defined from a set to another such that the first set is termed the domain and the second set is termed the codomain. The subset of the codomain that has associated with it at least one element of the domain is called the range. However, in probability theory, the first set for a probability function is termed the range. This should illustrate for you that whenever reading a math text find the glossary, index, and list of abbreviations and mark them! What one may think is the standard use of a symbol is not - - there really is not a standard.

Before each area of mathematics is discussed, acceptable syntactic and semantic rules must be adopted and one must understand the syntax and semantics in order to have any hope of understanding the area. When one notes that | C | = | R | = À₁ and that | N | = | Z | = | Q | = À₀; that À₀ + 1 = À₀; whilst À₁ > À₀; hence, | I | = À₁ one needs an understanding of relations, sets, functions, and cardinality in order to understand transfinite arithmetic. Indeed, if one were to switch to ordinality and not the transfinite ordinal equation w₀ + 1 > w₀ one can be truly confused by this (and hopefully you are; for if you are not then you should not be in this class - - for you know too much to waste time in this introductory level mathematics class). Hopefully this illustrates the idea that there is a language that is mathematics and that it is an exciting field with truly remarkable ideas that one can learn and master; but that it is a building process that leads us to these really astonishingly beautiful ideas. One cannot run before one walks and one cannot walk before one crawls. You, the student, have passed the crawling stage and are in the walking stage; so please do not be impatient and imprudent and try to run before walking; but I digress.

The first component of many axiom systems is the notion of atoms. Atoms (or primitive statements) are the undefined terms that are agreed to. For example in Euclidean geometry these atoms would be: there exist a point, a line, and a plane. A point has no dimension, a line has one dimension, and a plane has two dimensions. You should note that these atoms are used in many fields besides geometry and are some of the basic building blocks of mathematical thought.

A set of axioms is consistent if and only if it is impossible to deduce a statement and it logical opposite (e.g.: an axiom system is consistent Û one cannot deduced P Ù ØP for some statement P).

For us, this is an important point because if a set of axioms is inconsistent, then it is of no use to us.

Finally an axiom system needs a set of rules of inference so that theorems, examples, counter-examples, lemmas, and corollaries may be deduced from the axioms and definitions may be created to define terms, ideas, etc. Thankfully, for our studies the basic rules of inference of propositional and syllogistic calculus (logic) are the rules used in classical mathematics.

In principle any set of consistent axioms can be studied, but the choice of axioms that we oft study (especially in a rigorous undergraduate mathematics curriculum) is not chosen in a capricious manner. Recall the discussion of the Göttengen mathematicians, they were central to much of modern mathematics because they attempted to reduce down to the axiomatic level the practical, useful, applied, and pure mathematics of the day in order to better understand that which was being claimed was true or false and to find the justification for things like calculus, topology, algebra, etc.

Mathematical theories are now understood to follow from axiom systems so that by deductive reasoning the theorems, examples, counter-examples, lemmas, and corollaries can be proven based on said axioms. Definitions are presented to clarify ideas, terms, etc. Consider the foundation of the system is the set of axioms; thus, the theory literally and figuratively is built upon that foundation. If the foundation be shoddy, then the theory collapses. So there is great import in ensuring the system is consistent, the syntactic rules are sound, and the rules of inference are understood and properly executed, so that proofs and counterexamples are not possibly correct, maybe so, or any other nonsensical relativistic term but are declaratively true or false.

Example 3.1.1: Let U = {a, b, g, d, e, w}. Let A = {a, b, g, d}. Let ‘#^’ be the operator such that an element of A ‘#^’ another element of A is defined by table 3.1.1. The operation is pound; so we ‘pound’ two elements together. The elements of the universe are alpha, beta, gamma, delta, epsilon, and omega respectively. Hence, the reader can determine the elements of A. The operation pound is called a binary operation since it associates pairs of elements of A.

The elements are ‘pounded’ by reading the first column as the first element and the pound at the top of the first column and in the first row then reading the second element as the entry in the first row then follow the specified row and column to see what the elements ‘pounded’ together results.

#	a	b	g	d
a	a	b	g	d
b	b	g	d	a
g	g	d	a	b
d	d	a	b	g

Table 3.3.1 (A, #)

Note that we did not define pound for all elements of the universe. Hence, there is no understanding as to what pound might do with an element of A and A^C or two elements of A^C.

Note further that a # b is b, b # a is b, g # d is b, and d # g is b. Let us examine this rather rudimentary mathematical system for its basic properties.

Note that whenever two elements are pounded together in A the result is a unique element in A. So, there is one and only one result when two elements of A are pounded together. So, this is an algebraic concept know as closure. The set A is closed under the binary operation pound. Inspection of the table suffices to prove that this claim is true. If one were to prove the claim that A is closed under pound, then a method of proof that will suffice is the method of exhaustion. This is because A is a finite set so that we need only make 16 observations ( observations). Please note that the method of exhaustion is not a valid method to prove that N is closed under ‘+’ in ordinary arithmetic since N is an infinite set (more on this later).

Definition 3.1.1: A system (S, ã) is closed if and only if given the binary operation ã together with a pair of elements of S associates a unique element of S with the that pair of elements.

Note that when two elements, x and y, of A are pounded together the result is the same as when y and x are pounded together. Once again we can use the method of exhaustion to prove this claim. Note that we used the variables x and y to denote arbitrary elements of the set A rather than any of the specific symbols a, b, g, or d. This is because we are trying to discuss the general truth that when two elements of A are pounded together the result is the same as when they are pounded in opposite order rather than a specific example of such like, beta pound gamma is delta and gamma pound beta is delta. So we say that # is a commutative or abelian operation on A when

x # y = y # x " x, y Î A.

Definition 3.1.2: An operation ã on a set S (for the system (S, ã)) is commutative if and only if given the binary operation ã together with a pair of elements of S the order of the pair of elements does not matter, that is to say that element one operated (ã) with element two is the same as element two operated (ã) with element one.

Note further that when three elements, x, y, and z, of A are pounded together the result is the same no matter the order. That is to say that x # y # z = (x # y) # z = x # (y # z) no matter what x, y, and z are in A. Once again we can use the method of exhaustion to prove this claim. Note that we used the variables x, y, and z to denote arbitrary elements of the set A rather than any of the specific symbols a, b, g, or d (even though there are but four elements in A). So we say that # is an associative operation on A when

x # y # z = (x # y) # z = x # (y # z) " x, y, z Î A.

Definition 3.1.3: An operation ã on a set S (for the system (S, ã)) is associative if and only if given the binary operation ã together with any three elements of S the order of the execution of the operation does not matter, that is to say that element one operated (ã) with element two then that result operated (ã) with element three is the same as element two operated (ã) with element three first, the result of which when operated (ã) with element one yields the same result.

Note another interesting property that (A, #) exhibits. There is an element such that that element pounded with any element yields the element. That unique element is a. Notice a # b = b, a # d = d, and a # a is a (do not forget that it must be true for itself). We say that a is the identity element of A for the operation # on A. For a general definition consider:

Definition 3.1.4: An element x of the set S with the operation ã on S (for the system (S, ã)) is called the identity element if and only if given the binary operation ã together with any element y in S it is the case that x ã y = y ã x = y.

Note for (A, #) we only needed to check the left operation (such as a # b is b) since we already noted that # was commutative on A. Indeed note that a # x is x and x # a is x " x Î A.

So, the identity is a particular element that operates on every element in the set such that the operation with it ‘changes nothing.’

Finally let us consider that there are other interesting elements in the system (A, #). That is easily proven using the method of exhaustion since a # b is b, g # g = a, and a # a = a . We say that the elements x and y are inverses with respect to # when x # y = y # x = a (the identity element). For a general definition consider:

Definition 3.1.5: An pair of elements x and y of the set S with the operation ã on S (for the system (S, ã)) are called inverse elements of each other with respect to ã if and only if given the binary operation ã together with x and y it is the case that x ã y = y ã x which results in the identity element.

Note for (A, #) we only needed to check the left operation (such as d # b is a) since we already noted that # was commutative on A. Further notice that the definition of inverse elements was contingent on there being an identity. So, the definition of inverse elements would make no sense if there was not an identity.

Example 3.1.2: Let U = Z. Let us consider N. Let ‘–^’ be the operator such that it is standard subtraction. So we define x – y to be the normal difference between to natural numbers. Note that (N, – ) is not closed since 3 Î N, but 3 – 3 = 0 Ï N. Note (N, – ) does not have an identity. So, inverses under subtraction are out of the question. Note that – is not a commutative binary operation for N. Also, notice that – is not an associative binary operation for N since

13 – (2 – 5) does not exist for N but (13 – 2) – 5 is well defined for the natural numbers and is 6.

Example 3.1.3: Let U = Z. Let us consider Z. Let ‘–^’ be the operator such that it is standard subtraction. So we define x – y to be the normal difference between to integers. Note that (Z, – ) is closed. Note (Z, – ) has an identity, 0. Indeed, subtractive inverses exist. Note, however, that – is not a commutative binary operation for Z. Also, notice that – is not an associative binary operation for Z since 13 – (2 – 5) = 13 – (-3) = 16 but (13 – 2) – 5 = 6.

So, when we compare and contrast examples 3.1.2 and 3.1.3 we see that the set can make an important contribution to the discussion of mathematical systems. So too can the operation for consider the following example:

Example 3.1.4: Let U = Z. Let us consider Z. Let ‘+^’ be the operator such that it is standard addition. So we define x + y to be the normal sum of integers. Note that (Z, + ) is closed. Note (Z, + ) has an identity, 0. Indeed, additive inverses exist. Note that + is a commutative binary operation for Z. Also, note + is an associative binary operation for Z.

So, when we compare and contrast examples 3.1.2, 3.1.3, and 3.1.4 we see that not only the set but the operation is very important to consider. Slight changes in either the operation or the set can cause each of the five properties discussed to be true or false, but not both. Note that for clarity we used the vernacular, ‘true or false but not both’ to properly represent Ú .

There are other definitions that are generalisations of the standard properties of the real numbers that can be noted. However, considering just the five properties here gives you, the student, the exposure to and the experience with abstract mathematical systems that is needed at this stage of your development. This is not to say that you, the student, cannot delve further into this topic if you are interested; it is merely to say that the subject will be expanded to include other operations, sets, and mathematical systems as your mathematics studies progress.

§ 3.1 EXERCISES.

1. Prove that # from example 3.1.1 is commutative on A.

2. Prove that # from example 3.1.1 is associative on A.

3. Define the following on U from example 3.1.1:

#	a	b	g	d	e	w
a	a	b	g	d	e	w
b	b	g	d	a	w	e
g	g	d	a	b	d	b
d	d	a	b	g	b	d
e	e	w	d	b	a	g
w	w	e	b	d	g	a

A. Prove or disprove that U is closed under #.

B. Prove or disprove that # is commutative on U.

C. Prove or disprove that # is associative on U.

D. Prove or disprove that there exists an identity under # in U.

E. Prove or disprove that there exists an inverse for a in U under the operation #.

F. Prove or disprove that there exists an inverse for b in U under the operation #.

G. Prove or disprove that there exists an inverse for g in U under the operation #.

H. Prove or disprove that there exists an inverse for d in U under the operation #.

I. Prove or disprove that there exists an inverse for e in U under the operation #.

J. Prove or disprove that there exists an inverse for w in U under the operation #.

4. Let U = M such that M = {V, X, d}. Define the binary operation ê on M so that

ê	V	X	d
V	d	V	X
X	V	X	d
d	X	d	V

A. Find V ê V. H. Is it the case that V ê X = X ê V ?

B. Find V ê X. I. Is it the case that (V ê X) ê d = V ê (X ê d) ?

C. Find V ê d. K. Is it the case that (X ê d) ê V = X ê (d ê V) ?

D. Find d ê X. L. Is there an inverse element for d in M under ê ?

E. Find d ê V. M. Is there an inverse element for X in M under ê ?

F. Is there an identity element for ê in M ?

G. Is it the case that (d ê V) ê X = d ê (V ê X) ?

5. Let U = Z. Let us consider Z. Let ‘Ä^’ be the operator such that it means, ‘if the two integers are the same select the number and if the two numbers are not the same select the lesser of the two numbers.’ So we define x Ä y to be x if x = y [or y if one so desires], x Ä y to be x if x < y, and

x Ä y to be y if x > y.

A. Compute 5 Ä 3. H. Is Z closed under Ä? Justify your response.

B. Compute 3 Ä 3. I. Does there exist an identity for (Z, Ä)? Justify.

C. Compute 5 Ä 5. J. Is Ä a commutative operation in Z? Justify.

D. Compute 3 Ä 3. K. Is Ä an associative operation in Z? Justify.

E. Compute (-5) Ä 3. L. Does there exist an inverse for each x Î Z under Ä? Justify.

F. Compute 5 Ä (-3).

G. Compute (-5) Ä (-3).

6. Let U = Z. Let us consider N. Let ‘Ä^’ be the operator such that it means, ‘if the two natural numbers are the same select the number and if the two numbers are not the same select the lesser of the two numbers.’ So we define x Ä y to be x if x = y [or y if one so desires], x Ä y to be x if x < y, and x Ä y to be y if x > y.

A. Compute 5 Ä 3. H. Is N closed under Ä? Justify your response.

B. Compute 3 Ä 3. I. Does there exist an identity for (N, Ä)? Justify.

C. Compute 51 Ä 15. J. Is Ä a commutative operation in N? Justify.

D. Compute 3 Ä 3. K. Is Ä an associative operation in N? Justify.

E. Compute 1 Ä 3. L. Does there exist an inverse for each x Î N under Ä? Justify.

F. Compute 5 Ä 13.

G. Compute 4701 Ä 4701.

7. Let U = Z. Let us consider Z. Let ‘Å^’ be the operator such that it means, ‘select the integer before the sign.’ So we define x Å y to be x.

A. Compute 5 Å 3. H. Is Z closed under Å? Justify your response.

B. Compute 3 Å 3. I. Does there exist an identity for (Z, Å)? Justify.

C. Compute 5 Å 5. J. Is Å a commutative operation in Z? Justify.

D. Compute 3 Å 3. K. Is Å an associative operation in Z? Justify.

E. Compute (-5) Å 3. L. Does there exist an inverse for each x Î Z under Å? Justify.

F. Compute 5 Å (-3).

G. Compute (-5) Å (-3).

6. Let U = Z. Let us consider N. Let ‘Å^’ be the operator such that it means, ‘select the natural number before the sign.’ So we define x Å y to be x.

A. Compute 5 Å 3. H. Is N closed under Å? Justify your response.

B. Compute 3 Å 3. I. Does there exist an identity for (N, Å)? Justify.

C. Compute 51 Å 15. J. Is Å a commutative operation in N? Justify.

D. Compute 3 Å 3. K. Is Å an associative operation in N? Justify.

E. Compute 1 Å 3. L. Does there exist an inverse for each x Î N under Å? Justify.

F. Compute 15 Å 3.

G. Compute 4301 Å 4701.

§ 3.2 SOME FUNDAMENTAL AXIOM SYSTEMS.

The theories of arithmetic, geometry, logic, sets, calculus, analysis, algebra, etc. are all fundamentally supported by an axiom system. In some areas of mathematics, the axioms overlap to produce a tapestry of great detail that produces some very interesting results.

On the other hand, each individual area has its own nomenclature; definitions; theorems; etc. so caution is advised - - one should carefully review the foundations of a mathematical area and not assume that terminology that one is familiar with is used in the way in which he has become familiar.

A brief perusal of a statistics text would give a student a clear exposition of statistics, but he might be under a cloud of misunderstanding if he read the sentences: “Let X be a binomial random variable with parametres n and p such that n Î N and p Î (0, 1). So, n defines the range of the probability mass function is discrete,” and thought, for example, that random and variable were redundant, that (0, 1) referred to a point in the plane, or that range means the analytic range from the concepts of domain, codomain, and range. Understanding statistics requires a strong foundation in analysis, algebra, probability theory, and set theory since it is an interdisciplinary off-shoot of mathematics. Indeed, a working knowledge of programming is helpful to apply the theory of statistics.

However, as is the case with most mathematics, a cursory understanding of the subject allows many to delve into the subject. One can then use technology to derive solutions to problems that might not ordinarily be easily obtained. Then inferences can be derived from the solutions which however pleasing or intuitively appealing are dead wrong and can cause mistakes, errors, confusion, etc.

It is the academic’s responsibility to not fall into said trap. It is his responsibility to study an area of academia unencumbered with pre-concepts, notions, or biases. For if the search for knowledge is not entered into through the spirit of truth, honesty, honour, and curiosity, then how can one ever obtain knowledge, understanding, or - - one hopes - -wisdom?

So, we enter into an area free of pre-concepts, but demand that the axioms system we develop or study be consistent. One such example of a fundamental axiom system is the axioms of the real numbers. Recall from chapter two that the reals, R, are the set of all points on the line and have graphical representation:

¬¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾®

Recall there is no centre (e.g.: the nonsense about ¥ + (-¥) = 0) so the line is:

¬¾¾¾¾¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾¾¾® or

-4 -3 -2 -1 0 1 2 3 4

¬¾¾¾¾¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾|¾¾¾¾® or

-p -3 10 20 40 60 1,000 10²⁰

The axioms define the relationship between the points and define the binary operations addition and multiplication on the reals. They allow us to deduce many advanced properties of the reals that are not necessarily true but are only conditionally true dependent on the truth of the axioms. So, in essence, the axioms of the reals are exemplary of that people which once thought were self-evident truths. However, there is no intrinsic truth to the axioms; they are but axioms that are generally considered of use and are generally agreed to.

Axiom Set 3.2.1: Let U = R.. The field axioms[3] are:

Axiom 1 (closure of addition): " x, y Î R, x + y Î R and (x = w Ù y = v) Þ (x + y = w + v).

Axiom 2 (commutative of addition): " x, y Î R, x + y = y + x..

Axiom 3 (associative of addition): " x, y, z Î R, (x + y) + z = x + (y + z).

Axiom 4 (existence of identity of addition): $ a unique number 0 ' x + 0 = x " x Î R.

Axiom 5 (existence of additive inverse): " x Î R $ a unique number -x ' x + (-x) = 0.

Axiom 6 (closure of multiplication): " x, y Î R , x × y Î R and (x = w Ù y = v) Þ (x × y = w × v).

Axiom 7 (commutative of multiplication): " x, y Î R , x × y = y × x.

Axiom 8 (associative of multiplication): " x, y, z Î R, (x × y) × z = x × (y × z).

Axiom 9 (existence of identity of multiplication): $ a unique number 1 ' x × 1 = x " x Î R

where 1 ¹ 0.

Axiom 10 (existence of multiplicative inverse): " x Î R ' x ¹ 0 $ a unique number

' x × () = 1.

Axiom 11 (distributive of multiplication over addition): " x, y, z Î R , x × (y + z) = (x × y) + (x× z).

Algebraists (of whom I am not one) study sets that have these properties and not that if the set along with two binary operators satisfy these axioms for that set, then the set is said to be a field (hence the terminology field axioms of the reals). Such systems will be studied in Math 371 and 372 (Abstract Algebra I and II). For now, it suffices to note that the student should have been exposed to these axioms prior to entry in college and convinced himself of their apparent veracity.

Axiom Set 3.2.2: Let U = R. The order axioms are:

Axiom 12 (trichotomy): " x, y Î R , exactly one of the following relationships exists between x and y :

x < y, x = y, Ú x > y. [meaning that (x < y) exor (x = y) exor (x > y)].

Axiom 13 (transitivity of “<”): " x, y, z Î R , [ (x < y) Ù (y < z)] Þ (x < z).

Axiom 14 (preservation of order under addition): " x, y, z Î R , (x < y) Þ (x + z < y + z).

Axiom 15 (preservation of order for positive multiplier): " x, y Î R , [(x < y) Ù (0 < z)] Þ

(x × z < y × z).

The order axioms establish the relationship between points and axiomatised the important principle that two distinct points occupy different geometric locations (the trichotomy), that order is transitive, that order is preserved under addition, and that order is preserved for a positive multiplier. Note that the theorem that order is reversed for a negative multiplier need not be assumed - - it can be proven based on these axioms!

Furthermore, that 0 ¹ 1 is all we assumed from the field axioms. So, we can prove certain established truths about some of the relationships with numbers that most students believe are true but have not proved are true. For example the fact that that 0 ^. 0 = 0, 0 ^. x = 0 where x is any real, 0 < 1, and other titbits based on the field axioms and the order axioms.

Claim 3.2.1: 0 ^. 0 = 0 .

Proof: Let U = R. Assume the field axioms and order axioms of the reals. Consider that 0 is a unique real number by the axiom of additive identity. Let x be a real number. Note that x + 0 = x by the axiom of additive identity. But, x + 0 = 0 + x by the axiom of additive commutativity. So,

0 + x = x by transitivity of equality. Now, 0 ^. (0 + x) = 0 ^. x by preservation of equality (closure) under multiplication. So, 0 ^. 0 + 0 ^. x = 0 ^. x by the distributive axiom of multiplication over addition. Now, note 0 ^. 0 = b for some real number b since R is closed under multiplication[4].

Also, since R is closed under multiplication this means that 0 ^. x = a for some real number a.

So, we have 0 ^. 0 + a = a by substitution.[5] Since a Î R , -a exist and is real by the axiom of the additive inverse. So, we know that 0 ^. 0 + a + (-a) = a + (-a) by the preservation of equality under addition. However, that means that 0 ^. 0 + (a + (-a)) = a + (-a) by the associativity of addition. Note that a + (-a) = 0 by the axiom of the additive inverse. So, we have 0 ^. 0 + (a + (-a)) = 0 Þ

0 ^. 0 + 0 = 0. Recall that 0 ^. 0 was b, so we have b + 0 = 0 by substitution. But the axiom of additive identity requires that b + 0 = b. So, by the transitivity of equality note that b = 0. Hence, 0 ^. 0 = 0.

QED

I am certain that there is a shorter more elegant and pleasing argument that establishes the veracity of 0 ^. 0 = 0. However, as stated in the previous chapters the object of mathematics at this level (or any level if one inquires as to my opinion) is not elegance by correctness. Try to create arguments which are true and blast the elegance!

Since the claim is true, let us state it as a lemma (a small theorem, recall, that helps prove a ‘bigger’ result subsequently):

Lemma 3.2.1: 0 ^. 0 = 0 .

Let us consider another ditty that many people believe is a definition but is not.

Claim 3.2.2: 0 ^. x = 0 " x Î R .

Proof: Let U = R. Assume the field axioms and order axioms of the reals. By the existence of the additive identity axiom, 0 exists. Note that -0 is 0 since 0 has an additive inverse. We have already established 0 ^. 0 = 0 so, let x be a real number (meaning x Î R ) where x ¹ 0. Note that 0 ^. x is a real number since the reals are closed under multiplication (meaning it exists) so $ c Î R

' 0 ^. x = c. Note that (-c) is also a real number by the axiom of the additive inverse.

Consider that 0 ^. x = (0 + 0) ^. x . Now, 0 ^. x = (0 ^. x) + (0 ^. x) by the distributive axiom of multiplication over addition (and commutativity since the axiom was stated for multiplication on the left). But 0 + 0 ^. x = 0 ^. x by the axiom of the additive identity. So, we have

0 + 0 ^. x = (0 ^. x) + (0 ^. x). Thus, 0 + c = c + c. Now we can say that this implies that

0 + c + (-c) = c + c + (-c). But addition is associative so, 0 + c + (-c) = c + c + (-c) Þ

0 + (c + (-c)) = c + c + (-c) Þ 0 + (c + (-c)) = c + (c + (-c)) Þ 0 + 0 = c + 0 Þ 0 = c.

Since c = 0 ^. x we finally note that it must be the case that 0 = 0 ^. x Þ 0 ^. x = 0.

QED

Since the claim is true, let us state it as a theorem:

Theorem 3.2.1: 0 ^. x = 0 " x Î R .

Claim 3.2.3: (-1) ^. x = -x " x Î R .

Proof: Let U = R. Assume the field axioms and order axioms of the reals. By the existence of the multiplicative identity axiom, 1 exists. By the additive inverse axiom, (-1) exists. Now let x be a real number. By the additive inverse axiom, (-x) exists.

Consider that the reals are closed under multiplication, so $ d Î R ' (-1) ^. x = d . Now we know that d = d; so, (-1) ^. x = (-1) ^. x. Consider x + (-1) ^. x = x + (-1) ^. x because equality is preserved under addition. But, x = 1 ^. x .

So, 1 ^. x + (-1) ^. x = x + (-1) ^. x. Since multiplication over addition is distributive, we have

(1 + (-1)) ^. x = x + (-1) ^. x. But 1 + (-1) = 0; so we have 0 ^. x = x + (-1) ^. x.. However, by theorem 3.2.1, we therefore have 0 = x + (-1) ^. x.. Now, the axiom of the additive inverse states that the additive inverse is unique; so since –x is the additive inverse of x it therefore follows

that –x = + (-1) ^. x..

QED

Since the claim is true, let us state it as a theorem:

Theorem 3.2.2: (-1) ^. x = -x " x Î R .

Claim 3.2.4: 0 < 1.

Proof: Let U = R. By the existence of the additive identity axiom, 0 exists. By the existence of the multiplicative identity 1 exists. Also, 0 ¹ 1 by the same axiom. Now by the trichotomy axiom exactly one of the following relationships exists 0 < 1 or 0 = 1, or 0 > 1.

Case 1: 0 = 1. But 0 ¹ 1. Hence, we have a contradiction. So, this cannot be the case.

Case 2: 0 > 1. Now, 1 has an additive inverse, (-1), which is unique by the axiom of additive inverses. So, 1 + (-1) = (-1) + 1 = 0 since addition is commutative.

Consider 0 > 1 Þ 0 + (-1) > 1 + (-1) by the preservation of order under addition. Nonetheless,

0 + (-1) = (-1) + 0 since addition is commutative, and by the existence of additive identity axiom, we therefore know that 0 + (-1) = -1. So, 0 > 1 Þ 0 + (-1) > 1 + (-1) Þ (-1) + 0 > 1 + (-1) Þ

0 + (-1) > 1 + (-1) Þ (-1) > 1 + (-1) Þ (-1) > 0. So, (-1) is a positive number; meaning that

0 < (-1). Now, let us consider that 1 < 0 and 0 < (-1). Applying the axiom of preservation of order for a positive multiplier where x = 1, y = 0, z = -1 yields 1 ^. (-1) < 0 ^. 0. Since multiplication is commutative, we have (-1) ^. 1 < 0 ^. 0. By lemma 3.2.1 we therefore know that (-1) ^. 1 < 0.

But by the axiom of the multiplicative identity (-1) ^. 1 = -1. So, -1 < 0. However, we also

have 0 < -1. So, -1 < 0 Ù 0 < -1 which is a contradiction of the trichotomy axiom; so, this cannot be the case.

So, we must conclude 0 < 1.

QED

Since the claim is true, let us state it as a corollary (a small theorem, recall, that follows from some ‘bigger’ result):

Corollary 3.2.1: 0 < 1.

There is a host of other results that one might view as ‘trivial’ but are in fact important results of field and order axioms of the reals such that when we were young we considered them ‘given’ but are in fact results that are proven based on the axioms. As such they need not be assumed (which is not to say that many don’t assume them[6]) they are deduced from the axioms. So, they rely on the axioms but are different than the axioms insofar as the axioms are those statements assumed to be the case that are not deduced from other statements.

Now, there is yet another axiom of the reals that is of import. That is the completeness axiom. It is very useful in analysis. We shall not define the terms in this axiom; we shall simply note that it is an axiom that will be used and results of which shall be studied in Math 361 (Real Analysis I). If you have an inkling as to the definition of boundedness and supremum, fine, that is not our concern at this stage of our mathematical development.

Axiom 16 (completeness): " A Í R ' A is bounded above $ a number m which is the supremum of the set

Recall in chapter two we discussed some basic notions of sets, properties of sets, Venn diagrammes, etc. Our treatment of sets was (to say the least) elementary. However, the subject was developed with a naïveté that was purposeful. In the theory of methods of teaching (the edu-speak term is pedagogy), one perspective is called constructivism. That is to say that the student should construct the ideas through his work. I do not adhere to said method, but liberally borrow from it from time to time when prudence and experience dictate. To study in an expository manner sets axiomatically is not the best way (in my opinion, though I lean somewhat toward the axiomatic side of methods of teaching arguments); it seems most students learn the theory of sets better by first getting some applied experience then studying the subject in a deep vertical manner later.

Nonetheless, the axioms exist. To leave you hanging in thin air to ‘develop’ them on your own might be an interesting exercise; but would be time-consuming and might not yield the desired result of the student learning to apply set theoretic concepts to algebra, analysis, probability, etc. Hence, we shall note the axioms, discuss a couple of the axioms, and leave it at that.

Axiom Set 3.2.3: Let U be a well defined universe. Let A, B, and C be sets of elements from that universe. The axioms of set theory[7] are:

Axiom 1 (The Axiom of Extension) Two sets are equal iff they have the same elements.

Axiom 2 (The Axiom of Null) There exists a set with no elements, call it Æ.

Axiom 3 (The Axiom of Pairing) Given any sets A and B, there exists a set C whose elements are A and B.

Axiom 4 (The Axiom of Union) Given any set A, the union of all elements in A is a set.

Axiom 5 (The Axiom of Power Set) Given any set A, there exists a set B consisting of all the

subsets of A.

Axiom 6 (The Axiom of Separation) Given any set A and a sentence p(a) that is a statement for all

a Î A, then there exists a set B = {a Î A: p(a) is true}.

Axiom 7 (The Axiom of Replacement) Given any set A and a function f defined on A,

the image f(A) is a set.

Axiom 8 (The Axiom of Infinity) There exists a set A such that Æ Î A, and whenever

a Î A, it follows that a È {a} Î A.

Axiom 9 (The Axiom of Regularity) Given any non-empty set A, there exists an a

such that a Ç A = Æ.

Axiom10 (The Axiom of Choice) Given any non-empty set A whose members are

pairwise disjoint non-empty sets, there exists a set B consisting of

exactly one element taken from each set belonging to A.

Now, notice the axiom of extension is a convenient way to describe a set so that the concept of U = N (or any set but let us use this example) means that if one were to say that A = {1, 2, 3} was a set and B = {2, 1, 3} was a set; it can be determined by the axiom of extension that naming them two different things does not imply that they are different!

Note the axiom of null; its existence is axiomatic. One can study[8] other systems of set theory that, for example, do not admit the axiom of null. So, one can readily opine that A Ç A^C presents a problem. In actuality it is not so difficult for A Ç A^C to not exist in such a system.

The other axioms are decidedly more complex and sublime so we shall leave the discussion of those for a later course. Let us instead consider another axiom system, the axioms of probability.

Axiom Set 3.2.4: Let U be a well defined universe from set theory. Rename the universe S and call it a sample space. Let E, E_i , F, etc. be sets of elements from that sample space such that

E, E_i , F, etc. will be called events. The axioms of probability[9] are:

Let S denote the sample space, E, E_i , F, etc. events and the notation Pr(·) the probability

of whatever [the dot is a dummy for an event].

Axiom 1 S is the space Þ Pr(S) = 1.

Axiom 2 E is an event Þ 0 £ Pr(E) £ 1.

Axiom 3 Let I be an index set. The collection being mutually exclusive

Þ =

Note that there are definitions that should be clearly delineated before the discussion of the axioms. For example, we did define sample space and event, but not mutual exclusivity. Two events are mutually exclusive iff their intersection is null. One must also define summation, function, etc. for compleat understanding of these axioms. One should clearly realise that the axioms of probability rest heavily on the reader’s understand of sets. I dare say that most upper division course-work relies on a clear, unambiguous, and full understanding of logic and sets. They are the tools that assist the student in mastering upper-level mathematics.

We shall return to these axioms later in the course when we discuss introductory probability and statistics. We will use them and in so doing (hopefully) a better understanding will develop as to their importance and utility.

§ 3.3 A BIT OF FORMAL NATURAL ARITHMETIC.

Imagine that we are children and we are learning about mathematics. Would we first discuss calculus? Of course not; that would be preposterous. We would begin with the natural numbers and arithmetic. We would conceive of 1, 2, 3, and so forth. We would then begin to understand things like 1 and 1 is 2. Later we would be introduced to 1 + 1 = 2 and be instructed that ‘+’ signifies the concept of ‘and’ (probably thinking of one and one apple makes two apples, I suppose) whilst the ‘=’ means the verb ‘is.’ We would memorise addition and multiplication tables, then develop subtraction, division, the rational numbers, etc. That is how our ‘numerical sense’ was probably developed, refined, and enhanced. But we are not children, so let us discuss the natural numbers in a more rigorous way.

Axiom Set 3.3.1: Let U = N.

Axiom 1 (closure of addition): " x, y Î N, x + y Î N.

Axiom 2 (commutative of addition): " x, y Î N, x + y = y + x.

Axiom 3 (associative of addition): " x, y, z Î N, (x + y) + z = x + (y + z).

Axiom 4 (axiom of identity): " x Î N, x = x.

Axiom 5 (axiom of substitution): " x, y Î N, x = y Þ y = x.

Axiom 6 (axiom of transitivity of equality): " x, y, z Î N, (x = y Ù y = z) Þ x = z.

Axiom 7 (preservation of equality): " w, x, y, z Î N, (x = w Ù y = z) Þ (x + y = w + z).

One can prove simple theorems based on these axioms. For example consider the following theorem:

Theorem 3.3.1: If x, y, and z are natural numbers, then (x + y) + z = (z + x) + y.

Proof: Let U = N. Assume axiom set 3.3.1. Let x, y, and z be natural numbers.

Consider (x + y) + z. By the axiom of closure of addition x + y Î N. So, it is some natural number. Hence that natural number plus z is also a natural number by the closure of addition axiom. Now, we know that (x + y) + z = x + (y + z) by the axiom of associativity.

By the axiom of commutativity, x + (y + z) = x + (z + y).

By the transitivity of equality we know that (x + y) + z = x + (z + y).

By the axiom of associativity we know x + (z + y) = (x + z) + y.

By the transitivity of equality we know that (x + y) + z = (x + z) + y.

By the axiom of commutativity, (x + z) + y = (z + x) + y.

By the transitivity of equality we know that (x + y) + z = (z + x) + y.

So, we must conclude (x + y) + z = (z + x) + y.

QED

Other trivial theorems can be deduced from the axioms. It is important to realise however, that the reasoning used is sound and that when we do something as trite as the following:

7

5

+ 6

18

we are implicitly using the associative and commutative axioms!

Note the first three basic axioms of (N, +) [just a fancy way of saying the natural numbers with addition). Do they hold for subtraction? In other words consider the following ‘axioms;’ are they axioms (e.g.: must we assume them) and are they even true?

‘Axiom’ 1 (closure of subtraction): " x, y Î N, x - y Î N.

‘Axiom’ 2 (commutative of subtraction): " x, y Î N, x - y = y - x.

‘Axiom’ 3 (associative of subtraction): " x, y, z Î N, (x - y) - z = x - (y - z).

Note that axiom 4, 5, and 6 do not explicitly mention addition. Hence, do they hold for subtraction? Why or why not? Finally, what of axiom 7?

The section on formal arithmetic will be expanded in subsequent semestres. However, for now it should be clear as to the nature of our discussion. Much is assumed but does it really have to be assumed or is it that we have not elucidated the reasons behind our actions?

§ 3.3 EXERCISES.

1. Name the axiom or axioms that justify the following.

A. 7 + 11 = 11 + 7.

B. 6 + (7 + 5) = (6 + 7) + 5.

C. 6 + (7 + 5) = 7 + (6 + 5).

D. Let x and y be natural numbers. x + y = x + y

2. Sketch an argument (some would call this an informal proof) to argue the veracity of the following based on axiom set 3.3.1:

A. If w, x, y, and z are natural numbers, then [(x + y) + z] + w is a natural number.

B. If w, x, y, and z are natural numbers, then x + y + z + w is a natural number.

C. If w, x, y, and z are natural numbers, then (x + y) + (z + w) = (z + w) + (x + y).

D. If x, y, and z are natural numbers, then (x + y) + z = z + (y + x).

E. If w, x, y, and z are natural numbers, then [(x + y) + z] + w = (x + y) + (z + w).

F. If w, x, y, and z are natural numbers, then [(x + y) + z] + w = w + ([y + x] + z).

3. Note the seventh basic axioms of (N, +). Does it hold for subtraction? Why or why not?

§ 3.4 ANOTHER TYPE OF ARITHMETIC.

Why do we count as we do? What is the reason? We use the base ten system and we define digits to be the universe D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. So our digits that are from the set natural numbers star (N^* = {0, 1, 2, 3, 4, 5, . . . } ) simply show positional meaning to the powers of ten. Hopefully, we all recall that the number 1,237 simply means that we have one 10³, two 10², three 10¹, and seven 10⁰. So our positional method (the Hindu-Arabic numeration system so named based on the symbols being developed in India then transmitted through the Muslim caliphate to Africa and Europe) is an elegant and useful method for expressing the natural numbers (with zero) and is extended to the integers, rationals, etc.

We were probably told that the Hindu-Arabic numeration system is that which it is and it is the best way to do it. But in the course of our existence we use other systems; for example, modular or base 12 and base 60 (sort of) for time, base 12 and base 3 (sort of) for English measurement of distance, etc. It is the best system; for if one studies other numeration systems one would find they lack the ease of operation and the rigor of the Hindu-Arabic numeration system. You are free to study other systems and compare them to this one. Our discussion will centre on base and modular arithmetic using the Hindu-Arabic numeration system or an extension of them.

Formally, a natural number can be expressed in any base system such that the base is well defined so that each position represents groups of powers of the base.

Consider 1,237 in base ten means one 10³, two 10², three 10¹, and seven 10⁰ but if this were base nine then 1,237 would mean one 9³, two 9², three 9¹, and seven 9⁰. This is meaningful, but for base five, for example it would not because since 7 > 5 how could one have 7 in base 5? Thus the digits for each type of base depend on the base.

For base 2 the set of digits is T = {0, 1};

for base 3 the set of digits is H = {0, 1, 2};

for base 4 the set of digits is F = {0, 1, 2, 3};

for base 5 the set of digits is V = {0, 1, 2, 3, 4};

for base 6 the set of digits is X = {0, 1, 2, 3, 4, 5};

for base 7 the set of digits is S = {0, 1, 2, 3, 4, 5, 6};

for base 8 the set of digits is E = {0, 1, 2, 4, 5, 6, 7}; and,

for base 9 the set of digits is N = {0, 1, 2, 4, 5, 6, 7, 8}. One can extend past base 10 in more than one way. Let us use the ‘alpha-numeral’ system such that

for base eleven the set of digits is L = {0, 1, 2, 4, 5, 6, 7, 8, 9, T};

for base twelve the set of digits is W = {0, 1, 2, 4, 5, 6, 7, 8, 9, T, E}; etc.

Now in each system the value in each position represents the number of powers of the base from right to left. Hence, the number 11010 in base 2 is well defined and for clarity when we are referencing a number in an alternate base system let us use a subscript to clarify the meaning; so, let us let ‘one one zero one zero base two,’ be written as 11010₂.

Now, it is 1 of 2⁴, 1 of 2³, 0 of 2², 1 of 2¹ , 0 of 2⁰. Hence it is

1 ´ 2⁴,1 ´ 2³, 0 ´ 2², 1 ´ 2¹ , and 0 ´ 2⁰ using the elementary sign for multiplication.

So, it is (1 ´ 2⁴) + (1 ´ 2³) + (0 ´ 2²) + (1 ´ 2¹) + (0 ´ 2⁰).

Hopefully, it is facile to see that we therefore have (16) + (8) + (0) + (2) + (0).

So, 11010₂ º 26 in standard decimal (base ten) form; we shall use the symbol for logically equivalent (º) since that is what we are expressing that the two concepts are indeed the same only they are expressed in different systems.

So, suppose we are presented with 113241₅. What is it?

Clearly it is (1 ´ 5⁵) + (1 ´ 5⁴) + (3 ´ 5³) + (2 ´ 5²) + (4 ´ 5¹) + (1 ´ 5⁰); which is by the axioms of the natural numbers, (1 ´ 5⁰) + (4 ´ 5¹) + (2 ´ 5²) + (3 ´ 5³) + (1 ´ 5⁴) + (1 ´ 5⁵) =

(1) + (20) + (50) + (375) + (625) + (3,125) = 4,196.

Now consider 3,401. Suppose we wish to convert it to base 6 (yes, I am aware this is rather odd but bear with me). Since conversion from base ‘A’ to base ten was done through expansion and multiplication it is logical to conclude that this process will require division (explain why this seems reasonable to yourself). However, we need the powers of 6. Note that

6⁰ = 1, 6¹ = 6, 6² = 36, 6³ = 216, 6⁴ = 1,296, 6⁵ = 7,776, and so forth. We only need those powers less than or equal to 3,401 since there can be no groups of size 7,776 or more to allot.

Now, note the algorithm we shall use.

Note that 1,296 ´ 2 = 2,596. So, we subtract

-2596

805 leaving 805 as a remainder.

Now, Note that 216 ´ 3 = 648. So, we subtract

- 648

157 leaving 157 as a remainder.

Now, Note that 36 ´ 4 = 144. So, we subtract

- 144

13 leaving 13 as a remainder.

So, Note that 6 ´ 2 = 12. So, we subtract

- 12

1 leaving 1 as a remainder.

Finally, Note that 1 ´ 1 = 11. So, we subtract

- 1

0 leaving no remainder.

Hence, it is the case that 3401 = 2596 + 648 + 144 + 12 + 1 =

(2 ´ 1296) + (3 ´ 216) + (4 ´ 36) + (2 ´ 6) + (1 ´ 1) =

(2 ´ 6⁴) + (3 ´ 6³) + (4 ´ 6²) + (2 ´ 6¹) + (1 ´ 6⁰) Þ

3401 º 23421₆.

Now, before proceeding any further explain what the algorithm was; how it was used; why it was used; and, opine as to its generalisation.

Consider 711. Let us convert this to base 2. You can create the algorithm yourself; suffice it to say the powers of two are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1,024, 2,048, etc. We only need begin our work with 512. 711 – 512 = 199. 199 – 128 = 81. 81– 64 = 17. 32 into 17 yields 0 with remainder 17 so proceed to 2⁴. 17 – 16 = 1. We divide by 8, 4, and 2 and also get zeros. Finally 1 divided by 1 is 1 with remainder zero. So we get 111010001₂

Let us consider 711 again only this time let us convert it to base 12. The powers of twelve are 1, 12, 144, 1,728, etc.

Note that 144 ´ 4 = 576. So, we subtract

-576

135 leaving 135 as a remainder.

Now, Note that 12 ´ 11 = 132. But, we cannot use ‘11’ so we use E. - 132 Subtract

3 leaving 3 as a remainder.

Now, Note that 1 ´ 3 = 3 So, we are done.

Hence, 711 º 4E3₁₂.

Now, the easiest way to convert from base A to base B (where A and B are not 10) is to convert to base ten then out of it.

For example converting 312₄ to base 7 would entail considering that

312₄ is (3 ´ 4²) + (1 ´ 4¹) + (2 ´ 4⁰) = (3 ´ 16) + (1 ´ 4) + (2 ´ 1) = 48 + 4 + 2 = 54.

Now the powers of seven are 1, 7, 49, 343, 2,401, 16,807, etc. We could begin with 343; but that would be foolish. We need only begin with 49.

Note that 49 ´ 1 = 49. So, we subtract

-49

5 leaving 5 as a remainder.

Note that 7 ´ 0 = 0. So, we don’t subtract.

still leaving 5 as a remainder.

Now, Note that 1 ´ 5 = 5. Subtract

- 5

0 So, we are done.

Hence, 312₄ º 105₇. Please note that we are using transitivity to deduce this.

There are shortcuts and other tricks that (long ago) we studied in Sister Rose Dominic’s fifth grade class at St. Margaret’s School; but, suffice it to say that is the gist of base systems. So, try some!

§ 3.4 EXERCISES.

1. Convert the following numbers to base ten.

A. 813₉ G. 313₄ M. 6611₈

B. 110311₄ H. 3103013₄ N. 1166₈

C. 110101₂ I. 1010101₂ O. 6116₈

D. 03413₅ J. 34013₅ P. 3ET1₁₂

E. 110311₇ K. 110131₇ Q. 1562₁₂

F. 1661₈ L. 6161₈ R. 111₁₁

2. Convert 913 the following bases

A. base 2 G. base 8

B. base 3 H. base 9

C. base 4 I. base 12

D. base 5 J. base 16 (define the symbols used)

E. base 6

F. base 7

3. Convert the following numbers to the specified base.

A. 813₉ to base 3 G. 313₄ to base 5 M. 6611₈ to base 6

B. 110311₄ to base 2 H. 3103013₄ to base 9 N. 1166₈ to base 6

C. 110101₂ to base 3 I. 1010101₂ to base 8 O. 6116₈ to base 6

D. 03413₅ to base 8 J. 34013₅ to base 7 P. 3ET1₁₂ to base 2

E. 110311₇ to base 12 K. 110131₇ to base 5 Q. 1562₁₂ to base 5

F. 1661₈ to base 7 L. 6161₈ to base 4 R. 111₁₁ to base 5

4. Convert 11001010101010101₂ to base 10.

5. Let the digits for base 16 be {0, 1, 2, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} where A is ten B is eleven, C is twelve, D is thirteen, E is fourteen, and F is fifteen. Convert the following to base 10:

A. 813₁₆ C. BAD₁₆ E. FACE₁₆

B. 110311₁₆ D. 5F3₁₆ F. 111₁₆

6. Determine which is greater 1304₅ or 503₇ and justify your conclusion.

7. Define addition and multiplication in other bases to be as we would naturally assume them to be (e.g.: a_b + c_b = d_b if and only if a_b º x₁₀ and c_b º y₁₀ yields x + y = z and z º d_b

a_b ´ c_b = f_b if and only if a_b º x₁₀ and c_b º y₁₀ yields x ´ y = w and z º f_b ).

Compute the following:

A. 813₉ + 712₉ F. 110101₂ + 1111₂ M. 1101₂ ´ 1001₂

B. 110311₄ + 110311₄ G. 31₄ + 11₄ N. 6₈ ´ 7₈

C. 110101₂ + 110101₂ H. 31₄ + 32₄ O. 3₈ ´ 2₈

D. 110101₂ + 1101₂ I. 31₄ ´ 11₄ P. 3ET1₁₂ ´ 7₁₂

E. 110101₂ + 1001₂ J. 31₄ ´ 32₄ Q. 110101₂ ´ 1001₂

§ 3.5 MODULAR ARITHMETIC.

As discussed in the previous section, we count in other ways besides just base ten. The illustration that I alluded to was time, weight, distance, etc. that we in the United States follow rather than as most humans where they have acclimated to a decimal system for all but time.

Nonetheless, there is something really odd about our system. Think about the following:

Start with 1 minim. After a while we get 60 minims which is one dram. Later we finally have 8 drams which is an ounce. Sixteen ounces and we have a pint. Two pints and we have a quart. Four quarts and we have a gallon, and so for and so on.

What of drams, ounces, pounds, tons, etc. not to mention inches, feet, yards, miles, etc.? Why measure time as 60 seconds for one minute, sixty minutes for an hour, but twenty-four hours for a day; and more preposterous months with 28, 29, 30, or 31 days but there are twelve of them so a year has 365, 366, or 367 days?[10]

Well, it is convention and sometimes ten is not always the best under any and all circumstances, eh? So, what of these systems? They illustrate modular arithmetic (some with changes in the place values). Consider 11 + 5 = 4. Note it is nonsense since the universe was not defined and it leads on to assume it is referencing real arithmetic. We are not in the business to play games and attempt to fool others, each other, or ourselves.

So, let us define modular arithmetic as follows. Let U = and D = Where p Î N. Let a Î D and b Î D. Let a +_p b be z Î D where z is the remainder from the division of p into

(a + b) under ordinary addition for the natural numbers.

So, for example let us see what +₄ is. 0 +₄ 0 = 0, 0 +₄ 1 = 1, 0 +₄ 2 = 2, 0 +₄ 3 = 3,

1 +₄ 0 = 0, 2 +₄ 0 = 2, 3 +₄ 0 = 3 all because 4 divided into any of these is zero with remainder whatever the non-zero constant was. Consider 1 +₄ 1 = 2, 2 +₄ 1 = 3, 1 +₄ 2 = 3 for the same reasons.

So, we are left with the other possibilities:

1 +₄ 3 = 0 since 4 ¸ 4 = 1 with remainder 0.

2 +₄ 2 = 0 since 4 ¸ 4 = 1 with remainder 0.

2 +₄ 3 = 1 since 5 ¸ 4 = 1 with remainder 1.

3 +₄ 2 = 1 since 5 ¸ 4 = 1 with remainder 1.

3 +₄ 3 = 2 since 6 ¸ 4 = 1 with remainder 2.

Note that this is all good and well but it can be confusing. So, let us note the results in tabular form:

+4	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

This should look strikingly familiar (see section 3.1).

You should be comfortable with defining the same for other mods (modular arithmetic operations with some natural number) such as:

+3	0	1	2
0	0	1	2
1	1	2	3
2	2	3	0

and:

+6	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

We can also define modular multiplication: Let U = for some p Î N.

Let a Î and b Î . Let a ´_p b be z Î where z is the remainder from the division of p into (a ´ b) under ordinary multiplication for the natural numbers. Do the arithmetic in your head for mod 4 multiplication to get the following:

´4	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

Now reconsider 11 + 5 = 4. Recall we are not in the business to play ‘games.’

Consider +₁₂. Note it is fine to consider U = and let the set of digits be .

11 +₁₂ 5 = 4 is understandable from the applied problem of 11 a.m. and 5 hours is 4 p.m. (5 hours after 11 a.m. is 4 p.m.). Notice we do not use the universe D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, T, E} as with base arithmetic. Also, note that commutativity and associativity hold.

Now, does there exist a distributive property of modular multiplication over modular addition? If so, how would you prove it; if not, can you devise a counterexample?

It is perfectly acceptable to define a system of modular arithmetic that includes p Î N for

U = as with time. Hence, in modular 12 arithmetic, 7 +₁₂ 5 = 0 but in practical applications most would say it is 12 Since 12 Û 0 in the sense of time (in hours). Once again defining the domain of discourse for the discussion (logic) and noting the universe (sets) is paramount to clearly and objectively investigating, understanding, and applying the mathematical system.

§ 3.5 EXERCISES.

1. Construct the table for addition and multiplication mod 5.

2. Construct the table for addition and multiplication mod 8.

3. Calculate the following

A. 8 +₉ 1 +₉ 3 G. 7 +₉ 7 +₉ 7 N. 7 +₈ 5 +₈ 6

B. 8 ´₉ 1 ´₉ 3 H. 7 ´₉ 7 ´₉ 7 O. 6 +₈ 5 +₈ 7

C. 1 +₂ 1 +₂ 1 I. 7 +₈ 7 +₈ 7 N. (7 +₈ 5) +₈ 6

D. 0 ´₂ 1 ´₂ 1 J. 7 ´₈ 7 ´₈ 7 O. 5 ´₈ 7 ´₈ 6

E. 4 +₅ 3 +₅ 1 K. 3 +₅ 3 +₅ 1 N. 5 +₁₂ 5 +₁₂ 5

F. 4 ´₅ 3 ´₅ 1 L. 4 ´₅ 3 ´₅ 3 O. 5 ´₈ 6 ´₈ 7

4. What is incorrect about the following claim?

9 ´₈ 7 = 7 ´₈ 9

5. Compute the following:

A. 813 +₉ 712 F. 110101 +₂ 1111 M. 1101 ´₂ 1001

B. 110311 +₄ 110311 G. 31+₄ 11 N. 6 ´₈ 7

C. 110101 +₂ 110101 H. 31 +₄ 32 O. 3 ´₈ 2

D. 110101 +₂ 1101 I. 31₄ ´₄ 11 P. 31 ´₁₂ 7

E. 110101 +₂ 1001 J. 31 ´₄ 32 Q. 110101 ´₂ 1001

6. Compare the results of exercise 5 with exercise 7 of section 3.4. What patterns (if any) exist and can they be explained or an hypothesis formed as to the relationship between modular arithmetic and arithmetic of natural numbers in different bases?

§ 3.6 THE PEANO AXIOMS, COUNTING, AND MATHEMATICAL INDUCTION.

We learned to count before elementary school (one hopes); but, the formal theory of counting is oft called Number Theory (Math 475) or Combinatorics (not yet offered).

At an introductory level for mathematics, combinatorics is considered a branch of Discrete Mathematics (Math 211) in which the main focus is the number of ways to choose or arrange objects from a finite set from Set Theory (Math 255). It is a branch of number theory insofar as the axioms of number theory create the building blocks from which combinatorics arises. Much work in Numerical Analysis (Math 467) requires a rudimentary understanding of number theory as well as Real Analysis (Math 361 – 362 – 463 sequence). Indeed one needs to understand theoretical mathematics (including counting theory) in order to really understand and master Applied Mathematics) Math 325 and 327).

Most of the counting techniques that we will concern ourselves with are of the type that lay the groundwork for an intuitive understanding of Probability Theory (Math 341 - 342).

We have already discussed at least one method of counting from a finite set and that was the applications of Venn Diagrammes to surveys. Now, we will extend our understanding to some more complex problems.

Recall that N = {1, 2, 3, 4, 5, . . . , (k - 1), k, (k + 1), . . . .}. They seemingly go on and on – well, they do because it has been proven to be true. Let us consider this important theorem.

Theorem 3.6.1 (the Archimedean property of N in R ): The natural numbers are unbounded above in the reals.

The properties of addition of natural numbers can be derived from a short set of axioms. The axioms are called the Peano Axioms:

There exists a set, P, which is defined by the following four axioms.

Axiom 1: There exists a natural number, call it 1, that is not the successor of any other natural number.

Axiom 2: Every natural number has a unique successor. If k Î P , then let k¢ denote the successor of k.

Axiom 3: Every natural number except one is the successor of exactly one natural number.

Axiom 4: If M is a set of natural numbers such that

(i) 1 Î M and

(ii) for each k Î P, if k Î M, then k¢ Î P,

then P = M.

P, of course is N.

So, the Peano axioms assert the uniqueness of the naturals that this successor property along with the element 1 creates the entirety of the natural numbers. No matter how you name the set (you can call it Ray, or you can call it Jay, . . .) if it has these properties then it really is the naturals.

From these axioms arise the natural numbers by defining what addition by one means.

Definition 3.6.1: For every k Î N , define k + 1 = k¢.

Then, note inductively, the entire understanding of addition flows from this definition (likewise multiplication, etc.).

So, it seems the basis of our understanding of counting will be based N.

No, pity. We need .

Recall = { 0, 1, 2, 3, . . ., (j - 1), j, (j + 1), . . . .} = N È {0} = {0} È N.

Finally, before proceeding we need to define factoral.

Let k Î r ecursively define k! Such that

0 ! = 1

1 ! = 1

2 ! = 2 ^. 1

3 ! = 3 ^. 2 ^. 1

.

.

.

k ! = k ^. (k - 1) ^. . . . ^. 3 ^. 2 ^. 1 where k ³ 3.

A more succinct definition is k ! =

Theorem 3.6.2: Let k Î N . It is the case that k ! = k ^. (k - 1) !

Now, to the business at hand:

Lemma 3.6.3: If we have a set, A, with m elements such that m Î N and we have a set, B, with n elements such that n Î N, then the number of ways to order the elements from A then the elements from B is .

Theorem 3.6.3 (The Fundamental Principle of Counting): If activities 1, 2, 3, . . ., k can be performed in n₁, n₂, n₃, . . . n_k ways, respectively, such that k Î N and n_i Î N " i Î N_k then

the k activities can be performed in = ways.

Consider we choose one of 2 objects from the set {a, b}, then we choose one of three objects from the set {2, 4, 6}. Hence, the number of ways to do this is = 6.

The sequence of activities can be illustrated with a set of ordered pairs since the activities are in order:

{(a, 2), (a, 4), (a, 6), (b, 2), (b, 4), (b, 6)}.

Further, the sequence of activities can be illustrated with a tree diagramme:

2

ƒ

ƒ

a ¾¾¾ 4

‚

‚

6

2

ƒ

ƒ

b ¾¾¾ 4

‚

‚

6

A tree diagramme is a simple graphical illustration of an ordered sequence of activities.

In many counting problems, the task assigned is one involving arranging a set of objects. Now, the arrangement may or may not involve order.

Definition 3.6.2: Suppose the set A has n objects such that n Î and we wish to order k of the objects ' k £ n where k Î

The number of ways to do this is referred to as the permutations of n things taken k at a time and is symbolised as P_{n, k} where

Alternate notation for permutations include the following: P_n,k = _nP_k = = = P(n, k).

Definition 3.6.3: Suppose the set A has n objects such that n Î and we wish to choose k of the objects (without regard to order) ' k £ n where k Î The number of ways to do this is referred to as the combinations of n things taken k at a time and is symbolised as where

Alternate notation for combinations include the following: = C_n,k = _nC_k = = =

C(n, k).

Theorem 3.6.4: Let n Î and k Î ' k £ n. P_n,k = k! ^. .

As we know, inductive reasoning is fraught with fallacies. Deductive reasoning is not.

Consider a statement F(n) that we wish to prove for all n Î N. This is logically equivalent to the statement " n Î N, F(n). Such types of claims oft ‘pop up’ in number theory, analysis, algebra, etc. Thus, it would behoove us to have a method of proof to tackle such quantification claims. Well, fortunately there is a method:

First principle (axiom) of mathematical induction:

{ F(1) Ù [" k Î N, F(k) ® F(k + 1)] } Þ " n Î N , F(n).

Thus, if we can prove the antecedent of the axiom, then by the axiom (an application of modus ponens) , we can deduce " n Î N, F(n).

Thus, there are two steps to prove a claim:

Prove F(1) is true. This is oft referred to as the basis step.

Prove given k Î N , F(k) ® F(k + 1). This is oft referred to as the inductive step.

To understand this process intuitively, note we have deduced an endless sequence of sentences.

F(1).

F(1) ® F(2).

F(2) ® F(3).

F(3) ® F(4).

.

.

.

F(j - 1) ® F(j).

F(j) ® F(j + 1).

.

.

.

So, what we have is an endless sequence of modus ponens arguments:

F(1). F(2). F(3). . . . F(j). . . .

F(1) ® F(2). F(2) ® F(3). F(3) ® F(4). F(j) ® F(j + 1).

\ F(2). \ F(3). \ F(4). . . . \ F(j + 1). . . .

Producing the endless sequence of true statements: F(1), F(2), F(3), F(4), . . ., F(j), . . .

Note there is no need to begin with n = 1. What is necessary is that the set which we are considering is of the form of a “list” which in Set Theory will be defined for you and whose properties will be explored (such sets are called denumerable). The set N in the first principle of mathematical induction is referred to as the index set or the set of indices.

Also, note that since there is not a need to begin with n = 1, there will be other principles of mathematical induction. All generally conform to this idea; however, so understanding this basic form is a step toward understanding more sophisticate forms.

Second principle (axiom) of mathematical induction: Let a_i Î I., where I is some denumerable index set. { F(a₁) Ù [" k Î N, F(a_k) ® F(a_{(k + 1)}] } Þ " a_n Î I., F(a_n).

Third principle (axiom) of mathematical induction (also called strong induction): Let X. be a subset of the natural numbers. If k Î X when " j Î N ' j < k j Î X, then X = N.

Now, let us consider a claim.

Claim 3.6.1: for all n Î N. Prove or disprove the claim

As always, you must first read the claim and decide whether or not you think it is true (you may be wrong, but you have to practice this step; it is based on your prior experience and knowledge). It is an inductive step; hence, there is no guarantee that you are right.

Next, after considering the claim, suppose we think it true. Thinking it is true is not proving it is true. Hence, we need to construct a proof. We must announce it is a proof and frame it at the

beginning (Proof:) and at the end (Q.E.D.[Quod Erat Demonstratum]).

Proof:

0. Assume the premises (the axioms) 0. premises

1. Let n = 1 1. Basis step

2. Consider 2. Hypothesis

3. = 1 (1!) 3. Definition of Sigma

4. = 1 ^. 1 4. Definition of factoral

5. = 1 5. Multiplication

6. Consider (n + 1 )! 6. Hypothesis

7. = (1 + 1)! 7. Substitution

8. = 2! 8. Addition

9. = 2 9. Definition of factoral

10. 1 < 2 10. Properties of the real numbers

11. 1 < 2 1 = 2 11. Law of Addition (10)

12. 1 2 12. Definition of less than or equal to.

13. (1 + 1)! 13. Substitution

14. Assume $ m Î N ' 14. Inductive Hypothesis

15. Consider 15. Hypothesis

16. = 1(1!) + 2(2!) + . . . .+ m(m!) + (m+1)[(m+1)!] 16. Definition of Sigma

17. = {1(1!) + 2(2!) + . . . .+ m(m!)} + (m+1)[(m+1)!] 17. Associative of +

18. = + (m + 1)[(m + 1)!] 18. Definition of Sigma

19. (m + 1)! + (m + 1)[(m + 1)!] 19. Substitution

20. = (m + 1)! [1 + (m + 1)] 20. Distributive of ´ over +

21. = (m + 1)! [(m + 1) + 1] 21. Commutative of +

22. = ((m + 1) + 1)! 22. Definition of factoral

23. Thus, = ((m + 1) + 1)! 23. Transitivity of equality.

24. So, Þ ((m + 1) + 1)!

Q. E. D.

§ 3.6 EXERCISES.

Prove or disprove the following:

1. Claim: " n Î N

2. Claim: 2ⁿ < 2^{(n + 1)} " n Î N

3. Claim: 2ⁿ > n " n Î N

4. Claim: 2ⁿ < n! " n Î N

5. Claim: 2ⁿ £ " n Î N – N₃

6. Claim: Let a Î R Ù a > 1. It is the case that (1 + a)ⁿ ³ 1 + an " n Î N

7. Claim: " n Î N

8. Claim: " n Î N

9. Claim: 2 + 4 + 6 + … + 2n = n(n + 1) " n Î N

10. Claim: 1 + 3 + 5 + … + (2n – 1) = " n Î N

11. Claim: 1 - 3 + 5 – 7 + 9 – 11 +… + (2n – 1) = " n Î N

12. Claim: " n Î N

13. Claim: Let a Î R Ù b Î R. It is the case that " n Î N

14. Claim: " n Î N

15. Claim: " n Î N

---

[1] Actually Euclid’s fifth postulate was stated differently. The statement given here is the logically equivalent version of Euclid’s fifth postulate from John Playfair’s book, Elements of Geometry, published in 1795 or so.

[2] Axiom: from the Greek axiwma loosely translated to mean that which is self-evident or thought to be fitting. Some thought axioms were self evident; but twentieth century logicians showed that self-evident is a rather dangerous concept. Hence, we shall adopt the position that the axioms are those primitive statements that are generally agreed to and that when we are going to study a particular branch of mathematics must be adhere to or obeyed.

[3] These axioms form the foundation of Math 361 and 362 (Real Analysis I and II) along with the order axioms and the completeness axiom; all the interesting results from algebra, graph theory, functional analysis, differential, and integral Calculus all stem from these). When one studies other systems which have these properties they are studying Algebra (Math 371 and 372).

[4] We will use this later.

[5] This makes it easier to see the next part of the proof to substitute for 0 ^. x but it is not necessary just as it was not necessary to substitute for 0 ^. 0.

[6] Read this carefully. Decide what is being said.

[7] These are the axioms that are the basis of Math 255, Set Theory. However, they are difficult to ‘deal’ with and so one does not typically work with them until a graduate class in Set Theory.

[8] I have studied such set theories. It is a fascinating discussion to determine when one deletes certain axioms what results hold or do not hold. That is to say that just because an axiom is presented does not necessitate its acceptance. So, one can study mathematical systems such that different axiom systems are predicated. However, if such a system is predicated the axioms must be stated.

[9] These are the axioms that form the basis of Math 341 and Math 342 (Probability and Mathematical Statistics). Note: the axioms of probability are one of the shortest lists I can recall for an area of mathematics - - they form the basis of probability theory; however, probability theory depends on other mathematical theories (for example, set theory). Thus, the brevity of the axiom list is somewhat deceiving.

[10] Check this out – hint: years ending with ‘00’ but not divisible by 400.