Homework 3
MATH 327 A / 574 A
美国数学代写 Choose a sufficiently small integer k (e.g., n or 2n) such that k is less than thelength of (a, b), and then “scale the problem” by a factor of k.
Problem 1. §1.2 Exercise 4 美国数学代写
In this problem, we will make use of the following lemma.
Lemma. Let S ⊆ R. If S has a maximum value, then S is nonempty and bounded above and max S = sup S. Similarly, if S has a minimum value, then S is nonempty and bounded below and min S = inf S. 美国数学代写
Proof. Let S ⊆ R, and suppose first that S has a maximum value M = max S. Then, by the definition of the maximum of a set of real numbers, M ∈ S and x ≤ M for all x ∈ S. The former condition implies that S ƒ= ∅ and the latter is precisely what it means for S to be bounded above by M , so by the Completeness Axiom, S has a least upper bound M ∗ = sup S. Since M is an upper bound for S, we have M ∗ ≤ M by the definition of the least upper bound. Conversely, since M ∈ S and M ∗ is an upper bound for S, we have M ≤ M ∗. Therefore, M = M ∗ by the second positivity axiom; that is, max S = sup S.
If instead S has a minimum value m, then by the same reasoning, S is nonempty and boundedbelow, so it has a greatest lower bound m∗ = inf S by Theorem 1.4. Again, a nearly identical argument shows that both m ≤ m∗ and m∗ ≤ m. □
(a)Let A = {1/n : n ∈ N}.Then
max A = sup A = 1 and inf A = 0,
but min A is undefined.
Proof. Let A = {1/n : n ∈ N}, and recall that, if 0 < x < y, then 0 < 1/y < 1/x. Since min N = 1—that is, since 1 ≤ n for all n ∈ N—we have
for all n ∈ N. In particular, 1 is an upper bound for A, and since 1 = 1/1 ∈ A, it follows from the definition of the maximum of a set of real numbers that 1 = max A.
Hence, sup A exists and is equal to 1 by the preceding lemma. 美国数学代写
Next, since each element of A is the multiplicative inverse of a positive number, each element of A is (strictly) positive. That is, 0 < x for all x ∈ A, so A is bounded below.
As noted above, A ƒ= ∅, so by Theorem 1.4, A has a greatest lower bound. Certainly inf A ≥ 0, since 0 is a lower bound for A and inf A is the greatest lower bound. Suppose for a contradiction that inf A > 0. Then, by the Archimedean Property of R, there exists n ∈ N such that 1/n < inf A, contradicting the fact that inf A is a lower bound for A. Hence, we must have inf A ≤ 0, so by the second positivity axiom, inf A = 0.
By the preceding lemma, if A has a minimum value, then min A = inf A. However, the minimum of a set must belong to that set whereas 0 ƒ∈ A, so min A cannot exist.
This proves that A has a maximum and a least upper bound given by max A = sup A = 1 as well as a greatest lower bound inf B = 0, but also that A has no minimum. □
(b)Proposition. Let B = {x ∈ R : x2< 2}. Then
sup B = √2 and inf B = −√2,
but max B and min B are undefined.
Proof. Let B = {x ∈ R : x2 < 2}. By §1.1 Exercise 17, the set B‘ = {x ∈ R : 0 ≤x and x2 < 2} = √B ∩ [0, ∞) has a positive least upper bound s such that s2 = 2; in other words, s = 2 = sup B‘.
Let x ∈ B. Then x ∈ B‘ or x < 0, and in b√oth cases, x ≤ √2.
This shows that √2 is an upper bound for B. In addition, if b <2, then there is an element y ∈ B‘ √⊂ B such that b < y (because every upper bound for Bj is greater than or equal to 2), so b is not an upper bound for B. That is, √2 is an upper bound for B and no real number less than √2 is an upper bound for B, so sup B = √2. 美国数学代写
Suppose for a contradiction that B has a maximum M . Then M ∈ B, so M 2 < 2. However, the preceding lemma shows that M = sup B, so it is also the case that M 2 = ( 2)2 = 2—a contradiction. Therefore, B does not have a maximum value.
We now consider inf B and min B. Recall from the proof of Theorem 1.4 that A is a lower bound for B is and only if −A is an upper bound for −B, where −B = {x ∈ R :−x ∈ B}. However, we have x ∈ B if and only if x2 < 2, which in turn holds if and only if (−x)2 < 2.
That is, x ∈ B if and only if −x ∈ B, so B = −B. Consequently,A i√s a lower bound for B if and only if −A is an up√per bound for B√, so it follows that− 2 is a lower bound for B.
In addition, if A > − 2, then −A < 2, so −A is not√an upper bound for B and, in turn, A is not a lower bound for B. T√his proves that − 2 is a lower b√ound for B and that no real number greater tha√n − 2 is a lower bound for B, so − 2 is the greatest lower bound for B: inf B = − 2. 美国数学代写
As before, we suppose for a contradiction that B has a minimum m. Then m ≤ x for all x ∈ B, so x ≤ −m for all x ∈ −B. However, since B = −B, this is equivalent to saying that x ≤ −m for all x ∈ B, and since m ∈ B, it follows that −m ∈ B; that is,−m is the maximum of B. This is a contradiction, as we already proved that B has no maximum value, so we conclude that B has no minimum value, either.
Hence, B has a least upper bound sup B = √2 and an greatest lower bound inf B =−√2, but it has neither a maximum nor a minimum. □
Common Issues
- In part (b), it isn’t immediately apparent that B = (−√2, √2). However, weshowed in the previous homework that, for x, y ≥ 0, we have x2 < y2 if√and only if x < y. Applying this reasoning to the set Bj = B ∩ [0, ∞) gives B‘ = [0, − 2), because taking the square root of each term in the inequalities 0 ≤ x2 <√2 gives 0 ≤ x < 2 and taking the square of each term in the inequalities 0 ≤ x <2.This is how we show that B‘ is precisely equal to the interval [0, √ 2).This level of detail wasn’t quite necessary, but I was looking for some acknowledgement of the fact that B is not equal to (− 2, 2) by definition, but rather, that this relies on deep facts about the real numbers that we put a lot of effort into proving beforehand.
Problem 2. §1.3 Exercise 25 美国数学代写
(a)If n is a natural number, then 2n> n.
Proof. We prove by mathematical induction. For the base case, recall that x+a < y +a for all x, y, a ∈ R such that x < y. Applying this result with x = 0, y = 1, and a = 1 gives
1 = 0 + 1 < 1 + 1 = 2.
Since 2 = 21, we have 21 > 1, thereby concluding the base case. 美国数学代写
For the inductive step, suppose that 2n > n for some n ∈ N. We know that 1 ≤ n, since 1 = min N, so we have 2n > 1 as well. Thus,
n + 1 < 2n + 1 < 2n + 2n = 2n(1 + 1) = 2n · 2 = 2n+1,
where we first used the fact that n < 2n and then the fact that 1 < 2n. Hence, we have shown that 2n+1 > n + 1, and this concludes the inductive step.
Having shown that 21 > 1 and that 2n+1 > n + 1 for all n ∈ N such that 2n > n, we conclude by the principle of mathematical induction that 2n > n for all n ∈ N. □
(b)Proposition.If n is a natural number,then
n = 2k0 A0 (2.1)
for some odd natural number A0 and some nonnegative integer k0.
Proof. Let n ∈ N. If n is odd, then—since x0 = 1 for all x ƒ= 0—we have n = 20n, so Equation (2.1) holds with k0 = 0 and A0 = n. 美国数学代写
Suppose instead, therefore, that n is even, i.e., that n = 2m for some m ∈ Z. If m < 0, then 2m < 0, and if m = 0, then 2m = 0. Both possibilities contradict the fact that
the natural numbers are all positive, so we must have m > 0; in particular, m is a positive integer, so it is a natural number.
Now let A = {k ∈ N : n = 2kA for some A ∈ N}. Then A ƒ= ∅, since we can take k = 1and A = m to conclude that 1 ∈ A.
We claim that A is bounded above. To see this, consider the natural numbers of the form 2jA, where j ≥ n and A ∈ N. Since A ≥ 1, we have 2jA ≥ 2j · 1 = 2j, and by part (a), 2j > j. Therefore, 2jA ≥ 2j > n whenever j ≥ n, so A does not contain any natural number that is greater than or equal to n. That is, n is an upper bound for A, so A is bounded above, and it follows from Proposition 1.7 that A contains a maximum.
Let k0 = max A, so that n = 2k0 A0 for some A0 ∈ N by the definition of A. We claim that A0 is odd and, consequently, that Equation (2.1) is satisfied with this choice of k0 and A0. Assume for a contradiction that A0 is even, so that A0 = 2A for some A ∈ Z.
We already showed that, since A0 is a natural number, A must be a natural number as well. We therefore have
n = 2k0 (2A) = (2k0 · 2)A = 2k0+1A,
so k0 + 1 ∈ A by the definition of A. However, k0 + 1 > k0, contradicting our choice of k0 as the maximum of A. Therefore, we reject our hypothesis that A0 is even and
conclude (since each integer is either even or odd) that A0 is odd. Hence, Equation (2.1) is satisfied with this choice of k0 and A0. 美国数学代写
First, we showed that the result holds given the additional hypothesis that n is even; next, we proved the result with the hypothesis that n is odd. Since every inte- ger—hence, every natural number—is either even or odd, we conclude that result holds for all n ∈ N. □
Remark. As noted in the hint, part (b) is trivial when n is odd. Hence, the upshot of part(b)is that, if n = 2m is an even number, then we can factor all the powers of 2 out of m to get n = 2 [power of 2] ·[odd].
Common Issues
- In part (a), it was common to assert that 21> 1 without explanation. Even if you do not write it out explicitly, you should be able to prove this: we have 21 = 2 by the definition of exponentiation, and since 1 > 0, it follows from adding 1 to both sides of the inequality 1 > 0 that 2 > 1.
- Also in part (a), it was common to assert that 2k ≥ k + 1 “because k ≥ 1.” This is fine, but again, you know be able to prove this from the ground up: we know that k + k = 2k (try proving this), so adding k to both sides of the inequality k ≥ 1 gives 2k ≥ k + 1. 美国数学代写
- In part (b), strong induction was a common It is not detrimental to have too many case cases, but only one was needed, whereas everyone seemed to usetwo base cases. More importantly, though, it was common for the inductive step to say something like, “Suppose that the proposition holds for all k ≤ n, where n > 2. We show that it is also true for n + 1.” Assuming that you showed the n = 1 and n = 2 cases as base cases, it is still necessary to assume that n ≥ 2, not that n > 2. To see why, consider the following “proof” by strong induction that all horses are the same color:
If H1 is a set containing 1 horse, then trivially, all horses in H1 are the same color.
Suppose for the induction hypothesis that all horses in Hk are the same color whenever |Hk| = k and k ≤ n, and let Hn+1 be a set containing n + 1 horses. Consider two distinct subsets A, B ⊂ Hn+1, each containing n horses.
Then all horses in A are the same color and all horses in B are the same color by the induction hypothesis. Since the sets A and B are distinct and contain n horses each, A ∩ B contains n − 1 horses, so the induction hypothesis implies that all horses in A ∩ B are the same color. Of course, the predicate “is the same color as” is transitive, and since each horse in Hn+1 belongs to at least one of A or B, we conclude that all horses in Hn+1 are the same color. By strong mathematical induction, we conclude that all horses are the same color.
If you can spot the error in this proof, if should convince you that the preceding remarks are not mere pedantry.
Problem 3. §1.3 Exercise 27 美国数学代写
Definition. A real number of the form m/2n, where m and n are integers, is called a dyadic rational .
Proposition. The set of dyadic rationals is dense in R.
Proof. Let (a, b) ⊂ R be an open interval, where a < b. Then 0 < b − a, so by the Archimedean Property of R, there exists n ∈ Z such that 1 < b − a. We know from Exercise 25 that n < 2n, so it follows that
(3.1)
Consider the real number c = 2nb − 1. By Theorem 1.8, there is a unique integer m such that m ∈ [c, c + 1), or equivalently, such that
2nb − 1 ≤ m < 2nb.
Dividing the expressions in these inequalities by 2n gives
(Note that this uses Proposition A.7 and the fact that 2n > 0.) However, (3.1) implies that −(b − a) < −1/2n, so it follows that
In particular, m/2n ∈ (a, b), and since a and b were arbitrary, we conclude that every open interval in R contains a dyadic rational m/2n for some m, n ∈ Z. This is precisely what it means for the set of dyadic rationals to be dense in R. □
Remark.
Theorem 1.8 provides the foundation for both Theorem 1.9 (the density of Q in R) and the result we just proved. Note the method used inboth:
(1)Choose a sufficiently small integer k (e.g., n or 2n) such that k is less than thelength of (a, b), and then “scale the problem” by a factor of k.
(2)Thedistance between kb − 1 and kb is exactly 1, so by Theorem 8, there is a unique integer m ∈ [kb − 1, kb). 美国数学代写
(3)“Scale the problem” back down by a factor of 1/k to get m/k ∈ 
Our choiceof k guarantees that
⊂ (a, b), so we are done.
By choosing a real number d ∈ (0, 1) ∪ (1, ∞) in advance and taking k to be of the form k = dn, we can use this same technique to show that the numbers of the form m/dn are dense in R (although some extra care is required if d ∈ (0, 1)).
Remark. This result is useful for simplifying certain geometric arguments. For example, one can define the Riemann integral (in one or multiple variables) using intervals (or squares, cubes, etc.) whose vertices are dyadic rationals rather than arbitrary real numbers.
