Ordering numbers
In calculus, order relations between real numbers are crucial, for instance when we want to find the maximum value of a function over a certain range.
In mathematical terms, the notation x < y indicates that the difference y - x is positive, while x ≤ y signifies that y - x is nonnegative This can also be expressed as y > x for x < y, and y ≥ x for x ≤ y Visually, on a number line where positive numbers extend to the right, the relationship x < y is represented by an arrow pointing from x to y.
It is often helpful to signify the relationx ≤ y with an arrow fromx to y, without requiring the arrow to go horizontally from left to right.
Understanding order relations in algebra is essential for manipulating numbers effectively The first fundamental rule is reflexivity, which states that for any real, integral, or natural number x, it holds that x ≤ x While this rule may seem trivial, it serves as a foundational concept The second important rule is transitivity, which asserts that if x ≤ y and y ≤ z, then it follows that x ≤ z for any real, integral, or natural numbers x, y, and z For instance, if Xavier cannot defeat Yerkes and Yerkes cannot defeat Zandor, it logically follows that Xavier cannot defeat Zandor either This relationship holds true because if x ≤ y and y ≤ z, the differences y - x and z - y are both nonnegative, leading to the conclusion that z - x is also nonnegative, thus confirming x ≤ z This concept of transitivity can be visualized through a natural arrow diagram.
The final rule in the order relation, known as antisymmetry, states that if x is less than or equal to y and y is less than or equal to x, then x must equal y This principle is illustrated in the context of competition, where if Xavier cannot defeat Yerkes and Yerkes cannot defeat Xavier, it results in a tie between the two.
Rules for an order relation
(T) Transitivity: x≤y and y≤z imply x≤z(A) Antisymmetry: x≤y and y≤x imply x=y
As an illustration of the use of the rules, here’s a proposition with its proof.
Supposex,y, andzare real numbers If x≤y≤z≤x, thenx=z.
PROOF Sincex≤y ≤z, transitivity shows thatx≤z But alsoz≤x, so antisymmetry givesx=z.
The Well-Ordering Principle
In comparing (1.1) with (1.4), it's evident that the elements of Zin (1.1) extend infinitely to the left within the braces, indicating that there is no smallest integer This concept can be illustrated through a variation of the schoolyard game “My Dad earns more than your Dad,” where two players attempt to name the smaller integer Regardless of the number the first player chooses, such as -10,000,000, the second player can always select a number that is even smaller, like -10,000,001 In contrast, the scenario is distinctly different when it comes to natural numbers, which can be succinctly summarized in a specific statement.
Each nonempty subsetSof Nhas a least element infS.
The infimum of a set, denoted as inf S, applies primarily to infinite subsets S, while for finite nonempty subsets, the least element, commonly referred to as the minimum (min S), can be easily identified.
The set S, defined as S = {n ∈ N | 10^n < (1/2) n^n}, consists of natural numbers n for which the power of 10 raised to n is less than half of n raised to the power of n This set is not only nonempty but also infinite, as it can be observed that for values of n greater than 10, the growth rate of n^n surpasses that of 10^n Thus, according to the Well-Ordering Principle, S contains infinitely many elements.
10 n ) =∞.) The Well-Ordering Principle guarantees thatS has a least element infS You are invited to find it in Exercise 5.
The Well-Ordering Principle is fundamental to the techniques of recursion and mathematical induction, exemplified by the recursive definition of the factorial of a natural number n, denoted as n!.
How can we be sure that the definition is complete, that it will not leave a quantity such as 50001200! undefined?
For generality, consider a property P(n) of a natural number n, say the property thatn! is defined by the given recursive procedure.
• TheInduction Basisis the statement that the propertyP(0) holds.
• TheInduction Stepis the statement that truth of the propertyP(n) implies the truth of the property P(n+ 1).
• ThePrinciple of Inductionstates: The Induction Basis and Induction Step together guarantee thatP(n) holds for all natural numbersn.
To justify the Principle of Induction, suppose that it goes wrong In other words, the set
The set S, defined as {n | P(n) is false}, is nonempty, indicating that it contains at least one element According to the Well-Ordering Principle, this set has a least element, denoted as s The Induction Basis establishes that s cannot be 0, leading to the conclusion that s is greater than 0, making s - 1 a natural number Since s - 1 is not in S, the property P(s - 1) must hold true Consequently, the Induction Step reveals a contradiction, confirming that P(s) is true Therefore, the Principle of Induction is validated and remains reliable.
Example 1.3 (A model proof by induction.)
LetP(n) be the statement that the identity
The statement (1.8) is valid for natural numbers, beginning with the induction basis where it simplifies to the trivial equation 0 = 0 when n = 0, confirming that P(0) is true In the induction step, we assume P(n) holds true, thereby affirming that (1.8) remains valid in its original form.
6 , so thatP(n+ 1) is true This proves (1.8) by induction.
Divisibility
The set of integers is a subset of the set of real numbers, allowing for the comparison of integers using the order relation ≤ However, in many instances, the relation of divisibility is more significant for integers An integer m is considered a multiple of another integer n if there exists an integer r such that m = r × n.
The number 946 is a multiple of 11, as it can be expressed as 946 = 86 × 11 Additionally, all even integers are multiples of 2, and zero is considered a multiple of every integer In mathematical terms, an integer \( n \) is defined as a divisor of another integer \( m \) if \( m \) is a multiple of \( n \) Therefore, the statement that \( n \) divides \( m \) is equivalent to saying that \( m \) is a multiple of \( n \).
The statement “ndividesm” is written symbolically asn|m.
Comparing the concepts of divisibility and being a multiple reveals that while divisibility is advantageous for formulating mathematical claims, proving these claims is often simpler using the equation m = rãn For instance, the divisibility relation on integers (Z) exhibits reflexivity and transitivity, similar to the relation of less than or equal to (≤) on real numbers (R).
PROPOSITION 1.4 (Divisibility on Zis reflexive and transitive.) Let m,n, andpbe integers Then:
PROOF (R) For each integerm, the equationm= 1ãmholds, somis a multiple ofm.
(T) Sincem|n, there is an integerrwithn=rm Since n|p, there is an integerswithp=sn Then p=sn=s(rm) = (sr)m is a multiple ofm, so m|p.
However, the relation|onZis not antisymmetric For example, 5| −5 since
−5 = (−1)ã5, and−5|5 since 5 = (−1)ã(−5) Nevertheless, 56=−5 The situation changes when we restrict ourselves to natural numbers We regain all three properties: reflexivity (R), transitivity (T), and antisymmetry (A).
PROPOSITION 1.5 (Divisibility on Nis an order relation.) Let m,n, andpbe natural numbers Then:
Proposition 1.5, which is detailed in Exercise 14, illustrates that the divisibility relations among natural numbers can be represented through arrow diagrams, similar to how order relations are depicted for real numbers For instance, the set
{1,2,3,4,6,12} of divisors of 12 is exhibited in Figure 1.1 The diagram explicitly displays divisibilities such as 3 | 6 with arrows: 3 −→ 6 Other relations, such as
3|12 or 4|4, are implicit from the transitivity and reflexivity guaranteed by Proposition 1.5.
FIGURE 1.1: The positive divisors of 12.
The Division Algorithm
The Division Algorithm provides a formal method to determine if a positive integer \( d \) (the divisor) divides another integer \( a \) (the dividend), which can be positive, negative, or zero By applying this algorithm, we obtain two results: an integer \( q \) (the quotient) and an integer \( r \) (the remainder) These results satisfy the equation \( a = dq + r \).
For example, given the divisor 5 and dividend 37, the algorithm produces 7 as the quotient and 2 as the remainder: 37 = 5ã7 + 2, with 0≤2 b > 0, the algorithm generates a strictly decreasing sequence of natural numbers, starting with r−1 = a and r0 = b Through a series of steps, the Division Algorithm is applied, where each step involves dividing the previous remainder by the current remainder, yielding a new remainder until the process concludes with rk+1 = 0 The final nonzero remainder, rk, represents the gcd(a, b), effectively providing both the gcd and its representation as a linear combination.
Why isrk = gcd(a, b), and how isrk produced as a linear combination ofa andb.? To answer these questions, it is helpful to rewrite (1.26) as the matrix equation ri − 1 ri qi+1 1
In the context of matrix multiplication, as discussed in Section 2.3 on page 28, equation (1.27) establishes an equality for 2-dimensional column vectors with integral entries, specifically holding true for the range 0≤i≤k While the equality of the bottom entries is straightforward, equation (1.26) pertains to the equality of the top entries.
, so (1.27) is equivalent to the matrix equation ri ri+1
(1.28) for 0≤i≤k Repeated use of (1.28) gives rk rk+1
In the context of integer computations involving matrices, the expression for rk can be represented as an integral linear combination of integers s and t, formulated as rk = sr - 1 + tr0 = sa + tb According to Proposition 1.8, any common divisor of integers a and b is also a divisor of rk, thereby establishing that rk meets the criteria for the greatest common divisor of a and b Additionally, the application of the formula (1.27) leads to further insights into the relationship between a, b, and their respective divisors.
0 for integerss ′ ,t ′ ,u ′ , andv ′ , so that a=s ′ rk and b=u ′ rk This means that rk | a and rk | b Thus rk satisfies the requirement (1.22) for the greatest common divisor ofaandb.
Now we know that rk = gcd(a, b), the import of the equation (1.29) may be recorded for future reference as follows (Compare Exercise 28.)
PROPOSITION 1.9 (GCD as an integral linear combination.) Let aandb be nonzero integers Then the greatest common divisorgcd(a, b) may be expressed as an integral linear combination ofaandb.
Example 1.10 (A run of the Euclidean Algorithm.)
Consider the determination of gcd(7,5) with the Euclidean Algorithm The calls to the Division Algorithm are as follows:
Thus gcd(7,5) emerges as 1, the remainder from the penultimate Step (1). The matrix equations (1.27) become
Primes and irreducibles
The positive number 35 can be reduced to a product 5ã7 of smaller positive numbers 5 and 7 On the other hand, neither 5 nor 7 can be reduced further.
In fact, if 5 =aãbfor positive integersaandb, thena= 1 andb= 5 ora= 5 andb= 1 We define a positive integerpto be irreducible ifp >1 and
(1.30) for integersd Irreducibility is an “internal” or “local” property of a positive integerp, only involving the finite set of positive divisors ofp.
Shift your focus outward instead of inward The number 35 can divide a product without dividing its individual factors For instance, while 35 divides the product of 7 and 10, it does not divide either 7 or 10 separately.
5 divides the product 7ã10, and then 5 divides the factor 10 in the product.
We define a positive integerpto beprime ifp >1 and p|aãb implies p|a or p|b
(1.31) for any integers a and b Primality may be considered as an “external” or
“global” property of a positive integerp, since it involves arbitrary integersa andb The two properties are summarized as follows:
(internal) irreducible: 0< d|p implies d= 1 or d=p (external) prime: p|aãb implies p|a or p|b
It is a feature of the integers that the internal concept of irreducibility agrees with the external concept of primality.
PROPOSITION 1.11 (“Prime” ≡“irreducible” for integers.) Let p >1be an integer.
(a) If pis prime, then it is irreducible.
(b) If pis irreducible, then it is prime.
To prove that if \( p \) is a prime number and \( d \) is a positive divisor of \( p \), then \( d \) must be either \( 1 \) or \( p \) Given that \( p = d' d \) for some positive integer \( d' \), it follows that \( p \) divides \( d' d \) Since \( p \) is prime, it must divide either \( d' \) or \( d \) If \( p \) divides \( d \), then by antisymmetry, \( d \) equals \( p \) Conversely, if \( p \) divides \( d' \), the same reasoning leads to \( d' \) being equal to \( p \), which implies \( d = 1 \) Thus, the only divisors of a prime number are \( 1 \) and the prime itself.
If \( p \) is an irreducible element and \( p \) divides \( a \cdot b \), then we can express \( a \cdot b = p^k \) for some integer \( k \) Given that \( p \) does not divide \( a \), it follows that \( p \) must divide \( b \) Since \( p \) is irreducible, its only positive divisors are 1 and \( p \), which implies that \( \text{gcd}(p, a) = 1 \) If \( \text{gcd}(p, a) \) were equal to \( p \), it would indicate that \( p \) divides \( a \) By applying Proposition 1.9, we can express \( \text{gcd}(p, a) \) as an integral linear combination.
1 =lp+ma ofpand a Postmultiplying bybgives b=lpb+mab
=lpb+mpk=p(lb+mk), so thatp|bas required.
With Proposition 1.11 proved, prime numbers (as in Figure 1.4) may be characterized equally well by either the irreducibility (1.30) or the primality (1.31) (See the Notes to this section on page 24.)
FIGURE 1.4: The first 50 prime numbers.
There is a traditional adjective for numbers which are not prime:
DEFINITION 1.12 (Composite numbers.) An integer n is said to be composite if n >1, butnis not prime.
Thus a number n > 1 is composite if it is not irreducible, i.e., if it has a nontrivial factorizationn=aãb with integers 1< a < nand 1< b < n.
The Fundamental Theorem of Arithmetic
The number 72 can be expressed as the product of its prime factors: 72 = 8 × 9 = 2³ × 3² This factorization can be arranged in different orders, such as 72 = 2 × 3 × 2 × 2 × 3 or 72 = 2 × 3 × 2 × 3 × 2 However, despite these rearrangements, the factorization remains unique According to the Fundamental Theorem of Arithmetic, every integer greater than one has a unique prime factorization.
1 has a factorization as a product of primes, unique up to reordering of the factors.
The existence part of the theorem is stated and proved as follows.
Each integern >1 may be expressed as a product of prime numbers.
Let B be the set of integers greater than 1 that cannot be expressed as a product of primes If the theorem is incorrect, then B contains at least one element, which, according to the Well-Ordering Principle, must have a least element b Since b is in B, it cannot be prime, implying it has divisors g1 and g2 such that b = g1g2, with 1 < g1, g2 < b As g1 and g2 are less than b, they can be expressed as products of primes This means that b can also be expressed as a product of primes, contradicting its membership in B Therefore, the assumption that the theorem is false leads to a contradiction, confirming that the theorem is indeed true.
Theorem 1.13 provides a method for factorizing integers greater than 1 into their prime components, albeit a slow one For instance, the integer 500 can be expressed as the product of its factors 50 and 10, which can further be broken down into primes, resulting in 500 = 5³ × 2² However, for less manageable numbers like 281957, the factorization process requires dividing the number by successive prime numbers such as 2, 3, 5, 7, and 11, continuing up to the square root of the number.
We now state the uniqueness half of the fundamental theorem.
Suppose that p1, p2, , prand q1, q2 , qsare primes Then if p1ãp2ã .ãpr=q1ãq2ã .ãqs, (1.33) r = s, and each pi on the left-hand side of (1.33) appears as a qj on the right-hand side of (1.33).
To prove Theorem 1.14, we will use a subsidiary result, a “lemma.”
Suppose that p1, q1, q2, , qs are primes Then if p1|q1ãq2ã .ãqs, (1.34) there is some1≤j≤ssuch that p1=qj.
To prove the lemma, we assume it is false and define the set S as the collection of natural numbers s for which there exist primes p1, q1, q2, , qs satisfying a specific condition, with the stipulation that p1 does not appear among the qj values Since we assume the lemma is false, S must be nonempty and has a smallest element s For this s, we examine the primes p1, q1, q2, , qs If p1 divides the product of q1, q2, , qs minus one, it would imply that p1 is among the qj values, contradicting the minimality of s Given that p1 is prime and the conditions hold, it leads to the conclusion that p1 equals qs, which contradicts our initial assumption Therefore, the lemma must be true.
To complete the proof of Theorem 1.14, suppose (1.33) holds Then p1|q1ãq2ã .ãqs.
By Lemma 1.15, there is some 1≤j≤ssuch thatp1=qj Then p2ãp3ã .ãpr=q1ã .ãqj − 1ãqj+1ã .ãqs.
According to Lemma 1.15, the term p2 cancels with certain qk on the right side of the equation This process continues, pairing the pi terms on the left side of (1.33) with the corresponding qj terms on the right Notably, the quantity r, representing the number of factors on the left side of (1.33), matches the number of factors present on the right side.
The Fundamental Theorem of Arithmetic establishes a relationship between the order relations ≤ and | within the set of natural numbers (N) It states that for distinct primes p1, p2, , pr and natural numbers e1, f1, e2, f2, , er, fr, the expression p1^e1 × p2^e2 × × pr^er divides p1^f1 × p2^f2 × × pr^fr if and only if e1 ≤ f1, e2 ≤ f2, , er ≤ fr This theorem highlights the significance of prime factorization in understanding the divisibility of natural numbers.
We conclude with an application of this idea.
DEFINITION 1.16 (Least common multiple.) Let a and b be nonzero integers The least common multiple lcm(a, b) of a and b is the minimum element of the set S = {m | m > 0, a | m , b | m} of positive common multiples ofa andb.
Write max{e, f} for the maximum of integers eand f The Fundamental Theorem of Arithmetic yields the following result Its proof is assigned as Exercise 39.
PROPOSITION 1.17 (Computing the least common multiple.) Leta=p e 1 1 ãp e 2 2 ã .ãp e r r andb=p f 1 1 ãp f 2 2 ã .ãp f r r for distinct primesp1,p2, , pr, and natural numberse1,f1,e2,f2, , er,fr Then lcm(a, b) =p max 1 { e 1 ,f 1 } ãp max 2 { e 2 ,f 2 } ã .ãp max r { e r ,f r }
Exercises
1 Supposex,y, and z are real numbers Ifx≤y≤z≤x, give a formal proof that y=zby use of transitivity and antisymmetry.
2 Suppose thatx0, x1, , xn are real numbers, withx0≤x1≤ ã ã ã ≤xn.
Ifxn≤x0, show that x0=xr for 1≤r≤n.
5 Find the least element infS of the setS from Example 1.2.
6 Find the smallest integer nfor which 2 n < n!.
7 Let S be a nonempty subset of N Let s be an element of S The intersection {0,1, , s−1} ∩S denotes the set of elements of S less thans.
(a) If the intersection{0,1, , s−1}∩Sis empty, show that infS=s. (b) If the intersection {0,1, , s−1} ∩S is nonempty, show that infS= min({0,1, , s−1} ∩S).
(b) Can you prove (1.35) directly, without using induction?
(a) Show that n | m implies |n| ≤ |m| (In words: each divisor of a nonzero integer is no greater than that integer in absolute value.)
(b) If you are uncomfortable with absolute values, show instead that n|m impliesn 2 ≤m 2
(c) Conclude that the set of divisors ofmis finite.
12 Show that every integer divides zero.
13 There are 36 inches in a yard, and 100 centimeters in a meter.
(a) In how many ways can a piece of wood a yard long be divided into equal pieces whose length is an integral number of inches?
(b) In how many ways can a piece of wood a meter long be divided into equal pieces whose length is an integral number of centimeters?
14 Prove Proposition 1.5 [Hint: To prove the antisymmetry (A) that does not hold for divisibility on Z, consider the solutions x of the equation x 2 = 1 inZandN.]
15 Describe the divisibility relation|on the setRof real numbers.
16 Consider running the Division Algorithm on the inputsa= 1 andd= 0.
(a) For the setS of (1.16), what is infS?
(b) Show that a unique remainderris obtained, but that the quotient qis not unique.
17 Letdbe a positive odd number Show that for each integera, there are unique integersqandr such that a=dq+r with |r|< d/2.
In other words, each integeracan be approximated by a multiple ofd to within an error of less thand/2.
18 Consider the 16×11 rectangular array of 176 pixels in a display.
Pixels are organized in an array based on their coordinates, with the bottom left pixel at (0,0) and the top right at (15,10) Each pixel is assigned a unique address ranging from 0 to 175, calculated using the formula a = 11q + r, where (q, r) represents the pixel's coordinates.
(a) What is the address of the pixel with the black square?
(b) What are the coordinates of the pixel with address 106?
19 Let d >1 be a fixed integer, known as thebase To represent a given positive integernas a sequencen=nknk − 1 n2n1 of digits in based, with 0≤ni< dfor 1≤i≤k, consider the following algorithm: (a) Initialize withq0=nandi= 1 ;
(b) At Step (i), obtain qi − 1=qid+ni with the Division Algorithm;
(d) Otherwise, replaceibyi+ 1 and return to (b).
20 Express the base 10 number 3817 as ahexadecimal (base 16) number. Use A= 10, B = 11, C = 12, D = 13, E = 14, F = 15 for the digits above 9.
21 In a certain state, persons under age 21 are not allowed into bars that serve intoxicating beverages If 21 were read as anoctal number (to base
8), what would be the minimum age (to the usual base 10) of persons allowed into bars?
(a) Identify the set of positive divisors of 18.
(b) Identify the set of positive divisors of 24.
(c) Identify the set S of common divisors of 18 and 24.
(d) Identify gcd(18,24) as the largest element of the setS.
23 Find all pairs of relatively prime positive integers less than 10.
24 Show that 1 is the only positive integer that is relatively prime to every positive integer.
In a gearbox, gear wheel A with 'a' teeth meshes with gear wheel B having 'b' teeth, allowing both to rotate together multiple times Each tooth of gear A will mesh with each tooth of gear B at some point if and only if the numbers of teeth 'a' and 'b' are relatively prime.
To prove Proposition 1.9 directly, we can utilize the Well-Ordering Principle, which states that every non-empty set of positive integers has a least element Consider the set S, defined as the collection of all positive integral linear combinations of two integers, a and b By applying the Well-Ordering Principle, we can demonstrate that the greatest common divisor (gcd) of a and b is indeed the smallest element in this set S This establishes that the gcd is the least positive integer that can be expressed as a linear combination of a and b, thereby confirming the proposition without resorting to the Euclidean Algorithm.
29 Letc be a positive common divisor of two nonzero integersaandb.
30 For nonzero integersa,b, andc, show that gcd(ac, bc) = gcd(a, b)ãc ifc >0.
31 Letaandbbe distinct nonzero integers Show that the greatest common divisor gcd(a, b) can be expressed in infinitely many distinct ways as an integral linear combination gcd(a, b) =la+mb ofaandb.
32 Use the Euclidean Algorithm to determine gcd(109,60), and to express it as an integral linear combination of 109 and 60.
33 Show that 2n+ 1 and 3n+ 1 are coprime for all natural numbersn.
34 Show that the Euclidean Algorithm will make at most b calls to the Division Algorithm when it computes gcd(a, b) witha > b >0.
35 (a) In how many ways can 72 be expressed as an ordered product of three twos and two threes?
(b) Interpret each such expression 72 =p1p2p3p4p5 (withpi= 2 or 3) as a walk from 1 to 72 along the path
(c) Conversely, show that each path from 1 to 72, following the arrows at each step, determines an ordered factorization.
36 (a) Show that a composite numberbhas a prime divisorpwithp≤√ b.
(b) Conclude that an integer n is prime if it is not divisible by any prime less than or equal to√ n.
37 Factorizeb= 281957 as a product of primes.
38 Can you prove thatn 2 −n+ 41 is prime for each natural number n?
40 For positive integersaandb, show that an integer is a multiple of both aandb if and only if it is a multiple of lcm(a, b).
41 Use the Fundamental Theorem of Arithmetic to obtain a formula for gcd(a, b), similar to the formula for lcm(a, b) given in Proposition 1.17.
42 For nonzero integersa,b, and c, show that gcd(a, bc) = 1 if and only if both gcd(a, b) = 1 and gcd(a, c) = 1.
43 For positive integersaandb, prove aãb= gcd(a, b)ãlcm(a, b).
[Hint: Prove e+f = min{e, f}+ max{e, f} for natural numberseandf.]
44 (a) Give an example of prime numbersp1,p2 and natural numberse1, f1,e2,f2such that lcm p e 1 1 p e 2 2 , p f 1 1 p f 2 2
=p max 1 { e 1 ,f 1 } ãp max 2 { e 2 ,f 2 } (b) Why does this not contradict Proposition 1.17?
45 (a) Letp1= 2, p2= 3, p3= 5, , prbe the firstrprimes Show that n=p1ãp2ã .ãpr+ 1 is not divisible by any ofp1, p2, , pr.
(b) Applying Theorem 1.13 ton, deduce that there is a prime number pswithpr< ps≤n.
(c) Conclude that there is an infinite number of primes.
46 Letnbe a positive integer A positive integerdis said to be aunitary divisor ofnif:
In this case,nis said to be aunitary multiple ofd.
(a) Determine the unitary divisors of 72 and 1200.
(b) Determine the least common unitary multiple of 18 and 45. (c) Show that there is no least common unitary multiple of 3 and 9.
47 Consider a world in which the only positive numbers are the numbers
1,5,9,13,17,21,25,29, (1.36) of the form 4r+ 1 for r in N Suppose that the numbers are only multiplied, not added.
(a) Show that the product of two numbers from the list (1.36) also appears in the list.
(b) Show that the numbers below 25 in the list (1.36) are irreducible within this alternative world.
(c) Show that 9 divides 21ã21, but 9 does not divide 21.
(d) Conclude that in this world, the property of being prime is distinct from the property of being irreducible.
48 A subsetS ofZis said to be summary if the two conditions
(ii) m=n+rfor some elementsofS are equivalent for each ordered pair (n, m) of elements ofS.
(b) IfS containsNas a proper subset, show thatS is not summary.
49 For positive integersa, bandc, define A= gcd(a, b) andC= gcd(b, c). Show that gcd(A, c) = gcd(a, C).
Xn i=1 i(i−1)(i−2) .(i−r) = (n+ 1)n(n−1) .(n−r) r+ 2 for each natural number n [Compare Exercise 9 for the caser= 0.]
51 Definef(n) = 2 n −1 for each positive integern.
(a) Ifnis composite, show thatf(n) is composite.
(b) Ifpis prime, show thatf(p) may be composite.
Study projects
1 For a sport competition of your choice (say one season of a particular league), determine whether the transitivity rule (1.6) and antisymmetry rule (1.7) apply.
To find the minimum value, minS, from a finite set S of n natural numbers, a procedure can be designed that requires only n−1 comparisons between pairs of elements in S This approach is analogous to the structure of brackets in a single-elimination sports competition involving n members, as illustrated in Figure 1.5 for the case when n equals 6.
3 The number 946 is a multiple of 11 Also, the difference between the respective sums 9 + 6 and 4 of the odd-placed and even-placed digits of
946 is (a multiple of) 11 Is this just a coincidence, or can you extend the observation to derive a quick way of recognizing multiples of 11?
Proposition 1.6 is essential because it addresses the limitations of computational tools in handling large integers when calculating unique quotients and remainders Simply stating that a computer or calculator can generate these values for given dividend and divisor is insufficient, as it does not account for the potential size of the integers involved Many calculators and computers may struggle or fail to process extremely large integers, highlighting the necessity of Proposition 1.6 to ensure the reliability and validity of mathematical operations in all scenarios.
The efficiency of the Euclidean Algorithm can be analyzed by examining the number of steps it takes to compute the greatest common divisor (GCD) of two integers Exercise 34 provides a basic estimate for the steps needed, but there is potential to refine this estimate further For any positive integer k, it is possible to identify pairs of integers a and b, where a is greater than b and both exceed k, such that the Euclidean Algorithm requires approximately b steps to determine their GCD.
6 Greatest common divisors Consider the following method to find the greatest common divisor of positive integersaandb:
(a) If a and b are even, remember gcd(a, b) = 2ãgcd(a/2, b/2) and compute gcd(a/2, b/2) instead (Compare Exercise 29.)
(b) If sayais even andbis odd, remember gcd(a, b) = gcd(a/2, b) and compute gcd(a/2, b) instead.
(c) If aand b are odd, say a > b, remember gcd(a, b) = gcd(a−b, b) and compute gcd(a−b, b) instead.
To compute the greatest common divisors (GCD) of large integer pairs, utilize this effective method, which offers a distinct approach compared to the traditional Euclidean Algorithm Additionally, this new method can be adapted to express gcd(a, b) as a linear combination of the integers a and b, enhancing its utility in various mathematical applications.
Notes
Euclid (Eυκλειδης) was a Greek mathematician living in the third century B.C.
When discussing integers, it has been traditional to define a number pto be “prime” if it is irreducible The proof of primality as we have defined it
Euclid’s Lemma, as outlined in Proposition 1.11(b), highlights the distinction between internal and external properties, a differentiation that gained prominence in the 19th century During this period, mathematicians began exploring various factorization systems, such as the one mentioned in Exercise 47, revealing that these properties may not always align.
Algebra, just like calculus, works with many different kinds of functions In this chapter, we will learn how to specify functions, and how to compose them.
We will also see how functions form mathematical structures: semigroups,monoids, and groups.
Specifying functions
In mathematics, a function f: X → Y is a rule that assigns a unique element f(x) in the codomain Y to each element x in the domain X The elements x are referred to as the arguments, while f(x) represents the function's values For instance, the squaring function sq: Z → N is defined by sq(n) = n² for integers n, and the absolute value function abs: Z → N is defined by abs(n) = |n| In this context, the domain of the squaring function is Z, and its codomain is N It's important to note that functions can differ based on their codomains, as seen with sq: Z → Z defined by sq(n) = n², which is distinct from sq: Z → N Two functions f: X → Y and g: Z → T are considered equal if they satisfy three specific conditions.
• The domainX off equals the domainZ ofg ;
• The codomain Y off equals the codomainT ofg ;
• The function valuesf(x) andg(x) agree on each argumentxinX.
The reason for including the domain and codomain in the specification of a function will become apparent in Section 2.5.
A function \( f \) must assign a unique value \( f(x) \) to each argument \( x \) within its domain For example, a function defined as \( \text{inv}: \mathbb{R} \to \mathbb{R} \) with \( \text{inv}(x) = x - 1 \) is invalid for the element 0 in the domain Additionally, not every element \( y \) in the codomain of a function \( f: X \to Y \) needs to correspond to an actual function value \( f(x) \) While every natural number appears as the absolute value of some integer, certain natural numbers, like 3, do not represent the square of any integer The only requirement for the codomain is that it must be sufficiently large to encompass all possible function values For instance, defining a function \( \text{sqrt}: \mathbb{N} \to \mathbb{N} \) with \( \text{sqrt}(n) = \sqrt{n} \) is not feasible since the square root of a natural number may not yield another natural number.
3 does not lie inN But setting sqrt :N→R would be fine, since square roots of natural numbers are always real numbers.
To ensure the function rule operates effectively, the domain must be sufficiently small, while the codomain should be expansive enough to encompass all possible function values In a function denoted as f: X→Y, the image of the function is defined as the set f(X) = {f(x) | x ∈ X}, representing the function values derived from the domain elements For instance, the image of the squaring function illustrates this concept effectively.
In certain situations, it can be beneficial to define a function without explicitly naming it To achieve this, we will use barred arrows to indicate the function's action at the element level, for example, sq : n7 → n² Consequently, the squaring function can be represented in this manner.
The notation Z→N and n7→n 2 allows us to express functions without relying on the artificial designation of "sq." This barred arrow notation proves particularly useful when analyzing functions that involve sets as their arguments or values For instance, if A and B are sets, then f: A→B indicates a function with domain A and codomain B, while f: A 7→ B signifies that the function f maps the argument A to the value B.
In calculus, the notation “f(x)” represents a function, as seen in expressions like “the function sin(x).” Conversely, in algebra, “f(x)” specifically refers to the value of the function f at a given argument x.
Do not confuse functions with elements of their domains or codomains.
Composite functions
In mathematics, when we have two functions, f: X → Y and g: Y → Z, where the codomain Y of f serves as the domain for g, we can create a composite function g◦f: X → Z defined as g(f(x)) This composite function inherits the domain from f and the codomain from g For instance, by composing the squaring function sq: Z → Z with the absolute value function abs: Z → N, we obtain the new function abs◦sq: Z → N, which is expressed as n ↦ |n²|.
In fact, since |n 2 | = n 2 for any natural number n, this composite function abs◦sq is the same as the original squaring function (2.1).
Composition of functionsf :X →Y andg:Y →Z may be illustrated by an arrow picture, strongly reminiscent of the picture of transitivity on page 2:
If you find yourself getting confused by a profusion of functions, it can be helpful to draw such pictures.
Suppose that there are functions f :X →Y, g :Y →Z, andh:Z →T. These functions may be composed in two different ways: h◦(g◦f) :X →T;x7→h(g◦f(x)) and
(h◦g)◦f :X →T;x7→(h◦g)(f(x)). However, h(g◦f(x)) =h(g(f(x))) = (h◦g)(f(x)) for allxinX, so in fact we have the associative law h◦(g◦f) = (h◦g)◦f (2.5) forX −→ f Y −→ g Z −→ h T.
Linear functions
Linear functions form one of the most important classes of functions For positive integersmandn, consider the set
) of m×n real matrices In particular, R 1 2 is the set of 2-dimensional real column vectors x x1 x2 withx1,x2 inR Each 2×2 real matrix
LA(x) =Ax using matrix multiplication Note that
, so the linear functionLA determines the matrixA.
B b11b12 b21b22 with a corresponding linear function LB :x7→Bx, the matrix product BA is defined by b11b12 b21b22 a11a12 a21a22 b11a11+b12a21b11a12+b12a22 b21a11+b22a21b21a12+b22a22
This apparently complicated formula is designed to make the equation
The equation LBA(x) = LB◦LA(x) illustrates that matrix multiplication corresponds to the composition of linear functions for all x in R Notably, the associativity of matrix multiplication stems directly from the associativity of function composition, highlighting a fundamental relationship between these mathematical operations.
Semigroups of functions
A self-map is a function f: X → X that maps a set X to itself, with X referred to as the base set for the function.
DEFINITION 2.1 (Semigroup of functions.) A set S of functions f : X → X with domain X and codomain X is said to be a semigroup of functions on the base setX if f and g in S imply g◦f in S (2.9)
We also say that the set S is closed under composition.
Iff is an element of a semigroupS of functions, the powersf n for positive integersnare defined recursively byf 1 =f andf n+1 =f n ◦f.
Here are some important examples of semigroups of functions.
For a base setX, defineX X to be the set of all functions fromX toX Then
X X forms a semigroup of functions onX (For a justification of the notation, see Exercise 5.)
Let X be a set and Y a subset of X For every element y in Y, we define a constant function cy: X → X, where cy(x) = y It follows that for any element x in X and for any y, z in Y, the composition cz ◦ cy(x) equals cz(y), which simplifies to z = cz(x) Therefore, we conclude that cz ◦ cy = cz.
CY ={cy|y in Y} (2.10) forms a semigroup of functions onX.
Recall that in calculus, a functionf :R→Risnondecreasing ifx≤yimplies f(x)≤f(y) Then the set of nondecreasing functions forms a semigroup of functions onR(Exercise 6).
For each real numberr, define theshift byrto be the map σr:R→R;x7→r+x Note that for real numbersr,s, andx, we have σr◦σs(x) =r+ (s+x) = (r+s) +x=σr+s(x), soσr◦σs=σr+s Thus the set Σ of shifts forms a semigroup of functions on
R For a positive integernand real numberr, the equation σ n r =σnr (2.11) holds (Exercise 9).
A function \( f: \mathbb{N} \rightarrow \mathbb{N} \) is defined as computable if there exists a computer program that outputs \( f(n) \) for any natural number input \( n \) When both \( f \) and \( g \) are computable functions, their composition \( g \circ f \) is also computable Specifically, for an input \( n \), a program for \( g \circ f \) can take the output \( f(n) \) from the program for \( f \) and use it as input for the program for \( g \), thereby producing the output \( g \circ f(n) \) Consequently, the collection of computable functions constitutes a semigroup of functions on \( \mathbb{N} \).
DEFINITION 2.7 (Identity function.) For any set X, the identity function idX is defined byidX :X →X;x7→x
Note that for setsX,Y andf :X→Y, we have idY ◦f =f =f◦idX (2.12)
A monoid of functions on a base set X is defined as a set S of self-maps that not only forms a semigroup but also includes the identity function idX as one of its elements.
Clearly, X is a monoid on X A notable example is the identity function idN on the set of natural numbers N, which is computable When given a natural number n as input, a "lazy" program can be designed to immediately return n as output Therefore, the set of computable functions illustrated in Example 2.6 forms a monoid of functions on N.
For an elementf of a monoid of functions on a set X, the power notation may be extended by settingf 0 = idX.
By (2.8), the set L(2,R) of linear functions fromR 1 2 to itself forms a semigroup of functions onR 1 2 Now for the 2×2identity matrix
, (2.13) the linear functionLI 2is the identity function id R 1
2, so L(2,R) forms a monoid of functions onR 1 2
Injectivity and surjectivity
A function f: X → Y must assign a unique value f(x) in the codomain Y for every argument x from the domain X, although it is possible for different arguments to yield the same function value For example, in the squaring function sq: Z → N, both sq(−5) and sq(5) equal 25, illustrating that different inputs can produce identical outputs.
DEFINITION 2.10 (Injective function.) A function f : X →Y is said to be injective, or an injection, or “one-to-one,” if f(x) =f(x ′ ) implies x=x ′ (2.14) for all elementsxandx ′ of the domain X.
To express the injectivity condition, the equation f(x) = y must have a unique solution x in the domain X for every element y in the image of f Notably, any function with an empty domain is considered injective For instance, the restricted squaring function sq: N → N, defined by n ↦ n², is injective, whereas the original squaring function sq: Z → N is not This illustrates the importance of the domain in defining a function's properties.
PROPOSITION 2.11 (Retracts of injective functions.)
Letf :X →Y be injective, with nonempty domain Then there is a function r:Y →X (2.17) such that r◦f = idX (2.18)
To establish the function r:Y→X, we begin by selecting an element x0 from the set X For any element y that is not part of the image f(X), we define r(y) as x0 For elements y within the image f(X), the equation f(x) = y guarantees a unique solution due to the injective nature of f This unique solution is designated as r(y) Consequently, we have r◦f: X→X, and for every element x in X, it follows that r◦f(x) = r(f(x)).
DEFINITION 2.12 (Retracts.) A function r : Y → X is called a retractof a function f :X →Y if r◦f = idX.
PROPOSITION 2.13 (Functions with retracts are injective.)
If a function f :X →Y has a retract, then it is injective.
PROOF Letr:Y →X be a retract forf Then f(x) =f(x ′ ) implies x=r◦f(x) =r◦f(x ′ ) =x ′ forx, x ′ in X.
Proposition 2.11 establishes that every injection with a nonempty domain possesses a retract It is important to note that an injection \( f \) can have multiple retracts due to the arbitrary selection of the element \( x_0 \) during the proof of the retract's existence (refer to Exercise 22) Additionally, the identity function \( \text{id}_{\emptyset} \) on the empty set serves as its own retract.
DEFINITION 2.14 (Surjective function.) A function f : X → Y is said to be surjective, or a surjection, or to map onto its codomain, if the codomain and image coincide: Y =f(X).
A solution to the equation f(x) = y exists for every element y in the codomain, indicating that the preimage f⁻¹{y} must be nonempty for each y in Y It is important to note that the only surjective function with an empty domain is the identity function on the empty set The absolute value function from integers to natural numbers is surjective, while the absolute value function from integers to integers is not, as it does not satisfy the equation for all values.
|n|=−5 has no solution n This shows why the codomain is an integral part of the specification of a function.
PROPOSITION 2.15 (Sections of surjective functions.)
Let f :X →Y be surjective Then there is a function s:Y →X (2.20) such that f◦s= idY (2.21)
PROOF IfXis empty, then so isY, andf is just the identity function id∅.
In this scenario, the identity function \( id∅ \) ensures the functionality of equation (2.21) Assuming that \( X \) is nonempty, for every element \( y \) in \( Y \), there exists an element \( x \) in \( X \) such that \( f(x) = y \) By selecting the function values \( s(y) \) as a specific element \( x_y \), we can define a function \( s: Y \rightarrow X \) Consequently, for each element \( y \) in \( Y \), the relationship \( f \circ s(y) = f(s(y)) \) holds true.
DEFINITION 2.16 (Sections.) A function s : Y → X is called a sectionof a function f :X →Y if f◦s= idY.
PROPOSITION 2.17 (Functions with sections are surjective.)
If a function f :X →Y has a section, then it is surjective.
PROOF Lets:Y →X be a section forf Then f s(y)
Proposition 2.15 establishes that every surjection has at least one section It is important to note that a surjection can possess multiple sections due to the arbitrary selection of elements in the proof of the section's existence.
Isomorphisms
DEFINITION 2.18 (Bijective function, isomorphism of sets.) A function f :X →Y is said to be bijective, or an isomorphism (of sets), or a bijection, if it is both injective and surjective.
Let f :X →Y be a bijection Then there is a function g:Y →X (2.22) such that g◦f = idX and f◦g= idY (2.23)
PROOF By Propositions 2.11 and 2.15, we have r◦f = idX and f◦s= idY (2.24)
By the associativity of function composition, we have r=r◦idY =r◦f◦s= idX◦s=s Defineg=r=s Then (2.23) follows from (2.24).
DEFINITION 2.20 (Inverse, invertible function.) For a function f : X →Y, a function g : Y →X satisfying g◦f = idX andf ◦g = idY is called an inverse of f A function is described as invertible if it has an inverse.
The exponential function, defined as exp: R → (0, ∞) with the mapping x ↦ e^x, is invertible over the set of positive real numbers (0, ∞) Its inverse is the natural logarithm function, log: (0, ∞) → R This relationship is captured in the equations log_e x = x for real numbers x and e^(log y) = y for positive real numbers y, highlighting the fundamental connection between these two mathematical functions.
Proposition 2.19 demonstrates that bijections are invertible, meaning that the inverse of an invertible function \( f \) serves as both a retraction and a section for \( f \) Consequently, an invertible function \( f \) is characterized as both injective and surjective, confirming that invertible functions are indeed bijective.
Example 2.22 (Inverses of real shifts.)
For each real numberr, the shift σr of Example 2.5 has the shift σ − r as an inverse Thus the shifts are bijective.
Recall that sections and retractions need not be unique With inverses, the situation is different.
The inverse of an invertible function is unique.
PROOF Let g : Y → X be an inverse of a function f : X → Y If a functionh:Y →X satisfies h◦f = idX or f◦h= idY , then h=h◦idY =h◦f ◦g= idX◦g=g or g=g◦idY =g◦f◦h= idX◦h=h respectively In particular,g:Y →X is uniquely specified by (2.23).
In view of Propositon 2.23, we can speak ofthe inversef − 1 of an invertible functionf Note that
(f − 1 ) − 1 =f for an invertible functionf, so that inverses of invertible functions are again invertible.
If there is an isomorphism f : X →Y from a setX to a set Y, we often write
Sets X and Y are considered isomorphic if X ∼= Y (2.25), indicating a one-to-one correspondence between them This relationship is reciprocal, meaning Y ∼= X due to the inverse isomorphism f − 1 To demonstrate that two sets are isomorphic, the common method involves identifying two mutually inverse functions, f: X → Y and g: Y → X.
The set of integers Z is isomorphic to the subset of natural numbers N through the functions f and g The function f maps natural numbers to integers by defining f(0) = 0, f(2r) = r for non-negative integers r, and f(2r−1) = −r for positive integers r Conversely, the function g maps integers to natural numbers, with g(n) = 2n for n ≥ 0 and g(n) = 2|n| − 1 for n < 0 Together, these functions f and g serve as mutual inverses, establishing a clear relationship between the two sets.
The proof of the following proposition is left as Exercise 34.
(a) If f andg are injective, then so is g◦f.
(b) If f andg are surjective, then so is g◦f.
(c) Iff andgare bijective, then so isg◦f Moreover,(g◦f) − 1 =f − 1 ◦g − 1
For every natural number \( n \), we define the finite set \( n = \{0, 1, 2, \ldots, n-1\} \), which consists of natural numbers less than \( n \) and contains exactly \( n \) elements It is important to note that when \( n = 0 \), the set is considered the empty set Furthermore, if a finite set \( X \) contains \( n \) elements, it can be represented in a similar manner.
X ={x0, x1, , xn − 1}, then there is a bijection k:n→X;i7→xi (2.27)
Indeed, a setX hasnelements if and only if there is a bijection k:n→X.
The size, order, or cardinality of a finite set X, denoted as |X|, represents the number of elements within that set According to Proposition 2.25(c), two finite sets X and Y are isomorphic if and only if their cardinalities are equal, meaning |X|=|Y|.
Groups of permutations
DEFINITION 2.27 (Groups of permutations.) Let X be a set. (a) A bijective functionf :X→X is called a permutationof the setX.
(b) A set Gof permutations on X is said to be a group of permutationsof
X or a permutation groupon the set X if it is a monoid of functions satisfying the additional property f in G implies f − 1 in G (2.28)The property (2.28)is known as closure under inversion.
The set of all permutations of a given set X, denoted as X!, forms a semigroup of functions on X according to Proposition 2.25(c) As idX is a permutation, X! also constitutes a monoid of functions on X Furthermore, since the inverses of invertible functions are themselves invertible, X! is classified as a group of permutations This group is referred to as the symmetric group on X.
Example 2.28 (The group of real shifts.)
The monoid ΣRof shifts onR(compare Example 2.5 and Exercise 8) forms a group of permutations ofR, since (σr) − 1 =σ − r as noted in Example 2.22.
The set Σ + R = {σr | r ≥ 0} represents shifts by nonnegative real numbers and constitutes a monoid of permutations on R However, it fails to qualify as a permutation group on R because it does not meet the closure under inversion property.
Example 2.29 (The symmetric groups Sn.)
For every natural number n, define Sn as the symmetric group n! on the set of natural numbers less than n The group Sn is referred to as the symmetric group on n symbols Additionally, for a set of distinct elements {a1, a2, , ar} within n, a cycle can be formed.
In the context of permutations, a bijection from the set of natural numbers n to itself can be represented by cycles, such as (a1 a2 ar), where elements are mapped in a specific manner, with certain elements being excluded from the cycle The identity permutation is denoted as id n, represented by the cycle (0) Two cycles, such as (a1 a2 ar) and (b1 b2 bs), are considered disjoint if their corresponding sets share no common elements Notably, every permutation can be expressed as a product of mutually disjoint cycles, illustrating the fundamental structure of permutations in combinatorial mathematics.
07→3,17→1,27→7,37→6,47→8,67→0,77→2,87→4 in S9 may be written as the product (0 3 6)◦(2 7)◦(4 8) of disjoint cycles.
By following the effect of these functions, it is easy to express products of permutations as products of disjoint cycles For example,
Example 2.30 (The cyclic groups Cn.)
For each positive integern, thecyclic groupCnconsists of thenpermutations
, and (0) fromSn These permutations correspond to the respective counter- clockwise rotations of a regularn-gon by the angles
TheKlein 4-groupV4is the set
{(0), (0 1)(2 3), (0 2)(1 3), (0 3)(1 2)} of permutations It forms a group of permutations of the setnfor each natural numbern≥4 (Exercise 40).
The cycle notation is extended to denote permutations of arbitrary sets. For example,
(A♥3♥J♥7♥)◦(K♥4♥)◦(10♥9♥2♥) might denote a shuffle of the suit♥of hearts from (1.3) For an application of permutations to elementary cryptography, see Study Project 3 at the end of the chapter.
Exercises
1 Show that the empty set∅={ }cannot be the codomain of a function f :X→∅with nonempty domainX.
2 Draw an arrow picture to illustrate all the functions f, g, h, g◦f, h◦(g◦f), h◦g, (h◦g)◦f involved in the associative law (2.5).
3 Verify that (2.8) holds for all 2-dimensional real column vectorsx.
4 Letm,n, andpbe positive integers Show that for anm×nreal matrix
5 Let X be a finite set with n elements Show that the semigroupX X hasn n elements.
6 Show that the set of nondecreasing functions forms a monoid of functions onR.
7 A function f : R→R is said to be strictly increasing if x < yimplies f(x)< f(y) Show that the set of strictly increasing functions forms a monoid of functions on R.
8 Show that the set Σ of shifts in Example 2.5 forms a monoid of functions onR.
9 Verify the equation (2.11), and show that it also holds forn= 0 (Hint: Consider using induction withn= 0 as the basis.)
10 For each natural numbern, define thepower map pn:R→R;x7→x n (2.29)
Show that the setP of all power maps forms a monoid of functions on the setR.
11 Letn be an integer such thatnx=cn(x) for all integersx Show that n= 0.
12 LetY be a subset of a setX Under what conditions onX andY does the set (2.10) of constant functions form a monoid of functions onX?
13 A functionf :R→Ris said to be affine if there are real numbers m andc such that f :x7→mãx+c (2.30)
Show that the setAof all affine functions forms a monoid of functions on
R (In calculus, affine functions are often called “linear,” but in algebra it is best to reserve this term for the casec= 0.)
14 A functionf :R→Ris said to be a polynomial function if there is a natural numbernand real numbersf0, f1, , fn such that f(x) =fnx n + .+f1x+f0 forxinR.
(a) Show that the set of all polynomial functions forms a monoid of functions onR.
(b) Show that there is a functionf :R→Rwhich is not a polynomial function.
15 Show that the setC(R) of all continuous functionsf :R→Rforms a monoid of functions on R.
16 Let r be a positive integer Let C r (R) denote the set of all functions f :R→Rfor which ther-th derivativef r (x) exists at each real number x Show thatC r (R) forms a monoid of functions onR.
17 Let X be an infinite set A function f : X → X is said to be almost identical if the set
{x∈X |x6=f(x)} of elements x of X, differing from their image f(x) under f, is finite. LetF be the subset ofX X consisting of the almost identical functions. Show thatF is a monoid of functions.
18 Show that the power mappnof (2.29) is injective if and only ifnis odd.
19 Show that the power mappn of (2.29) is surjective if and only ifn is odd.
20 Show that sections are injective.
21 Show that retracts are surjective.
22 Show that the injection (2.16) has infinitely many retracts.
23 Show that the surjection (2.2) has infinitely many sections.
24 Consider the function f :R→R;x7→x(x−1)(x+ 1).(a) Show thatf is not injective.
(b) Using the Intermediate Value Theorem or otherwise, show thatf is surjective.
(b) Is the natural logarithm function a retraction forf?
(c) Show thatf is not surjective.
26 Let f : X → X be a function with finite domain X Show that the following three conditions are equivalent:
Show that the following three conditions are equivalent:
(a) The linear functionLA is injective;
(c) The linear functionLA is surjective.
In a function f: X → Y, where X is a finite set with m elements and Y is a finite set with n elements, if m exceeds n (m > n), it follows that f cannot be injective This conclusion is derived from the Pigeonhole Principle, which states that if m pigeons are placed into n holes and m is greater than n, at least two pigeons must occupy the same hole.
29 Show that the setRof real numbers is isomorphic to its proper subset
(0,∞) of positive real numbers (Compare Example 2.21.)
30 Show that a finite setX cannot be isomorphic to a proper subsetY of
X (Recall that a subsetY of a setX isproper if there is an elementx ofX that does not lie inY.)
(a) Show that there is a unique subsetY ′ ofY such that theminimal corestriction
(b) What is the minimal corestriction of the absolute value function (2.19)?
(a) Show that there is a subsetX ′ ofX such that the function
(b) Give an example to show that the subsetX ′ need not be unique.
33 Let f : X → Y be a function with nonempty domain X Show that there is a function g:Y →X such thatf =f ◦g◦f.
35 LetX andY be finite sets Show thatX ∼=Y if and only if |X|=|Y|.
36 LetX be a set Suppose that a nonempty semigroupGof permutations ofX satisfies the property (2.28) of closure under inversion.
(a) Show that idX lies inG.
(b) Conclude thatGis a permutation group onX.
(0 7 2 1)◦(3 4 5 6)◦(0 6 2 4)◦(3 1 5 7) as a product of disjoint cycles.
38 Letβ and α= (x1x2 xr − 1 xr) be permutations of a finite setX Show that β◦α◦β − 1 = β(x1)β(x2) β(xr − 1)β(xr)
39 Let nbe a positive integer Show that Sn hasn! elements: To specify a permutation αofn, there aren choices forα(0), then n−1 choices forα(1) (avoidingα(0)), thenn−2 choices forα(2) (avoidingα(0) and α(1)), and so on.
40 Show thatV4 forms a group of permutations of each setnwithn≥4.
41 Show that for distinct elementsa1, a2, , ar − 1, arof the setn,
42 Show that for distinct elementsa1, a2, , ar − 1, arof the setn,
= (b1b2 bs − 1 bs)◦(a1 a2 ar − 1 ar) for disjoint cycles (a1 a2 ar) and (b1 b2 bs).
44 LetX be a finite set withnelements Show that the symmetric group
45 Let Aff(R) be the set of all affine functions (2.30) withm6= 0 (compare Exercise 13) Show that Aff(R) forms a group of permutations ofR.
46 Suppose that a groupGof permutations ofRcontains the real shiftsσa andσb for real numbersaandb.
(a) Show thatGcontainsσma for each positive integerm.
(b) Show thatGcontainsσma for each integerm.
(c) Show thatGcontainsσma+nbfor each integral linear combination ma+nbofaandb.
47 Suppose that a groupGof permutations ofRcontains the real shiftsσ2 andσ5 Show thatGcontainsσn for each integern.
48 LetM be a monoid of functions on a base setX Define
Show thatS is a monoid of functions onX.
49 Let Gbe the set of all permutations αof the set {0,1,2,3} such that α(0)