Math 330: Number Systems
Announcements
Section 01, Zaslavsky
Main class page | Schedule and homework | Additional homework and projects | Announcements | Term Project | Syllabus
Contents
Midterm Test (Tues., Oct. 27)
Grading guidelines:
A B C D F
75-100 65-74 53-64 50-52 0-49
Individual problems: approximate guides:
1 9 7 5 3
2 14 11 8 7
3 13 12 8 6
4a 10 10 10 9
4b 10 10 10 10
5 5 0 0 0
6a 10 7 6 6
6b 5 3 1 1
7 10 10 10 10
Final Exam (Mon., Dec. 14)
Grading guidelines:
A B C D F
125-150 95-124 65-94 58-64 0-57
Individual problems: approximate guides:
1 1 1 1 1
2a 2 2 1 0
2b 6 5 4 3
2c 5 4 2 1
2d 6 5 4 3
3 15 11 7 2
4 8 6 4 2
5 15 12 9 7
6 14 12 9 7
7 10 8 6 4
8 61 49 37 28
Homework
Grading guidelines:
A B C D F
415-490 340-414 270-339 250-269 0-249
Each problem was worth a scale factor of 490/(162x11) times:
A B C D F - ?
11 9 6 3 1 0 4
A+ or A- is the same as A, etc.
? means there was no grade assigned; this is for problems that were left in the red-line status.
- means the problem was never handed in.
Explanation. The 490/(162x11) means that completely perfect homework would have had 1782 = (11 points) x (162 problems) total raw score, which has to be pro-rated out of the 490 points for homework. There were a total of 1000 course points: 490 for HW, 10 for quizzes, 150 for midterm, 200 for final, 150 for project.
Quizzes
Grading guidelines:
A B C D F
8-10 6-7 4-5 3 0-2
Term Project
Grading guidelines:
A B C D F
120-150 93-119 63-92 56-62 0-55
Each problem has a weight according to how important it is. The scoring is a bit complicated, but basically, using the homework point scale, you get full credit for a problem with an A, 9/11 credit for a B, etc.
Please follow these easy rules to help me grade your work. Thanks!
- Write each separate assignment on a separate paper. If you use more than one page for an assignment, staple the pages (other methods
don't work). I will no longer accept unstapled pages.
All homework is due at the beginning of class.
Not accepted at the end of class.
To make corrections, write a new solution starting from either the beginning or the first place you went wrong. Hand in the complete solution.
Don't give me the same solution with a few cross-outs and replacements. I can't grade it. (Thank you.)
- Remove all stubs from your papers, if you tore them out of a spiral binder. (They cause chaos!)
- Use complete sentences.
I will get more and more strict about this as the course progresses.
- In any proof: First, state what you are going to prove. Then prove it. Don't omit the final step.
- Revised papers: If there's plenty of space on the previous paper you may write the revision on it, but label it clearly! You may cut and
paste the good parts of the previous write-up.
- Get rewrites in as soon as possible.
There's no firm deadline but you'll have plenty of new work. Preferred but not required: the day after I
return them.
- You may submit each assignment up to four times.
-
Proofs: I'll read down until I find a significant error. I'll underline the error (it may be something missing) and stop there.
You should figure out what's wrong and fix it. If you can't figure it out and your friends can't help, please do come and ask. That's what office hours are for (and if you can't get to them, make an appointment to see me at some other time).
-
Writing: I will mark errors by circling them, including minor ones like grammatical and punctuation errors. Here are some common
ones. Don't worry; you'll get better as the term progresses.
- RUN-ON: A run-on sentence should be two or more separate sentences. It probably combines thoughts that should be separate.
- FRAG: A sentence fragment. Every sentence needs a subject and a verb. No exceptions. (Oops?)
- PUNC: Punctuation and capitalization.
- Use a CAPITAL letter at the beginning and a PERIOD (.) at the end of every sentence. That's how I identify different sentences.
-
Grades: I will give a grade (A, B, ...), usually only when the problem is basically solved or when the work is way off base. If you get a lower
grade than you like, such as B, then you may submit a rewrite. Your rewrite grade can be higher or lower than the original grade; if it's lower, there's
something new to learn – take advantage of that opportunity!
Many problems will get two grades.
- (M) marks the mathematics grade.
- (W) denotes the writing grade.
(Added late! 13 December 2009)
- In math, "unique" has a very precise meaning: "one and only one". It never means "different". If you mean "different", say "different", or "distinct" to mean "different from each other.
- "So" means "therefore". Throwing in random "so"s here and there will confuse your reader and get a lower grade.
- If you do mean "therefore", don't say "and". "And" does not mean "therefore". Good synonyms for "therefore" are "thus", "consequently", and so on.
- Pay attention to the difference between a subset and an element of a set. Can you explain the difference? If not, think about it carefully. (Then see the explanation at Chapter 5.)
Pay attention also to the difference betweeen the notations for a subset of a set, ⊆, and for an element of the set, ∈. (These symbols may not show correctly in all browsers.)
[Added after the semester.]
- Just to give it a name, let's say Axiom 1.0 is the following pair of axioms:
- Z is closed under addition (i.e., if x, y in Z, then x + y is uniquely defined in Z).
- Z is closed under multiplication (i.e., if x, y in Z, then x · y is uniquely defined in Z).
- There should be a Proposition 1.7½. For every m in Z, (−m) + m = 0.
- There should be a Proposition 1.8½. If m, n, and p are integers and n + m = p + m, then n = p.
- There should be a Proposition 1.9½. If m, x1, x2 in Z satisfy m + x = 0, then x1 = x2 .
(This means there is only one −m on the left as well as on the right.)
- If ... then ... statements. The discussion on pages 17-18 is very important but too short. We'll work on this (essential) topic in class.
- Proposition 1.20, proof. In the formulas, −m should have parentheses: (−m). E.g., x = (−m) + n. The notation −m + n is not defined yet. (We're being very careful!)
- Proposition 1.20, proof. The last sentence is wrong. Can you find the hidden assumption?
- The minus sign − is used in two different ways. −x means the negative (the additive inverse) of x; that is a unary operation (it acts on one number). y − x means y + (−x); this is a binary operation (it acts on two numbers). Don't confuse them; even though they use the same symbol (and they are somewhat similar), they are not the same thing.
- In this chapter, we use the integer operations defined in Chapter 1: addition, multiplication, and subtraction. (This doesn't include division; we have not defined division yet.) However, do not slow yourself down by going step-by-step the way we did in Chapter 1.
The focus in Chapter 2 is on properties related to induction, so we don't want to get distracted by details from Chapter 1. Don't worry, we'll get back to the Chapter 1 viewpoint soon.
In Chapter 2 we assume you know about polynomials and elementary algebra (as in the marginal note on page 25 about powers of k).
- Digits (page 24). This is not entirely correct. A "digit" is not a number, it's a symbol for a number – a single symbol, as contrasted with a multiple symbol like 10 or 209.
In the decimal system, the digits are 0, 1, ..., 9. These are called decimal digits. In the binary system, they are only 0, 1. These are called binary digits or bits. (Did you ever wonder what a "bit" is in computerese? And a "byte" is made up of 8 bits.)
In the hexadecimal system (base 16) they are 0, 1, ..., 9, A, B, C, D, E, F. If you're a computer hacker you probably know this. If not, can you figure out which numbers are meant by these 16 hexadecimal digits?
Do you know where this use of the word "digit" comes from? Did you ever hear of "digital dexterity"?
- On page 27, the Law of the Excluded Middle is not stated correctly. The law is: (Heart) must be either true or false.
(There are systems of advanced logic in which a statement may be neither true nor false, but something else. But we don't need these systems in our course.)
- On page 28, in the third paragraph, the book refers to a "direct" proof. This means a proof that does not use contradiction or the contrapositive.
- At the beginning of Section 2.4, the book refers to positive and negative numbers. It says "we have defined the positive integers", but actually we didn't. What we defined was the natural numbers. We'll define positive and negative numbers in this section, and we'll prove that the positive integers are the same as the natural numbers (Proposition 2.8). This is not a trivial fact, even though it seems obvious.
- If you want my opinion about the use of "negative" for both negative numbers and the negative of a number (which can be a positive number; the negative of −3 is a positive number): I think this is not unfortunate. Once you understand about the two uses of the word "negative", it should not be a problem for you.
(By the way, some people say "negative 3" for −3, and other people say "minus 3". "Minus 3" is the traditional name from hundreds of years ago. "Negative 3" is an invention of American high school educators from the 1960s, which in math is like last month (almost) (joke!).)
- Possibly the most important special case of Theorem 2.22 is where the induction starts at 0; that is, where m = 0. The special case where induction starts at 2 (that is, m = 2, as in Proposition 2.23) is also important.
- Warning about the Well Ordering Principle: It doesn't only say N has a smallest element. It applies to every subset of N except the empty set.
- Perhaps we should have, in addition to Theorem 2.25, also Corollary 2.25a. Any subset of Z that is bounded below has a unique smallest element. (Proving this is good mathematical brain exercise.)
- Remember the greatest common divisor, gcd(m, n)? Definition: It's the largest positive integer k such that k|m and k|n (k divides m and k divides n).
- Let's define logical equivalence. Two statements A and B are called logically equivalent if they are always both true or both false, but it can never happen that one is true while the other is false. Note that these statements may involve variables, like the statements P(k) in induction, so they may not actually be always true, or always false; by "logical equivalence" we mean that whenever one is true, the other must be true also – and similarly for falsehood.
The book (page 36, margin) defines "equivalence" of statements A and B, symbolized by the two-headed double arrow (page 36, bottom), as "A implies B and B implies A". We proved in class a theorem that these two definitions are themselves equivalent, i.e.:
Theorem 3.3½. A and B are "logically equivalent" if and only if they are "equivalent".
- Properties of the logical operations AND and OR. In order to analyze set intersections and unions (Chapter 5) you have to know how to manipulate logical expressions that combine AND, OR, and NOT. NOT is adequately handled in the book (Project 3.1). For AND and OR you should know the following rules. P, Q, and R are any statements.
Project 3.0. Convince yourself that the following logical laws are correct:
- P AND P is logically equivalent to P.
- P OR P is logically equivalent to P.
- P AND Q is logically equivalent to Q AND P.
- P OR Q is logically equivalent to Q OR P.
- (P AND Q) OR R is logically equivalent to (P OR R) AND (Q OR R).
- (P OR Q) AND R is logically equivalent to (P AND R) OR (Q AND R).
[Added after the semester.]
- Unique existence symbol. The book (see page 36) gives a definition of ∃! (existence symbol with !) that is not completely precise and
formal. Their definition is: "(i) AND (ii)". We can give a formal definition based on the book's definition on page 36:
Let P(x) be a property of x (e.g., for all x in Z). We say there is a unique x in Z such that P(x) if
[ (there is an x in Z such that) P(x) ] AND [ (for all x, y in Z) [ {P(x) AND P(y)} implies y=x ] ].
In symbols, if your browser supports the symbols:
[ (∃ x ∈ Z such that) P(x) ] AND [ (∀ x, y ∈ Z) [ {P(x) AND P(y)} ⇒ y=x ] ].
The first part is their (i) and the second part is their (ii). This is (and I'm sorry!) not exactly the same as my definition I gave in class, which was
(there is an x in Z such that) { P(x) AND [ (for all y in Z) [ P(y) implies y=x ] ] }.
Project 3L: Are these two different definitions logically equivalent? (The answer ought to be "Yes" – but is it?)
That's an optional problem, and I think it's challenging.
- Proving an "or" statement. Suppose you have two statements, P and Q. How can you prove the compound statement "P or Q"? (You also have some assumptions given to you, which you're supposed to use in the proof.) There are (at least) two usual methods.
Method 1. Go through your deduction, using the given assumptions, and at some points you'll have two cases, in one of which you prove P is true, and in the other one of which you prove Q is true.
Method 2. Assume P is false; add this hypothesis to the given assumptions. Then prove Q is true. (Of course, you could reverse the roles of P and Q.)
- Proving an "and" statement is much simpler. To prove "P and Q" you just prove P and also prove Q. That's two separate proofs.
- Example 4.2, the "3x+1 problem", is very mysterious. It shows how much more harder it can be to understand a sequence with a recursive definition than a sequence with a simple formula for each term as in example 4.1.
- We could make up similar problems. Consider the "x+1 problem". Here you start with any positive integer x1 and you define xn+1 (for n ≥ 1) recursively by the rule xn+1 = (1/2)xn if xn is even, and xn+1 = xn + 1 if xn is odd. Question. If you start with any positive integer, do you always get to 1 eventually? Hint: This problem is much easier than the 3x+1 problem. It's solvable!
- In Proposition 4.11 (i, ii), the index of summation should be j, not i: sum from j=1 to k.
- In Section 4.2, we should have
Proposition 4.14a. If (aj)j=1infinity and (bj)j=1infinity are two infinite sequences of real numbers, and if aj ≤ bj for every j ≥ 1, then ∑j=1k aj ≤ ∑j=1k bj for every k ≥ 1.
(We need this proposition in Chapter 12. Although we haven't proved it, I want you to use it freely in Ch. 12, because if you don't, you'll have to do extra work in Ch. 12 that's not appropriate to that chapter.)
- Pay attention to the difference between an element of a set and a subset of a set.
Suppose you have a set S. A subset of S is a set, and it is not (except in very unusual cases) one of the things that is in the set S. An element or member of S is one of the things that is in the set S; it is not necessarily a set, although it can be (since sometimes the elements of S might be sets themselves).
Pay attention also to the difference betweeen the notations for a subset of S, ⊆ (as in T ⊆ S), and for an element of S, ∈ (as x ∈ S).
[Added after the semester.]
- When reading or writing a set definition, pay attention to what is a variable inside the set definition and what is not a variable. As examples, how do the following pairs of sets differ?
- S = {n: n ∈ N}, and T = {n} where n ∈ N.
- R = {my: y ∈ Z, m ∈ N, and my > 0}, and Um = {my: y ∈ Z and my > 0} where m ∈ N.
- Um and Wm = {my: y ∈ Z and y > 0}, where m ∈ Z.
- W2, and Wm with m = 2.
- V = {2y: y ∈ Z and 2y > 0}, and Um with m = 2.
[Added after the semester.]
- Find the simplest possible way of writing each of the sets in the preceding problem.
[Added after the semester.]
- In comparing sets for equality or containment, there is usually more than one method that may help.
- There are (at least) two methods for showing two sets equal.
- The two-way comparison method, described in the "Template for proving A = B" on page 55.
- Transform the defining equations or properties of A until you get the description of B.
- There are two ways to show two sets are not equal.
- Find an element in one that isn't in the other.
- Restate them both in comparable ways (as in A2) that make the answer obvious.
- Two ways to find the intersection of two sets:
- Combine the defining properties and (as in A2) simplify.
- Show the intersection is empty by proving that no element can be in both sets. (Of course, only if the intersection really is empty.)
- Regarding partitions, we could add to Proposition 6.5 the following.
Corollary 8.5a. Given an equivalence relation on the set A, with equivalence classes [a], the set { [a] : a in A } is a partition of A.
(Proof hint: Use 6.4 and 6.5.)
- The first part of the remark preceding Project 8.8 should perhaps be a proposition, since it needs proof.
Proposition 8.7a. 1/x = x−1.
I advise you to use this freely in later work, even though we haven't proved it (it will save a lot of annoying and unimportant trouble).
- In Axiom 8.9(iv), the "either" does not mean exclusive or. Exclusivity is proved in Proposition 11; it isn't an axiom.
- The book has no definition of negative real numbers. Here it is:
A real number x is called negative if −x is in R>0 .
- In the proof of Proposition 8.10, we should not be using a later proposition! What we need here, instead of Proposition 8.11, is Axiom 8.9(iv).
- Notice that we have no
Proposition 8.11a. x > 0 if and only if x in R>0.
(And this is not a proposition you can use in proofs, unless you prove it yourself.) An equivalent statement is:
R>0 = { x in R : x > 0 }.
- Extra proposition:
Corollary 8.20a. If x in R<0, then 1/x in R<0.
- Proposition 8.19 is valuable. It could have been proved (for Z) in Ch. 2, and it would have been helpful several times then.
- Extra proposition:
Proposition 8.20b. If x, y in R>0 and x < y, then 0 < 1/y < 1/x.
- The definition of largest element on page 84 may not be clear. Let A be a nonempty subset of R and let b be a real number. We say b is the largest element of A if b is an upper bound for A and b is in A.
- The definition of least upper bound on page 84 may not be clear. Let A be a nonempty subset of R and let b be a real number. We say b is the least upper bound of A if b is an upper bound for A and for every upper bound u, b ≤ u.
- In Proposition 8.28, last sentence, what you need to prove is that max(A) = sup(A).
- Additional thoughts for Sect. 9.2. [These may not be used in proofs since we only looked at examples, without proof (and they're not part of the logical development in Ch. 9). We will be proving these in Ch. 13, if we have time. –Added after the semester.] The contrapositives are just as useful as the original statements (and that's true of proposition 9.5 and many other propositions in Ch. 9).
Note that these observations cannot be used in proofs because they are not proved.
- "Observations 9.4.6". Given sets B and C.
(i) If B is bigger than C, then no function g: B → C is injective. Contrapositive: If there exists a function g: B → C that is injective, then B is not bigger than C.
(ii) If B is smaller than C, then no function g: B → C is surjective. Contrapositive: If there exists a function g: B → C that is surjective, then B is not smaller than C.
(iii) "Corollary 9.4.6(iii)". If there exist an injective function f: B → C and a surjective function g: B → C, then B and C have the same number of elements.
"Corollary 9.4.8(iii)" is one reason we're so interested in injective and surjective functions.
- "Observation 9.4.7". For finite sets B and C, a function that's injective has to be surjective. (This is deep! I hope we'll be able to prove it later.)
- "Observation 9.4.8". For finite sets B and C, that need not be true! I gave examples of functions h: N → Z and g: Z → N such that h is injective and g is surjective. This proves (if you accept Observation 9.4.6(iii)) that the number of all integers equals the number of all natural numbers! But h is not surjective, contrary to Observation 9.4.7 (that's why Obs. 9.4.7 only applies to finite sets).
- "Proposition 9.4.9". Given functions f, g as in proposition 9.5.
(i) If g o f is injective, then f is injective. Contrapositive: If f is not injective, then g o f is not injective.
(ii) If g o f is surjective, then g is surjective. Contrapositive: If g is not surjective, then g o f is not surjective.
- Exactly how proposition 9.8(iii) follows from (i) and (ii) is not as simple as you might think.
- For the proof of proposition 9.12, I described one possible left inverse for e in class on T 11/17. That is the "greatest integer function". Can you think of a different left inverse for e?
- On page 96, after Theorem 10.1, "the possibility that the dots representing the natural numbers bunch up" is not the real problem. The real problem is that there might be a real number that is bigger than every natural number (whether or not the naturals "bunch up"). That is what Theorem 10.1 is proving cannot happen.
- Proposition 10.3 is not saying the same thing as the sentence preceding "In other words". I asked you to think about the difference.
- Add Proposition 10.6.1. For any x,y in R, |x| < |y| if and only if x2 < y2.
- Proposition 10.7 should have additional parts
- (v): |x| < y if and only if -y < x < y; and
- (vi): |x| ≤ y if and only if -y ≤ x ≤ y.
- Add Proposition 10.11(iii). limn → infinity 1/n = 0. (We proved this in class. It's useful in all kinds of examples.)
- Proposition 10.11a. For any real number r > 1, the sequence (rn)n=0infinity is unbounded above.
(This generalizes part of the proof of Proposition 10.11(ii).) (Prove 10.11a without using Bernoulli's inequality, Proposition 4.19. Proposition 4.19 is in Section 4.4, which we omitted. There is a proof that uses only properties we've studied.)
- Proposition 10.11b. For any real number r > 1, limn → infinity 1/rn = 0.
- Add Proposition 10.16(v). limn → infinity c = c.
- Outline of the proof of Theorem 10.18.
- Define the set A.
- Show that A has an upper bound.
- Define u = sup A.
- Show that u2 is not < 2.
- Show that u2 is not > 2.
- Deduce that u2 = 2. (In the book, this step is left for you.)
- Theorem 10.18a. The positive number u such that u2 = 2 is unique.
- Theorem 10.19a. Let r be any positive real number. The positive number u such that u2 = r is unique.
- Limits equal to infinity (Project 10.17). We don't treat these limits in this course. The reason is that they have a different definition. There are other kinds of limits too, which you saw in calculus. We aren't trying to treat all kinds of limits; instead, we want you to understand one kind of limit well. So, we'll only be working with limits that are real numbers; if there is not a real number limit, we'll say the limit does not exist.
- Add Proposition 11.0. Z is a subset of Q.
- In Project 11.14 we want a set that has an upper bound in the rationals but not a least upper bound in the rationals.
- The definition of a "series" on page 112 is wrong! A series is not a sequence; it's a (usually long) sum like
∑k=1m ak (a finite series) or ∑k=1infinity ak (an infinite series). An infinite series has two sequences associated to it:
the sequence of terms, which is (ak)k=1infinity, and
the sequence of partial sums, which is (sm)m=1infinity, where we define sm = ∑k=1m ak.
Keep these two sequences clearly apart! They're related but different.
- The "zeroth term" of a geometric series (p. 112) is also called the initial term. The initial term of a geometric series is always
the first term that appears in the series, whether its index (subscript) is 0, 1, or anything else.
- The "common ratio" of a geometric series (p. 112) is usually called the ratio, for short (though "common ratio" is a good name).
- On page 120, notice that we have not defined the "cardinal number" (or "cardinality") of a set. All we defined is the property of having the same cardinality.
Thus, in Sections 13.1-2 we cannot use any comparison of sizes or cardinalities of sets, such as "A is larger than B", or "A has more elements than "B". All we might possibly be able to say is that "A and B have the same cardinality". Any proof that depends on comparing different cardinalities is invalid.
- There should be a
Proposition 13.0. N is infinite. Furthermore, any countably infinite set is infinite.
(However, we don't have this proposition so you should not use it in proofs.)
- N.B. Proposition 9.5(iii) is used frequently in the proofs in this section, though it is not usually mentioned explicitly. See if you can detect all the places it's used.
- Before Proposition 13.7 here should be a
Proposition 13.7z. Any subset of a finite set is finite.
(However, we don't have this proposition so you should not use it in proofs.)
- Proposition 13.6a. A nonempty subset of N is finite if and only if it is bounded above.
(We don't have this proposition so you should not use it in proofs.)
Main class page | Schedule and homework | Additional homework and projects | Announcements | Term Project | Syllabus
"Where shall I begin?" he asked. "Begin at the beginning," the King said, "and stop when you get to the end."
—Lewis Carroll, Alice in Wonderland