Math 330: Number Systems
Announcements
Section 5, Zaslavsky · Spring 2015
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
Contents
Midterm Test (Tu 4/14)
The midterm will cover Chapters 1 - 6.
The format will be open-book, open-notes: you can have your textbook and notes, but no electronic devices (obviously?!). There will be some questions everyone should answer and possibly some questions you can choose from. (For instance, there might be 3 required questions and 4 other questions of which you choose 2 to answer—these may not be the actual numbers.)
Grading guidelines:
A B C D F
75-100 60-74 40-59 35-39 0-34
Final Exam (F 5/15)
The final exam will cover the entire course.
Grading guidelines:
A B C D F
90-150 65-89 40-64 35-39 0-34
I gave 10 points per problem in part I, for 60 points, and 30 points per solution in part II, for 60 points.
Grading guidelines:
A B C D F
60-100 45-59 25-44 20-24 0-19
Homework
Each problem was worth up to 20 points:
A+ A B C D F ? X
20 18 14 10 6 2 4 0
? means there was no grade assigned; this is for problems that were left in the red-line status.
X means the problem was never handed in.
The total for homework and quizzes was scaled to 50% of the course grade. There were 114 homework problems in toto so each one was worth 50/114 percent of
your grade. Quizzes were a tiny amount added on.
Quiz 1 (M 3/16).
Quiz 2 (W 3/18).
Quiz 3 (F 3/20).
Quiz 4 (W 4/8).
- Write precise definitions of
- a function,
- an injective function,
- a surjective function,
- a bijective function.
- What is your favorite movie? (No partial credit.)
Quiz 5 (F 4/24).
- In math, "unique" has a very precise meaning: "only one". It never means "different". If you mean "different", say "different", or "distinct" to mean "different from each other.
We often use "unique" as part of a phrase like "There is a unique ...". That means "There is one and only one ...".
- "Therefore" and non-synonyms.
- "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.
- The symbol ⇒ means "implies". The symbol ∴ means "therefore". They don't mean the same thing.
"A ⇒ B" means "If A is true, then B is true." It doesn't assert that A is true and it doesn't assert that B is true.
"A, therefore B", also written "A ∴ B", means "A is true, and therefore B is true." It does assert that A is true and it also asserts that B is true.
- "Assume" means "suppose for this discussion". It does not mean "I'm going to prove" or "This is a known fact".
- 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.
Pay attention also to the difference between the notations for a subset of a set, ⊆, and for an element of the set, ∈. (These symbols may not show correctly in all browsers.)
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
Chapter 1 2 3 4 5 6 8 9 10 11 13
- The distributive law is really two laws: one for the left and one for the right. The full name of Axiom 1.1(iii) is left distributivity. Proposition 1.6 is right distributivity.
- 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.
- Natural numbers vs. positive integers (page 14). I disagree with the book on the best definitions. The set of natural numbers is N, as in the book. A positive integer should be defined to be an integer that's > 0 (because positive means > 0).
Here's how I think we should do the definitions. We should define a set P =(def) {m ∈ Z : m > 0}. This is the set of positive integers. Then Proposition 2.3 says: P = N. (After this proposition we don't need the symbol P any more, because by the proposition, P is just another name for N.)
- Section 2.3, Induction should probably be called Mathematical Induction.
That's the full name of what we're doing here. There are other kinds of reasoning outside mathematics that are called "induction", for instance in science. They are not axiomatic or deductive logic, like mathematical induction, so don't assume any time anyone says "induction" they mean our kind of induction—unless they're math people.
- If n is an integer, we call n+1 the successor of n. The reason is that there are no integers between n and n+1, as we'll prove later.
- An application of Axiom 2.15: How do we know there are no natural numbers other than 1, 2, 3, ...? Axiom 2.15 tells us that. Proof.
Suppose we take A to be the set of all numbers you can get by taking 1, its successor 1+1 = 2, its successor 3, and so on all the way. Do we miss any natural numbers? No, because Axiom 2.15 tells us that set contains all of N.
(We can deduce using Prop. 2.16 that A is equal to N, but that isn't necessary for what I'm saying here.)
- Digits (page 19). 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.
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?
(Etymology: Do you know where this use of the word "digit" comes from? Did you ever hear of "digital dexterity"?)
- Possibly the most important special case of Theorem 2.25 (Mathematical Induction) is where the induction starts at 0; that is, where m = 0. The special case where induction starts at 2 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.
- The definition of gcd(m, n) in the book (page 22) is not the customary definition. Normally, gcd means "greatest common divisor" and is defined in terms of divisibility. However, that's not the definition to use in this book.
They want you to find the smallest element of the set S. Divisibility doesn't come into the statement of the problem or their definition of gcd.
- At the beginning of Section 3.1, the book describes the structure of a quantified statement (that is, a statement that has a quantifier or quantifiers). It says the statement consists of "quantified segments" (where variables are quantified) and a "final statement" (after all the quantifiers). I recommend a slightly different analysis (which is equivalent to theirs).
- The basic structure of a statement with a quantifier is that it has two parts ("segments").
- The first part is the quantification segment (or "range segment"). It states (a) the range of a variable, i.e., the set of possible values—for instance, "∀ x ∈ Z" or "∃ x ∈ Z" tells us x is an integer—and it also states (b) whether we are talking about all values (i.e., every value) of x (∀) or (at least) one value of x (∃).
- The second part is the property of that variable. For instance, "x is even", or "x2 ≤ 4".
For clarity we normally enclose the quantification segment in parentheses (or square brackets [] or curly brackets {}), and also (usually) enclose the property segment in parentheses. For instance, "(∀ x ∈ Z) (x is even)". (That happens to be false, but true or false, the structure of the statement is the same).
- The property of x can be complicated. It may include a quantified statement about another variable. For instance,
"(∀ x ∈ Z) [ (∀ y ∈ N) (x > y) ]",
or
"(∀ x ∈ Z) [ x < 1000 AND [(∃ y ∈ N) (x > y)] ]",
but no matter how complicated, it is a property of x.
- One reason quantification segments must be in order is that a statement with a quantifier should have one variable with one quantification segment and one property segment. The property segment may contain its own quantified statement, whose property can contain a third quantified statement, etc. These multiple statements are always nested within one another, so there's a natural order from inside to outside (or outside to inside, if you prefer).
- As the book says, there's a simplification when two (or more) variables have the same quantifier (universal, or existential). Then the order of quantification doesn't affect the meaning, so the quantification segments can be combined. However, that's just to make it more convenient for us. It may still be helpful to rewrite the statement according to the basic structure, where only one variable is quantified at a time (especially when negating the statement).
- Sometimes, it's possible to omit the brackets without causing confusion. If you're not sure how to interpret a quantified statement, you should start by figuring out where the brackets ought to be.
- Uniqueness in quantification requires care! This will be discussed in class. Summary: the correct format for the two parts (see top of page 28) is illustrated by this example:
{ (∃ n ∈ Z such that) (n has property P) } AND { if ([n1 has property P] AND [n2 has property P]), then (n1 = n2) }.
Watch the bracketing very closely!
- For Section 3.2, 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 28, margin) defines a different property, equivalence of statements A and B, symbolized by the two-headed double arrow ⇔ (read "if and only if"), as "A implies B and B implies A". That's our definition of ⇔. Whenever you use ⇔ as part of a statement, such as "A ⇔ B" ("A if and only if B"), the correct definition is "(A ⇒ B) AND (B ⇒ A)".
We could, but we don't, have a theorem that:
Theorem 3.2?. A and B are "logically equivalent" if and only if they are "equivalent".
(We might have time to prove it in class, but I think not.)
- 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.7). For AND and OR you should know the following rules. P, Q, and R are any statements.
Project 3.6?. 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).
- 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 alternative 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. (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.
- In Proposition 4.16 the sequences should be (xj)j=a∞ and (yj)j=a∞.
- In Proposition 4.17 it should be stated that a, a+r ≥ 1. (If not, then the summations are not both defined. Think about why not.)
- In Project 4.26 it should be stated that m, n ∈ Z.
- 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).
- 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? First, we define some sets:
- R = {my: y ∈ Z, m ∈ N, and my > 0}.
- S = {n: n ∈ N}.
- T = {n}.
- Um = {my: y ∈ Z and my > 0}.
- V = {2y: y ∈ Z and 2y > 0}.
- Wm = {my: y ∈ Z and y > 0}.
Now we state the pairs of sets to think about:
- S, and T where n ∈ N.
- R, and Um where m ∈ N.
- Um and Wm, where m ∈ Z.
- W2, and Wm with m = 2.
- V, and Um with m = 2.
Now, find the simplest possible way of writing each of the sets in the preceding list.
(The book used the previous version of these examples as the basis for Project 5.5.)
- In comparing sets X and Y 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 49.
- Transform the defining equations or properties of X until you get the description of Y.
- 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.)
- In Project 5.5(iii), do you think m is supposed to be the same m for both Vm and Wm? What is the range of m supposed to be?
The problem is not stated clearly enough. (It's my fault; I wrote the problem for them.) The sets should be defined before the subproblem (i, ii, iii) statements. The range of m should appear within each subproblem statement. For instance, (iii) should read:
"Vm and Wm for a specified m ∈ Z."
See the discussion above on "set definition".
- The definition of a partition on page 57 is missing an essential condition: No subset P ∈ Π can be empty.
- I define the degree of the zero polynomial as −1. Then I don't need to treat it as a special case in Proposition 6.18. Either my way or the book's way is acceptable.
- Proposition 6.18 is fine if the polynomials are real or at least rational (i.e., the coefficients are real rational numbers). Otherwise, q(x) and r(x) may not exist with the stated properties. It is also fine if all coefficients are integers and the divisor n(x) is monic. We'll assume the polynomials in the Division Algorithm for Polynomials are real or, if they are integral, they are monic.
- A "root" of a polynomial is also often called a zero of the polynomial, because it's a value of x that makes the polynomial take on the value 0.
- Here are some extra propositions that are interesting. They should not be used in proving propositions from the book.
- Proposition 6.23?. Let n ∈ N and m, k ∈ Z.
Write m = qn + r and k = pn + s using the division algorithm, so 0 ≤ r,
s < n. Then m is congruent to k (mod n) if and only if r = s.
(This proves that my equivalence relation =n is the same relation as their equivalence relation = (mod n).)
- Proposition 6.A. 1 is odd.
- Proposition 6.B. Suppose n ∈ N. If c ∈ Z and 0 < c < n, then c is not divisible by n.
- Here are the propositions derived from Prop. 6.18 that I presented in class.
- Proposition 6.19A. If you divide p(x) by x−a, the remainder is p(a).
- Proposition 6.19. (Alternate statement.) p(x) is divisible by x−a if and only if p(a) = 0.
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
- On pages 80, line 4 up, and 81, line 1, Proposition 8.32(ii) should be 8.32(iii).
- For Sect. 8.3, an instructive Example. Let
S = { x in R : x is a rational number and x ≥ √2 }
and let
T = { x in R : x is a rational number and x ≤ √2 }.
Then S has many lower bounds (think of one), but no infimum (greatest lower bound), in the rational numbers. Similarly, T has many upper bounds, but no supremum (least upper bound), in the rational numbers. The reason is that √2 is not a rational number (see the facts, below).
In the real numbers, the facts change! In the real numbers, √2 = inf(S), i.e., it is the greatest lower bound of S in the real numbers. And, √2 = sup(T), i.e., it is the least upper bound of T in the real numbers.
The purpose of this example is to show that Axioms 8.1 and 8.9 are not enough to specify the real numbers (since they're satisfied also by the rational numbers—and other systems). We need the Completeness Axiom, Axiom 8.32, to narrow down to the real numbers.
Facts used in the preceding example, but not proved at this time (they would take us off the subject).
- A rational number is a number that is the ratio (i.e., quotient) of two integers. (This is getting ahead of the logical development, but the rational numbers make a good example, so I'll just postpone all the proofs about them till later.)
- √2 is not a rational number.
- Proposition 8.50 should be stated differently: Proposition 8.50'. If A ⊆ B, and if sup(A) and sup(B) exist, then sup(A) ≤ sup(B).
- Example 9.5: See Section 5.4 for the definition of the graph of f.
- There is one property of Z that hasn't been proved of e(Z) (what the book calls "Z as a subset of R"). That is the following:
- Corollary 9.21. The Induction Axiom 2.15 is true for Z and N as subsets of R.
(Stated more precisely: it is true for e(Z) and e(N), which are actually subsets of R.)
- The proof of Theorem 10.1 could be simpler. We deduce the existence of a least upper bound u, as in the book. Now, u−1 is not an upper bound because u−1 < u, the least upper bound. Therefore, there exists a natural number n such that u−1 < n. Consequently, u < n+1. But then u is not an upper bound for N, which contradicts the definition of u. Therefore, the assumption that N has an upper bound in R must be false.
- What the book calls an increasing sequence (page 101) is usually called "weakly increasing" (or "non-decreasing"), while a sequence such that xk+1 > xk for all k is called "strictly increasing" (or "increasing").
Similar terminology ("weakly" or "strictly") is used for decreasing sequences.
- There should be a Proposition 10.18&12;. If (xk) is an increasing sequence, then i < j implies xi ≤ xj.
We haven't proved it, but it's so useful in proofs like 10.19 that we should use it (as the book does, without comment, in proving 10.19).
- The proof of Theorem 10.25 (page 104) is a bit sloppy (not seriously so) in spots. Here is how I would modify it:
- P. 104, line 5: "Thus every element in A is bounded above by 2." This has been proved only for x ∈ A such that x ≥ 1. We should also prove it for x < 1. Can you find an easy proof?
- In (a), line 3, "the distance between (u−h)2 and u2" is not u2 − (u−h)2, it is |u2 − (u−h)2|. Thus, to prove the distance is < δ, they ought to prove u2 − (u−h)2 > 0. The book is assuming we know that. In fact, a few lines later at (a), lines 7-8, they prove u−h < u, which we can use to prove (u−h)2 < u2. (Can you provide that proof?) If they had proved it sooner, they would have fixed this oversight.
- For (a), line 5, they again need the fact that (u−h)2 < u2.
- In (a), last line, the reason we have a contradiction could be stated more precisely as "u−h < u and u−h is an upper bound for A, ...". The fact that h > 0 is not the exact reason; it's that u−h is an upper bound which is < u. (Of course you realized what they meant.)
- P. 104, line 4 up: "By a similar argument as in" is bad English. Good English would be "By an argument similar to that in".
- Theorem 13.4 should be accompanied by a corollary: Theorem 13.4'. If a set X has the cardinality of [n] and also the cardinality of [m], where n, m ∈ Z≥0, then m = n. (I think this helps to explain the meaning of Theorem 13.4.)
- Proposition 13.13 has the corollary (which I think is the main result):
Proposition 13.13'. Z is countably infinite.
(Why is it not finite? There are proofs (1) using Proposition 13.6 and (2) using a bijection N → Z.)
Main class page | Schedule and homework | Announcements | Term Project | Syllabus