[PDF] Basic properties of the integers

947_6BasicPropertiesOfIntegers.pdf

Basic properties of the integers

MA 341 { Spring 2011

1 Denitions

Thenatural numbersare the numbers 1;2;3;:::(some authors include zero, as well), and for shorthand, we will denote the collection of them byN. Theintegers(a.k.a. thewhole numbers) are the natural numbers, together with zero and the negatives of the natural numbers, and we will denote them byZ. So,

Z? ?:::;?2;?1;0;1;2;:::?:

The integers come equipped with extra structure with which you are all familiar: addition (?), multiplication (?), and an ordering (?). I'll leave addition and multiplication undened (but I could dene it by starting from even more basic assumptions). As for ordering, I'll simply point out that one can give the following denition: Denition 1.1.Given two integersa;b, we say thataisless thanb, writtena?b, if there exists ac?Nsuch that b?a?c:

2 Basic properties of the integers

In this section, we'll list some basic properties of the integers that will form the basis of everything we will prove this semester, i.e. everything we prove this semester will be trace- able all the way back to these simple properties. In the next section, we will prove some basic consequences of these properties; you will prove more basic consequences on your rst assignment.

2.1 Arithmetic properties

We begin with thearithmeticproperties, i.e. those related to addition, multiplication, and the relation between the two. (1)if a;b?Z, thena?b?Z(closureunder addition) (2) if a;b?Z, thena?b?Z(closureunder multiplication) (3) if a;b?Z, thena?b?b?a(commutativityof addition) (4) if a;b?Z, thena?b?b?a(commutativityof multiplication) (5) if a;b;c?Z, thena? ?b?c? ? ?a?b? ?c(associativityof addition) (6) i fa;b;c?Z, thena? ?b?c? ? ?a?b? ?c(associativityof multiplication) (7) t hereexists an elemen t0 ?Zsuch that for alla?Z a?0?a(existence of anadditive identity) (8) there exists an elemen t1 ?Zsuch that for alla?Z a?1?a(existence of amultiplicative identity) (9) for ev erya?Z, there is a solutionx?Zto a?x?0 (namelyx? ?a) (existence of anadditive inverse) (10) if a;b;c?Zandc?0, then a?c?b?cimpliesa?b(cancellation law) (11) if a;b;c?Z, thena? ?b?c? ?a?b?a?c. (distributivity law)

Remark 2.1.

(a) F orprop erties(1){(8), there is a prop ertyof addition follo wedb ya corresp onding property of multiplication. This breaks down for property (9). The corresponding property would be that for alla?Zthere is a solutionx?Ztoa?x?1. But, of course, this fails, e.g. takea?2, there is no integerxsuch that 2x?1. However, the cancellation law (10) often serves as a substitute for the lack of multiplicative inverses: often you just want to divide both sides of an equation by the same quantity, the cancellation law allows you to do this without actually having to divide. (b)Prop erty(9) allo wsus to dene subtractionas follows: a?b:?a? ??b?; i.e. subtractingbisdenedto be adding its additive inverse.

2.2 Ordering properties

Theorderingproperties are those concerning the relation?. (12) if a;b?0, thena?b?0 (closureof \?0" under addition) (13) if a;b?0, thena?b?0 (closureof \?0" under multiplication) (14) for an yt woin tegersa;b?Z exactly one ofa?b;a?b;ora?bis true (trichotomy law) (15) Ev erynon-empt yset of natural n umbershas a least elemen t,i.e. for an yS?N, if

S? ?, then there is anm?Ssuch that

m?s;for alls?S:(well-ordering property)

Remark 2.2.

(a) Just to b eclear, w ewrite a?bifb?a, and we writea?bifa?bora?b. (b) Prop erty(14) suggests a con venientw ayto pro vet won umbersa;bare equal: rst prove a?b, then proveb?a. Since it can't be true that botha?bandb?a, this implies thata?b.

3 Some basic consequences

Here, we give some examples of some basic consequences of the properties listed above, as well as their proof. A major reason for including some proofs here is to give you some experience with proofs, so do read through them and try to understand why they are how they are. You'll have a chance to practice similar proofs on the rst assignment. Proposition 3.1.The additive identity inZis unique, i.e.0is the only element inZsatis- fying property (7). Proof.Lete?Zdenote an integer such thata?e?afor alla?Z. In particular, this is true fora?0, so

0?e?0:

Also,

0?e?e?0 (by commutativity of?)

?e:(since 0 is an additive identity)

Putting these together, we get

0?0?e?e

soe?0. So, any integer satisfying property (7) is necessarily 0.Can you nd a shorter proof of the above?

Proposition 3.2.Givena?Z, its additive inverse is unique, i.e. the equationa?x?0has a unique solutionx?Z. Proof.Supposex;y?Zare such thata?x?0 anda?y?0. Addingxto both sides of the second equation gives a?y?x?x: By commutativity of addition, denition ofx, and the fact that 0 is the additive identity, a?y?x?a?x?y?0?y?y: Combing these two lines givesx?y.Proposition 3.3.For alla?Z,

0?a?0:

Proof.By distributivity,

?0?0? ?b?0?b?0?b:

Since 0 is an additive identity, 0?0?0, so

?0?0? ?b?0?b:

Combing these two equations yields

0?b?0?b?0?b:

Adding??0?b?to both sides gives

0?b?0;

as desired.Proposition 3.4.For alla?Z, ?a? ??1? ?a: Proof.First, we'll show that??1? ?ais an additive inverse ofa. Indeed, a? ??1? ?a?1?a? ??1? ?a(by (8) and (4)) ? ?1? ??1?? ?a(by distributivity and (3)) ?0?a(by (7)) ?0;(by proposition 3.3)

as desired. By the uniqueness of additive inverses (proposition 3.2), the result follows.Proposition 3.5.Leta;b?Z. Ifa?b?0, thena?0orb?0.

Proof.(Proof by contradiction) Sincea?b?0,

a?b?a?b?a?b?0: By the uniqueness of additive inverses (proposition 3.2), this implies that ??a?b? ?a?b:

Applying proposition 3.4 (and (8)), gives

??1? ?a?b?1?a?b:

Ifb?0, we can use the cancellation law to obtain

??1? ?a?1?a: Ifais also not 0, we can apply the cancellation law again to get ?1?1: But 1?1?2?Nand hence 1?1?0, i.e. 1? ?1. Therefore, the assumption that bothaand

bare not zero leads to a contradiction. Therefore, one of them must be zero, as desired.Proposition 3.6.Letb?Z. Thenb?Nif, and only,b?0.

Proof.???: supposeb?N. By (7) and (3),

b?0?b; i.e., using denition 1.1 (witha?0 andc?b), we can say 0?b. ???: (contrapositive) supposeb?N, then we want to show thatb?0 is not true. By denition,Zconsists of the natural numbers, 0, and the negatives of the natural numbers. Sinceb?N, eitherb?0 or there isa?Nsuch thatb? ?a. Ifb?0, then the trichotomy law implies that you can't haveb?0. In the second case (b? ?a), we have

0? ?a?a?b?a:

In terms of denition 1.1, this means thatb?0. By the trichotomy law,b?0 cannot be true.The well-ordering property is a statement aboutN. More generally, given any \ordered set" X, we say it is \well-ordered" if every non-empty subsetS?Xhas a least element. Let a?Zand dene the notation Z ?a:? ?b?Z:b?a?; in particular,N?Z?1. All of these sets are well-ordered.

Proposition 3.7.Leta?Z, thenZ?ais well-ordered.

Proof.LetS?Z?abe any non-empty subset. Let

X:? ?s?a?1 :s?S?:

Claim(1).Xis a non-empty subset ofN.

Proof of claim (1).Xis non-empty sincea?a?1?1?X. To showX?N, it's enough to show that for allx?X,x?0 (by proposition 3.6). By a question on assignment 1, s?aif, and only if,s?r?a?rfor allr?Z:(?)

Using this withr? ?a?1, we get that for alls?S

s?a?1?a?a?1?1:

Letx?X, then there is ans?Ssuch thatx?s?a?1. Hence,x?1.SinceNis well-ordered andXis a non-empty subset of it, there is a least elementx0?X.

Claim(2).s0:?x0?a?1is a least element ofS.

Proof of claim (2).Lets?S. Using???again withr? ?a?1, s?s0if, and only ifs?a?1?x0: By denition ofX,s?a?1?X, so we know thats?a?1?x0. Hence,s?s0, and the

latter is a least element ofS.Swas arbitrary, soZ?ais well-ordered.Proposition 3.8.The integersZare not well-ordered.

Proof.(Proof by counterexample) We need to nd a non-empty subsetSofZwhich has no least element. Let's simply takeS?Z(our proposed counterexample). Let's supposem?Z is a least element and derive a contradiction. Sincem? ?m?1? ?1, denition 1.1 says m?1?m, contradicting the minimality ofm. Therefore,S?Zhas no least element.