Homework involves working through new ideas, not adapting examples, so there are rarely models to follow. However, the Practice Problems in the course notes on Blackboard (which you should conscientiously work through (not just read) before doing the homework) can and should serve as models of how to write solutions and they can help you absorb the relevant ideas for the homework. The homework solutions that will be posted on Blackboard can also serve as models for future assignments.  Solutions must be written in paragraphs, with each paragraph consisting of complete sentences written in standard English, supplemented with mathematical notation. Equations that are (a) particularly important, (b) long, or (c) that would otherwise be split between two lines, should be put in display mode (between a matching pair of $$ signs in LATEX). Other than properly using display mode, you should not do anything to force line breaks (that is not done in English prose writing). Most homework problems have fairly short solutions. On the one hand, make sure that your solution is complete (the top priority); on the other hand, aim to get directly to the heart of the matter (needlessly long solutions can be a symptom of not having the key ideas or not distinguishing the main ideas from the details). See Chapter 0 of the course notes for guidance on writing. LATEX templates are provided for each assignment; using them will save you work and will show you the correct LATEX code for the symbols that you need.

Due dates at a glance:

. Monday, September 26: Homework 3                              . Monday, November 21: Homework 8

. Monday, October 3: Homework 4                                     . Wednesday, November 30: Homework 9

. Monday, October 10: Homework 5                                   . Wednesday, December 7: Homework 10

Homework 1 — Due Monday, September 12

(1)  Consider the following theorem.

Theorem. Let P be a point inside a triangle ABC. Through P and, in turn, each vertex of ABC, draw a line that meets the side opposite the vertex, giving the points X on the side AB, Y on the side BC, and Z on the side AC, as shown in the figure below. Then the lengths of the six resulting line segments satisfy

AX    BY   CZ XB . YC . ZA

A

= 1.

B                    Y          C

Below is a jumbled proof of this theorem.  Construct a proof of the theorem by properly (a) matching the beginnings and endings of the incomplete sentences (denoted with . . .) and (b) putting the sentences in order so that the argument follows logically. In particular, you need to think carefully about which items need to be said before others so that the latter make sense and are evident.  (We use l△ABCl to denote the area of the triangle ABC.)

. . . since the two triangles have the same height. Similarly

BY l△BAP l

=

YC      l△ACP l

Therefore

AX     XB =

and = .

l△ACP l

l△CBP l . . .

. . . by taking differences.

Therefore

l△APXl AX

=

l△XPBl     XB . . .

The terms cancel, so we get 1, as needed.

Similarly,

l△ACXl AX

=

l△XCBl     XB .

Recall that the area of a triangle is half the base times the height.

Therefore

AX BY CZ l△ACP l l△BAP l l△CBP l

XB . YC . ZA = l△CBP l . l△ACP l . l△BAP l .

(2)  Carefully read through Section 1.3 of the notes, watch the three videos on Blackboard on this material, and work through the Practice Problems there (seriously try to solve those problems before reading the solutions). Then do problems (a)–(c).

(a)  Give an argument (not using Venn diagrams) to prove that for any three sets A, B , and C, we have

(A u B) _ C C (A _ (B u C)) u (B _ (A n C)).

(b)  Using the labels on the regions in the Venn diagram shown below,

(i)  list the regions that should be shaded in order to represent (A u B) _ C,

(ii)  list the regions that should be shaded in order to represent A _ (B u C), and (iii)  list the regions that should be shaded in order to represent B _ (A n C).

(c)  Does the equality (A u B) _ C = (A _ (B u C)) u (B _ (A n C)) hold for all sets A, B , and C? If so, prove it; if not, give three sets for which the equality fails.

● Before working problems (3) and (4), seriously try to solve the Practice Problems in Section 1.4 of the course notes on Blackboard (put in serious effort before reading the solutions).

(3)  (i) Prove that for all real numbers x and y, the inequality      xy < ╱ 、2

holds. (ii) Prove that equality holds in this inequality if and only if x = y . (iii) By interpreting each side of the inequality, deduce which rectangle, among those with a fixed perimeter, has the greatest area. (Use only this inequality; do not use calculus. If you think about the inequality carefully, the answer is just a matter of interpreting what it says.)

(4)  Show that for any positive numbers a and b,

min ╱ , 、< 2 < max ╱ , 、.

(The two sides refer to the minimum (min) and the maximum (max) of the pair of numbers. For a numerical example, min(3, 5) = min(5, 3) = 3 and max(3, 5) = max(5, 3) = 5.)

Homework 2 — Due Monday, September 19

● Before working the problems below, seriously try to solve the Practice Problems in Sections 1.5 and 1.6 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Show that if the triangular number tn is the square of some integer, then t4n(n＋1)  is also a square.

(2)  If the following statement is true, prove it; otherwise, give a counterexample to the claim.

For any positive integer n, there is an integer k with n3  < k2 < (n + 1)3 ; that is, between any successive cubes, there is a square.

(3)  Prove the following statement. For integers m and n, the difference m3 _ n3 is even if and only if m _ n is even.

(4)  Prove that for any three sets A, B , and C, we have A _ (B _ C) = (A _ B) u (A n C). % begincenter

Homework 3 — Due Monday, September 26

● Before working the problems below, seriously try to solve the Practice Problems in Sections 1.7 and 1.8 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Put the jumbled sentences of the proof of the statement below in the correct logical order so that the proof makes sense.  In particular, you need to think carefully about which items need to be said before others so that the latter make sense and are evident.  (The statement is a biconditional statement, so the proof comes in two parts, namely, a proof of each conditional statement.  Sentences are jumbled only within each part (conditional statement) separately, not between the two parts.)

Assertion. For any sets A and B, we have p(A)up(B) = p(AuB) if and only if either A C B or B C A.

● First we prove that if p(A) u p(B) = p(A u B), then either A C B or B C A. From B C A u B and A u B C A, we get B C A.

If A u B e p(A), then A u B C A.

Thus, either A C B or B C A.

From A C A u B and A u B C B , we get A C B .

Therefore either A u B e p(A) or A u B e p(B).

If A u B e p(B), then A u B C B .

Since A u B e p(A u B), from the assumed equality we get A u B e p(A) u p(B).

● Next we prove that if either A C B or B C A, then p(A) u p(B) = p(A u B). Therefore p(A) u p(B) = p(B) = p(A u B).

Thus, p(B) C p(A).

Then A u B = B , so p(B) = p(A u B).

Also, if X e p(A), then we have X C A and A C B , so X C B , and so X e p(B). Thus, p(A) C p(B).

If A C\ B , then B C A.

Thus, A u B = A, and so p(A) = p(A u B).

Assume that A C B .

Also, if X e p(B), then we have X C B and B C A, so X C A, and so X e p(A). Therefore p(A) u p(B) = p(A) = p(A u B).

(2)  Using the Venn diagram below,

(a)  list the regions (by number) that should be shaded to represent A n (B u C), and (b)  list the regions (by number) that should be shaded to represent (A n B) u C.

Then

(c)  use those results to figure out the correct way to complete the statement below,

For sets A, B, and C, we have An(BuC) = (AnB)uC if and only if , and

(d)  prove that your answer is correct. (Give an argument; do not use Venn diagrams or tables.)

(3)  Assume that f : A → X is a function, that B and C are subsets of A, and Y and Z are subsets of X . One of the points of the problems below is to get you familiar with using the definitions of images and preimages (which we defined in class and in the notes). Make sure you use the definitions, and do not confuse preimage (which makes sense for any function) with inverse (which exists only for bijections).

(a)  Prove that f(B n C) C f(B) n f(C).

(i)  Give an example showing that the inclusion can be proper, that is, f(B n C) f(B) n f(C).

(ii)  Determine whether equality must hold if we assume that f is injective; justify your answer with a proof or a counterexample.

(iii)  Determine whether equality must hold if we assume that f is surjective (not necessarily injective);

justify your answer with a proof or a counterexample.

(b)  Prove that f - 1 (Y u Z) = f - 1 (Y) u f - 1 (Z).

(4)  Is the following statement true for all functions f : A → B and g : B → A? If g(f(x)) = x for all x e A, then g is injective.  Provide a proof if you claim that this statement is correct; provide a counterexample if you claim that this statement is false.

Homework 4 — Due Monday, October 3

● Before working problems (2)–(3) below, seriously try to solve the Practice Problems in Sections 2. 1 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Let f : A → X be a function and let B be a subset of A. (a)  Prove that B C f - 1 (f(B)).

(b)  Give an example showing that the inclusion can be proper, that is, B f - 1 (f(B)).

(c)  Determine whether equality must hold if we assume that f is injective; justify your answer with a proof or a counterexample.

(d)  Determine whether equality must hold if we assume that f is surjective (not necessarily injective); justify your answer with a proof or a counterexample.

(2)  Use induction to prove that for every positive integer n,

1 + 1 + 1 + . . . + 1 < 2 _ 1

(3)  Use induction to prove that for every positive integer n, when we factor the product

(n + 1)(n + 2) . . . (2n _ 1)2n

into primes, there are exactly n copies of the prime 2.

(Note: like similar formulas for sums (for instance, triangular numbers), the product above indicates where to start, n + 1, and where to stop, 2n. For n = 1, we start at 2 and end at 2, so the product is 2; for n = 3, we start at 4 and end at 6, so the product is 4 . 5 . 6.)

Homework 5 — Due Monday, October 10

● Problem (3) uses induction (Section 2. 1 in the course notes); problem (4) uses strong induction (Section 2.3); try to solve the Practice Problems in those sections before doing these problems (put in serious effort before reading the solutions).

(1)  Is it true that for all subsets A and B of a set U, there is a subset X of U for which A△X C B△X? If there is such an X , then prove it (in particular, say what X can be, and prove your assertion); if there can fail to be such an X , then give an example where there is no such X .

(2)  Is the following statement true for all sets A, B , and C? If A C B , then A△C C B△C. Provide a proof if you claim that this statement is correct; provide a counterexample if you claim that this statement is false.

(3)  Use induction to show that for any sets A1 , A2 , . . . , An with n > 2, the iterated symmetric difference

(*) ╱ . . . ╱(A1 △A2 )△A3、△ . . . 、△An

consists of the elements that are in an odd number of the sets A1 , A2 , . . . , An  (either in exactly one of the sets, or in exactly three of the sets, or in exactly five of the sets, or . . .).

(To help clarify the question in your mind, it is useful to draw the Venn diagram for the case n = 3. Also, work out (for yourself, not as part of the solution), step-by-step, what

╱ ╱ ╱{a, b, c, d, e}△{a}、△{a, b, c, d}、△{a, b, c}、△{a, b}

is. Equation (*) gives the general term in the sequence A1 △A2 , (A1 △A2 )△A3 , ((A1 △A2 )△A3 )△A4 , and so on.  Sometimes setting up useful notation can help significantly when addressing a problem, and in this problem, one way to recast the set of interest is as follows:  set B2  = A1 △A2  and for i with 3 < i < n, set Bi = Bi - 1 △Ai ; the set of interest is Bn . A corollary of this problem is that the symmetric difference A1 △A2 △A3 △ . . . △An does not depend on the order of the terms or how we insert parentheses.)

(4)  Below are the steps in a proof, by induction, of the following assertion.

Assertion. For each positive integer n and each integer a with 1 < a < n!, the integer a can be written as a sum of distinct (that is, unequal) divisors of n!, using at most n such divisors.

The sentences in the proof are jumbled.  Put the sentences in the correct order so that the proof makes sense. In particular, you need to think carefully about which items need to be said before others so that the latter make sense and are evident.

Note that d1 k, d2 k, . . . , ds k, r are distinct since d1 , d2 , . . . , ds  are distinct and r is the only term that is less than k.

Thus, qk = d1 k + d2 k + . . . + ds k and d1 k, d2 k, . . . , ds k are distinct divisors of k!, all are multiples of k, and s < k _ 1.

Now we have a = qk + r = d1 k + d2 k + . . . + ds k + r and, since s < k _ 1, there are at most k terms in the sum.

By the division algorithm, dividing a by k, we have a = qk + r for some unique integers q and r where 0 < r < k.

Now assume that for some positive integer k _ 1, each integer a with 1 < a < (k _ 1)! can be written as a sum of distinct divisors of (k _ 1)!, using at most k _ 1 such divisors.

Thus, we have verified the claim in case k, using case k _ 1, so the statement is true by induction.

If r = 0, then we have the desired conclusion; otherwise, 1 < r < k, and r is a divisor of k!. For case k, consider a with 1 < a < k!.

Thus, the inductive hypothesis applies to q, so q = d1 +d2 + . . . +ds for some distinct divisors d1 , d2 , . . . , ds of (k _ 1)!, where s < k _ 1.

In the base case n = 1, the only integer a with 1 < a < 1! (namely, a = 1) is a sum, with just one term, of distinct divisors of 1!.

Since a < k!, we have q < (k _ 1)!.

We induct on n.

Homework 6 — Due Monday, October 31

● Before working the problems below, seriously try to solve the Practice Problems in Sections 3. 1–3.4 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Prove that if a, b, and c are odd integers, then the polynomial p(x) = ax45 + bx19 + c has no rational root, that is, there are no integers s and t with p(s/t) = 0.  (You should also think about using the idea in your argument to prove a more general result, but you do not have to write up the more general result.)

(2)  Let S be a set of rational numbers that has the following properties: (A)  if a and b are in S, then ab and a + b are in S, and

(B)  for each a e Q, exactly one of the following statements holds: (i) a = 0, (ii) a e S, or (iii) _a e S. Prove that (a) 0 e/ S, (b) N C S, and (c) S = {r e Q  : r > 0}.

(3)  Assume that S = {k1 , k2 , . . . , kn } is a set of n different integers, all greater than 1, and that x1 , x2 , . . . , xm is a list with m entries, where m > 2n and each xi is in S. Prove that at least one product xi . xi＋1 . xi＋2 . . . xj of consecutive terms in the list is a perfect square.  (For instance, if S  =  {3, 7, 8}, then one such list is 8, 7, 8, 3, 8, 7, 3, 7 and the product of the last six entries is (3 . 7 . 8)2 .)

(4)  Recall that p(U) is the set of all subsets of U. For a subset A of a set U, let f : p(U) → p(U) be given by f (X) = A n X . Must the function f be surjective? If so, then prove that it is surjective; if not, then give a counterexample and identify precisely the additional conditions under which f would be surjective.

Homework 7 — Due Monday, Monday, November 7

● Before working the problems below, seriously try to solve the Practice Problems in Sections 3.5–3. 10 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Consider the following property that a function f : R → R may or may not have: For allfunctions g : R → R,

if lim g(x) does not exist, then lim╱f (x) + g(x)、does not exist. Prove that f (x) has this property if and only

if lim f (x) exists. (You can use the standard properties of limits that you know from calculus; the relevant

(2)  Decide whether each of the statements below about sequences of real numbers is true. Prove the statements that are true and give counterexamples to the statements that are false. These problems use the definition of what it means for a sequence to be bounded, which we reproduce here for your convenience.

A sequence a〇 , a1 , a2 , . . . of real numbers is bounded if there is a real number M so that, for all n > 0, we have lan l < M.

(a)  If the sequences a〇 , a1 , a2 , . . . and b〇 , b1 , b2 , . . . are both bounded, then, a〇 + b〇 , a1 + b1 , a2 + b2 , . . ., the sequence of sums, is bounded.

(b)  If the sequences a〇 , a1 , a2 , . . . and b〇 , b1 , b2 , . . . are both unbounded, then a〇 + b〇 , a1 + b1 , a2 + b2 , . . ., the sequence of sums, is unbounded.

(c)  If the sequences a〇 , a1 , a2 , . . . and b〇 , b1 , b2 , . . . are both bounded, then a〇 . b〇 , a1 . b1 , a2 . b2 , . . ., the sequence of products, is bounded.

(d)  If the sequences a〇 , a1 , a2 , . . . and b〇 , b1 , b2 , . . . are both unbounded, then a〇 . b〇 , a1 . b1 , a2 . b2 , . . ., the sequence of products, is unbounded.

Homework 8 — Due Monday, Monday, November 21

● Before working the problems below, seriously try to solve the Practice Problems in Section 5. 1 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Show that in a projective plane (P, c) of order q, the number of lines, lcl, is q2 + q + 1.

(2)  Let (P, c) be any projective plane. For each point a e P, set ca  = {L e c  : a e L}, and let cP be the set of all such sets, that is, cP  = {ca   : a e P}. Show that the pair (c, cP ) is a projective plane.

(3)  Thirty chairs are evenly placed around a circular table. On the table are the name cards of thirty guests. After the guests sit down, it turns out that no one is sitting in front of his or her own card. Prove that the table can be rotated so that at least two guests are simultaneously correctly seated.

(4)  Answer the following questions about a function f : A → B .

(a)  Prove that if f is injective, then f (Y _ X) = f (Y) _ f (X) for all sets X and Y with X C Y C A.

(b)  Without the assumption that f is injective, must the inclusion f (Y _ X) C f (Y) _ f (X) hold for all sets X and Y with X C Y C A?  Justify your claim with either a proof that the inclusion holds or a counterexample showing a case where it fails.

(c)  Without the assumption that f is injective, must the inclusion f (Y) _ f (X) C f (Y _ X) hold for all sets X and Y with X C Y C A?  Justify your claim with either a proof that the inclusion holds or a counterexample showing a case where it fails.

Homework 9 — Due Wednesday, November 30

● Before working the problems below, seriously try to solve the Practice Problems in Section 5.2 of the course notes on Blackboard (put in serious effort before reading the solutions).

(1)  Let ~1 and ~2 be two equivalence relations on the same set A. Assume that there are at least two equivalence classes for ~1 , and that any two elements that are in different equivalence classes of ~1  are in the same equivalence class of ~2 . As completely as possible, describe the equivalence classes of ~2 , and prove your assertion.

(2)  The following argument attempts to show that a relation ~ on A that is both symmetric and transitive is also reflexive.

Given a e A, from a ~ b and symmetry we get b ~ a. From both a ~ b and b ~ a, transitivity gives a ~ a. Thus, a ~ afor all a e A, so ~ is reflexive.

● Find an example that shows that the assertion is false; that is, find a relation that is symmetric and transitive but not reflexive. (You can give the example as a set of ordered pairs.)

● Identify precisely the flaw in the argument. (The flaw is not that the conclusion is false; instead, it is some statement or implicit assumption in the attempted proof that is not justifiable.  You need to identify that unjustifiable statement. Examine every small step in the proof and ask yourself whether it is valid.)

(3)  Is the following statement true for all sets A, B , C, and D? If A x B C C x D, then A C C and B C D. Provide a proof if you claim that this statement is correct; provide a counterexample if you claim that this statement is false.

(4)  On Homework #8, you showed that if f : A → B is injective, then f (Y _ X) = f (Y) _ f (X) for all sets X and Y with X C Y C A.

State the converse of this result.

(b)  Determine whether the converse is true. If you claim that it is true, then prove it. If you claim that it is false, then give a counterexample showing a case where it fails.

Homework 10 — Due Wednesday, December 7

● Before working the problems below, seriously try to solve the Practice Problems in Section 5.3 of the course

notes on Blackboard (put in serious effort before reading the solutions).

The first two exercises differ in exactly one crucial word, which is highlighted.

(1)  Assume that (A, 31 ) and (A, 32 ) are ordered sets on A. Let a relation 3 on A be given as follows: a 3 b if and only if a 31  b and a 32  b.

Is (A, 3) an ordered set? Either prove that it is an ordered set or give a counterexample.

(2)  Assume that (A, 31 ) and (A, 32 ) are ordered sets on A. Let a relation 3 on A be given as follows: a 3 b if and only if a 31  b or a 32  b.

Is (A, 3) an ordered set? Either prove that it is an ordered set or give a counterexample.

(3)  Assume that the sets A1 , A2 , . . . , A1982 have the following two properties:

(i)  lAi l = 45 for each i with 1 < i < 1982, and

(ii) lAi n Aj l = 1 for each pair i and j with 1 < i < j < 1982.