Mathematics for Computer Science

7.4. Does All This Really Work? 233 That is,G 0000 DG 10 Dno-1s and so strings.G 0000 /Dstrings.G 10 /D 0 . This means that 000 ...

Chapter 7 Infinite Sets234 Problems for Section 7.3 Class Problems Problem 7.27. Forming a pair.a;b/of itemsaandbis a mathematic ...

7.4. Does All This Really Work? 235 The only issue here is that set theory is technically supposed to be expressed in terms ofpu ...

Chapter 7 Infinite Sets236 (c)The Foundation axiom of set theory says that 2 is a well founded relation on sets. Express the Fou ...

7.4. Does All This Really Work? 237 is to represent.a;b/as pair.a;b/WWDfa;fa;bgg: (b)Explain how to write a formula Pair.p;a;b/, ...

Chapter 7 Infinite Sets238 That is: Rule.Ordinal Induction 8 x:. 8 y 2 next.x/:P.y// IMPLIES P.next.x//; 8 S:. 8 x 2 S:P.x// IMP ...

II Structures ...

...

Introduction The properties of the set of integers are the subject of Number Theory. This part of the text starts with a chapter ...

Part II Structures242 lationships, such as being in conflict, being compatible, being independent, being capable of running in p ...

8 Number Theory Number theoryis the study of the integers.Whyanyone would want to study the integers may not be obvious. First o ...

Chapter 8 Number Theory244  ajb,  adividesb,  ais adivisorofb,  ais afactorofb,  bisdivisiblebya,  bis amultipleofa. Some ...

8.1. Divisibility 245 Ifajbandajc, thenajsbCtcfor allsandt. For allc¤ 0 ,ajbif and only ifcajcb. Proof. These facts all follow ...

Chapter 8 Number Theory246 The numberqis called thequotientand the numberris called theremainderof ndivided byd. We use the nota ...

8.1. Divisibility 247 theb-jug is big enough: .0;0/!.a;0/ fill first jug !.0;a/ pour first into second !.a;a/ fill first jug !.2 ...

Chapter 8 Number Theory248 So we have established that the jug problem has a preserved invariant, namely, the amount of water in ...

8.2. The Greatest Common Divisor 249 8.2.1 Euclid’s Algorithm The first thing to figure out is how to find gcd’s. A good way cal ...

Chapter 8 Number Theory250 Euclid’s Algorithm as a State Machine Euclid’s algorithm can easily be formalized as a state machine. ...

8.2. The Greatest Common Divisor 251 of these common divisors. Since any constant multiple of a linear combination is also a lin ...

Chapter 8 Number Theory252 replacedxandyby equivalent linear combinations ofaandb, which we already had computed. After simplify ...