Math101 Selected Solutions for Problem Set 4

Thomas Allen and Stefan Karpinski November 16, 1999

Problem N 3.3.1

Let A ⊂ B ⊂ ℝ^{n}. Take x ∈ KA. For every ϵ > 0, there exists an a ∈ A ⊂ B such that d(x, a) < ϵ. So, x ∈ KB, by definition. Therefore,KA ⊂ KB.

Now, note that A ∩ B ⊂ A ⇒ K(A ∩ B) ⊂ KA. Similarly, for KB. So, K(A ∩ B) ⊂ KA ∩ KB.

Problem W 6.2.2

Part (a) No, not symmetric Part (b) Yes Part (c) Yes Part (d) No, not transitive. Part (e) Yes Part (f) No, A ⊂ ℝ may not have a smallest member. So, not reflexive.

Problem W 6.2.4

Some common answers and mistakes Part (a) |a − b| < 1 Part (b) a ≤ b Part (c) A common mistake included a proof that symmetric and transitive implies reflexive. While it is true that symmestric and transitive implies reflexive for the elements contained in R, it does not give you reflexivity for all x ∈ A. Consider:

R = {(x, y) ∈ ℕ^{2}|x ≤ y} − {(x, y)|x = 1 or y = 1}.

This does not contain (1, 1).

Part (d) 0 ≤ a − b ≤ 1

Part (e) a ≠ b

Part (f) a < b

Part (g) a = 2b

Problem W 6.2.8

The relation is clearly reflexive and symmetric. The main issue comes down showing that the relation is transitive. First, suppose (a, b) (c, d) and (c, d) (e, f) ⇒ ad = bc and cf = de ⇒ adf = bcf ⇒ adf = bde ⇒ d(af − be) = 0. But, d ≠ 0 by construction, so af −be = 0. Thus we have af = be or (a, b) (e, f), as desired. Many people tried to use division (i.e. multiplication by inverses). However, since we’re working entirely inside ℤ, which doesn’t have multiplicative inverses, this is no good.

Problem W 6.3.20 and 6.3.21

For a “critique” of a proof you must first determine whether the proof is correct or not. If the proof is correct you need only state that it is correct and briefly explain why the proof is in fact legitimate at each possible point of concern. If the proof is incorrect (or incomplete) you need to pinpoint precisely where it goes wrong and explain why it is wrong. Commentary on style and philosophical concerns is not required.

The proof in 20 is in fact correct. The biggest possible concern is over the disjointness of R and S: because of this the relation R∪S has the property that for any x ∈ A and y ∈ B neither (x, y) nor (y, x) is in R∪S. However this is not a difficulty for the proof given in problem 20 since we are only trying to prove that R ∪ S is a partial ordering. However for problem 21 it is a big problem. The proof asserts “since R is total on A and S is total on B, R ∪ S is total on A ∪ B′’ but there is no reason for this at all—in fact by the above observation, unless A = B = ∅ the ordering R ∪ S cannot be total on A ∪ B.

Problem W 8.2.12 (not assigned but I did it by accident)

The technique here is an important and common one. We take a minimal element of some sort (in this case the least common multiple of two integers). Then we assume that the proposition is not true and use this to show that our minimal element cannot in fact be minimal, yielding a contradiction.

Let l be the least common multiple of n and m.I.e. let l be the least positive integer such that both n and m divide l. Now suppose that there exists some k which is a common multiple of n and m but such that l does not divide k (without loss of generality, we can let k be positive since we can always replace k by −k). Since we picked l to be minimal, we know that l < k. Thus we may use the Euclidean algorithm, more commonly known as division with remainder. I.e. we may find positive integers q and r (why do we know that they’re both non-zero?) such that r < l and

k = ql + r.

Thus we may also write r as k −ql. But since both n and m divide k and l, they must also divide r but r < l, contradicting the minimality of l as a common multiple of n and m.

Problem W 8.3.13

Two integers m and n are said to be relatively prime if there exist integers k and l such that mk + nl = 1. This is equivalent to m and n having no common factors other than 1. (More generally, the least common factor of m and n is the smallest positive integer of the form mk + nl.) But

∃ l s.t. mk + nl = 1 ⟺ mk ≡ 1 (mod n)

Thus the existence of an inverse for m in ℤ_{n} is equivalent to the relative primality of m and n. Now, since primes are relatively prime to everything but multiples of themselves (i.e. numbers that are ≡ 0 (mod p)), in particular, a prime p is relatively prime to every m such that 0 < m < p, so each such m is invertible in ℤ_{p}.

Problem W 8.3.15

Part (a) An important idea to use here is that the order of an element divides the order of the group it is contained in. Therefore, if a^{d} = 1, then d|3 (3 = |𝔽_{4} - {0} | ). So, d = 1 or 3. But, a ≠ 1, so d = 3 and a^{3} = 1. So, a^{(−1)} = a^{2}. This fact allows for the completion of both tables.

Problem W 9.5.4

Part (a) Suppose cn < dn and n > 0. Then n(c − d) < 0. But, n > 0 ⇒ c − d < 0. So, c < d. Therefore, if we have a < b and b < c, then ab < bc (assuming b > 0, which you can do wlog). The lemma ⇒ a < c, as desired.

Part (b) Division is not defined for ℤ since there are no multiplicative inverses (for z ≠ ±1).