Department of Mathematical Sciences
Binghamton University

Math 330: Number Systems
Announcements

Section 01, Zaslavsky

Tests
More About Homework
Mathematical Language
Additions and Corrections to the Textbook
Chapter 1 2 3 4 5 6 8 9 10 11 12 13

Test Coverage and Grade Guidelines

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.

More About Homework

How to Prepare Homework Papers

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.

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.

How I Grade Homework

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.

Mathematical Language

(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.

Additions and Corrections to the Textbook

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.]

Chapter 1

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, x₁, x₂ in Z satisfy m + x = 0, then x₁ = x₂ .
(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.

Chapter 2

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).

Chapter 3

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.

Chapter 4

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 x₁ and you define x_n+1 (for n ≥ 1) recursively by the rule x_n+1 = (1/2)x_n if x_n is even, and x_n+1 = x_n + 1 if x_n 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 (a_j)_j=1^infinity and (b_j)_j=1^infinity are two infinite sequences of real numbers, and if a_j ≤ b_j for every j ≥ 1, then ∑_j=1^k a_j ≤ ∑_j=1^k b_j 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.)

Chapter 5

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 U_m = {my: y ∈ Z and my > 0} where m ∈ N.
U_m and W_m = {my: y ∈ Z and y > 0}, where m ∈ Z.
W₂, and W_m with m = 2.
V = {2y: y ∈ Z and 2y > 0}, and U_m 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.
1. The two-way comparison method, described in the "Template for proving A = B" on page 55.
2. 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.
1. Find an element in one that isn't in the other.
2. Restate them both in comparable ways (as in A2) that make the answer obvious.

Two ways to find the intersection of two sets:
1. Combine the defining properties and (as in A2) simplify.
2. Show the intersection is empty by proving that no element can be in both sets. (Of course, only if the intersection really is empty.)

"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.